线性链表-深圳大学计算机与软件学院课件.ppt

1、深圳大学计算机系 蔡茂国数据结构数据结构课程简介课程简介 本课程教材为：本课程教材为：n数据结构数据结构(C C语言版语言版)严蔚敏，吴伟民严蔚敏，吴伟民清华大学出版社清华大学出版社20042004年年1111月（第月（第2828次印刷）次印刷）2主要参考教材主要参考教材数据结构数据结构课程简介课程简介所有课件、作业及实验，均上传至：n深圳大学首页深圳大学首页 课程中心课程中心 输入学生姓名及密码，实现登录输入学生姓名及密码，实现登录 从数据结构从数据结构课程下下载课程下下载3课件下载课件下载第一章第一章深圳大学计算机系 蔡茂国一、数据一、数据5第一节数据结构第一节数据结构n是信息的载体，是信

2、息的载体，是描述客观事物的数、字符、以及所有能输入到计算机中，被计算机程序识别和处理的符号的集合符号的集合n数值性数据数值性数据n非数值性数据非数值性数据第章数据结构绪论第章数据结构绪论二、数据元素（二、数据元素（Data ElementData Element）6第一节数据结构第一节数据结构n数据的基本单位。数据的基本单位。在计算机程序中常作为一个整体进行考虑和处理。n有时一个数据元素可以由若干数据项由若干数据项(Data Data Item)Item)组成组成（此时数据元素被称为记录）n数据元素又称为元素、结点、记录数据元素又称为元素、结点、记录第章数据结构绪论第章数据结构绪论三、数据项（

3、三、数据项（Data ItemData Item）7第一节数据结构第一节数据结构n具有独立含义的最小标识单位。具有独立含义的最小标识单位。第章数据结构绪论第章数据结构绪论学号学号姓名姓名学院学院专业专业四、数据对象（四、数据对象（Data ObjectData Object）8第一节数据结构第一节数据结构n具有相同性质的数据元素的集合。具有相同性质的数据元素的集合。n整数数据对象整数数据对象 N=0,N=0,1,1,2,2,n字母字符数据对象字母字符数据对象 C=A,B,C,C=A,B,C,F F。第章数据结构绪论第章数据结构绪论五、结构（五、结构（StructureStructure）9第一

4、节数据结构第一节数据结构结构是元素之间的：n空间位置关系空间位置关系n相互作用和依赖关系相互作用和依赖关系第章数据结构绪论第章数据结构绪论五、结构五、结构10第一节数据结构第一节数据结构四种基本结构n集合结构集合结构n线性结构线性结构n树形结构树形结构n图图形结构结构第章数据结构绪论第章数据结构绪论456231125436123456123456六、数据结构（六、数据结构（Data StructureData Structure）11第一节数据结构第一节数据结构1.1.形式定义：形式定义：n某一数据对象的所有数据成员之间的关系。记为：某一数据对象的所有数据成员之间的关系。记为：Data_Str

5、uctureData_Structure=D,S=D,Sn其中，其中，D D 是某一数据对象，是某一数据对象，nS S 是该对象中所有数据成员之间的关系的有限集合。是该对象中所有数据成员之间的关系的有限集合。第章数据结构绪论第章数据结构绪论六、数据结构六、数据结构12第一节数据结构第一节数据结构2.2.线性数据结构举例线性数据结构举例 L=K,R L=K,RnK=1,2,3,4,5,6K=1,2,3,4,5,6nR=,R=,第章数据结构绪论第章数据结构绪论123456六、数据结构六、数据结构13第一节数据结构第一节数据结构3.3.树形数据结构举例树形数据结构举例 T=K,R T=K,RnK=1

6、,2,3,4,5,6K=1,2,3,4,5,6nR=,R=,第章数据结构绪论第章数据结构绪论456231六、数据结构六、数据结构14第一节数据结构第一节数据结构4.4.图图形数据结构举例数据结构举例 G=K,R G=K,RnK=1,2,3,4,5,6K=1,2,3,4,5,6nR=(1,2),(1,5),(1,6),(2,3),(2,4),R=(1,2),(1,5),(1,6),(2,3),(2,4),(2,6),(3,4),(4,5),(4,6),(5,6)(2,6),(3,4),(4,5),(4,6),(5,6)第章数据结构绪论第章数据结构绪论123456七、应用举例七、应用举例15第一节

7、数据结构第一节数据结构1.1.线性数据结构举例线性数据结构举例n数据结构学生选课名单（部分）数据结构学生选课名单（部分）第章数据结构绪论第章数据结构绪论学号学号姓名姓名 学院学院 专业专业 2004131221黄磊黄磊 信息工程学院信息工程学院 信息工程学院信息工程学院 2004131209熊玲玲熊玲玲 信息工程学院信息工程学院 信息工程学院信息工程学院 2004131135彭智俊彭智俊 信息工程学院信息工程学院 信息工程学院信息工程学院 2004131252徐元庆徐元庆 信息工程学院信息工程学院 信息工程学院信息工程学院 2004131099吴小池吴小池 信息工程学院信息工程学院 信息工程学

8、院信息工程学院 2004131031陈明亮陈明亮 信息工程学院信息工程学院 信息工程学院信息工程学院 七、应用举例七、应用举例16第一节数据结构第一节数据结构2.2.树形数据结构举例树形数据结构举例nUNIXUNIX文件系统结构图文件系统结构图（部分）（部分）第章数据结构绪论第章数据结构绪论/rootbinlibuseretcmathdsswhang xiongpan七、应用举例七、应用举例17第一节数据结构第一节数据结构3.3.图图形形数据结构举例数据结构举例n深圳城市交通示意图深圳城市交通示意图（部分）（部分）第章数据结构绪论第章数据结构绪论南山南山福田福田罗湖罗湖盐田盐田宝安宝安西丽西丽

9、梅林梅林布吉布吉龙华龙华龙岗龙岗八、数据结构要解决的问题八、数据结构要解决的问题18第一节数据结构第一节数据结构n如何为应用程序中涉及到各种各样的数据，建如何为应用程序中涉及到各种各样的数据，建立相应的数据结构（表、树或图），并依此实立相应的数据结构（表、树或图），并依此实现软件功能现软件功能n从广义上讲，数据结构描述现实世界实体的数从广义上讲，数据结构描述现实世界实体的数学模型及其上的操作在计算机中的表示和实现学模型及其上的操作在计算机中的表示和实现第章数据结构绪论第章数据结构绪论一、逻辑结构一、逻辑结构19第二节数据的结构第二节数据的结构n逻辑结构描述数据元素之间的关系逻辑结构描述数据元素

10、之间的关系n线性结构线性结构n线性表（表，栈，队列，串等）线性表（表，栈，队列，串等）n非线性结构非线性结构n树（二叉树，树（二叉树，HuffmanHuffman树，二叉排序树等）树，二叉排序树等）n图（有向图，无向图等）图（有向图，无向图等）第章数据结构绪论第章数据结构绪论456231123456123456二、物理结构（存储结构）二、物理结构（存储结构）20第二节数据的结构第二节数据的结构n物理结构是数据结构在计算机中的表示（或映物理结构是数据结构在计算机中的表示（或映象）象）n顺序存储表示顺序存储表示（可以用C语言中一维数组表示）n链接存储表示链接存储表示（可以用C语言中的指针表示）n索

11、引存储表示索引存储表示n散列存储表示散列存储表示第章数据结构绪论第章数据结构绪论二、物理结构（存储结构）二、物理结构（存储结构）21第二节数据的结构第二节数据的结构n复数存储结构举例复数存储结构举例第章数据结构绪论第章数据结构绪论z1=3.0-2.3i指针或链(地址)041506110613-2.33.00415z1=3.0-2.3i z2=-0.7+4.8i03000302063206343.0-2.3-0.74.8顺序存储结构链式存储结构一、数据类型一、数据类型22第三节数据类型第三节数据类型n数据类型是一个值的集合和定义在这个值集上数据类型是一个值的集合和定义在这个值集上的一组操作的总称

12、的一组操作的总称n如如C C语言中的整型变量语言中的整型变量(intint)，其值集为某个区其值集为某个区间上的整数，定义在其上的操作为间上的整数，定义在其上的操作为+,-,+,-,x,/x,/等等第章数据结构绪论第章数据结构绪论二、原子数据类型和结构数据类型二、原子数据类型和结构数据类型23第三节数据类型第三节数据类型1.1.原子数据类型原子数据类型n是不可分解的数据类型是不可分解的数据类型n如如C C语言中的整型语言中的整型(intint)，实型实型(float)float)，字符字符型型(char)char)，指针类型指针类型(*)和空类型和空类型(void)void)等等第章数据结构绪

13、论第章数据结构绪论二、原子数据类型和结构数据类型二、原子数据类型和结构数据类型24第三节数据类型第三节数据类型2.2.结构数据类型结构数据类型n由若干成分由若干成分（原子类型或结构类型）按某种结按某种结构组成的数据类型构组成的数据类型n结构数据类型可以看作是一种数据结构和定义结构数据类型可以看作是一种数据结构和定义在其上的一组操作组成的整体在其上的一组操作组成的整体n如数组，由若干分量组成，每个分量可以是整如数组，由若干分量组成，每个分量可以是整数，也可以是数组（如数，也可以是数组（如intint A10 A10）第章数据结构绪论第章数据结构绪论三、抽象数据类型（三、抽象数据类型（Abstra

14、ct Data TypeAbstract Data Type）25第三节数据类型第三节数据类型n由用户定义，用以表示应用问题的数据模型由用户定义，用以表示应用问题的数据模型n由基本的数据类型组成由基本的数据类型组成,并包括一组相关的服并包括一组相关的服务（或称操作）务（或称操作）n信息隐蔽和数据封装，使用与实现相分离信息隐蔽和数据封装，使用与实现相分离第章数据结构绪论第章数据结构绪论三、抽象数据类型（三、抽象数据类型（ADTADT）26第三节数据类型第三节数据类型n抽象数据类型（抽象数据类型（ADTADT）是一个数学模型以及定是一个数学模型以及定义在该模型上的一组操作义在该模型上的一组操作n抽

15、象数据类型抽象数据类型=数据结构数据结构+定义在此数据结定义在此数据结 构上的一组操作构上的一组操作第章数据结构绪论第章数据结构绪论三、抽象数据类型（三、抽象数据类型（ADTADT表示）表示）27第三节数据类型第三节数据类型n抽象数据类型可用（抽象数据类型可用（D D，S S，P P）三元组表示三元组表示nD D是数据对象是数据对象nS S是是D D上的关系集上的关系集nP P是对是对D D的基本操作集。的基本操作集。第章数据结构绪论第章数据结构绪论三、抽象数据类型（三、抽象数据类型（ADTADT定义）定义）28第三节数据类型第三节数据类型nADT ADT 抽象数据类型名抽象数据类型名 数据对

16、象：数据对象的定义数据对象：数据对象的定义 数据关系：数据关系的定义数据关系：数据关系的定义 基本操作：基本操作基本操作：基本操作(函数函数)的定义的定义 ADT ADT 抽象数据类型名抽象数据类型名第章数据结构绪论第章数据结构绪论三、抽象数据类型（三、抽象数据类型（ADTADT定义举例）定义举例）29第三节数据类型第三节数据类型nADT Triplet 数据对象：D=e1,e2,e3|e1,e2,e3ElemSet 数据关系：R=,基本操作：Max(T,&e)初始条件：三元组T已存在。操作结果：用e返回T的3个元素中的最大值。Min(T,&e)初始条件：三元组T已存在。操作结果：用e返回T的

17、3个元素中的最小值。ADT Triplet第章数据结构绪论第章数据结构绪论三、抽象数据类型（三、抽象数据类型（ADTADT定义实现）定义实现）30第三节数据类型第三节数据类型n抽象数据类型可以通过固有数据类型抽象数据类型可以通过固有数据类型(C C语言中语言中已实现的数据类型已实现的数据类型)来实现来实现n抽象数据类型抽象数据类型 类类 classclassn数据对象数据对象 数据成员数据成员n基本操作基本操作 成员函数成员函数(方法方法)第章数据结构绪论第章数据结构绪论一、算法（一、算法（AlgorithmAlgorithm）31第四节算法分析第四节算法分析n算法是对特定问题求解步骤的一种描

18、述算法是对特定问题求解步骤的一种描述n是一有限长的操作序列是一有限长的操作序列第章数据结构绪论第章数据结构绪论一、算法（特性）一、算法（特性）32第四节算法分析第四节算法分析n有穷性有穷性：算法在执行有穷步后能结束n确定性确定性：每步定义都是确切、无歧义n可行性可行性：每一条运算应足够基本(已验算正确)n输入输入：有0个或多个输入n输出输出：有一个或多个输出第章数据结构绪论第章数据结构绪论一、算法（举例）一、算法（举例）33第四节算法分析第四节算法分析例子：选择排序例子：选择排序问题：递增排序问题：递增排序解决方案：逐个选择最小数据解决方案：逐个选择最小数据算法框架：算法框架：for(int

19、i=0;i n-1;i+)/n-1趟趟从从ai检查到检查到an-1，找到最小数找到最小数;若最小整数在若最小整数在ak,交换交换ai与与ak;第章数据结构绪论第章数据结构绪论二、算法设计的要求二、算法设计的要求34第四节算法分析第四节算法分析n正确性正确性：满足具体问题的需求n可读性可读性：便于理解和修改n健壮性健壮性：当输入数据非法时，也能适当反应n效率高：效率高：执行时间时间少n空间空间省省：执行中需要的最大存储空间第章数据结构绪论第章数据结构绪论三、时间复杂度三、时间复杂度35第四节算法分析第四节算法分析n衡量算法的效率，主要依据算法执行所需要的衡量算法的效率，主要依据算法执行所需要的时

20、间，即时间复杂度时间，即时间复杂度n事后统计法事后统计法：计算算法开始时间与完成时间差值n事前统计法事前统计法：依据算法选用何种策略及问题的规模n，是常用的方法第章数据结构绪论第章数据结构绪论三、时间复杂度三、时间复杂度36第四节算法分析第四节算法分析n时间复杂度是问题规模时间复杂度是问题规模n n的函数的函数f(nf(n)，即：即：T(nT(n)=)=O(f(nO(f(n)n一般地，时间复杂度用算法中最深层循环内的一般地，时间复杂度用算法中最深层循环内的语句中的原操作的重复执行次数表示语句中的原操作的重复执行次数表示第章数据结构绪论第章数据结构绪论三、时间复杂度三、时间复杂度37第四节算法分

21、析第四节算法分析a.y*=x;b.for(i=1;i=n;i+y*=x;c.for(j=1;j=n;j+for(i=1;i=n;i+y*=x;na,b,c三个算法中，三个算法中，“y*=x;”程序段的时间程序段的时间复杂度分别为复杂度分别为O(1),O(n),O(n2)，分别称为常分别称为常量阶，线性阶，平方阶量阶，线性阶，平方阶第章数据结构绪论第章数据结构绪论三、时间复杂度三、时间复杂度38第四节算法分析第四节算法分析n时间复杂度除常量阶时间复杂度除常量阶O(1),线性阶线性阶O(n),平平方阶方阶O(n2)外，还有对数阶外，还有对数阶O(logn)，排列排列阶阶O(n!)，指数阶指数阶O(

22、2n)等，是相对于问题规等，是相对于问题规模模n的增长率的表示方法的增长率的表示方法n指数阶随问题规模增长过快，一般不宜使用指数阶随问题规模增长过快，一般不宜使用第章数据结构绪论第章数据结构绪论三、时间复杂度三、时间复杂度39第四节算法分析第四节算法分析n如果算法的执行有多种可能的操作顺序，则求如果算法的执行有多种可能的操作顺序，则求其平均时间复杂度其平均时间复杂度n如果无法求取平均时间复杂度，则采用最坏情如果无法求取平均时间复杂度，则采用最坏情况下的时间复杂度况下的时间复杂度n时间复杂度是衡量算法好坏的一个时间复杂度是衡量算法好坏的一个第章数据结构绪论第章数据结构绪论四、空间复杂度四、空间复

23、杂度40第四节算法分析第四节算法分析n空间复杂度指算法执行时，所需要存储空间的空间复杂度指算法执行时，所需要存储空间的量度，它也是问题规模的函数，即：量度，它也是问题规模的函数，即：S(n)=O(f(n)第章数据结构绪论第章数据结构绪论第二章第二章深圳大学计算机系 蔡茂国一、线性数据结构的特点一、线性数据结构的特点42第一节线性表第一节线性表n在数据元素的非空有限集中在数据元素的非空有限集中、存在惟一的一个被称作、存在惟一的一个被称作“第一个第一个”的数据元素的数据元素(如如“”)”)、存在惟一的一个被称作、存在惟一的一个被称作“最后一个最后一个”的数据元素的数据元素(如如“”)”)、除第一个

24、元素外，每个数据元素均只有一个前驱、除第一个元素外，每个数据元素均只有一个前驱、除最后一个元素外，每个数据元素均只有一个后继、除最后一个元素外，每个数据元素均只有一个后继(next)(next)(如如“1”“1”的的nextnext是是“2”,“2”“2”,“2”的的nextnext是是“3”)“3”)第章线性表第章线性表123456二、线性表二、线性表43第一节线性表第一节线性表n线性表是最简单的一类线性数据结构线性表是最简单的一类线性数据结构n线性表是由线性表是由n n个数据元素组成的有限序列，相个数据元素组成的有限序列，相邻数据元素之间存在着序偶关系，可以写为：邻数据元素之间存在着序偶关

25、系，可以写为：(a a1 1,a,a2 2,a ai-1i-1,a ai i,a,ai+1i+1,a an-1n-1,a,an n)其中,ai是表中元素,i表示元素ai的位置,n是表的长度第章线性表第章线性表二、线性表二、线性表44第一节线性表第一节线性表n线性表中的元素具有相同的特性，属于同一数线性表中的元素具有相同的特性，属于同一数据对象，如：据对象，如：1.261.26个字母的字母表个字母的字母表:(:(A,B,C,D,A,B,C,D,Z),Z)2.2.近期每天的平均温度近期每天的平均温度:(30:(30,28 28,29 29,)第章线性表第章线性表一、顺序表一、顺序表45第二节顺序表

26、第二节顺序表n顺序表是线性表的顺序表示顺序表是线性表的顺序表示n用一组地址连续的存储单元依次存储线性表的用一组地址连续的存储单元依次存储线性表的数据元素数据元素第章线性表第章线性表ABCDEYZ b b+1 b+2 b+3 b+4 b+24 b+25一、顺序表（元素位置）一、顺序表（元素位置）46第二节顺序表第二节顺序表n顺序表数据元素的位置：顺序表数据元素的位置：LOC(a i)=LOC(a i-1)+l LOC(a i)=LOC(a1)+(i-1)*l l表示元素占用的内存单元 数第章线性表第章线性表 a1 a2 a i an 1 2 i n b b+l b+(i-1)*l b+(n-1)

27、*l idle二、顺序表的定义二、顺序表的定义47第二节顺序表第二节顺序表n采用采用C C语言中动态分配的语言中动态分配的一维数组一维数组表示顺序表表示顺序表第章线性表第章线性表#define LIST_INIT_SIZE 100/线性表存储空间的初始分配量#define LISTINCREMENT 10/线性表存储空间的分配增量Typedef struct ElemType*elem;/存储空间基址intlength;/当前长度int listsize;/当前分配的存储容量(元素数)Sqlist;三、顺序表的初始化三、顺序表的初始化48第二节顺序表第二节顺序表n创建一个顺序表创建一个顺序表L

28、 L第章线性表第章线性表Status InitList_Sq(Sqlist&L)L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType);if(!L.elem)exit(OVERFLOW);/存储分配失败L.length=0;/空表长度为0L.listsize=LIST_INIT_SIZE;/初始存储容量return OK;/InitList_Sq三、顺序表的插入三、顺序表的插入49第二节顺序表第二节顺序表n顺序表的插入操作是指在顺序表的第顺序表的插入操作是指在顺序表的第i-1i-1个数个数据元素和第据元素和第i i个数据元素之间插入一个

29、新的数个数据元素之间插入一个新的数据元素，即将长度为据元素，即将长度为n n的顺序表：的顺序表：(a a1 1,a ai-1i-1,a ai i,a,an n)变成长度为变成长度为n+1n+1的顺序表：的顺序表：(a a1 1,a ai-1i-1,e,e,a ai i,a,an n)第章线性表第章线性表三、顺序表的插入三、顺序表的插入50第二节顺序表第二节顺序表n在第在第3 3个元素与第个元素与第4 4个元素之间插入新元素个元素之间插入新元素b bn需要将最后元素需要将最后元素n n至第至第4 4元素元素(共共7-4+1)7-4+1)都向后移一位都向后移一位置置第章线性表第章线性表 25 34

30、 57 16 48 09 63 0 1 2 3 4 5 6 725 34 57 50 16 48 09 63 5050插入 ei=4 0 1 2 3 4 5 6 7三、顺序表的插入三、顺序表的插入51第二节顺序表第二节顺序表第章线性表第章线性表Status ListInsert_Sq(Sqlist&L,int i,ElemType e)if(iL.length+1)return ERROR;if(L.length=L.listsize)newbase=realloc(L.listsize+LISTINCREMENT)*sizeof(ElemType);if(!newbase)exit(OVER

31、FLOW);L.elem=newbase;L.listsize+=LISTINCRMENT;/以上皆为准备阶段 q=&(L.elemi-1);/找到插入位置 for(p=&(L.elemL.length-1);p=q;-p)*(p+1)=*p;/右移 *q=e;+L.length;return OK;/ListInsert_Sq/请注意元素位置数值较元素序号少1三、顺序表的插入三、顺序表的插入52第二节顺序表第二节顺序表n在顺序表中插入一个元素，需要向后移动元素在顺序表中插入一个元素，需要向后移动元素个数为：个数为：n-i+1n-i+1n平均移动元素数为：平均移动元素数为：n+1 n+1 E

32、Eisis=p pi i x(n-i+1)x(n-i+1)i=1 i=1第章线性表第章线性表三、顺序表的插入三、顺序表的插入53第二节顺序表第二节顺序表n当插入位置等概率时，当插入位置等概率时，p pi i=1/(n+1)=1/(n+1)，因此：因此：n+1 n+1 E Eisis=1/(n+1)x(n-i+1)=n/2 1/(n+1)x(n-i+1)=n/2 i=1 i=1n顺序表插入操作的时间复杂度为顺序表插入操作的时间复杂度为O(nO(n)第章线性表第章线性表四、顺序表的删除四、顺序表的删除54第二节顺序表第二节顺序表n顺序表的删除操作是指将顺序表的第顺序表的删除操作是指将顺序表的第i

33、i个数据个数据元素删除，即将长度为元素删除，即将长度为n n的顺序表：的顺序表：(a a1 1,a ai-1i-1,a ai i,a,ai+1i+1,a,an n)变成长度为变成长度为n-1n-1的顺序表：的顺序表：(a a1 1,a ai-1i-1,a,ai+1i+1,a,an n)第章线性表第章线性表四、顺序表的删除四、顺序表的删除55第二节顺序表第二节顺序表n将第将第4 4个元素删除个元素删除n需要将最后元素需要将最后元素n n至第至第5 5元素元素(共共7-4)7-4)都向前移一位置都向前移一位置第章线性表第章线性表 25 34 57 48 09 63 0 1 2 3 4 5 6 72

34、5 34 57 48 09 63 16删除16i=4 0 1 2 3 4 5 6 7四、顺序表的删除四、顺序表的删除56第二节顺序表第二节顺序表第章线性表第章线性表Status ListDelete_Sq(Sqlist&L,int i,ElemType e)if(iL.length)return ERROR;p=&(L.elemi-1);/找到要删除的元素位置 e=*p;q=L.elem+L.length 1;/找到最后一个元素位置 for(+p;pnext;j=1;/p指向第一个结点while(p&jnext;j+;/顺指针查指if(!p|ji)return ERROR;/第i元素不存在e=

35、p-data;/取第i元素值return OK;/GetElem_L第章线性表第章线性表na1aian L四、找指定元素四、找指定元素66第二节线性链表第二节线性链表n算法时间复杂度主要取决于算法时间复杂度主要取决于while循环中的语循环中的语句频度句频度n频度与被查找元素在单链表中的位置有关频度与被查找元素在单链表中的位置有关n若若1in，则频度为则频度为i-1，否则为否则为nn因此时间复杂度为因此时间复杂度为O(n)第章线性表第章线性表na1aian L五、线性链表的插入五、线性链表的插入67第二节线性链表第二节线性链表n在线性链表的第在线性链表的第i-1元素与第元素与第i元素之间插入一

36、元素之间插入一个新元素个新元素第章线性表第章线性表ai-1aise插入前pai-1aise插入后ps-next=p-next;p-next=s;五、线性链表的插入五、线性链表的插入68第二节线性链表第二节线性链表Status ListInsert_L(LinkList&L,int i,ElemType e)/在带头结点的单链表L中第i个位置之前插入元素ep=L;j=0;while(p&jnext;j+;/寻找i-1结点if(!p|ji-1)return ERROR;s=(LinkList)malloc(sizeof(LNode);/生成新结点s-data=e;s-next=p-next;p-n

37、ext=s;/插入L中return OK;/ListInsert_L第章线性表第章线性表五、线性链表的插入五、线性链表的插入69第二节线性链表第二节线性链表n同样，算法时间复杂度主要取决于同样，算法时间复杂度主要取决于while循环循环中的语句频度中的语句频度n频度与在线性链表中的元素插入位置有关频度与在线性链表中的元素插入位置有关n因此线性链表插入的时间复杂度为因此线性链表插入的时间复杂度为O(n)第章线性表第章线性表六、线性链表的删除六、线性链表的删除70第二节线性链表第二节线性链表n将线性链表的第将线性链表的第i元素删除元素删除第章线性表第章线性表pai-1ai+1ai删除前ai-1ai

38、ai+1pq删除后p-next=p-next-next六、线性链表的删除六、线性链表的删除71第二节线性链表第二节线性链表Status ListDelete_L(LinkList&L,int i,ElemType&e)/在带头结点的单链表L中，删除第i个位置的元素p=L;j=0;while(p-next&jnext;j+;/寻找i结点if(!p-next|ji-1)return ERROR;q=p-next;p-next=q-next;/删除i结点e=q-data;free(q);/取值并释放结点return OK;/ListDelete_L第章线性表第章线性表六、线性链表的删除六、线性链表的

39、删除72第二节线性链表第二节线性链表n同样，算法时间复杂度主要取决于同样，算法时间复杂度主要取决于while循环循环中的语句频度中的语句频度n频度与被删除元素在线性链表中的位置有关频度与被删除元素在线性链表中的位置有关n因此线性链表删除元素的时间复杂度为因此线性链表删除元素的时间复杂度为O(n)第章线性表第章线性表七、静态链表七、静态链表73第二节线性链表第二节线性链表n线性链表也可以采用静态数组实现线性链表也可以采用静态数组实现n与顺序表有两点不同：与顺序表有两点不同：、每个元素包括数据域和指针域、每个元素包括数据域和指针域、元素的逻辑关系由指针确定、元素的逻辑关系由指针确定第章线性表第章线

40、性表DCFBAE7592836 10 4 110 1 2 3 4 5 6 7 8 9 10 数据指针七、静态链表七、静态链表74第二节线性链表第二节线性链表n与单链表区别：与单链表区别：、静态链表暂时不用结点，链成一个备用链表、静态链表暂时不用结点，链成一个备用链表、插入时，从备用链表中申请结点、插入时，从备用链表中申请结点、删除结点时，将结点放入备用链表、删除结点时，将结点放入备用链表第章线性表第章线性表一、循环链表一、循环链表75第三节循环链表第三节循环链表n循环链表是一种特殊的线性链表循环链表是一种特殊的线性链表n循环链表中最后一个结点的指针域指向头结点，循环链表中最后一个结点的指针域指

41、向头结点，整个链表形成一个环。整个链表形成一个环。第章线性表第章线性表na1aianL二、查找、插入和删除二、查找、插入和删除76第三节循环链表第三节循环链表n在循环链表中查找指定元素，插入一个结点或在循环链表中查找指定元素，插入一个结点或删除一个结点的操作与线性链表基本一致删除一个结点的操作与线性链表基本一致n差别仅在于算法中的循环条件不是差别仅在于算法中的循环条件不是p-next或或p是否为空是否为空()，而是它们是否等于头指针，而是它们是否等于头指针(L)第章线性表第章线性表na1aianL一、双向链表一、双向链表77第四节双向链表第四节双向链表n双向链表也是一种特殊的线性链表双向链表也

42、是一种特殊的线性链表n双向链表中每个结点有两个指针，一个指针指双向链表中每个结点有两个指针，一个指针指向直接后继向直接后继(next)，另一个指向直接前驱另一个指向直接前驱(prior)第章线性表第章线性表指向直接前驱指向直接前驱 指向直接指向直接后继后继二、双向循环链表二、双向循环链表78第四节双向链表第四节双向链表n双向循环链表中存在两个环双向循环链表中存在两个环(一个是直接后继一个是直接后继环环(红)，另一个是直接前驱环，另一个是直接前驱环(蓝)第章线性表第章线性表非空表非空表 空表空表LL三、双向链表的定义三、双向链表的定义79第四节双向链表第四节双向链表n定义一个双向链表的结点定义一

43、个双向链表的结点Typedef struct DuLNode ElemTypedata;struct DuLNode*prior;struct DuLNode*next;DuLNode,*DuLinkList;第章线性表第章线性表指向直接前驱指向直接前驱 指向直接指向直接后继后继对于任何一个中间结点有：p=p-next-priorp=p-prior-next四、双向链表的插入四、双向链表的插入80第四节双向链表第四节双向链表n双向链表的插入操作需要改变两个方向的指针双向链表的插入操作需要改变两个方向的指针第章线性表第章线性表L314815pL31482515pss-next=p;s-prior

44、=p-prior;p-prior-next=s;p-prior=s;四、双向链表的删除四、双向链表的删除81第四节双向链表第四节双向链表n双向链表的删除操作需要改变两个方向的指针双向链表的删除操作需要改变两个方向的指针第章线性表第章线性表L314815pL3115p-prior-next=p-next;p-next-prior=p-prior;一、基于空间的比较一、基于空间的比较82第五节顺序表与链表的比较第五节顺序表与链表的比较n存储分配的方式存储分配的方式u顺序表的存储空间是静态分配的顺序表的存储空间是静态分配的u链表的存储空间是动态分配的链表的存储空间是动态分配的n存储密度存储密度=结点

45、数据本身所占的存储量结点数据本身所占的存储量/结点结点结构所占的存储总量结构所占的存储总量u顺序表的存储密度顺序表的存储密度=1=1u链表的存储密度链表的存储密度 1 topstacksizestacksize时，栈满，溢出时，栈满，溢出第章栈和队列第章栈和队列a1topbasean.进栈进栈 出栈出栈四、顺序栈的主要操作四、顺序栈的主要操作91第二节顺序栈第二节顺序栈第章栈和队列第章栈和队列nADT Stack 数据对象：D=ai|aiElemSet,i=1,2,3,n 数据关系：R=|ai-1,aiD 基本操作：InitStack(&S)/构造空栈 Push(&S,e)/进栈 Pop(&S

46、,&e)/出栈 GetTop(S,&e)/取栈顶元素值StackEmpty(S)/栈是否为空 ADT Stack五、创建顺序栈五、创建顺序栈92第二节顺序栈第二节顺序栈第章栈和队列第章栈和队列Status InitStack(SqStack&S)S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType);if(!S.base)exit(OVERFLOW);/存储分配失败S.top=S.base;S.stacksize=STACK_INIT_SIZE;return OK;/InitStacktopbase 空栈空栈六、进栈（插入新元素）

47、六、进栈（插入新元素）93第二节顺序栈第二节顺序栈第章栈和队列第章栈和队列Status Push(SqStack&S,SElemType e)if(S.top S.base=S.stacksize)/栈满，追加存储空间 S.base=(SElemType*)realloc(S.base,(S.stacksize+STACKINCRMENT*sizeof(SElemType);if(!S.base)exit(OVERFLOW);S.top=S.base+S.stacksize;S.stacksize+=STACKINCRMENT;*S.top+=e;return OK;/Pushtopbasee

48、ba e进栈进栈topbaseba 操作前操作前七、出栈（删除元素）七、出栈（删除元素）94第二节顺序栈第二节顺序栈第章栈和队列第章栈和队列Status Pop(SqStack&S,SElemType&e)if(S.top=S.base)return ERROR;e=*-S.top;return OK;/Poptopbaseeba e出栈出栈topbaseeba 操作前操作前八、取栈顶元素八、取栈顶元素95第二节顺序栈第二节顺序栈第章栈和队列第章栈和队列Status GetTop(SqStack S,SElemType&e)if(S.top=S.base)return ERROR;e=*(S.

49、top-1);return OK;/GetToptopbaseeba e进栈进栈topbaseeba 操作前操作前一、数值转换一、数值转换96第三节栈的应用举例第三节栈的应用举例n将十进制转换为其它进制将十进制转换为其它进制(d)d)，其原理为：其原理为：N=(N/d)N=(N/d)*d+N mod dd+N mod d例如：（例如：（1348)10=(2504)8 1348)10=(2504)8，其运算过程如下：，其运算过程如下：N N N/8 N mod 8N/8 N mod 813481348 168 4 168 4 168 168 21 21 0 0 21 21 2 2 5 5 2 2

50、 0 0 2 2第章栈和队列第章栈和队列输出顺序输出顺序计算顺序计算顺序一、数值转换一、数值转换97第三节栈的应用举例第三节栈的应用举例void conversion()InitStack(S);/创建新栈S scanf(“%d”,N);/输入一个十进制数N while(N)Push(S,N%8);/将余数送入栈中 N=N/8;/求整除数 while(!StackEmpty(S)/如果栈不空 Pop(S,e);/将栈中数出栈 printf(%d,e);/conversion第章栈和队列第章栈和队列二、行编辑程序二、行编辑程序98第三节栈的应用举例第三节栈的应用举例n用户输入一行字符用户输入一行