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

返回主目錄

本章說明2.1線性表的類型定義2.2線性表的順序表示和實現(xiàn)2.3線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)2.4循環(huán)鏈表和雙向鏈2.5一元多項式的表示及相加

本章小結(jié)本章說明學(xué)習(xí)目標(biāo)了解線性表的邏輯結(jié)構(gòu)特性是數(shù)據(jù)元素之間存在著線性關(guān)系，在計算機(jī)中表示這種關(guān)系的兩類不同的存儲結(jié)構(gòu)是順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)。用前者表示的線性表簡稱為順序表，用后者表示的線性表簡稱為鏈表。熟練掌握這兩類存儲結(jié)構(gòu)的描述方法以及線性表的基本操作在這兩種存儲結(jié)構(gòu)上的實現(xiàn)。能夠從時間和空間復(fù)雜度的角度綜合比較線性表兩種存儲結(jié)構(gòu)的不同特點及其適用場合。結(jié)合線性表類型的定義增強(qiáng)對抽象數(shù)據(jù)類型的理解。本章說明重點和難點鏈表是本章的重點和難點。扎實的指針操作和內(nèi)存動態(tài)分配的編程技術(shù)是學(xué)好本章的基本要求，分清鏈表中指針p和結(jié)點*p之間的對應(yīng)關(guān)系，區(qū)分鏈表中的頭結(jié)點、頭指針和首元結(jié)點的不同所指以及循環(huán)鏈表、雙向鏈表的特點等。知識點線性表、順序表、鏈表、有序表線性結(jié)構(gòu)的特點：在數(shù)據(jù)元素的非空有限集中存在唯一的一個被稱做“第一個”的數(shù)據(jù)元素存在唯一的一個被稱做“最后一個”的數(shù)據(jù)元素除第一個之外，每個元素都只有一個前驅(qū)除最后一個之外，每個元素都只有一個后繼1.線性表是最常用、最簡單的一種線性數(shù)據(jù)結(jié)構(gòu)。定義：一個線性表是n個數(shù)據(jù)元素的有限序列。2.1線性表的類型定義例如：英文字母（A，B，C，……，Z）是一個線性表。表中元素是一個字母。例如：星期（星期日，星期一，星期二，……，星期六）是一個線性表。表中的數(shù)據(jù)元素是星期中一天的名稱。例如：在稍復(fù)雜的線性表中，一個數(shù)據(jù)元素可以是由若干個數(shù)據(jù)項組成的記錄，含有大量記錄線性表稱為文件。如，一個學(xué)校的學(xué)生健康情況登記表。姓名學(xué)號性別年齡班級健康狀況王小林790631男18計91健康陳紅790632女20計91一般劉建平790633男21計91健康張立立790634男17計91神經(jīng)衰弱┆┆┆┆┆┆數(shù)據(jù)元素2.線性表的結(jié)構(gòu)特性

線性表是n≥0個數(shù)據(jù)元素a1，a2，…，ai-1，ai，ai+1，…，an的有限序列。一個線性表中的數(shù)據(jù)元素是屬于同一數(shù)據(jù)對象，相鄰數(shù)據(jù)元素之間存在著序偶關(guān)系。(同構(gòu)元素）可將線性表記為（a1,…,ai-1,ai,ai+1,…an）。ai-1是ai的直接前驅(qū)元素，ai+1是ai的直接后繼元素。

a1無直接前驅(qū)，an無直接后繼。i是數(shù)據(jù)元素ai在線性表中的位序。線性表的長度定義為線性表中數(shù)據(jù)元素的個數(shù)n。當(dāng)n=0時，為空表。2.1線性表的類型定義3.線性表的基本運(yùn)算表的初始化求表長?。ɑ蛐薷模┍碇械慕Y(jié)點查找結(jié)點插入結(jié)點刪除結(jié)點不是全部操作，不同的問題需要的操作不同。2.1線性表的類型定義4.抽象數(shù)據(jù)類型線性表的定義P19

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=1,2,…,n}

基本操作：

InitList(&L)//創(chuàng)建一個空的線性表LDestroyList(&L)//撤消L2.1線性表的類型定義ClearList(&L)//將L重置為空表

ListEmpty(L)//判L是否為空?空為TListLength(L)//返回表長度(元素個數(shù))GetElemList(L,i,&e)//用e返回L中第i個數(shù)據(jù)元素的個數(shù)2.1線性表的類型定義4.抽象數(shù)據(jù)類型線性表的定義P19

例2-1兩個線性表LA、LB，將存在于線性表LB中而不在LA中的數(shù)據(jù)元素加入到線性表LA中。即LA=LA∪LB算法思想：逐一取出LB中的元素，判斷是否在LA中，若不在,則插入之。僅已知LA、LB

（1）先求出LA、LB長度（2）若LB未取空，取LB中一元素=>e，若LB取空則轉(zhuǎn)（4）（3）如e不在LA中，則插入到LA中，轉(zhuǎn)（2）（4）結(jié)束2.1線性表的類型定義voidunin(List&La，ListLb){La_len=(ListLength(La));Lb_len=(ListLength(Lb));for(i=1;i<=Lb_len;i++){GetElem(Lb,i,&e);//取LB中第i個元素

if(!LocateElem(La,e,equal))ListInsert(&La,++La_len,e); }//La中不存在和e相同的元素，則插入之}//union算法的時間復(fù)雜度：O(ListLength(LA)×ListLength(LB))算法2.1實現(xiàn)求表長、插入、取元素時間復(fù)雜度：O(1)2.1線性表的類型定義例2-2線性表LA和LB是非遞減有序的，將兩表合并成新的線性表LC，且LC也是非遞減的。算法思想：將LA、LB兩表中的元素逐一按序加入到一個新表LC中。即（1）LA、LB均不空，則在LA中取一元素=>a,LB中取一元素=>b,否則轉(zhuǎn)（3）（2）若a<=b,a=>c,否則b=>c,轉(zhuǎn)（1）（3）若LA不空，則LA剩余部分放到LC尾（4）若LB不空，則LA剩余部分放到LC尾voidMergeList(ListLa,ListLb,List&Lc){InitList(Lc);//建一空表LCi=j=1;k=0;//i，j，k分別指向La，Lb，Lc

初始位置算法2.22.1線性表的類型定義La_len=(ListLength(La));Lb_len=(ListLength(Lb));while(i<=La_len)&&(j<=Lb_len){//La和Lb均非空

GetElem(La,i,ai);GetElem(Lb,j,bj);if(ai<=bj){ListInsert(Lc,++k,ai);++i;}else{ListInsert(Lc,++k,bj);++j;}}算法2.22.1線性表的類型定義while(i<=La_len)//La還有元素

{GetElem(La,i++,ai);ListInsert(Lc,++k,ai);}while(j<=Lb_len)//Lb還有元素

{GetElem(Lb,j++,bj);ListInsert(Lc,++k,bj);}}//MergeList時間復(fù)雜度：(ListLength(LA)+ListLength(LB))2.1線性表的類型定義2.2線性表的順序表示和實現(xiàn)3.線性表的動態(tài)分配順序存儲結(jié)構(gòu)4.順序線性表的操作2.順序表的特點1.線性表的順序表示5.順序表的優(yōu)缺點用一組地址連續(xù)的存儲單元存儲一個線性表的數(shù)據(jù)元素，稱為順序表。用一維數(shù)組表示元素地址計算方法：

元素存儲位置：LOC(ai+1)=LOC(ai)+L一般存儲位置：LOC(ai)=LOC(a1)+(i-1)*L其中：L—一個元素占用的存儲單元個數(shù)

LOC(ai)—線性表第i個元素的地址實現(xiàn)：可用C語言的一維數(shù)組實現(xiàn)2.2線性表的順序表示和實現(xiàn)a1a2an01n-112n內(nèi)存V數(shù)組下標(biāo)元素序號M-1typedefintDATATYPE;#defineM1000DATATYPEdata[M];例typedefstructcard{intnum;charname[20];charauthor[10];charpublisher[30];floatprice;}DATATYPE;DATATYPElibrary[M];空閑空間數(shù)據(jù)元素不是簡單類型時,可定義結(jié)構(gòu)體數(shù)組或動態(tài)申請和釋放內(nèi)存DATATYPE*pData=(DATATYPE*)malloc(M*sizeof(DATATYPE));free(pData);2.順序表的特點特點：實現(xiàn)邏輯上相鄰—物理地址相鄰

實現(xiàn)隨機(jī)存取2.2線性表的順序表示和實現(xiàn)3.線性表的動態(tài)分配順序存儲結(jié)構(gòu)用一維數(shù)組定義一個線性表#defineLIST_INIT_SIZE100#defineLISTINCREAMENT10typestruct{ElemType*elem;//指向線性表起始地址的指針

intlength;//線性表實際存放數(shù)據(jù)長度

intlistsize;//線性表申請長度

}SqList2.2線性表的順序表示和實現(xiàn)4.順序線性表的操作順序表容易實現(xiàn)訪問操作，可隨機(jī)存取元素。但插入和刪除操作主要是移動元素。(1)初始化操作算法思想：構(gòu)造一個空表。設(shè)置表的起始位置表長可用空間2.2線性表的順序表示和實現(xiàn)線性表初始化算法2.3StatusInitList_Sq(SqList&L){L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType)); If(!L.elem)exit(OVERFLOW); L.length=0;L.listsize=LIST_INIT_SIZE; ReturnOK;}//InitList_Sq2.2線性表的順序表示和實現(xiàn)（2）插入定義：線性表的插入是指在第i（1

i

n+1）個元素之前插入一個新的數(shù)據(jù)元素x，使長度為n的線性表

變成長度為n+1的線性表

需將第i至第n共（n-i+1)個元素后移算法時間復(fù)雜度T(n)內(nèi)存a1a2aiai+1an01i-1V數(shù)組下標(biāo)n-1in12i元素序號i+1nn+1內(nèi)存a1a2aiai+1an01i-1V數(shù)組下標(biāo)n-1in12i元素序號i+1nn+1an-1xX插入算法2.4

（在表L中的第i個元素之前插入e），見P24①判i值的合法性，1≤i≤表長+1；②判表的空間滿否？若滿則增加分配（動態(tài)分配）；③從表元素n到i，依次后移一個位置；④將e插入第i個位置，表長度增1。＊算法中定義的線性表是L，以結(jié)構(gòu)形式出現(xiàn)2.2線性表的順序表示和實現(xiàn)插入算法2.4時間復(fù)雜度T(n)

可見插入元素的時間主要花費(fèi)在移動元素上，而移動元素的個數(shù)主要取決于插入的位置。

設(shè)pi是在第i個元素之前插入一個元素的概率，則在長度為n的線性表中插入一個元素時需移動元素的平均次數(shù)為若在任何位置上插入元素都是等概率2.2線性表的順序表示和實現(xiàn)

在順序表中插入一個元素時，平均移動表的一半元素，當(dāng)n很大時，效率很低。（3）刪除

算法思想：刪除第i個元素，將第（i+1）至第n個元素逐一向前移動一個位置，將長度為n

變成長度為n-1=>n的線性表

需將第i+1至第n個，共（n-i)個元素前移算法算法時間復(fù)雜度內(nèi)存a1a2aiai+1an01i-1V數(shù)組下標(biāo)n-1i12i元素序號i+1n內(nèi)存a1a2ai+201i-1V數(shù)組下標(biāo)n-1i12i元素序號i+1nanai+1刪除在表L中刪除第i個元素，放入e，見P24①判i值的合法性，1≤i≤表長n②取第i個元素，放入e③從i+1到表長n，依次前移④表長度減1刪除算法2.5思想2.2線性表的順序表示和實現(xiàn)刪除算法2.5時間復(fù)雜度

可見刪除元素的時間主要花費(fèi)在移動元素上，而移動元素的個數(shù)主要取決于刪除的位置。

設(shè)qi是刪除第i個元素的概率，則在長度為n的線性表中刪除一個元素所需移動的元素次數(shù)的平均次數(shù)為若在任何位置上插入元素都是等概率2.2線性表的順序表示和實現(xiàn)

在順序表中刪除一個元素時，平均移動表的一半元素，當(dāng)n很大時，效率很低。5.順序表的的優(yōu)缺點優(yōu)點邏輯相鄰，物理相鄰可隨機(jī)存取任一元素存儲空間使用緊湊缺點插入、刪除操作需要移動大量的元素預(yù)先分配空間需按最大空間分配，利用不充分表容量難擴(kuò)充2.2線性表的順序表示和實現(xiàn)2.3線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)

1.特點用一組任意的存儲單元存儲線性表的數(shù)據(jù)元素利用指針實現(xiàn)了用不相鄰的存儲單元存放邏輯上相鄰的元素每個數(shù)據(jù)元素ai，除存儲本身信息外，還需存儲其直接后繼的信息（指針），用來表示線性表數(shù)據(jù)元素的邏輯關(guān)系結(jié)點

數(shù)據(jù)域：元素本身信息指針域：指示直接后繼的存儲位置數(shù)據(jù)域指針域結(jié)點ZHAOQIANSUNLIZHOUWUZHENGWANG^H例線性表(ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG)43131NULL3771925數(shù)據(jù)域指針域LIQIANSUNWANGWUZHAOZHENGZHOU存儲地址1713192531374331H頭指針數(shù)據(jù)之間的邏輯關(guān)系由結(jié)點中的指針指示最后結(jié)點2.線性鏈表的定義由n個結(jié)點鏈結(jié)成一個鏈表，稱為線性鏈表或單鏈表。結(jié)點（Node）、數(shù)據(jù)域、指針域、指針、鏈、頭指針3.線性鏈表的實現(xiàn)

typedefstructLnode{ElemTypedata;structLnode*next;}Lnode,*LinkList;2.3線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)LNode*L,*p;(*p)表示p所指向的結(jié)點p->data表示p指向結(jié)點的數(shù)據(jù)域p->next表示p指向結(jié)點的指針域生成一個LNode型新結(jié)點：p=(LNode*)malloc(sizeof(LNODE));系統(tǒng)回收p結(jié)點：free(p)帶頭結(jié)點非空表：空表：datanextp結(jié)點（*p）a1a2an/\…L/\L2.3線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)4.鏈?zhǔn)酱鎯Y(jié)構(gòu)的優(yōu)點插入、刪除操作是不再需要移動大量的元素，但失去了順序表的可隨機(jī)存取特點。5.單鏈表的操作取第i個元素（算法2.8）算法思想：單鏈表是非隨機(jī)存取結(jié)構(gòu)。每個元素的位置信息都包含在前驅(qū)結(jié)點的信息中，所以取得第i個元素必須從頭指針出發(fā)尋找。設(shè)置一個指針變量指向第一個結(jié)點，然后，讓該指針變量逐一向后指向，直到第i個元素。2.3線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)StatusGetElem_L(LinkListL,inti,ElemType){ //L為帶頭結(jié)點的單鏈表的頭指針。

//當(dāng)?shù)趇個元素存在時，其值賦給e并返回OK，否則返回ERROR p=L→next;//p指向第1個結(jié)點，j做計數(shù)器

j=1; while(p&&j<i)//直到p指向第i元素或p為空

{p=p→next;++j;} e=p→data; returnOK;}//GetElem_L取結(jié)點算法實現(xiàn)2.3線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)要求：在帶頭結(jié)點的單鏈表L中第i個位置之前插入元素e（即在數(shù)據(jù)元素a和b之間插入元素e）算法思想：設(shè)p為指向頭結(jié)點的指針，s為指向結(jié)點e的指針先找到第i-1個位置（即p指向元素a的位置）生成新結(jié)點然后插入:修改s、p的指針決定a和b之間的相鄰關(guān)系是由a的指針決定的。若要實現(xiàn)插入，生成e結(jié)點，然后讓a的指針指向e且e的指針指向b。實現(xiàn)三個元素a、e和b的邏輯關(guān)系。插入結(jié)點算法2.92.3線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)EsB…A…ps->next=p->nextp->next=sXsB…A…p可否交換兩個指針的修改次序？La1a2頭結(jié)點an^…...0pj=0pj=n非法插入情況：i>表長:j<i-1,p=nulli<1:即i=0,-1,-2…..,j>i-1StatusListInsert_L(ListLInk&L,inti,ElemTypee){//在帶頭結(jié)點的單鏈表L中第i個位置之前插入元素e p=L;j=0; while(p&&j<i-1){p=p→next;++j;}//找第i-1結(jié)點

if(!p||j>i-1)returnERROR;//i小于1或大于表長

s=(LinkList*)malloc(sizeof(LNode)); s→data=e;s→next=p-next; p→next=s; returnOK;}//ListInsert_L 插入結(jié)點算法2.9實現(xiàn)2.3線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)BC…A…pC…A…p刪除操作p->next=p->next->next刪除結(jié)點算法2.10實現(xiàn)StatusListDelete_L(LinkList&L,inti,ElemType&e){//在帶頭結(jié)點的單鏈表L中刪除第i個元素，并由e返回

p=L;j=0;while(p->next&&j<i-1){p=p->next;++j;}//尋找第i個結(jié)點，并令p指向其前驅(qū)第i-1結(jié)點

if(!p->next)||j>i-1)returnERROR;//i>表長||i<1q=p->next;p->next=q->next;e=q->data;free(q);returnOK;}//ListDelete_L2.3線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)動態(tài)創(chuàng)建鏈表算法算法思想：設(shè)線性表n個元素，逆位序輸入數(shù)據(jù)元素建立一個單鏈表，h為頭指針。h頭結(jié)點an^0h頭結(jié)點an-10an^a2…...h頭結(jié)點an-10an^ha1a2頭結(jié)點an^…...0h頭結(jié)點0^動態(tài)創(chuàng)建鏈表算法2.11實現(xiàn)VoidCreateList_L(LinkList&L,intn){//逆位序輸入n個元素值，建立帶頭結(jié)點的單鏈表LL=（LinkList*)malloc(sizeof(LNode));L->next=NULL;for(i=n;i>0;--i){p=(LinkList*)malloc(sizeof(LNode));scanf(&p->data);p->next=L->next;L->next=p;}}//CreatList_L2.3線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)例：將兩個有序鏈表合并為一個有序鏈表。算法思想設(shè)立三個指針pa、pb和pc分別用來指向兩個有序鏈表和合并表的當(dāng)前元素。比較兩個表的當(dāng)前元素的大小，將小的元素鏈接到合并表Lc中,讓合并表的當(dāng)前指針指向該元素，然后，修改指針。在歸并兩個鏈表為一個鏈表時，不需要另建新表的結(jié)點空間，而只需將原來兩個鏈表中結(jié)點之間的關(guān)系解除，重新建立關(guān)系。合并有序鏈表算法2.122.3線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)3511/\La8152620/\8911LbLcpbpapcpc-next=pbpc->next=papbpcpapcpapcpbpcpapcpbpcpbpcpapc每次鏈接pa或pb的一個結(jié)點后，便做如下操作：

pa=pa->next;pc=pc->next;pa和pc分別后移一個位置或pb=pb->next;pc=pc->next;pb和pc分別后移一個位置合并有序鏈表算法2.12實現(xiàn)VoidMergeList_L(LinkListLa,LinkListLb,LinkList&Lc){pa=La->next;pb=Lb->next;Lc=pc=La;while(pa&&pb){if(pa->data<=pb->data){pc->next=pa;pc=pa;pa=pa->next;}else{pc->next=pb;pc=pb;pb=pb->next;}}pc->next=pa?pa:pb;free(Lb);}//MergeList_L2.3線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)單鏈表特點它是一種動態(tài)結(jié)構(gòu)，整個存儲空間為多個鏈表共用。不需預(yù)先分配空間。指針占用額外存儲空間。不能隨機(jī)存取，查找速度慢。插入、刪除操作的速度快。2.3線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)6.靜態(tài)單鏈表有些高級語言沒有指針，我們可以用數(shù)組來表示單鏈表，在數(shù)組中以整型游標(biāo)來代替指針。這種用數(shù)組描述的鏈表稱為靜態(tài)鏈表。存儲結(jié)構(gòu)：

#defineMAXSIZE1000typedefstruct{ ElemTypedata; intcur;}component,SLinklist[MAXSIZE];S[i].cur指示第i+1個結(jié)點的位置。靜態(tài)鏈表的操作和動態(tài)鏈表相似，以整型游標(biāo)代替動態(tài)指針。2.3線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)011ZHAO22QIAN33SUN44LI55ZHOU66WU77ZHENG88WANG0910011ZHAO22QIAN33SUN44LI55ZHOU66WU77ZHENG88WANG0910SHI9S[0].cur為頭指針，可以遍歷整個靜態(tài)鏈表找到插入位置i011ZHAO22QIAN33SUN44LI55ZHOU66WU87ZHENG88WANG09SHI510SHI85刪除ZHENG,s[6].cur=s[7].curintLocateElem_SL(SLinkListS,ElemTypee){//在靜態(tài)單鏈線性表L中查找第1個值為e的元素

//找到返回位序，否則返回0i=S[0].cur;while(i&&S[i].data!=e)i=S[i].cur;returni;//沒找到則到鏈尾，i=0}//LocateElem_SL算法2.13靜態(tài)鏈表查找2.3線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)假設(shè)由終端輸入A集合元素并建立靜態(tài)鏈表S，然后輸入集合B元素在S中查找，若存在和B相同的元素，則從S中刪除之，否則插入到S中。算法思想：將整個數(shù)組空間初始化成一個鏈表從備用空間取得一個結(jié)點將空閑結(jié)點鏈接到備用鏈表上例2-3運(yùn)算(A-B)U(B-A)2.3線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)01122334455667788991010003122c0344556677089910100Space[0].cur是備用空閑鏈表的頭指針，space[1].cur是鏈表的頭指針A=(c,b,e,g,f,d),B=(a,b,n,f)。即0、1下標(biāo)不存放數(shù)據(jù)初始化后04122c33b0455667708991010005122c33b44e05667788991010006122c33b44e55g0677889910100Space[0].cur是備用空閑鏈表的頭指針，space[1].cur是鏈表的頭指針A=(c,b,e,g,f,d),B=(a,b,n,f)07122c33b44e55g66f07889910100A=(c,b,e,g,f,d),B=(a,b,n,f)取B中元素在A中查找，若有與其相同的，則將A中的同元素刪除，若沒有則在A中插入08122c33b44e55g66f77d089910100A輸入結(jié)束09122c33b44e55g66f77d88a091010003122c43b94e55g66f77d88a0910100刪b,space[2].cur取a，在A中找，沒有插入A=(c,b,e,g,f,d),B=(a,b,n,f)取B中元素在A中查找，若有與其相同的，則將A中的同元素刪除，若沒有則在A中插入03122c43b94e55g66f77d88a091010009122c43n04e55g66f77d88a391010006122c43n04e55g76f97d88a3910100插入n，space[0].data=e;刪除f，space[5].cur=space[6].curvoidInitSpace_SL(SLinkList&space){//將一維數(shù)組space中各分量鏈成一個備用鏈表

//space[0].cur為頭指針，0表示空指針

for(i=0;i<MAXSIZE-1;++i)space[i].cur=i+1;space[MAXSIZE-1].cur=0;}//InitSpace_SLintMalloc_SL(SLinkList&space){i=space[0].cur;//返回分配結(jié)點的下標(biāo)，有空閑的

if(space[0].cur)space[0].cur=space[i].cur;returni;}//Malloc_SL算法2.142.15靜態(tài)鏈表初始化2.3線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)voidFree_SL(SLinkList&space,intk){//將下標(biāo)為k的空閑結(jié)點回收到備用鏈表

space[k].cur=space[0].cur;space[0].cur=k;}//Free_SL(2.16)voiddifferece(SLinkList&space,int&S){//依次輸入集合A和B，在space中建立靜態(tài)鏈表，S為頭指針

//設(shè)space的備用空間足夠大，space[0].cur為其頭指針，

InitSpace_SL(space);//初始化備用空間

S=Malloc_SL(space);//生成S頭結(jié)點，分配下標(biāo)1r=S;scanf(m,n);//r指向表尾元素，輸入A,B元素個數(shù)算法2.162.17靜態(tài)鏈表初始化2.3線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)for(j=1;j<=m;++j){//建立集合A的鏈表

i=Malloc_SL(space);//分配結(jié)點，i為結(jié)點下標(biāo)

scanf(space[i].data);space[r].cur=i;r=i;//插入到表尾，r指向新表尾

}//forspace[r].cur=0;//創(chuàng)建結(jié)束，表尾的指針為空

for(j=1;j<=n;++j){//輸入B元素，在插入否則刪除

scanf(b);p=S;k=space[S].cur;//k指向集合A中第一個結(jié)點算法2.17續(xù)2.3線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)while(k!=space[r].cur&&space[k].data!=b){p=k;k=space[k].cur;}//在當(dāng)前表中查找

if(k==space[r].cur{i=Malloc_SL(space);space[i].data=b;space[i].cur=space[r].cur;space[r].cur=i；r=i;}//ifelse{space[p].cur=space[k].cur;Free_SL(space,k);if(r==k)r=p;}//else}//for}//difference算法2.17續(xù)2.3線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)2.4循環(huán)鏈表和雙向鏈表

1.循環(huán)鏈表：循環(huán)鏈表是表中最后一個結(jié)點的指針指向頭結(jié)點，使鏈表構(gòu)成環(huán)狀特點：從表中任一結(jié)點出發(fā)均可找到表中其他結(jié)點，提高查找效率操作與單鏈表基本一致，判表尾條件不同單鏈表p或p->next=NULL循環(huán)鏈表p或p->next=H

非空表空表HH2.雙向鏈表在雙向鏈表的結(jié)點中有兩個指針域，分別指向前驅(qū)和后繼。雙向鏈表也可以有循環(huán)鏈表。雙向鏈表的存儲結(jié)構(gòu)

typedefstructDuLNode{ElemTypedata;structDuLNode*prior;structDuLNode*next;}DuLNode,*DuLinklist;priordatanext2.4循環(huán)鏈表和雙向鏈表

L空雙向循環(huán)鏈表：非空雙向循環(huán)鏈表：Labbcapp->prior->next=p=p->next->proir;雙向鏈表的操作雙指針使得鏈表的雙向查找更為方便、快捷NextElem和PriorElem的執(zhí)行時間為O(1)僅需涉及一個方向的指針的操作和線性鏈表的操作相同插入和刪除需同時修改兩個方向的指針2.4循環(huán)鏈表和雙向鏈表

Hab插入算法：在表L中第i個位置之前插入元素e設(shè)P指針，p=GetElemP-DuL(L,i)，使其指向第i個結(jié)點p

若p=null，則i不存在；p<>null，則為e申請結(jié)點,e賦值xs

插入

s->prior=p->prior

p->prior->next=s

s->next=pp->prior=s算法實現(xiàn)2.18思考：四個指針的修改順序可否任意改變？刪除算法：刪除表L中第i個元素，賦于e。P37算法2．19

設(shè)P指針，p=GetElemP-DuL(L,i)，使其指向第i個結(jié)點pp=null，則i不存在；若p<>null，p指向第i個結(jié)點，將其賦給e

刪除

p->prior->next=p-nextp->next->prior=p->priorHbca算法實現(xiàn)算法評價：T(n)=O(1)2.19與單鏈表相同2.5一元多項式的表示及相加

可用線性表P表示

但對S(x)這樣的多項式浪費(fèi)空間

一般

其中

用數(shù)據(jù)域含兩個數(shù)據(jù)項的線性表表示其存儲結(jié)構(gòu)可以用順序存儲結(jié)構(gòu)，也可以用單鏈表一元多項式的表示coefexpnext一元多項式相加單鏈表的結(jié)點定義TypedefstructPnode{floatcoef;intexpn;structPnode*next;}term,ElemType;-1A70517^3198-98^22781-1B-1C70517^111227和存放在A鏈中設(shè)p,q分別指向A,B中某一結(jié)點，p,q初值是第一結(jié)點比較p->exp與q->expp->exp<q->exp:p結(jié)點是和多項式中的一項

p后移,q不動p->exp>q->exp:q結(jié)點是和多項式中的一項將q插在p之前,q后移,p不動p->exp=q->exp:

系數(shù)相加0：從A表中刪去p,

釋放p,q，p,q后移

0：修改p系數(shù)域,

釋放q，p,q后移直到p或q為NULL

若q==NULL，結(jié)束

若p==NULL，將B中剩余部分連到A上即可運(yùn)算規(guī)則釋放B的表頭q-1pa703198517^-1pb81227-98^ppreq-1pa703198517^-1pb81227-98^ppreq-1pa7011198517^-1pb81227-98^ppreq=NULL-1pa7011198517^-1pb81227-98^ppreq-1pa7011198517^-1pb81227-98^ppreq=NULL-1pa7011198517^-1pb81227-98^ppre-1pa70111227517^算法描述2.20本章小結(jié)線性表是n(n≥0)個數(shù)據(jù)元素的序列，通常寫成

（a1,…,ai-1,ai,ai+1,…an）線性表中除了第一個和最后一個元素之外，都只有一個前驅(qū)和一個后繼。線性表中每個元素都有自己確定的位置，即“位序”。n=0時的線性表稱為“空表”，在寫線性表的操作算法時一定要考慮你的算法對空表的情況是否也正確。順序表是線性表的順序存儲結(jié)構(gòu)的一種別稱。特點是以“存儲位置相鄰”表示兩個元素之間的前驅(qū)、后繼關(guān)系。優(yōu)點是可以隨機(jī)存取表中任意一個元素。缺點是每作一次插入或刪除操作時，平均來說必須移動表中一半元素。常應(yīng)用于主要是為查詢而很少作插入和刪除操作，表長變化不大的線性表。本章小結(jié)鏈表是線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)的別稱。特點：是以“指針”指示后繼元素，因此線性表的元素可以存儲在存儲器中任意一組存儲單元中。優(yōu)點：是便于進(jìn)行插入和刪除操作。缺點：是不能進(jìn)行隨機(jī)存取，每個元素的存儲位置都存放在其前驅(qū)元素的指針域中，為取得表中任意一個數(shù)據(jù)元素都必須從第一個數(shù)據(jù)元素起查詢。由于它是一種動態(tài)分配的結(jié)構(gòu)，結(jié)點的存儲空間可以隨用隨取，并在刪除結(jié)點時隨時釋放，以便系統(tǒng)資源更有效地被利用。這對編制大型軟件非常重要，作為一個程序員在編制程序時必須養(yǎng)成這種習(xí)慣。本章小結(jié)基礎(chǔ)知識題描述以下三個概念的區(qū)別：頭指針，頭結(jié)點，首元結(jié)點(第一個元素結(jié)點)。簡述線性表的兩種存儲結(jié)構(gòu)順序表和鏈表的優(yōu)缺點。已知L是無表頭結(jié)點的單鏈表，且P是指向表中某個結(jié)點的指針，試寫出在P所指結(jié)點之前插入指針S所指結(jié)點的語句序列。已知P是指向雙向鏈表中某個結(jié)點的指針，試寫出刪除P所指結(jié)點的前驅(qū)結(jié)點的語句序列。簡述以下算法的功能。

(1)StatusA(LinkedListL){//L是無表頭結(jié)點的單鏈表

if(L&&L->next){

Q=L;L=L->next;P=L;

while(P->next)P=P->next;

P->next=Q;Q->next=NULL;

}

returnOK;

}//A

(2)voidBB(LNode*s,LNode*q){

p=s;

while(p->next!=q)p=p->next;

p->next=s;

}//BB

voidAA(LNode*pa,LNode*pb){

//pa和pb分別指向單循環(huán)鏈表中的兩個結(jié)點

BB(pa,pb);

BB(pb,pa);

}//AA基礎(chǔ)知識題1.設(shè)順序表

a中的數(shù)據(jù)元素遞增有序。試寫一算法，將x插入到順序表的適當(dāng)位置上，以保持該表的有序性。

voidInsertOrderList(SqList&a,ElemTypex)

//已知順序表a中的數(shù)據(jù)元素遞增有序，將x插入到順序表的適當(dāng)位置上，以保持該表的有序性。2.設(shè)A=(,…,)和B=(,…,)均為順序表，A'和B'分別為A和B中除去最大共同前綴后的子表（例如，A=(x,y,y,z,x,z)，B=(x,y,y,z,y,x,x,z)，則兩者中最大的共同前綴為(x,y,y,z)，在兩表中除去最大共同前綴后的子表分別為A'=(x,z)和B'=(y,x,x,z)）。若A'=B'=空表，則A=B；若A'=空表，而B'≠空表，或者兩者均不為空表，且A'的首元小于B'的首元，則A<B；否則A>B。試寫一個比較A、B大小的算法。（請注意：在算法中，不要破壞原表A和B，并且，也不一定先求得A'和B'才進(jìn)行比較）

charCompare(SqListA,SqListB)

//已知順序表A和B,返回'<'(若'A<B')或'='(若'A=B')或'>'(若'A>B')編程題3.已知線性表中的元素以值遞增有序排列，并以單鏈表作存儲結(jié)構(gòu)。試寫一高效的算法，刪除表中所有值大于mink且小于maxk的元素(若表中存在這樣的元素)同時釋放被刪結(jié)點空間。（注意：mink和maxk是給定的兩個參數(shù)值，它們的值可以和表中的元素相同，也可以不同）

voiddel_between_mink_and_maxk(LinkList&hlink,ElemTypemink,ElemTypemaxk)

//hlink為指向單鏈表頭結(jié)點的指針，刪除鏈表中其值介于mink和maxk之間的結(jié)點。4.試寫一算法，實現(xiàn)順序表的就地逆置，即利用原表的存儲空間將線性表(a1,…,an)逆置為(an,an