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

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

(C語(yǔ)言版)主講教師：吳讓仲Instructor:WU,RANGZHONGE-mail:wurangzhong@163.com第二章線性表2.1線性表的類型定義2.2線性表的順序表示和實(shí)現(xiàn)2.3線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)2.3.1線性鏈表2.3.2循環(huán)鏈表2.3.3雙向鏈表2.4一元多項(xiàng)式的表示及相加2.1線性表的邏輯結(jié)構(gòu)線性表(LinearList)：由n(n≧0)個(gè)數(shù)據(jù)元素(結(jié)點(diǎn))a1，a2，…an組成的有限序列。其中數(shù)據(jù)元素的個(gè)數(shù)n定義為表的長(zhǎng)度。當(dāng)n=0時(shí)稱為空表，常常將非空的線性表(n>0)記作：(a1，a2，…an)這里的數(shù)據(jù)元素ai(1≦i≦n)只是一個(gè)抽象的符號(hào)，其具體含義在不同的情況下可以不同。例1、26個(gè)英文字母組成的字母表（A，B，C、…、Z）例2、某校從1978年到1983年各種型號(hào)的計(jì)算機(jī)擁有量的變化情況。（6，17，28，50，92，188）例3、學(xué)生健康情況登記表如下：姓名學(xué)號(hào)性別年齡健康情況王小林790631男18健康陳紅790632女20一般劉建平790633男21健康張立立790634男17神經(jīng)衰弱……..……..…….…….…….例4、一副撲克的點(diǎn)數(shù)（2，3，4，…，J，Q，K，A）從以上例子可看出線性表的邏輯特征是：在非空的線性表，有且僅有一個(gè)開(kāi)始結(jié)點(diǎn)a1，它沒(méi)有直接前趨，而僅有一個(gè)直接后繼a2；有且僅有一個(gè)終端結(jié)點(diǎn)an，它沒(méi)有直接后繼，而僅有一個(gè)直接前趨an-1；其余的內(nèi)部結(jié)點(diǎn)ai(2≦i≦n-1)都有且僅有一個(gè)直接前趨ai-1和一個(gè)直接后繼ai+1。線性表是一種典型的線性結(jié)構(gòu)。數(shù)據(jù)的運(yùn)算是定義在邏輯結(jié)構(gòu)上的，而運(yùn)算的具體實(shí)現(xiàn)則是在存儲(chǔ)結(jié)構(gòu)上進(jìn)行的。抽象數(shù)據(jù)類型的定義為：P19抽象數(shù)據(jù)類型線性表的定義ADTList{數(shù)據(jù)對(duì)象：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利用兩個(gè)線性表LA和LB分別表示兩個(gè)集合A和B，現(xiàn)要求一個(gè)新的集合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歸并為一個(gè)新的線性表LC，且LC中的元素仍按值非遞減有序排列。此問(wèn)題的算法如下：

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);}}兩種算法時(shí)間復(fù)雜度比較算法1：O(ListLength(LA)*ListLength(LB))算法2：O(ListLength(LA)+ListLength(LB))自測(cè)題1線性表是具有n個(gè)（）的有限序列（n>0）?！厩迦A大學(xué)1998一.4（2分）】A．表元素B．字符C．?dāng)?shù)據(jù)元素D．?dāng)?shù)據(jù)項(xiàng)E．信息項(xiàng)

2.2線性表的順序存儲(chǔ)結(jié)構(gòu)2.2.1線性表(LinearList)把線性表的結(jié)點(diǎn)按邏輯順序依次存放在一組地址連續(xù)的存儲(chǔ)單元里。用這種方法存儲(chǔ)的線性表簡(jiǎn)稱順序表。假設(shè)線性表的每個(gè)元素需占用l個(gè)存儲(chǔ)單元，并以所占的第一個(gè)單元的存儲(chǔ)地址作為數(shù)據(jù)元素的存儲(chǔ)位置。則線性表中第i+1個(gè)數(shù)據(jù)元素的存儲(chǔ)位置LOC(ai+1)和第i個(gè)數(shù)據(jù)元素的存儲(chǔ)位置LOC(ai)之間滿足下列關(guān)系：LOC(ai+1)=LOC(ai)+l線性表的第i個(gè)數(shù)據(jù)元素ai的存儲(chǔ)位置為：LOC(ai)=LOC(a1)+(i-1)*l由于C語(yǔ)言中的一維數(shù)組也是采用順序存儲(chǔ)表示，故可以用數(shù)組類型來(lái)描述順序表。又因?yàn)槌擞脭?shù)組來(lái)存儲(chǔ)線性表的元素之外，順序表還應(yīng)該用一個(gè)變量來(lái)表示線性表的長(zhǎng)度屬性，所以我們用結(jié)構(gòu)類型來(lái)定義順序表類型。#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順序表上實(shí)現(xiàn)的基本操作在順序表(SequentialList)存儲(chǔ)結(jié)構(gòu)中，很容易實(shí)現(xiàn)線性表的一些操作，如線性表的構(gòu)造、第i個(gè)元素的訪問(wèn)。注意：C語(yǔ)言中的數(shù)組下標(biāo)從“0”開(kāi)始，因此，若L是Sqlist類型的順序表，則表中第i個(gè)元素是L.data[i-1]。以下主要討論線性表的插入和刪除兩種運(yùn)算。1、插入(Insert)線性表的插入運(yùn)算是指在表的第i個(gè)位置上，插入一個(gè)新結(jié)點(diǎn)x，使長(zhǎng)度為n的線性表(a1，…ai-1，ai，…，an)變成長(zhǎng)度為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ù)雜度。這里的問(wèn)題規(guī)模是表的長(zhǎng)度，設(shè)它的值為。該算法的時(shí)間主要化費(fèi)在循環(huán)的結(jié)點(diǎn)后移語(yǔ)句上，該語(yǔ)句的執(zhí)行次數(shù)（即移動(dòng)結(jié)點(diǎn)的次數(shù)）是。由此可看出，所需移動(dòng)結(jié)點(diǎn)的次數(shù)不僅依賴于表的長(zhǎng)度，而且還與插入位置有關(guān)。當(dāng)時(shí)，由于循環(huán)變量的終值大于初值，結(jié)點(diǎn)后移語(yǔ)句將不進(jìn)行；這是最好情況，其時(shí)間復(fù)雜度O（1）；當(dāng)i=1時(shí)，結(jié)點(diǎn)后移語(yǔ)句將循環(huán)執(zhí)行n次，需移動(dòng)表中所有結(jié)點(diǎn)，這是最壞情況，其時(shí)間復(fù)雜度為O（n）。由于插入可能在表中任何位置上進(jìn)行，因此需分析算法的平均復(fù)雜度在長(zhǎng)度為n的線性表中第i個(gè)位置上插入一個(gè)結(jié)點(diǎn)，令Eis(n)表示移動(dòng)結(jié)點(diǎn)的期望值（即移動(dòng)的平均次數(shù)），則在第i個(gè)位置上插入一個(gè)結(jié)點(diǎn)的移動(dòng)次數(shù)為n-i+1。故Eis(n)=∑pi(n-i+1)不失一般性，假設(shè)在表中任何位置(1≦i≦n+1)上插入結(jié)點(diǎn)的機(jī)會(huì)是均等的，則p1=p2=p3=…=pn+1=1/(n+1)因此，在等概率插入的情況下，Eis(n)=∑(n-i+1)/(n+1)=n/2也就是說(shuō)，在順序表上做插入運(yùn)算，平均要移動(dòng)表上一半結(jié)點(diǎn)。當(dāng)表長(zhǎng)n較大時(shí)，算法的效率相當(dāng)?shù)?。雖然Eis(n)中n的的系數(shù)較小，但就數(shù)量級(jí)而言，它仍然是線性階的。因此算法的平均時(shí)間復(fù)雜度為O(n)。2、刪除(Delete)線性表的刪除運(yùn)算是指將表的第i(1≦i≦n)結(jié)點(diǎn)刪除，使長(zhǎng)度為n的線性表：(a1，…ai-1，ai，ai+1…，an)變成長(zhǎng)度為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--;}該算法的時(shí)間分析與插入算法相似，結(jié)點(diǎn)的移動(dòng)次數(shù)也是由表長(zhǎng)n和位置i決定。若i=n，則由于循環(huán)變量的初值大于終值，前移語(yǔ)句將不執(zhí)行，無(wú)需移動(dòng)結(jié)點(diǎn)；若i=1，則前移語(yǔ)句將循環(huán)執(zhí)行n-1次，需移動(dòng)表中除開(kāi)始結(jié)點(diǎn)外的所有結(jié)點(diǎn)。這兩種情況下算法的時(shí)間復(fù)雜度分別為O(1)和O(n)。刪除算法的平均性能分析與插入算法相似。在長(zhǎng)度為n的線性表中刪除一個(gè)結(jié)點(diǎn)，令Ede(n)表示所需移動(dòng)結(jié)點(diǎn)的平均次數(shù)，刪除表中第i個(gè)結(jié)點(diǎn)的移動(dòng)次數(shù)為n-i，故Ede(n)=∑pi(n-i)式中，pi表示刪除表中第i個(gè)結(jié)點(diǎn)的概率。在等概率的假設(shè)下，p1=p2=p3=…=pn=1/n由此可得：Ede(n)=∑(n-i)/n=(n-1)/2即在順序表上做刪除運(yùn)算，平均要移動(dòng)表中約一半的結(jié)點(diǎn)，平均時(shí)間復(fù)雜度也是O(n)。

順序表的優(yōu)點(diǎn)和缺點(diǎn)優(yōu)點(diǎn)存儲(chǔ)密度大隨機(jī)存取缺點(diǎn)插入和刪除必須大量移動(dòng)元素必須預(yù)先確定空間表空間不易擴(kuò)充2.3線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)線性表的順序表示的特點(diǎn)是用物理位置上的鄰接關(guān)系來(lái)表示結(jié)點(diǎn)間的邏輯關(guān)系，這一特點(diǎn)使我們可以隨機(jī)存取表中的任一結(jié)點(diǎn)，但它也使得插入和刪除操作會(huì)移動(dòng)大量的結(jié)點(diǎn).為避免大量結(jié)點(diǎn)的移動(dòng)，我們介紹線性表的另一種存儲(chǔ)方式，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，簡(jiǎn)稱為鏈表(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線性鏈表鏈表是指用一組任意的存儲(chǔ)單元來(lái)依次存放線性表的結(jié)點(diǎn)，這組存儲(chǔ)單元即可以是連續(xù)的，也可以是不連續(xù)的，甚至是零散分布在內(nèi)存中的任意位置上的。因此，鏈表中結(jié)點(diǎn)的邏輯次序和物理次序不一定相同。為了能正確表示結(jié)點(diǎn)間的邏輯關(guān)系，在存儲(chǔ)每個(gè)結(jié)點(diǎn)值的同時(shí)，還必須存儲(chǔ)指示其后繼結(jié)點(diǎn)的地址（或位置）信息，這個(gè)信息稱為指針(pointer)或鏈(link)。這兩部分組成了鏈表中的結(jié)點(diǎn)結(jié)構(gòu)：

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

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

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

free(p)釋放所指的結(jié)點(diǎn)變量空間。一、建立單鏈表假設(shè)線性表中結(jié)點(diǎn)的數(shù)據(jù)類型是字符，我們逐個(gè)輸入這些字符型的結(jié)點(diǎn)，并以換行符‘\n’為輸入結(jié)束標(biāo)記。動(dòng)態(tài)地建立單鏈表的常用方法有如下兩種：1、頭插法建表該方法從一個(gè)空表開(kāi)始，重復(fù)讀入數(shù)據(jù)，生成新結(jié)點(diǎn)，將讀入數(shù)據(jù)存放到新結(jié)點(diǎn)的數(shù)據(jù)域中，然后將新結(jié)點(diǎn)插入到當(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ǎn)單，但生成的鏈表中結(jié)點(diǎn)的次序和輸入的順序相反。若希望二者次序一致，可采用尾插法建表。該方法是將新結(jié)點(diǎn)插入到當(dāng)前鏈表的表尾上，為此必須增加一個(gè)尾指針r，使其始終指向當(dāng)前鏈表的尾結(jié)點(diǎn)。例：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);}

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

)，那么會(huì)帶來(lái)以下兩個(gè)優(yōu)點(diǎn)：a、由于開(kāi)始結(jié)點(diǎn)的位置被存放在頭結(jié)點(diǎn)的指針域中，所以在鏈表的第一個(gè)位置上的操作就和在表的其它位置上的操作一致，無(wú)需進(jìn)行特殊處理；b、無(wú)論鏈表是否為空，其頭指針是指向頭結(jié)點(diǎn)在的非空指針（空表中頭結(jié)點(diǎn)的指針域?yàn)榭眨?，因此空表和非空表的處理也就統(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);}上述算法里動(dòng)態(tài)申請(qǐng)新結(jié)點(diǎn)空間時(shí)未加錯(cuò)誤處理，可作下列處理：p=(listnode*)malloc(sizeof(listnode))if(p==NULL)error(〝Nospacefornodecanbeobtained〞);returnERROR;以上算法的時(shí)間復(fù)雜度均為O(n)。二、查找運(yùn)算

1、按序號(hào)查找在鏈表中，即使知道被訪問(wèn)結(jié)點(diǎn)的序號(hào)i，也不能象順序表中那樣直接按序號(hào)i訪問(wèn)結(jié)點(diǎn)，而只能從鏈表的頭指針出發(fā)，順鏈域next逐個(gè)結(jié)點(diǎn)往下搜索，直到搜索到第i個(gè)結(jié)點(diǎn)為止。因此，鏈表不是隨機(jī)存取結(jié)構(gòu)。設(shè)單鏈表的長(zhǎng)度為n，要查找表中第i個(gè)結(jié)點(diǎn)，僅當(dāng)1≦i≦n時(shí)，i的值是合法的。但有時(shí)需要找頭結(jié)點(diǎn)的位置，故我們將頭結(jié)點(diǎn)看做是第0個(gè)結(jié)點(diǎn)，其算法如下：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é)點(diǎn)值等于給定值key的結(jié)點(diǎn)，若有的話，則返回首次找到的其值為key的結(jié)點(diǎn)的存儲(chǔ)位置；否則返回NULL。查找過(guò)程從開(kāi)始結(jié)點(diǎn)出發(fā)，順著鏈表逐個(gè)將結(jié)點(diǎn)的值和給定值key作比較。其算法如下：Listnode*locatenode(linklisthead，intkey){listnode*p=head–>next;while(p&&p–>data!=key)p=p–>next;returnp;}

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

p->next=s;

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

注意：兩條語(yǔ)句的順序不能顛倒，否則ai的地址會(huì)丟失。另外，要注意合法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è)鏈表的長(zhǎng)度為n，合法的插入位置是1≦i≦n+1。注意當(dāng)i=1時(shí)，getnode找到的是頭結(jié)點(diǎn)，當(dāng)i=n+1時(shí)，getnode找到的是結(jié)點(diǎn)an。因此，用i-1做實(shí)參調(diào)用getnode時(shí)可完成插入位置的合法性檢查。算法的時(shí)間主要耗費(fèi)在查找操作getnode上，故時(shí)間復(fù)雜度亦為O(n)。四、刪除運(yùn)算刪除運(yùn)算是將表的第i個(gè)結(jié)點(diǎn)刪去。因?yàn)樵趩捂湵碇薪Y(jié)點(diǎn)ai的存儲(chǔ)地址是在其直接前趨結(jié)點(diǎn)aai-1的指針域next中，所以我們必須首先找到

ai-1的存儲(chǔ)位置p。然后令p–>next指向ai的直接后繼結(jié)點(diǎn)，即把a(bǔ)i從鏈上摘下。最后釋放結(jié)點(diǎn)ai的空間，將其歸還給“存儲(chǔ)池”。此過(guò)程為：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è)單鏈表的長(zhǎng)度為n，則刪去第i個(gè)結(jié)點(diǎn)僅當(dāng)1≦i≦n時(shí)是合法的。注意，當(dāng)i=n+1時(shí)，雖然被刪結(jié)點(diǎn)不存在，但其前趨結(jié)點(diǎn)卻存在，它是終端結(jié)點(diǎn)。因此被刪結(jié)點(diǎn)的直接前趨*p存在并不意味著被刪結(jié)點(diǎn)就一定存在，僅當(dāng)*p存在（即p!=NULL）且*p不是終端結(jié)點(diǎn)（即p–>next!=NULL）時(shí)，才能確定被刪結(jié)點(diǎn)存在。顯然此算法的時(shí)間復(fù)雜度也是O(n)。從上面的討論可以看出，鏈表上實(shí)現(xiàn)插入和刪除運(yùn)算，無(wú)須移動(dòng)結(jié)點(diǎn)，僅需修改指針。線性表實(shí)現(xiàn)方法的比較實(shí)現(xiàn)不同順序表方法簡(jiǎn)單，各種高級(jí)語(yǔ)言中都有數(shù)組類型，容易實(shí)現(xiàn)；鏈表的操作是基于指針的，相對(duì)來(lái)講復(fù)雜些。

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

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

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

a1an

….head⑴非空表⑵空表在用頭指針表示的單鏈表中，找開(kāi)始結(jié)點(diǎn)a1的時(shí)間是O(1)，然而要找到終端結(jié)點(diǎn)an，則需從頭指針開(kāi)始遍歷整個(gè)鏈表，其時(shí)間是O(n)head在很多實(shí)際問(wèn)題中，表的操作常常是在表的首尾位置上進(jìn)行，此時(shí)頭指針表示的單循環(huán)鏈表就顯得不夠方便.如果改用尾指針rear來(lái)表示單循環(huán)鏈表，則查找開(kāi)始結(jié)點(diǎn)a1和終端結(jié)點(diǎn)an都很方便，它們的存儲(chǔ)位置分別是(rear–>next)—>next和rear，顯然，查找時(shí)間都是O(1)。因此，實(shí)際中多采用尾指針表示單循環(huán)鏈表。由于循環(huán)鏈表中沒(méi)有NULL指針，故涉及遍歷操作時(shí)，其終止條件就不再像非循環(huán)鏈表那樣判斷p或p—>next是否為空，而是判斷它們是否等于某一指定指針，如頭指什或尾指針等.算法舉例單鏈表的合并LinkedListUnion(LinkedListla，LinkedListlb){∥將非遞減有序的單鏈表la和lb合并成新的∥非遞減有序單鏈表lc，并要求利用原表空間lc=(LNode*)malloc(sizeof(LNode);∥申請(qǐng)結(jié)點(diǎn)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;}（接上頁(yè)）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自測(cè)題2若線性表最常用的操作是存取第I個(gè)元素及其前驅(qū)和后繼元素的值，為節(jié)省時(shí)間應(yīng)采用的存儲(chǔ)方式()。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):在單鏈表的每個(gè)結(jié)點(diǎn)里再增加一個(gè)指向其直接前趨的指針域prior。這樣就形成的鏈表中有兩個(gè)方向不同的鏈，故稱為雙向鏈表。形式描述為：

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

(p—>prior)—>next=p=(p—>next)—>prior即結(jié)點(diǎn)*p的存儲(chǔ)位置既存放在其前趨結(jié)點(diǎn)*(p—>prior)的直接后繼指針域中，也存放在它的后繼結(jié)點(diǎn)*(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);}

注意：與單鏈表的插入和刪除操作不同的是，在雙鏈表中插入和刪除必須同時(shí)修改兩個(gè)方向上的指針。上述兩個(gè)算是法的時(shí)間復(fù)雜度均為O(1)。自測(cè)題3某線性表中最常用的操作是在最后一個(gè)元素之后插入一個(gè)元素和刪除第一個(gè)元素，則采用（）存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間。A.單鏈表B.僅有頭指針的單循環(huán)鏈表C.雙鏈表D.僅有尾指針的單循環(huán)鏈表【南開(kāi)大學(xué)2000一.3】自測(cè)題4設(shè)一個(gè)鏈表最常用的操作是在末尾插入結(jié)點(diǎn)和刪除尾結(jié)點(diǎn)，則選用()最節(jié)省時(shí)間。A.帶頭結(jié)點(diǎn)的雙循環(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)鏈表有些高級(jí)程序設(shè)計(jì)語(yǔ)言并沒(méi)有指針類型，如FORTRAN和JAVA。我們可以用數(shù)組來(lái)表示和實(shí)現(xiàn)一個(gè)鏈表，稱為靜態(tài)鏈表?？啥x如下：#defineMAXSIZE1000//最多元素個(gè)數(shù)typedefstruct{ElemTypedata;//數(shù)據(jù)元素intnext;//指向后繼元素在數(shù)組中的位置}SLinkedList[MAXSIZE];靜態(tài)鏈表圖示線性表L=（2，3，4，6，8，9）的靜態(tài)鏈表圖示datanext0416623334142259-16857891011自測(cè)題5靜態(tài)鏈表中指針表示的是()A.下一元素的地址B.內(nèi)存儲(chǔ)器的地址C.下一元素在數(shù)組中的位置D.左鏈或右鏈指向的元素的地址【中南大學(xué)2003二.2(1分)】靜態(tài)鏈表與動(dòng)態(tài)鏈表靜態(tài)鏈表的操作和動(dòng)態(tài)鏈表相似，只是以整型游標(biāo)代替動(dòng)態(tài)指針。設(shè)以Sa表示靜態(tài)鏈表，通?？砂裇a[0]理解為“頭結(jié)點(diǎn)”，第1個(gè)元素的位置由Sa[0].next指出,用全局整型變量av指出可利用空間的下標(biāo)。初始時(shí)將整個(gè)靜態(tài)鏈表看作一個(gè)“空表”，操作中用GetNode()和FreeNode()函數(shù)模擬C中的malloc()和free()函數(shù)。以下是初始化、取結(jié)點(diǎn)和釋放結(jié)點(diǎn)3個(gè)函數(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)鏈表的申請(qǐng)結(jié)點(diǎn)空間intGetNode()/*取結(jié)點(diǎn)*/{if(av!=-1)/*-1表示無(wú)空間*/{p=av;av=Sa[av].next;}/*p為可利用空間的下標(biāo)*/returnp;}靜態(tài)鏈表的釋放結(jié)點(diǎn)空間intFreeNode(intp)/*將p歸還到可利用空間表中*/{Sa[p].next=av;av=p;returnav;}靜態(tài)鏈表的操作舉例（1）

（1）查找值為x的結(jié)點(diǎn)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第個(gè)結(jié)點(diǎn)ElemTypeLocate(SLinkedListSL,

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

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

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