【導讀】考慮上一章的職工卡片問題，用計算機管理。首先，用什么數(shù)據(jù)結構存儲：一張卡片是一。個結構體，所有卡片自然用結構體數(shù)組。產(chǎn)生數(shù)組不夠大的可能。以后的其它元素依次向后移動。–數(shù)組尺寸不好確定。最好把這些卡片存儲成動態(tài)的，–中間加一張卡片時不要向后串別的卡片，到鏈的適當位置上。例如，要增加一張卡片50插入到2、若刪除一節(jié)，只需要將其從鏈上摘下來即可。計算機系統(tǒng)，以便作其它用途。是標識動態(tài)變量的有力手段。靜態(tài)變量是程序中由程序員“顯式”說明的。已經(jīng)給它分配存儲空間。量的名字來標識。動態(tài)變量是在程序運行時。而是一般程序設計概念中的靜態(tài)變量、應類型數(shù)據(jù)所需要的字節(jié)數(shù)。釋放由malloc申請的內(nèi)存區(qū)域。下使用free都會造成災難性后果。立的不能與其它變量相聯(lián)系，顯然作用不大。–引進動態(tài)變量的目的是構造動態(tài)數(shù)據(jù)結構。組有一定的局限性。

　　

【正文】 qnext = base 。 base = q 。 } else { /* 插在鏈中 r0 、 r之間 */ qnext = r 。 r0 next = q 。 } } p0 = p 。 /* 前進一項 */ p = pnext 。 } return base 。 } /* sort */ 對任意給定的自然數(shù) n ，把所有如下形式的不可約分數(shù) 按遞增順序排列起來，稱該序列為 n 級法雷序列 Fn 。 例如 F8 為 : 編函數(shù)，對任意給定的正整數(shù) n ，求 n級法雷序列，并帶回n級法雷序列鏈指針。 ( 0 i n 。 0 j i )ji ? ? = ? = ? =0 1 1 1 1 1 2 1 3 2 3 1 4 3 5 2 5 3 4 5 6 7 1, , , , , , , , , , , , , , , , , , , , , ,1 8 7 6 5 4 7 3 8 5 7 2 7 5 8 3 7 4 5 6 7 8 1例 123 法雷序列 分析： 法雷序列的每項是個分數(shù)，不能用實數(shù)精確的表示，而且這些數(shù)的排列順序是不規(guī)則的。用下圖形式的鏈表來表示它。 分子 分母 分子 分母 分子 分母 分子 分母 ... 顯然法雷序列的各項均在區(qū)間 [0/1,1/1]之內(nèi)。生成法雷序列算法 ?先把一階法雷序列： 0/1,1/1放入鏈表中； ?然后順序分別以 i=2,3, ... ,n 作分母，對任意 i以 j=1,2, ... , i1作 分子，作成分數(shù) j/i； ?若 j/i是不可約分數(shù)，則該 j/i必然是法雷序列的一項；把該 j/i插入到鏈表的合適位置上，并使鏈表仍保持按遞增排序。 0/1 , 1/1 放入序列 讀入 n 生成 n 階 法雷序列鏈表 結束 for(i=2。 i=n。 i++) for(j=1。 ji。 j++) 把 j/i 放入序列 j/i 不可 約分 把 j/i 插入到 r0,r 之間 查 j/i 應插入 的位置 r0,r struct farlei_item { int numerator , denominator 。 struct farlei_item *next 。 }。 typedef struct farlei_item * farleipointer 。 int gcd( int x , int y ) { /* 求最大公約數(shù) */ if ( y==0 ) return x 。 else return gcd( y , x % y ) 。 } /*構造法雷序列 ,并返回序列頭指針 */ farleipointer farlei(int n) { int i,j 。 farleipointer fn , r , r0 , p 。 if( n1 ) //如果 n=0,則沒有法雷序列 return NULL。 /* 0/1 , 1/1 送入序列 ， fn指向鏈首 */ fn = (farleipointer)malloc(sizeof(struct farlei_item))。 //構造 0/1 fnnumerator = 0 。 fndenominator = 1 。 fnnext = (farleipointer) malloc(sizeof(struct farlei_item))。 //構造 1/1 fnnextnumerator = 1 。 fnnextdenominator = 1 。 fnnextnext = NULL 。 /* 生成序列 */ for ( i=2。 i=n。 i++) for (j=1。 ji。 j++) if ( gcd( i,j ) == 1 ) { /* 查 j/i 位置 r0,r */ r = fn 。 while ( j*rdenominator i*rnumerator ) { r0 = r 。 r = rnext 。 } /* j/i 插入到 r0,r 之間 */ p = (farleipointer)malloc(sizeof(struct farlei_item))。 pnumerator = j 。 pdenominator = i 。 r0next = p 。 pnext = r 。 } return fn 。 } 例 124 多項式加法 多項式可以用如下形式的鏈表來存儲； 冪次 系數(shù) ... 冪次 系數(shù) 冪次 系數(shù) 冪次 系數(shù) ． 52( ) x X X X= ? ? ?52( ) x X X X= ? ? ?5 2 1 1 0 例如多項式 可以表示成如下形式 : 編一個函數(shù)，實現(xiàn)多項式加法： p(X)+q(X) = s(X) 。 設有類型說明： struct item { float coef。 int exp。 struct item *next。 }。 typedef struct item *polynome。 解 :在本程序的算法中，在鏈表上利用了一個哨兵項。所謂哨兵是在鏈表的鏈首多加一節(jié)，該節(jié)不存儲有效的鏈表項的值，而保存一個邊界值或空值，本程序的哨兵項是空值。由于利用了哨兵變量，所以處理統(tǒng)一了。多項式加法的算法如下圖： 開始 p = s 。 p = pnext p+q=s。 q = qnext。 p = pnext q=s。 q = qnext 結束 (p!=NULL) amp。amp。 (q!=NULL) p exp q exp p!=NULL q!=NULL p=s。 p = pnext q=s。 q = qnext pexp qexp 程序如下： void adds( int exp0 , float coef0 ， polynome r ) { /* 向 s加入一項 */ polynome r0。 r0 = ( polynome)malloc( sizeof(struct item) )。 r0exp = exp0。 r0coef = coef0。 r0next = NULL。 rnext=r0。 } polinome addpolynome(polinome p, polinome q ) { polinome s ， r // s為結果多項式鏈首； r 始終指向結果多項式 s的最低次冪項。 /* 申請一個哨兵變量 ，以便算法統(tǒng)一 */ s = (polynome)malloc( sizeof(struct item) )。 r = s。 while ( (p!=NULL)amp。amp。(q!=NULL) ) /* 相加 */ if ( pexp qexp ) { adds( pexp , pcoef ， r )。 p = pnext。 }else if ( pexp qexp ) { adds( qexp , qcoef ， r )。 q = qnext。 }else{ adds( pexp , pcoef+qcoef ， r )。 q = qnext。 p = pnext。 } r=rnext。 /* p 多項式尾 */ while (p!=NULL) { adds( pexp , pcoef ， r )。 p = pnext。 r=rnext。 } /* q 多項式尾 */ while (q!=NULL) { adds( pexp , pcoef ， r )。 q = qnext。 r=rnext。 } /* 釋放哨兵變量 */ r = s。 s = snext。 free(r)。 return s 。 } ? 本章講述十分重要的動態(tài)數(shù)據(jù)結構 – 動態(tài)數(shù)據(jù)結構概念 – 各種簡單的動態(tài)數(shù)據(jù)結構 ?棧 ?隊列 ?鏈表 ?樹 ?圖 重點掌握動態(tài)數(shù)據(jù)結構的操作 本章小結 作業(yè) ① ② ③ ④ ⑤