管科大二上學(xué)期課件數(shù)據(jù)結(jié)構(gòu)第一章

第二章線性表

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)的特點(diǎn)：在數(shù)據(jù)元素的非空有限集中，⑴存在唯一的一個(gè)被稱作“第一個(gè)”的數(shù)據(jù)元素；⑵存在唯一的一個(gè)被稱作“最后一個(gè)”的數(shù)據(jù)元素；⑶除第一個(gè)之外，集合中的每個(gè)數(shù)據(jù)元素均只有一個(gè)前驅(qū)；⑷除最后一個(gè)之外，集合中每個(gè)數(shù)據(jù)元素均只有一個(gè)后繼。線性表中的數(shù)據(jù)元素可以是多種多樣的，但同一線性表中的元素必定具有相同的特性，即屬同一數(shù)據(jù)對(duì)象，相鄰數(shù)據(jù)元素之間存在序偶關(guān)系。若將線性標(biāo)記為(a1,…,ai-1,ai,ai+1,…,an)<ai-1,ai><ai,ai+1>ai-1是ai的直接前驅(qū)元素，ai+1是ai的直接后繼元素。例、學(xué)生健康情況登記表如下：姓名學(xué)號(hào)性別年齡健康情況王小林790631男

18健康陳紅790632女

20一般劉建平790633男

21健康張立立790634男

17神經(jīng)衰弱

……..

……..…….…….

…….線性表中元素的個(gè)數(shù)n（n>=0)定義為線性表的長(zhǎng)度，n=0時(shí)稱為空表。在非空表中的每個(gè)數(shù)據(jù)元素都有一個(gè)確定的位置，ai是第i個(gè)元素，稱i是數(shù)據(jù)元素ai在線性表中的位序。線性表的長(zhǎng)度可根據(jù)需要增長(zhǎng)或縮短。（插入、刪除操作）抽象數(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}

基本操作：

InitList(&L);

操作結(jié)果：構(gòu)造一個(gè)空的線性表L。

DestroyList(&L);

初始條件：線性表L已存在。操作結(jié)果：銷毀線性表L。

ClearList(&L);

初始條件：線性表L已存在。操作結(jié)果：將L重置為空表。

ListEmpty(L)初始條件：線性表L已存在。操作結(jié)果：若L為空表，則返回TRUE，否則返回FALSE。ListLength(L)初始條件：線性表L已存在。操作結(jié)果：返回L中數(shù)據(jù)元素個(gè)數(shù)。

GetElem(L,i,&e)初始條件：線性表L已存在，1≤i≤ListLength(L)。操作結(jié)果：用e返回L中第i個(gè)數(shù)據(jù)元素的值。

LocateElem(L,e,compare())初始條件：線性表L已存在，compare()是數(shù)據(jù)元素判定函數(shù)。操作結(jié)果：返回L中第1個(gè)與e滿足關(guān)系compare()的數(shù)據(jù)元素的位序。若這樣的數(shù)據(jù)元素不存在，則返回0。PriorElem(L,cur_e,&pre_e)初始條件：線性表L已存在。操作結(jié)果：若cur_e是L的數(shù)據(jù)元素，且不是第1個(gè)，則用pre_e返回它的前驅(qū)，否則操作失敗，pre_e無(wú)定義。

NextItem(L,cur_e,&next_e)初始條件：線性表L已存在。操作結(jié)果：若cur_e是L的數(shù)據(jù)元素，且不是最后一個(gè)，則用next_e返回它的后繼，否則操作失敗，next_e無(wú)定義。

ListInsert(&L,i,e)初始條件：線性表L已存在，1≤i≤ListLength(L)+1。操作結(jié)果:在L中第i個(gè)位置之前插入新的數(shù)據(jù)元素e，L的長(zhǎng)度加1。

ListDelete(&L,i,&e)初始條件：線性表L已存在，1≤i≤ListLength(L)。操作結(jié)果:刪除L的第i個(gè)數(shù)據(jù)元素，并用e返回其值，L的長(zhǎng)度減1。

ListTraverse(L,visit())

初始條件：線性表L已存在。操作結(jié)果：依次對(duì)L的每個(gè)數(shù)據(jù)元素調(diào)用函數(shù)visit（）。一旦visit（）失敗，則操作失敗。}ADTList對(duì)上述定義的抽象數(shù)據(jù)類型線性表，還可進(jìn)行一些更復(fù)雜的操作。例：假設(shè)利用兩個(gè)線性表LA和LB分別表示兩個(gè)集合A和B（即線性表中的數(shù)據(jù)元素即為集合中的成員），現(xiàn)要求一個(gè)新的集合，使得A=AUB。需要對(duì)線性表進(jìn)行如下操作：擴(kuò)大線性表A，將存在于線性表LB中而不存在于LA中的數(shù)據(jù)元素插入到線性表LA中。abcdefLALBabfgvabcdefLAgv從LB中依次取得每個(gè)數(shù)據(jù)元素，并依值在LA中進(jìn)行查訪，若不存在，則執(zhí)行插入操作。Voidunion(List&La,ListLb){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線性表的順序表示和實(shí)現(xiàn)線性表的順序表示指的是用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表的數(shù)據(jù)元素。假如線性表每個(gè)元素占用L個(gè)存儲(chǔ)單元，并以第一個(gè)單元的存儲(chǔ)地址作為數(shù)據(jù)元素的存儲(chǔ)位置，則LOC（ai+1）=LOC（ai）+LLOC（ai）=LOC（a1）+（i-1）*L線性表第1個(gè)元素a1的存儲(chǔ)位置，稱作線性表的起始位置或基地址。線性表的動(dòng)態(tài)分配順序存儲(chǔ)結(jié)構(gòu)：#defineLIST_INIT_SIZE100#defineLISTINCREMENT10Typedefstruct{ElemType*elem;intlength;intlistsize;}SqList;指示線性表基地址指示線性表當(dāng)前長(zhǎng)度指示順序表當(dāng)前分配的存儲(chǔ)空間大小，一旦因插入元素而空間不足時(shí)，可進(jìn)行再分配，即為順序表增加一個(gè)大小為存儲(chǔ)LISTINCREMENT個(gè)數(shù)據(jù)元素的空間線性表存儲(chǔ)空間的初始分配量線性表存儲(chǔ)空間的分配增量以sizeof(Elemtype)為單位順序表的初始化操作：statusInitList_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;}線性表的插入和刪除操作在順序存儲(chǔ)表示時(shí)的實(shí)現(xiàn)方法一般情況下，在第i個(gè)（1≤i≤n）個(gè)元素之前插入一個(gè)元素時(shí)，需將第n至第i（共n-i+1）個(gè)元素向后移動(dòng)一個(gè)位置。a1a2a3a4a5a6a7

a8a9a1a2a3a4ea5a7

a8a9a6

statusListInsert_Sq(SqList&L,inti,ElemTypee){if(i<1||i>L.length+1)returnERROR;

//異常處理if(L.length>=L.ListSize){

//存儲(chǔ)空間不足newbase=(ElemType*)realloc(L.elem,(L.ListSize+LISTINCREMENT)*sizeof(ElemType));if(!newbase)exit(OVERFLOW);L.elem=newbase;L.ListSize+=LISTINCREMENT;}q=&(L.elem[i-1]);for(p=&(L.elem[L.length-1]);p>=q;--p)*(p+1)=*p;//從n向i依次移動(dòng)*q=e;++L.length;returnOK;}對(duì)于刪除操作，線性表的邏輯關(guān)系發(fā)生了變化，表長(zhǎng)減1。一般情況下，刪除第i（1≤i≤n）個(gè)元素時(shí)需將從第i+1至第n（共n-i）個(gè)元素依次向前移動(dòng)一個(gè)位置。StatusListDelete_Sq(SqList&L,inti,ElemType&e){if((i<1)||(i>L.length))returnERROR;p=&(L.elem[i-1]);e=*p;q=L.elem+L.length-1;for(++p;p<=q;++p)*(p-1)=*p;--L.length;returnOK;}算法時(shí)間復(fù)雜度的分析：假設(shè)pi是在第i個(gè)元素之前插入一個(gè)元素的概率，則在長(zhǎng)度為n的線性表中插入一個(gè)元素時(shí)，所需移動(dòng)的元素的次數(shù)的期望值（平均次數(shù)）為

不失一般性，假定在線性表的任何位置上插入或刪除元素是等概率的。即類似的可以求出則順序存儲(chǔ)結(jié)構(gòu)的線性表中插入或刪除一個(gè)數(shù)據(jù)元素，平均約移動(dòng)表中一半元素。若表長(zhǎng)為n，則算法ListInsert_Sq和ListDelete_Sq的時(shí)間復(fù)雜度為O（n）。在順序存儲(chǔ)表示的線性表中插入或刪除一個(gè)數(shù)據(jù)元素，平均約需移動(dòng)表中一半元素。這個(gè)數(shù)目在線性表的長(zhǎng)度較大時(shí)是很可觀的。這個(gè)缺陷完全是由于順序存儲(chǔ)要求線性表的元素依次緊挨存放造成的。因此，這種順序存儲(chǔ)表示僅適用于不常進(jìn)行插入和刪除操作、表中元素相對(duì)穩(wěn)定的線性表。2.3線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)線性表的順序映象結(jié)構(gòu)的特點(diǎn)：邏輯關(guān)系上相鄰的兩個(gè)元素，在物理位置上也相鄰，可以隨機(jī)存取表中任一元素。弱點(diǎn)：在做插入或刪除操作時(shí)，需移動(dòng)大量元素。線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的特點(diǎn)是用一組任意的存儲(chǔ)單元存儲(chǔ)線性表的數(shù)據(jù)元素。（這些存儲(chǔ)單元可以是連續(xù)的，也可以是不連續(xù)的）2.3.1線性鏈表有關(guān)線性鏈表的基本概念：結(jié)點(diǎn)：包括兩個(gè)域結(jié)點(diǎn)中只包含一個(gè)指針域的鏈表稱為線性鏈表或單鏈表。整個(gè)鏈表的存取必須從頭指針開(kāi)始進(jìn)行，頭指針指示鏈表中第一個(gè)結(jié)點(diǎn)的存儲(chǔ)位置，線性鏈表中最后一個(gè)結(jié)點(diǎn)的指針域?yàn)椤翱铡?。?shù)據(jù)域指針域存儲(chǔ)數(shù)據(jù)元素信息存儲(chǔ)直接后繼存儲(chǔ)位置例1、線性表:(bat，cat，eat，fat，hat，jat，lat，mat)的單鏈表示意圖如下：

…… 110 …… 130 135 …… 160頭指針head165 170 …… 200 205 …………………h(huán)at200…….……cat135eat170….……matNullbat130fat110…………jat205lat160…………

165單鏈表的存儲(chǔ)結(jié)構(gòu)可以用“結(jié)構(gòu)指針”描述為typedefstructLnode{ElemTypedata;structLnode*next;}Lnode,*LinkList;為了便于處理一些特殊情況，在第一個(gè)結(jié)點(diǎn)之前附加一個(gè)“頭結(jié)點(diǎn)”，令該結(jié)點(diǎn)中指針域的指針指向第一個(gè)元素結(jié)點(diǎn)，并令頭指針指向頭結(jié)點(diǎn)值得注意的是，若線性表為空，在不帶頭結(jié)點(diǎn)的情況下，頭指針為空(NULL)，但在帶頭結(jié)點(diǎn)的情況下，鏈表的頭指針不為空，而是其頭結(jié)點(diǎn)中指針域的指針為空a1a2anΛΛ…LL單鏈表的查訪操作如何實(shí)現(xiàn)？單鏈表是一種"順序存取"的結(jié)構(gòu)，即：為取第i元素，首先必須先找到第i-1個(gè)元素。因此不論i值為多少，都必須從頭結(jié)點(diǎn)開(kāi)始起"點(diǎn)數(shù)"，直數(shù)到第i個(gè)為止。頭結(jié)點(diǎn)可看成是第0個(gè)結(jié)點(diǎn)。statusGetElem_L(LinkListL,inti,ElemType&e){p=L->next;j=1;while(p&&j<i){p=p->next;++j;}if(!p||j>i)returnERROR;e=p->data;returnOK;}對(duì)單鏈表執(zhí)行插入操作：abpapbxs假設(shè)S為指向結(jié)點(diǎn)x的指針，則：

s->next=p->next;P->next=s;statusListInsert_L(LinkList&L,inti,ElemTypee){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;s->next=p->next;p->next=s;returnOK;}在單鏈表中刪除結(jié)點(diǎn)時(shí)指針變化情況：abpcp->next=p->next->nextstatusListDelete_L(LinkList&L,inti;ElemType&e){p=L;j=0;while(p->next&&j<i-1){p=p->next;++j;}if(!(p->next)||j>i-1)returnERROR;q=p->next;p->next=q->next;e=q->data;free(q);returnOK;}逆序創(chuàng)建鏈表鏈表的動(dòng)態(tài)生成：從“空表”的初始狀態(tài)起，依次建立各元素結(jié)點(diǎn)，并逐個(gè)插入鏈表。voidCreateList_L(LinkList&L,intn){L=(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;}}如何將兩個(gè)有序鏈表合并為一個(gè)有序鏈表：voidMergeList_L(LinkList&La,LinkList&Lb,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);}12pa5Λ34Lb6ΛpbLaLcpcif(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;2.3.2循環(huán)鏈表循環(huán)鏈表（CircularLinkedList）特點(diǎn)：表中最后一個(gè)結(jié)點(diǎn)的指針域指向頭結(jié)點(diǎn)，整個(gè)鏈表形成一個(gè)環(huán)。由此，從表中任一結(jié)點(diǎn)出發(fā)均可找到表中其他結(jié)點(diǎn)。循環(huán)條件的判斷不是p或p->next是否為空，而是它們是否等于頭指針。HH在單鏈表中只有一個(gè)指示直接后繼的指針域，從某個(gè)結(jié)點(diǎn)出發(fā)只能順時(shí)針往后尋查其他結(jié)點(diǎn)。若要尋查結(jié)點(diǎn)的直接前驅(qū)，則需從表頭指針出發(fā)，為此，引出了雙向鏈表。在雙向鏈表的結(jié)點(diǎn)中有兩個(gè)指針域，其一指向直接后繼，另一指向直接前驅(qū)，用C語(yǔ)言描述為：typedefstructDulNode{ElemTypedata;structDulNode*prior;structDulNode*next;}DulNode,*DuLinkList;與單鏈表類似，雙向鏈表也是由指向頭結(jié)點(diǎn)的頭指針唯一確定，若將頭尾結(jié)點(diǎn)鏈接起來(lái)則構(gòu)成雙向循環(huán)鏈表。空的雙向循環(huán)鏈表則由只含一個(gè)自成雙環(huán)的頭結(jié)點(diǎn)表示。///在雙向鏈表中，若d為指向表中某一結(jié)點(diǎn)的指針，則有

d->next->prior=d->prior->next=d在對(duì)雙向鏈表進(jìn)行插入和刪除操作時(shí)，需同時(shí)修改兩個(gè)方向上的指針。abxstatusListInsert_Dul(DulLinkList&L,inti,ElemTypee){if(!(p=GetElemp_Dul(L,i)))returnERROR;//空表if(!(s=(DuLinkList)malloc(sizeof(DulNode))))returnERROR;//無(wú)足夠空間分配s->data=e;s->prior=p->prior;p->prior->next=s;s->next=p;p->prior=s;returnOK;}voidddeletenode(dlistnode*p){p–>prior–>next=p–>next;p–>next–>prior=p–>prior;free(p);}注意：與單鏈表的插入和刪除操作不同的是，在雙鏈表中插入和刪除必須同時(shí)修改兩個(gè)方向上的指針。上述兩個(gè)算法的時(shí)間復(fù)雜度均為O(1)。多項(xiàng)式相加問(wèn)題存儲(chǔ)結(jié)構(gòu)的選取

任一一元多項(xiàng)式可表示為Pn(x)=P0+P1x+P2x2+...+Pnxn，顯然，由其n+1個(gè)系數(shù)可惟一確定該多項(xiàng)式。故一元多項(xiàng)式可用一個(gè)僅存儲(chǔ)其系數(shù)的線性表來(lái)表示，多項(xiàng)式指數(shù)i隱含于Pi的序號(hào)中。P=(P0，P1，P2，...，Pn)

若采用順序存儲(chǔ)結(jié)構(gòu)來(lái)存儲(chǔ)這個(gè)線性表，那么多項(xiàng)式相加的算法實(shí)現(xiàn)十分容易，同位序元素相加即可。但當(dāng)多項(xiàng)式的次數(shù)很高而且變化很大時(shí)，采用這種順序存儲(chǔ)結(jié)構(gòu)極不合理。例如，多項(xiàng)式S(x)=1+3x+12x999需用一長(zhǎng)度為1000的線性表來(lái)表示，而表中僅有三個(gè)非零元素，這樣將大量浪費(fèi)內(nèi)存空間。此時(shí)可考慮另一種表示方法，如線性表S(x)可表示成S=((1,0)，(3,1),(12,999))，其元素包含兩個(gè)數(shù)據(jù)項(xiàng)：系數(shù)項(xiàng)和指數(shù)項(xiàng)。第二種多項(xiàng)式表示方法在計(jì)算機(jī)內(nèi)同樣對(duì)應(yīng)兩種存儲(chǔ)方式：順序存儲(chǔ)結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)當(dāng)只對(duì)多項(xiàng)式進(jìn)行訪問(wèn)、求值等不改變多項(xiàng)式指數(shù)(即表的長(zhǎng)度不變化)的操作時(shí)，宜采用順序存儲(chǔ)結(jié)構(gòu)；當(dāng)要對(duì)多項(xiàng)式進(jìn)行加法、減法、乘法等改變多項(xiàng)式指數(shù)的操作時(shí)，宜采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。抽象數(shù)據(jù)類型一元多項(xiàng)式的定義如下：ADTList{

數(shù)據(jù)對(duì)象：D={ai|ai∈Termset，i=1，2，…m，m>=0,Termset中的每個(gè)元素包含一個(gè)表示系數(shù)的實(shí)數(shù)和表示指數(shù)的實(shí)數(shù)}

數(shù)據(jù)關(guān)系：

R1={<ai-1,ai>|ai-1,ai∈D，且ai-1

中的指數(shù)<ai

中的指數(shù)}

基本操作：

CreatePoly(&P,m);

操作結(jié)果：輸入m項(xiàng)系數(shù)和指數(shù)，建立一元多項(xiàng)式

DestroyPolyn(&P);

初始條件：一元多項(xiàng)式P已存在。操作結(jié)果：銷毀一元多項(xiàng)式P。

PrintPolyp(P);

初始條件：一元多項(xiàng)式P已存在。操作結(jié)果：打印輸出一元多項(xiàng)式。

PolynLength(P)初始條件：一元多項(xiàng)式P已存在。操作結(jié)果：返回一元多項(xiàng)式P中的系數(shù)。AddPolyn(&Pa,&Pb)初始條件：一元多項(xiàng)式Pa和Pb已存在。操作結(jié)果：完成多項(xiàng)式相加運(yùn)算，即Pa=Pa+Pb,并銷毀一元多項(xiàng)式Pb。

SubstractPolyn(&Pa,&Pb);

初始條件：一元多項(xiàng)式Pa和Pb已存在。操作結(jié)果：完成多項(xiàng)式相減運(yùn)算，即Pa=Pa-Pb，并且銷毀一元多項(xiàng)式Pb。

MultiPolyp(&Pa,&Pb);

初始條件：一元多項(xiàng)式Pa和Pb已存在。操作結(jié)果：完成多項(xiàng)式相乘運(yùn)算，即Pa=Pa*Pb，并銷毀一元多項(xiàng)式Pb。}ADTPolynomial.例AH=1-10x6+2x8+7x14BH=-x4+10x6-3x10+8x14+4x18CH(x)=AH(x)+BH(x)它的單鏈表表示如圖一元多項(xiàng)式相加預(yù)算規(guī)則（假設(shè)指針qa和qb分別指向多項(xiàng)式A和B中的某個(gè)點(diǎn)）：指針qa所指結(jié)點(diǎn)的指數(shù)值<指針qb所指結(jié)點(diǎn)的指數(shù)值，則摘取qa指針?biāo)傅慕Y(jié)點(diǎn)插入到“和多項(xiàng)式”鏈表中；指針qa所指結(jié)點(diǎn)的指數(shù)值>指針qb所指結(jié)點(diǎn)的指數(shù)值，則摘取qb指針?biāo)傅慕Y(jié)點(diǎn)插入到“和多項(xiàng)式”鏈表中；指針qa所指結(jié)點(diǎn)的指數(shù)值=指針qb所指結(jié)點(diǎn)的指數(shù)值，則將兩個(gè)結(jié)點(diǎn)中的系數(shù)相加，若和數(shù)不為零，則修改qa所指結(jié)點(diǎn)的系數(shù)值，同時(shí)釋放qb所指結(jié)點(diǎn)；反之，從多項(xiàng)式A中刪除相應(yīng)結(jié)點(diǎn)，釋放指針qa和qb所指結(jié)點(diǎn)；typedefstruct{ float coef; //系數(shù) int len; //指數(shù)}term,ElemType;//兩個(gè)類型名TypedefLinkListpolynomial;//完成多項(xiàng)式相加運(yùn)算，即：Pa=Pa+Pb,并銷毀一元多項(xiàng)式voidAddPolyn(polynomial&Pa,polynomial&Pb){ ha=GetHead(Pa);hb=GetHead(Pb);//頭結(jié)點(diǎn)位置

qa=NextPos(ha); qb=NextPos(hb)；//開(kāi)始結(jié)點(diǎn)位置

while(qa&&qb) { a=GetCurElem(qa);b=GetCurElem(qb); switch(*cmp(a,b)){ case-1://多項(xiàng)式PA中當(dāng)前結(jié)點(diǎn)的指數(shù)小 ha=qa;qa=NextPos(Pa,qa);break;

case0: //兩者的指數(shù)值相等 sum=a.coef+b.coef; if(sum!=0.0){SetCurElem(qa,sum);ha=qa; } else{ DelFirst(ha,qa);FreeNode(qa);} DelFirst(hb,qb);FreeNode(qb);qb=NextPos(Pb,hb); qa=NextPos(Pa,qa);break; case1://多項(xiàng)式PB中當(dāng)前結(jié)點(diǎn)的指數(shù)小 DelFirst(hb,qb);InsFirst(ha,qb);qb=NextPos(Pb,hb);ha=NextPos(Pa,ha);break; } //EndofSwitch } //Endofwhile if(!ListEmpty(Pb))Append(Pa,qb);//鏈接Pb中剩余結(jié)點(diǎn)

FreeNode(hb);//釋Pb頭結(jié)點(diǎn) }//EndofAddPolyn()小結(jié)線性表是n(n≥0)個(gè)數(shù)據(jù)元素的序列因此線性表中除了第一個(gè)和最后一個(gè)元素之外都只有一個(gè)前驅(qū)和一個(gè)后繼。線性表中每個(gè)元素都有自己確定的位置，即“位序”。

n=0時(shí)的線性表稱為"空表"，它是線性表的一種特殊狀態(tài)，因此在寫線性表的操作算法時(shí)一定要考慮你的算法對(duì)空表的情況是否也正確。

順序表是線性表的順序存儲(chǔ)結(jié)構(gòu)的一種別稱。它的特點(diǎn)是以"存儲(chǔ)位置相鄰"表示兩個(gè)元素之間的前驅(qū)后繼關(guān)系。因此，順序表的優(yōu)點(diǎn)是可以隨機(jī)存取表中任意一個(gè)元素，其缺點(diǎn)是每作一次插入或刪除操作時(shí)，平均來(lái)說(shuō)必須移動(dòng)表中一半元素。常應(yīng)用于主要是為查詢而很少作插入和刪除操作，