數(shù)據(jù)結構 第二章 線性表

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

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

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

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

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

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

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

ListInsert(LA,n+1,e)算法實現(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個數(shù)據(jù)元素賦給e

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

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

}}算法舉例：例2-2歸并兩個“其數(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中取得當前元素ai

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

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

中，否則將bj

插入到Lc

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

或Lb

中元素被取完為止；將La

表或Lb表中剩余元素復制插入到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算法的時間復雜度：O(ListLength(La)+ListLength(Lb)）

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

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

123456

data用物理位置來表示邏輯結構。

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

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

——C語言定義#define

LIST_INIT_SIZE100#defineLISTINCREAMENT10typedef

struct{ElemType

*elem；

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

int

length；

/*線性表的長度*/

intlistsize；

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

}SqList；

elemlengthlistsizeSqListElemType順序線性表的操作

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

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)分析：“插入元素”使線性表的邏輯結構發(fā)生什么變化？假設在線性表的第i個元素之前插入一個元素e。

插入元素時，線性表的邏輯結構由

(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），若超出，則進行“超出范圍”錯誤處理；將線性表的第i個元素和它后面的所有元素均向后移動一個位置；將新元素寫入到空出的第i個位置上；使線性表的長度增1。

StatusListInsert_Sq(SqList&L,inti,ElemTypee){//在順序表L的第i個元素之前插入新的元素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;//當前存儲空間已滿

L.elem=newbase;

L.

listsize+=LISTINCREMENT;

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

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

刪除元素時，線性表的邏輯結構由

(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），若超出，則進行“超出范圍”錯誤處理；將線性表的第i個元素后面的所有元素均向前移動一個位置；使線性表的長度減1。StatusListDelete_Sq(SqList&L,inti,ElemType&e){

//在順序線性表L中刪除第i個元素，并用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)){//在順序表中查詢第一個滿足判定條件的數(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

此算法的時間復雜度為:

O(ListLength(L))

平均比較次數(shù)為：(n+1)/2例如：順序表23754138546217L.elemL.length=7L.listsizee=38pppppi12341850p可見，基本操作是，將順序表中的元素逐個和給定值e相比較。順序存儲結構的優(yōu)缺點優(yōu)點邏輯相鄰，物理相鄰可隨機存取任一元素存儲空間使用緊湊缺點插入、刪除操作需要移動大量的元素預先分配空間需按最大空間分配，利用不充分表容量難以擴充順序表的合并問題例1、已知順序表LA和LB中的數(shù)據(jù)元素按值非遞減有序排列，現(xiàn)要將LA和LB歸并為一個新表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

時間復雜度？2.3線性表的鏈式表示與實現(xiàn)特點用一組任意的存儲單元存儲線性表的數(shù)據(jù)元素利用指針實現(xiàn)了用不相鄰的存儲單元存放邏輯上相鄰的元素每個數(shù)據(jù)元素ai，除存儲本身信息外，還需存儲其直接后繼的信息結點:數(shù)據(jù)元素ai

的存儲映像。

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

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

ElemType

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

ElemType

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

p=(LinkList)malloc(sizeof(LNode));系統(tǒng)回收p結點：

free(p)單鏈表特點:它是一種動態(tài)結構，整個存儲空間為多個鏈表共用不需預先分配空間指針占用額外存儲空間插入、刪除方便不能隨機存取，查找速度慢單鏈表基本操作的實現(xiàn)GetElem(L,i,&e)//取第i個數(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∧實現(xiàn)GetElem(L,3,&e)實現(xiàn)GetElem(L,6,&e)45算法的基本思想令p為指針變量，首先指向第一個結點，變量j為計數(shù)器；依次向后查找，循環(huán)結束的條件，p為空或者j=i。如果p為空或j>i，出錯。找到了，用e返回第i個元素。算法實現(xiàn)StatusGetElem_L(LinkListL,inti,ElemType&e){//L是帶頭結點的鏈表的頭指針，以e返回第i個元素

p=L->next;//p指向第一個結點

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

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

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

ListInsert(&L,i,e)分析：“插入元素”使線性表的邏輯結構和物理結構發(fā)生什么變化？假設在線性表的第i個元素之前插入一個元素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個元素之前插入元素es=(LinkList)malloc(sizeof(LNode));//生成新結點s->data=e;s->next=p->next; p->next=s；ai(插入前)(插入后)aiai-1peai-1sp單鏈表插入操作

—ListInsert(&L,i,e)Lpj122017406034∧實現(xiàn)ListInsert(L,3,10)10s{//帶頭結點的單鏈表L中第i個位置之前插入元素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));//生成新結點s->data=e;//使新結點數(shù)據(jù)域的值為es->next=p->next;//將新結點插入到單鏈表L中p->next=s;//修改第i-1個結點指針returnOK;}//ListInsert_LStatusListInsert_L(LinkList&L,inti,ElemTypee)時間復雜度：T(n)=O(n)（3）單鏈表的刪除操作

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

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

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

——ListDelete(&L,i,&e)Lpj122017406034∧實現(xiàn)ListDelete(&L,3,&e)q{//刪除第i個元素，并由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指向被刪除結點p->next=q->next;//刪除第i個結點e=q->data;//取出第i個結點數(shù)據(jù)域值free(q);//釋放第i個結點returnOK;}//LinkDelete_LStatusListDelete_L(LinkListL,inti,ElemType&e)時間復雜度：T(n)=O(n)

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

——CreateList_L(&L,n)Lp2017406034∧已知線性表（20，17，40，60，34）頭插法創(chuàng)建帶有頭結點的單鏈表。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個數(shù)據(jù)元素的值，建立帶頭結點的單鏈表

L

LNode*p;inti;

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

L->next=NULL;//先建立一個帶頭結點的空鏈表

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)建帶有頭結點的單鏈表。思考：算法如何實現(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歸并為一個新的鏈表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的頭結點作為Lc的頭結點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的頭結點}//MergeList_L2.3.2循環(huán)鏈表循環(huán)鏈表是單鏈表的變形。循環(huán)鏈表最后一個結點的指針域不為NULL，而是指向了表的前端。為簡化操作，在循環(huán)鏈表中往往加入頭結點。循環(huán)鏈表的特點是：只要知道表中某一結點的地址，就可搜尋到所有其他結點的地址。循環(huán)鏈表示例帶頭結點的循環(huán)鏈表

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

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

在表尾刪除，時間復雜性O(n)

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

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

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ù)放入新結點的數(shù)據(jù)域

s->prior=p->prior;//將p的前驅結點指針放入新結點的前向指針域

s->next=p;//將p的放入新結點的反向指針域

p->prior->next=s;//修改p的前驅結點的反向指針

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

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

ElemType

data;structLNode*next;}LNode，*LinkList;帶頭結點的單鏈表類型typedefstructLNode{//結點類型

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

Linkhead,tail;//分別指向頭結點和

最后一個結點的指針

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

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

n+1項。

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

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

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

exp;structPolynode*next;}Polynode

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

一元多項式的建立

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

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{