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

1、第第2章章 線性表線性表 2.1 線性表的概念及運(yùn)算線性表的概念及運(yùn)算 2.2 線性表的順序存儲線性表的順序存儲 2.3 線性表的鏈?zhǔn)酱鎯€性表的鏈?zhǔn)酱鎯?2.4 一元多項(xiàng)式的表示及相加一元多項(xiàng)式的表示及相加 2.1 線性表的概念及運(yùn)算線性表的概念及運(yùn)算4. 線性表的邏輯結(jié)構(gòu)線性表的邏輯結(jié)構(gòu) 1. 線性表的定義線性表的定義 一個(gè)線性表是具有一個(gè)線性表是具有n個(gè)數(shù)據(jù)元素的有限序列。個(gè)數(shù)據(jù)元素的有限序列。記為記為(a1, , ai-1 , ai , ai+1 , , an)2. 線性表的長度線性表的長度 線性表中元素的個(gè)數(shù)線性表中元素的個(gè)數(shù)n (n=0), n=0時(shí)時(shí),稱為空表。稱為空表。3. 位

2、序位序 ai是第是第i個(gè)元素，稱個(gè)元素，稱i為數(shù)據(jù)元素為數(shù)據(jù)元素ai在線性表中的位序在線性表中的位序 。例子：例子： l英文字母表英文字母表(A, B, , Z) ；l車輛登記表車輛登記表 。5. 線性表的特點(diǎn)線性表的特點(diǎn) l同一性：線性表由同類數(shù)據(jù)元素組成，每一同一性：線性表由同類數(shù)據(jù)元素組成，每一個(gè)個(gè)ai必須屬于同一數(shù)據(jù)對象。必須屬于同一數(shù)據(jù)對象。 l有窮性：線性表由有限個(gè)數(shù)據(jù)元素組成，有窮性：線性表由有限個(gè)數(shù)據(jù)元素組成， 表表長度就是表中數(shù)據(jù)元素的個(gè)數(shù)。長度就是表中數(shù)據(jù)元素的個(gè)數(shù)。 l有序性：線性表中相鄰數(shù)據(jù)元素之間存在著有序性：線性表中相鄰數(shù)據(jù)元素之間存在著序偶關(guān)系序偶關(guān)系。 6. 線

3、性表的基本運(yùn)算線性表的基本運(yùn)算l 初始化初始化 InitList（&L） 建立一個(gè)空表。建立一個(gè)空表。l 求表長求表長 ListLength（L） 返回線性表的長度。返回線性表的長度。 l 讀表元素讀表元素 GetElem（L, i, &e) 用用e返回返回L中第中第i個(gè)數(shù)據(jù)元素的個(gè)數(shù)據(jù)元素的值。值。l 定位定位 LocateElem（L, e, compare()） 返回滿足關(guān)系的數(shù)據(jù)元返回滿足關(guān)系的數(shù)據(jù)元素的位序。素的位序。l 插入插入 ListInsert （&L, i, e） 在在L中第中第i個(gè)位置之前插入新的數(shù)個(gè)位置之前插入新的數(shù)據(jù)元素?fù)?jù)元素e，線性表的長度增，線性表的長度增1。 l

4、 刪除刪除 ListDelete （&L, i, & e） 刪除刪除L的第的第i個(gè)位置上的數(shù)據(jù)元個(gè)位置上的數(shù)據(jù)元素素e，線性表的長度減，線性表的長度減1。 l 輸出輸出 ListDisplay （L） 按前后次序輸出線性表的所有元素。按前后次序輸出線性表的所有元素。 練習(xí)練習(xí)1：兩個(gè)線性表：兩個(gè)線性表LA和和LB分別表示兩個(gè)集合分別表示兩個(gè)集合A和和B， 現(xiàn)求一個(gè)新的集合現(xiàn)求一個(gè)新的集合A=AB。void union( List &La, List Lb) La_len = ListLength(La); Lb_len = ListLength(Lb); for( i=1; ib時(shí)void M

5、ergeList( List La, List Lb, List &Lc) InitList(Lc); La_len = ListLength(La); Lb_len = ListLength(Lb); i=j=1; k=0; while( (i=La_len) & (j=Lb_len) GetElem(La, i, a); GetElem(Lb, j, b); if(a=b) ListInsert(Lc, +k, a); +i; else ListInsert(Lc, +k, b); +j; while(i=La_len) GetElem(La, i+, a); ListInsert(Lc,

6、 +k, a); while(j=Lb_len) GetElem(Lb, j+, b); ListInsert(Lc, +k, b); O(ListLength(La)+ListLength(Lb)例，例，La = ( 3, 5, 8 ) Lb = ( 2, 6, 8, 9, 15 )構(gòu)造構(gòu)造 Lc = ( 2, 3, 5, 6, 8, 8, 9, 15 )358La268Lb915Lcij2首先，首先，La_len = 3；Lb_len = 5；3ijij5ij6ij88jij9j15j算法結(jié)束算法結(jié)束！2.2 線性表的順序表示和實(shí)現(xiàn)線性表的順序表示和實(shí)現(xiàn)順序表：順序表： 按順序存按順序存儲

7、方式構(gòu)儲方式構(gòu)造的線性造的線性表。表。內(nèi)存空間狀態(tài)a1a2aianloc(a1) (n 1)kloc(a1) (i 1)kloc(a1)loc(a1) k存儲地址邏輯地址12in空閑 假設(shè)線性表中有假設(shè)線性表中有n個(gè)元素，每個(gè)元素占個(gè)元素，每個(gè)元素占k個(gè)單元，第一個(gè)元素的地址為個(gè)單元，第一個(gè)元素的地址為loc(a1)，則可，則可以通過如下公式計(jì)算出第以通過如下公式計(jì)算出第i個(gè)元素的地址個(gè)元素的地址loc(ai)： loc(ai) =loc(a1)+(i-1)k其中其中l(wèi)oc(a1)稱為基地址。稱為基地址。 2. 順序表的特點(diǎn)：順序表的特點(diǎn)：l 邏輯結(jié)構(gòu)中相鄰的數(shù)據(jù)元素在存儲結(jié)構(gòu)中邏輯結(jié)構(gòu)中相鄰

8、的數(shù)據(jù)元素在存儲結(jié)構(gòu)中 仍然相鄰。仍然相鄰。 l 線性表的順序存儲結(jié)構(gòu)是一種隨機(jī)存取線性表的順序存儲結(jié)構(gòu)是一種隨機(jī)存取 的存儲結(jié)構(gòu)。的存儲結(jié)構(gòu)。 3. 順序表的描述：順序表的描述：typedef struct ElemType *elem； int length; /當(dāng)前長度當(dāng)前長度 int listsize; /分配的存儲容量分配的存儲容量 SqList； /ElemType elemMAXSIZE;typedef # ElemType; #為根據(jù)具體問題確定的數(shù)據(jù)類型為根據(jù)具體問題確定的數(shù)據(jù)類型typedef int Status;4. 順序表上基本運(yùn)算的實(shí)現(xiàn)順序表上基本運(yùn)算的實(shí)現(xiàn) l 初

9、始化初始化 Status InitList_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; return OK;L.elem = new ElemTypeLIST_INIT_SIZE;順序表的插入順序表的插入：在表中第：在表中第4個(gè)元素之前插入個(gè)元素之前插入“21”。順序表中插入元素順序表中插入元素 49152830304251624915283

10、0304251624915283030425162序號移動元素插入元素21l 插入插入 Status ListInsert_Sq (SqList &L, int i, ElemType e) if( (iL.length+1) ) return ERROR; if(L.length = L.listsize) realloc(); .; / 越界處理越界處理 ； q = &(L.elemi-1); for( p = &(L.elemL.length-1; p=q; -p) *(p+1) = *p; *q = e; +L.length; return OK;/ 越界處理越界處理newbase =

11、 ( ElemType * ) realloc ( L.elem ， ( L.listsize + LISTINCREMENT ) * sizeof(ElemType) )；if ( ! newbase ) exit(OVERFLOW) ；L.elem = newbase ；L.listsize += LISTINCREMENT ； if ( L.length = L.listsize ) 算法時(shí)間復(fù)雜度算法時(shí)間復(fù)雜度:時(shí)間主要花在移動元素上，而移動元素的個(gè)數(shù)取決時(shí)間主要花在移動元素上，而移動元素的個(gè)數(shù)取決于插入元素位置。于插入元素位置。i=1，需移動，需移動 n 個(gè)元素；個(gè)元素；i=i，需移

12、動，需移動 n i +1 個(gè)元素；個(gè)元素；i=n+1，需移動，需移動 0 個(gè)元素；個(gè)元素；假設(shè)假設(shè)pi是在第是在第 i 個(gè)元素之前插入一個(gè)新元素的概率個(gè)元素之前插入一個(gè)新元素的概率則長度為則長度為 n 的線性表中插入一個(gè)元素所需移動元的線性表中插入一個(gè)元素所需移動元素次數(shù)的素次數(shù)的期望值期望值為為: Eis = pi (n i + 1)n+1i=1設(shè)在任何位置插入元素設(shè)在任何位置插入元素等概率等概率， pi = n+11Eis = (n i + 1) = n+11i=1n+12nO(n)圖圖 順序表中刪除元素順序表中刪除元素 順序表的刪除順序表的刪除：刪除第：刪除第5個(gè)元素，個(gè)元素，l 刪除刪

13、除 Status ListDelete_Sq (SqList &L, int i, ElemType &e) if( (iL.length) ) return ERROR; p = &(L.elemi-1); e = *p; q = L.elem+L.length-1; for( +p; p=q; +p) *(p-1) = *p; -L.length; return OK;算法時(shí)間復(fù)雜度算法時(shí)間復(fù)雜度:時(shí)間主要花在移動元素上，而移動元素的個(gè)數(shù)取決時(shí)間主要花在移動元素上，而移動元素的個(gè)數(shù)取決于刪除元素位置。于刪除元素位置。i=1，需移動，需移動n - - 1 1個(gè)元素；個(gè)元素；i=i，需移動，需

14、移動n i 個(gè)元素；個(gè)元素；i=n，需移動，需移動0個(gè)元素；個(gè)元素；假設(shè)假設(shè)qi是刪除第是刪除第 i 個(gè)元素的概率個(gè)元素的概率則長度為則長度為 n 的線性表中刪除一個(gè)元素所需移動元的線性表中刪除一個(gè)元素所需移動元素次數(shù)的素次數(shù)的期望值期望值為為: Edl = qi (n i) ni=1設(shè)刪除任何位置的元素設(shè)刪除任何位置的元素等概率等概率， qi = n1Edl = (n i) = n1i=1 n2n - - 1 1O(n)l順序表的歸并，表中元素非遞減排列。順序表的歸并，表中元素非遞減排列。void MergeList_Sq (SqList La, SqList Lb, SqList &Lc)

15、 pa = La.elem; pb = Lb.elem; Lc.listsize = Lc.length = La.length+Lb.length; pc = Lc.elem = (ElemType *)malloc(); 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

16、+ = *pa+; while(pbnext=NULL; (2)銷毀線性表銷毀線性表DestroyList(L) 釋放單鏈表釋放單鏈表L占用的內(nèi)存空間。即逐一釋放全部結(jié)點(diǎn)占用的內(nèi)存空間。即逐一釋放全部結(jié)點(diǎn)的空間。的空間。 void DestroyList(LinkList L) LinkList p=L, q=p-next;while (q!=NULL) free(p); p=q;q=p-next;free(p); (3)判線性表是否為空表判線性表是否為空表ListEmpty(L) 若單鏈表若單鏈表L沒有數(shù)據(jù)結(jié)點(diǎn)沒有數(shù)據(jù)結(jié)點(diǎn),則返回真則返回真,否則返回假。否則返回假。 int ListEmpt

17、y(LinkList L) return(L-next=NULL); (4)求線性表的長度求線性表的長度ListLength(L) 返回單鏈表返回單鏈表L中數(shù)據(jù)結(jié)點(diǎn)的個(gè)數(shù)。中數(shù)據(jù)結(jié)點(diǎn)的個(gè)數(shù)。 int ListLength(LinkList L) LinkList p=L;int i=0;while (p-next!=NULL) i+; p=p-next;return(i); (5)輸出線性表輸出線性表DispList(L) 逐一掃描單鏈表逐一掃描單鏈表L的每個(gè)數(shù)據(jù)結(jié)點(diǎn)的每個(gè)數(shù)據(jù)結(jié)點(diǎn),并顯示各結(jié)點(diǎn)并顯示各結(jié)點(diǎn)的的data域值。域值。 void DispList(LinkList L) LinkL

18、ist p=L-next;while (p!=NULL) printf(%c,p-data); p=p-next;printf(n); Status GetElem(LinkList L, int i, ElemType &e) p = L-next; j = 1; while( p & j next; +j; if (!p | ji) return ERROR; e = p-data; return OK;(6) 取表元素取表元素l從頭指針從頭指針L出發(fā)，出發(fā)，從頭結(jié)點(diǎn)（從頭結(jié)點(diǎn)（L-next）開始順著鏈域掃描；開始順著鏈域掃描； l用用j做計(jì)數(shù)器，累做計(jì)數(shù)器，累計(jì)當(dāng)前掃描過的結(jié)計(jì)當(dāng)前掃描過

19、的結(jié)點(diǎn)數(shù)，當(dāng)點(diǎn)數(shù)，當(dāng)j = i 時(shí)，時(shí)， 指針指針p所指的結(jié)點(diǎn)就所指的結(jié)點(diǎn)就是要找的第是要找的第i個(gè)結(jié)點(diǎn)。個(gè)結(jié)點(diǎn)。例，例，取第取第i=3個(gè)元素。個(gè)元素。ZhaoQian0Li LSunp = L- -nextj = 1p = p- -nextj = 2p = p- -nextj = 3e = p- -data = Sun時(shí)間復(fù)雜度時(shí)間復(fù)雜度:O(n)La1ai 1aianpre(a) 尋找第 i1 個(gè)結(jié)點(diǎn)es(b) 申請新的結(jié)點(diǎn)La1ai 1aianprees 與ai連鏈:snextprenextai-1與ai斷鏈,插入 e:prenexts；(c) 插入l在單鏈表第在單鏈表第i個(gè)結(jié)點(diǎn)前插入一

20、個(gè)結(jié)點(diǎn)的過程個(gè)結(jié)點(diǎn)前插入一個(gè)結(jié)點(diǎn)的過程(7) 插入插入Status ListInsert(LinkList &L, int i, ElemType e) p = L; j = 0; while (p & j next; +j if (!p | ji-1) return ERROR; s = (LinkList) malloc( sizeof (LNode) ); s-data = e; s-next = p-next; p-next = s; return OK;l 刪除單鏈表的第刪除單鏈表的第i個(gè)結(jié)點(diǎn)的過程個(gè)結(jié)點(diǎn)的過程La1ai 1aianp(a) 尋找第i 1 個(gè)結(jié)點(diǎn)由 p 指向它La1a

21、i 1aianpai 1rr p next;p next p next next;free(r);(b) 刪除并釋放第i結(jié)點(diǎn)(8) 刪除刪除Status ListDelete(LinkList &L, int i, ElemType &e) p = L; j = 0; while (p-next & j next; +j if (!(p-next) | ji-1) return ERROR; r = p-next; e = r-data; p-next = p-next-next; /(p-next = r-next;) free(r); return OK;l 動態(tài)建立單鏈表的過程動態(tài)建立單

22、鏈表的過程執(zhí) 行 的 語 句 組 為 :s next L next； L next s；L(a) 建空表c1ss 指向新申請的結(jié)點(diǎn)s data c1(b) 申請新結(jié)點(diǎn)并賦值Lci 1s(c) 插入第一個(gè)結(jié)點(diǎn)Lc2c1cic1s(d) 插入第i個(gè)元素頭插法建立單鏈表頭插法建立單鏈表(9) 頭插法建表頭插法建表CreateList_H(LinkList &L, int n) L = (LinkList) malloc( sizeof (LNode) ); L-next = NULL; for( i=n; i0; -i) s = (LinkList) malloc( sizeof (LNode) )

23、; scanf( &s-data); s-next = L-next; L-next = s; rs；r始終指向單鏈表的表尾L(a) 建空表c1ss 指向新申請的結(jié)點(diǎn)空間sdatac1(b) 申請新結(jié)點(diǎn)并賦值Lc1s(c) 插入第一個(gè)結(jié)點(diǎn)Lc2c1rrr nexts；(d) 插入第二個(gè)結(jié)點(diǎn)srl尾插法建表尾插法建表(10) 尾插法建表尾插法建表CreateList_T(LinkList &L, int n) tail = L = (LinkList) malloc( sizeof (LNode) ); L-next = NULL; for( i=n; i0; -i) s = (LinkList

24、) malloc( sizeof (LNode) ); scanf( &s-data); s-next = NULL; tail-next = s; tail = s; (11)按元素值查找按元素值查找LocateElem(L,e) 思路：在單鏈表思路：在單鏈表L中從頭開始找第中從頭開始找第1個(gè)值域與個(gè)值域與e相等的相等的結(jié)點(diǎn)結(jié)點(diǎn),若存在這樣的結(jié)點(diǎn)若存在這樣的結(jié)點(diǎn),則返回位置則返回位置,否則返回否則返回0。 int LocateElem(LinkList L,ElemType e) LinkList p=L-next;int n=1;while (p!=NULL & p-data!=e) p=

25、p-next; n+; if (p=NULL) return(0);else return(n); 練習(xí)：已知練習(xí)：已知L是帶頭結(jié)點(diǎn)的非空單鏈表，指針是帶頭結(jié)點(diǎn)的非空單鏈表，指針p所指的所指的結(jié)點(diǎn)既不是第一個(gè)結(jié)點(diǎn)，也不是最后一個(gè)結(jié)點(diǎn)結(jié)點(diǎn)既不是第一個(gè)結(jié)點(diǎn)，也不是最后一個(gè)結(jié)點(diǎn)l 刪除刪除*p結(jié)點(diǎn)的直接后繼結(jié)點(diǎn)的語句序列結(jié)點(diǎn)的直接后繼結(jié)點(diǎn)的語句序列 q = p-next; p-next = q-next; free(q);l 刪除刪除*p結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)的語句序列結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)的語句序列 q = L; while(q-next-next != p) q = q-next; s = q-next

26、; q-next = p; free(s);l 刪除刪除*p結(jié)點(diǎn)的語句序列結(jié)點(diǎn)的語句序列 q = L; while( q-next != p) q = q-next; q-next = p-next; free(p);l 刪除首元結(jié)點(diǎn)的語句序列刪除首元結(jié)點(diǎn)的語句序列 q = L-next; L-next = q-next; free(q);l 刪除最后一個(gè)結(jié)點(diǎn)的語句序列刪除最后一個(gè)結(jié)點(diǎn)的語句序列 while(p-next-next != NULL) p = p-next; q = p-next; p-next = NULL; free(q);鏈?zhǔn)浇Y(jié)構(gòu)的特點(diǎn) 非隨機(jī)存貯結(jié)構(gòu)，所以取表元素要慢于順

27、非隨機(jī)存貯結(jié)構(gòu)，所以取表元素要慢于順序表。序表。 節(jié)約了大塊內(nèi)存 適合于插入和刪除操作適合于插入和刪除操作 實(shí)際上用空間換取了時(shí)間，結(jié)點(diǎn)中加入了指針，使得這兩種操作轉(zhuǎn)換為指針操作;線性表實(shí)現(xiàn)方法的比較 實(shí)現(xiàn)不同實(shí)現(xiàn)不同順序表方法簡單，各種高級語言中都有數(shù)組類型，順序表方法簡單，各種高級語言中都有數(shù)組類型，容易實(shí)現(xiàn)；鏈表的操作是基于指針的，相對來講復(fù)容易實(shí)現(xiàn)；鏈表的操作是基于指針的，相對來講復(fù)雜些。雜些。 存儲空間的占用和分配不同存儲空間的占用和分配不同從存儲的角度考慮，順序表的存儲空間是靜態(tài)分配從存儲的角度考慮，順序表的存儲空間是靜態(tài)分配的，在程序執(zhí)行之前必須明確規(guī)定它的存儲規(guī)模，的，在程序執(zhí)

28、行之前必須明確規(guī)定它的存儲規(guī)模，也就是說事先對也就是說事先對“MAXSIZE”要有合適的設(shè)定，過要有合適的設(shè)定，過大造成浪費(fèi)，過小造成溢出。而鏈表是動態(tài)分配存大造成浪費(fèi)，過小造成溢出。而鏈表是動態(tài)分配存儲空間的，不用事先估計(jì)存儲規(guī)模?？梢妼€性表儲空間的，不用事先估計(jì)存儲規(guī)模?？梢妼€性表的長度或存儲規(guī)模難以估計(jì)時(shí)，采用鏈表。的長度或存儲規(guī)模難以估計(jì)時(shí)，采用鏈表。 線性表運(yùn)算的實(shí)現(xiàn)不同線性表運(yùn)算的實(shí)現(xiàn)不同 按序號訪問數(shù)據(jù)元素，使用順序表優(yōu)于鏈表。按序號訪問數(shù)據(jù)元素，使用順序表優(yōu)于鏈表。插入刪除操作插入刪除操作 ，使用鏈表優(yōu)于順序表。，使用鏈表優(yōu)于順序表。 l作業(yè)：作業(yè)： 2.4 2.19 3.

29、靜態(tài)鏈表靜態(tài)鏈表有些高級程序設(shè)計(jì)語言并沒有指針類型，如有些高級程序設(shè)計(jì)語言并沒有指針類型，如FORTRAN和和JAVA。我們可以用數(shù)組來表示。我們可以用數(shù)組來表示和實(shí)現(xiàn)一個(gè)鏈表，稱為和實(shí)現(xiàn)一個(gè)鏈表，稱為靜態(tài)鏈表靜態(tài)鏈表?？啥x如下：可定義如下：#define MAXSIZE 1000 /最多元素個(gè)數(shù)最多元素個(gè)數(shù)typedef struct ElemType data; int cur; /游標(biāo)，指示器游標(biāo)，指示器component, SLinkListMAXSIZE; data cur 0 6 1 2 2 a 3 3 b 4 4 c 5 5 d 0 6 7 7 0 li = si.cur; 指

30、針后移操作指針后移操作lMalloc: i = s0.cur; 第一個(gè)可用結(jié)點(diǎn)位置第一個(gè)可用結(jié)點(diǎn)位置 if(s0.cur) s0.cur = si.cur;lFree: /釋放釋放k結(jié)點(diǎn)結(jié)點(diǎn) sk.cur = s0.cur; s0.cur = k;lInsert: /將將i插在插在r之后之后 si.cur = sr.cur; sr.cur = i;lDelete: ;/p為為k的直接前驅(qū)，釋放的直接前驅(qū)，釋放k sp.cur = sk.cur Free(k);單鏈表基礎(chǔ)要點(diǎn)單鏈表基礎(chǔ)要點(diǎn)l 在單鏈表中，不能從當(dāng)前結(jié)點(diǎn)出發(fā)訪問到任一結(jié)點(diǎn)。在單鏈表中，不能從當(dāng)前結(jié)點(diǎn)出發(fā)訪問到任一結(jié)點(diǎn)。l 在單鏈表

31、中，刪除某一指定結(jié)點(diǎn)時(shí)，必須找到該結(jié)在單鏈表中，刪除某一指定結(jié)點(diǎn)時(shí)，必須找到該結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)。點(diǎn)的前驅(qū)結(jié)點(diǎn)。l 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)是一種順序存取的存儲結(jié)構(gòu)，線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)是一種順序存取的存儲結(jié)構(gòu)，不具有隨機(jī)訪問任一元素的特點(diǎn)。不具有隨機(jī)訪問任一元素的特點(diǎn)。l 設(shè)置頭結(jié)點(diǎn)的作用：使在鏈表的第一個(gè)位置上的操設(shè)置頭結(jié)點(diǎn)的作用：使在鏈表的第一個(gè)位置上的操作和表中其它位置上的操作一致，無需進(jìn)行特殊處作和表中其它位置上的操作一致，無需進(jìn)行特殊處理，對空表和非空表的處理統(tǒng)一。理，對空表和非空表的處理統(tǒng)一。練習(xí)：練習(xí)：2.22寫一算法，對單鏈表實(shí)現(xiàn)就地逆置。寫一算法，對單鏈表實(shí)現(xiàn)就地逆置。void R

32、everse_L( LinkList &L) p = L-next; L-next = NULL; while(p != NULL) q = p; p = p-next; q-next = L-next; L-next = q; 循環(huán)鏈表循環(huán)鏈表l循環(huán)鏈表是另一種形式的鏈?zhǔn)酱鎯Y(jié)構(gòu)；循環(huán)鏈表是另一種形式的鏈?zhǔn)酱鎯Y(jié)構(gòu)；l可從當(dāng)前結(jié)點(diǎn)出發(fā)，訪問到任一結(jié)點(diǎn)；可從當(dāng)前結(jié)點(diǎn)出發(fā)，訪問到任一結(jié)點(diǎn)；l循環(huán)單鏈表；循環(huán)單鏈表；l多重循環(huán)鏈表。多重循環(huán)鏈表。l單循環(huán)鏈表單循環(huán)鏈表La1ai 1aianL(a) 帶頭結(jié)點(diǎn)的空循環(huán)鏈表(b) 帶頭結(jié)點(diǎn)的循環(huán)單鏈表的一般形式a1ai 1aianrearrear*(r

33、earnext)*(c) 采用尾指針的循環(huán)單鏈表的一般形式設(shè)置尾指針設(shè)置尾指針rear, 比設(shè)頭指針更好。比設(shè)頭指針更好。連接兩個(gè)只設(shè)尾指針的單循環(huán)鏈表L1和L2 操作如下：操作如下：p= R1 next; /保存保存L1 的頭結(jié)點(diǎn)指針的頭結(jié)點(diǎn)指針R1-next=R2-next-next; /頭尾連接頭尾連接free(R2-next); /釋放第二個(gè)表的頭結(jié)點(diǎn)釋放第二個(gè)表的頭結(jié)點(diǎn) R2-next=p; R2b1bna1anR1p例，取循環(huán)鏈表第例，取循環(huán)鏈表第 i 個(gè)元素。個(gè)元素。p = L- -next ；j = 1 1 ；while ( p != L & j next ；+j ；if (

34、p = L | j i ) return ERROR ；e = p- -data ；return OK ；Status GetElem_L ( LinkList L，int i，ElemType &e ) 操作與線性單鏈表基本一致，差別只是在于算法中的操作與線性單鏈表基本一致，差別只是在于算法中的循環(huán)結(jié)束條件不是循環(huán)結(jié)束條件不是p是否為空是否為空，而是，而是p是否等于頭指針是否等于頭指針。雙鏈表 希望查找前驅(qū)的時(shí)間復(fù)雜度達(dá)到希望查找前驅(qū)的時(shí)間復(fù)雜度達(dá)到O(1)，我，我們可以用空間換時(shí)間們可以用空間換時(shí)間, ,每個(gè)結(jié)點(diǎn)再加一個(gè)指向每個(gè)結(jié)點(diǎn)再加一個(gè)指向前驅(qū)的指針域，使鏈表可以進(jìn)行雙方向查找。前驅(qū)的

35、指針域，使鏈表可以進(jìn)行雙方向查找。用這種結(jié)點(diǎn)結(jié)構(gòu)組成的鏈表稱為用這種結(jié)點(diǎn)結(jié)構(gòu)組成的鏈表稱為雙向鏈表雙向鏈表。 結(jié)點(diǎn)的結(jié)構(gòu)結(jié)點(diǎn)的結(jié)構(gòu)圖圖: priornextdata雙向鏈表的邏輯表示priordatanextLL2. 雙向鏈表雙向鏈表(Double Linked List)l 類型描述類型描述typedef struct DuLNode ElemType data; struct DuLNode *prior; struct DuLNode *next;DuLNode, *DuLinkList;prior data next前驅(qū)指針域 數(shù)據(jù)域后繼指針域La1a2a3L(a) 空的雙向循環(huán)鏈表(

36、b) 非空的雙向循環(huán)鏈表l雙向循環(huán)鏈表雙向循環(huán)鏈表p-next-prior = p-prior-next;pl雙向鏈表的前雙向鏈表的前(后后)插入操作插入操作abspcs-prior = p-prior; p-prior-next = s; s-next = p; p-prior = s;qs-next = q-next; q-next-prior= s; s-prior = q; q-next = s;abcpl雙向鏈表的刪除操作雙向鏈表的刪除操作p-prior-next = p-next;p-next-prior = p-prior;l刪除刪除*p的直接后繼結(jié)點(diǎn)的語句序列的直接后繼結(jié)點(diǎn)的語

37、句序列 q = p-next; p-next = p-next-next; p-next-prior = p; free(q);l刪除刪除*p的直接前驅(qū)結(jié)點(diǎn)的語句序列的直接前驅(qū)結(jié)點(diǎn)的語句序列 q = p-prior; p-prior = p-prior-prior; p- prior-next = p; free(q); l作業(yè)：作業(yè)：2.8 2.9 循環(huán)鏈表算法舉例循環(huán)鏈表算法舉例 （1 1） 假設(shè)一個(gè)單循環(huán)鏈表，其結(jié)點(diǎn)含有三個(gè)域假設(shè)一個(gè)單循環(huán)鏈表，其結(jié)點(diǎn)含有三個(gè)域pre、data、link。其中。其中data為數(shù)據(jù)域；為數(shù)據(jù)域；pre為指針域，它的值為空指針為指針域，它的值為空指針（nul

38、l）；）；link為指針域，它指向后繼結(jié)點(diǎn)。請?jiān)O(shè)計(jì)算法，將為指針域，它指向后繼結(jié)點(diǎn)。請?jiān)O(shè)計(jì)算法，將此表改成雙向循環(huán)鏈表。此表改成雙向循環(huán)鏈表。void SToDouble（DuLinkList la）/ la是結(jié)點(diǎn)含有是結(jié)點(diǎn)含有pre，data，link三個(gè)域的單循環(huán)鏈表。其中三個(gè)域的單循環(huán)鏈表。其中data為數(shù)據(jù)域；為數(shù)據(jù)域； pre為空指針域，為空指針域，link是指向后繼的指針域。是指向后繼的指針域。本算法將其改造成雙向循環(huán)鏈表。本算法將其改造成雙向循環(huán)鏈表。while（la-link-pre=null） la-link-pre=la/將結(jié)點(diǎn)將結(jié)點(diǎn)la后繼的后繼的pre指針指向指針指向la la=la-link； /la指針后移指針后移 /算法結(jié)束算法結(jié)束循環(huán)鏈表算法舉例循環(huán)鏈表算法舉例（2）已知一雙向循環(huán)鏈表，從第二個(gè)結(jié)點(diǎn)至表尾遞增有序，已知一雙向循環(huán)鏈表，從第二個(gè)結(jié)點(diǎn)至表尾遞增有序，（設(shè)（設(shè)a1xan）如下圖。試編寫程序，將第一個(gè)結(jié)點(diǎn)刪）如下圖。試編寫程序，將第一個(gè)結(jié)點(diǎn)刪除并插入表中適當(dāng)位置，使整個(gè)鏈表遞增有序除并插入表中適當(dāng)位置，使整個(gè)鏈表遞增有序 x a1 a2 anLvoid DInsert（DuLinkList &L） L是無頭結(jié)點(diǎn)的雙向循環(huán)鏈表，