程序设计基础链表简介 计算机教学课件PPT

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