順序表與鏈表的比較

1、第二章 線性表v線性表線性表v順序表順序表 v鏈表鏈表v順序表與鏈表的比較順序表與鏈表的比較線性表線性表定義：定義：n n（ 0 0）個數(shù)據(jù)元素的有限序列，記作個數(shù)據(jù)元素的有限序列，記作（a1, ai-1, ai, ai+1, an） 其中其中,ai 是表中數(shù)據(jù)元素，是表中數(shù)據(jù)元素，n 是表長度。是表長度。特點特點: n同一線性表中元素具有相同特性。同一線性表中元素具有相同特性。n相鄰數(shù)據(jù)元素之間存在序偶關(guān)系。相鄰數(shù)據(jù)元素之間存在序偶關(guān)系。n除第一個元素外，其他每一個元素有一個且僅除第一個元素外，其他每一個元素有一個且僅有一個直接前驅(qū)。有一個直接前驅(qū)。n除最后一個元素外，其他每一個元素有一個且

2、除最后一個元素外，其他每一個元素有一個且僅有一個直接后繼。僅有一個直接后繼。順序表順序表定義：定義：將線性表中的元素相繼存放在一將線性表中的元素相繼存放在一個個的存儲空間中。的存儲空間中。 存儲結(jié)構(gòu)：存儲結(jié)構(gòu)：數(shù)組。數(shù)組。特點：特點：線性表的順序存儲方式。線性表的順序存儲方式。存取方式：存取方式：順序存取順序存取順序存儲結(jié)構(gòu)示意圖順序存儲結(jié)構(gòu)示意圖45 89 90 67 40 78 0 1 2 3 4 5 順序表的存儲方式：順序表的存儲方式：LOC(a i+1) = LOC( a i )+lLOC(a i) = LOC(a1)+(i-1)*l a1 a2 a i an 1 2 i n a a+

3、l a+(i-1)*l a+(n-1)*l idle順序表（順序表（SeqList）的類型定義的類型定義#define ListSize 100 /最大允許長度最大允許長度typedef int ListData;typedef struct ListData * data; /存儲空間基址存儲空間基址 int length; /當前元素個數(shù)當前元素個數(shù) SeqList;順序表基本運算順序表基本運算n初始化初始化 void InitList ( SeqList & L ) L.data = ( ListData * ) malloc ( ListSize * sizeof ( ListData

4、 ) ); if ( L.data = NULL ) printf ( “存儲分配失敗存儲分配失敗!n” ); exit (1); L.length = 0; 按值查找按值查找找找x x在表中的位置，若查找成功，在表中的位置，若查找成功，返回表項的位置，否則返回返回表項的位置，否則返回-1-1int Find ( SeqList &L, ListData x ) int i = 0; while ( i L.length & L.datai != x ) i+; if ( i L.length ) return i; else return - -1; 按值查找按值查找判斷判斷x x是否在表中

5、是否在表中int IsIn ( SeqList &L, ListData x ) int i = 0,found=0;while ( i = 0 & i 0 & i 0 & i L.length ) return i-1 1;else return - -1; 插入插入221)(1)(1 0)1(011)(11=nnnnnnininnAMN25 34 57 16 48 09 63 0 1 2 3 4 5 6 750插入 x25 34 57 50 16 48 09 63 0 1 2 3 4 5 6 750i順序表插入時，平均數(shù)據(jù)移動次數(shù)順序表插入時，平均數(shù)據(jù)移動次數(shù)AMN在各表項在各表項插入概率

6、相等時插入概率相等時順序表的插入順序表的插入 int Insert ( SeqList &L, ListData x, int i ) /在表中第在表中第 i 個位置插入新元素個位置插入新元素 x if (i L.length | L.length = ListSize) return 0; /插入不成功插入不成功 else for ( int j = L.length; j i; j- ) L.dataj = L.dataj - -1; L.datai = x; L.length+; return 1; /插入成功插入成功 刪除刪除102121)(11)(1=ninnnninnAMN25 3

7、4 57 50 16 48 09 63 16刪除 x25 34 57 50 48 09 63 0 1 2 3 4 5 6 7順序表刪除平均數(shù)據(jù)移動次數(shù)順序表刪除平均數(shù)據(jù)移動次數(shù)AMN在各表項在各表項刪除概率相等時刪除概率相等時順序表的刪除順序表的刪除 int Delete ( SeqList &L, ListData x ) /在表中刪除已有元素在表中刪除已有元素 x int i = Find (L, x); /在表中查找在表中查找 x if ( i = 0 ) L.length - ; for ( int j = i; j L.length; j+ ) L.dataj = L.dataj+1

8、; return 1; /成功刪除成功刪除 return 0; /表中沒有表中沒有 x 順序表的應用順序表的應用:集合的集合的“并并”運算運算void Union ( SeqList &A, SeqList &B ) int n = Length ( A ); int m = Length ( B ); for ( int i = 0; i m; i+ ) int x = GetData ( B, i ); /在在B中取一元素中取一元素 int k = Find (A, x); /在在A中查找它中查找它 if ( k = - -1 ) /若未找到插入它若未找到插入它 Insert ( A, x

9、, n ); n+; 集合的集合的“交交”運算運算 void Intersection ( SeqList &A, SeqList &B ) int n = Length ( A ); int m = Length ( B ); int i = 0; while ( i -link = first ; first = newnode;（插入前）（插入前） （插入后）（插入后） firstnewnodenewnodefirst第二種情況：在鏈表中間插入第二種情況：在鏈表中間插入 newnode-link = p-link; p-link = newnode； ( (插入前插入前) () (插入后

10、插入后) )newnodepnewnodep第三種情況：在鏈表末尾插入第三種情況：在鏈表末尾插入 newnode-link = p-link; p-link = newnode；p ( (插入前插入前) () (插入后插入后) )newnodenewnodep 算法描述算法描述int Insert ( LinkList& first, ListData x, int i ) /在鏈表第在鏈表第 i 個結(jié)點處插入新元素個結(jié)點處插入新元素 x ListNode * p = first; int k = 0; while ( p != NULL & k -link; k+; /找第找第 i-1個結(jié)點

11、個結(jié)點 if ( p = NULL & first != NULL ) printf ( “無效的插入位置無效的插入位置!n” );/終止插入終止插入 return 0; ListNode * newnode = /創(chuàng)建新結(jié)點創(chuàng)建新結(jié)點 (ListNode *) malloc ( sizeof (ListNode) );newnode-data = x; if ( first = NULL | i = 1 ) /插入空表或非空表第一個插入空表或非空表第一個結(jié)點之前結(jié)點之前 newnode-link = first;/新結(jié)點成為第一個結(jié)點新結(jié)點成為第一個結(jié)點 if(first=NULL)last

12、=newnode;/若是空表，表尾指針若是空表，表尾指針指向新結(jié)點指向新結(jié)點 first = newnode; else /插在表中間或末尾插在表中間或末尾newnode-link = p-link; if(p-link =NULL)last=newnode;p-link = newnode; return 1; n刪除刪除在單鏈表中刪除在單鏈表中刪除ai結(jié)點結(jié)點 q = p-link; p-link = q-link;刪除前刪除前刪除后刪除后ai-1aiai+1pqpai-1ai+1aiint Delete ( LinkList& first, int i ) /在鏈表中刪除第在鏈表中刪除第

13、 i 個結(jié)點個結(jié)點 ListNode *p, *q; if ( i = 0 ) /刪除表中第刪除表中第 1 個結(jié)點個結(jié)點 q = first; first = first-link; else p = first; int k = 0; while ( p != NULL & k -link; k+; /找第找第 i- -1個結(jié)點個結(jié)點if ( p = NULL | p-link = NULL ) /找不到第i-1個結(jié)點 printf ( “無效的刪除位置!n” ); return 0; else /刪除中間結(jié)點或尾結(jié)點元素 q = p-link; p-link = q-link; if (q

14、=last) last=p;/刪除表尾結(jié)點 k= q-data; free ( q ); return k; /取出被刪結(jié)點數(shù)據(jù)并釋放q帶帶表頭結(jié)點表頭結(jié)點的單鏈表的單鏈表表頭結(jié)點表頭結(jié)點位于表的最前端，本身不帶數(shù)位于表的最前端，本身不帶數(shù)據(jù)，僅標志表頭。據(jù)，僅標志表頭。設(shè)置表頭結(jié)點的目的設(shè)置表頭結(jié)點的目的:簡化鏈表操作的實現(xiàn)。簡化鏈表操作的實現(xiàn)。非空表非空表 空表空表ana1firstfirst插入插入q-link = p-link; p-link = q;firstqfirstqfirstqfirstqpppp插入前插入前插入后插入后表頭表頭表尾表尾qq插入pp表中表中int Insert

15、 (LinkList first, ListData x, int i ) /將新元素將新元素 x 插入在鏈表中第插入在鏈表中第 i 號結(jié)點位置號結(jié)點位置 ListNode * p = Locate ( first, i-1 ); if ( p = NULL ) return 0; /參數(shù)參數(shù)i值不合理返回值不合理返回0 ListNode * newnode = /創(chuàng)建新結(jié)點創(chuàng)建新結(jié)點 (ListNode *) malloc (sizeof (ListNode) ); newnode-data = x; newnode-link = p-link; /鏈入鏈入 p-link = newnode

16、; return 1; 刪除刪除 q = p-link; p-link = q-link; delete q; 刪除前刪除前first(非空表）非空表）(空表）空表）firstfirstpqpqfirst刪除后刪除后int delete ( LinkList first, int i ) /將鏈表第將鏈表第 i 號元素刪去號元素刪去 ListNode * p, * qp = Locate ( first, i- -1 ); /尋找第尋找第i-1個個結(jié)點結(jié)點 if ( p = NULL | p-link = NULL) return 0;/i值不合理或空表值不合理或空表 q = p-link;

17、p-link = q-link; /刪除結(jié)點刪除結(jié)點 free ( q ); /釋放釋放 return 1;前插法建立單鏈表前插法建立單鏈表從一個空表開始，重復讀入數(shù)據(jù)：從一個空表開始，重復讀入數(shù)據(jù)：生成新結(jié)點生成新結(jié)點將讀入數(shù)據(jù)存放到新結(jié)點的數(shù)據(jù)域中將讀入數(shù)據(jù)存放到新結(jié)點的數(shù)據(jù)域中將該新結(jié)點插入到鏈表的前端將該新結(jié)點插入到鏈表的前端直到讀入結(jié)束符為止。直到讀入結(jié)束符為止。firstqfirstqLinkList createListF ( void ) char ch; ListNode *q; LinkList head = /建立表頭結(jié)點建立表頭結(jié)點 (LinkList) malloc

18、(sizeof (ListNode); head-link = NULL; while ( (ch = getchar( ) ) != n ) q = (ListNode *) malloc (sizeof(ListNode); q-data = ch; /建立新結(jié)點建立新結(jié)點 q-link = head-link; /插入到表前端插入到表前端 head-link = q; return head; 后插法建立單鏈表后插法建立單鏈表每次將新結(jié)點加在鏈表的表尾；每次將新結(jié)點加在鏈表的表尾；尾指針尾指針r ,總是指向表中最后一個結(jié)點，新結(jié)點總是指向表中最后一個結(jié)點，新結(jié)點插在它的后面；插在它的后面

19、；qfirstrfirstrLinkList createListR ( void ) char ch; LinkList head = /建立表頭結(jié)點建立表頭結(jié)點 (LinkList) malloc (sizeof (ListNode); ListNode *q, *r = head; while ( (ch = getchar( ) ) != n ) q = (ListNode *) malloc (sizeof(ListNode); q-data = ch; /建立新結(jié)點建立新結(jié)點 r -link = q; r =q; /插入到表末端插入到表末端 r -link = NULL; retu

20、rn head; 單鏈表清空單鏈表清空void makeEmpty ( LinkList first ) /刪去鏈表中除表頭結(jié)點外的所有其它結(jié)點刪去鏈表中除表頭結(jié)點外的所有其它結(jié)點 ListNode *q; while ( first-link != NULL ) /當鏈不空時，循環(huán)當鏈不空時，循環(huán)逐個刪去所有結(jié)點逐個刪去所有結(jié)點 q = first-link; first-link = q-link;free( q ); /釋放釋放 last=first; 計算單鏈表長度計算單鏈表長度int Length ( LinkList first ) ListNode *p = first-link

21、; /指針指針 p 指示第一個結(jié)點指示第一個結(jié)點int count = 0; while ( p != NULL ) /逐個結(jié)點檢測逐個結(jié)點檢測 p = p-link; count+; return count;按值查找按值查找ListNode * Find ( LinkList first, ListData value ) /在鏈表中從頭搜索其數(shù)據(jù)值為在鏈表中從頭搜索其數(shù)據(jù)值為value的結(jié)點的結(jié)點 ListNode * p = first-link; /指針指針 p 指示第一個結(jié)點指示第一個結(jié)點 while ( p != NULL & p-data != value ) p = p-li

22、nk; return p; 按序號查找（定位）按序號查找（定位）ListNode * Locate ( LinkList first, int i ) /返回表中第返回表中第 i 個元素的地址個元素的地址 if ( i 0 ) return NULL; ListNode * p = first; int k = 0 0; while ( p != NULL & k -link; k+; /找第找第 i 個結(jié)點個結(jié)點 if ( k = i ) return p; /返回第返回第 i 個結(jié)點地址個結(jié)點地址 else return NULL; 1ZHANG2WANG6LI5ZHAO5WU-1CHEN

23、31ZHANG2WANG3LI4ZHAO5WU-101234560123456修改前修改前（插入（插入chen,刪除刪除zhao)修改后修改后用一維數(shù)組描述線性鏈表用一維數(shù)組描述線性鏈表靜態(tài)鏈表靜態(tài)鏈表 定義定義const int MaxSize = 100; /靜態(tài)鏈表大小靜態(tài)鏈表大小typedef int ListData;typedef struct node /靜態(tài)鏈表結(jié)點靜態(tài)鏈表結(jié)點 ListData data; int link; SNode;typedef struct /靜態(tài)鏈表靜態(tài)鏈表 SNode NodesMaxSize; int newptr; /當前可分配空間首地址當前

24、可分配空間首地址 SLinkList;鏈表空間初始化鏈表空間初始化void InitList ( SLinkList* SL ) SL-Nodes0.link = 1; SL-newptr = 1; /當前可分配空間從當前可分配空間從 1 開始開始 /建立帶表頭結(jié)點的空鏈表建立帶表頭結(jié)點的空鏈表 for ( int i = 1; i Nodesi.link = i+1; /構(gòu)成空閑鏈接表構(gòu)成空閑鏈接表 SL-NodesMaxSize- -1.link = - -1; /鏈表收尾鏈表收尾在靜態(tài)鏈表中查找具有給定值的結(jié)點在靜態(tài)鏈表中查找具有給定值的結(jié)點int Find ( SLinkList SL

25、, ListData x ) int Find ( SLinkList SL, ListData x ) int p = SL.Nodes0.link; int p = SL.Nodes0.link; /指針指針 p p 指指向鏈表第一個結(jié)點向鏈表第一個結(jié)點while ( p != -1 )while ( p != -1 )/逐個查找有給定值的結(jié)點逐個查找有給定值的結(jié)點 if ( SL.Nodesp.data != x)if ( SL.Nodesp.data != x) p = SL.Nodesp.link; p = SL.Nodesp.link; else break; else break

26、;return p;return p; 在靜態(tài)鏈表中查找第在靜態(tài)鏈表中查找第 i 個結(jié)點個結(jié)點int Locate ( SLinkList SL, int i ) if ( i 0 ) return - -1;/參數(shù)不合理參數(shù)不合理 int j = 0, p = SL.Nodes0.link; while ( p != - -1 & j newptr; /分配結(jié)點分配結(jié)點 SL-newptr = SL-NodesSL-newptr.link; SL-Nodesq.data = x; SL-Nodesq.link = SL.Nodesp.link; SL-Nodesp.link = q; /插入

27、插入 return 1;在靜態(tài)鏈表中釋放第在靜態(tài)鏈表中釋放第 i 個結(jié)點個結(jié)點int Remove ( SLinkList* SL, int i ) int p = Locate ( SL, i- -1 ); if ( p = - -1 ) return 0; /找不到結(jié)點找不到結(jié)點 int q = SL-Nodesp.link; /第第 i 號結(jié)點號結(jié)點 SL-Nodesp.link = SL-Nodesq.link; SL-Nodesq.link = SL-newptr; /釋放釋放 SL-newptr = q; return 1;循環(huán)鏈表循環(huán)鏈表 (Circular List)特點特點:

28、最后一個結(jié)點的最后一個結(jié)點的 link 指針不為指針不為NULL，而，而是指向頭結(jié)點。只要已知表中某一結(jié)點的地址，是指向頭結(jié)點。只要已知表中某一結(jié)點的地址，就可搜尋所有結(jié)點的地址就可搜尋所有結(jié)點的地址存儲結(jié)構(gòu)存儲結(jié)構(gòu):鏈式存儲結(jié)構(gòu)鏈式存儲結(jié)構(gòu) 帶表頭結(jié)點的循環(huán)鏈表帶表頭結(jié)點的循環(huán)鏈表an-1firsta1a0first( (空表空表) )( (非空表非空表) )循環(huán)鏈表的插入循環(huán)鏈表的插入約瑟夫問題約瑟夫問題 用循環(huán)鏈表求解約瑟夫問題用循環(huán)鏈表求解約瑟夫問題 n 個人圍成一個圓圈，首先第個人圍成一個圓圈，首先第1個人從個人從1開始一開始一個人一個人順時針報數(shù)個人一個人順時針報數(shù), 報到第報到第

29、m個人，令其個人，令其出列。然后再從下一個人開始，從出列。然后再從下一個人開始，從1順時針報順時針報數(shù)，報到第數(shù)，報到第m個人，再令其出列，個人，再令其出列，如此下，如此下去去, 直到圓圈中只剩一個人為止。此人即為優(yōu)直到圓圈中只剩一個人為止。此人即為優(yōu)勝者。勝者。 例如例如 n = 8 m = 3約瑟夫問題的解法約瑟夫問題的解法#include #include “CircList.h”void Josephus ( int n, int m ) for ( int i=0; in- -1; i+ ) /執(zhí)行執(zhí)行n-1次次 for ( int j=0; jm- -1; j+ ) Next (

30、); /數(shù)數(shù)m-1個人個人 cout “Delete person ” getData ( ) endl; Remove ( ); /刪去刪去 void main ( ) CircList clist; int n, m; cout n m; for ( int i=1; i=n; i+ ) clist.insert (i); /形成約形成約瑟夫環(huán)瑟夫環(huán) clist.Josephus (n, m); /解決約瑟夫問題解決約瑟夫問題v多項式及其相加多項式及其相加 在多項式的鏈表表示中每個結(jié)點增加了一個在多項式的鏈表表示中每個結(jié)點增加了一個數(shù)據(jù)成員數(shù)據(jù)成員link，作為鏈接指針。，作為鏈接指針。

31、優(yōu)點是：優(yōu)點是： 多項式的項數(shù)可以動態(tài)地增長，不存在多項式的項數(shù)可以動態(tài)地增長，不存在存儲溢出問題。存儲溢出問題。 插入、刪除方便，不移動元素。插入、刪除方便，不移動元素。多項式鏈表的相加多項式鏈表的相加AH = 1 - 10 x6 + 2x8 +7x14BH = - x4 + 10 x6 - 3x10 + 8x14 +4x18 Polynomial operator + ( const Polynomial & ah, const Polynomial & bh ) Term *pa, *pb, *p; ListIterator Aiter ( ah.poly ); ListIterator

32、 Biter ( bh.poly ); /建立兩個多項式對象建立兩個多項式對象 Aiter、 Biter pa = pc = Aiter.First ( ); / pa 檢測指針檢測指針 p = pb = Biter.First ( ); / pb 檢測指針檢測指針 pa = Aiter.Next ( ); pb = Biter.Next( ); / pa, pb 越過表頭結(jié)點越過表頭結(jié)點 delete p;while ( Aiter.NotNull ( ) & Biter.NotNull ( ) ) switch ( compare ( paexp, pbexp ) ) case = : p

33、acoef = pacoef + pbcoef; p = pb; pb = Biter.Next ( ); delete p; if ( !pacoef ) p = pa; pa = Aiter.Next ( ); delete p; else pclink = pa; pc = pa; pa = Aiter.Next ( ); break; case : pclink = pb; pc = pb; pb = Biter.Next ( ); break; case -prior = first-next = first; /表頭結(jié)點的鏈指針指向自己表頭結(jié)點的鏈指針指向自己計算雙向循環(huán)鏈表的長度

34、計算雙向循環(huán)鏈表的長度int Length ( DblList first ) /計算帶表頭結(jié)點的雙向循環(huán)鏈表的長度計算帶表頭結(jié)點的雙向循環(huán)鏈表的長度 DblNode * p = first-next; int count = 0; while ( p != first ) p = p-next; count+; return count; 雙向循環(huán)鏈表的插入雙向循環(huán)鏈表的插入 (非空表非空表)q-prior = p;q-next = p-next;p-next = q;q-next-prior = q;在結(jié)點在結(jié)點 *p 后插入后插入25firstfirst314815pp31482515q雙向循環(huán)鏈表的插入雙向循環(huán)鏈表的插入 (空表空表)q-prior = p;q-next = p-next; p-next = q;q-next-prior = q; pqfirs