09級使用數(shù)據(jù)結(jié)構(gòu)第2章

1、返回主目錄 本 章 說 明2.1 線性表的類型定義2.2 線性表的順序表示和實現(xiàn)2.3 線性表的鏈式存儲結(jié)構(gòu)2.4 循環(huán)鏈表和雙向鏈2.5 一元多項式的表示及相加 本 章 小 結(jié)本章說明學習目標了解線性表的邏輯結(jié)構(gòu)特性是數(shù)據(jù)元素之間存在著線性關(guān)系，在計算機中表示這種關(guān)系的兩類不同的存儲結(jié)構(gòu)是順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)。用前者表示的線性表簡稱為順序表，用后者表示的線性表簡稱為鏈表。熟練掌握這兩類存儲結(jié)構(gòu)的描述方法以及線性表的基本操作在這兩種存儲結(jié)構(gòu)上的實現(xiàn)。能夠從時間和空間復雜度的角度綜合比較線性表兩種存儲結(jié)構(gòu)的不同特點及其適用場合。結(jié)合線性表類型的定義增強對抽象數(shù)據(jù)類型的理解。本章說明重點和難

2、點鏈表是本章的重點和難點。扎實的指針操作和內(nèi)存動態(tài)分配的編程技術(shù)是學好本章的基本要求，分清鏈表中指針 p 和結(jié)點 *p 之間的對應(yīng)關(guān)系，區(qū)分鏈表中的頭結(jié)點、頭指針和首元結(jié)點的不同所指以及循環(huán)鏈表、雙向鏈表的特點等。知識點線性表、順序表、鏈表、有序表線性結(jié)構(gòu)的特點：在數(shù)據(jù)元素的非空有限集中存在唯一的一個被稱做“第一個”的數(shù)據(jù)元素存在唯一的一個被稱做“最后一個”的數(shù)據(jù)元素除第一個之外，每個元素都只有一個前驅(qū)除最后一個之外，每個元素都只有一個后繼1.線性表定義：一個線性表是n個數(shù)據(jù)元素的有限序列。2.1 線性表的類型定義例如：英文字母（A，B，C，Z）是一個線性表。表中元素是一個字母。例如：星期（星

3、期日，星期一，星期二，星期六）是一個線性表。表中的數(shù)據(jù)元素是星期中一天的名稱。例如：在稍復雜的線性表中，一個數(shù)據(jù)元素可以是由若干個數(shù)據(jù)項組成的記錄，含有大量記錄線性表稱為文件。如，一個學校的學生健康情況登記表。姓 名學 號性別年齡班級健康狀況王小林790631男18計91健康陳 紅790632女20計91一般劉建平790633男21計91健康張立立790634男17計91神經(jīng)衰弱數(shù)據(jù)元素2.線性表的結(jié)構(gòu)特性綜上三個例子，我們可以如下描述線性表： 線性表是n0個數(shù)據(jù)元素a1，a2，ai-1，ai，ai+1，an的有限序列。線性表的長度定義為線性表中數(shù)據(jù)元素的個數(shù)n。當n=0時，為空表。n0時記為

4、（a1，a2，an） ai-1是ai的直接前驅(qū)，a1無直接前趨 ai+1是ai的直接后繼，an無直接后繼數(shù)據(jù)元素同構(gòu)，相鄰數(shù)據(jù)元素之間存在著序偶關(guān)系。所以可將線性表記為 （a1, , ai-1, ai, ai+1, an）數(shù)據(jù)元素在線性表中的位置只取決于它們自己的序號。數(shù)據(jù)元素之間的相對位置是線性的2.1 線性表的類型定義3.線性表的基本運算表的初始化求表長取（或修改）表中的結(jié)點查找結(jié)點插入結(jié)點刪除結(jié)點。 不是全部操作，不同的問題需要的操作不同。2.1 線性表的類型定義4.抽象數(shù)據(jù)類型線性表的定義P19 ADT List 數(shù)據(jù)對象：D=ai|aiElemSet, i=1,2,n,n=0 數(shù)據(jù)關(guān)

5、系：R1=|ai-1, aiD, i=1,2,n 基本操作： InitList(&L) /創(chuàng)建一個空的線性表L DestroyList(&L) /撤消L2.1 線性表的類型定義 ClearList(&L) /將L重置為空表 ListEmpty(L) /判L是否為空? 空為T ListLength(L) /返回表長度(元素個數(shù)) GetElemList(L,I,&e) /用e返回L中第i個數(shù)據(jù)元素的個數(shù)2.1 線性表的類型定義4.抽象數(shù)據(jù)類型線性表的定義P19 LocateElem(L, e, compare() ) /查找并返回第1個與e滿足關(guān)系compare()的元素的位序,若沒找到則返回0

6、 PriorElem(L, cur_e, &pre_e) /找cur_e并返回其前驅(qū)pre_e,否則操作失敗,pre_e無定義 NextElem(L, cur_e, &next_e) /找cur_e并返回其后繼next_e,否則操作失敗,next_e無定義 ListInsert(&L, i, e) ListDelete(&L, i, &e) ListTraverse(L, visit() /依次對L的元素調(diào)用visit(),如visit()失敗,則操作失敗ADT List2.1 線性表的類型定義 例2-1 兩個線性表LA、LB，將存在于線性表LB中而不在LA中的數(shù)據(jù)元素加入到線性表LA中。即L

7、A=LALB 算法思想：逐一取出LB中的元素，判斷是否在LA中，若不在,則插入之。 僅已知LA、LB （1）先求出LA、LB長度 （2）取LB中一元素=e，若LB取空則轉(zhuǎn)（4） （3）如e不在LA中，則插入到LA中，轉(zhuǎn)（2） （4）結(jié)束2.1 線性表的類型定義void unin(List &La，List Lb) La_len=(ListLength(La); Lb_len=(ListLength(Lb); for (i=1; ia,LB中取一元素=b, 否則轉(zhuǎn)（3） （2）若ac,否則b=c,轉(zhuǎn)（1） （3）若LA不空，則LA剩余部分放到LC尾 （4）若LB不空，則LA剩余部分放到LC尾vo

8、id MergeList(List La, List Lb, List &Lc) InitList(Lc); /建一空表LC i=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,

9、 +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時間復雜度：O(ListLength(LA) +ListLength(LB)算法2.22.1 線性表的類型定義2.2 線性表的順序表示和實現(xiàn)3.線性表的動態(tài)分配順序存儲結(jié)構(gòu)4.順序線性表的操作 2.順序表的特點 1.線性表的順序表示 5

10、.順序表的優(yōu)缺點 1.線性表的順序表示 定義：用一組地址連續(xù)的存儲單元存儲一個線性表的數(shù)據(jù)元素，稱為順序表。元素地址計算方法： 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ù)組下標元素序號M-1typedef int DATATYPE; #define M 1000DATATYPE dataM;例 typedef struct card int num; char name20; c

11、har author10; char publisher30; float price;DATATYPE;DATATYPE libraryM; 備用空間數(shù)據(jù)元素不是簡單類型時,可定義結(jié)構(gòu)體數(shù)組或動態(tài)申請和釋放內(nèi)存DATATYPE *pData = (DATATYPE *)malloc(M*sizeof(DATATYPE);free(pData); 2.順序表的特點 特點： 實現(xiàn)邏輯上相鄰物理地址相鄰 實現(xiàn)隨機存取2.2 線性表的順序表示和實現(xiàn)3.線性表的動態(tài)分配順序存儲結(jié)構(gòu)用一維數(shù)組定義一個線性表#define LIST_INIT_SIZE 100#define LISTINCREAMENT

12、10type struct ElemType *elem; /指向線性表起始地址的指針 int length; /線性表實際存放數(shù)據(jù)長度 int listsize; /線性表申請長度 SqList2.2 線性表的順序表示和實現(xiàn) 4.順序線性表的操作順序表容易實現(xiàn)訪問操作，可隨機存取元素。但插入和刪除操作主要是移動元素。(1)初始化操作算法思想：構(gòu)造一個空表。設(shè)置表的起始位置表長可用空間2.2 線性表的順序表示和實現(xiàn)線性表初始化算法2.3Status InitList_Sq(SqList &L)L.elem= (ElemType*) malloc(LIST_INIT_SIZE*sizeof(El

13、emType);If (!L.elem) exit(OVERFLOW);L.length=0; L.listsize= LIST_INIT_SIZE;Return OK;/InitList_Sq2.2 線性表的順序表示和實現(xiàn)（2）插入定義：線性表的插入是指在第i（1i n+1）個元素之前插入一個新的數(shù)據(jù)元素x，使長度為n的線性表 變成長度為n+1的線性表 需將第n至第i,共（n-i+1)個元素后移算法Ch2_1.c內(nèi)存a1a2aiai+1an01i-1V數(shù)組下標n-1in12i元素序號i+1nn+1內(nèi)存a1a2aiai+1an01i-1V數(shù)組下標n-1in12i元素序號i+1nn+1an-1x

14、X插入算法2.4 （在表L中的第i個元素之前插入e），見P24判i值的合法性，1i表長+1；判表的空間滿否？若滿則增加分配（動態(tài)分配）；從表元素n到i，依次后移一個位置；將e插入第i個位置，表長度增1。算法中定義的線性表是L，以結(jié)構(gòu)形式出現(xiàn)2.2 線性表的順序表示和實現(xiàn)Status ListInsert_Sq(SqList &L, int i, ElemType e )if (iL.length+1) return ERROR; /i不合法 if (L.length=L.listsize) /當前可用空間已滿 /增加分配 newbase=(ElemType*)realloc(L.elem, (

15、L.listsize+ LISTINCREMENT)sizeof(ElemType); if (!newbase) exit(OVERFLOW); L.elem=newbase; /新基址 L.listsize+= LISTINCREMENT; 插入算法2.4實現(xiàn)2.2 線性表的順序表示和實現(xiàn) q=&(L.elemi-1); /取插入位置 for (p=&(L.elemL.length-1); p=q; -p) *(p+1)=*p; /將ni位置的元素后移 *q=e; /插入e +L.length; /表長度+1 return OK;插入算法2.4實現(xiàn)2.2 線性表的順序表示和實現(xiàn)插入算法2.

16、4時間復雜度 可見插入元素的時間主要花費在移動元素上，而移動元素的個數(shù)主要取決于插入的位置。 設(shè)pi是在第i個元素之前插入一個元素的概率，則在長度為n的線性表中插入一個元素時需移動元素的平均次數(shù)為若在任何位置上插入元素都是等概率2.2 線性表的順序表示和實現(xiàn)（3）刪除算法思想：刪除第i個元素，將第（i+1）至第n個元素逐一向前移動一個位置，將長度為n/ListInsert_Sq(a1,a2ai-1,ai,ai+1an)變成長度為n=n-1的線性表(a1,a2ai-1, ai+1an) 需將第i+1至第n共（n-i)個元素前移算法Ch2_1.c內(nèi)存a1a2aiai+1an01i-1V數(shù)組下標n-

17、1i12i元素序號i+1n內(nèi)存a1a2ai+201i-1V數(shù)組下標n-1i12i元素序號i+1nanai+1刪除在表L中刪除第i個元素，放入e，見P24 判i值的合法性，1i表長n 取第i個元素，放入e 從i+1到表長n，依次前移 表長度減1刪除算法2.5思想2.2 線性表的順序表示和實現(xiàn)刪除算法2.5實現(xiàn)Status ListDelete_Sq(SqList &L, int i, ElemType &e )if ( (iL.length) ) return ERROR; /i不合法 p=&(L.elemi-1); /取被刪除元素位置 e=*p; /取插入位置 q=L.elem+L.Lengt

18、h-1; /取表尾元素的位置 for (+p; p=q; +p;) *(p-1)=*p; /將i+1n位置的元素前移 -L.length; /表長度+1 return OK;/ListInsert_Sq2.2 線性表的順序表示和實現(xiàn)刪除算法2.5時間復雜度 可見刪除元素的時間主要花費在移動元素上，而移動元素的個數(shù)主要取決于刪除的位置。 設(shè)qi是刪除第i個元素的概率，則在長度為n的線性表中刪除一個元素所需移動的元素次數(shù)的平均次數(shù)為若在任何位置上插入元素都是等概率2.2 線性表的順序表示和實現(xiàn)查找算法2.6Int LocateElem_Sq(SqList L,ElemType e, Status(

19、*compare)(ElemType, ElemType) /在順序線性表L中找第一個值與e滿足compare()的元素的位序，找到返回位序，否則返回0 i=1; p=L.elem; while (i=L.length&!(*compare)(*p+,e) +i; if (i=L.length) return i; else return 0;/ LocateElem_Sq 時間復雜度：O(L.length)2.2 線性表的順序表示和實現(xiàn)合并算法2.7實現(xiàn)Int MergeList_Sq(SqList La, SqList Lb, SqList &Lc) /已知順序線性表La和Lb的元素非遞減

20、排列，歸并得到線性表Lc，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);2.2 線性表的順序表示和實現(xiàn) pa_last=La.elem+La.length-1; pb_last=Lb.elem+Lb.length-1; while (pa=pa_last & pb=pb_last) /歸并 if (*pa=*

21、pb) *pc+=*pa+; else *pc+=*pb+; while (pa=pa_last) *pc+=*pa+; /插入La剩余部分 while (pbdata表示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 線性表的鏈式存儲結(jié)構(gòu)4. 鏈式存儲結(jié)構(gòu)的優(yōu)點 插入、刪除操作是不再需要移動大量的元素，但失去了順序表的可隨機存取特點。5.單鏈表的操作（1）取第i個元素算法思想：單鏈表是非隨

22、機存取結(jié)構(gòu)。每個元素的位置信息都包含在前驅(qū)結(jié)點的信息中，所以取得第i個元素必須從頭指針出發(fā)尋找。設(shè)置一個指針變量指向第一個結(jié)點，然后，讓該指針變量逐一向后指向，直到第i個元素。2.3 線性表的鏈式存儲結(jié)構(gòu)Status GetElem_L(LinkList L, int i, ElemType)/L為帶頭結(jié)點的單鏈表的頭指針。/當?shù)趇個元素存在時，其值賦給e并返回OK，否則返回ERROR p=Lnext; j=1; /p指向第一個結(jié)點，j做計數(shù)器 while(p & ji) return ERROR; e=pdata; return OK;/GetElem_L取結(jié)點算法2.82.3 線性表的鏈式

23、存儲結(jié)構(gòu)（2）插入操作： 要在數(shù)據(jù)元素a和b 之間插入元素x。算法思想：決定a和b之間的相鄰關(guān)系是由a的指針決定的。若要實現(xiàn)插入，生成x結(jié)點，然后讓a的指針指向x 且x的指針指向b。實現(xiàn)三個元a、x和b的邏輯關(guān)系。設(shè)p為指向結(jié)點a 的指針，s為指向結(jié)點x的指針，則修改s、a的指針：插入結(jié)點算法2.92.3 線性表的鏈式存儲結(jié)構(gòu)XsBAps-next=p-nextp-next= sXsBApStatus ListInsert_L(ListLInk &L, int i, ElemType e) /在帶頭結(jié)點的單鏈表L中第i個位置之前插入元素ep=L; j=0;while(p & ji-1) ret

24、urn ERROR; /i小于1或大于表長s=(LinkList)malloc(sizeof(LNode);sdata=e; snext=p-next;pnext=s;return OK;/ListInsert_L插入結(jié)點算法2.9實現(xiàn)2.3 線性表的鏈式存儲結(jié)構(gòu)BCApCAp（3）刪除操作p-next=p-next-next刪除結(jié)點算法2.10實現(xiàn)Status ListDelete_L(LinkList &L,int i,ElemType &e) /在帶頭結(jié)點的單鏈表L中刪除第i個元素，并由e返回 p=L; j=0; while (p-next & jnext; +j; /尋找第i個結(jié)點，并

25、令p指向其前驅(qū) if (!(p-next) | ji-1) return ERROR; q=p-next; p-next=q-next; e=q-data; free(q); return OK;/ListDelete_L 2.3 線性表的鏈式存儲結(jié)構(gòu)動態(tài)創(chuàng)建鏈表算法動態(tài)建立單鏈表算法：設(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)Void CreateList_L(LinkList &L, int n) /逆位序輸入n個元素值，建立帶頭結(jié)點的

26、單鏈表L L=（LinkList)malloc(sizeof(LNode); L-next=NULL; for (i=n; i0; -i) p=(LinkList)malloc(sizeof(LNode); scanf(&p-data); p-next=L-next; L-next=p; /CreatList_L2.3 線性表的鏈式存儲結(jié)構(gòu)（4）單鏈表的合并例：將兩個有序鏈表合并為一個有序鏈表。算法思想：設(shè)立三個指針pa、pb和pc分別用來指向兩個有序鏈表和合并表的當前元素。比較兩個表的當前元素的大小，將小的元素鏈接到合并表Lc中,讓合并表的當前指針指向該元素，然后，修改指針。在歸并兩個鏈表為

27、一個鏈表時，不需要另建新表的結(jié)點空間，而只需將原來兩個鏈表中結(jié)點之間的關(guān)系解除，重新建立關(guān)系。合并有序鏈表算法2.122.3 線性表的鏈式存儲結(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)Void MergeList_L(LinkList La, Lin

28、kList Lb, LinkList &Lc) pa=La-next; pb=Lb-next; Lc=pc=La; while (pa & pb) if (pa-data 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 線性表的鏈式存儲結(jié)構(gòu)6.靜態(tài)單鏈表 有些高級語言沒有指針，我們可以用數(shù)組來表示單鏈表，在數(shù)組中以整型游標來代替指針。這種用數(shù)組描述的鏈表稱為靜態(tài)鏈表。存儲結(jié)構(gòu)： #define MAXSIZE 1

29、000 typedef struct ElemType data; int cur; component, SLinklistMAXSIZE;Si.cur 指示第i+1個結(jié)點的位置。靜態(tài)鏈表的操作和動態(tài)鏈表相似，以整型游標代替動態(tài)指針。2.3 線性表的鏈式存儲結(jié)構(gòu)011ZHAO22QIAN33SUN44LI55ZHOU66WU77ZHENG88WANG0910011ZHAO22QIAN33SUN44LI55ZHOU66WU77ZHENG88WANG0910SHI9S0.cur為頭指針，可以遍歷整個靜態(tài)鏈表找到插入位置i011ZHAO22QIAN33SUN44LI95ZHOU66WU87ZHEN

30、G88WANG09SHI510刪除ZHENG, s6.cur=s7.curSHI85int LocateElem_SL(SLinkList S, ElemType e) /在靜態(tài)單鏈線性表L中查找第1個值為e的元素 / 找到返回位序，否則返回0 i=S0.cur; while (i & Si.data!=e) i=Si.cur; return i; /沒找到則到鏈尾，i=0/LocateElem_SL 算法2.13靜態(tài)鏈表查找 2.3 線性表的鏈式存儲結(jié)構(gòu)假設(shè)由終端輸入A集合元素并建立靜態(tài)鏈表S，然后輸入集合B元素在S中查找，若存在和B相同的元素，則從S中刪除之，否則插入到S中。算法思想：將整

31、個數(shù)組空間初始化成一個鏈表從備用空間取得一個結(jié)點將空閑結(jié)點鏈接到備用鏈表上例2-3 運算(A-B)U(B-A)2.3 線性表的鏈式存儲結(jié)構(gòu)01122334455667788991010003122c0344556677089910100Space0.cur是備用空閑鏈表的頭指針，space1.cur是鏈表的頭指針A=(c, b, e, g, f, d), B=(a, b, n, f)初始化后04122c33b0455667708991010005122c33b44e05667788991010006122c33b44e55g0677889910100Space0.cur是備用空閑鏈表的頭指針，

32、space1.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é)束取a，在A中找，沒有插入09122c33b44e55g66f77d88a091010003122c43b94e55g66f77d88a0910100刪b, space2.curA=(c, b, e, g, f, d

33、), B=(a, b, n, f) 取B中元素在A中查找，若有與其相同的，則將A中的同元素刪除，若沒有則在A中插入03122c43b94e55g66f77d88a091010009122c43n04e55g66f77d88a391010006122c43n04e55g76f97d88a3910100插入n刪除f，space5.cur=space6.curvoid InitSpace_SL(SLinkList &space) /將一維數(shù)組space中各分量鏈成一個備用鏈表 / space0.cur為頭指針，0表示空指針 for (i=0; iMAXSIZE-1; +i) spacei.cur=i

34、+1; spaceMAXSIZE-1.cur=0;/ InitSpace _SL int Malloc_SL(SLinkList &space) i=space0.cur; if (space0.cur) space0.cur=spacei.cur; return i;/Malloc_SL算法2.14 2.15靜態(tài)鏈表初始化 2.3 線性表的鏈式存儲結(jié)構(gòu) void Free_SL(SLinkList &space, int k) /將下標為k的空閑結(jié)點回收到備用鏈表 spacek.cur=space0.cur; space0.cur=k;/ Free _SL (2.16) void diffe

35、rece(SLinkList &space, int &S) /依次輸入集合A和B，在space中建立靜態(tài)鏈表，S為頭指針 /設(shè)space的備用空間足夠大，space0.cur為其頭指針， InitSpace_SL(space); /初始化備用空間 S=Malloc_SL(space); /生成S頭結(jié)點 r=S; scanf(m,n); /r指向表尾元素，輸入A,B元素個數(shù)算法2.16 2.17靜態(tài)鏈表初始化 2.3 線性表的鏈式存儲結(jié)構(gòu) for (j=1; j=m; +j) /建立集合A的鏈表 i=Malloc_SL(space); /分配結(jié)點，i為結(jié)點下標 scanf(spacei.dat

36、a); spacer.cur=i; r=i; /插入到表尾，r指向新表尾 /for spacer.cur=0; /創(chuàng)建結(jié)束，表尾的指針為空 for (j=1; jnext=NULL循環(huán)鏈表p-next=H 非空表空表HH2.雙向鏈表 在雙向鏈表的結(jié)點中有兩個指針域，分別指向前驅(qū)和后繼。雙向鏈表也可以有循環(huán)鏈表。雙向鏈表的存儲結(jié)構(gòu) typedef struct DuLNode ElemType data; struct DuLNode *prior; struct DuLNode *next; DuLNode, *DuLinklist;priordatanext2.4 循環(huán)鏈表和雙向鏈表 L空雙

37、向循環(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不存在；pnull，則為e申請結(jié)點, e賦值xs 插入 s-prior=p-prior p-prior-next=s s-next=p p

38、-prior=s算法實現(xiàn)刪除算法：刪除表L中第i個元素，賦于e。P37算法219 設(shè)P指針，p=GetElemP-DuL(L,i)，使其指向第i個結(jié)點 p p=null，則i不存在；若pnull，p指向第i個結(jié)點，將其賦給e 刪除 p-prior-next=p-next p-next-prior=p-priorHbca算法實現(xiàn)算法評價：T(n)=O(1)3.帶頭結(jié)點的線性鏈表類型類型定義：typedef struct LNode ElemType data; struct LNode *next *Link, *Position;typedef struct /鏈表類型 Link head,t

39、ail; int len; LinkList2.4 循環(huán)鏈表和雙向鏈表 操作 從實際應(yīng)用出發(fā)，重新定義了線性表及其基本操作?；静僮鞫x見P37 利用這些基本操作，很容易實現(xiàn)插入和刪除操作2.4 循環(huán)鏈表和雙向鏈表 算法2.20Status ListInsert_L(LinkList &L, int I, ElemType e) /在帶頭結(jié)點的單鏈表L的第i個元素之前插入元素e if ( !LocatePos(L, i-1, &h) return ERROR; /找第i-1個結(jié)點,h指向i-1結(jié)點 if ( !MakeNode(s,e) return ERROR;/結(jié)點申請失敗 InsFirs

40、t(h,s); /h指向頭結(jié)點,將s插在第一個結(jié)點之前 return OK;/ListInsert_L2.4 循環(huán)鏈表和雙向鏈表 Status MargeList_L(LinkList &La, LinkList &Lb, LinkList &Lc, int(*compare)(ElemType,ElemTYpe) ) if ( !InitList(Lc) return ERROR; ha=GetHead(La); hb= GetHead(Lb); pa=NextPos(La,ha); pb=NextPos(Lb,hb); while (pa&pb) a=GetCurElem(pa); b= GetCurElem(pb); if (*compare)(a,b)=0) /aexp與q-expp-exp 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é)束