Scratch学习课件-08_链表简介.ppt

08链表简介 程序设计基础 本节目标 链表及其操作常见数据结构 链表及其操作2 1 手工方式新建和删除导入和导出数据添加删除元素显示和隐藏改变显示大小命令方式见下页 链表及其操作2 2 链表应用练习2 1 新建链表chengji 通过程序清空链表所有元素提示用户输入5个数字 并将数字保存到链表计算输出所有链表元素的和 最大值 最小值和平均值 链表应用练习2 2 链表元素输入 查找计算 数据结构3 1 数据结构是计算机存储 组织数据的方式 数据结构是指相互之间存在一种或多种特定关系的数据元素的集合 通常情况下 精心选择的数据结构可以带来更高的运行或者存储效率 数据结构往往同高效的检索算法和索引技术有关 数据结构3 2 一个数据结构是由数据元素依据某种逻辑联系组织起来的 对数据元素间逻辑关系的描述称为数据的逻辑结构 数据必须在计算机内存储 数据的存储结构是数据结构的实现形式 是其在计算机内的表示 讨论一个数据结构必须同时讨论在该类数据上执行的运算才有意义 数据结构3 3 常见数据结构集合数据元素除了同属于一种类型外 别无其它关系线性结构线性结构中元素之间存在一对一关系树形结构树形结构中元素之间存在一对多关系图形结构 网状结构 图形结构中元素之间存在多对多关系 集合 性质由一组相同数据类型的成员组成同一集合的成员必须互不相同集合中的成员一般是无序的 没有先后次序关系应用举例实现一个生字本 记录不熟悉的英语单词 同一单词只记录一次 线性结构6 1 性质除起始元素外 线性表中的其他元素仅有一个直接前驱元素除终端元素外 线性表中的其他元素仅有一个直接后继元素应用举例输入并保存班级英语成绩 计算平均成绩 线性结构6 2 分类1 数组 Array 在程序设计中 为了处理方便 把具有相同类型的若干变量按有序的形式组织起来 这些按序排列的同类数据元素的集合称为数组数组大小一般是 静态 的 插入 删除操作比较困难 线性结构6 3 分类2 栈 Stack 是只能在某一端插入和删除的特殊线性表它按照后进先出的原则存储数据 先进入的数据被压入栈底 最后的数据在栈顶 需要读数据的时候从栈顶开始弹出数据 最后一个数据被第一个读出来 插入删除只能从一端进行 线性结构6 4 线性结构6 5 分类3 队列 Queue 一种特殊的线性表 它只允许在表的前端 front 进行删除操作 而在表的后端 rear 进行插入操作 进行插入操作的端称为队尾 进行删除操作的端称为队头 队列中没有元素时 称为空队列先进先出插入从一端进行 删除从另一端进行 线性结构6 6 分类链表 LinkedList 是一种物理存储单元上非连续 非顺序的存储结构 数据元素的逻辑顺序是通过链表中的指针链接次序实现的 链表由一系列结点 链表中每一个元素称为结点 组成 结点可以在运行时动态生成 每个结点包括两个部分 一个是存储数据元素的数据域 另一个是存储下一个结点地址的指针域 插入 删除可从任意位置进行 树形结构 树 Tree 包含n n 0 个结点的有穷集合K 且在K中 1 有且仅有一个结点k0 没有前驱 称K0为树的根结点 简称为根 root 2 除k0外 k中的每个结点 有且仅有一个前驱 3 K中各结点 可以有m个后继 m 0 C盘下所有文件夹和文件构成一棵树 图 网状结构 图 Graph 图是由结点的有穷集合V和边的集合E组成其中 为了与树形结构加以区别 在图结构中常常将结点称为顶点边是顶点的有序偶对 若两个顶点之间存在一条边 就表示这两个顶点具有相邻关系简单图 不含多重边和自环的图应用举例 多个城市 道路相连 最短路径选择 数据结构的操作 不同的数据结构其操作集不同 但下列操作必不可缺 1 结构的生成2 结构的销毁3 在结构中查找满足规定条件的数据元素4 在结构中插入新的数据元素5 删除结构中已经存在的数据元素6 遍历 总结 链表及其操作常见数据结构 。