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

1、08 链表简介链表简介 程序设计基础 2 home back first prev next last 本节目标本节目标 链表及其操作链表及其操作 常见数据结构常见数据结构 3 home back first prev next last 链表及其操作链表及其操作 2-1 手工方式手工方式 新建和删除新建和删除 导入和导出数据导入和导出数据 添加删除元素添加删除元素 显示和隐藏显示和隐藏 改变显示大小改变显示大小 命令方式命令方式 见下页见下页 4 home back first prev next last 链表及其操作链表及其操作 2-2 5 home back first prev ne

2、xt last 链表应用练习链表应用练习 2-1 新建链表新建链表 chengji，通过程序，通过程序 清空链表所有元素清空链表所有元素 提示用户输入提示用户输入5个数字，并将数字保存到链表个数字，并将数字保存到链表 计算输出所有链表元素的和、最大值、最小值计算输出所有链表元素的和、最大值、最小值 和平均值和平均值 6 home back first prev next last 链表应用练习链表应用练习 2-2 链表元素输入链表元素输入 查找计算查找计算 7 home back first prev next last 数据结构数据结构 3-1 数据结构是计算机存储、组织数据的方式。数据结构

3、是计算机存储、组织数据的方式。 数据结构是指相互之间存在一种或多种特定数据结构是指相互之间存在一种或多种特定 关系的数据元素的集合。关系的数据元素的集合。 通常情况下，精心选择的数据结构可以带来通常情况下，精心选择的数据结构可以带来 更高的运行或者存储效率。更高的运行或者存储效率。 数据结构往往同高效的检索算法和索引技术数据结构往往同高效的检索算法和索引技术 有关。有关。 8 home back first prev next last 数据结构数据结构 3-2 一个数据结构是由数据元素依据某种逻辑联一个数据结构是由数据元素依据某种逻辑联 系组织起来的。系组织起来的。 对数据元素间逻辑关系的描

4、述称为数据的逻对数据元素间逻辑关系的描述称为数据的逻 辑结构；辑结构； 数据必须在计算机内存储，数据的存储结构数据必须在计算机内存储，数据的存储结构 是数据结构的实现形式，是其在计算机内的是数据结构的实现形式，是其在计算机内的 表示；表示； 讨论一个数据结构必须同时讨论在该类数据讨论一个数据结构必须同时讨论在该类数据 上执行的运算才有意义。上执行的运算才有意义。 9 home back first prev next last 数据结构数据结构 3-3 常见数据结构常见数据结构 集合集合 数据元素除了同属于一种类型外，别无其它关系数据元素除了同属于一种类型外，别无其它关系 线性结构线性结构 线

5、性结构中元素之间存在一对一关系线性结构中元素之间存在一对一关系 树形结构树形结构 树形结构中元素之间存在一对多关系树形结构中元素之间存在一对多关系 图形结构（网状结构）图形结构（网状结构） 图形结构中元素之间存在多对多关系图形结构中元素之间存在多对多关系 10 home back first prev next last 集合集合 性质性质 由一组相同数据类型的成员组成由一组相同数据类型的成员组成 同一集合的成员必须互不相同同一集合的成员必须互不相同 集合中的成员一般是无序的，没有先后次序关集合中的成员一般是无序的，没有先后次序关 系系 应用举例应用举例 实现一个生字本，记录不熟悉的英语单词，

6、同实现一个生字本，记录不熟悉的英语单词，同 一单词只记录一次一单词只记录一次 11 home back first prev next last 线性结构线性结构 6-1 性质性质 除起始元素外除起始元素外,线性表中的其他元素仅有一个直线性表中的其他元素仅有一个直 接前驱元素接前驱元素 除终端元素外除终端元素外,线性表中的其他元素仅有一个直线性表中的其他元素仅有一个直 接后继元素接后继元素 应用举例应用举例 输入并保存班级英语成绩，计算平均成绩输入并保存班级英语成绩，计算平均成绩 12 home back first prev next last 线性结构线性结构 6-2 分类分类 1、数组数

7、组 (Array) 在程序设计中，为了处理方便，在程序设计中，为了处理方便， 把具有相同类型的把具有相同类型的 若干变量按有序的形式组织起来。这些按序排列的若干变量按有序的形式组织起来。这些按序排列的 同类数据元素的集合称为数组同类数据元素的集合称为数组 数组大小一般是“静态”的，插入、删除操作比较数组大小一般是“静态”的，插入、删除操作比较 困难困难 13 home back first prev next last 线性结构线性结构 6-3 分类分类 2、栈、栈 (Stack) 是只能在某一端插入和删除的特殊线性表是只能在某一端插入和删除的特殊线性表 它按照它按照后进先出后进先出的原则存储

8、数据，先进入的数据被的原则存储数据，先进入的数据被 压入栈底，最后的数据在栈顶，需要读数据的时候压入栈底，最后的数据在栈顶，需要读数据的时候 从栈顶开始弹出数据（最后一个数据被第一个读出从栈顶开始弹出数据（最后一个数据被第一个读出 来）来） 插入删除只能从一端进行插入删除只能从一端进行 14 home back first prev next last 线性结构线性结构 6-4 15 home back first prev next last 线性结构线性结构 6-5 分类分类 3、队列、队列 (Queue) 一种特殊的线性表，它只允许在表一种特殊的线性表，它只允许在表 的前端（的前端（fr

9、ont）进行删除操作，而）进行删除操作，而 在表的后端（在表的后端（rear）进行插入操作。）进行插入操作。 进行插入操作的端称为队尾，进行进行插入操作的端称为队尾，进行 删除操作的端称为队头。队列中没删除操作的端称为队头。队列中没 有元素时，称为空队列有元素时，称为空队列 先进先出先进先出 插入从一端进行，删除从另一端进插入从一端进行，删除从另一端进 行行 16 home back first prev next last 线性结构线性结构 6-6 分类分类 链表链表 (Linked List) 是一种物理存储单元上非连续、非顺序的存储结构，数据元素是一种物理存储单元上非连续、非顺序的存储结

10、构，数据元素 的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系 列结点（链表中每一个元素称为结点）组成，结点可以在运行列结点（链表中每一个元素称为结点）组成，结点可以在运行 时动态生成。每个结点包括两个部分：一个是存储数据元素的时动态生成。每个结点包括两个部分：一个是存储数据元素的 数据域，另一个是存储下一个结点地址的指针域。数据域，另一个是存储下一个结点地址的指针域。 插入、删除可从任意位置进行插入、删除可从任意位置进行 17 home back first prev next last 树形结构树形结构 树树 (Tree) 包含包

11、含n（n0）个结点的有穷集合）个结点的有穷集合K，且在，且在K中：中： （1）有且仅有一个结点）有且仅有一个结点 k0，没有前驱，称，没有前驱，称K0为树的根为树的根 结点。简称为根（结点。简称为根（root） （2）除）除k0外，外，k中的每个结点，有且仅有一个前驱中的每个结点，有且仅有一个前驱 （3）K中各结点，可以有中各结点，可以有m个后继（个后继（m=0） C 盘下所有文件夹和文件构成一棵树盘下所有文件夹和文件构成一棵树 18 home back first prev next last 图（网状结构）图（网状结构） 图图 (Graph) 图是由结点的有穷集合图是由结点的有穷集合V和边

12、的集合和边的集合E组成组成 其中，为了与树形结构加以区别，在图结构中常常将结其中，为了与树形结构加以区别，在图结构中常常将结 点称为顶点点称为顶点 边是顶点的有序偶对，若两个顶点之间存在一条边，就边是顶点的有序偶对，若两个顶点之间存在一条边，就 表示这两个顶点具有相邻关系表示这两个顶点具有相邻关系 简单图简单图 ：不含多重边和自环的图：不含多重边和自环的图 应用举例：多个城市，道路相连，最短路径选择应用举例：多个城市，道路相连，最短路径选择 19 home back first prev next last 数据结构的操作数据结构的操作 不同的数据结构其操作集不同，但下列操作不同的数据结构其操作集不同，但下列操作 必不可缺：必不可缺： 1. 结构的生成结构的生成 2. 结构的销毁结构的销毁 3. 在结构中查找满足规定条件的数据元素在结构中查找满足规定条件的数据元素 4. 在结构中插入新的数据元素在结构中插入新的数据元素 5. 删除结构中已经存在的数据元素删除结构中已经存在的数据元素 6. 遍历遍历 20 home back first prev next last 总结总结 链表及其操作链表及其操作 常见数据结构常见数据结构