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

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

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

4、( ListSize * sizeof ( ListData ) ); if ( L.data = NULL ) printf ( “存儲(chǔ)分配失敗存儲(chǔ)分配失敗!n” ); exit (1); L.length = 0; 順序搜索圖示 x = 48 x = 50按值查找按值查找找找x x在表中的位置，若查找成功，在表中的位置，若查找成功，返回表項(xiàng)的位置，否則返回返回表項(xiàng)的位置，否則返回-1-1int Find ( SeqList &L, ListData x ) int i = 0; while ( i L.length & L.datai != x ) i+; if ( i L

5、.length ) return i; else return - -1; niniicpACN10=212)(11)2(111)(1=10nnnnnninACNni 按值查找按值查找判斷判斷x x是否在表中是否在表中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

6、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í)，平均數(shù)據(jù)移動(dòng)次數(shù)順序表插入時(shí)，平均數(shù)據(jù)移動(dòng)次數(shù)AMN在各表項(xiàng)在各表項(xiàng)插入概率相等時(shí)插入概率相等時(shí)順序表的插入順序表的插入 int Insert ( SeqList &L, ListData x, int i ) /在表中第在表中第 i 個(gè)位置插入新元素個(gè)位置插入新元素 x if (i L.length | L.length = ListSize) return 0; /插入不成功插入不成功 else for ( int j

7、= L.length; j i; j- ) L.dataj = L.dataj - -1; L.datai = x; L.length+; return 1; /插入成功插入成功 刪除刪除102121)(11)(1=ninnnninnAMN25 34 57 50 16 48 09 63 16刪除 x25 34 57 50 48 09 63 0 1 2 3 4 5 6 7順序表刪除平均數(shù)據(jù)移動(dòng)次數(shù)順序表刪除平均數(shù)據(jù)移動(dòng)次數(shù)AMN在各表項(xiàng)在各表項(xiàng)刪除概率相等時(shí)刪除概率相等時(shí)順序表的刪除順序表的刪除 int Delete ( SeqList &L, ListData x ) /在表中刪除已有

8、元素在表中刪除已有元素 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; return 1; /成功刪除成功刪除 return 0; /表中沒有表中沒有 x 順序表的應(yīng)用順序表的應(yīng)用:集合的集合的“并并”運(yùn)算運(yùn)算void Union ( SeqList &A, SeqList &B ) int n = Length ( A ); int m = Length ( B ); for ( int i

9、 = 0; i m; i+ ) int x = GetData ( B, i ); /在在B中取一元素中取一元素 int k = Find (A, x); /在在A中查找它中查找它 if ( k = - -1 ) /若未找到插入它若未找到插入它 Insert ( A, x, n ); n+; 集合的集合的“交交”運(yùn)算運(yùn)算 void Intersection ( SeqList &A, SeqList &B ) int n = Length ( A ); int m = Length ( B ); int i = 0; while ( i n ) int x = GetData

10、( A, i ); /在在A中取一元素中取一元素 int k = Find ( B, x ); /在在B中查找它中查找它if ( k = - -1 ) Delete ( A, i ); n-; else i+; /未找到在未找到在A中刪除它中刪除它 iniinnnxaxaxaxaaxP02210 )( n階多項(xiàng)式階多項(xiàng)式Pn(x)有有n+1項(xiàng)。項(xiàng)。 系數(shù)系數(shù) a0, a1, a2, , an 指數(shù)指數(shù) 0, 1, 2, , n。按升冪排列。按升冪排列class Polynomial public: Polynomial ( ); /構(gòu)造函數(shù)構(gòu)造函數(shù) int operator ! ( ); /判

11、斷是否零多項(xiàng)式判斷是否零多項(xiàng)式 Coefficient Coef (Exponent e); Exponent LeadExp ( ); /返回最大指數(shù)返回最大指數(shù) Polynomial Add (Polynomial poly); Polynomial Mult (Polynomial poly); float Eval ( float x); /求值求值 #include class power double x; int e; double mul; public: power (double val, int exp); double get_power ( ) return mul;

12、 ; power:power (double val, int exp) /按按val值計(jì)算乘冪值計(jì)算乘冪 x = val; e = exp; mul = 1.0; if (exp = 0 ) return; for ( ; exp0; exp-) mul = mul * x; main ( ) power pwr ( 1.5, 2 ); cout pwr.get_power ( ) “n”; private: int degree; float coef maxDegree+1; pl.degree = n pl.coefi = ai, 0 i nprivate: int degree; f

13、loat * coef; Polynomial:Polynomial (int sz) degree = sz; coef = new float degree + 1; ： class Polynomial;class term /多項(xiàng)式的項(xiàng)定義多項(xiàng)式的項(xiàng)定義friend Polynomial;private: float coef; /系數(shù)系數(shù) int exp; /指數(shù)指數(shù);class Polynomial /多項(xiàng)式定義多項(xiàng)式定義public: private: static term termArrayMaxTerms; /項(xiàng)數(shù)組項(xiàng)數(shù)組 static int free; /當(dāng)前空閑位置指

14、針當(dāng)前空閑位置指針 / term Polynomial:termArrayMaxTerms; / int Polynomial:free = 0; int start, finish; /多項(xiàng)式始末位置多項(xiàng)式始末位置 A(x) = 2.0 x1000+1.8 B(x) = 1.2 + 51.3x50 + 3.7x101 兩個(gè)多項(xiàng)式存放在兩個(gè)多項(xiàng)式存放在termArray中中Polynomial Polynomial:Add ( Polynomial B ) Polynomial C; int a = start; int b = B.start; C.start = free; float c

15、; while ( a = finish & b : NewTerm ( termArrayb.coef, termArrayb.exp ); b+; break; case : NewTerm ( termArraya.coef, termArraya.exp ); a+; for ( ; a=finish; a+ ) /a未檢測(cè)完時(shí)未檢測(cè)完時(shí) NewTerm ( termArraya.coef, termArraya.exp ); for ( ; b= maxTerms ) cout Too many terms in polynomials” -link = first ; fi

16、rst = newnode;（插入前）（插入前） （插入后）（插入后） firstnewnodenewnodefirst第二種情況：在鏈表中間插入第二種情況：在鏈表中間插入 newnode-link = p-link; p-link = newnode； ( (插入前插入前) () (插入后插入后) )newnodepnewnodep第三種情況：在鏈表末尾插入第三種情況：在鏈表末尾插入 newnode-link = p-link; p-link = newnode；p ( (插入前插入前) () (插入后插入后) )newnodenewnodep 算法描述算法描述int Insert ( Li

17、nkList& first, ListData x, int i ) /在鏈表第在鏈表第 i 個(gè)結(jié)點(diǎn)處插入新元素個(gè)結(jié)點(diǎn)處插入新元素 x ListNode * p = first; int k = 0; while ( p != NULL & k -link; k+; /找第找第 i-1個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn) if ( p = NULL & first != NULL ) printf ( “無效的插入位置無效的插入位置!n” );/終止插入終止插入 return 0; ListNode * newnode = /創(chuàng)建新結(jié)點(diǎn)創(chuàng)建新結(jié)點(diǎn) (ListNode *) malloc ( s

18、izeof (ListNode) );newnode-data = x; if ( first = NULL | i = 1 ) /插入空表或非空表第一個(gè)插入空表或非空表第一個(gè)結(jié)點(diǎn)之前結(jié)點(diǎn)之前 newnode-link = first;/新結(jié)點(diǎn)成為第一個(gè)結(jié)點(diǎn)新結(jié)點(diǎn)成為第一個(gè)結(jié)點(diǎn) if(first=NULL)last=newnode;/若是空表，表尾指針若是空表，表尾指針指向新結(jié)點(diǎn)指向新結(jié)點(diǎn) first = newnode; else /插在表中間或末尾插在表中間或末尾newnode-link = p-link; if(p-link =NULL)last=newnode;p-link = new

19、node; return 1; n刪除刪除在單鏈表中刪除在單鏈表中刪除ai結(jié)點(diǎn)結(jié)點(diǎn) q = p-link; p-link = q-link;刪除前刪除前刪除后刪除后ai-1aiai+1pqpai-1ai+1aiint Delete ( LinkList& first, int i ) /在鏈表中刪除第在鏈表中刪除第 i 個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn) ListNode *p, *q; if ( i = 0 ) /刪除表中第刪除表中第 1 個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn) q = first; first = first-link; else p = first; int k = 0; while ( p != NULL &

20、amp; k -link; k+; /找第找第 i- -1個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn)if ( p = NULL | p-link = NULL ) /找不到第i-1個(gè)結(jié)點(diǎn) printf ( “無效的刪除位置!n” ); return 0; else /刪除中間結(jié)點(diǎn)或尾結(jié)點(diǎn)元素 q = p-link; p-link = q-link; if (q=last) last=p;/刪除表尾結(jié)點(diǎn) k= q-data; free ( q ); return k; /取出被刪結(jié)點(diǎn)數(shù)據(jù)并釋放q帶帶表頭結(jié)點(diǎn)表頭結(jié)點(diǎn)的單鏈表的單鏈表表頭結(jié)點(diǎn)表頭結(jié)點(diǎn)位于表的最前端，本身不帶數(shù)位于表的最前端，本身不帶數(shù)據(jù)，僅標(biāo)志表頭。據(jù)，僅標(biāo)志表

21、頭。設(shè)置表頭結(jié)點(diǎn)的目的設(shè)置表頭結(jié)點(diǎn)的目的:簡(jiǎn)化鏈表操作的實(shí)現(xiàn)。簡(jiǎn)化鏈表操作的實(shí)現(xiàn)。非空表非空表 空表空表ana1firstfirst插入插入q-link = p-link; p-link = q;firstqfirstqfirstqfirstqpppp插入前插入前插入后插入后表頭表頭表尾表尾qq插入pp表中表中int Insert (LinkList first, ListData x, int i ) /將新元素將新元素 x 插入在鏈表中第插入在鏈表中第 i 號(hào)結(jié)點(diǎn)位置號(hào)結(jié)點(diǎn)位置 ListNode * p = Locate ( first, i-1 ); if ( p = NULL ) re

22、turn 0; /參數(shù)參數(shù)i值不合理返回值不合理返回0 ListNode * newnode = /創(chuàng)建新結(jié)點(diǎn)創(chuàng)建新結(jié)點(diǎn) (ListNode *) malloc (sizeof (ListNode) ); newnode-data = x; newnode-link = p-link; /鏈入鏈入 p-link = newnode; return 1; 刪除刪除 q = p-link; p-link = q-link; delete q; 刪除前刪除前first(非空表）非空表）(空表）空表）firstfirstpqpqfirst刪除后刪除后int delete ( LinkList firs

23、t, int i ) /將鏈表第將鏈表第 i 號(hào)元素刪去號(hào)元素刪去 ListNode * p, * qp = Locate ( first, i- -1 ); /尋找第尋找第i-1個(gè)個(gè)結(jié)點(diǎn)結(jié)點(diǎn) if ( p = NULL | p-link = NULL) return 0;/i值不合理或空表值不合理或空表 q = p-link; p-link = q-link; /刪除結(jié)點(diǎn)刪除結(jié)點(diǎn) free ( q ); /釋放釋放 return 1;前插法建立單鏈表前插法建立單鏈表從一個(gè)空表開始，重復(fù)讀入數(shù)據(jù)：從一個(gè)空表開始，重復(fù)讀入數(shù)據(jù)：生成新結(jié)點(diǎn)生成新結(jié)點(diǎn)將讀入數(shù)據(jù)存放到新結(jié)點(diǎn)的數(shù)據(jù)域中將讀入數(shù)據(jù)存放到

24、新結(jié)點(diǎn)的數(shù)據(jù)域中將該新結(jié)點(diǎn)插入到鏈表的前端將該新結(jié)點(diǎn)插入到鏈表的前端直到讀入結(jié)束符為止。直到讀入結(jié)束符為止。firstqfirstqLinkList createListF ( void ) char ch; ListNode *q; LinkList head = /建立表頭結(jié)點(diǎn)建立表頭結(jié)點(diǎn) (LinkList) malloc (sizeof (ListNode); head-link = NULL; while ( (ch = getchar( ) ) != n ) q = (ListNode *) malloc (sizeof(ListNode); q-data = ch; /建立新結(jié)點(diǎn)

25、建立新結(jié)點(diǎn) q-link = head-link; /插入到表前端插入到表前端 head-link = q; return head; 后插法建立單鏈表后插法建立單鏈表每次將新結(jié)點(diǎn)加在鏈表的表尾；每次將新結(jié)點(diǎn)加在鏈表的表尾；尾指針尾指針r ,總是指向表中最后一個(gè)結(jié)點(diǎn)，新結(jié)點(diǎn)總是指向表中最后一個(gè)結(jié)點(diǎn)，新結(jié)點(diǎn)插在它的后面；插在它的后面；qfirstrfirstrLinkList createListR ( void ) char ch; LinkList head = /建立表頭結(jié)點(diǎn)建立表頭結(jié)點(diǎn) (LinkList) malloc (sizeof (ListNode); ListNode *q,

26、*r = head; while ( (ch = getchar( ) ) != n ) q = (ListNode *) malloc (sizeof(ListNode); q-data = ch; /建立新結(jié)點(diǎn)建立新結(jié)點(diǎn) r -link = q; r =q; /插入到表末端插入到表末端 r -link = NULL; return head; 單鏈表清空單鏈表清空void makeEmpty ( LinkList first ) /刪去鏈表中除表頭結(jié)點(diǎn)外的所有其它結(jié)點(diǎn)刪去鏈表中除表頭結(jié)點(diǎn)外的所有其它結(jié)點(diǎn) ListNode *q; while ( first-link != NULL ) /

27、當(dāng)鏈不空時(shí)，循環(huán)當(dāng)鏈不空時(shí)，循環(huán)逐個(gè)刪去所有結(jié)點(diǎn)逐個(gè)刪去所有結(jié)點(diǎn) q = first-link; first-link = q-link;free( q ); /釋放釋放 last=first; 計(jì)算單鏈表長(zhǎng)度計(jì)算單鏈表長(zhǎng)度int Length ( LinkList first ) ListNode *p = first-link; /指針指針 p 指示第一個(gè)結(jié)點(diǎn)指示第一個(gè)結(jié)點(diǎn)int count = 0; while ( p != NULL ) /逐個(gè)結(jié)點(diǎn)檢測(cè)逐個(gè)結(jié)點(diǎn)檢測(cè) p = p-link; count+; return count;按值查找按值查找ListNode * Find ( Li

28、nkList first, ListData value ) /在鏈表中從頭搜索其數(shù)據(jù)值為在鏈表中從頭搜索其數(shù)據(jù)值為value的結(jié)點(diǎn)的結(jié)點(diǎn) ListNode * p = first-link; /指針指針 p 指示第一個(gè)結(jié)點(diǎn)指示第一個(gè)結(jié)點(diǎn) while ( p != NULL & p-data != value ) p = p-link; return p; 按序號(hào)查找（定位）按序號(hào)查找（定位）ListNode * Locate ( LinkList first, int i ) /返回表中第返回表中第 i 個(gè)元素的地址個(gè)元素的地址 if ( i 0 ) return NULL; Lis

29、tNode * p = first; int k = 0 0; while ( p != NULL & k -link; k+; /找第找第 i 個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn) if ( k = i ) return p; /返回第返回第 i 個(gè)結(jié)點(diǎn)地址個(gè)結(jié)點(diǎn)地址 else return NULL; 1ZHANG2WANG6LI5ZHAO5WU-1CHEN31ZHANG2WANG3LI4ZHAO5WU-101234560123456修改前修改前（插入（插入chen,刪除刪除zhao)修改后修改后用一維數(shù)組描述線性鏈表用一維數(shù)組描述線性鏈表靜態(tài)鏈表靜態(tài)鏈表 定義定義const int MaxSize =

30、100; /靜態(tài)鏈表大小靜態(tài)鏈表大小typedef int ListData;typedef struct node /靜態(tài)鏈表結(jié)點(diǎn)靜態(tài)鏈表結(jié)點(diǎn) ListData data; int link; SNode;typedef struct /靜態(tài)鏈表靜態(tài)鏈表 SNode NodesMaxSize; int newptr; /當(dāng)前可分配空間首地址當(dāng)前可分配空間首地址 SLinkList;鏈表空間初始化鏈表空間初始化void InitList ( SLinkList* SL ) SL-Nodes0.link = -1; SL-newptr = 1; /當(dāng)前可分配空間從當(dāng)前可分配空間從 1 開始開始

31、/建立帶表頭結(jié)點(diǎn)的空鏈表建立帶表頭結(jié)點(diǎn)的空鏈表 for ( int i = 1; i Nodesi.link = i+1; /構(gòu)成空閑鏈表構(gòu)成空閑鏈表 SL-NodesMaxSize- -1.link = - -1; /鏈表收尾鏈表收尾在靜態(tài)鏈表中查找具有給定值的結(jié)點(diǎn)在靜態(tài)鏈表中查找具有給定值的結(jié)點(diǎn)int Find ( SLinkList SL, ListData x ) int Find ( SLinkList SL, ListData x ) int p = SL.Nodes0.link; int p = SL.Nodes0.link; /指針指針 p p 指指向鏈表第一個(gè)結(jié)點(diǎn)向鏈表第一個(gè)

32、結(jié)點(diǎn)while ( p != -1 )while ( p != -1 )/逐個(gè)查找有給定值的結(jié)點(diǎn)逐個(gè)查找有給定值的結(jié)點(diǎn) if ( SL.Nodesp.data != x)if ( SL.Nodesp.data != x) p = SL.Nodesp.link; p = SL.Nodesp.link; else break; else break;return p;return p; 在靜態(tài)鏈表中查找第在靜態(tài)鏈表中查找第 i 個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn)int Locate ( SLinkList SL, int i ) if ( i 0 ) return - -1;/參數(shù)不合理參數(shù)不合理 int j = 0,

33、 p = SL.Nodes0.link; while ( p != - -1 & j newptr; /分配結(jié)點(diǎn)分配結(jié)點(diǎn) SL-newptr = SL-NodesSL-newptr.link; SL-Nodesq.data = x; SL-Nodesq.link = SL.Nodesp.link; SL-Nodesp.link = q; /插入插入 return 1;在靜態(tài)鏈表中釋放第在靜態(tài)鏈表中釋放第 i 個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn)int Remove ( SLinkList* SL, int i ) int p = Locate ( SL, i- -1 ); if ( p = - -1 ) re

34、turn 0; /找不到結(jié)點(diǎn)找不到結(jié)點(diǎn) int q = SL-Nodesp.link; /第第 i 號(hào)結(jié)點(diǎn)號(hào)結(jié)點(diǎn) SL-Nodesp.link = SL-Nodesq.link; SL-Nodesq.link = SL-newptr; /釋放釋放 SL-newptr = q; return 1;循環(huán)鏈表循環(huán)鏈表 (Circular List)特點(diǎn)特點(diǎn):最后一個(gè)結(jié)點(diǎn)的最后一個(gè)結(jié)點(diǎn)的 link 指針不為指針不為NULL，而，而是指向頭結(jié)點(diǎn)。只要已知表中某一結(jié)點(diǎn)的地址，是指向頭結(jié)點(diǎn)。只要已知表中某一結(jié)點(diǎn)的地址，就可搜尋所有結(jié)點(diǎn)的地址就可搜尋所有結(jié)點(diǎn)的地址存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu):鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 帶

35、表頭結(jié)點(diǎn)的循環(huán)鏈表帶表頭結(jié)點(diǎn)的循環(huán)鏈表an-1firsta1a0first( (空表空表) )( (非空表非空表) )循環(huán)鏈表的插入循環(huán)鏈表的插入約瑟夫問題約瑟夫問題 用循環(huán)鏈表求解約瑟夫問題用循環(huán)鏈表求解約瑟夫問題 n 個(gè)人圍成一個(gè)圓圈，首先第個(gè)人圍成一個(gè)圓圈，首先第1個(gè)人從個(gè)人從1開始一開始一個(gè)人一個(gè)人順時(shí)針報(bào)數(shù)個(gè)人一個(gè)人順時(shí)針報(bào)數(shù), 報(bào)到第報(bào)到第m個(gè)人，令其個(gè)人，令其出列。然后再?gòu)南乱粋€(gè)人開始，從出列。然后再?gòu)南乱粋€(gè)人開始，從1順時(shí)針報(bào)順時(shí)針報(bào)數(shù)，報(bào)到第數(shù)，報(bào)到第m個(gè)人，再令其出列，個(gè)人，再令其出列，如此下，如此下去去, 直到圓圈中只剩一個(gè)人為止。此人即為優(yōu)直到圓圈中只剩一個(gè)人為止。此人

36、即為優(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 ( ); /數(shù)數(shù)m-1個(gè)人個(gè)人 cout “Delete person ” getData ( ) endl; Remove ( ); /刪去刪去 void main ( ) CircList clist; int n, m; cout n m; f

37、or ( int i=1; i=n; i+ ) clist.insert (i); /形成約形成約瑟夫環(huán)瑟夫環(huán) clist.Josephus (n, m); /解決約瑟夫問題解決約瑟夫問題v多項(xiàng)式及其相加多項(xiàng)式及其相加 在多項(xiàng)式的鏈表表示中每個(gè)結(jié)點(diǎn)增加了一個(gè)在多項(xiàng)式的鏈表表示中每個(gè)結(jié)點(diǎn)增加了一個(gè)數(shù)據(jù)成員數(shù)據(jù)成員link，作為鏈接指針。，作為鏈接指針。 優(yōu)點(diǎn)是：優(yōu)點(diǎn)是： 多項(xiàng)式的項(xiàng)數(shù)可以動(dòng)態(tài)地增長(zhǎng)，不存在多項(xiàng)式的項(xiàng)數(shù)可以動(dòng)態(tài)地增長(zhǎng)，不存在存儲(chǔ)溢出問題。存儲(chǔ)溢出問題。 插入、刪除方便，不移動(dòng)元素。插入、刪除方便，不移動(dòng)元素。多項(xiàng)式鏈表的相加多項(xiàng)式鏈表的相加AH = 1 - 10 x6 + 2x8

38、+7x14BH = - x4 + 10 x6 - 3x10 + 8x14 +4x18 Polynomial operator + ( const Polynomial & ah, const Polynomial & bh ) Term *pa, *pb, *p; ListIterator Aiter ( ah.poly ); ListIterator Biter ( bh.poly ); /建立兩個(gè)多項(xiàng)式對(duì)象建立兩個(gè)多項(xiàng)式對(duì)象 Aiter、 Biter pa = pc = Aiter.First ( ); / pa 檢測(cè)指針檢測(cè)指針 p = pb = Biter.First

39、( ); / pb 檢測(cè)指針檢測(cè)指針 pa = Aiter.Next ( ); pb = Biter.Next( ); / pa, pb 越過表頭結(jié)點(diǎn)越過表頭結(jié)點(diǎn) delete p;while ( Aiter.NotNull ( ) & Biter.NotNull ( ) ) switch ( compare ( paexp, pbexp ) ) case = : pacoef = pacoef + pbcoef; p = pb; pb = Biter.Next ( ); delete p; if ( !pacoef ) p = pa; pa = Aiter.Next ( ); del

40、ete 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é)點(diǎn)的鏈指針指向自己表頭結(jié)點(diǎn)的鏈指針指向自己計(jì)算雙向循環(huán)鏈表的長(zhǎng)度計(jì)算雙向循環(huán)鏈表的長(zhǎng)度int Length ( DblList first ) /計(jì)算帶表頭結(jié)點(diǎn)的雙向循環(huán)鏈表的長(zhǎng)度計(jì)算帶表頭結(jié)點(diǎn)的雙向循環(huán)鏈表的長(zhǎng)度 DblNode * p = first-next; int count = 0; while ( p != first ) p = p-next; count+; return count; 雙向循環(huán)鏈表的插入雙向循環(huán)鏈表的插入 (非空