數據結構第2章

1、第第2章章 線性表線性表 2.1 線性表的概念及運算線性表的概念及運算 2.2 線性表的順序存儲線性表的順序存儲 2.3 線性表的鏈式存儲線性表的鏈式存儲 2.4 一元多項式的表示及相加一元多項式的表示及相加 2.1 線性表的概念及運算線性表的概念及運算4. 線性表的邏輯結構線性表的邏輯結構 1. 線性表的定義線性表的定義 一個線性表是具有一個線性表是具有n個數據元素的有限序列。個數據元素的有限序列。記為記為(a1, , ai-1 , ai , ai+1 , , an)2. 線性表的長度線性表的長度 線性表中元素的個數線性表中元素的個數n (n=0), n=0時時,稱為空表。稱為空表。3. 位

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

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

4、 刪除刪除 ListDelete （&L, i, & e） 刪除刪除L的第的第i個位置上的數據元個位置上的數據元素素e，線性表的長度減，線性表的長度減1。 l 輸出輸出 ListDisplay （L） 按前后次序輸出線性表的所有元素。按前后次序輸出線性表的所有元素。 練習練習1：兩個線性表：兩個線性表LA和和LB分別表示兩個集合分別表示兩個集合A和和B， 現求一個新的集合現求一個新的集合A=AB。void union( List &La, List Lb) La_len = ListLength(La); Lb_len = ListLength(Lb); for( i=1; ib時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 )構造構造 Lc = ( 2, 3, 5, 6, 8, 8, 9, 15 )358La268Lb915Lcij2首先，首先，La_len = 3；Lb_len = 5；3ijij5ij6ij88jij9j15j算法結束算法結束！2.2 線性表的順序表示和實現線性表的順序表示和實現順序表：順序表： 按順序存按順序存儲

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

8、的數據元素在存儲結構中 仍然相鄰。仍然相鄰。 l 線性表的順序存儲結構是一種隨機存取線性表的順序存儲結構是一種隨機存取 的存儲結構。的存儲結構。 3. 順序表的描述：順序表的描述：typedef struct ElemType *elem； int length; /當前長度當前長度 int listsize; /分配的存儲容量分配的存儲容量 SqList； /ElemType elemMAXSIZE;typedef # ElemType; #為根據具體問題確定的數據類型為根據具體問題確定的數據類型typedef int Status;4. 順序表上基本運算的實現順序表上基本運算的實現 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個元素之前插入個元素之前插入“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 ) 算法時間復雜度算法時間復雜度:時間主要花在移動元素上，而移動元素的個數取決時間主要花在移動元素上，而移動元素的個數取決于插入元素位置。于插入元素位置。i=1，需移動，需移動 n 個元素；個元素；i=i，需移

12、動，需移動 n i +1 個元素；個元素；i=n+1，需移動，需移動 0 個元素；個元素；假設假設pi是在第是在第 i 個元素之前插入一個新元素的概率個元素之前插入一個新元素的概率則長度為則長度為 n 的線性表中插入一個元素所需移動元的線性表中插入一個元素所需移動元素次數的素次數的期望值期望值為為: Eis = pi (n i + 1)n+1i=1設在任何位置插入元素設在任何位置插入元素等概率等概率， pi = n+11Eis = (n i + 1) = n+11i=1n+12nO(n)圖圖 順序表中刪除元素順序表中刪除元素 順序表的刪除順序表的刪除：刪除第：刪除第5個元素，個元素，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;算法時間復雜度算法時間復雜度:時間主要花在移動元素上，而移動元素的個數取決時間主要花在移動元素上，而移動元素的個數取決于刪除元素位置。于刪除元素位置。i=1，需移動，需移動n - - 1 1個元素；個元素；i=i，需移動，需

14、移動n i 個元素；個元素；i=n，需移動，需移動0個元素；個元素；假設假設qi是刪除第是刪除第 i 個元素的概率個元素的概率則長度為則長度為 n 的線性表中刪除一個元素所需移動元的線性表中刪除一個元素所需移動元素次數的素次數的期望值期望值為為: Edl = qi (n i) ni=1設刪除任何位置的元素設刪除任何位置的元素等概率等概率， 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占用的內存空間。即逐一釋放全部結點占用的內存空間。即逐一釋放全部結點的空間。的空間。 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沒有數據結點沒有數據結點,則返回真則返回真,否則返回假。否則返回假。 int ListEmpt

17、y(LinkList L) return(L-next=NULL); (4)求線性表的長度求線性表的長度ListLength(L) 返回單鏈表返回單鏈表L中數據結點的個數。中數據結點的個數。 int ListLength(LinkList L) LinkList p=L;int i=0;while (p-next!=NULL) i+; p=p-next;return(i); (5)輸出線性表輸出線性表DispList(L) 逐一掃描單鏈表逐一掃描單鏈表L的每個數據結點的每個數據結點,并顯示各結點并顯示各結點的的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ā)，從頭結點（從頭結點（L-next）開始順著鏈域掃描；開始順著鏈域掃描； l用用j做計數器，累做計數器，累計當前掃描過的結計當前掃描過

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

20、個結點的過程個結點前插入一個結點的過程(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個結點的過程個結點的過程La1ai 1aianp(a) 尋找第i 1 個結點由 p 指向它La1a

21、i 1aianpai 1rr p next;p next p next next;free(r);(b) 刪除并釋放第i結點(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 指向新申請的結點s data c1(b) 申請新結點并賦值Lci 1s(c) 插入第一個結點Lc2c1cic1s(d) 插入第i個元素頭插法建立單鏈表頭插法建立單鏈表(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 指向新申請的結點空間sdatac1(b) 申請新結點并賦值Lc1s(c) 插入第一個結點Lc2c1rrr nexts；(d) 插入第二個結點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個值域與個值域與e相等的相等的結點結點,若存在這樣的結點若存在這樣的結點,則返回位置則返回位置,否則返回否則返回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); 練習：已知練習：已知L是帶頭結點的非空單鏈表，指針是帶頭結點的非空單鏈表，指針p所指的所指的結點既不是第一個結點，也不是最后一個結點結點既不是第一個結點，也不是最后一個結點l 刪除刪除*p結點的直接后繼結點的語句序列結點的直接后繼結點的語句序列 q = p-next; p-next = q-next; free(q);l 刪除刪除*p結點的直接前驅結點的語句序列結點的直接前驅結點的語句序列 q = L; while(q-next-next != p) q = q-next; s = q-next

26、; q-next = p; free(s);l 刪除刪除*p結點的語句序列結點的語句序列 q = L; while( q-next != p) q = q-next; q-next = p-next; free(p);l 刪除首元結點的語句序列刪除首元結點的語句序列 q = L-next; L-next = q-next; free(q);l 刪除最后一個結點的語句序列刪除最后一個結點的語句序列 while(p-next-next != NULL) p = p-next; q = p-next; p-next = NULL; free(q);鏈式結構的特點 非隨機存貯結構，所以取表元素要慢于順

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

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

29、靜態(tài)鏈表靜態(tài)鏈表有些高級程序設計語言并沒有指針類型，如有些高級程序設計語言并沒有指針類型，如FORTRAN和和JAVA。我們可以用數組來表示。我們可以用數組來表示和實現一個鏈表，稱為和實現一個鏈表，稱為靜態(tài)鏈表靜態(tài)鏈表。可定義如下：可定義如下：#define MAXSIZE 1000 /最多元素個數最多元素個數typedef struct ElemType data; int cur; /游標，指示器游標，指示器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; 第一個可用結點位置第一個可用結點位置 if(s0.cur) s0.cur = si.cur;lFree: /釋放釋放k結點結點 sk.cur = s0.cur; s0.cur = k;lInsert: /將將i插在插在r之后之后 si.cur = sr.cur; sr.cur = i;lDelete: ;/p為為k的直接前驅，釋放的直接前驅，釋放k sp.cur = sk.cur Free(k);單鏈表基礎要點單鏈表基礎要點l 在單鏈表中，不能從當前結點出發(fā)訪問到任一結點。在單鏈表中，不能從當前結點出發(fā)訪問到任一結點。l 在單鏈表

31、中，刪除某一指定結點時，必須找到該結在單鏈表中，刪除某一指定結點時，必須找到該結點的前驅結點。點的前驅結點。l 線性表的鏈式存儲結構是一種順序存取的存儲結構，線性表的鏈式存儲結構是一種順序存取的存儲結構，不具有隨機訪問任一元素的特點。不具有隨機訪問任一元素的特點。l 設置頭結點的作用：使在鏈表的第一個位置上的操設置頭結點的作用：使在鏈表的第一個位置上的操作和表中其它位置上的操作一致，無需進行特殊處作和表中其它位置上的操作一致，無需進行特殊處理，對空表和非空表的處理統(tǒng)一。理，對空表和非空表的處理統(tǒng)一。練習：練習：2.22寫一算法，對單鏈表實現就地逆置。寫一算法，對單鏈表實現就地逆置。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)鏈表是另一種形式的鏈式存儲結構；循環(huán)鏈表是另一種形式的鏈式存儲結構；l可從當前結點出發(fā)，訪問到任一結點；可從當前結點出發(fā)，訪問到任一結點；l循環(huán)單鏈表；循環(huán)單鏈表；l多重循環(huán)鏈表。多重循環(huán)鏈表。l單循環(huán)鏈表單循環(huán)鏈表La1ai 1aianL(a) 帶頭結點的空循環(huán)鏈表(b) 帶頭結點的循環(huán)單鏈表的一般形式a1ai 1aianrearrear*(r

33、earnext)*(c) 采用尾指針的循環(huán)單鏈表的一般形式設置尾指針設置尾指針rear, 比設頭指針更好。比設頭指針更好。連接兩個只設尾指針的單循環(huán)鏈表L1和L2 操作如下：操作如下：p= R1 next; /保存保存L1 的頭結點指針的頭結點指針R1-next=R2-next-next; /頭尾連接頭尾連接free(R2-next); /釋放第二個表的頭結點釋放第二個表的頭結點 R2-next=p; R2b1bna1anR1p例，取循環(huán)鏈表第例，取循環(huán)鏈表第 i 個元素。個元素。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)結束條件不是循環(huán)結束條件不是p是否為空是否為空，而是，而是p是否等于頭指針是否等于頭指針。雙鏈表 希望查找前驅的時間復雜度達到希望查找前驅的時間復雜度達到O(1)，我，我們可以用空間換時間們可以用空間換時間, ,每個結點再加一個指向每個結點再加一個指向前驅的指針域，使鏈表可以進行雙方向查找。前驅的

35、指針域，使鏈表可以進行雙方向查找。用這種結點結構組成的鏈表稱為用這種結點結構組成的鏈表稱為雙向鏈表雙向鏈表。 結點的結構結點的結構圖圖: priornextdata雙向鏈表的邏輯表示priordatanextLL2. 雙向鏈表雙向鏈表(Double Linked List)l 類型描述類型描述typedef struct DuLNode ElemType data; struct DuLNode *prior; struct DuLNode *next;DuLNode, *DuLinkList;prior data next前驅指針域 數據域后繼指針域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的直接后繼結點的語句序列的直接后繼結點的語

37、句序列 q = p-next; p-next = p-next-next; p-next-prior = p; free(q);l刪除刪除*p的直接前驅結點的語句序列的直接前驅結點的語句序列 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） 假設一個單循環(huán)鏈表，其結點含有三個域假設一個單循環(huán)鏈表，其結點含有三個域pre、data、link。其中。其中data為數據域；為數據域；pre為指針域，它的值為空指針為指針域，它的值為空指針（nul

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