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

　　

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