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

第二章線性表2.1線性表的類型定義2.2線性表的順序表示與實(shí)現(xiàn)2.3線性表的鏈?zhǔn)奖硎九c實(shí)現(xiàn)2.4一元多項(xiàng)式的表示及相加學(xué)習(xí)目標(biāo)了解線性表的邏輯結(jié)構(gòu)特性是數(shù)據(jù)元素之間存在著線性關(guān)系。在計(jì)算機(jī)中表示這種關(guān)系的兩類不同的存儲結(jié)構(gòu)是順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)。熟練掌握這兩類存儲結(jié)構(gòu)的描述方法以及線性表的基本操作在這兩種存儲結(jié)構(gòu)上的實(shí)現(xiàn)。能夠從時(shí)間和空間復(fù)雜度的角度綜合比較線性表兩種存儲結(jié)構(gòu)的不同特點(diǎn)及其適用場合。結(jié)合線性表類型的定義增強(qiáng)對抽象數(shù)據(jù)類型的理解。重點(diǎn)難點(diǎn)鏈表指針操作和內(nèi)存動態(tài)分配的編程技術(shù)；鏈表中指針p和結(jié)點(diǎn)*p之間的對應(yīng)關(guān)系；頭結(jié)點(diǎn)、頭指針和首元結(jié)點(diǎn)的不同；循環(huán)鏈表、雙向鏈表的特點(diǎn)。線性結(jié)構(gòu)的特點(diǎn)在數(shù)據(jù)元素的非空有限集中存在唯一一個(gè)被稱做“第一個(gè)”的數(shù)據(jù)元素；存在唯一一個(gè)被稱做“最后一個(gè)”的數(shù)據(jù)元素；除第一個(gè)數(shù)據(jù)元素之外，每個(gè)元素都只有一個(gè)前驅(qū)；除最后一個(gè)數(shù)據(jù)元素之外，每個(gè)元素都只有一個(gè)后繼。

§2.1線性表的類型定義線性表：是n個(gè)數(shù)據(jù)元素的有限序列。除了第一個(gè)元素沒有直接前驅(qū)和最后一個(gè)元素沒有直接后繼之外，其余的每個(gè)數(shù)據(jù)元素只有一個(gè)直接前驅(qū)和一個(gè)直接后繼。例數(shù)據(jù)元素線性表的特征有窮性：由有限個(gè)元素組成，元素個(gè)數(shù)n—表長度，n=0空表。設(shè)線性表為(a1，a2,...，ai，...，an),稱i為ai

在線性表中的位序。有序性：線性表元素之間存在序偶關(guān)系，1<i<n時(shí)ai的直接前驅(qū)是ai-1，a1無直接前驅(qū)ai的直接后繼是ai+1，an無直接后繼同一性：線性表由同類數(shù)據(jù)元素組成，每一個(gè)元素都屬于同一數(shù)據(jù)對象線性表抽象數(shù)據(jù)類型定義：ADT

List{數(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}基本操作：（1）InitList（&L）操作結(jié)果：將L初始化為空表。（2）DestroyList(&L)初始條件：線性表L已存在。操作結(jié)果：將L銷毀。（3）ClearList(&L)初始條件：線性表L已存在。操作結(jié)果：將表L置為空表。（4）EmptyList（L）初始條件：線性表L已存在。操作結(jié)果：如果L為空表則返回真，否則返回假。（5）ListLength（L）初始條件：線性表L已存在。操作結(jié)果：如果L為空表則返回0，否則返回表中的元素個(gè)數(shù)。（6）GetItem(L,i,&e)初始條件：表L已存在，1<=i<=ListLength(L)。操作結(jié)果：用e返回L中第i個(gè)元素的值。（7）LocateElem(L,e)初始條件：表L已存在，e為合法元素值。操作結(jié)果：如果L中存在元素e，則將“當(dāng)前指針”指向第一個(gè)這樣的元素e所在位置并返回真，否則返回假。（8）ListInsert(&L,i,e)初始條件：表L已存在，e為合法元素值且1≤i≤ListLength(L)+1。操作結(jié)果：在L中第i個(gè)位置之前插入新的數(shù)據(jù)元素e，L的長度加1。（9）ListDelete(&L,i,&e)初始條件：表L已存在且非空，1≤i≤ListLength(L)。初始條件：刪除L的第i個(gè)數(shù)據(jù)元素，并用e返回其值，L的長度減1。}ADT

List利用上述定義的線性表類型，可以實(shí)現(xiàn)其它更復(fù)雜的操作，例如：歸并、拆分、復(fù)制、排序算法舉例：例2-1假設(shè)有兩個(gè)集合A和B分別用兩個(gè)線性表LA和LB表示（即：線性表中的數(shù)據(jù)元素即為集合中的成員），現(xiàn)要求一個(gè)新的集合A＝A∪B。要求對線性表作如下操作：擴(kuò)大線性表LA，將存在于線性表LB中而不存在于線性表LA中的數(shù)據(jù)元素插入到線性表LA中去。(注：∪——并集，屬于A或者屬于B)思路：

1．從線性表LB中依次取得每個(gè)數(shù)據(jù)元素;GetElem(LB,i)→e2．依值在線性表LA中進(jìn)行查訪;

LocateElem(LA,e,equal())3.若不存在，則插入之。

ListInsert(LA,n+1,e)算法實(shí)現(xiàn)：voidunion(List&La,ListLb){//將所有在線性表Lb中但不在La中的數(shù)據(jù)元素插入到La中

La_len=ListLength(La);Lb_len=ListLength(Lb);//求線性表的長度

for(i=1;i<=Lb_len;i++){GetElem(Lb,i,e);//取Lb中第i個(gè)數(shù)據(jù)元素賦給e

if(!LocateElem(La,e,equal())

ListInsert(La,++La_len,e);//La中不存在和e相同的數(shù)據(jù)元素，則插入之

}}算法舉例：例2-2歸并兩個(gè)“其數(shù)據(jù)元素按值非遞減有序排列”的有序表La

和Lb，求得有序表Lc

也具有同樣特性。問題分析：La=(a1,…,ai,…,an),Lb=(b1,…,bj,…,bm),Lc=(c1,…,ck,…,cm+n)且已由(a1,…,ai-1)和(b1,…,bj-1)歸并得(c1,…,ck-1)k=1,2,…,m+n算法基本思路初始化Lc

為空表；分別從La和Lb中取得當(dāng)前元素ai

和bj；GetElem(La,i,ai);GetElem(Lb,j,bj);

若ai≤bj，則將ai插入到Lc

中，否則將bj

插入到Lc

中；ListInsert(Lc,++k,ai);ListInsert(Lc,++k,bj);重復(fù)2和3兩步，直至La

或Lb

中元素被取完為止；將La

表或Lb表中剩余元素復(fù)制插入到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)){//La和Lb均非空

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,bj);}}//MergeList算法的時(shí)間復(fù)雜度：O(ListLength(La)+ListLength(Lb)）

2.2線性表的順序表示和實(shí)現(xiàn)

——順序映象線性表的順序存儲是指用一組地址連續(xù)的存儲單元依次存儲線性表中的各個(gè)元素。203145342535

123456

data用物理位置來表示邏輯結(jié)構(gòu)。

LOC(ai+1)=LOC(ai)+l;LOC(ai)=LOC(a1)+(i-1)*l

特點(diǎn)：是一種隨機(jī)存取的存儲結(jié)構(gòu)，只要確定了起始位置，就可以訪問表中的任何一個(gè)元素。2012334535542365767812345678910llllllllllLOC(ai)=LOC(ai-1)+l=arr+(i-1)*larr+(i-1)*larr線性表順序存儲結(jié)構(gòu)的

——C語言定義#define

LIST_INIT_SIZE100#defineLISTINCREAMENT10typedef

struct{ElemType

*elem；

/*線性表占用的數(shù)組空間。*/

int

length；

/*線性表的長度*/

intlistsize；

/*當(dāng)前分配的存儲容量(以sizeof(ElemType)為單位)/*

}SqList；

elemlengthlistsizeSqListElemType順序線性表的操作

順序表容易實(shí)現(xiàn)訪問操作，可隨機(jī)存取元素。但插入和刪除操作需要移動元素。⑴初始化操作算法思想：構(gòu)造一個(gè)空表。設(shè)置表的起始位置、表長及可用空間。0100La..[0][1][98][99]初始化操作實(shí)現(xiàn)StatusInitList_Sq(SqList&L){//構(gòu)造一個(gè)空的線性表

L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType)); if(!L.elem)exit(OVERFLOW);//存儲分配失敗

L.length=0;//空表長度為0

L.listsize=LIST_INIT_SIZE;//初始存儲容量

returnOK;}//InitList_Sq

（2）線性表的順序表插入操作

ListInsert(&L,i,e)分析：“插入元素”使線性表的邏輯結(jié)構(gòu)發(fā)生什么變化？假設(shè)在線性表的第i個(gè)元素之前插入一個(gè)元素e。

插入元素時(shí)，線性表的邏輯結(jié)構(gòu)由

(a1,…,ai-1,ai,…,an)(a1,…,ai-1,e,ai,…,an)<ai-1,ai><ai-1,e>,<e,ai>a1a2

…ai-1ai

…ana1a2

…ai-1

…aieanListInsert(&La,4,29)2038461840397812345678La78平均移動次數(shù)：39401829算法的基本思想檢查i值是否超出所允許的范圍（1≤i≤n+1），若超出，則進(jìn)行“超出范圍”錯(cuò)誤處理；將線性表的第i個(gè)元素和它后面的所有元素均向后移動一個(gè)位置；將新元素寫入到空出的第i個(gè)位置上；使線性表的長度增1。

StatusListInsert_Sq(SqList&L,inti,ElemTypee){//在順序表L的第i個(gè)元素之前插入新的元素e,

//i的合法范圍為1≤i≤L.length+1

ElemType*p,*q;

if(i<1||i>L.length+1)

returnERROR;

//插入位置不合法

if(L.length>=L.listsize){………..}q=&(L.elem[i-1]);//q指示插入位置

for(p=&(L.elem[L.length-1]);p>=q;--p)

*(p+1)=*p;

//插入位置及之后的元素右移

*q=e;

//插入e

++L.length;

//表長增1

returnOK;}//ListInsert_Sq

newbase=(ElemType*)realloc(L.elem,(LIST_INIT_SIZE+LISTINCREMENT)*sizeof(ElemType));If(!newbase)returnOVERFLOW;//當(dāng)前存儲空間已滿

L.elem=newbase;

L.

listsize+=LISTINCREMENT;

（3）線性表的順序表刪除操作

ListDelete(&La,i,&e)分析：“刪除元素”線性表的邏輯結(jié)構(gòu)發(fā)生什么變化？假設(shè)刪除線性表的第i個(gè)元素保存在變量e中。

刪除元素時(shí)，線性表的邏輯結(jié)構(gòu)由

(a1,…,ai-1,ai,…,an)(a1,…,ai-1,ai+1,…,an)<ai-1,ai>a1a2

…ai-1ai

ai+1

…ana1a2

…ai-1

…ai+1ean<ai,ai+1><ai-1,ai+1>

aiListDelete(&La,4,&e)2038461840397812345678La78平均移動次數(shù)：3940e18算法的基本思想檢查i值是否超出所允許的范圍（1≤i≤n），若超出，則進(jìn)行“超出范圍”錯(cuò)誤處理；將線性表的第i個(gè)元素后面的所有元素均向前移動一個(gè)位置；使線性表的長度減1。StatusListDelete_Sq(SqList&L,inti,ElemType&e){

//在順序線性表L中刪除第i個(gè)元素，并用e返回其值。

//i的合法值為1≤i≤ListLength_Sq(L)

if((i<1)||(i>L.length))returnERROR;

//刪除位置不合法

p=&(L.elem[i-1]);//p為被刪除元素的位置

e=*p;//被刪除元素的值賦給e

q=L.elem+L.length-1;//表尾元素的位置

for(++p;p<=q;++p)*(p-1)=*p;

//被刪除元素之后的元素左移

--L.length;

returnok;}（4）線性表的順序表查找操作LocateElem_Sq(La,e)StatusLocateElem_Sq(SqListL,ElemTypee,Status(*compare)(ElemType,ElemType)){//在順序表中查詢第一個(gè)滿足判定條件的數(shù)據(jù)元素，//若存在，則返回它的位序，否則返回0inti;ElemType*p;

i=1;p=L.elem;while(i<=L.length&&!(*compare(*p++,e))++i;if(i<=L.length)returni;elsereturn0;}//LocateElem_Sq

此算法的時(shí)間復(fù)雜度為:

O(ListLength(L))

平均比較次數(shù)為：(n+1)/2例如：順序表23754138546217L.elemL.length=7L.listsizee=38pppppi12341850p可見，基本操作是，將順序表中的元素逐個(gè)和給定值e相比較。順序存儲結(jié)構(gòu)的優(yōu)缺點(diǎn)優(yōu)點(diǎn)邏輯相鄰，物理相鄰可隨機(jī)存取任一元素存儲空間使用緊湊缺點(diǎn)插入、刪除操作需要移動大量的元素預(yù)先分配空間需按最大空間分配，利用不充分表容量難以擴(kuò)充順序表的合并問題例1、已知順序表LA和LB中的數(shù)據(jù)元素按值非遞減有序排列，現(xiàn)要將LA和LB歸并為一個(gè)新表LC，且LC中的數(shù)據(jù)元素仍按非值遞減有序排序。例如：LA＝（3,5,8,9）LB＝（2,6,8,9,11,15,20）則LC＝（2,3,5,6,8,8,9,11,11,15,20）85398210111520papbpc2356688910111520voidMergeList_Sq(SqListLa,SqListLb,SqList&Lc){pa=La.elem;pb=Lb.elem;Lc.listsize=Lc.length=La.length+Lb.length;pc=Lc.elem=(ElemType*)malloc(Lc.listsize*sizeof(ElemType));If(!Lc.elem)exit(OVERFLOW);pa_last=La.elem+La.length-1;pb_last=Lb.elem+Lb.length-1;while(pa<=pa_last&&pb<=pb_last){if(*pa<=*pb)*pc++=*pa++;else*pc++=*pb++;}while(pa<=pa_last)*pc++=*pa++;while(pb<=pb_last)*pc++=*pb++;}//MergeList_Sq

時(shí)間復(fù)雜度？2.3線性表的鏈?zhǔn)奖硎九c實(shí)現(xiàn)特點(diǎn)用一組任意的存儲單元存儲線性表的數(shù)據(jù)元素利用指針實(shí)現(xiàn)了用不相鄰的存儲單元存放邏輯上相鄰的元素每個(gè)數(shù)據(jù)元素ai，除存儲本身信息外，還需存儲其直接后繼的信息結(jié)點(diǎn):數(shù)據(jù)元素ai

的存儲映像。

數(shù)據(jù)域：元素本身信息指針域：指示直接后繼的存儲位置數(shù)據(jù)域指針域結(jié)點(diǎn)ZHAOQIANSUNLIZHOUWUZHENGWANG^H

線性表(ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG)43131NULL3771925數(shù)據(jù)域指針域LIQIANSUNWANGWUZHAOZHENGZHOU存儲地址1713192531374331H頭指針2.3.1單鏈表（線性鏈表）定義：結(jié)點(diǎn)中只含一個(gè)指針域的鏈表。特征：每個(gè)元素(表項(xiàng))由結(jié)點(diǎn)(Node)構(gòu)成。線性結(jié)構(gòu)結(jié)點(diǎn)可以不連續(xù)存儲表可擴(kuò)充Ha1a2a3a4^nextdata頭指針、頭結(jié)點(diǎn)、第一個(gè)元素結(jié)點(diǎn)以線性表中第一個(gè)數(shù)據(jù)元素a1的存儲地址作為線性表的地址，稱作線性表的頭指針有時(shí)為了操作方便，在第一個(gè)結(jié)點(diǎn)之前虛加一個(gè)“頭結(jié)點(diǎn)”，以指向頭結(jié)點(diǎn)的指針為鏈表的頭指針a1a2a3an^空指針…頭指針頭結(jié)點(diǎn)線性表為空表時(shí)，頭結(jié)點(diǎn)的指針域?yàn)榭誢單鏈表存儲結(jié)構(gòu)的實(shí)現(xiàn)typedefstructLNode{

ElemType

data;structLNode*next;}LNode，*LinkList;structLNode{

ElemType

data;structLNode*next;};typedefLNode*LinkList;p結(jié)點(diǎn)（*p）(*p)表示p所指向的結(jié)點(diǎn)(*p).datap->data表示p指向結(jié)點(diǎn)的數(shù)據(jù)域(*p).nextp->next表示p指向結(jié)點(diǎn)的指針域LinkListLNodeLNodenextdata生成一個(gè)LNode型新結(jié)點(diǎn)：

p=(LinkList)malloc(sizeof(LNode));系統(tǒng)回收p結(jié)點(diǎn)：

free(p)單鏈表特點(diǎn):它是一種動態(tài)結(jié)構(gòu)，整個(gè)存儲空間為多個(gè)鏈表共用不需預(yù)先分配空間指針占用額外存儲空間插入、刪除方便不能隨機(jī)存取，查找速度慢單鏈表基本操作的實(shí)現(xiàn)GetElem(L,i,&e)//取第i個(gè)數(shù)據(jù)元素ListInsert(&L,i,e)//插入數(shù)據(jù)元素ListDelete(&L,i,&e)//刪除數(shù)據(jù)元素CreateList_L(&L,n)//創(chuàng)建線性表（1）單鏈表查找操作

—GetElem(L,i,&e)Lpj1232017406034∧實(shí)現(xiàn)GetElem(L,3,&e)實(shí)現(xiàn)GetElem(L,6,&e)45算法的基本思想令p為指針變量，首先指向第一個(gè)結(jié)點(diǎn)，變量j為計(jì)數(shù)器；依次向后查找，循環(huán)結(jié)束的條件，p為空或者j=i。如果p為空或j>i，出錯(cuò)。找到了，用e返回第i個(gè)元素。算法實(shí)現(xiàn)StatusGetElem_L(LinkListL,inti,ElemType&e){//L是帶頭結(jié)點(diǎn)的鏈表的頭指針，以e返回第i個(gè)元素

p=L->next;//p指向第一個(gè)結(jié)點(diǎn)

j=1;//j為計(jì)數(shù)器

while(p&&j<i) {p=p->next;++j; }if(!p||j>i)returnERROR; e=p->data;//取得第i個(gè)元素

returnOK;}//GetElem_L（2）單鏈表的插入操作

ListInsert(&L,i,e)分析：“插入元素”使線性表的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)發(fā)生什么變化？假設(shè)在線性表的第i個(gè)元素之前插入一個(gè)元素e。

(a1,…,ai-1,ai,…,an)(a1,…,ai-1,e,ai,…,an)<ai-1,ai><ai-1,e>,<e,ai>ai-1anai……∧a1……Le第i個(gè)元素之前插入元素es=(LinkList)malloc(sizeof(LNode));//生成新結(jié)點(diǎn)s->data=e;s->next=p->next; p->next=s；ai(插入前)(插入后)aiai-1peai-1sp單鏈表插入操作

—ListInsert(&L,i,e)Lpj122017406034∧實(shí)現(xiàn)ListInsert(L,3,10)10s{//帶頭結(jié)點(diǎn)的單鏈表L中第i個(gè)位置之前插入元素eLNode*p,*s;intj;p=L;j=0;while(p&&j<i-1){p=p->next;++j;}if(!p||j>i-1)returnERROR;s=(LinkList)malloc(sizeof(LNode));//生成新結(jié)點(diǎn)s->data=e;//使新結(jié)點(diǎn)數(shù)據(jù)域的值為es->next=p->next;//將新結(jié)點(diǎn)插入到單鏈表L中p->next=s;//修改第i-1個(gè)結(jié)點(diǎn)指針returnOK;}//ListInsert_LStatusListInsert_L(LinkList&L,inti,ElemTypee)時(shí)間復(fù)雜度：T(n)=O(n)（3）單鏈表的刪除操作

——ListDelete(&L,i,&e)

分析：“刪除元素”使線性表的物理結(jié)構(gòu)發(fā)生什么變化？ai-1anai……∧a1Lai+1刪除第i個(gè)元素，并保存數(shù)據(jù)到元素e中q=p->next;//用指針q指向被刪除結(jié)點(diǎn)

p->next=q->next;//刪除第i個(gè)結(jié)點(diǎn)*e=ai;free(q);pqpai+1aiai-1aie單鏈表的刪除操作

——ListDelete(&L,i,&e)Lpj122017406034∧實(shí)現(xiàn)ListDelete(&L,3,&e)q{//刪除第i個(gè)元素，并由e返回其值LNode*p,*q;intj;p=L;j=0;while(p->next&&j<i-1){p=p->next;++j;}if(!(p->next)||j>i-1)returnERROR;//刪除位置不合理

q=p->next;//用指針q指向被刪除結(jié)點(diǎn)p->next=q->next;//刪除第i個(gè)結(jié)點(diǎn)e=q->data;//取出第i個(gè)結(jié)點(diǎn)數(shù)據(jù)域值free(q);//釋放第i個(gè)結(jié)點(diǎn)returnOK;}//LinkDelete_LStatusListDelete_L(LinkListL,inti,ElemType&e)時(shí)間復(fù)雜度：T(n)=O(n)

（4）創(chuàng)建單鏈表

——CreateList_L(&L,n)Lp2017406034∧已知線性表（20，17，40，60，34）頭插法創(chuàng)建帶有頭結(jié)點(diǎn)的單鏈表。pppp頭插法創(chuàng)建單鏈表CreateList_L(LinkList&L,intn){L=(LinkList)malloc(sizeof(LNode));L->next=NULL;for(i=n;i>0;--i){s=(LinkList)malloc(sizeof(LNode));scanf(&s->data);s->next=L->next;①L->next=s;②}}頭插法創(chuàng)建單鏈表voidCreateList_L(LinkList&L,intn){//輸入n個(gè)數(shù)據(jù)元素的值，建立帶頭結(jié)點(diǎn)的單鏈表

L

LNode*p;inti;

L=(LinkList)malloc(sizeof(LNode));

L->next=NULL;//先建立一個(gè)帶頭結(jié)點(diǎn)的空鏈表

for(i=n;i>0;--i){ p=(LinkList)malloc(sizeof(LNode)); scanf("%d",&p->data);

p->next=L->next; L->next=p;

}}

//CreateList_L

（4）創(chuàng)建單鏈表

——CreateList_L(&L,n)Lp2017∧已知線性表（20，17，40，60）尾插法創(chuàng)建帶有頭結(jié)點(diǎn)的單鏈表。思考：算法如何實(shí)現(xiàn)？pq40p60p∧用尾插法建立線性單鏈表用尾插法建立線性單鏈表CreateList_L(LinkList&L,intn){

tail=L=(LinkList)malloc(sizeof(LNode));L->next=NULL;for(i=n;i>0;--i)

{s=(LinkList)malloc(sizeof(LNode));scanf(&s->data);s->next=NULL;

tail->next=s;①

tail=s;②}}線性表的合并問題例1、已知線性表Lc和Lb中的數(shù)據(jù)元素按值非遞減有序排列，現(xiàn)要將Lc和Lb歸并為一個(gè)新的鏈表Lc，且Lc中的數(shù)據(jù)元素仍按非值遞減有序排序。例如：La＝（3,5,8,11）Lb＝（2,6,9,15,20）La11853Lb2015962pcpbpa∧∧LcvoidMergeList_L(LinkList&La,LinkList&Lb,LinkList&Lc

){//歸并La和Lb得到新的單鏈表Lc，Lc的元素也按非遞減排列LNode*pa,

*pb,*pc;pa=La->next;pb=Lb->next;Lc=pc=La;//用La的頭結(jié)點(diǎn)作為Lc的頭結(jié)點(diǎn)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);//釋放Lb的頭結(jié)點(diǎn)}//MergeList_L2.3.2循環(huán)鏈表循環(huán)鏈表是單鏈表的變形。循環(huán)鏈表最后一個(gè)結(jié)點(diǎn)的指針域不為NULL，而是指向了表的前端。為簡化操作，在循環(huán)鏈表中往往加入頭結(jié)點(diǎn)。循環(huán)鏈表的特點(diǎn)是：只要知道表中某一結(jié)點(diǎn)的地址，就可搜尋到所有其他結(jié)點(diǎn)的地址。循環(huán)鏈表示例帶頭結(jié)點(diǎn)的循環(huán)鏈表

a1a2a3anHanHa2a1H(空表)(非空表)循環(huán)鏈表的搜索算法H31481557搜索15pppH31481557搜索25ppppp思考整個(gè)搜索算法的條件是？循環(huán)鏈表中尾指針的應(yīng)用考慮如何實(shí)現(xiàn)將帶有尾指針的兩個(gè)循環(huán)鏈表合并為一個(gè)？anAa2a1ana2a1Bp=A->next;A=B->next->next;free(B->next);B->next=p;A=B;帶尾指針的循環(huán)鏈表rear3148155722

如果插入與刪除僅在鏈表的兩端發(fā)生，可采用帶表尾指針的循環(huán)鏈表結(jié)構(gòu)。在表尾插入，時(shí)間復(fù)雜性O(shè)(1)

在表尾刪除，時(shí)間復(fù)雜性O(shè)(n)

在表頭插入，相當(dāng)于在表尾插入在表頭刪除，時(shí)間復(fù)雜性O(shè)(1)2.3.3雙向鏈表雙向鏈表是指在前驅(qū)和后繼方向都能游歷(遍歷)的線性鏈表。雙向鏈表每個(gè)結(jié)點(diǎn)有兩個(gè)指針域,結(jié)構(gòu)如下：雙向鏈表通常采用帶頭結(jié)點(diǎn)的循環(huán)鏈表形式。前驅(qū)方向后繼方向priordatanext雙向鏈表的C語言定義typedefstructDuLNode{ElemTypedata;

structDuLNode*prior,*next;}DuLNode,*DuLinkList;priordatanext空雙向循環(huán)鏈表：非空雙向循環(huán)鏈表：LLAB結(jié)點(diǎn)指向

p->prior->next==p==p->next->priorp->priorp->nextppriornext雙向鏈表中插入操作

s=(DuLNode*)malloc(sizeof(DuLNode));s->data=e;s->prior=p->prior;s->next=p;p->prior->next=s;p->prior=s;esbap雙向鏈表的插入操作算法:StatusListInsert_DuL(DuLinkList&L,inti,ElemTypee){if(!(p=GetElemP_DuL(L,i)))returnERROR;

if(!(s=(DuLinkList)malloc(sizeof(DuLNode))))

returnERROR;

s->data=e;//將數(shù)據(jù)放入新結(jié)點(diǎn)的數(shù)據(jù)域

s->prior=p->prior;//將p的前驅(qū)結(jié)點(diǎn)指針放入新結(jié)點(diǎn)的前向指針域

s->next=p;//將p的放入新結(jié)點(diǎn)的反向指針域

p->prior->next=s;//修改p的前驅(qū)結(jié)點(diǎn)的反向指針

p->prior=s;//修改p的前向指針

returnOK;}//ListInsert_DuL算法評價(jià)：T(n)=O(n)刪除操作bcapp->prior->next=p->next;p->next->prior=p->prior;free(p);雙向鏈表的刪除操作算法:StatusListDelete_DuL(DuLinkList&L,inti,ElemType&e){//刪除帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表L中第i個(gè)元素并將元素值返回，1≤i≤表長if(!(p=GetElemP_DuL(L,i)))returnERROR;//在L中確定第i個(gè)元素，p為指向該結(jié)點(diǎn)的指針；//若i<1或i>表長，則p為NULL，第i個(gè)元素不存在e=p->data;//將p指向的結(jié)點(diǎn)數(shù)據(jù)域中的值取出p->prior->next=p->next;//修改p的前驅(qū)結(jié)點(diǎn)的反向指針p->next->prior=p->prior;//修改p的后繼結(jié)點(diǎn)的前向指針free(p);//釋放p結(jié)點(diǎn)returnOK;}//ListDelete_DuL算法評價(jià)：T(n)=O(n)順序表與鏈表的比較存取方式順序表可以隨機(jī)存取，也可以順序存取鏈表是順序存取的插入/刪除時(shí)移動元素個(gè)數(shù)順序表平均需要移動近一半元素鏈表不需要移動元素，只需要修改指針若插入/刪除僅發(fā)生在表的兩端，宜采用帶尾指針的循環(huán)鏈表考慮如何選擇合適的存儲結(jié)構(gòu)？用上述定義的單鏈表實(shí)現(xiàn)線性表的操作時(shí)，存在的問題：單鏈表的表長是一個(gè)隱含的值；在單鏈表的最后一個(gè)元素之后插入元素時(shí)，需遍歷整個(gè)鏈表；在鏈表中，元素的“位序”概念淡化，結(jié)點(diǎn)的“位置”概念加強(qiáng)。typedefstructLNode{

ElemType

data;structLNode*next;}LNode，*LinkList;帶頭結(jié)點(diǎn)的單鏈表類型typedefstructLNode{//結(jié)點(diǎn)類型

ElemTypedata;structLNode*next;}*Link,*Position;typedefstruct{//鏈表類型

Linkhead,tail;//分別指向頭結(jié)點(diǎn)和

最后一個(gè)結(jié)點(diǎn)的指針

intlen;//指示鏈表長度}LinkList;靜態(tài)鏈表定義：用一維數(shù)組描述的鏈表叫靜態(tài)鏈表存儲結(jié)構(gòu)：#defineMAXSIZE=100;//靜態(tài)鏈表的最大長度typedefstruct{ElemTypedata;intcur;//游標(biāo),代替指針指示結(jié)點(diǎn)在數(shù)組中的位置}component,

SLinkList[MAXSIZE];目的：為了在不設(shè)指針類型的高級程序設(shè)計(jì)語言中使用鏈表結(jié)構(gòu)2.4一元多項(xiàng)式的表示與相加一元多項(xiàng)式的表示n階多項(xiàng)式Pn(x)有

n+1項(xiàng)。

系數(shù)P0,P1,P2,…,Pn

指數(shù)0,1,2,…,n。按升冪排列可用線性表P表示：若：

對S(x)這樣的多項(xiàng)式采用全部存儲的方式則浪費(fèi)空間。怎么辦？一般n次多項(xiàng)式可以寫成：其中因此可以用數(shù)據(jù)域含兩個(gè)數(shù)據(jù)項(xiàng)的線性表來表示：其存儲結(jié)構(gòu)可以用順序存儲結(jié)構(gòu)，也可以用單鏈表。多項(xiàng)式的鏈表表示typedefstructPolynode{intcoef,

exp;structPolynode*next;}Polynode

,*Polylist;優(yōu)點(diǎn)是：多項(xiàng)式的項(xiàng)數(shù)可以動態(tài)地增長，不存在存儲溢出問題。插入、刪除方便，不移動元素。coefexpnext

一元多項(xiàng)式的建立

通過鍵盤輸入一組多項(xiàng)式的系數(shù)和指數(shù)，以輸入系數(shù)0為結(jié)束標(biāo)志，并約定建立多項(xiàng)式鏈表時(shí)，總是按指數(shù)從小到大的順序排列。算法描述：從鍵盤接受輸入的系數(shù)和指數(shù)；用尾插法建立一元多項(xiàng)式的鏈表。Polylistpolycreate(){Polynode*head,*rear,*s;intc,e;head=(Polynode*)malloc(sizeof(Polynode));rear=head;scanf(″%d,%d″,&c,&e);while(c!=0){s=(Polynode*)malloc(sizeof(Polynode));s->coef=c;s->exp=e;rear->next=s;rear=s;scanf(″%d,%d″,&c,&e);}rear->next=NULL;return(head);}一元多項(xiàng)式相加掃描兩個(gè)多項(xiàng)式，若都未檢測完：若當(dāng)前被檢測項(xiàng)指數(shù)相等，系數(shù)相加。若未變成0，則將結(jié)果加到結(jié)果多項(xiàng)式。若當(dāng)前被檢測項(xiàng)指數(shù)不等，將指數(shù)小者加到結(jié)果多項(xiàng)式。若一個(gè)多項(xiàng)式已檢測完，將另一個(gè)多項(xiàng)式剩余部分復(fù)制到結(jié)果多項(xiàng)式。設(shè)計(jì)思想：1)令指針Pa，Pb分別指向A和B中當(dāng)前進(jìn)行比較的結(jié)點(diǎn)。2)根據(jù)結(jié)點(diǎn)的指數(shù)比較結(jié)點(diǎn)大小。ea<eb取結(jié)點(diǎn)a放入和的鏈表中結(jié)點(diǎn)pa，pb指數(shù)比較ea>eb取結(jié)點(diǎn)b放入和的鏈表中ea=eb將a，b中系數(shù)相加系數(shù)不為0，則修改a結(jié)點(diǎn)的系數(shù)為系數(shù)之和，釋放b節(jié)點(diǎn)系數(shù)之和為0，從A鏈表中刪除該結(jié)點(diǎn)，并釋放b11多項(xiàng)式相加過程演示-1A70198517^-1B81227-98^papbCpc3r0rr算法實(shí)現(xiàn)voidpolyadd(Polylistpolya;Polylistpolyb){Polynode*p,*q,*pre;*temp;intsum;p=polya->next;q=polyb->next;pre=polya;/*pre指向和多項(xiàng)式的尾結(jié)點(diǎn)*/

while(p!=NULL&&q!=NULL)

{

…………

………....

}

if(p!=NULL)pre->next=p;

elsepre->next=q;

}while(p!=NULL&&q!=NULL){

if(p->exp<q->exp){pre->next=p;pre=pre->next;p=p->next;}

elseif(p->exp==q->exp){sum=p->coef+q->coef;

if(sum!=0){p->coef=sum;pre->next=p;pre=pre->next;p=p->next;}

else{