【正文】 } ? 本章講述十分重要的動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu) – 動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)概念 – 各種簡單的動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu) ?棧 ?隊(duì)列 ?鏈表 ?樹 ?圖 重點(diǎn)掌握動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)的操作 本章小結(jié) 作業(yè) ① ② ③ ④ ⑤ 。 free(r)。 } /* 釋放哨兵變量 */ r = s。 q = qnext。 r=rnext。 /* p 多項(xiàng)式尾 */ while (p!=NULL) { adds( pexp , pcoef ， r )。 p = pnext。 }else{ adds( pexp , pcoef+qcoef ， r )。 }else if ( pexp qexp ) { adds( qexp , qcoef ， r )。(q!=NULL) ) /* 相加 */ if ( pexp qexp ) { adds( pexp , pcoef ， r )。 while ( (p!=NULL)amp。 /* 申請(qǐng)一個(gè)哨兵變量 ，以便算法統(tǒng)一 */ s = (polynome)malloc( sizeof(struct item) )。 rnext=r0。 r0coef = coef0。 r0 = ( polynome)malloc( sizeof(struct item) )。 p = pnext q=s。amp。 p = pnext q=s。 p = pnext p+q=s。由于利用了哨兵變量，所以處理統(tǒng)一了。 解 :在本程序的算法中，在鏈表上利用了一個(gè)哨兵項(xiàng)。 }。 int exp。 例如多項(xiàng)式 可以表示成如下形式 : 編一個(gè)函數(shù)，實(shí)現(xiàn)多項(xiàng)式加法： p(X)+q(X) = s(X) 。 } return fn 。 r0next = p 。 pnumerator = j 。 r = rnext 。 j++) if ( gcd( i,j ) == 1 ) { /* 查 j/i 位置 r0,r */ r = fn 。 i++) for (j=1。 /* 生成序列 */ for ( i=2。 fnnextdenominator = 1 。 fnnext = (farleipointer) malloc(sizeof(struct farlei_item))。 //構(gòu)造 0/1 fnnumerator = 0 。 if( n1 ) //如果 n=0,則沒有法雷序列 return NULL。 } /*構(gòu)造法雷序列 ,并返回序列頭指針 */ farleipointer farlei(int n) { int i,j 。 int gcd( int x , int y ) { /* 求最大公約數(shù) */ if ( y==0 ) return x 。 }。 j++) 把 j/i 放入序列 j/i 不可 約分 把 j/i 插入到 r0,r 之間 查 j/i 應(yīng)插入 的位置 r0,r struct farlei_item { int numerator , denominator 。 i++) for(j=1。 0/1 , 1/1 放入序列 讀入 n 生成 n 階 法雷序列鏈表 結(jié)束 for(i=2。 ... 顯然法雷序列的各項(xiàng)均在區(qū)間 [0/1,1/1]之內(nèi)。用下圖形式的鏈表來表示它。 ( 0 i n 。 } /* sort */ 對(duì)任意給定的自然數(shù) n ，把所有如下形式的不可約分?jǐn)?shù) 按遞增順序排列起來，稱該序列為 n 級(jí)法雷序列 Fn 。 /* 前進(jìn)一項(xiàng) */ p = pnext 。 r0 next = q 。 base = q 。 p = p0 。 } if (r!=p) { /* p插入到 r0、 r之間 */ /* 若 r==p ，在鏈尾，則不用插入 */ q = p 。 ( r!=p ) ) { r0 = r 。 /* 尋找位置 */ while ( ( rkey pkey ) amp。 p = base 。 r0next = q； 現(xiàn)在鏈表結(jié)構(gòu)是： data key data key ... data key data key base: data key data key data key data key r0: r: p: p0: q: pt sort( pt base ) { /* 鏈表排序， base 為鏈?zhǔn)? */ pt p , p0 , r , r0 , q 。 p = p0 。如圖所示： 設(shè)從 base到 p0之間的子鏈表已經(jīng)遞增，現(xiàn)在加入 p所指示的節(jié)； 在 base~p0之間查找合適位置，設(shè)應(yīng)該把 p所指的節(jié)插入到 r0,r所之間； 把 p獨(dú)立出來 =q ， p指向 p0： q = p 。 base = q r == base 尋找位置 r = base rkeypkey ∧ r!=p r0 = r。 p指向 p0 插入到 r0,r之間 : qnext = r 。 ... base: 開始 p = base p!=NULL 使 base～ p遞增 p0 = p 。 typedef struct item *pt 以 base為鏈?zhǔn)椎逆湵砣缦聢D所示。 struct item *next 。 struct item { datatype data 。下邊用逐步增加遞增子序列的方法實(shí)現(xiàn)鏈表排序。 printf(\n)。 j=f。 } void printp( int e,int f ) { int j。 j++ ) if ( ii==p[j] ) return true。 for ( j=u。 hh = hhlink。 while ( hh!=NULL ) { i = hhno。 if ( m==n ) printp(0,r)。 int i。 /* 網(wǎng)的鄰接鏈表 */ void printp( int,int )； // 函數(shù)原型：輸出 bool iinp( int,int,int ) 。 int p[h] 。 struct node *link。 在走的過程中，保證不走重復(fù)點(diǎn)，可以得到下圖的算法 : m==n 輸出 p[0～ r] m點(diǎn)的所有 后繼結(jié)點(diǎn) i i∈ p[0～ r] p[r] = m route(i,n,r+1) route m:開始點(diǎn)； n:終結(jié)點(diǎn)； r:路跡數(shù)組 p尾標(biāo) 結(jié)束 在該算法中，關(guān)鍵在于找出 m點(diǎn)的所有后繼點(diǎn)。 2. 然后再站在新的點(diǎn)上，再向前走一步 。 找路徑是指求從結(jié)點(diǎn) m到結(jié)點(diǎn) n的所有路徑。其中 , ? v=(v1 ,v2 , … ,vn) 為網(wǎng) g的結(jié)點(diǎn)集合 , ? vi為網(wǎng)中結(jié)點(diǎn)。以它為鏈?zhǔn)?, 把與結(jié)點(diǎn) i直接相連的結(jié)點(diǎn)鏈成一個(gè)鏈。 0 4 3 1 6 7 5 2 0 1 2 1 1 0 3 4 1 2 0 4 5 1 3 1 4 1 4 1 2 3 6 7 1 5 2 6 7 1 6 4 5 1 7 4 5 1 (二 ) 鄰接矩陣方法 設(shè) 圖 G有 k個(gè)結(jié)點(diǎn)，使用一個(gè) k*k的 bool類型矩陣 g表示 圖 G 矩陣元素 利用這種表示法，左圖的網(wǎng)表示成右圖 8*8 的 bool 矩陣。 0 4 3 1 6 7 5 2 圖 ——graph (一 ) 鄰接表方法 設(shè) 圖 G有 k個(gè)結(jié)點(diǎn)，使用一個(gè) k*k的 int型矩陣 g表示 圖 G, 矩陣 g的第 i行順序列出與結(jié)點(diǎn) i直接相連的結(jié)點(diǎn)編號(hào) , 最后以 “ 1‖結(jié)尾。 // 把將釋放的變量指針帶回主程序 } 1 2 3 4 5 9 7 6 8 10 11 12 13 14 15 p: s: 9 r: root: 圖 G=(V， E)。由于 s參數(shù)是指向指針的變量 */ /* 本語句把 *s 左分支接到 *s 的父結(jié)點(diǎn)上， */ /* 從而在樹上摘下了 *s 所指向的結(jié)點(diǎn)。 r = *s 。((*s)right),p ) //右分支非空 , 在右方向以下繼續(xù)查找 else { /* 找到右分支為空的結(jié)點(diǎn) *s */ (*p)key =(*s) key 。root )