《【精品】【考研计算机专业课】武汉大学数据结构ppt课件 第2章线性表（可编辑.ppt》由会员分享，可在线阅读，更多相关《【精品】【考研计算机专业课】武汉大学数据结构ppt课件 第2章线性表（可编辑.ppt（143页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、【考研计算机专业课】武汉大学数据结构PPT课件 第2章 线性表2.1.1 线性表的定义线性表的定义 线性表是具有线性表是具有相同特性的数据元素相同特性的数据元素的一个的一个有限有限序列序列。该序列中所含元素的个数叫做线性表的长度，用该序列中所含元素的个数叫做线性表的长度，用n表示，表示，n0。当当n=0时，表示线性表是一个空表，即表中不包含任何元时，表示线性表是一个空表，即表中不包含任何元素。设序列中第素。设序列中第i（i表示表示逻辑位序逻辑位序）个元素为）个元素为ai（1in）。）。线性表的一般表示为：线性表的一般表示为：(a1，a2，ai，ai+1，an)逻辑结构逻辑结构2.1 线性表的基
2、本概念线性表的基本概念 其其中中a1为为第第一一个个元元素素，又又称称做做表表头头元元素素，a2为为第第二二个元素，个元素，an为最后一个元素，又称做表尾元素。为最后一个元素，又称做表尾元素。例如，在线性表例如，在线性表 (1，4，3，2，8，10)中，中，1为表头元素，为表头元素，10为表尾元素。为表尾元素。2.1.2 线性表的运算线性表的运算 线性表的基本运算如下：线性表的基本运算如下：（1）初始化线性表）初始化线性表InitList(&L)：构造一个空的线性表：构造一个空的线性表L。（2）销销毁毁线线性性表表DestroyList(&L)：释释放放线线性性表表L占占用用的的内内存空间。存
3、空间。逻辑结构抽象运算逻辑结构抽象运算ADT （3）判判线线性性表表是是否否为为空空表表ListEmpty(L)：若若L为为空空表表，则则返回真，否则返回假。返回真，否则返回假。（4）求线性表的长度）求线性表的长度ListLength(L)：返回：返回L中元素个数。中元素个数。（5）输输出出线线性性表表DispList(L)：当当线线性性表表L不不为为空空时时，顺顺序序显示显示L中各结点的值域。中各结点的值域。（6）求求 线线 性性 表表 L中中 指指 定定 位位 置置 的的 某某 个个 数数 据据 元元 素素GetElem(L,i,&e)：用用e返返回回L中中第第 i(1iListLengt
4、h(L)个个元元素素的值。的值。假定线性表的元素类型为假定线性表的元素类型为ElemType，则每个元素所占用，则每个元素所占用存储空间大小（即字节数）为存储空间大小（即字节数）为sizeof(ElemType)，整个线性表，整个线性表所占用存储空间的大小为：所占用存储空间的大小为：n*sizeof(ElemType)其中，其中，n表示线性表的长度。表示线性表的长度。顺序表示意图顺序表示意图 在在定定义义一一个个线线性性表表的的顺顺序序存存储储类类型型时时，需需要要定定义义一一个个数数组组来来存存储储线线线线表表中中的的所所有有元元素素和和定定义义一一个个整整型型变变量量来来存存储储线线性性表
5、的长度表的长度。假假定定数数组组用用dataMaxSize表表示示，长长度度整整型型变变量量用用length表表示示，并并采采用用结结构构体体类类型型表表示示，则则元元素素类类型型为为通通用用类类型型标标识识符符ElemType的线性表的顺序存储类型可描述如下的线性表的顺序存储类型可描述如下：typedef struct ElemType dataMaxSize;int length;SqList;/顺序表类型顺序表类型 其中，其中，data成员存放元素，成员存放元素，length成员存放线性表的实际成员存放线性表的实际长度。长度。说明：由于说明：由于C/C+中数组的下标从中数组的下标从0开始
6、，线性表的第开始，线性表的第i个元个元素素ai存放顺序表的第存放顺序表的第i-1位置上。为了清楚，将位置上。为了清楚，将ai在逻辑序列在逻辑序列中的位置称为中的位置称为逻辑位序逻辑位序，在顺序表中的位置称为，在顺序表中的位置称为物理位序物理位序。地址地址城市名城市名区号区号说明说明100Beijing010首都首都130Shanghai021直辖市直辖市160Wuhan027湖北省省会湖北省省会190Xian029陕西省省会陕西省省会210Nanjing025江苏省省会江苏省省会 对于第对于第1章的逻辑结构章的逻辑结构City，假定每个元素占用，假定每个元素占用30个存个存储单元，数据从储单元
7、，数据从100号单元开始由低地址向高地址方向存号单元开始由低地址向高地址方向存储，对应的顺序表如下：储，对应的顺序表如下：2.2.2 顺序表基本运算的实现顺序表基本运算的实现 一旦采用顺序表存储结构，可以用一旦采用顺序表存储结构，可以用C/C+语言实现线语言实现线性表的各种基本运算。为了方便，假设性表的各种基本运算。为了方便，假设ElemType为为char类型，使用如下自定义类型语句：类型，使用如下自定义类型语句：typedef char ElemType;1.建立顺序表建立顺序表其方法是将给定的含有其方法是将给定的含有n个元素的数组的每个元素依次放入个元素的数组的每个元素依次放入到顺序表中
8、，并将到顺序表中，并将n赋给顺序表的长度成员。算法如下：赋给顺序表的长度成员。算法如下：void CreateList(SqList*&L,ElemType a,int n)/建立顺序表建立顺序表 int i;L=(SqList*)malloc(sizeof(SqList);for(i=0;idatai=ai;L-length=n;由给定的由给定的CC+数组建立顺序表。数组建立顺序表。2.顺序表基本运算算法顺序表基本运算算法 （1）初始化线性表初始化线性表InitList(L)该该运运算算的的结结果果是是构构造造一一个个空空的的线线性性表表L。实实际际上上只只需需将将length成员设置为成员
9、设置为0即可。即可。void InitList(SqList*&L)/引用型指针引用型指针 L=(SqList*)malloc(sizeof(SqList);/分配存放线性表的空间分配存放线性表的空间 L-length=0;本算法的时间复杂度为本算法的时间复杂度为O(1)。LL指针指向一个顺序表指针指向一个顺序表引用的作用：引用的作用：当不用引用时当不用引用时main()SqList*sq;InitList(sq);op(sq);void InitList(SqList*L)L=(SqList*)malloc(sizeof(SqList)；L-length=0；？sqL0？sqmain：调用调
10、用InitList返回到返回到main：顺序表顺序表引用的作用：当使用引用时引用的作用：当使用引用时main()SqList*sq;InitList(sq);op(sq);void InitList(SqList*&L)/用引用用引用 L=(SqList*)malloc(sizeof(SqList)；L-length=0；？sqL0sqmain：调用调用InitList返回到返回到main：顺序表顺序表 （2）销毁线性表销毁线性表DestroyList(L)该运算的结果是释放线性表该运算的结果是释放线性表L占用的内存空间。占用的内存空间。void DestroyList(SqList*&L)f
11、ree(L);本算法的时间复杂度为本算法的时间复杂度为O(1)。思考题：思考题：这里采用顺序指针，而不是直接给定顺序这里采用顺序指针，而不是直接给定顺序表。两者有什么区别？表。两者有什么区别？例如，如果直接采用顺序表：例如，如果直接采用顺序表：void InitList(SqList&L)/引用型引用型 L.length=0;（3）判定是否为空表判定是否为空表ListEmpty(L)该该运运算算返返回回一一个个值值表表示示L是是否否为为空空表表。若若L为为空空表表，则则返返回回1，否则返回，否则返回0。int ListEmpty(SqList*L)return(L-length=0);本算法的
12、时间复杂度为本算法的时间复杂度为O(1)。（4）求线性表的长度）求线性表的长度ListLength(L)该该运运算算返返回回顺顺序序表表L的的长长度度。实实际际上上只只需需返返回回length成成员员的值即可。的值即可。int ListLength(SqList*L)return(L-length);本算法的时间复杂度为本算法的时间复杂度为O(1)。（5）输出线性表）输出线性表DispList(L)该运算当线性表该运算当线性表L不为空时，顺序显示不为空时，顺序显示L中各元素的值。中各元素的值。void DispList(SqList*L)int i;if(ListEmpty(L)return;
13、for(i=0;ilength;i+)printf(%c，L-datai);printf(n);本本算算法法中中基基本本运运算算为为for循循环环中中的的printf语语句句，故故时时间间复杂度为：复杂度为：O(L-length)或或O(n)（n表示表示L中的元素个数）中的元素个数）（6）求某个数据元素值）求某个数据元素值GetElem(L,i,e)该该运运算算返返回回L中中第第 i(1iListLength(L)个个元元素素的的值值，存存放放在在e中。中。int GetElem(SqList*L,int i,ElemType&e)if(iL-length)return 0;e=L-datai
14、-1;return 1;本算法的时间复杂度为本算法的时间复杂度为O(1)。（7）按元素值查找按元素值查找LocateElem(L,e)该该运运算算顺顺序序查查找找第第1个个值值域域与与e相相等等的的元元素素的的位位序序。若若这这样样的的元元素不存在，则返回值为素不存在，则返回值为0。int LocateElem(SqList*L,ElemType e)int i=0;while(ilength&L-datai!=e)i+;if(i=L-length)return 0;else return i+1;本本算算法法中中基基本本运运算算为为while循循环环中中的的i+语语句句，故故时时间间复复杂度
15、为：杂度为：O(L-length)或或O(n)（n表示表示L中的元素个数）中的元素个数）（8）插入数据元素插入数据元素ListInsert(L,i,e)该该运运算算在在顺顺序序表表L的的第第i个个位位置置(1iListLength(L)+1)上插入新的元素上插入新的元素e。思思路路：如如果果i值值不不正正确确，则则显显示示相相应应错错误误信信息息；否否则则将将顺顺序序表表原原来来第第i个个元元素素及及以以后后元元素素均均后后移移一一个个位位置置，腾腾出一个空位置插入新元素，顺序表长度增出一个空位置插入新元素，顺序表长度增1。int ListInsert(SqList*&L,int i,Elem
16、Type e)int j;if(iL-length+1)return 0;i-;/将顺序表逻辑位序转化为将顺序表逻辑位序转化为data下标即物理位序下标即物理位序 for(j=L-length;ji;j-)/将将datai及后面元素后移及后面元素后移 L-dataj=L-dataj-1;L-datai=e;L-length+;/顺序表长度增顺序表长度增1 return 1;a0ai-1aian-1逻辑位序逻辑位序1 i i+1 n MaxSize 对于本算法来说，元素移动的次数不仅与表长对于本算法来说，元素移动的次数不仅与表长L.length=n有关，而且与插入位置有关，而且与插入位置i有关：
17、当有关：当i=n+1时，移动次数为时，移动次数为0；当当i=1时，移动次数为时，移动次数为n，达到最大值。在线性表，达到最大值。在线性表sq中共有中共有n+1个可以插入元素的地方。假设个可以插入元素的地方。假设pi（=）是在第）是在第i个位置个位置上插入一个元素的概率，则在长度为上插入一个元素的概率，则在长度为n的线性表中插入一个的线性表中插入一个元素时所需移动元素的平均次数为：元素时所需移动元素的平均次数为：因此插入算法的平均时间复杂度为因此插入算法的平均时间复杂度为O(n)。an-1ai-1（共（共n-1-(i-1)+1=n-i+1）个）个元素移动元素移动 （9）删除数据元素）删除数据元素
18、ListDelete(L,i,e)删除顺序表删除顺序表L中的第中的第i(1iListLength(L)个元素。个元素。思思路路：如如果果i值值不不正正确确，则则显显示示相相应应错错误误信信息息；否否则则将将线线性性表表第第i个个元元素素以以后后元元素素均均向向前前移移动动一一个个位位置置，这这样样覆覆盖盖了了原原来来的的第第i个个元元素素，达达到到删删除除该该元元素素的的目目的的，最最后后顺顺序表长度减序表长度减1。int ListDelete(SqList*&L,int i,ElemType&e)int j;if(iL-length)return 0;i-;/将逻辑位序转化为将逻辑位序转化为
19、data下标即物理位序下标即物理位序 e=L-datai;for(j=i;jlength-1;j+)/将将datai之后的元素后前移之后的元素后前移 L-dataj=L-dataj+1;L-length-;/顺序表长度减顺序表长度减1 return 1;a0ai-1aian-1逻辑位序逻辑位序1 i i+1 n MaxSize 对于本算法来说，元素移动的次数也与表长对于本算法来说，元素移动的次数也与表长n和删除元素和删除元素的位置的位置i有关：当有关：当i=n时，移动次数为时，移动次数为0；当当i=1时，移动次数为时，移动次数为n-1。在线性表。在线性表sq中共有中共有n个元素可个元素可以被删
20、除。假设以被删除。假设pi（pi=）是删除第）是删除第i个位置上元素的概率，个位置上元素的概率，则在长度为则在长度为n的线性表中删除一个元素时所需移动元素的平的线性表中删除一个元素时所需移动元素的平均次数为：均次数为：=因此删除算法的平均时间复杂度为因此删除算法的平均时间复杂度为O(n)。aian-1（共（共n-1-i+1=n-i个元素）个元素）均前移一个位置均前移一个位置 例例2.2 设设计计一一个个算算法法，将将x插插入入到到一一个个有有序序(从从小小到到大大排排序序)的的线线性性表表（顺顺序序存存储储结结构构即即顺顺序序表表）的的适适当当位位置置上上，并并保保持持线线性性表的有序性。表的
21、有序性。解解：先先通通过过比比较较在在顺顺序序表表L中中找找到到存存放放x的的位位置置i，然然后后将将x插入到插入到L-L-datai中，最后将顺序表的长度增中，最后将顺序表的长度增1。void Insert(SqList*&L,ElemType x)int i=0，j;while(ilength&L-datailength-1;j=i;j-)L-dataj+1=L-dataj;L-datai=x;L-length+;查找插入位置查找插入位置元素后移一个位置元素后移一个位置a0ai-1aian-1逻辑位序逻辑位序1 i i+1 n MaxSize 例例2.3 设设计计一一个个算算法法，将将两两
22、个个元元素素有有序序（从从小小到到大大）的的顺序表合并成一个有序顺序表。顺序表合并成一个有序顺序表。求解思路：求解思路：将两个顺序表进行将两个顺序表进行二路归并二路归并。1 3 5 2 4 10 20 ij 1 3 5 2 4 10 20 ij1 k 1 3 5 2 4 10 20 ij1 2 k1 2 3 kpqrpqrpqr 1 3 5 2 4 10 20 ij1 2 3 4 k 1 3 5 i 2 4 10 20 1 2 3 4 5 kjj 1 3 5 i 2 4 10 20 1 2 3 4 5 k复制pqrpqrpqrSqList*merge(SqList*p,SqList*q)SqL
23、ist*r;int i=0，j=0，k=0;r=(SqList*)malloc(sizeof(SqList);while(ilength&jlength)if(p-dataidataj)r-datak=p-datai;i+;k+;else r-datak=q-dataj;j+;k+;由由p和和q中的元素建立顺序表中的元素建立顺序表qwhile(ilength)r-datak=p-datai;i+;k+;while(jlength)r-datak=q-dataj;j+;k+;r-length=k;/或或p-length+q-length return(r);例例2.4 已已知知长长度度为为n的的
24、线线性性表表A采采用用顺顺序序存存储储结结构构，编编写写一一个个时时间间复复杂杂度度为为O(n)、空空间间复复杂杂度度为为O(1)的的算算法法，该该算算法法删删除除线性表中所有值为线性表中所有值为x的数据元素。的数据元素。解解法法一一：用用k记记录录顺顺序序表表A中中等等于于x的的元元素素个个数数，边边扫扫描描A边边统统计计k，并并将将不不为为x的的元元素素放放置置在在k位位置置上上，最最后后修修改改A的的长长度。度。12323213x=213313AA1A1 A可以直接利用可以直接利用A的空间建立的空间建立A1void delnode1(SqList&A,ElemType x)int k=0
25、，i;/k记录值不等于记录值不等于x的元素个数的元素个数 for (i=0;iA.length;i+)if(A.datai!=x)A.datak=A.datai;k+;/不等于不等于x的元素增的元素增1 A.length=k;/顺序表顺序表A的长度等于的长度等于k算法算法1 1：类似于：类似于建顺序表建顺序表 解解法法二二：用用k记记录录顺顺序序表表A中中等等于于x的的元元素素个个数数，边边扫扫描描A边边统计统计k，并将不为，并将不为x的元素前移的元素前移k个位置，最后修改个位置，最后修改A的长度。的长度。123232x=2i=0,k=0:1前移前移0个位置个位置123232i=1,k=112
26、3232i=2,k=1:3前移前移1个位置个位置133232133232i=3,k=2133232i=4,k=2:3前移前移2个位置个位置133232133232i=5,k=3A.length=6-3=3，A变为：变为：133void delnode2(SqList&A,ElemType x)int k=0，i=0;/k记录值等于记录值等于x的元素个数的元素个数 while(idata0;/取基准取基准i=0;j=A-length-1;while(i!=j)while(ji&A-datajbase)j-;/从右向左扫描，找一个小元素从右向左扫描，找一个小元素 A-datai=A-dataj;/
27、将小元素前移将小元素前移 while(idataidataj=A-datai;/将大元素后移将大元素后移A-datai=base;2.3.1 线性表的链式存储线性表的链式存储链表链表 在在链链式式存存储储中中，每每个个存存储储结结点点不不仅仅包包含含有有所所存存元元素素本本身身的的信信息息（称称之之为为数数据据域域），而而且且包包含含有有元元素素之之间间逻逻辑辑关关系系的的信信息息，即即前前驱驱结结点点包包含含有有后后继继结结点点的的地地址址信信息息，这这称称为为指指针针域域，这这样样可可以以通通过过前前驱驱结结点点的的指指针针域域方方便便地地找找到到后后继继结结点点的的位置，提高数据查找速度
28、。位置，提高数据查找速度。一一般般地地，每每个个结结点点有有一一个个或或多多个个这这样样的的指指针针域域。若若一一个个结结点点中中的的某某个个指指针针域域不不需需要要任任何何结结点点，则则仅仅它它的的值值为为空空，用用常量常量NULL表示。表示。2.3 线性表的链式存储线性表的链式存储 由由于于顺顺序序表表中中的的每每个个元元素素至至多多只只有有一一个个前前驱驱元元素素和和一一个个后后继继元元素素，即即数数据据元元素素之之间间是是一一对对一一的的逻逻辑辑关关系系，所所以以当当进进行行链式存储时，一种最简单也最常用的方法是：链式存储时，一种最简单也最常用的方法是：在在每每个个结结点点中中除除包包
29、含含有有数数据据域域外外，只只设设置置一一个个指指针针域域，用用以以指指向向其其后后继继结结点点，这这样样构构成成的的链链接接表表称称为为线线性性单单向向链链接接表表，简称简称单链表单链表。带头结点单链表示意图带头结点单链表示意图 在线性表的链式存储中，为了便于插入和删除算法的实现，在线性表的链式存储中，为了便于插入和删除算法的实现，每个链表带有一个头结点，并通过头结点的指针唯一标识该链每个链表带有一个头结点，并通过头结点的指针唯一标识该链表。表。或尾结点或尾结点对于第对于第1章的逻辑结构章的逻辑结构City，采用带头结点的单链表，采用带头结点的单链表存储时的结构如下所示：存储时的结构如下所示
30、：在在单单链链表表中中，由由于于每每个个结结点点只只包包含含有有一一个个指指向向后后继继结结点点的的指指针针，所所以以当当访访问问过过一一个个结结点点后后，只只能能接接着着访访问问它它的的后后继继结结点点，而无法访问它的，而无法访问它的前驱结点前驱结点。另一种可以采用的方法是：另一种可以采用的方法是：在在每每个个结结点点中中除除包包含含有有数数值值域域外外，设设置置有有两两个个指指针针域域，分分别别用用以以指指向向其其前前驱驱结结点点和和后后继继结结点点，这这样样构构成成的的链链接接表表称之为线性双向链接表，简称称之为线性双向链接表，简称双链表双链表。带头结点的双链表示意图带头结点的双链表示意
31、图或尾结点或尾结点 在在双双链链表表中中，由由于于每每个个结结点点既既包包含含有有一一个个指指向向后后继继结结点点的的指指针针，又又包包含含有有一一个个指指向向前前驱驱结结点点的的指指针针，所所以以当当访访问问过过一一个个结结点点后后，既既可可以以依依次次向向后后访访问问每每一一个个结结点点，也也可可以以依依次次向向前访问每一个结点。前访问每一个结点。双链表的特点双链表的特点与单链表相比，双链表中从某结点访问前后结点更方便。与单链表相比，双链表中从某结点访问前后结点更方便。在单链表中，假定每个结点类型用在单链表中，假定每个结点类型用LinkList表示，它应包表示，它应包括存储元素的数据域，这
32、里用括存储元素的数据域，这里用data表示，其类型用通用类型标表示，其类型用通用类型标识符识符ElemType表示，还包括存储后继元素位置的指针域，这表示，还包括存储后继元素位置的指针域，这里用里用next表示。表示。LinkList类型的定义如下：类型的定义如下：typedef struct LNode /定义单链表结点类型定义单链表结点类型 ElemType data;struct LNode*next;/指向后继结点指向后继结点 LinkList;2.3.2 2.3.2 单链表基本运算的实现单链表基本运算的实现 1.建立单链表建立单链表 先先考考虑虑如如何何建建立立单单链链表表。假假设设
33、我我们们通通过过一一个个含含有有n个个数数据据的的数数组组来来建建立立单单链链表表。建建立立单单链链表表的的常常用用方方法法有有如如下下两两种：种：（1）头插法建表头插法建表 该方法从一个空表开始，读取字符数组该方法从一个空表开始，读取字符数组a中的字符，生中的字符，生成新结点，将读取的数据存放到新结点的数据域中，然后成新结点，将读取的数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头将新结点插入到当前链表的表头上，直到结束为止。采用上，直到结束为止。采用头插法建表的算法如下：头插法建表的算法如下：void CreateListF(LinkList*&L,ElemType a,int
34、 n)LinkList*s;int i;L=(LinkList*)malloc(sizeof(LinkList);/创建头结点创建头结点 L-next=NULL;for(i=0;idata=ai;s-next=L-next;L-next=s;/将将*s*s插在开始结点之前，头结点之后插在开始结点之前，头结点之后 adcbi=0 i=1 i=2 i=3 L采用头插法建立单链表的过程采用头插法建立单链表的过程La Lda Lcda Lbcda 第第1 1步：建头结点步：建头结点第第2 2步：步：i i0 0，新建，新建a a结点，插入到头结点之后结点，插入到头结点之后第第3 3步：步：i i1 1
35、，新建，新建d d结点，插入到头结点之后结点，插入到头结点之后第第4 4步：步：i i2 2，新建，新建c c结点，插入到头结点之后结点，插入到头结点之后第第5 5步：步：i i3 3，新建，新建b b结点，插入到头结点之后结点，插入到头结点之后 （2）尾插法建表）尾插法建表 头插法建立链表虽然算法简单，但生成的链表中结点的头插法建立链表虽然算法简单，但生成的链表中结点的次序和原数组元素的顺序相反。若希望两者次序一致，可次序和原数组元素的顺序相反。若希望两者次序一致，可采用尾插法建立。采用尾插法建立。该方法是将新结点插到当前链表的表尾上，为此必须增该方法是将新结点插到当前链表的表尾上，为此必须
36、增加一个尾指针加一个尾指针r r，使其，使其始终指向当前链表的尾结点始终指向当前链表的尾结点。采用尾。采用尾插法建表的算法如下：插法建表的算法如下：void CreateListR(LinkList*&L,ElemType a,int n)LinkList*s，*r;int i;L=(LinkList*)malloc(sizeof(LinkList);/创建头结点创建头结点 r=L;/r始终指向终端结点，开始时指向头结点始终指向终端结点，开始时指向头结点 for(i=0;idata=ai;r-next=s;r=s;/将将*s插入插入*r之后之后 r-next=NULL;/终端结点终端结点nex
37、t域置为域置为NULLbcdai=0 i=1 i=2 i=3head头结点头结点b采用尾插法建立单链表的过程采用尾插法建立单链表的过程adc 2.插入结点运算插入结点运算 插插入入运运算算是是将将值值为为x的的新新结结点点插插入入到到单单链链表表的的第第i个个结结点点的的位位置置上上。先先在在单单链链表表中中找找到到第第i-1个个结结点点，再再在在其后插入新结点。其后插入新结点。单链表插入结点的过程如下图所示。单链表插入结点的过程如下图所示。插入结点示意图插入结点示意图 3.删除结点运算删除结点运算 删除运算是将单链表的第删除运算是将单链表的第i个结点删去。先在单链表中个结点删去。先在单链表中
38、找到第找到第i-1个结点，再删除其后的结点。个结点，再删除其后的结点。删除单链表结点的过程如下图所示。删除单链表结点的过程如下图所示。删除结点示意图删除结点示意图 4.线性表基本运算实现线性表基本运算实现 （1）初始化线性表初始化线性表InitList(L)该运算建立一个空的单链表，即创建一个头结点。该运算建立一个空的单链表，即创建一个头结点。void InitList(LinkList*&L)L=(LinkList*)malloc(sizeof(LinkList);/创建头结点创建头结点L-next=NULL;L （2）销毁线性表）销毁线性表DestroyList(L)释放单链表释放单链表L
39、占用的内存空间。即逐一释放全部结点的空间。占用的内存空间。即逐一释放全部结点的空间。void DestroyList(LinkList*&L)LinkList*p=L,*q=p-next;while(q!=NULL)free(p);p=q;q=p-next;free(p);初始时初始时循环结束时循环结束时L pqL pq=NULL （3）判线性表是否为空表）判线性表是否为空表ListEmpty(L)若单链表若单链表L没有数据结点，则返回真，否则返回假。没有数据结点，则返回真，否则返回假。int ListEmpty(LinkList*L)return(L-next=NULL);（4）求线性表的长
40、度）求线性表的长度ListLength(L)返回单链表返回单链表L中数据结点的个数。中数据结点的个数。int ListLength(LinkList*L)LinkList*p=L;int i=0;while(p-next!=NULL)i+;p=p-next;return(i);初始时初始时循环结束时循环结束时L p，i=0L p p，i i为结点个数为结点个数 （5）输出线性表）输出线性表DispList(L)逐逐一一扫扫描描单单链链表表L的的每每个个数数据据结结点点，并并显显示示各各结结点点的的data域域值。值。void DispList(LinkList*L)LinkList*p=L-n
41、ext;while(p!=NULL)printf(%c，p-data);p=p-next;printf(n);（6）求线性表）求线性表L中指定位置的某个数据元素中指定位置的某个数据元素GetElem(L,i,&e)思思路路：在在单单链链表表L中中从从头头开开始始找找到到第第i个个结结点点，若若存存在在第第i个个数数据结点，则将其据结点，则将其data域值赋给变量域值赋给变量e。int GetElem(LinkList*L,int i,ElemType&e)int j=0;LinkList*p=L;while(jnext;if(p=NULL)return 0;/不存在第不存在第i个数据结点个数据
42、结点 else /存在第存在第i个数据结点个数据结点 e=p-data;return 1;循环结束时循环结束时 Le ij （7）按元素值查找）按元素值查找LocateElem(L,e)思思路路：在在单单链链表表L中中从从头头开开始始找找第第1个个值值域域与与e相相等等的的结结点点，若若存在这样的结点，则返回位置，否则返回存在这样的结点，则返回位置，否则返回0。int LocateElem(LinkList*L,ElemType e)LinkList*p=L-next;int i=1;while(p!=NULL&p-data!=e)p=p-next;i+;if(p=NULL)return(0)
43、;else return(i);循环结束时循环结束时 Le i （8）插入数据元素）插入数据元素ListInsert(&L,i,e)思思路路：先先在在单单链链表表L中中找找到到第第i-1个个结结点点*p，若若存存在在这这样样的的结结点，将值为点，将值为e的结点的结点*s插入到其后。插入到其后。int ListInsert(LinkList*&L,int i,ElemType e)int j=0;LinkList*p=L，*s;while(jnext;if(p=NULL)return 0;/未找到位序为未找到位序为i-1的结点的结点 else/找到位序为找到位序为i-1的结点的结点*p s=(L
44、inkList*)malloc(sizeof(LinkList);/创建新结点创建新结点*s s-data=e;s-next=p-next;p-next=s;/将将*s插入到插入到*p之后之后 return 1;（9）删除数据元素）删除数据元素ListDelete(&L,i,&e)思思路路：先先在在单单链链表表L L中中找找到到第第i-1i-1个个结结点点*p*p，若若存存在在这这样样的的结结点，且也存在后继结点，则删除该后继结点。点，且也存在后继结点，则删除该后继结点。int ListDelete(LinkList*&L,int i,ElemType&e)int j=0;LinkList*p
45、=L，*q;while(jnext;if(p=NULL)return 0;/未找到位序为未找到位序为i-1的结点的结点 else /找到位序为找到位序为i-1的结点的结点*p q=p-next;/q指向要删除的结点指向要删除的结点 if(q=NULL)return 0;/若不存在第若不存在第i个结点，返回个结点，返回0 p-next=q-next;/从单链表中删除从单链表中删除*q结点结点 free(q);/释放释放*q结点结点 return 1;例例2.5 设设C=a1，b1，a2，b2，an，bn为为一一线线性性表表，采采用用带带头头结结点点的的hc单单链链表表存存放放，编编写写一一个个算
46、算法法，将将其其拆拆分分为为两两个线性表，使得：个线性表，使得：A=a1，a2，an，B=b1，b2，bn 解：解：设拆分后的两个线性表都用带头结点的单链表存放。设拆分后的两个线性表都用带头结点的单链表存放。先先建建立立两两个个头头结结点点*ha和和*hb，它它们们用用于于存存放放拆拆分分后后的的线线性性表表A和和B，ra和和rb分分别别指指向向这这两两个个单单链链表表的的表表尾尾，用用p指指针针扫扫描描单单链链表表hc，将将当当前前结结点点*p链链到到ha未未尾尾，p沿沿next域域下下移移一一个个结结点点，若若不不为为空空，则则当当前前结结点点*p链链到到hb未未尾尾，p沿沿next域域下
47、下移移一一个个结结点点，如此这样，直到如此这样，直到p为空。最后将两个尾结点的为空。最后将两个尾结点的next域置空。域置空。ha phbvoid fun(LinkList*hc,LinkList*&ha,LinkList*&hb)LinkList*p=hc-next，*ra，*rb;ha=hc;/ha的头结点利用的头结点利用hc的头结点的头结点 ra=ha;/ra始终指向始终指向ha的末尾结点的末尾结点 hb=(LinkList*)malloc(sizeof(LinkList);/创建创建hb头结点头结点 rb=hb;/rb始终指向始终指向hb的末尾结点的末尾结点 while(p!=NULL
48、)ra-next=p;ra=p;/将将*p链到链到ha单链表未尾单链表未尾 p=p-next;rb-next=p;rb=p;/将将*p链到链到hb单链表未尾单链表未尾 p=p-next;ra-next=rb-next=NULL;/两个尾结点的两个尾结点的next域置空域置空 本本算算法法实实际际上上是是采采用用尾尾插插法法建建立立两两个个新新表表。所所以以，尾尾插法和头插法建表算法是很多类似习题的基础插法和头插法建表算法是很多类似习题的基础！思考题思考题已知一个带有表头结点的单链表，结点结构为：已知一个带有表头结点的单链表，结点结构为：datalink 假设该单链表只给出了头指针假设该单链表只
49、给出了头指针list。在不改变链表的前提。在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第下，请设计一个尽可能高效的算法，查找链表中倒数第k个个位置上的结点（位置上的结点（k为正整数）。若查找成功，算法输出该结为正整数）。若查找成功，算法输出该结点的点的data域的值，并返回域的值，并返回1；否则，只返回；否则，只返回0。要求：。要求：（1）描述算法的基本设计思想；）描述算法的基本设计思想；（2）描述算法的详细实现步骤；）描述算法的详细实现步骤；（3）根据设计思想和实现步骤，采用程序设计语言描述）根据设计思想和实现步骤，采用程序设计语言描述算法（使用算法（使用C或或C+或或J
50、AVA语言实现），关键之处请给出语言实现），关键之处请给出简要注释。简要注释。0909考研题考研题关键：找正数第关键：找正数第n-k+1个结点。个结点。list.倒数第倒数第k k个结点个结点.正数第正数第k k个结点个结点.共有共有n-k+1个结点个结点（1）算法的基本设计思想：（）算法的基本设计思想：（5分）分）定义两个指针变量定义两个指针变量p和和q，初始时均指向头结点的下一个结，初始时均指向头结点的下一个结点。点。p指针沿链表移动；当指针沿链表移动；当p指针移动到第指针移动到第k个结点时，个结点时，q指针指针开始与开始与p指针同步移动；当指针同步移动；当p指针移动到链表最后一个结点时，