1、第第2 2章章 线性表线性表2022年8月3日星期三本章概述本章概述线性结构的基本特征是：在数据元素的非空有限集线性结构的基本特征是：在数据元素的非空有限集中，数据元素间存在着一一对应的逻辑关系，即中，数据元素间存在着一一对应的逻辑关系，即 (1)(1)存在唯一的一个没有直接前驱的数据元素，称存在唯一的一个没有直接前驱的数据元素，称为为“第一元素第一元素”，其余元素有且仅有一个直接前驱。，其余元素有且仅有一个直接前驱。(2)(2)存在唯一的一个没有直接后继的数据元素，称存在唯一的一个没有直接后继的数据元素，称为为“最后元素最后元素”，其余元素有且仅有一个直接后继。，其余元素有且仅有一个直接后继
2、。线性表、栈、队列和串的逻辑结构都属于线性结构。线性表、栈、队列和串的逻辑结构都属于线性结构。线性表是一种最简单的线性结构。线性表是一种最简单的线性结构。2022年8月3日星期三2.12.1 线性表的基本概念线性表的基本概念 线性表是最常见、最简单的一种具有线性特征的线性表是最常见、最简单的一种具有线性特征的数据结构。数据结构。简单地说，线性表就是具有相同特性的数据元素简单地说，线性表就是具有相同特性的数据元素的有限集合，其元素可以是数值、符号或是由许多不的有限集合，其元素可以是数值、符号或是由许多不同的数据项组成的复杂信息。同的数据项组成的复杂信息。线性表中数据元素的类型可根据需要进行具体定
3、线性表中数据元素的类型可根据需要进行具体定义，但同一个线性表中每个元素都应具有相同的数据义，但同一个线性表中每个元素都应具有相同的数据类型。类型。2.1.1 2.1.1 线性表的定义及特性线性表的定义及特性2022年8月3日星期三 在较为复杂的线性表中，一个数据元素可以由若干在较为复杂的线性表中，一个数据元素可以由若干个数据项组成。在这种情况下，常把数据元素称为记个数据项组成。在这种情况下，常把数据元素称为记录录(record)(record)，或结点，或结点(node)(node)，由大量记录构成的线性，由大量记录构成的线性表又称为文件表又称为文件(file)(file)。综上所述，线性表是
4、综上所述，线性表是n(n0)n(n0)个具有相同类型的数个具有相同类型的数据元素据元素a1,a2,ana1,a2,an的有限序列。线性表可以表示成如的有限序列。线性表可以表示成如下形式：下形式：(a1,ai-1,ai,ai+1,an)(a1,ai-1,ai,ai+1,an)2022年8月3日星期三 线性表具有如下特性：线性表具有如下特性：(1)(1)不同线性表中数据元素的类型可以是各种各样的，不同线性表中数据元素的类型可以是各种各样的，但同一线性表中的元素必须是同一类型的。但同一线性表中的元素必须是同一类型的。(2)(2)在表中在表中ai-1ai-1领先于领先于aiai，aiai领先于领先于a
5、i+1ai+1，称，称ai-1ai-1是是aiai的直接前驱，的直接前驱，ai+1ai+1是是aiai的直接后继。的直接后继。(3)(3)线性表中，除第一个和最后一个元素外，其他元线性表中，除第一个和最后一个元素外，其他元素有且仅有一个直接前驱，有且仅有一个直接后继，这素有且仅有一个直接前驱，有且仅有一个直接后继，这是所有线性结构的共同特征。线性表是一种线性结构。是所有线性结构的共同特征。线性表是一种线性结构。(4)(4)线性表中元素的个数线性表中元素的个数n n 称为线性表的长度，称为线性表的长度，n=0n=0时时称为空表。称为空表。(5)(5)元素元素aiai是线性表的第是线性表的第i i
6、个元素，称个元素，称i i为数据元素为数据元素aiai的位序，每一个元素在线性表中的位置，仅取决于它的的位序，每一个元素在线性表中的位置，仅取决于它的位序。位序。2022年8月3日星期三 线性表的抽象数据类型可以由数据对象、数据关线性表的抽象数据类型可以由数据对象、数据关系及基本操作系及基本操作3 3个要素来定义。定义如下：个要素来定义。定义如下：ADT ListADT List数据对象：数据对象：D=ai|aiElemSetD=ai|aiElemSet，i=1,2,n,n1i=1,2,n,n1数据关系：数据关系：R1=|ai-1,aiDR1=|ai-1,aiD，i i2,n2,n基本操作：基
7、本操作：InitList(&LInitList(&L)初始条件：线性表初始条件：线性表L L不存在。不存在。操作结果：构造一个空的线性表操作结果：构造一个空的线性表L L。2.1.2 2.1.2 线性表的抽象数据类型线性表的抽象数据类型2022年8月3日星期三ListEmpty(LListEmpty(L)初始条件：线性表初始条件：线性表L L已存在。已存在。操作结果：若操作结果：若L L为空表，则返回为空表，则返回TRUETRUE，否则返回，否则返回FALSEFALSE。ListLength(LListLength(L)初始条件：线性表初始条件：线性表L L已存在。已存在。操作结果：返回操作结
8、果：返回L L中数据元素的个数。中数据元素的个数。ListInsertListInsert(L,i,eL,i,e)初始条件：线性表初始条件：线性表L L已存在，已存在，1iListLength(L)1iListLength(L)。操作结果：在操作结果：在L L中第中第i i个位置之前插入新的数据元个位置之前插入新的数据元素素e e，L L的长度加的长度加1 1。2022年8月3日星期三ListDeleteListDelete(L,iL,i,e)e)初始条件：线性表初始条件：线性表L L已存在且非空，已存在且非空，1iListLength(L)1iListLength(L)。操作结果：删除操作结
9、果：删除L L的第的第i i个数据元素，并用个数据元素，并用e e返回其返回其值，值，L L的长度减的长度减1 1。GetElem(L,iGetElem(L,i,e)e)初始条件：线性表初始条件：线性表L L已存在，已存在，1iListLength(L)1iListLength(L)。操作结果：用操作结果：用e e返回返回L L中第中第i i个数据元素的值。个数据元素的值。ADT ListADT List 以上仅列出了线性表的一组最基本的操作。对于实以上仅列出了线性表的一组最基本的操作。对于实际应用中所涉及到的其他更复杂的操作，可以用基本操际应用中所涉及到的其他更复杂的操作，可以用基本操作的组
10、合来实现。作的组合来实现。2022年8月3日星期三 【例【例2-12-1】已知线性表】已知线性表L L中的元素按元素值非递减有中的元素按元素值非递减有序排列，编写一个函数删除线性表中多余的值相同的序排列，编写一个函数删除线性表中多余的值相同的元素。例如，设元素。例如，设L=(1,3,3,5,9,13,13,13,17,21)L=(1,3,3,5,9,13,13,13,17,21)执行过函数后，则执行过函数后，则L=(1,3,5,9,13,17,21)L=(1,3,5,9,13,17,21)2022年8月3日星期三 本题的算法思想是：本题的算法思想是：由于线性表中的元素按非递减有序排列，值由于线
11、性表中的元素按非递减有序排列，值相同的元素必为相邻的元素，所以依次比较相邻相同的元素必为相邻的元素，所以依次比较相邻的两个元素，若值相等，则删除其中的一个的两个元素，若值相等，则删除其中的一个;否则继续向后查找，直到表中所有元素都查否则继续向后查找，直到表中所有元素都查找结束。找结束。上述删除过程如算法上述删除过程如算法2.12.1所示。所示。2022年8月3日星期三void DeleteSame(Listvoid DeleteSame(List&L)&L)i=1;i=1;Len=ListLength(LLen=ListLength(L););while(iwhile(iLen)elemi-1
12、L-elemi-1。上述定义的顺序表，其存储空间由编译程序分配，称上述定义的顺序表，其存储空间由编译程序分配，称静态分配，需要在使用前分配好存储空间。假设表中已存静态分配，需要在使用前分配好存储空间。假设表中已存放了放了n n个元素，即个元素，即a1,a2,ana1,a2,an，则顺序表中数据元素在内，则顺序表中数据元素在内存中的表示如图所示。存中的表示如图所示。其中，其中，b b表示数组表示数组elemelem的基地址，的基地址，l l是该数组元素应是该数组元素应占的存储单元数。占的存储单元数。2022年8月3日星期三 1.1.初始化操作初始化操作 顺序存储结构的线性表在使用前必须进行初始化
13、顺序存储结构的线性表在使用前必须进行初始化操作，即需要为其分配好内存空间。操作，即需要为其分配好内存空间。具体过程如算法具体过程如算法2.22.2所示。所示。2.2.22.2.2 顺序表的基本操作顺序表的基本操作2022年8月3日星期三Status InitList_Sq(SqListStatus InitList_Sq(SqList&L)&L)构造一个空的线性表构造一个空的线性表L.elem=(ElemTypeL.elem=(ElemType*)malloc(LIST_SIZE)malloc(LIST_SIZE*sizeofsizeof(ElemType(ElemType););if(!L.
14、elem)exit(OVERFLOWif(!L.elem)exit(OVERFLOW););L.lengthL.length=0;=0;return OK;return OK;InitList_Sq InitList_Sq算法算法2.22.22022年8月3日星期三 在初始化操作中分配空间使用了在初始化操作中分配空间使用了mallocmalloc函数，格函数，格式为式为malloc(sizemalloc(size)，其功能是在系统内存中分配，其功能是在系统内存中分配sizesize个存储单元，并返回该空间的基地址。与其对应，释个存储单元，并返回该空间的基地址。与其对应，释放空间的是放空间的是f
15、reefree函数，格式为函数，格式为free(pfree(p)，其功能是将指，其功能是将指针变量针变量p p所指示的存储空间回收到系统内存空间中去。所指示的存储空间回收到系统内存空间中去。2022年8月3日星期三 2.2.插入操作插入操作 顺序表的插入操作是指在表的第顺序表的插入操作是指在表的第i(1in+1)i(1in+1)个位置个位置上插入一个新元素上插入一个新元素e e，使长度为，使长度为n n的线性表的线性表(a1,ai-1,ai,an)(a1,ai-1,ai,an)变为长度为变为长度为n+1n+1的顺序表的顺序表(a1,ai-1,e,ai,an)(a1,ai-1,e,ai,an)插
16、入过程如图所示插入过程如图所示2022年8月3日星期三 算法思想如下：算法思想如下：在插入前先判断插入位置是否合法及是否有剩余空在插入前先判断插入位置是否合法及是否有剩余空间。如果条件满足则定位要插入的位置，然后把第间。如果条件满足则定位要插入的位置，然后把第i i个个元素及其后的元素都向后移动一个位置，在原来的第元素及其后的元素都向后移动一个位置，在原来的第i i个位置上插入新元素，最后对表长进行处理。个位置上插入新元素，最后对表长进行处理。具体过程如算法具体过程如算法2.32.3所示。所示。2022年8月3日星期三Status ListInsert_Sq(SqList&L,int i,El
17、emTypeStatus ListInsert_Sq(SqList&L,int i,ElemType e)e)在顺序表在顺序表L L的第的第i i个元素之前插入新的元素个元素之前插入新的元素e e i i的合法值为的合法值为1iListLength_Sq(L)+11iListLength_Sq(L)+1if(iif(i L.length+1)return ERROR;L.length+1)return ERROR;i i值不合法值不合法if(L.length=L.listsize)returnif(L.length=L.listsize)return OVERFLOW;OVERFLOW;存储空
18、间已满，则退出存储空间已满，则退出q=&(L.elemq=&(L.elemi-1i-1););q q为插入位置为插入位置for(p=&(L.elemfor(p=&(L.elemL.length-1L.length-1);p=q;-);p=q;-p p)*(p+1)=(p+1)=*p;p;插入位置及之后的元素插入位置及之后的元素右移右移*q=e;q=e;插入插入e e+L.length+L.length;表长增表长增1 1return OK;return OK;ListInsert_Sq ListInsert_Sq 算法算法2.32.32022年8月3日星期三 算法算法2.32.3需要注意以下几
19、点：需要注意以下几点：(1)(1)由于函数要回传对顺序表插入后的结果，所以由于函数要回传对顺序表插入后的结果，所以参数参数L L要定义为引用参数，即要定义为引用参数，即SqListSqList&L&L。如果把。如果把L L定义定义为为SqListSqList类型是错误的，将无法对类型是错误的，将无法对L L进行改变。进行改变。(2)(2)为了避免元素间的覆盖，算法中元素的后移必为了避免元素间的覆盖，算法中元素的后移必须从表中最后一个元素开始，直到第须从表中最后一个元素开始，直到第i i个元素为止。个元素为止。(3)(3)线性表中元素的序号比数组元素下标大线性表中元素的序号比数组元素下标大1 1
20、。2022年8月3日星期三 3.3.删除操作删除操作 线性表的删除操作是使长度为线性表的删除操作是使长度为n n的线性表的线性表(a1,ai-1,ai,ai+1,an)(a1,ai-1,ai,ai+1,an)变为长度为变为长度为n-1n-1的线性表的线性表(a1,ai-1,ai+1,an)(a1,ai-1,ai+1,an)删除过程如图所示。删除过程如图所示。2022年8月3日星期三 算法思想如下：算法思想如下：在删除前先判断删除位置是否合法。若合法则定在删除前先判断删除位置是否合法。若合法则定位要删除的位置，并把要删除的元素值赋给位要删除的位置，并把要删除的元素值赋给e e，然后把，然后把第第
21、i+1i+1个元素及其后的元素都向前移动一个位置，最后个元素及其后的元素都向前移动一个位置，最后对表长进行处理。对表长进行处理。具体过程如算法具体过程如算法2.42.4所示。所示。2022年8月3日星期三Status ListDelete_Sq(SqList&L,int i,ElemTypeStatus ListDelete_Sq(SqList&L,int i,ElemType&e)&e)在顺序表在顺序表L L中删除第中删除第i i个元素，并用个元素，并用e e返回其值返回其值ii的合法值为的合法值为1iListLength_Sq(L)1iListLength_Sq(L)if(iL.lengt
22、h)returnif(iL.length)return ERROR;ERROR;ii值不合法值不合法p=&(L.elemp=&(L.elemi-1i-1););p p为被删除元素的为被删除元素的位置位置e=e=*p;p;被删除元素的值赋给被删除元素的值赋给e eq=L.elem+L.length-1;q=L.elem+L.length-1;表尾元素的位表尾元素的位置置for(+p;p=q;+pfor(+p;p=q;+p)*(p-1)=(p-1)=*p;p;被删除元素之后的被删除元素之后的元素左移元素左移-L.length-L.length;表表长减长减1 1return OK;return O
23、K;ListDelete_Sq ListDelete_Sq 算法算法2.42.4注意注意：删除算法中元素的前移是从第：删除算法中元素的前移是从第i+1i+1个元素开始，到第个元素开始，到第n n个元素为止。个元素为止。2022年8月3日星期三 在顺序表中插入元素，时间主要耗费在移动元素上，在顺序表中插入元素，时间主要耗费在移动元素上，而移动的次数取决于插入的位置以及表的长度。插入位而移动的次数取决于插入的位置以及表的长度。插入位置与移动元素个数的关系如图所示。置与移动元素个数的关系如图所示。2.2.3 2.2.3 顺序表基本操作的算法分析顺序表基本操作的算法分析2022年8月3日星期三 在顺序
24、表中插入或删除一个数据元素平均需要移动在顺序表中插入或删除一个数据元素平均需要移动表中一半的元素。若表长为表中一半的元素。若表长为n n，则插入操作和删除操作，则插入操作和删除操作算法的平均时间复杂度为算法的平均时间复杂度为O(nO(n)。讨论【例讨论【例2-12-1】的操作在顺序表中的实现方法和时】的操作在顺序表中的实现方法和时间复杂度的分析：间复杂度的分析：容易看出，顺序表的容易看出，顺序表的“求表长求表长”和和“取第取第i i个元素个元素”的时间复杂度均为的时间复杂度均为O(1)O(1)，则其主要时间都消耗在元素删，则其主要时间都消耗在元素删除上，算法除上，算法2.52.5是【例是【例2
25、-12-1】在顺序表中的实现算法。】在顺序表中的实现算法。2022年8月3日星期三void DeleteSame(Listvoid DeleteSame(List&L)&L)p=L.elemp=L.elem;while(pwhile(pL.elem+L.length-1)L.elem+L.length-1)if(if(*p!=p!=*(p+1)p+;(p+1)p+;else else for(+p;p for(+p;pL.elem+L.length-1;+p)next=NULL;L-next=NULL;for(i=n;ifor(i=n;i0;-i)0;-i)p=(LinkList)malloc
26、(sizeof(LNode p=(LinkList)malloc(sizeof(LNode););生成新结点生成新结点 scanf(&pscanf(&p-data);-data);输入元素值输入元素值 p-next=L-next;L-next=p;p-next=L-next;L-next=p;插入到头结点之后插入到头结点之后 CreateList_L CreateList_L 算法算法2.62.62022年8月3日星期三 顺序建立单链表是每次把新结点插入到链表尾部，顺序建立单链表是每次把新结点插入到链表尾部，因为单链表没有专门指示最后一个结点的指针，所以因为单链表没有专门指示最后一个结点的指针
27、，所以需另设一个指针指向最后一个结点。需另设一个指针指向最后一个结点。顺序建立单链表的算法所示算法顺序建立单链表的算法所示算法2.72.7。2022年8月3日星期三void CreateList_L(LinkList&L,intvoid CreateList_L(LinkList&L,int n)n)顺序建立单链表，尾插法顺序建立单链表，尾插法L=(LinkList)malloc(sizeof(LNodeL=(LinkList)malloc(sizeof(LNode););生成头结点生成头结点for(i=n;ifor(i=n;i0;-i)0;-i)p=(LinkList)malloc(size
28、of(LNode p=(LinkList)malloc(sizeof(LNode););scanf(&p scanf(&p-data);-data);输入元素值输入元素值 last-next=p;lastlast-next=p;last=p;=p;使用使用lastlast指针指向最后一个结点指针指向最后一个结点 last-next=NULL;last-next=NULL;CreateList_L CreateList_L 算法算法2.72.72022年8月3日星期三 2 2）单链表的查找操作）单链表的查找操作 查找操作就是找出单链表中的第查找操作就是找出单链表中的第i(1in)i(1in)个结
29、点，个结点，并返回该结点数据域的值。并返回该结点数据域的值。操作步骤：操作步骤：(1)(1)用指针用指针p p扫描单链表，用扫描单链表，用j j作为计数器。初始化作为计数器。初始化p p指向指向第一个结点，第一个结点，j j为为1 1。(2)(2)当当p p扫描一个结点时，扫描一个结点时，j j就相应地加就相应地加1 1，则，则j j的值就是的值就是p p已扫描过的结点数。已扫描过的结点数。(3)(3)当当j j的值刚好为的值刚好为i i时，时，p p的值就是第的值就是第i i个结点的指针。个结点的指针。2022年8月3日星期三 具体过程如算法具体过程如算法2.82.8所示。所示。Status
30、 GetElem_L(LinkList&L,int i,ElemTypeStatus GetElem_L(LinkList&L,int i,ElemType&e)&e)L L为带头结点的单链表的头指针为带头结点的单链表的头指针 当第当第i i个元素存在时，其值赋给个元素存在时，其值赋给e e并返回并返回OKOK，否则返回，否则返回ERRORERRORp=L-next;p=L-next;j=1;j=1;初始化初始化p p指向头结指向头结点，计数器点，计数器j j置置1 1while(pwhile(p&ji)&jnext;+jp=p-next;+j;if(!pji)returnif(!pji)re
31、turn ERROR;ERROR;当当i0inin时，表时，表中无第中无第i i个结点个结点e=p-data;e=p-data;取第取第i i个元素个元素return OK;return OK;GetElem_L GetElem_L 算法算法2.82.82022年8月3日星期三 查找算法的基本操作是指针后移，其执行的频度与查找算法的基本操作是指针后移，其执行的频度与被查找元素在表中的位置有关，若被查找元素在表中的位置有关，若1in1in，则频度为，则频度为i-1i-1，否则为，否则为n n，因此上面算法的时间复杂度为，因此上面算法的时间复杂度为O(nO(n)。单链表的长度是表中除头结点外的结点
32、数目。求单单链表的长度是表中除头结点外的结点数目。求单链表的长度运算，可用类似于上一算法的算法来实现，链表的长度运算，可用类似于上一算法的算法来实现，即用即用p p扫描单链表的结点，扫描单链表的结点，j j计数计数p p已扫描过的结点数，已扫描过的结点数，当当p p指向最后一个结点时，指向最后一个结点时，j j就计数到了表的长度。就计数到了表的长度。2022年8月3日星期三 3 3）单链表的插入操作）单链表的插入操作 插入操作是将新数据元素插入操作是将新数据元素e e插入到表中第插入到表中第i i个元素之个元素之前，显然前，显然i i的合法值是的合法值是1in+11in+1，n n为插入前表的
33、长度。为插入前表的长度。插入过程如下图所示。插入过程如下图所示。2022年8月3日星期三 假设假设s s为指向结点为指向结点e e的指针，则上述指针修改用语句的指针，则上述指针修改用语句描述为：描述为：s-next=p-next;p-next=s;s-next=p-next;p-next=s;操作步骤：操作步骤：(1)(1)寻找第寻找第i-1i-1个结点。个结点。(2)(2)判断判断i i的取值是否合法，合法的取值应为：的取值是否合法，合法的取值应为：i1i1，n+1n+1。(3)(3)给待插入元素分配存储空间。给待插入元素分配存储空间。(4)(4)插入新结点。插入新结点。2022年8月3日星
34、期三 具体过程如算法具体过程如算法2.92.9所示。所示。Status ListInsert_L(LinkList&L,int i,ElemTypeStatus ListInsert_L(LinkList&L,int i,ElemType e)e)在带头结点的单链表在带头结点的单链表L L的第的第i i个元素之前插入元素个元素之前插入元素e ep=L;jp=L;j=0;=0;初始化初始化while(pwhile(p&j i-1)&j next;p=p-next;+j;+j;if(!pjif(!pj i-1)return ERROR;i-1)return ERROR;未找到，未找到，i1in+1
35、in+1s=(LinkList)malloc(sizeof(LNodes=(LinkList)malloc(sizeof(LNode););生成新结点生成新结点s-data=e;s-data=e;s-next=p-next;p-next=s;s-next=p-next;p-next=s;插入新结点插入新结点return OK;return OK;LinstInsert_LLinstInsert_L 算法算法2.92.92022年8月3日星期三 算法算法2.92.9的时间主要消耗在查找第的时间主要消耗在查找第i-1i-1个结点上，个结点上，所以，算法的平均时间复杂度为所以，算法的平均时间复杂度为
36、O(nO(n)。若不考虑寻找。若不考虑寻找结点的因素，仅就插入而言，其时间复杂度为结点的因素，仅就插入而言，其时间复杂度为O(1)O(1)。4 4）单链表的删除操作）单链表的删除操作 删除操作是指删除单链表中第删除操作是指删除单链表中第i i个结点，个结点，i i的合法的合法值是值是1in1in。注意：注意：头结点是不能删除的。头结点是不能删除的。2022年8月3日星期三 具体方法是：具体方法是：先找到第先找到第i-1i-1个结点，若找到并且该结点的直接后继个结点，若找到并且该结点的直接后继(即第即第i i个结点个结点)存在，则把第存在，则把第i i个结点删除。个结点删除。注意：注意：删除删除
37、一个结点只需要修改它的直接前驱的指针域，但因被删一个结点只需要修改它的直接前驱的指针域，但因被删除结点已经无用途，所以要向系统申请释放被删除结点除结点已经无用途，所以要向系统申请释放被删除结点的空间。的空间。删除过程如下图所示删除过程如下图所示2022年8月3日星期三 假设假设p p为指向结点为指向结点ai-1ai-1的指针，则修改指针的语句为：的指针，则修改指针的语句为：p-next=p-next-next;p-next=p-next-next;操作步骤：操作步骤：(1)(1)寻找第寻找第i-1i-1个结点。个结点。(2)(2)判断判断i i的取值是否合法，合法的取值应为：的取值是否合法，合
38、法的取值应为：i1i1，nn。(3)(3)修改第修改第i-1i-1个元素的指针来删除第个元素的指针来删除第i i个元素。个元素。(4)(4)释放第释放第i i个元素所占的存储空间。个元素所占的存储空间。2022年8月3日星期三 具体过程如算法具体过程如算法2.102.10所示。所示。Status ListDelete_L(LinkList&L,int i,ElemTypeStatus ListDelete_L(LinkList&L,int i,ElemType&e)&e)在带头结点的单链表在带头结点的单链表L L中，删除第中，删除第i i个元素，并由个元素，并由e e返返回其值回其值p=L;j
39、p=L;j=0;=0;while(pwhile(p-next&j next&j next;p=p-next;+j;+j;if(!(p-next)jif(!(p-next)j i-1)return ERROR;i-1)return ERROR;删除位置不合理删除位置不合理q=p-next;q=p-next;p-next=q-next;p-next=q-next;删除结点删除结点e=q-data;e=q-data;free(qfree(q););释放结点空间释放结点空间return OK;return OK;ListDelete_LListDelete_L 算法算法2.102.102022年8月3
40、日星期三 整个删除算法的时间也消耗在查找第整个删除算法的时间也消耗在查找第i-1i-1个结点上，个结点上，其时间复杂度为其时间复杂度为O(nO(n)。若不考虑查找所消耗的时间，。若不考虑查找所消耗的时间，仅就其删除过程而言一步就可实现，其时间复杂度为仅就其删除过程而言一步就可实现，其时间复杂度为O(1)O(1)。【例【例2-22-2】编写一个算法，统计单链表中值为】编写一个算法，统计单链表中值为x x的元的元素的个数，统计结果由函数值返回。素的个数，统计结果由函数值返回。2022年8月3日星期三 算法思想：从表头依次访问链表中的每个结点，算法思想：从表头依次访问链表中的每个结点，判断当前结点的
41、数据域是否为判断当前结点的数据域是否为x x，若是则结点个数加，若是则结点个数加1 1，结点个数存储在变量，结点个数存储在变量countcount中。中。具体过程如算法具体过程如算法2.112.11所示。所示。int Count_x(LinkList L,ElemTypeint Count_x(LinkList L,ElemType x)x)p=L-next;p=L-next;指针指针p p指向单链表的第一个结点指向单链表的第一个结点count=0;count=0;计数器计数器countcount清零清零while(pwhile(p!=NULL)!=NULL)if(p-data=x)count
42、if(p-data=x)count+;+;若当前数据域为若当前数据域为x x，则计数器加，则计数器加1 1p=p-next;p=p-next;指针指针p p指向下一个结点指向下一个结点 return count;return count;Count_x Count_x 算法算法2.112.112022年8月3日星期三 【例【例2-32-3】在非空链表】在非空链表L L中，中，p p结点不是第一个结点，结点不是第一个结点，试编写删除试编写删除p p的直接前驱结点的算法。的直接前驱结点的算法。可采取以下方法：查找可采取以下方法：查找p p结点的直接前驱结点的直接前驱q q结点，交结点，交换换p p
43、结点和结点和q q结点的数据域，然后删除结点的数据域，然后删除p p结点。此时不需结点。此时不需要重新定位，并且数据元素间的相对逻辑关系不变。要重新定位，并且数据元素间的相对逻辑关系不变。具体过程如算法具体过程如算法2.122.12所示。所示。2022年8月3日星期三void Delete_Prior(LinkList&L,LinkListvoid Delete_Prior(LinkList&L,LinkList p)p)q=L-next;q=L-next;while(qwhile(q-next!=p)q=q-next;-next!=p)q=q-next;移动指针移动指针q q直到直到q q的
44、后继是的后继是p pp-dataq-data;p-dataq-data;交换交换p p和和q q的数据域的数据域q-next=p-next;q-next=p-next;删除并释放结点删除并释放结点p pfree(pfree(p););算法算法2.122.122022年8月3日星期三 【例【例2-42-4】设有两个非递减的单链表】设有两个非递减的单链表LaLa和和LbLb，现归并，现归并LaLa和和LbLb得到得到LcLc，要求不能重新申请新的结点。，要求不能重新申请新的结点。算法思想：利用单链表算法思想：利用单链表LaLa和和LbLb非递减的特点，依次进非递减的特点，依次进行比较，将当前值较小
45、的结点摘下，插入到链表行比较，将当前值较小的结点摘下，插入到链表LcLc的表的表头。头。具体过程如算法具体过程如算法2.132.13所示。所示。2022年8月3日星期三void MergeList_L(LinkList&La,LinkList&Lb,LinkList void MergeList_L(LinkList&La,LinkList&Lb,LinkList&Lc&Lc)归并非递减单链表归并非递减单链表LaLa和和LbLb得得LcLcpa=La-next;pbpa=La-next;pb=Lb-next;=Lb-next;LcLc=pc=La;=pc=La;用用LaLa的头结点作为的头结点
46、作为LcLc的头结点的头结点while(pa&pbwhile(pa&pb)if(pa-datadatadata)-data)插入值较小的结点插入值较小的结点pc-next=pa;pc=pa;pa=papc-next=pa;pc=pa;pa=pa-next;-next;else pc-next=pb;pc=pb;pb=pbelse pc-next=pb;pc=pb;pb=pb-next;-next;pc-next=pa?pa:pbpc-next=pa?pa:pb;插入剩余段插入剩余段free(Lbfree(Lb););释放释放LbLb的头结点的头结点 MergeList_L MergeList_
47、L算法算法2.132.132022年8月3日星期三 单链表中最后一个结点的指针域的值为空，将这个单链表中最后一个结点的指针域的值为空，将这个空的指针域的指针指向头结点，则整个链表就形成了一空的指针域的指针指向头结点，则整个链表就形成了一个环形结构，故称为循环链表。个环形结构，故称为循环链表。如图所示为单链的循环链表，即单循环链表。类似如图所示为单链的循环链表，即单循环链表。类似地还有多重链的循环链表。地还有多重链的循环链表。2.3.22.3.2 循环链表及其基本操作循环链表及其基本操作2022年8月3日星期三 循环链表和单链表的差别仅在于，判别链表中最后循环链表和单链表的差别仅在于，判别链表中
48、最后一个结点的条件不再是一个结点的条件不再是“后继是否为空后继是否为空”，而是，而是“后后继是否为头结点继是否为头结点”。【例【例2-52-5】将单循环链表倒置。】将单循环链表倒置。所谓倒置，就是把单循环链表所谓倒置，就是把单循环链表(a1,a2,an)(a1,a2,an)变为变为(an,a2,a1)(an,a2,a1)。具体过程如算法具体过程如算法2.142.14所示。所示。2022年8月3日星期三void InvertList(LinkListvoid InvertList(LinkList&L)&L)q=L;q=L;初始化指针初始化指针q q、p p、r rp=L-next;p=L-ne
49、xt;r=p-next;r=p-next;dodop-next=q;p-next=q;使使p p的指针域指向其前驱的指针域指向其前驱q=p;q=p;qq、p p、r r在原逻辑关系上后移一位在原逻辑关系上后移一位p=r;p=r;r=r-next;r=r-next;while(qwhile(q!=L);!=L);当当q=Lq=L时全部指针域均改完，结束时全部指针域均改完，结束 算法算法2.142.142022年8月3日星期三 【例【例2-62-6】有两个尾指针表示的单循环链表】有两个尾指针表示的单循环链表LaLa和和LbLb，编写一个算法将编写一个算法将LbLb链接到链接到LaLa，链接后的链表
50、仍保持单，链接后的链表仍保持单循环链表的形式。循环链表的形式。算法思想：算法思想：将两个单循环链表合并成一个单循环链表时，仅将两个单循环链表合并成一个单循环链表时，仅需将一个表的表尾和另一个表的表头相接。当单循环需将一个表的表尾和另一个表的表头相接。当单循环链表以尾指针表示的循环链表作为存储结构时，这个链表以尾指针表示的循环链表作为存储结构时，这个操作仅需改变两个指针值即可，如图所示。操作仅需改变两个指针值即可，如图所示。2022年8月3日星期三2022年8月3日星期三具体过程如算法具体过程如算法2.152.15所示。所示。LinkList MergeCircle_L(LinkList&La,
