《数据结构线性表.ppt》由会员分享，可在线阅读，更多相关《数据结构线性表.ppt（74页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数据结构线性表现在学习的是第1页，共74页2.1 线性表的类型定义线性表的类型定义 线性表线性表(Linear List)：是由：是由n(n0)个数据元素个数据元素(结点结点)a1，a2，an组成的有限序列。该序列中的所有结点具有相同组成的有限序列。该序列中的所有结点具有相同的数据类型。其中数据元素的个数的数据类型。其中数据元素的个数n称为线性表的长度。称为线性表的长度。当当n=0时，称为空表。时，称为空表。当当n0时，将非空的线性表记作：时，将非空的线性表记作：(a1，a2，an)a1称为线性表的称为线性表的第一个第一个(首首)结点，结点，an称为线性表的称为线性表的最后一个最后一个(尾尾)
2、结点。结点。2.1.1 线性表的定义线性表的定义现在学习的是第2页，共74页a1，a2，ai-1都是都是ai(2in)的的前驱前驱，其中，其中ai-1是是ai的的直接前驱直接前驱;ai+1，ai+2，an都是都是ai(1i n-1)的的后继后继，其中，其中ai+1是是ai的的直接直接后继后继。2.1.2 线性表的逻辑结构线性表的逻辑结构 线性表中的数据元素线性表中的数据元素ai所代表的具体含义随具体应用的不所代表的具体含义随具体应用的不同而不同，在线性表的定义中，只不过是一个抽象的表示符同而不同，在线性表的定义中，只不过是一个抽象的表示符号。号。线性表中的线性表中的结点结点可以是可以是单值元素
3、单值元素(每个元素只有一个每个元素只有一个数据项数据项)。例例1:26个英文字母组成的字母表：个英文字母组成的字母表：(A，B，C、Z）现在学习的是第3页，共74页例例2：某校从某校从1978年到年到1983年各种型号的计算机拥有量的年各种型号的计算机拥有量的变化情况：变化情况：(6，17，28，50，92，188）例例3：一副扑克的点数一副扑克的点数 (2，3，4，J，Q，K，A)线性表中的线性表中的结点结点可以是可以是记录型记录型元素，每个元素含有多元素，每个元素含有多个数据项个数据项，每个项称为结点的一个域，每个项称为结点的一个域。每个元素有一个。每个元素有一个可以唯一标识每个结点的可以
4、唯一标识每个结点的数据项组数据项组，称为，称为关键字关键字。例例4：某校某校2001级同学的基本情况：级同学的基本情况：(2001414101，张里户张里户，男男，06/24/1983)，(2001414102，张化司张化司，男男，08/12/1984)，(2001414102，李利辣李利辣，女女，08/12/1984)若线性表中的结点是若线性表中的结点是按值按值(或按关键字值或按关键字值)由小到大由小到大(或或由大到小由大到小)排列排列的，称线性表是有序的。的，称线性表是有序的。现在学习的是第4页，共74页2.1.3 线性表的抽象数据类型定义线性表的抽象数据类型定义ADT List数据对象：
5、数据对象：D=ai|aiElemSet,i=1,2,n,n0 数据关系：数据关系：R=|ai-1,aiD,i=2,3,n 基本操作：基本操作：InitList(&L)操作结果：构造一个空的线性表操作结果：构造一个空的线性表L；线性表是一种相当灵活的数据结构，其长度可根据线性表是一种相当灵活的数据结构，其长度可根据需要增长或缩短。需要增长或缩短。对线性表的数据元素可以访问、插入和删除。对线性表的数据元素可以访问、插入和删除。现在学习的是第5页，共74页ListLength(L)初始条件：线性表初始条件：线性表L已存在；已存在；操作结果：若操作结果：若L为空表，则返回为空表，则返回TRUE，否则返
6、回，否则返回FALSE；.GetElem(L,i,&e)初始条件：线性表初始条件：线性表L已存在，已存在，1iListLength(L)；操作结果：用操作结果：用e返回返回L中第中第i个数据元素的值；个数据元素的值；ListInsert(L,i,&e)初始条件：线性表初始条件：线性表L已存在，已存在，1iListLength(L)；操作结果：在线性表操作结果：在线性表L中的第中的第i个位置插入元素个位置插入元素e；ADT List现在学习的是第6页，共74页2.2 线性表的顺序表示和实现线性表的顺序表示和实现 顺序存储顺序存储：把线性表的结点：把线性表的结点按逻辑顺序按逻辑顺序依次存放在一组地
7、址依次存放在一组地址连续的存储单元连续的存储单元里。用这种方法存储的线性表简称顺序表。里。用这种方法存储的线性表简称顺序表。顺序存储顺序存储的线性表的的线性表的特点特点：线性表的逻辑顺序与物理顺序一致线性表的逻辑顺序与物理顺序一致;数据元素之间的关系是以元素在计算机内数据元素之间的关系是以元素在计算机内“物理位置物理位置相邻相邻”来体现。来体现。设有非空的线性表：设有非空的线性表：(a1，a2，an)。顺序存储如图。顺序存储如图2-1所示。所示。2.2.1 线性表的顺序存储结构线性表的顺序存储结构现在学习的是第7页，共74页 在具体的机器环境下在具体的机器环境下：设线性表的每个元素需占用：设线
8、性表的每个元素需占用1个存个存储单元，以所占的第一个单元的存储地址作为数据元素的存储位储单元，以所占的第一个单元的存储地址作为数据元素的存储位置。则线性表中第置。则线性表中第i+1个数据元素的存储位置个数据元素的存储位置LOC(ai+1)和第和第i个数个数据元素的存储位置据元素的存储位置LOC(ai)之间满足下列关系：之间满足下列关系：LOC(ai+1)=LOC(ai)+l 线性表的第线性表的第i个数据元素个数据元素ai的存储位置为：的存储位置为：LOC(ai)=LOC(a1)+(i-1)*l a1 a2 ai an Loc(a1)Loc(ai)+(i-1)*l 图图2-1 线性表的顺序存储表
9、示线性表的顺序存储表示现在学习的是第8页，共74页 在高级语言在高级语言(如如C C语言语言)环境下环境下：数组具有随机存取的特：数组具有随机存取的特性性，因此，借助，因此，借助数组数组来描述顺序表。除了用数组来存储线性来描述顺序表。除了用数组来存储线性表的元素之外，顺序表还应该有表示线性表的长度属性，所以表的元素之外，顺序表还应该有表示线性表的长度属性，所以用用结构类型结构类型来定义顺序表类型。来定义顺序表类型。#define OK 1#define ERROR -1#define MAX_SIZE 100typedef int Status;typedef int ElemType;typ
10、edef struct sqlist ElemType Elem_arrayMAX_SIZE;int length;SqList;现在学习的是第9页，共74页2.2.2 顺序表的基本操作顺序表的基本操作 顺序存储结构中，很容易实现线性表的一些操作：初始化、顺序存储结构中，很容易实现线性表的一些操作：初始化、赋值、查找、修改、插入、删除、求长度等赋值、查找、修改、插入、删除、求长度等。以下将对几种主要的操作进行讨论以下将对几种主要的操作进行讨论。1 顺序线性表初始化顺序线性表初始化 Status Init_SqList(SqList*L)L-elem_array=(ElemType*)mallo
11、c(MAX_SIZE*sizeof(ElemType);if(!L-elem_array)return ERROR;else L-length=0;return OK;现在学习的是第10页，共74页2 顺序顺序线性表的插入线性表的插入 在线性表在线性表 L=(a1，a i-1，ai，ai+1，an)中中的第的第i(1in)个位置上插入一个新结点个位置上插入一个新结点e，使其成为线性表，使其成为线性表：L=(a1，a i-1，e，ai，ai+1，an)实现步骤实现步骤(1)(1)将线性表将线性表L中的中的第第i个至第个至第n个结点后移一个位置。个结点后移一个位置。(2)(2)将结点将结点e插入到
12、结点插入到结点ai-1之后之后。(3)(3)线性表长度加线性表长度加1。现在学习的是第11页，共74页算法描述算法描述Status Insert_SqList(Sqlist*L，int i，ElemType e)int j;if (iL-length-1)return ERROR;if (L-length=MAX_SIZE)printf(“线性表溢出线性表溢出!n”);return ERROR;for (j=L-length1;j=i-1;-j)L-Elem_arrayj+1=L-Elem_arrayj;/*i-1位置以后的所有结点后移位置以后的所有结点后移 */L-Elem_arrayi-1
13、=e;/*在在i-1位置插入结点位置插入结点 */L-length+;return OK;现在学习的是第12页，共74页 时间复杂度分析时间复杂度分析 在线性表在线性表L中的中的第第i个个元素之前插入新结点，其时间主要耗元素之前插入新结点，其时间主要耗费在表中结点的移动操作上，因此，可用结点的移动来估计算法费在表中结点的移动操作上，因此，可用结点的移动来估计算法的时间复杂度。的时间复杂度。设设在线性表在线性表L中的中的第第i个个元素之前插入结点的概率为元素之前插入结点的概率为Pi，不，不失一般性，设各个位置插入是等概率，则失一般性，设各个位置插入是等概率，则Pi=1/(n+1)，而插，而插入时
14、移动结点的次数为入时移动结点的次数为n-i+1。总的平均移动次数：总的平均移动次数：Einsert=pi*(n-i+1)(1in)Einsert=n/2。即即在顺序表上做插入运算，平均要移动表上一半结点。在顺序表上做插入运算，平均要移动表上一半结点。当表长当表长n较大时，算法的效率相当低。因此算法的平均时间较大时，算法的效率相当低。因此算法的平均时间复杂度为复杂度为O(n)。现在学习的是第13页，共74页3 顺序线性表的删除顺序线性表的删除 在线性表在线性表 L=(a1，a i-1，ai，ai+1，an)中删除结点中删除结点ai(1in)，使其成为线性表，使其成为线性表：L=(a1，ai-1，
15、ai+1，an)实现步骤实现步骤(1)(1)将线性表将线性表L中的中的第第i+1个至第个至第n个结点依此向前移动一个个结点依此向前移动一个位置。位置。(2)(2)线性表长度减线性表长度减1。算法描述算法描述ElemType Delete_SqList(Sqlist*L，int i)int k;ElemType x;现在学习的是第14页，共74页if (L-length=0)printf(“线性表线性表L为空为空!n”);return ERROR;else if(iL-length)printf(“要删除的数据元素不存在要删除的数据元素不存在!n”);return ERROR;else x=L-
16、Elem_arrayi-1;/*保存结点的值保存结点的值*/for(k=i;klength;k+)L-Elem_arrayk-1=L-Elem_arrayk;/*i位置以后的所有结点前移位置以后的所有结点前移 */L-length-;return(x);现在学习的是第15页，共74页 时间复杂度分析时间复杂度分析 删除线性表删除线性表L中的中的第第i个个元素，其时间主要耗费在表中结点元素，其时间主要耗费在表中结点的移动操作上，因此，可用结点的移动来估计算法的时间复杂度。的移动操作上，因此，可用结点的移动来估计算法的时间复杂度。设设在线性表在线性表L中中删除第删除第i个个元素的概率为元素的概率为
17、Pi，不失一般，不失一般性，设删除各个位置是等概率，则性，设删除各个位置是等概率，则Pi=1/n，而删除时移动，而删除时移动结点的次数为结点的次数为n-i。则总的平均移动次数：则总的平均移动次数：Edelete=pi*(n-i)(1in)Edelete=(n-1)/2。即即在顺序表上做删除运算，平均要移动表上一半结点。在顺序表上做删除运算，平均要移动表上一半结点。当表长当表长n较大时，算法的效率相当低。因此算法的平均时间复较大时，算法的效率相当低。因此算法的平均时间复杂度为杂度为O(n)。现在学习的是第16页，共74页4 顺序线性表的查找定位删除顺序线性表的查找定位删除 在线性表在线性表 L=
18、(a1，a2，an)中删除值为中删除值为x的第一个结点的第一个结点。实现步骤实现步骤(1)(1)在线性表在线性表L查找值为查找值为x的第的第一个数据元素。一个数据元素。(2)(2)将从找到的位置至最后一将从找到的位置至最后一个结点依次向前移动一个位置。个结点依次向前移动一个位置。(3)(3)线性表长度减线性表长度减1。算法描述算法描述Status Locate_Delete_SqList(Sqlist*L，ElemType x)/*删除线性表删除线性表L中值为中值为x的的第第一个一个结点结点 */int i=0,k;现在学习的是第17页，共74页while (ilength)/*查找值为查找值
19、为x的的第第一个一个结点结点*/if (L-Elem_arrayi!=x)i+;else for(k=i+1;klength;k+)L-Elem_arrayk-1=L-Elem_arrayk;L-length-;break;if (iL-length)printf(“要删除的数据元素不存在要删除的数据元素不存在!n”);return ERROR;return OK;现在学习的是第18页，共74页 时间复杂度分析时间复杂度分析 时间主要耗费在数据元素的比较和移动操作上。时间主要耗费在数据元素的比较和移动操作上。首先，首先，在线性表在线性表L中查找值为中查找值为x的的结点是否存在结点是否存在;其次
20、，若其次，若值为值为x的的结点存在，且在结点存在，且在线性表线性表L中的位置为中的位置为i，则在，则在线性表线性表L中删除中删除第第i个个元素。元素。设设在线性表在线性表L删除删除数据元素概率为数据元素概率为Pi，不失一般性，设各，不失一般性，设各个位置是等概率，则个位置是等概率，则Pi=1/n。比较的平均次数比较的平均次数：Ecompare=pi*i (1in)Ecompare=(n+1)/2。删除时平均移动次数删除时平均移动次数：Edelete=pi*(n-i)(1in)Edelete=(n-1)/2。平均时间复杂度：平均时间复杂度：Ecompare+Edelete=n，即为即为O(n)现
21、在学习的是第19页，共74页顺序存储的线性表的特点顺序存储的线性表的特点:优点优点：表中任一结点的存取很方便，也能进行插入和删除操作。缺点缺点：(1)插入和删除不方便插入和删除不方便。为保持连续存放，操作中需要移动大量元素。(2)会造成空间的浪费以及不易扩充。数组大小固定大小固定，对于处理长度变化较大的线性表时，分配数组大小不够，会造成溢出;分配大小太大，会造成空间浪费。现在学习的是第20页，共74页2.3 线性表的链式存储线性表的链式存储 2.3.1 线性表的链式存储结构线性表的链式存储结构 链式存储链式存储：用用一组任意的存储单元存储一组任意的存储单元存储线性表中的数线性表中的数据元素。用
22、这种方法存储的线性表简称据元素。用这种方法存储的线性表简称线性链表线性链表。存储链表中结点的一组任意的存储单元可以是连续的，存储链表中结点的一组任意的存储单元可以是连续的，也可以是不连续的，甚至是零散分布在内存中的任意位置上也可以是不连续的，甚至是零散分布在内存中的任意位置上的。的。链表中结点的逻辑顺序和物理顺序不一定相同。链表中结点的逻辑顺序和物理顺序不一定相同。现在学习的是第21页，共74页 为了正确表示结点间的逻辑关系，在存储每个结点值为了正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其直接后继结点的地址的同时，还必须存储指示其直接后继结点的地址(或位置或位置)，称为指
23、针，称为指针(pointer)或链或链(link)，这两部分组成了链表中的，这两部分组成了链表中的结点结构，如图结点结构，如图2-2所示。所示。链表是通过每个结点的指针域将线性表的链表是通过每个结点的指针域将线性表的n个结点按其逻辑个结点按其逻辑次序链接在一起的。次序链接在一起的。每一个结只包含一个指针域的链表，称为每一个结只包含一个指针域的链表，称为单链表单链表。为操作方便，总是在链表的第一个结点之前附设一为操作方便，总是在链表的第一个结点之前附设一个头个头结点结点(头指针头指针)head指向第一个结点。头结点的数据域可以不存储指向第一个结点。头结点的数据域可以不存储任何信息任何信息(或链表
24、长度等信息或链表长度等信息)。data next图图2-2 链表结点结构链表结点结构data：数据域，存放结点的值。：数据域，存放结点的值。next：指针域，存放结点的：指针域，存放结点的直接后继的地址。直接后继的地址。现在学习的是第22页，共74页 3695headfat1100bat1300cat1305eat3700hatNULL1100370013001305bat cat eat fat hat head 图图2-3 带头结点的单链表的逻辑状态、物理存储方式带头结点的单链表的逻辑状态、物理存储方式 单链表是由表头唯一确定，因此单链表可单链表是由表头唯一确定，因此单链表可以用头指针的名
25、字来命名。以用头指针的名字来命名。例例1 1、线性表、线性表L=(bat，cat，eat，fat，hat)其其带头结点的单带头结点的单链表的逻辑状态和物理存链表的逻辑状态和物理存储方式如图储方式如图2-3所示。所示。现在学习的是第23页，共74页1 结点的描述与实现结点的描述与实现 C语言中用语言中用带指针的结构体类型带指针的结构体类型来描述来描述typedef struct Lnode ElemType data;/*数据域，保存结点的值数据域，保存结点的值*/struct Lnode *next;/*指针域指针域*/LNode;/*结点的类型结点的类型*/2 结点的实现结点的实现 结点是通
26、过动态分配和释放来的实现结点是通过动态分配和释放来的实现，即需要时分配，不，即需要时分配，不需要时释放。实现时是分别使用需要时释放。实现时是分别使用C语言提供的标准函数：语言提供的标准函数：malloc()，realloc()，sizeof()，free()。现在学习的是第24页，共74页动态分配动态分配 p=(LNode*)malloc(sizeof(LNode);函数函数malloc分配了一个类型为分配了一个类型为LNode的结点变量的空间，并的结点变量的空间，并将其首地址放入指针变量将其首地址放入指针变量p中。中。动态释放动态释放 free(p);系统回收由指针变量系统回收由指针变量p所
27、指向的内存区。所指向的内存区。P必须是最近一次必须是最近一次调用调用malloc函数时的返回值。函数时的返回值。3 最常用的基本操作及其示意图最常用的基本操作及其示意图 结点的赋值结点的赋值 LNode *p;p=(LNode*)malloc(sizeof(LNode);p-data=20;p-next=NULL;p20NULL现在学习的是第25页，共74页 常见的指针操作常见的指针操作 q=p;pa操作前paq操作后 q=p-next;bpa操作前操作后qbpa p=p-next;bpa操作前操作后pba q-next=p;cpbqa操作前操作后qbacp(a)现在学习的是第26页，共74页
28、 q-next=p-next;(a)xypbqa操作前操作后qbaxyp操作前ypxbqa操作后ypxbqa(b)操作前ypxbqa操作后ypxbqa(b)现在学习的是第27页，共74页2.3.2 单线性链式的基本操作单线性链式的基本操作1 建立单链表建立单链表 假设线性表中结点的数据类型是整型，以假设线性表中结点的数据类型是整型，以32767作为结作为结束标志。动态地建立单链表的常用方法有如下两种：束标志。动态地建立单链表的常用方法有如下两种：头插入头插入法法，尾插入法尾插入法。头插入法建表头插入法建表 从一个空表开始，重复读入数据，生成新结点，将读入从一个空表开始，重复读入数据，生成新结点
29、，将读入数据存放到新结点的数据域中，然后将新结点插入到当前链数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头上，直到读入结束标志为止。即表的表头上，直到读入结束标志为止。即每次插入的结点都每次插入的结点都作为链表的第一个结点作为链表的第一个结点。现在学习的是第28页，共74页算法描述算法描述LNode *create_LinkList(void)/*头插入法创建单链表头插入法创建单链表,链表的头结点链表的头结点head作为返回值作为返回值 */int data;LNode*head,*p;head=(LNode *)malloc(sizeof(LNode);head-next=NU
30、LL;/*创建链表的表头结点创建链表的表头结点head */while(1)scanf(“%d”,&data);if(data=32767)break;p=(LNode *)malloc(sizeof(LNode);pdata=data;/*数据域赋值数据域赋值 */现在学习的是第29页，共74页pnext=headnext;headnext=p;/*钩链钩链，新创建，新创建的结点总是作为第一个结点的结点总是作为第一个结点 */return(head);(2)尾插入法建表尾插入法建表 头插入法建立链表虽然算法简单，但生成的链表中结头插入法建立链表虽然算法简单，但生成的链表中结点的次序和输入的顺
31、序相反。若希望二者次序一致，可采点的次序和输入的顺序相反。若希望二者次序一致，可采用尾插法建表。该方法是将用尾插法建表。该方法是将新结点插入到当前链表的表尾，新结点插入到当前链表的表尾，使其成为当前链表的尾结点使其成为当前链表的尾结点。现在学习的是第30页，共74页算法描述算法描述LNode *create_LinkList(void)/*尾插入法创建单链表尾插入法创建单链表,链表的头结点链表的头结点head作为返回值作为返回值 */int data;LNode*head,*p,*q;head=p=(LNode *)malloc(sizeof(LNode);p-next=NULL;/*创建单链
32、表的表头结点创建单链表的表头结点head */while(1)scanf(“%d”,&data);if(data=32767)break;q=(LNode *)malloc(sizeof(LNode);qdata=data;/*数据域赋值数据域赋值 */qnext=pnext;pnext=q;p=q;现在学习的是第31页，共74页/*钩链钩链，新创建，新创建的结点总是作为最后一个结点的结点总是作为最后一个结点*/return(head);无论是哪种插入方法，如果要插入建立的单线性链表的结无论是哪种插入方法，如果要插入建立的单线性链表的结点是点是n个，个，算法的时间复杂度均为算法的时间复杂度均为
33、O(n)。对于单链表，无论是哪种操作，只要涉及到钩链对于单链表，无论是哪种操作，只要涉及到钩链(或或重新钩链重新钩链)，如果，如果没有明确给出直接后继没有明确给出直接后继，钩链，钩链(或重新钩或重新钩链链)的次序必须是的次序必须是“先右后左先右后左”。现在学习的是第32页，共74页2 单链表的查找单链表的查找(1)按序号查找按序号查找取单链表中的第取单链表中的第i个元素。个元素。对于单链表，不能象顺序表中那样直接按序号对于单链表，不能象顺序表中那样直接按序号i访问结访问结点，而只能从链表的头结点出发，沿链域点，而只能从链表的头结点出发，沿链域next逐个结点往下逐个结点往下搜索，直到搜索到第搜
34、索，直到搜索到第i个结点为止。因此，个结点为止。因此，链表不是随机存取链表不是随机存取结构结构。设单链表的长度为设单链表的长度为n，要查找表中第，要查找表中第i个结点，仅当个结点，仅当1in时，时，i的值是合法的。的值是合法的。现在学习的是第33页，共74页算法描述算法描述ElemType Get_Elem(LNode*L，int i)int j;LNode*p;p=L-next;j=1;/*使使p指向第一个结点指向第一个结点 */while (p!=NULL&jnext;j+;/*移动指针移动指针p,j计数计数 */if (j!=i)return(-32768);else return(p-
35、data);/*p为为NULL 表示表示i太大太大;ji表示表示i为为0 */移动指针移动指针p的频度：的频度：in：n次。次。时间复杂度时间复杂度:O(n):O(n)。现在学习的是第34页，共74页(2)按值查找按值查找 按值查找是在链表中，查找是否有结点值等于给定值按值查找是在链表中，查找是否有结点值等于给定值key的的结点结点?若有，则返回首次找到的值为若有，则返回首次找到的值为key的结点的存储位置；的结点的存储位置；否则返回否则返回NULL。查找时从开始结点出发，沿链表逐个将结点的。查找时从开始结点出发，沿链表逐个将结点的值和给定值值和给定值key作比较。作比较。现在学习的是第35页
36、，共74页算法描述算法描述LNode *Locate_Node(LNode*L，int key)/*在以在以L为头结点的单链表中查找值为为头结点的单链表中查找值为key的第一个结点的第一个结点 */LNode*p=Lnext;while (p!=NULL&pdata!=key)p=pnext;if (pdata=key)return p;else printf(“所要查找的结点不存在所要查找的结点不存在!n”);retutn(NULL);算法的执行与形参算法的执行与形参keykey有关，平均时间复杂度为有关，平均时间复杂度为O(n)O(n)。现在学习的是第36页，共74页3 单链表的插入单链表
37、的插入 插入运算是将值为插入运算是将值为e的新结点插入到表的第的新结点插入到表的第i个结点的位个结点的位置上，即插入到置上，即插入到ai-1与与ai之间。因此，必须首先找到之间。因此，必须首先找到ai-1所在所在的的结点结点p，然后生成一个数据域为，然后生成一个数据域为e的新结点的新结点q，q结点作为结点作为p的直的直接后继结点。接后继结点。算法描述算法描述void Insert_LNode(LNode*L，int i，ElemType e)/*在以在以L为头结点的单链表的第为头结点的单链表的第i个位置插入值为个位置插入值为e的结点的结点*/int j=0;LNode*p，*q;p=Lnext
38、;while (p!=NULL&jnext;j+;现在学习的是第37页，共74页if (j!=i-1)printf(“i太大或太大或i为为0!n”);else q=(LNode*)malloc(sizeof(LNode);qdata=e;qnext=pnext;pnext=q;设链表的长度为设链表的长度为n，合法的插入位置是，合法的插入位置是1in。算法的时。算法的时间主要耗费间主要耗费移动指针移动指针p上，故上，故时间复杂度亦为时间复杂度亦为O(n)O(n)。现在学习的是第38页，共74页4 单链表的删除单链表的删除 按序号删除按序号删除 删除单链表中的第删除单链表中的第i个结点。个结点。为
39、了删除第为了删除第i个结点个结点ai，必须找到结点的存储地址。该存，必须找到结点的存储地址。该存储地址是在其直接前趋结点储地址是在其直接前趋结点ai-1的的next域中，因此，必须首域中，因此，必须首先找到先找到ai-1的存储位置的存储位置p，然后令，然后令pnext指向指向ai的直接后继结的直接后继结点，即把点，即把ai从链上摘下。最后释放结点从链上摘下。最后释放结点ai的空间，将其归还给的空间，将其归还给“存储池存储池”。设单链表长度为设单链表长度为n，则删去第，则删去第i个结点仅当个结点仅当1in时是合时是合法的。则当法的。则当i=n+1时，虽然被删结点不存在，但其前趋结点却时，虽然被删
40、结点不存在，但其前趋结点却存在，是终端结点。故判断条件之一是存在，是终端结点。故判断条件之一是pnext!=NULL。显。显然此算法的然此算法的时间复杂度也是时间复杂度也是O(n)O(n)。现在学习的是第39页，共74页算法描述算法描述void Delete_LinkList(LNode*L，int i)/*删除以删除以L为头结点的单链表中的第为头结点的单链表中的第i i个结点个结点 */int j=1;LNode*p，*q;p=L;q=L-next;while (p-next!=NULL&jnext;j+;if (j!=i)printf(“i太大或太大或i为为0!n”);else pnext
41、=qnext;free(q);现在学习的是第40页，共74页 按值删除按值删除 删除单链表中值为删除单链表中值为key的第一个结点。的第一个结点。与按值查找相类似，首先要查找值为与按值查找相类似，首先要查找值为keykey的结点是否存的结点是否存在在?若存在，则删除；否则返回若存在，则删除；否则返回NULL。现在学习的是第41页，共74页算法描述算法描述void Delete_LinkList(LNode*L，int key)/*删除以删除以L为头结点的单链表中值为为头结点的单链表中值为key的第一个结点的第一个结点 */LNode*p=L,*q=Lnext;while (q!=NULL&qd
42、ata!=key)p=q;q=qnext;if (qdata=key)p-next=q-next;free(q);else printf(“所要删除的结点不存在所要删除的结点不存在!n”);现在学习的是第42页，共74页 算法的执行与形参算法的执行与形参k key有关，有关，平均时间复杂度为平均时间复杂度为O(n)O(n)。从上面的讨论可以看出，链表上实现插入和删除运算，无需从上面的讨论可以看出，链表上实现插入和删除运算，无需移动结点，仅需修改指针。解决了顺序表的插入或删除操作需要移动结点，仅需修改指针。解决了顺序表的插入或删除操作需要移动大量元素的问题。移动大量元素的问题。变形之一：变形之一
43、：删除单链表中值为删除单链表中值为key的所有结点。的所有结点。与按值查找相类似，但比前面的算法更简单。与按值查找相类似，但比前面的算法更简单。基本思想基本思想：从单链表的第一个结点开始，对每个结点进行从单链表的第一个结点开始，对每个结点进行检查，若结点的值为检查，若结点的值为keykey，则删除之，然后检查下一个结点，则删除之，然后检查下一个结点，直到所有的结点都检查。直到所有的结点都检查。现在学习的是第43页，共74页算法描述算法描述void Delete_LinkList_Node(LNode*L，int key)/*删除以删除以L为头结点的单链表中值为为头结点的单链表中值为key的第一
44、个结点的第一个结点 */LNode*p=L,*q=Lnext;while (q!=NULL)if(qdata=key)p-next=q-next;free(q);q=p-next;else p=q;q=qnext;现在学习的是第44页，共74页变形之二：变形之二：删除单链表中所有值重复的结点，使得所有结点的值都不相删除单链表中所有值重复的结点，使得所有结点的值都不相同。同。与按值查找相类似，但比前面的算法更复杂。与按值查找相类似，但比前面的算法更复杂。基本思想基本思想：从单链表的第一个结点开始，对每个结点进行检从单链表的第一个结点开始，对每个结点进行检查：检查链表中该结点的所有后继结点，只要有
45、值和该结点的查：检查链表中该结点的所有后继结点，只要有值和该结点的值相同，则删除之；然后检查下一个结点，直到所有的结点都值相同，则删除之；然后检查下一个结点，直到所有的结点都检查。检查。现在学习的是第45页，共74页算法描述算法描述void Delete_Node_value(LNode*L)/*删除以删除以L为头结点的单链表中所有值相同的结点为头结点的单链表中所有值相同的结点 */LNode*p=L-next,*q,*ptr;while (p!=NULL)/*检查链表中所有结点检查链表中所有结点 */*q=p,*ptr=pnext;/*检查结点检查结点p的所有后继结点的所有后继结点ptr *
46、/while(ptr!=NULL)if(ptrdata=p-data)q-next=ptr-next;free(ptr);ptr=q-next;else q=ptr;ptr=ptrnext;现在学习的是第46页，共74页p=p-next;现在学习的是第47页，共74页5 单链表的合并单链表的合并 设有两个有序的单链表，它们的头指针分别是设有两个有序的单链表，它们的头指针分别是La、Lb，将它们合并为以，将它们合并为以Lc为为头指针的有序链表。合并前的示意图头指针的有序链表。合并前的示意图如图如图2-4所示。所示。15 图图2-4 两个有序的单链表两个有序的单链表La，Lb的初始状态的初始状态-
47、2 4 9 Lb pb-7 3 12 23 La Lcpapc现在学习的是第48页，共74页合并了值为合并了值为-7，-2的结点后示意图如图的结点后示意图如图2-5所示。所示。图图2-5 合并了值为合并了值为-7，-2的结点后的状态的结点后的状态-2 4 9 15 Lb pcpbLc-7 3 12 23 La pa算法说明算法说明 算法中算法中算法中算法中pa pa，pbpb分别是待考察的两个链表的当前结点，分别是待考察的两个链表的当前结点，分别是待考察的两个链表的当前结点，分别是待考察的两个链表的当前结点，pcpc是合并过程中合并的链表的最后一个结点。是合并过程中合并的链表的最后一个结点。是
48、合并过程中合并的链表的最后一个结点。是合并过程中合并的链表的最后一个结点。现在学习的是第49页，共74页算法描述算法描述LNode *Merge_LinkList(LNode*La，LNode*Lb)/*合并以合并以La,Lb为头结点的两个有序单链表为头结点的两个有序单链表 */LNode*Lc,*pa,*pb,*pc,*ptr;Lc=La;pc=La ;pa=La-next;pb=Lb-next ;while(pa!=NULL&pb!=NULL)if (pa-datadata)pc-next=pa;pc=pa;pa=pa-next ;/*将将pa所指的结点合并，所指的结点合并，pa指向下一个
49、结点指向下一个结点 */if (pa-datapb-data)pc-next=pb;pc=pb;pb=pb-next ;/*将将pa所指的结点合并，所指的结点合并，pa指向下一个结点指向下一个结点 */现在学习的是第50页，共74页if (pa-data=pb-data)pc-next=pa;pc=pa;pa=pa-next ;ptr=pb;pb=pb-next;free(ptr);/*将将pa所指的结点合并，所指的结点合并，pb所指结点删除所指结点删除 */if (pa!=NULL)pc-next=pa;else pc-next=pb;/*将剩余的结点链上将剩余的结点链上*/free(Lb)
50、;return(Lc);算法分析算法分析 若若La，Lb两个链表的长度分别是两个链表的长度分别是m，n，则链表合并的时间，则链表合并的时间复杂度为复杂度为O(m+n)。现在学习的是第51页，共74页6 6 静态静态链表链表也可用一维数组来描述线性表，类型说明如下也可用一维数组来描述线性表，类型说明如下:#define MAXSIZE 1000 /链表最大长度链表最大长度Typedef struct ElemType data;/数据项数据项 int cur;/游标项游标项 component,SLinkListMAXSIZE;数组的一个分量表示一个结点，同时用指示器数组的一个分量表示一个结点，