2線性表信息學院暑期培訓2線性表線性結構是最常用、最簡單的一種數據結構。而線性表是一種典型的線性結構。其基本特點是線性表中的數據元素是有序且是有限的。在這種結構中：①存在一個唯一的被稱為“第一個”的數據元素；②存在一個唯一的被稱為“最后一個”的數據元素；③除第一個元素外，每個元素均有唯一一個直接前驅；④除最后一個元素外，每個元素均有唯一一個直接后繼。2.1線性表的邏輯結構線性表(LinearList)：是由n(n≧0)個數據元素(結點)a1，a2，…an組成的有限序列。該序列中的所有結點具有相同的數據類型。其中數據元素的個數n稱為線性表的長度。當n=0時，稱為空表。當n>0時，將非空的線性表記作：(a1，a2，…an)a1稱為線性表的第一個(首)結點，an稱為線性表的最后一個(尾)結點。2.1.1

線性表的定義a1，a2，…ai-1都是ai(2≦i≦n)的前驅，其中ai-1是ai的直接前驅;ai+1，ai+2，…an都是ai(1≦i≦n-1)的后繼，其中ai+1是ai的直接后繼。2.1.2線性表的邏輯結構

線性表中的數據元素ai所代表的具體含義隨具體應用的不同而不同，在線性表的定義中，只不過是一個抽象的表示符號。◆線性表中的結點可以是單值元素(每個元素只有一個數據項)。例1:26個英文字母組成的字母表：(A，B，C、…、Z）例2：某校從1978年到1983年各種型號的計算機擁有量的變化情況：(6，17，28，50，92，188）例3：一副撲克的點數(2，3，4，…，J，Q，K，A)2.1.2線性表的邏輯結構◆

線性表中的結點可以是記錄型元素，每個元素含有多個數據項，每個項稱為結點的一個域。每個元素有一個可以唯一標識每個結點的數據項組，稱為關鍵字。例4：某校2001級同學的基本情況：{(‘2001414101’，‘張里戶’，‘男’，06/24/1983)，(‘2001414102’，‘張化司’，‘男’，08/12/1984)…，(‘2001414102’，‘李利辣’，‘女’，08/12/1984)}◆若線性表中的結點是按值(或按關鍵字值)由小到大(或由大到小)排列的，稱線性表是有序的。2.1.3線性表的抽象數據類型定義

◆

線性表是一種相當靈活的數據結構，其長度可根據需要增長或縮短。

◆

對線性表的數據元素可以訪問、插入和刪除。2.1.3線性表的抽象數據類型定義ADTList{

數據對象： 數據關系： 基本操作：

InitList(&L)/*初始化線性表*/ DestroyList(&L)/*銷毀線性表*/ ListEmpty(L)/*判斷是否為空線性表*/ ...... }2.1.3線性表的抽象數據類型定義2.2線性表的順序存儲

順序存儲：把線性表的結點按邏輯順序依次存放在一組地址連續的存儲單元里。用這種方法存儲的線性表簡稱順序表。順序存儲的線性表的特點：

◆線性表的邏輯順序與物理順序一致;

◆數據元素之間的關系是以元素在計算機內“物理位置相鄰”來體現。設有非空的線性表：(a1，a2，…an)。順序存儲如圖2-1所示。2.2.1

線性表的順序存儲結構

在具體的機器環境下：設線性表的每個元素需占用L個存儲單元，以所占的第一個單元的存儲地址作為數據元素的存儲位置。則線性表中第i+1個數據元素的存儲位置LOC(ai+1)和第i個數據元素的存儲位置LOC(ai)之間滿足下列關系：

LOC(ai+1)=LOC(ai)+L

線性表的第i個數據元素ai的存儲位置為：

LOC(ai)=LOC(a1)+(i-1)*L

…a1a2…ai…an…Loc(a1)Loc(ai)+(i-1)*L圖2-1

線性表的順序存儲表示2.2線性表的順序存儲

在高級語言(如C語言)環境下：數組具有隨機存取的特性，因此，借助數組來描述順序表。除了用數組來存儲線性表的元素之外，順序表還應該有表示線性表的長度屬性，所以用結構類型來定義順序表類型。#defineOK1/*預定義正確標識*/#defineERROR-1/*預定義錯誤標識*/#defineMAX_SIZE100/*預定義數組長度*/typedefintStatus;/*聲明元素類型*/typedefintElemType;/*聲明數據元素的類型*/typedefstructsqlist{ElemTypeelem_array[MAX_SIZE];intlength;/*數組的當前長度*/}SqList;2.2.2順序表的基本操作

順序存儲結構中，很容易實現線性表的一些操作：初始化、賦值、查找、修改、插入、刪除、求長度等。以下將對幾種主要的操作進行討論。1順序線性表初始化

StatusInit_SqList(SqList*L){L->elem_array=(ElemType*)malloc(MAX_SIZE*sizeof(ElemType));if(!L->elem_array)returnERROR;else{L->length=0;returnOK;}}補充C語言中malloc是動態內存分配函數。

函數原型：void*malloc(unsignedintnum_bytes);

參數：num_bytes是無符號整型，用于表示分配的字節數。

返回值：如果分配成功則返回指向被分配內存的指針(此存儲區中的初始值不確定)，否則返回空指針NULL。void*表示未確定類型的指針，void*可以指向任何類型的數據，更明確的說是指申請內存空間時還不知道用戶是用這段空間來存儲什么類型的數據（比如是char還是int或者...）

功能：分配長度為num_bytes字節的內存塊

注意：當內存不再使用時，應使用free()函數將內存塊釋放。函數返回的指針一定要適當對齊，使其可以用于任何數據對象。關于該函數的原型，在以前malloc返回的是char型指針，新的ANSIC標準規定，該函數返回為void型指針，因此必要時要進行類型轉換。2.2.2順序表的基本操作2

順序線性表的插入

在線性表L=(a1，…ai-1，ai，ai+1，…，an)中的第i(1≦i≦n)個位置上插入一個新結點e，使其成為線性表：

L=(a1，…ai-1，e，ai，ai+1，…，an)

實現步驟(1)

將線性表L中的第i個至第n個結點后移一個位置。(2)將結點e插入到結點ai-1之后。(3)線性表長度加1。2.2.2順序表的基本操作算法描述StatusInsert_SqList(Sqlist*L，inti，ElemTypee)

{intj;if(i<0||i>L->length-1)returnERROR;if(L->length>=MAX_SIZE){printf(“線性表溢出!\n”);returnERROR;}for(j=L->length–1;j>=i-1;--j)L->Elem_array[j+1]=L->Elem_array[j];/*i-1位置以后的所有結點后移*/L->Elem_array[i-1]=e;/*在i-1位置插入結點*/L->length++;returnOK;}2.2.2順序表的基本操作

時間復雜度分析

在線性表L中的第i個元素之前插入新結點，其時間主要耗費在表中結點的移動操作上，因此，可用結點的移動來估計算法的時間復雜度。設在線性表L中的第i個元素之前插入結點的概率為Pi，不失一般性，設各個位置插入是等概率，則Pi=1/(n+1)，而插入時移動結點的次數為n-i+1。總的平均移動次數：Einsert=∑pi*(n-i+1)(1≦i≦n)∴Einsert=n/2。即在順序表上做插入運算，平均要移動表上一半結點。當表長n較大時，算法的效率相當低。因此算法的平均時間復雜度為O(n)。2.2.2順序表的基本操作3順序線性表的刪除在線性表L=(a1，…ai-1，ai，ai+1，…，an)中刪除結點ai(1≦i≦n)，使其成為線性表：

L=(a1，…ai-1，ai+1，…，an)

實現步驟(1)將線性表L中的第i+1個至第n個結點依此向前移動一個位置。(2)線性表長度減1。2.2.2順序表的基本操作算法描述ElemTypeDelete_SqList(Sqlist*L，inti){intk;ElemTypex;if(L->length==0){printf(“線性表L為空!\n”);returnERROR;}elseif(i<1||i>L->length){printf(“要刪除的數據元素不存在!\n”);returnERROR;}else{x=L->Elem_array[i-1];/*保存結點的值*/for(k=i;k<L->length;k++)L->Elem_array[k-1]=L->Elem_array[k];/*i位置以后的所有結點前移*/L->length--;return(x);}}2.2.2順序表的基本操作

時間復雜度分析刪除線性表L中的第i個元素，其時間主要耗費在表中結點的移動操作上，因此，可用結點的移動來估計算法的時間復雜度。設在線性表L中刪除第i個元素的概率為Pi，不失一般性，設刪除各個位置是等概率，則Pi=1/n，而刪除時移動結點的次數為n-i。則總的平均移動次數：Edelete=∑pi*(n-i)(1≦i≦n)∴Edelete=(n-1)/2。即在順序表上做刪除運算，平均要移動表上一半結點。當表長n較大時，算法的效率相當低。因此算法的平均時間復雜度為O(n)。2.2.2順序表的基本操作4順序線性表的查找定位刪除在線性表L=(a1，a2，…，an)中刪除值為x的第一個結點。實現步驟(1)

在線性表L查找值為x的第一個數據元素。(2)將從找到的位置至最后一個結點依次向前移動一個位置。

(3)線性表長度減1。2.2.2順序表的基本操作算法描述StatusLocate_Delete_SqList(Sqlist*L，ElemTypex)/*刪除線性表L中值為x的第一個結點*/{inti=0,k;while(i<L->length)/*查找值為x的第一個結點*/{if(L->Elem_array[i]!=x)i++;else{for(k=i+1;k<L->length;k++)L->Elem_array[k-1]=L->Elem_array[k];L->length--;break;}}if(i>L->length){printf(“要刪除的數據元素不存在!\n”);returnERROR;}returnOK;}2.2.2順序表的基本操作

時間復雜度分析時間主要耗費在數據元素的比較和移動操作上。首先，在線性表L中查找值為x的結點是否存在;其次，若值為x的結點存在，且在線性表L中的位置為i，則在線性表L中刪除第i個元素。設在線性表L刪除數據元素概率為Pi，不失一般性，設各個位置是等概率，則Pi=1/n。

◆比較的平均次數：Ecompare=∑pi*i(1≦i≦n)∴Ecompare=(n+1)/2。

◆刪除時平均移動次數：Edelete=∑pi*(n-i)(1≦i≦n)∴Edelete=(n-1)/2。平均時間復雜度：Ecompare+Edelete=n，即為O(n)2.3線性表的鏈式存儲

2.3.1線性表的鏈式存儲結構鏈式存儲：用一組任意的存儲單元存儲線性表中的數據元素。用這種方法存儲的線性表簡稱線性鏈表。存儲鏈表中結點的一組任意的存儲單元可以是連續的，也可以是不連續的，甚至是零散分布在內存中的任意位置上的。鏈表中結點的邏輯順序和物理順序不一定相同。為了正確表示結點間的邏輯關系，在存儲每個結點值的同時，還必須存儲指示其直接后繼結點的地址(或位置)，稱為指針(pointer)或鏈(link)，這兩部分組成了鏈表中的結點結構，如圖2-2所示。鏈表是通過每個結點的指針域將線性表的n個結點按其邏輯次序鏈接在一起的。每一個結只包含一個指針域的鏈表，稱為單鏈表。為操作方便，總是在鏈表的第一個結點之前附設一個頭結點(頭指針)head指向第一結點。頭結點的數據域可以不存儲任何信息(或鏈表長度等信息)。datanext圖2-2鏈表結點結構data：數據域，存放結點的值。next：指針域，存放結點的直接后繼的地址。2.3線性表的鏈式存儲

3695headfat1100bat1300…………cat1305eat3700hatNULL…………1100370013001305batcateatfat

hat?head

圖2-3

帶頭結點的單鏈表的邏輯狀態、物理存儲方式單鏈表是由表頭唯一確定，因此單鏈表可以用頭指針的名字來命名。例1、線性表L=(bat，cat，eat，fat，hat)其帶頭結點的單鏈表的邏輯狀態和物理存儲方式如圖2-3所示。2.3線性表的鏈式存儲1結點的描述與實現

C語言中用帶指針的結構體類型來描述typedefstructLnode{ ElemTypedata;/*數據域，保存結點的值*/structLnode*next;/*指針域*/}LNode;/*結點的類型*/2結點的實現結點是通過動態分配和釋放來的實現，即需要時分配，不需要時釋放。實現時是分別使用C語言提供的標準函數：malloc()，realloc()，sizeof()，free()。2.3線性表的鏈式存儲補充原型：externvoid*realloc(void*ptr,size_tnewsize);用法：#include<stdlib.h>功能：改變ptr所指內存區域的大小為newsize長度。說明：如果重新分配成功則返回指向被分配內存的指針，否則返回空指針NULL。當內存不再使用時，應使用free()函數將內存塊釋放。補充Sizeof是計算對象所占的字節個數，通常用來查看變量或結構體等所占的字節個數。比如：int

a;

sizeof(a);

//

計算變量a所占的字節數，等價于sizeof(int)

struct

{

int

num;

char

name[];

int

age;

}person;

sizeof(person);

//

計算整個結構所占的字節總數

補充C語言中，free可以釋放calloc,malloc,realloc動態分配的空間。首先說明一下，你要釋放的不是你定義的指針，而是你定義的指針指向的空間。至于你定義的普通指針是不是可以通過free釋放，這個要看情況。如果你定義的指針指向動態分配的地址空間，則可以使用free釋放指針指向的這段空間；否則，就不能使用free釋放指針指向的空間。下面舉兩個例子：

例1：char*p=NULL;p=(char*)malloc(1024);if(p!=NULL)free(p);

例2：char*p=NULL;charbuf[1024];p=(char*)buf;free(p);其中，例1是對的，例2是錯誤的。

動態分配

p=(LNode*)malloc(sizeof(LNode));函數malloc分配了一個類型為LNode的結點變量的空間，并將其首地址放入指針變量p中。動態釋放

free(p);系統回收由指針變量p所指向的內存區。P必須是最近一次調用malloc函數時的返回值。2.3線性表的鏈式存儲2.3線性表的鏈式存儲⑴

結點的賦值

LNode*p;p=(LNode*)malloc(sizeof(LNode));p->data=20;p->next=NULL;p20NULL3最常用的基本操作及其示意圖⑵

常見的指針操作①

q=p;pa……操作前pa……q操作后②

q=p->next;bpa……操作前操作后qbpa……③

p=p->next;bpa……操作前操作后pba……④

q->next=p;c…pbqa……操作前操作后qb……ac…p(a)2.3線性表的鏈式存儲⑤

q->next=p->next;(a)xy…pbqa……操作前操作后qb……axy…p操作前ypx……bqa…操作后ypx……bqa…(b)操作前ypx……bqa…操作后ypx……bqa…(b)2.3線性表的鏈式存儲2.3.2單線性鏈式的基本操作1建立單鏈表假設線性表中結點的數據類型是整型，以32767作為結束標志。動態地建立單鏈表的常用方法有如下兩種：頭插入法，尾插入法。⑴頭插入法建表從一個空表開始，重復讀入數據，生成新結點，將讀入數據存放到新結點的數據域中，然后將新結點插入到當前鏈表的表頭上，直到讀入結束標志為止。即每次插入的結點都作為鏈表的第一個結點。算法描述LNode*create_LinkList(void)/*頭插入法創建單鏈表,鏈表的頭結點head作為返回值*/{intdata;LNode*head,*p;head=(LNode*)malloc(sizeof(LNode));head->next=NULL;/*創建鏈表的表頭結點head*/while(1){scanf(“%d”,&data);if(data==32767)break;p=(LNode*)malloc(sizeof(LNode));p–>data=data;/*數據域賦值*/p–>next=head–>next;head–>next=p;/*鉤鏈，新創建的結點總是作為第一個結點*/}return(head);}2.3.2單線性鏈式的基本操作(2)尾插入法建表頭插入法建立鏈表雖然算法簡單，但生成的鏈表中結點的次序和輸入的順序相反。若希望二者次序一致，可采用尾插法建表。該方法是將新結點插入到當前鏈表的表尾，使其成為當前鏈表的尾結點。2.3.2單線性鏈式的基本操作2.3.2單線性鏈式的基本操作算法描述LNode*create_LinkList(void)/*尾插入法創建單鏈表,鏈表的頭結點head作為返回值*/{intdata;LNode*head,*p,*q;head=p=(LNode*)malloc(sizeof(LNode));p->next=NULL;/*創建單鏈表的表頭結點head*/while(1){scanf(“%d”,&data);if(data==32767)break;q=(LNode*)malloc(sizeof(LNode));q–>data=data;/*數據域賦值*/q–>next=p–>next;p–>next=q;p=q;

/*鉤鏈，新創建的結點總是作為最后一個結點*/}return(head);}2.3.2單線性鏈式的基本操作無論是哪種插入方法，如果要插入建立的單線性鏈表的結點是n個，算法的時間復雜度均為O(n)。對于單鏈表，無論是哪種操作，只要涉及到鉤鏈(或重新鉤鏈)，如果沒有明確給出直接后繼，鉤鏈(或重新鉤鏈)的次序必須是“先右后左”。2.3.2單線性鏈式的基本操作2單鏈表的查找(1)按序號查找取單鏈表中的第i個元素。對于單鏈表，不能象順序表中那樣直接按序號i訪問結點，而只能從鏈表的頭結點出發，沿鏈域next逐個結點往下搜索，直到搜索到第i個結點為止。因此，鏈表不是隨機存取結構。設單鏈表的長度為n，要查找表中第i個結點，僅當1≦i≦n時，i的值是合法的。算法描述ElemTypeGet_Elem(LNode*L，inti){intj;LNode*p;p=L->next;j=1;/*使p指向第一個結點*/while(p!=NULL&&j<i){p=p–>next;j++;}/*移動指針p,j計數*/if(j!=i)return(-32768);elsereturn(p->data);/*p為NULL表示i太大;j>i表示i為0*/}移動指針p的頻度：i<1時：0次;i∈[1,n]：i-1次；i>n：n次。∴時間復雜度:O(n)。2.3.2單線性鏈式的基本操作(2)

按值查找

按值查找是在鏈表中，查找是否有結點值等于給定值key的結點?若有，則返回首次找到的值為key的結點的存儲位置；否則返回NULL。查找時從開始結點出發，沿鏈表逐個將結點的值和給定值key作比較。2.3.2單線性鏈式的基本操作算法描述LNode*Locate_Node(LNode*L，intkey)/*在以L為頭結點的單鏈表中查找值為key的第一個結點*/{LNode*p=L–>next;while(p!=NULL&&p–>data!=key)p=p–>next;if(p–>data==key)returnp;else{printf(“所要查找的結點不存在!!\n”);retutn(NULL);}}算法的執行與形參key有關，平均時間復雜度為O(n)。2.3.2單線性鏈式的基本操作3單鏈表的插入

插入運算是將值為e的新結點插入到表的第i個結點的位置上，即插入到ai-1與ai之間。因此，必須首先找到ai-1所在的結點p，然后生成一個數據域為e的新結點q，q結點作為p的直接后繼結點。設鏈表的長度為n，合法的插入位置是1≦i≦n。算法的時間主要耗費移動指針p上，故時間復雜度亦為O(n)。算法描述voidInsert_LNode(LNode*L，inti，ElemTypee)/*在以L為頭結點的單鏈表的第i個位置插入值為e的結點*/{intj=0;LNode*p，*q;p=L–>next;while(p!=NULL&&j<i-1){p=p–>next;j++;}if(j!=i-1)printf(“i太大或i為0!!\n”);else{q=(LNode*)malloc(sizeof(LNode));q–>data=e;q–>next=p–>next;p–>next=q;}}2.3.2單線性鏈式的基本操作4單鏈表的刪除⑴

按序號刪除

刪除單鏈表中的第i個結點。為了刪除第i個結點ai，必須找到結點的存儲地址。該存儲地址是在其直接前趨結點ai-1的next域中，因此，必須首先找到ai-1的存儲位置p，然后令p–>next指向ai的直接后繼結點，即把ai從鏈上摘下。最后釋放結點ai的空間，將其歸還給“存儲池”。設單鏈表長度為n，則刪去第i個結點僅當1≦i≦n時是合法的。則當i=n+1時，雖然被刪結點不存在，但其前趨結點卻存在，是終端結點。故判斷條件之一是p–>next!=NULL。顯然此算法的時間復雜度也是O(n)。2.3.2單線性鏈式的基本操作算法描述voidDelete_LinkList(LNode*L，inti)/*刪除以L為頭結點的單鏈表中的第i個結點*/{intj=1;LNode*p，*q;p=L;q=L->next;while(p->next!=NULL&&j<i){p=q;q=q–>next;j++;}if(j!=i)printf(“i太大或i為0!!\n”);else{p–>next=q–>next;free(q);}}2.3.2單線性鏈式的基本操作⑵按值刪除

刪除單鏈表中值為key的第一個結點。與按值查找相類似，首先要查找值為key的結點是否存在?若存在，則刪除；否則返回NULL。2.3.2單線性鏈式的基本操作算法描述voidDelete_LinkList(LNode*L，intkey)/*刪除以L為頭結點的單鏈表中值為key的第一個結點*/{LNode*p=L,*q=L–>next;while(q!=NULL&&q–>data!=key){p=q;q=q–>next;}if(q–>data==key){p->next=q->next;free(q);}elseprintf(“所要刪除的結點不存在!!\n”);}2.3.2單線性鏈式的基本操作算法的執行與形參key有關，平均時間復雜度為O(n)。從上面的討論可以看出，鏈表上實現插入和刪除運算，無需移動結點，僅需修改指針。解決了順序表的插入或刪除操作需要移動大量元素的問題。變形之一：刪除單鏈表中值為key的所有結點。與按值查找相類似，但比前面的算法更簡單。基本思想：從單鏈表的第一個結點開始，對每個結點進行檢查，若結點的值為key，則刪除之，然后檢查下一個結點，直到所有的結點都檢查。2.3.2單線性鏈式的基本操作算法描述voidDelete_LinkList_Node(LNode*L，intkey)/*刪除以L為頭結點的單鏈表中值為key的第一個結點*/{LNode*p=L,*q=L–>next;while(q!=NULL){if(q–>data==key){p->next=q->next;free(q);q=p->next;}else{p=q;q=q–>next;}}}2.3.2單線性鏈式的基本操作變形之二：刪除單鏈表中所有值重復的結點，使得所有結點的值都不相同。與按值查找相類似，但比前面的算法更復雜。基本思想：從單鏈表的第一個結點開始，對每個結點進行檢查：檢查鏈表中該結點的所有后繼結點，只要有值和該結點的值相同，則刪除之；然后檢查下一個結點，直到所有的結點都檢查。2.3.2單線性鏈式的基本操作算法描述voidDelete_Node_value(LNode*L)/*刪除以L為頭結點的單鏈表中所有值相同的結點*/{LNode*p=L->next,*q,*ptr;while(p!=NULL)/*檢查鏈表中所有結點*/{*q=p,*ptr=p–>next;/*檢查結點p的所有后繼結點ptr*/while(ptr!=NULL){if(ptr–>data==p->data){q->next=ptr->next;free(ptr);ptr=q->next;}else{q=ptr;ptr=ptr–>next;}}p=p->next;}}2.3.2單線性鏈式的基本操作5單鏈表的合并

設有兩個有序的單鏈表，它們的頭指針分別是La、Lb，將它們合并為以Lc為頭指針的有序鏈表。合并前的示意圖如圖2-4所示。15?圖2-4兩個有序的單鏈表La，Lb的初始狀態-249……Lb

pb-7312……23?La

Lcpapc2.3.2單線性鏈式的基本操作合并了值為-7，-2的結點后示意圖如圖2-5所示。圖2-5

合并了值為-7，-2的結點后的狀態-249……

15?Lb

pcpbLc-7312……

23?La

pa算法說明——算法中pa，pb分別是待考察的兩個鏈表的當前結點，pc是合并過程中合并的鏈表的最后一個結點。2.3.2單線性鏈式的基本操作算法描述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->data<pb->data){pc->next=pa;pc=pa;pa=pa->next;}/*將pa所指的結點合并，pa指向下一個結點*/if(pa->data>pb->data){pc->next=pb;pc=pb;pb=pb->next;}/*將pa所指的結點合并，pa指向下一個結點*/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;elsepc->next=pb;/*將剩余的結點鏈上*/free(Lb);return(Lc);}2.3.2單線性鏈式的基本操作算法分析若La，Lb兩個鏈表的長度分別是m，n，則鏈表合并的時間復雜度為O(m+n)。2.3.2單線性鏈式的基本操作2.3.3循環鏈表循環鏈表(CircularLinkedList)：是一種頭尾相接的鏈表。其特點是最后一個結點的指針域指向鏈表的頭結點，整個鏈表的指針域鏈接成一個環。從循環鏈表的任意一個結點出發都可以找到鏈表中的其它結點，使得表處理更加方便靈活。圖2-6是帶頭結點的單循環鏈表的示意圖。空表圖2-6單循環鏈表示意圖非空表a1

a2

……anhead

head

循環鏈表的操作對于單循環鏈表，除鏈表的合并外，其它的操作和單線性鏈表基本上一致，僅僅需要在單線性鏈表操作算法基礎上作以下簡單修改：⑴判斷是否是空鏈表：head->next==head;⑵判斷是否是表尾結點：p->next==head;2.3.3循環鏈表2.4雙向鏈表雙向鏈表(DoubleLinkedList):指的是構成鏈表的每個結點中設立兩個指針域：一個指向其直接前趨的指針域prior，一個指向其直接后繼的指針域next。這樣形成的鏈表中有兩個方向不同的鏈，故稱為雙向鏈表。和單鏈表類似，雙向鏈表一般增加頭指針也能使雙鏈表上的某些運算變得方便。將頭結點和尾結點鏈接起來也能構成循環鏈表，并稱之為雙向循環鏈表。雙向鏈表是為了克服單鏈表的單向性的缺陷而引入的。1雙向鏈表的結點及其類型定義雙向鏈表的結點的類型定義如下。其結點形式如圖2-7所示，帶頭結點的雙向鏈表的形式如圖2-8所示。typedefstructDulnode{ElemTypedata;structDulnode*prior,*next;}DulNode;datanextprior圖2-7雙向鏈表結點形式……非空雙向鏈表head?a2a1an?空雙向鏈表head??圖2-8帶頭結點的雙向鏈表形式2.4雙向鏈表雙向鏈表結構具有對稱性，設p指向雙向鏈表中的某一結點，則其對稱性可用下式描述：(p->prior)->next=p=(p->next)->prior;結點p的存儲位置存放在其直接前趨結點p->prior的直接后繼指針域中，同時也存放在其直接后繼結點p->next的直接前趨指針域中。2.4雙向鏈表2雙向鏈表的基本操作(1)

雙向鏈表的插入將值為e的結點插入雙向鏈表中。插入前后鏈表的變化如圖2-9所示。Sep…………aiai+1Sep…………aiai+1圖2-9雙向鏈表的插入2.4雙向鏈表①

插入時僅僅指出直接前驅結點，鉤鏈時必須注意先后次序是：“先右后左”

。部分語句組如下：S=(DulNode*)malloc(sizeof(DulNode));S->data=e;S->next=p->next;p->next->prior=S;p->next=S;S->prior=p;/*鉤鏈次序非常重要

*/②

插入時同時指出直接前驅結點p和直接后繼結點q，鉤鏈時無須注意先后次序。部分語句組如下：S=(DulNode*)malloc(sizeof(DulNode));S->data=e;p->next=S;S->next=q;S->prior=p;q->prior=S;

2.4雙向鏈表

(2)

雙向鏈表的結點刪除

設要刪除的結點為p，刪除時可以不引入新的輔助指針變量，可以直接先斷鏈，再釋放結點。部分語句組如下：p->prior->next=p->next;p->next->prior=p->prior;free(p);注意：

與單鏈表的插入和刪除操作不同的是，在雙向鏈表中插入和刪除必須同時修改兩個方向上的指針域的指向。2.4雙向鏈表2.5一元多項式的表示和相加1一元多項式的表示一元多項式p(x)=p0+p1x+p2x2+…+pnxn，由n+1個系數唯一確定。則在計算機中可用線性表(p0

，p1

，p2

，…

，pn

)表示。既然是線性表，就可以用順序表和鏈表來實現。兩種不同實現方式的元素類型定義如下：(1)順序存儲表示的類型typedefstruct{floatcoef;/*系數部分*/intexpn;/*指數部分*/}ElemType;(2)鏈式存儲表示的類型typedefstructploy{floatcoef;/*系數部分*/intexpn;/*指數部分*/structploy*next;}Ploy;2.5一元多項式的表示和相加2一元多項式的相加

不失一般性，設有兩個一元多項式：P(x)=p0+p1x+p2x2+…+pnxn，Q(x)=q0+q1x+q2x2+…+qmxm(m<n)R(x)=P(x)+Q(x)R(x)由線性表R((p0+q0)，(p1+q1)，(p2+q2)，…，(pm+qm)，…，pn)唯一表示。2.5一元多項式的表示和相加⑴

順序存儲表示的相加線性表的定義typedefstruct{ElemTypea[MAX_SIZE];intlength;}Sqlist;

用順序表示的相加非常簡單。訪問第5項可直接訪問：L.a[4].coef，L.a[4].expn(2)

鏈式存儲表示的相加當采用鏈式存儲表示時，根據結點類型定義，凡是系數為0的項不在鏈表中出現，從而可以大大減少鏈表的長度。2.5一元多項式的表示和相加一元多項式相加的實質是：指數不同：是鏈表的合并。指數相同：系數相加，和為0，去掉結點，和不為0，修改結點的系數域。算法之一：就在原來兩個多項式鏈表的基礎上進行相加，相加后原來兩個多項式鏈表就不在存在。當然再要對原來兩個多項式進行其它操作就不允許了。2.5一元多項式的表示和相加算法描述Ploy*add_ploy(ploy*La，ploy*Lb)/*將以La，Lb為頭指針表示的一元多項式相加*/{ploy*Lc,*pc,*pa,*pb,*ptr;floatx;Lc=pc=La;pa=La->next;pb=Lb->next;while(pa!=NULL&&pb!=NULL){if(pa->expn<pb->expn){pc->next=pa;pc=pa;pa=pa->next;}/*將pa所指的結點合并，pa指向下一個結點*/if(pa->expn>pb->expn){pc->next=pb;pc=pb;pb=pb->next;}/*將pb所指的結點合并，pb指向下一個結點*/2.5一元多項式的表示和相加else{x=pa->coef+pb->coef;if(abs(x)<=1.0e-6)/*如果系數和為0，刪除兩個結點*/{ptr=pa;pa=pa->next;free(ptr);ptr=pb;pb=pb->next;free(ptr);}else/*如果系數和不為0，修改其中一個結點的系數域，刪除另一個結點*/{pc->next=pa;pa->coef=x;pc=pa;pa=pa->next;ptr=pb;pb=pb->next;free(p