數(shù)據(jù)結(jié)構(gòu)(C語言版)第2章-線性表課件

數(shù)據(jù)結(jié)構(gòu)(DataStructures)

(C語言版)主講教師：吳讓仲Instructor:WU,RANGZHONGE-mail:wurangzhong@163.com第二章線性表2.1線性表的類型定義2.2線性表的順序表示和實現(xiàn)2.3線性表的鏈?zhǔn)奖硎竞蛯崿F(xiàn)2.3.1線性鏈表2.3.2循環(huán)鏈表2.3.3雙向鏈表2.4一元多項式的表示及相加2.1線性表的邏輯結(jié)構(gòu)線性表(LinearList)：由n(n≧0)個數(shù)據(jù)元素(結(jié)點)a1，a2，…an組成的有限序列。其中數(shù)據(jù)元素的個數(shù)n定義為表的長度。當(dāng)n=0時稱為空表，常常將非空的線性表(n>0)記作：(a1，a2，…an)這里的數(shù)據(jù)元素ai(1≦i≦n)只是一個抽象的符號，其具體含義在不同的情況下可以不同。例1、26個英文字母組成的字母表（A，B，C、…、Z）例2、某校從1978年到1983年各種型號的計算機擁有量的變化情況。（6，17，28，50，92，188）例3、學(xué)生健康情況登記表如下：姓名學(xué)號性別年齡健康情況王小林790631男18健康陳紅790632女20一般劉建平790633男21健康張立立790634男17神經(jīng)衰弱……..……..…….…….…….例4、一副撲克的點數(shù)（2，3，4，…，J，Q，K，A）從以上例子可看出線性表的邏輯特征是：在非空的線性表，有且僅有一個開始結(jié)點a1，它沒有直接前趨，而僅有一個直接后繼a2；有且僅有一個終端結(jié)點an，它沒有直接后繼，而僅有一個直接前趨an-1；其余的內(nèi)部結(jié)點ai(2≦i≦n-1)都有且僅有一個直接前趨ai-1和一個直接后繼ai+1。線性表是一種典型的線性結(jié)構(gòu)。數(shù)據(jù)的運算是定義在邏輯結(jié)構(gòu)上的，而運算的具體實現(xiàn)則是在存儲結(jié)構(gòu)上進(jìn)行的。抽象數(shù)據(jù)類型的定義為：P19抽象數(shù)據(jù)類型線性表的定義ADTList{數(shù)據(jù)對象：D={ai=ai∈ElemSet，i=1，2，…，n，n≧0}數(shù)據(jù)關(guān)系：R1={<ai-1，ai>|ai-1，ai∈D,i=2,..,n}基本操作：InitList(&L);Destory(&L);ClearList(&L)；ListEmpty(L);ListLength(L);GetElem(L,i,&e);LocateElem(L,e,compare());PriorElem(L,cur_e,&pre_e)NextElem(L,cur_e,&next_e);ListInsert(&L,i,e);ListDelete(&L,I,&e);}§2TheListADTObjects:(item0,item1,

,itemN

1)Operations:

Findingthelength,N,ofalist.

Printingalltheitemsinalist.

Makinganemptylist.

Findingthek-thitemfromalist,0

k<N.

Insertinganewitemafterthek-thitemofalist,0

k<N.

Deletinganitemfromalist.

Findingnextofthecurrentitemfromalist.

Findingpreviousofthecurrentitemfromalist.

ADT:Whyafter?【Definition】DataType={Objects}{Operations}〖Example〗int={0,1,2,,INT_MAX,INT_MIN}

{,,,,,}【Definition】AnAbstractDataType(ADT)isadatatypethatisorganizedinsuchawaythatthespecificationontheobjectsandspecificationoftheoperationsontheobjectsare

separatedfrom

therepresentationoftheobjectsandtheimplementationontheoperations.

算法2.1例2-1利用兩個線性表LA和LB分別表示兩個集合A和B，現(xiàn)要求一個新的集合A=A∪B。

voidUnion(SqList*La,SqListLb){ElemTypee;intLa_len,Lb_len;inti;La_len=ListLength(*La);Lb_len=ListLength(Lb);for(i=1;i<=Lb_len;i++){GetElem(Lb,i,&e);if(!LocateElem(*La,e,equal))ListInsert(La,++La_len,e);}}算法2.2例2-2巳知線性表LA和線性表LB中的數(shù)據(jù)元素按值非遞減有序排列，現(xiàn)要求將LA和LB歸并為一個新的線性表LC，且LC中的元素仍按值非遞減有序排列。此問題的算法如下：

voidmergelist(listla，listlb，list&lc){initlist(lc);I=j=1;k=0;la_len=listlength(la);lb_len=listlength(lb);while((I<=la_len)&&(j<=lb_len)){getelem(la，I，ai);getelem(lb，j，bj);if(ai<=bj){listinsert(lc，++k，ai);++I;}else{listinsert(lc，++k，bj);++j;}}while(I<=la_len){getelem((la，I++，ai);listinsert(lc，++k，ai);}while(j<=lb_len){getelem((lb，j++，bj);listinsert(lc，++k，bi);}}兩種算法時間復(fù)雜度比較算法1：O(ListLength(LA)*ListLength(LB))算法2：O(ListLength(LA)+ListLength(LB))自測題1線性表是具有n個（）的有限序列（n>0）?！厩迦A大學(xué)1998一.4（2分）】A．表元素B．字符C．?dāng)?shù)據(jù)元素D．?dāng)?shù)據(jù)項E．信息項

2.2線性表的順序存儲結(jié)構(gòu)2.2.1線性表(LinearList)把線性表的結(jié)點按邏輯順序依次存放在一組地址連續(xù)的存儲單元里。用這種方法存儲的線性表簡稱順序表。假設(shè)線性表的每個元素需占用l個存儲單元，并以所占的第一個單元的存儲地址作為數(shù)據(jù)元素的存儲位置。則線性表中第i+1個數(shù)據(jù)元素的存儲位置LOC(ai+1)和第i個數(shù)據(jù)元素的存儲位置LOC(ai)之間滿足下列關(guān)系：LOC(ai+1)=LOC(ai)+l線性表的第i個數(shù)據(jù)元素ai的存儲位置為：LOC(ai)=LOC(a1)+(i-1)*l由于C語言中的一維數(shù)組也是采用順序存儲表示，故可以用數(shù)組類型來描述順序表。又因為除了用數(shù)組來存儲線性表的元素之外，順序表還應(yīng)該用一個變量來表示線性表的長度屬性，所以我們用結(jié)構(gòu)類型來定義順序表類型。#defineListSize100typedefintDataType;typedefstruc{DataTypedata[ListSize];intlength;}Sqlist;SimpleArrayimplementationofListsarray[i]=itemi

MaxSizehastobeestimated.AddressContentarray+iitemiarray+i+1itemi+1……………………Sequentialmapping

Find_KthtakesO(1)time.

InsertionandDeletionnotonlytakeO(N)time,butalsoinvolvealotofdatamovementswhichtakestime.3/182.2.2順序表上實現(xiàn)的基本操作在順序表(SequentialList)存儲結(jié)構(gòu)中，很容易實現(xiàn)線性表的一些操作，如線性表的構(gòu)造、第i個元素的訪問。注意：C語言中的數(shù)組下標(biāo)從“0”開始，因此，若L是Sqlist類型的順序表，則表中第i個元素是L.data[i-1]。以下主要討論線性表的插入和刪除兩種運算。1、插入(Insert)線性表的插入運算是指在表的第i個位置上，插入一個新結(jié)點x，使長度為n的線性表(a1，…ai-1，ai，…，an)變成長度為n+1的線性表(a1，…ai-1，x，ai，…，an)

算法2.3voidInsertList(Sqlist*L，DataTypex，inti){intj;if(i<1||i>l.length+1)printf(“Positionerror”);returnERRORif(L.length>=ListSize)printf(“overflow”);exit(overflow);for(j=L.length-1;j>=i-1;j--)L.data[j+1]=L.data[j];L.data[i-1]=x;L.length++;}現(xiàn)在分析算法的復(fù)雜度。這里的問題規(guī)模是表的長度，設(shè)它的值為。該算法的時間主要化費在循環(huán)的結(jié)點后移語句上，該語句的執(zhí)行次數(shù)（即移動結(jié)點的次數(shù)）是。由此可看出，所需移動結(jié)點的次數(shù)不僅依賴于表的長度，而且還與插入位置有關(guān)。當(dāng)時，由于循環(huán)變量的終值大于初值，結(jié)點后移語句將不進(jìn)行；這是最好情況，其時間復(fù)雜度O（1）；當(dāng)i=1時，結(jié)點后移語句將循環(huán)執(zhí)行n次，需移動表中所有結(jié)點，這是最壞情況，其時間復(fù)雜度為O（n）。由于插入可能在表中任何位置上進(jìn)行，因此需分析算法的平均復(fù)雜度在長度為n的線性表中第i個位置上插入一個結(jié)點，令Eis(n)表示移動結(jié)點的期望值（即移動的平均次數(shù)），則在第i個位置上插入一個結(jié)點的移動次數(shù)為n-i+1。故Eis(n)=∑pi(n-i+1)不失一般性，假設(shè)在表中任何位置(1≦i≦n+1)上插入結(jié)點的機會是均等的，則p1=p2=p3=…=pn+1=1/(n+1)因此，在等概率插入的情況下，Eis(n)=∑(n-i+1)/(n+1)=n/2也就是說，在順序表上做插入運算，平均要移動表上一半結(jié)點。當(dāng)表長n較大時，算法的效率相當(dāng)?shù)?。雖然Eis(n)中n的的系數(shù)較小，但就數(shù)量級而言，它仍然是線性階的。因此算法的平均時間復(fù)雜度為O(n)。2、刪除(Delete)線性表的刪除運算是指將表的第i(1≦i≦n)結(jié)點刪除，使長度為n的線性表：(a1，…ai-1，ai，ai+1…，an)變成長度為n-1的線性表(a1，…ai-1，ai+1，…，an)voiddeleteList(Sqlist*L，inti){intj;if(i<1||i>L.length)printf(“Positionerror”);returnERRORfor(j=i;j<=L.length-1;j++)L.data[j-1]=L.data[j];L.length--;}該算法的時間分析與插入算法相似，結(jié)點的移動次數(shù)也是由表長n和位置i決定。若i=n，則由于循環(huán)變量的初值大于終值，前移語句將不執(zhí)行，無需移動結(jié)點；若i=1，則前移語句將循環(huán)執(zhí)行n-1次，需移動表中除開始結(jié)點外的所有結(jié)點。這兩種情況下算法的時間復(fù)雜度分別為O(1)和O(n)。刪除算法的平均性能分析與插入算法相似。在長度為n的線性表中刪除一個結(jié)點，令Ede(n)表示所需移動結(jié)點的平均次數(shù)，刪除表中第i個結(jié)點的移動次數(shù)為n-i，故Ede(n)=∑pi(n-i)式中，pi表示刪除表中第i個結(jié)點的概率。在等概率的假設(shè)下，p1=p2=p3=…=pn=1/n由此可得：Ede(n)=∑(n-i)/n=(n-1)/2即在順序表上做刪除運算，平均要移動表中約一半的結(jié)點，平均時間復(fù)雜度也是O(n)。

順序表的優(yōu)點和缺點優(yōu)點存儲密度大隨機存取缺點插入和刪除必須大量移動元素必須預(yù)先確定空間表空間不易擴(kuò)充2.3線性表的鏈?zhǔn)奖硎竞蛯崿F(xiàn)線性表的順序表示的特點是用物理位置上的鄰接關(guān)系來表示結(jié)點間的邏輯關(guān)系，這一特點使我們可以隨機存取表中的任一結(jié)點，但它也使得插入和刪除操作會移動大量的結(jié)點.為避免大量結(jié)點的移動，我們介紹線性表的另一種存儲方式，鏈?zhǔn)酱鎯Y(jié)構(gòu)，簡稱為鏈表(LinkedLists)。LinkedListsAddressDataPointer0010001101101011SUNQIANZHAOLI101100100011NULLHeadpointerptr=0110ZHAOQIANSUNLIptrNULLInitialization:typedefstructlist_node*list_ptr;typedefstructlist_node{

chardata[4];list_ptrnext;};list_ptrptr;Tolink‘ZHAO’and‘QIAN’:list_ptrN1,N2;N1=(list_ptr)malloc(sizeof(structlist_node));N2=(list_ptr)malloc(sizeof(structlist_node));N1->data=‘ZHAO’;N2->data=‘QIAN’;N1->next=N2;N2->next=NULL;ptr=N1;ZHAOQIANptrNULLLocationsofthenodesmaychangeondifferentruns.4/18

2.3.1線性鏈表鏈表是指用一組任意的存儲單元來依次存放線性表的結(jié)點，這組存儲單元即可以是連續(xù)的，也可以是不連續(xù)的，甚至是零散分布在內(nèi)存中的任意位置上的。因此，鏈表中結(jié)點的邏輯次序和物理次序不一定相同。為了能正確表示結(jié)點間的邏輯關(guān)系，在存儲每個結(jié)點值的同時，還必須存儲指示其后繼結(jié)點的地址（或位置）信息，這個信息稱為指針(pointer)或鏈(link)。這兩部分組成了鏈表中的結(jié)點結(jié)構(gòu)：

其中：data域是數(shù)據(jù)域，用來存放結(jié)點的值。next是指針域（亦稱鏈域），用來存放結(jié)點的直接后繼的地址（或位置）。鏈表正是通過每個結(jié)點的鏈域?qū)⒕€性表的n個結(jié)點按其邏輯次序鏈接在一起的。由于上述鏈表的每一個結(jié)只有一個鏈域，故將這種鏈表稱為單鏈表（SingleLinked)。顯然，單鏈表中每個結(jié)點的存儲地址是存放在其前趨結(jié)點next域中，而開始結(jié)點無前趨，故應(yīng)設(shè)頭指針head指向開始結(jié)點。同時，由于終端結(jié)點無后繼，故終端結(jié)點的指針域為空，即null（圖示中也可用^表示)。

例1、線性表:(bat，cat，eat，fat，hat，jat，lat，mat)datalink單鏈表示意圖如下：……110……130135……160頭指針head165170……200205…………………h(huán)at200…….……cat135eat170….……matNullbat130fat110…………jat205lat160…………165headbatcateatmat^…單鏈表是由表頭唯一確定，因此單鏈表可以用頭指針的名字來命名。例如：若頭指針名是head，則把鏈表稱為表head。用C語言描述的單鏈表如下：Typedefchardatatype;

Typedefstructnode{datatypedata;structnode*next;}listnode;typedeflistnode*linklist;listnode*p;linklisthead;注意區(qū)分指針變量和結(jié)點變量這兩個不同的概念。P為動態(tài)變量，它是通過標(biāo)準(zhǔn)函數(shù)生成的，即p=(listnode*)malloc(sizeof(listnode));函數(shù)malloc分配了一個類型為listnode的結(jié)點變量的空間，并將其首地址放入指針變量p中。一旦p所指的結(jié)點變量不再需要了，又可通過標(biāo)準(zhǔn)函數(shù)

free(p)釋放所指的結(jié)點變量空間。一、建立單鏈表假設(shè)線性表中結(jié)點的數(shù)據(jù)類型是字符，我們逐個輸入這些字符型的結(jié)點，并以換行符‘\n’為輸入結(jié)束標(biāo)記。動態(tài)地建立單鏈表的常用方法有如下兩種：1、頭插法建表該方法從一個空表開始，重復(fù)讀入數(shù)據(jù)，生成新結(jié)點，將讀入數(shù)據(jù)存放到新結(jié)點的數(shù)據(jù)域中，然后將新結(jié)點插入到當(dāng)前鏈表的表頭上，直到讀入結(jié)束標(biāo)志為止。linklistcreatelistf(void){charch;linklisthead;listnode*p;head=null;ch=getchar();while(ch!=‵\n′){p=(listnode*)malloc(sizeof(listnode));p–>data=ch;p–>next=head;head=p;ch=getchar();}return(head);}listlinkcreatelist(intn){intdata;linklisthead;listnode*phead=null;for(i=n;i>0;--i){p=(listnode*)malloc(sizeof(listnode));scanf((〝%d〞，&p–>data);p–>next=head;head=p;}return(head);}2、尾插法建表頭插法建立鏈表雖然算法簡單，但生成的鏈表中結(jié)點的次序和輸入的順序相反。若希望二者次序一致，可采用尾插法建表。該方法是將新結(jié)點插入到當(dāng)前鏈表的表尾上，為此必須增加一個尾指針r，使其始終指向當(dāng)前鏈表的尾結(jié)點。例：linklistcreater(){charch;linklisthead;listnode*p，*r;head=NULL;r=NULL;while((ch=getchar()!=‵\n′){p=(listnode*)malloc(sizeof(listnode));p–>data=ch;if(head=NULL)head=p;elser–>next=p;r=p;}if(r!=NULL)r–>next=NULL;return(head);}

說明：第一個生成的結(jié)點是開始結(jié)點，將開始結(jié)點插入到空表中，是在當(dāng)前鏈表的第一個位置上插入，該位置上的插入操作和鏈表中其它位置上的插入操作處理是不一樣的，原因是開始結(jié)點的位置是存放在頭指針（指針變量）中，而其余結(jié)點的位置是在其前趨結(jié)點的指針域中。算法中的第一個if語句就是用來對第一個位置上的插入操作做特殊處理。算法中的第二個if語句的作用是為了分別處理空表和非空表兩種不同的情況，若讀入的第一個字符就是結(jié)束標(biāo)志符，則鏈表head是空表，尾指針r亦為空，結(jié)點*r不存在；否則鏈表head非空，最后一個尾結(jié)點*r是終端結(jié)點，應(yīng)將其指針域置空。如果我們在鏈表的開始結(jié)點之前附加一個結(jié)點，并稱它為頭結(jié)點(dummyheadnode

)，那么會帶來以下兩個優(yōu)點：a、由于開始結(jié)點的位置被存放在頭結(jié)點的指針域中，所以在鏈表的第一個位置上的操作就和在表的其它位置上的操作一致，無需進(jìn)行特殊處理；b、無論鏈表是否為空，其頭指針是指向頭結(jié)點在的非空指針（空表中頭結(jié)點的指針域為空），因此空表和非空表的處理也就統(tǒng)一了?！腍(a)a1a2an∧H

(b)…其算法如下：linklistcreatelistr1(){charch;linklisthead=(linklist)malloc(sizeof(listnode));listnode*p，*r;r=head;while((ch=getchar())!=‵\n′{p=(listnode*)malloc(sizeof(listnode));p–>data=ch;p–>next=p;r=p;}r–>next=NULL;return(head);}上述算法里動態(tài)申請新結(jié)點空間時未加錯誤處理，可作下列處理：p=(listnode*)malloc(sizeof(listnode))if(p==NULL)error(〝Nospacefornodecanbeobtained〞);returnERROR;以上算法的時間復(fù)雜度均為O(n)。二、查找運算

1、按序號查找在鏈表中，即使知道被訪問結(jié)點的序號i，也不能象順序表中那樣直接按序號i訪問結(jié)點，而只能從鏈表的頭指針出發(fā)，順鏈域next逐個結(jié)點往下搜索，直到搜索到第i個結(jié)點為止。因此，鏈表不是隨機存取結(jié)構(gòu)。設(shè)單鏈表的長度為n，要查找表中第i個結(jié)點，僅當(dāng)1≦i≦n時，i的值是合法的。但有時需要找頭結(jié)點的位置，故我們將頭結(jié)點看做是第0個結(jié)點，其算法如下：Listnode*getnode(linklisthead，inti){intj;listnode*p;p=head;j=0;while(p–>next&&j<i){p=p–>next;j++;}if(i==j)returnp;elsereturnNULL;}

2、按值查找按值查找是在鏈表中，查找是否有結(jié)點值等于給定值key的結(jié)點，若有的話，則返回首次找到的其值為key的結(jié)點的存儲位置；否則返回NULL。查找過程從開始結(jié)點出發(fā)，順著鏈表逐個將結(jié)點的值和給定值key作比較。其算法如下：Listnode*locatenode(linklisthead，intkey){listnode*p=head–>next;while(p&&p–>data!=key)p=p–>next;returnp;}

該算法的執(zhí)行時間亦與輸入實例中的的取值key有關(guān)，其平均時間復(fù)雜度的分析類似于按序號查找，也為O(n)。三、插入運算插入運算是將值為x的新結(jié)點插入到表的第i個結(jié)點的位置上，即插入到ai-1與ai之間。因此，我們必須首先找到ai-1的存儲位置p，然后生成一個數(shù)據(jù)域為x的新結(jié)點*p，并令結(jié)點*p的指針域指向新結(jié)點，新結(jié)點的指針域指向結(jié)點ai。從而實現(xiàn)三個結(jié)點ai-1，x和ai之間的邏輯關(guān)系的變化，插入過程如：s->next=p->next;

p->next=s;

pxsai∧an…h(huán)…ai-1

注意：兩條語句的順序不能顛倒，否則ai的地址會丟失。另外，要注意合法i值為：1≤i≤n+1若i<1||i>n+1，則i值非法。①

②

Question:Whatwillhappeniftheorderofthetwostepsisreversed?具體算法如下：voidinsertnode(linklisthead，datetypex，inti){listnode*p，*q;p=getnode(head，i-1);if(p==NULL)error(〝positionerror〞);q=(listnode*)malloc(sizeof(listnode));q–>data=x;q–>next=p–next;p–>next=q;}設(shè)鏈表的長度為n，合法的插入位置是1≦i≦n+1。注意當(dāng)i=1時，getnode找到的是頭結(jié)點，當(dāng)i=n+1時，getnode找到的是結(jié)點an。因此，用i-1做實參調(diào)用getnode時可完成插入位置的合法性檢查。算法的時間主要耗費在查找操作getnode上，故時間復(fù)雜度亦為O(n)。四、刪除運算刪除運算是將表的第i個結(jié)點刪去。因為在單鏈表中結(jié)點ai的存儲地址是在其直接前趨結(jié)點aai-1的指針域next中，所以我們必須首先找到

ai-1的存儲位置p。然后令p–>next指向ai的直接后繼結(jié)點，即把ai從鏈上摘下。最后釋放結(jié)點ai的空間，將其歸還給“存儲池”。此過程為：s=p->next;ph…ai-1sp->next=p->next->next;free(s);ai∧an…ai+1ai①

②

Question:Howcanwedeletethefirstnodefromalist?Answer:Wecanaddadummyheadnodetoalist.具體算法如下：voiddeletelist(linklisthead，inti){listnode*p，*r;p=getnode(head，i-1);if(p==NULL||p–>next==NULL)returnERROR;r=p–>next;p–>next=r–>next;free(r);}

設(shè)單鏈表的長度為n，則刪去第i個結(jié)點僅當(dāng)1≦i≦n時是合法的。注意，當(dāng)i=n+1時，雖然被刪結(jié)點不存在，但其前趨結(jié)點卻存在，它是終端結(jié)點。因此被刪結(jié)點的直接前趨*p存在并不意味著被刪結(jié)點就一定存在，僅當(dāng)*p存在（即p!=NULL）且*p不是終端結(jié)點（即p–>next!=NULL）時，才能確定被刪結(jié)點存在。顯然此算法的時間復(fù)雜度也是O(n)。從上面的討論可以看出，鏈表上實現(xiàn)插入和刪除運算，無須移動結(jié)點，僅需修改指針。線性表實現(xiàn)方法的比較實現(xiàn)不同順序表方法簡單，各種高級語言中都有數(shù)組類型，容易實現(xiàn)；鏈表的操作是基于指針的，相對來講復(fù)雜些。

存儲空間的占用和分配不同從存儲的角度考慮，順序表的存儲空間是靜態(tài)分配的，在程序執(zhí)行之前必須明確規(guī)定它的存儲規(guī)模，也就是說事先對“MAXSIZE”要有合適的設(shè)定，過大造成浪費，過小造成溢出。而鏈表是動態(tài)分配存儲空間的，不用事先估計存儲規(guī)模?？梢妼€性表的長度或存儲規(guī)模難以估計時，采用鏈表。線性表運算的實現(xiàn)不同

按序號訪問數(shù)據(jù)元素，使用順序表優(yōu)于鏈表。插入刪除操作，使用鏈表優(yōu)于順序表。

2.3.2循環(huán)鏈表(LinkedCircularLists)循環(huán)鏈表時一種頭尾相接的鏈表。其特點是無須增加存儲量，僅對表的鏈接方式稍作改變，即可使得表處理更加方便靈活。單循環(huán)鏈表：在單鏈表中，將終端結(jié)點的指針域NULL改為指向表頭結(jié)點的或開始結(jié)點，就得到了單鏈形式的循環(huán)鏈表，并簡單稱為單循環(huán)鏈表。為了使空表和非空表的處理一致，循環(huán)鏈表中也可設(shè)置一個頭結(jié)點。這樣，空循環(huán)鏈表僅有一個自成循環(huán)的頭結(jié)點表示。如下圖所示：

a1an

….head⑴非空表⑵空表在用頭指針表示的單鏈表中，找開始結(jié)點a1的時間是O(1)，然而要找到終端結(jié)點an，則需從頭指針開始遍歷整個鏈表，其時間是O(n)head在很多實際問題中，表的操作常常是在表的首尾位置上進(jìn)行，此時頭指針表示的單循環(huán)鏈表就顯得不夠方便.如果改用尾指針rear來表示單循環(huán)鏈表，則查找開始結(jié)點a1和終端結(jié)點an都很方便，它們的存儲位置分別是(rear–>next)—>next和rear，顯然，查找時間都是O(1)。因此，實際中多采用尾指針表示單循環(huán)鏈表。由于循環(huán)鏈表中沒有NULL指針，故涉及遍歷操作時，其終止條件就不再像非循環(huán)鏈表那樣判斷p或p—>next是否為空，而是判斷它們是否等于某一指定指針，如頭指什或尾指針等.算法舉例單鏈表的合并LinkedListUnion(LinkedListla，LinkedListlb){∥將非遞減有序的單鏈表la和lb合并成新的∥非遞減有序單鏈表lc，并要求利用原表空間lc=(LNode*)malloc(sizeof(LNode);∥申請結(jié)點lc->next=NULL;∥初始化鏈表lcpa=la->next;∥pa是鏈表la的工作指針pb=lb->next;∥pb是鏈表lb的工作指針pc=lc;∥pc是鏈表lc的工作指針

while(pa&&pb)∥la和lb均非空 if(pa->data<=pb->data)∥la中元素插入lc

{pc->next=pa;pc=pa;pa=pa->next;}（接上頁）else∥lb中元素插入lc{pc->next=pb;pc=pb;pb=pb->next;}if(pa)pc->next=pa;∥若pa未到尾，將pc指向paelsepc->next=pb;∥若pb未到尾，將pc指向pb return(lc);}∥Union自測題2若線性表最常用的操作是存取第I個元素及其前驅(qū)和后繼元素的值，為節(jié)省時間應(yīng)采用的存儲方式()。A.單鏈表B.雙向鏈表C.單循環(huán)鏈表D.順序表【北京理工大學(xué)2004一.3(1分)】2.3.3雙向循環(huán)鏈表DoublyLinkedCircularListsDon’twehaveenoughheadachealready?Whydoweneedthedoublylinkedlists?Supposeyouhavealist1->2->3->…->m.Nowhowwouldyougetthem-thnode?I’llgofromthe1stnodetothem-thnode.Thenyouareaskedtofinditspreviousnodem

1?Uhhh...ThenI’llhavetogofromthe1stnodeagain.Buthey,whydoIwanttafindthepreviousnode?Whydoyouaskme?:-)Maybeyouwanttadeletethem-thnode?typedefstructnode*node_ptr;typedefstructnode{node_ptrllink;elementitem;node_ptrrlink;};item

llinkrlinkptr=ptr->llink->rlink=ptr->rlink->llinkAdoublylinkedcircularlistwithheadnode:item1

item2

item3

HAnemptylist:

H7/18雙向鏈表(DoublyLinkedLists):在單鏈表的每個結(jié)點里再增加一個指向其直接前趨的指針域prior。這樣就形成的鏈表中有兩個方向不同的鏈，故稱為雙向鏈表。形式描述為：

typedefstructdlistnode{datatypedata;structdlistnode*prior，*next;}dlistnode;typedefdlistnode*dlinklist;dlinklisthead;和單鏈表類似，雙鏈表一般也是由頭指針唯一確定的，增加頭指針也能使雙鏈表上的某些運算變得方便，將頭結(jié)點和尾結(jié)點鏈接起來也能構(gòu)成循環(huán)鏈表，并稱之為雙向鏈表。設(shè)指針p指向某一結(jié)點，則雙向鏈表結(jié)構(gòu)的對稱性可用下式描述：

(p—>prior)—>next=p=(p—>next)—>prior即結(jié)點*p的存儲位置既存放在其前趨結(jié)點*(p—>prior)的直接后繼指針域中，也存放在它的后繼結(jié)點*(p—>next)的直接前趨指針域中。head…a1a2∧an∧雙向鏈表的插入pqp->prior=q;12q->prior=p->prior;p->prior->next=q;q->next=p;34雙向鏈表的前插操作算法如下：voiddinsertbefor(dlistnode*p，datatypex){dlistnode*q=malloc(sizeof(dlistnode));q—>data=x;q—>prior=p—>prior;q—>next=p;p—>prior—>next=q;p—>prior=q;}雙向鏈表的刪除p12p->prior->next=p->next;p->next->prior=p->prior;free(p);voidddeletenode(dlistnode*p){p–>prior–>next=p–>next;p–>next–>prior=p–>prior;free(p);}

注意：與單鏈表的插入和刪除操作不同的是，在雙鏈表中插入和刪除必須同時修改兩個方向上的指針。上述兩個算是法的時間復(fù)雜度均為O(1)。自測題3某線性表中最常用的操作是在最后一個元素之后插入一個元素和刪除第一個元素，則采用（）存儲方式最節(jié)省運算時間。A.單鏈表B.僅有頭指針的單循環(huán)鏈表C.雙鏈表D.僅有尾指針的單循環(huán)鏈表【南開大學(xué)2000一.3】自測題4設(shè)一個鏈表最常用的操作是在末尾插入結(jié)點和刪除尾結(jié)點，則選用()最節(jié)省時間。A.帶頭結(jié)點的雙循環(huán)鏈表B.單循環(huán)鏈表C.帶尾指針的單循環(huán)鏈表D.單鏈表【江蘇大學(xué)2006一.3（2分）】TwoApplications

ThePolynomialADTObjects:P(x)=a1xe1+

+anxen;asetoforderedpairsof<ei,ai>whereaiisthecoefficientandeiistheexponent.ei

arenonnegativeintegers.Operations:

Findingdegree,max{ei

},ofapolynomial.

Additionoftwopolynomials.

Subtractionbetweentwopolynomials.

Multiplicationoftwopolynomials.

Differentiationofapolynomial.【Representation1】typedefstruct{

intCoeffArray[MaxDegree+1];

intHighPower;}*Polynomial;Ilikeit!It’seasytoimplementmostoftheoperations,suchasAddandMultiplication.Really?WhatisthetimecomplexityforfindingtheproductoftwopolynomialsofdegreeN1andN2?O(N1*N2)What’swrongwiththat?TrytoapplyMultPolynomialOnP1(x)=10x1000+5x14+1andP2(x)=3x1990

2x1492+11x+5--nowdoyouseemypoint?Given:Declaration:typedefstructpoly_node*poly_ptr;structpoly_node{

intCoefficient;/*assumecoefficientsareintegers*/

intExponent;poly_ptrNext;};typedefpoly_ptra;/*nodessortedbyexponent*/am1em1

a0e0NULL……a【Representation2】

Multilists〖Example〗Supposethatwehave40,000studentsand2,500courses.Printthestudents’namelistforeachcourses,andprinttheregisteredclasses’listforeachstudent.【Representation1】

intArray[40000][2500];11/18【Representation2】S1S2S3S4S5C1C2C3C412/183.CursorImplementationofLinkedLists(nopointer)

Featuresthatalinkedlistmusthave:Thedataarestoredinacollectionofstructures.Eachstructurecontainsdataandapointertothenextstructure.Anewstructurecanbeobtainedfromthesystem’sglobalmemorybyacalltomallocandreleasedbyacalltofree.CursorSpaceElementNext012S-1……123S-10Note:Theinterfaceforthecursorimplementation(giveninFigure3.27onp.52)isidenticaltothepointerimplementation(giveninFigure3.6onp.40).13/18ElementNext25S-20012S-1……malloc:pp=CursorSpace[0].Next;CursorSpace[0].Next=CursorSpace[p].Next;xElementNext25S-20012S-1……pfree(p):2CursorSpace[p].Next=CursorSpace[0].Next;pCursorSpace[0].Next=p;Note:Thecursorimplementationisusuallysignificantlyfaster

becauseofthelackofmemorymanagementroutines.ReadoperationimplementationsgiveninFigures3.31-3.3514/18靜態(tài)鏈表有些高級程序設(shè)計語言并沒有指針類型，如FORTRAN和JAVA。我們可以用數(shù)組來表示和實現(xiàn)一個鏈表，稱為靜態(tài)鏈表?？啥x如下：#defineMAXSIZE1000//最多元素個數(shù)typedefstruct{ElemTypedata;//數(shù)據(jù)元素intnext;//指向后繼元素在數(shù)組中的位置}SLinkedList[MAXSIZE];靜態(tài)鏈表圖示線性表L=（2，3，4，6，8，9）的靜態(tài)鏈表圖示datanext0416623334142259-16857891011自測題5靜態(tài)鏈表中指針表示的是()A.下一元素的地址B.內(nèi)存儲器的地址C.下一元素在數(shù)組中的位置D.左鏈或右鏈指向的元素的地址【中南大學(xué)2003二.2(1分)】靜態(tài)鏈表與動態(tài)鏈表靜態(tài)鏈表的操作和動態(tài)鏈表相似，只是以整型游標(biāo)代替動態(tài)指針。設(shè)以Sa表示靜態(tài)鏈表，通常可把Sa[0]理解為“頭結(jié)點”，第1個元素的位置由Sa[0].next指出,用全局整型變量av指出可利用空間的下標(biāo)。初始時將整個靜態(tài)鏈表看作一個“空表”，操作中用GetNode()和FreeNode()函數(shù)模擬C中的malloc()和free()函數(shù)。以下是初始化、取結(jié)點和釋放結(jié)點3個函數(shù)。靜態(tài)鏈表的初始化intInitilize()/*初始可利用空間表*/{inti;for(i=0;i<maxsize-1;i++)//鏈成可利用空間表

Sa[i].next=i+1;Sa[maxsize-1].next=-1;//鏈表尾av=1;

returnav;//返回可利用空間表的下標(biāo)}靜態(tài)鏈表的申請結(jié)點空間intGetNode()/*取結(jié)點*/{if(av!=-1)/*-1表示無空間*/{p=av;av=Sa[av].next;}/*p為可利用空間的下標(biāo)*/returnp;}靜態(tài)鏈表的釋放結(jié)點空間intFreeNode(intp)/*將p歸還到可利用空間表中*/{Sa[p].next=av;av=p;returnav;}靜態(tài)鏈表的操作舉例（1）

（1）查找值為x的結(jié)點intLocate(SLinkedListSL,ElemTypex){intp=SL[0].next;while(p!=-1&&SL[p].data!=x)p=SL[p].next;returnp;//元素下標(biāo)}靜態(tài)鏈表的操作舉例（2）(2)查找i第個結(jié)點ElemTypeLocate(SLinkedListSL,

inti){intj=1;if(i<0){printf(“參數(shù)錯誤”);exit(0);}p=SL[0].next;

while(p!=-1&&j<i){p=SL[p].next;j++;}if(p==-1){printf(“參數(shù)錯誤”);exit(0);}returnSL[i].data;}靜態(tài)鏈表的操作舉例（3）(3)插入第i個結(jié)點voidInsert(SLinkedListSL,ElemTypex,inti){pre=0;/*前驅(qū)*/j=1;s=GetNode();if(s==-1){printf(“overflow\n”);exit(0);}/*無空間*/else

{p=SL[0].next;while(p!=-1&&j<i)/*