数据结构ppt课件.pptx

《数据结构ppt课件.pptx》由会员分享，可在线阅读，更多相关《数据结构ppt课件.pptx（913页珍藏版）》请在三一办公上搜索。

1、数据结构,讲师：,第一章 绪论,课程性质,数据结构是计算机专业的专业基础课 公共基础课、专业基础课、专业方向课、专业选修课在教学计划中的地位：核心、承上启下 前导课：高等数学、离散数学、程序设计语言 后续课：数据库、操作系统、编译原理属于武术中的“练功”科目 “练武不练功，到头一场空”考研：专业课必考,教学目标,掌握基本的数据结构 工具箱复用、修改、重组培养算法设计能力、程序设计能力 算法程序的灵魂 问题求解过程：问题想法算法程序 程序设计研究的层次：算法方法学语言工具培养算法分析能力 评价算法、改进算法,学编程的境界,学会写程序 学会高效地写程序 学会写高效的程序 学会设计算法 学会设计有用

2、的算法,学习要求,循序渐进，切忌心浮气躁 提高课外学习的时间和内容 理解科学而不是背诵科学读书 正确对待考试作习题 华罗庚：“学数学不做习题等于入宝山而空返” 作实验 计算机学科是一门科学性与工程性并重的学科，表现为理论和实践紧密结合的特征。,第 1 章 绪 论,数据结构在程序设计中的作用 本书讨论的主要内容 数据结构的基本概念算法及算法分析,本章的基本内容是：,1938年出生，25岁毕业于加州理工学院数学系，博士毕业后留校任教，28岁任副教授。30岁时，加盟斯坦福大学计算机系，任教授。从31岁起，开始出版他的历史性经典巨著：The Art of Computer Programming，他计

3、划共写7卷，然而出版三卷之后，已震惊世界，使他获得计算机科学界的最高荣誉图灵奖，此时，他年仅36岁。,数据结构的创始人克努思,1.1 数据结构在程序设计中的作用,程序设计的实质是什么?,数据表示：将数据存储在计算机（内存）中数据处理：处理数据，设计方案（算法）,数据结构问题起源于程序设计,1.1 数据结构在程序设计中的作用,利用计算机求解问题的一般过程?,计算机不能分析问题并产生问题的解决方案，必须由人来分析问题，确定问题的解决方案，编写程序，然后让计算机执行程序最终获得问题的解。,1.1 数据结构在程序设计中的作用,例1-1 手机电话号码查询问题,将电话号码集合组织成线性结构和树结构，查找操

4、作的效率不同，当数据量较大时差别就更大。,1.2 本书讨论的主要内容,计算机求解问题: 问题抽象出问题的模型求模型的解 问题数值问题、非数值问题 数 值 问 题数学方程 非数值问题数据结构,例1-2 学籍管理问题,完成什么功能?各表项之间是什么关系？,1.2 本书讨论的主要内容,例1-3 人机对弈问题,如何实现对弈? 各格局之间是什么关系？,1.2 本书讨论的主要内容,例1-4 七巧板涂色问题,如何表示区域之间的邻接关系？,1.2 本书讨论的主要内容,本书讨论非数值问题的数据组织和处理，主要内容如下：（1）数据的逻辑结构：线性表、树、图等数据结构，其核心是如何组织待处理的数据以及数据之间的关系

5、；（2）数据的存储结构：如何将线性表、树、图等数据结构存储到计算机的存储器中，其核心是如何有效地存储数据以及数据之间的逻辑关系；（3）算法：如何基于数据的某种存储结构实现插入、删除、查找等基本操作，其核心是如何有效地处理数据；（4）常用数据处理技术：查找技术、排序技术、索引技术等。,1.2 本书讨论的主要内容,1.3 数据结构的基本概念,数据：所有能输入到计算机中并能被计算机程序识别和处理的符号集合。 数值数据：整数、实数等 非数值数据：图形、图象、声音、文字等 数据元素：数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 数据项：构成数据元素的不可分割的最小单位。,数据结构的基本

6、概念,数据、数据元素、数据项之间的关系,包含关系：数据由数据元素组成，数据元素由数据项组成。数据元素是讨论数据结构时涉及的最小数据单位，其中的数据项一般不予考虑。,1.3 数据结构的基本概念,数据结构：相互之间存在一定关系的数据元素的集合。按照视点的不同，数据结构分为逻辑结构和存储结构。逻辑结构：指数据元素之间逻辑关系的整体。,1.3 数据结构的基本概念,数据结构的基本概念,数据的逻辑结构是从具体问题抽象出来的数据模型,数据结构：相互之间存在一定关系的数据元素的集合。按照视点的不同，数据结构分为逻辑结构和存储结构。逻辑结构：指数据元素之间逻辑关系的整体。,1.3 数据结构的基本概念,数据结构的

7、基本概念,数据的逻辑结构在形式上可定义为一个二元组：Data_Structure = (D, R)其中D是数据元素的有限集合，R是D上关系的集合。,数据结构：相互之间存在一定关系的数据元素的集合。按照视点的不同，数据结构分为逻辑结构和存储结构。逻辑结构：指数据元素之间逻辑关系的整体。,1.3 数据结构的基本概念,数据结构的基本概念,Data_Structure = (D, R)其中D = A, B, C, D, E, F, GR = R1，R1 = , , , , , , , , , ,数据结构：相互之间存在一定关系的数据元素的集合。按照视点的不同，数据结构分为逻辑结构和存储结构。逻辑结构：指

8、数据元素之间逻辑关系的整体。存储结构：又称为物理结构，是数据及其逻辑结构在计算机中的表示。,1.3 数据结构的基本概念,数据结构的基本概念,存储结构实质上是内存分配，在具体实现时依赖于计算机语言。,数据结构从逻辑上分为四类： 集合：数据元素之间就是 “属于同一个集合” ；,1.3 数据结构的基本概念,数据结构的基本概念,数据结构从逻辑上分为四类： 集合：数据元素之间就是 “属于同一个集合” ； 线性结构：数据元素之间 存在着一对一的线性关系；,1.3 数据结构的基本概念,数据结构的基本概念,数据结构从逻辑上分为四类： 集合：数据元素之间就是 “属于同一个集合” ； 线性结构：数据元素之间 存在

9、着一对一的线性关系； 树结构：数据元素之间存在 着一对多的层次关系；,1.3 数据结构的基本概念,数据结构的基本概念,数据结构从逻辑上分为四类： 集合：数据元素之间就是 “属于同一个集合” ； 线性结构：数据元素之间 存在着一对一的线性关系； 树结构：数据元素之间存在 着一对多的层次关系； 图结构：数据元素之间存在 着多对多的任意关系。,1.3 数据结构的基本概念,数据结构的基本概念,通常有两种存储结构：1. 顺序存储结构：用一组连续的存储单元依次存储数据元素，数据元素之间的逻辑关系由元素的存储位置来表示。,1.3 数据结构的基本概念,数据结构的基本概念,通常有两种存储结构：1. 顺序存储结构

10、：用一组连续的存储单元依次存储数据元素，数据元素之间的逻辑关系由元素的存储位置来表示。2. 链接存储结构：用一组任意的存储单元存储数据元素，数据元素之间的逻辑关系用指针来表示 。,例：（bat, cat, eat）,1.3 数据结构的基本概念,数据结构的基本概念,bat0200,cat0325,eat ,逻辑结构和存储结构之间的关系,数据的逻辑结构属于用户视图，是面向问题的，反映了数据内部的构成方式；数据的存储结构属于具体实现的视图，是面向计算机的。 一种数据的逻辑结构可以用多种存储结构来存储，而采用不同的存储结构，其数据处理的效率往往是不同的。,1.3 数据结构的基本概念,抽象数据类型,1.

11、 数据类型（Data Type）：一组值的集合以及定义于这个值集上的一组操作的总称。 例如：C+中的整型变量 2. 抽象（Abstract）:抽出问题本质的特征而忽略非本质的细节。 例如： 地图、驾驶汽车3. 抽象数据类型（Abstract Data Type，ADT）:一个数据结构以及定义在该结构上的一组操作的总称。,1.3 数据结构的基本概念,1.3 数据结构的基本概念,抽象数据类型,在设计ADT时，把ADT的定义、设计和实现分开来。定义部分只包含数据的逻辑结构和所允许的操作集合，一方面，ADT的使用者依据这些定义来使用ADT，即通过操作集合对该ADT进行操作；另一方面，ADT的实现者依据

12、这些定义来完成该ADT各种操作的具体实现。,ADT 抽象数据类型名Data 数据元素之间逻辑关系的定义Operation 操作1 前置条件：执行此操作前数据所必须的状态 输 入：执行此操作所需要的输入 功 能：该操作将完成的功能 输 出：执行该操作后产生的输出 后置条件：执行该操作后数据的状态 操作2 操作n endADT,1.3 数据结构的基本概念,抽象数据类型,1.3 数据结构的基本概念（小结）,数据的操作：插入、删除、修改、检索、排序等,算法的相关概念,1.算法（Algorithm）:是对特定问题求解步骤的一种描述，是指令的有限序列。,2. 算法的五大特性： 输入：一个算法有零个或多个输

13、入。 输出：一个算法有一个或多个输出。 有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。 确定性：算法中的每一条指令必须有确切的含义，对于相同的输入只能得到相同的输出。 可行性：算法描述的操作可以通过已经实现的基本操作执行有限次来实现。,1.4 算法及算法分析,欧几里德算法（有穷性、确定性、可行性）,m,n,r,例：欧几里德算法辗转相除法求两个自然数 m 和 n 的最大公约数,1.4 算法及算法分析,算法的描述方法自然语言,优点：容易理解缺点：冗长、二义性使用方法：粗线条描述算法思想 注意事项：避免写成自然段,1.4 算法及算法分析,步骤1：将m除以n得到余数r；步骤

14、2：若r等于0，则n为最大公约数， 算法结束；否则执行步骤3；步骤3：将n的值放在m中，将r的值放在n中， 重新执行步骤1；,例：欧几里德算法,自然语言,1.4 算法及算法分析,优点：流程直观 缺点：缺少严密性、灵活性使用方法：描述简单算法注意事项：注意抽象层次,算法的描述方法流程图,1.4 算法及算法分析,流 程 图,例：欧几里德算法,1.4 算法及算法分析,优点：能由计算机执行 缺点：抽象性差，对语言要求高使用方法：算法需要验证注意事项：将算法写成子函数,算法的描述方法程序设计语言,1.4 算法及算法分析,#include int CommonFactor(int m, int n) in

15、t r = m % n; while (r != 0) m = n; n = r; r = m % n; return n;void main( ) coutCommonFactor(63, 54)endl;,程序设计语言,例：欧几里德算法,1.4 算法及算法分析,伪代码（Pseudocode）：介于自然语言和程序设计语言之间的方法，它采用某一程序设计语言的基本语法，操作指令可以结合自然语言来设计。优点：表达能力强，抽象性强，容易理解使用方法：7 2,算法的描述方法伪代码,1.4 算法及算法分析,1. r = m % n; 2. 循环直到 r 等于0 2.1 m = n; 2.2 n = r;

16、 2.3 r = m % n; 3. 输出 n ;,伪 代 码,上述伪代码再具体一些，用C+的函数来描述。,例：欧几里德算法,1.4 算法及算法分析,int CommonFactor(int m, int n) r = m % n; while (r != 0) m = n; n = r; r = m % n; return n;,1.4 算法及算法分析,对C+语言进行了如下简化： 局部变量可以不声明； 写出子函数即可，子函数不用在主函数中调用，省略主函数； 所有的包含函数（头函数.h）可以省略； 交换两个变量的语句可以简写为ab。,算法分析,度量算法效率的方法： 事后统计：将算法实现，测算其

17、时间和空间开销。 缺点： 编写程序实现算法将花费较多的时间和精力； 所得实验结果依赖于计算机的软硬件等环境因素。 事前分析：对算法所消耗资源的一种估算方法。,1.4 算法及算法分析,算法分析,算法分析（Algorithm Analysis）：对算法所需要的计算机资源时间和空间进行估算。 时间复杂性（Time Complexity） 空间复杂性（Space Complexity）,1.4 算法及算法分析,算法的时间复杂度分析,1.4 算法及算法分析,算法分析,算法的执行时间每条语句执行时间之和,for (i=1; i=n; i+) for (j=1; j=n; j+) x+;,问题规模：输入量的

18、多少。基本语句：是执行次数与整个算法的执行次数成正比的操作指令。,for (i=1; i=n; i+) for (j=1; j=n; j+) x+;,问题规模：n基本语句：x+,1.4 算法及算法分析,算法分析,定义 若存在两个正的常数c和n0，对于任意nn0，都有T(n)cf(n)，则称T(n)=O(f(n)。,当问题规模充分大时在渐近意义下的阶。,1.4 算法及算法分析,算法分析大O符号,定理：若A(n)=amnm+am-1nm-1+a1n+a0是一个m次多项式，则A(n)=O(nm)。,说明：在计算算法时间复杂度时，可以忽略所有低次幂和最高次幂的系数。,1.4 算法及算法分析,算法分析大

19、O符号,例1-5 +x; 例1-6 for (i=1; i=n; +i) +x; 例1-7 for (i=1; i=n; +i) for (j=1; j=n; +j) +x; 例1-8 for (i=1; i=n; +i) for (j=1; j=i-1; +j) +x;,1.4 算法及算法分析,算法分析,例1-9 for (i=1; i=n; +i) for (j=1; j=n; +j) cij=0; for (k=1; k=n; +k) cij+=aik*bkj; 例1-10 for (i=1; i=n; i=2*i) +x;,(1)(log2n)(n)(nlog2n)(n2)(n3)(2

20、n)(n!),1.4 算法及算法分析,算法分析,最好情况、最坏情况、平均情况,例：在一维整型数组An中顺序查找与给定值k相等的元素（假设该数组中有且仅有一个元素值为k）。,int Find(int A , int n) for (i = 0; i n; i+) if (Ai = k) break; return i; ,1.4 算法及算法分析,基本语句的执行次数是否只和问题规模有关？,最好情况：出现概率较大时分析最差情况：实时系统平均情况：已知输入数据是如何分布的， 通常假设等概率分布,结论：如果问题规模相同，时间代价与输入数据有关，则需要分析最好情况、最坏情况、平均情况。,1.4 算法及算法

21、分析,最好情况、最坏情况、平均情况,本章小结知识结构图,第二章 线性表,本章的基本内容,线性表的逻辑结构 线性表的顺序存储及实现 线性表的链接存储及实现 顺序表和链表的比较 线性表的其他存储方法,2.1 线性表的逻辑结构,数据元素之间的关系是什么？,2.1 线性表的逻辑结构,数据元素之间的关系是什么？,现实生活中，许多问题抽象出的数据模型是线性表，如何存储这种线性结构并实现插入、删除、查找等基本操作呢？,线性表：简称表，是n（n0）个具有相同类型的数据元素的有限序列。 线性表的长度：线性表中数据元素的个数。 空表：长度等于零的线性表，记为：L=( )。 非空表记为：L（a1, a2 , , a

22、i-1, ai , , an),2.1 线性表的逻辑结构,线性表的定义,其中，ai（1in）称为数据元素；下角标 i 表示该元素在线性表中的位置或序号 。,2.1 线性表的逻辑结构,线性表的特性,1. 有限性：线性表中数据元素的个数是有穷的。,2. 相同性：线性表中数据元素的类型是同一的。,3. 顺序性：线性表中相邻的数据元素ai-1和ai之间存在序偶关系(ai-1, ai)，即ai-1是ai的前驱， ai是ai-1的后继；a1无前驱，an无后继，其它每个元素有且仅有一个前驱和一个后继。,线性表的抽象数据类型定义,ADT ListData 线性表中的数据元素具有相同类型， 相邻元素具有前驱和后

23、继关系OperationInitList 前置条件：表不存在 输入：无 功能：表的初始化 输出： 无 后置条件：建一个空表,2.1 线性表的逻辑结构,DestroyList 前置条件：表已存在 输入：无 功能：销毁表 输出：无 后置条件：释放表所占用的存储空间Length 前置条件：表已存在 输入：无 功能：求表的长度 输出：表中数据元素的个数 后置条件：表不变,2.1 线性表的逻辑结构,线性表的抽象数据类型定义,Get 前置条件：表已存在 输入：元素的序号i 功能：在表中取序号为i的数据元素 输出：若i合法，返回序号为i的元素值，否则抛出异常 后置条件：表不变Locate 前置条件：表已存在

24、 输入：数据元素x 功能：在线性表中查找值等于x的元素 输出：若查找成功，返回x在表中的序号，否则返回0 后置条件：表不变,2.1 线性表的逻辑结构,线性表的抽象数据类型定义,Insert前置条件：表已存在输入：插入i；待插x功能：在表的第i个位置处插入一个新元素x输出：若插入不成功，抛出异常 后置条件：若插入成功，表中增加一个新元素Delete前置条件：表已存在输入：删除位置i功能：删除表中的第i个元素 输出：若删除成功，返回被删元素，否则抛出异常 后置条件：若删除成功，表中减少一个元素,2.1 线性表的逻辑结构,线性表的抽象数据类型定义,Empty 前置条件：表已存在 输入：无 功能：判断

25、表是否为空 输出：若是空表，返回1，否则返回0 后置条件：表不变ADT,进一步说明:（1）线性表的基本操作根据实际应用是而定；（2）复杂的操作可以通过基本操作的组合来实现；（3）对不同的应用，操作的接口可能不同。,2.1 线性表的逻辑结构,线性表的抽象数据类型定义,2.2 线性表的顺序存储结构及实现,顺序表线性表的顺序存储结构,例：（34, 23, 67, 43）,34,23,67,43,4,2.2 线性表的顺序存储结构及实现,顺序表线性表的顺序存储结构,例：（34, 23, 67, 43）,34,23,67,43,4,用什么属性来描述顺序表？,2.2 线性表的顺序存储结构及实现,顺序表线性表

26、的顺序存储结构,例：（34, 23, 67, 43）,34,23,67,43,4,如何实现顺序表的内存分配？,0 i-2 i-1 n-1 Max-1,a1,ai-1,ai,an,空闲,长度,2.2 线性表的顺序存储结构及实现,顺序表,一般情况下，(a1，a2，, ai-1，ai , , an)的顺序存储：,数组的长度Max,线性表的长度Length,数组的长度大于等于当前线性表的长度,如何求得任意元素的存储地址？,0 i-2 i-1 n-1 Max-1,a1,ai-1,ai,an,空闲,长度,2.2 线性表的顺序存储结构及实现,顺序表,一般情况下，(a1，a2，, ai-1，ai , , an

27、)的顺序存储：,0 i-2 i-1 n-1 Max-1,a1,ai-1,ai,an,空闲,长度,Loc(ai)=Loc(a1) + (i -1)c,随机存取：在O(1)时间内存取数据元素,2.2 线性表的顺序存储结构及实现,顺序表,一般情况下，(a1，a2，, ai-1，ai , , an)的顺序存储：,2.2 线性表的顺序存储结构及实现,存储结构是数据及其逻辑结构在计算机中的表示；存取结构是在一个数据结构上对查找操作的时间性能的一种描述。,存储结构和存取结构,“顺序表是一种随机存取的存储结构”的含义为：在顺序表这种存储结构上进行的查找操作，其时间性能为O(1)。,顺序表类的声明,const

28、int MaxSize=100; template /模板类class SeqList public: SeqList( ) ; /构造函数 SeqList(DataType a , int n); SeqList( ) ; /析构函数 int Length( ); DataType Get(int i); int Locate(DataType x ); void Insert(int i, DataType x); DataType Delete(int i); private: DataType dataMaxSize; int length;,2.2 线性表的顺序存储结构及实现,操作接

29、口：SeqList( ),算法描述：SeqList :SeqList( ) length = 0; ,2.2 线性表的顺序存储结构及实现,顺序表的实现无参构造函数,0,操作接口：SeqList(DataType a , int n),顺序表的实现有参构造函数,2.2 线性表的顺序存储结构及实现,5,35,12,24,33,42,template SeqList :SeqList(DataType a , int n) if (n MaxSize) throw 参数非法; for (i = 0; i n; i+ +) datai = ai; length = n; ,2.2 线性表的顺序存储结构

30、及实现,顺序表的实现有参构造函数,算法描述：,操作接口： void Insert(int i, DataType x)插入前：(a1, , ai-1, ai, , an)插入后：(a1, , ai-1, x , ai, , an),顺序表的实现插入,2.2 线性表的顺序存储结构及实现,ai-1和ai之间的逻辑关系发生了变化,顺序存储要求存储位置反映逻辑关系,存储位置要反映这个变化,例：（35，12，24，42），在i=2的位置上插入33。,表满：length=MaxSize合理的插入位置：1ilength+1（i指的是元素的序号）,2.2 线性表的顺序存储结构及实现,顺序表的实现插入,4,35

31、,12,24,42,a1,a2,a3,a4,0 1 2 3 4,42,24,12,33,什么时候不能插入？,1. 如果表满了，则抛出上溢异常;2. 如果元素的插入位置不合理，则抛出位置异常;3. 将最后一个元素至第i个元素分别向后移动一个位置；4. 将元素x填入位置i处；5. 表长加1；,算法描述伪代码,2.2 线性表的顺序存储结构及实现,顺序表的实现插入,template void SeqList:Insert(int i, DataType x) if (length = MaxSize) throw 上溢; if (i length + 1) throw 位置; for (j = len

32、gth; j = i; j-) dataj = dataj-1; datai-1 = x; length+;,算法描述C+描述,2.2 线性表的顺序存储结构及实现,顺序表的实现插入,基本语句？,最好情况（ i=n+1）： 基本语句执行0次，时间复杂度为O(1)。最坏情况（ i=1）： 基本语句执行n+1次，时间复杂度为O(n)。平均情况（1in+1）： 时间复杂度为O(n)。,时间性能分析,2.2 线性表的顺序存储结构及实现,顺序表的实现插入,操作接口： DataType Delete(int i)删除前：(a1, , ai-1,ai,ai+1,an)删除后：(a1,ai-1,ai+1, ,a

33、n),顺序表的实现删除,2.2 线性表的顺序存储结构及实现,ai-1和ai之间的逻辑关系发生了变化,顺序存储要求存储位置反映逻辑关系,存储位置要反映这个变化,例：（35, 33, 12, 24, 42），删除i=2的数据元素。,仿照顺序表的插入操作，完成：1. 分析边界条件；2. 分别给出伪代码和C+描述的算法；3. 分析时间复杂度。,2.2 线性表的顺序存储结构及实现,顺序表的实现删 除,5,35,a1,a2,a3,a4,0 1 2 3 4,42,24,12,33,a5,12,24,42,顺序表的实现按位查找,操作接口： DataType Get(int i),2.2 线性表的顺序存储结构及

34、实现,0 i-2 i-1 n-1 Max-1,a1,ai-1,ai,an,空闲,n,算法描述：template DataType SeqList :Get( int i ) if (i = 1 ,时间复杂度？,顺序表的实现按值查找,操作接口： int Locate(DataType x ),2.2 线性表的顺序存储结构及实现,5,35,a1,a2,a3,a4,0 1 2 3 4,42,24,12,33,a5,例：在（35, 33, 12, 24, 42） 中查找值为12的元素，返回在表中的序号。,template int SeqList :Locate(DataType x) for (i =

35、 0; i length; i+) if (datai = x) return i + 1; return 0; ,2.2 线性表的顺序存储结构及实现,顺序表的实现按值查找,算法描述：,时间复杂度？,顺序表的优缺点,顺序表的优点： 无需为表示表中元素之间的逻辑关系而增加额外的存储空间； 随机存取：可以快速地存取表中任一位置的元素。,顺序表的缺点： 插入和删除操作需要移动大量元素； 表的容量难以确定，表的容量难以扩充； 造成存储空间的碎片。,2.2 线性表的顺序存储结构及实现,单链表：线性表的链接存储结构。存储思想：用一组任意的存储单元存放线性表的元素。,2.3 线性表的链接存储结构及实现,单链

36、表,存储特点：逻辑次序和物理次序 不一定相同。 2.元素之间的逻辑关系 用指针表示。,2.3 线性表的链接存储结构及实现,例：(a1, a2 ,a3, a4)的存储示意图,单链表,a10200,a20325,a30300,a4 ,2.3 线性表的链接存储结构及实现,单链表,数据域,指针域,单链表是由若干结点构成的；单链表的结点只有一个指针域。,data：存储数据元素next：存储指向后继结点的地址,template struct Node DataType data; Node *next;,2.3 线性表的链接存储结构及实现,单链表,如何申请一个结点？,s=new Node ;,templa

37、te struct Node DataType data; Node *next;,2.3 线性表的链接存储结构及实现,单链表,s=new Node ;,2.3 线性表的链接存储结构及实现,单链表,如何引用数据元素？,data,如何引用指针域？,next,s-next;,2.3 线性表的链接存储结构及实现,单链表,重点在数据元素之间的逻辑关系的表示，所以，将实际存储地址抽象。,什么是存储结构？,2.3 线性表的链接存储结构及实现,单链表,头指针：指向第一个结点的地址。尾标志：终端结点的指针域为空。,2.3 线性表的链接存储结构及实现,单链表,空表和非空表不统一，缺点？如何将空表与非空表统一？,

38、头结点：在单链表的第以一个元素结点之前附设一个类型相同的结点，以便空表和非空表处理统一。,2.3 线性表的链接存储结构及实现,单链表,非空表,template class LinkList public: LinkList( )； LinkList(DataType a , int n); LinkList( ); int Length( ); DataType Get(int i); int Locate(DataType x); void Insert(int i, DataType x); DataType Delete(int i); void PrintList( ); privat

39、e: Node *first; ;,单链表类的声明,2.3 线性表的链接存储结构及实现,单链表的实现遍历操作,操作接口： void PrintList( );,核心操作（关键操作）：工作指针后移。从头结点（或开始结点）出发，通过工作指针的反复后移而将整个单链表“审视”一遍的方法称为扫描（或遍历）。,2.3 线性表的链接存储结构及实现,first,a1,a2,an,ai,单链表的实现遍历操作,操作接口： void PrintList( );,2.3 线性表的链接存储结构及实现,template void LinkList : PrintList( ) p = first-next; while

40、(p != NULL) cout data; p = p-next; ,单链表的实现按位查找,操作接口： DataType Get(int i);,2.3 线性表的链接存储结构及实现,first,a1,a2,an,ai,1. 工作指针p初始化; 累加器count初始化;2. 重复执行下述操作，直到p为空： 2.1 工作指针p后移; 2.2 count+;3. 返回累加器count的值；,template int LinkList : Length( ) p = first-next; count = 0; while (p != NULL) p = p-next; count+; return

41、 count; /注意count的初始化和返回值之间的关系,2.3 线性表的链接存储结构及实现,单链表的实现按位查找,算法描述C+描述,template int LinkList : Locate(DataType x) p = first-next; count = 1; while (p != NULL) if (p-data = x) return count;/查找成功，返回序号 p = p-next; count+; return 0; /退出循环表明查找失败,2.3 线性表的链接存储结构及实现,单链表的实现按值查找,算法描述C+描述,单链表的实现插入,操作接口： void Inse

42、rt(int i, DataType x);,2.3 线性表的链接存储结构及实现,如何实现结点ai-1、x和ai之间逻辑关系的变化？,算法描述：s=new Node; s-data=x;s-next=p-next; p-next=s;,注意分析边界情况表头、表尾。,单链表的实现插入,2.3 线性表的链接存储结构及实现,first,a1,an,ai,算法描述：s=new Node; s-data=x;s-next=p-next; p-next=s;,由于单链表带头结点，表头、表中、表尾三种情况的操作语句一致。,算法描述伪代码,1. 工作指针p初始化； 2. 查找第i-1个结点并使工作指针p指向该

43、结点； 3. 若查找不成功，则插入位置不合理，抛出插入位置异常； 否则， 3.1 生成一个元素值为x的新结点s； 3.2 将新结点s插入到结点p之后；,2.3 线性表的链接存储结构及实现,单链表的实现插入,template void LinkList : Insert(int i, DataType x) p = first ; count = 0; /工作指针p应指向头结点 while (p != NULL /结点s插入结点p之后 ,2.3 线性表的链接存储结构及实现,单链表的实现插入,基本语句？时间复杂度？,单链表的实现构造函数,操作接口：LinkList(DataType a , int

44、 n),头插法：将待插入结点插在头结点的后面 。,算法描述：first=new Node; first-next=NULL;,2.3 线性表的链接存储结构及实现,单链表的实现构造函数,操作接口：LinkList(DataType a , int n),头插法：将待插入结点插在头结点的后面 。,2.3 线性表的链接存储结构及实现,算法描述：s=new Node; s-data=a0;s-next=first-next;first-next=s;,插入第一个元素结点,first,单链表的实现构造函数,操作接口：LinkList(DataType a , int n),头插法：将待插入结点插在头结点

45、的后面 。,2.3 线性表的链接存储结构及实现,算法描述：s=new Node; s-data=a1;s-next=first-next;first-next=s;,依次插入每一个结点,template LinkList : LinkList(DataType a , int n) first = new Node; first-next = NULL; for (i = 0; i data = ai; s-next = first-next; first-next = s; ,2.3 线性表的链接存储结构及实现,单链表的实现构造函数,尾插法：将待插入结点插在终端结点的后面。,2.3 线性表的

46、链接存储结构及实现,单链表的实现构造函数,操作接口：LinkList(DataType a , int n),算法描述：first=new Node; rear=first;,尾插法：将待插入结点插在终端结点的后面。,2.3 线性表的链接存储结构及实现,单链表的实现构造函数,操作接口：LinkList(DataType a , int n),算法描述：s=new Node; s-data=a0;rear-next=s;rear=s;,插入第一个元素结点,尾插法：将待插入结点插在终端结点的后面。,2.3 线性表的链接存储结构及实现,单链表的实现构造函数,操作接口：LinkList(DataTyp

47、e a , int n),算法描述：s=new Node; s-data=a1;rear-next=s;rear=s;,依次插入每一个结点,35,尾插法：将待插入结点插在终端结点的后面。,2.3 线性表的链接存储结构及实现,单链表的实现构造函数,操作接口：LinkList(DataType a , int n),算法描述：rear-next=NULL;,最后一个结点插入后,35,template LinkList : LinkList(DataType a , int n) first = new Node; /生成头结点 r = first; /尾指针初始化 for (i = 0; i da

48、ta = ai; r-next = s; r = s; r-next = NULL; ,2.3 线性表的链接存储结构及实现,单链表的实现构造函数,算法描述：,单链表的实现删除,操作接口： DataType Delete(int i);,2.3 线性表的链接存储结构及实现,如何实现结点ai-1和ai之间逻辑关系的变化？,算法描述：q=p-next; x=q-data;p-next=q-next; delete q;,单链表的实现删除,2.3 线性表的链接存储结构及实现,算法描述：q=p-next; x=q-data;p-next=q-next; delete q;,注意分析边界情况表头、表尾。,

49、表尾的特殊情况：虽然被删结点不存在，但其前驱结点却存在。,p-next=NULL,算法描述伪代码,1.工作指针p初始化； 2. 查找第i-1个结点并使工作指针p指向该结点； 3. 若p不存在或p不存在后继结点，则抛出位置异常； 否则， 3.1 暂存被删结点和被删元素值； 3.2 摘链，将结点p的后继结点从链表上摘下； 3.3 释放被删结点； 3.4 返回被删元素值；,2.3 线性表的链接存储结构及实现,单链表的实现删除,template DataType LinkList : Delete(int i) p = first ; count = 0; while (p != NULL ,2.3

50、线性表的链接存储结构及实现,单链表的实现删除,单链表的实现析构函数,析构函数将单链表中所有结点的存储空间释放。,2.3 线性表的链接存储结构及实现,操作接口：LinkList( );,first,a1,a2,an,ai,算法描述：q = first; first = first-next;delete q;,注意：保证链表未处理的部分不断开,单链表的实现析构函数,template LinkList : LinkList( ) while (first != NULL) q = first; first = first-next; delete q; ,2.3 线性表的链接存储结构及实现,算法描