【導(dǎo)讀】單鏈表的結(jié)點(diǎn)類和鏈表類的類定義。ListNode<Type>*getLink(){returnlink;}//取得結(jié)點(diǎn)的下一結(jié)點(diǎn)地址。voidsetLink{link=next;}//修改結(jié)點(diǎn)的link指針。ListNode<Type>*Find;//搜索含數(shù)據(jù)value的元素并成為當(dāng)前元素。ListNode<Type>*Firster(){current=first;returnfirst;}//當(dāng)前指針定位于表頭結(jié)點(diǎn)?？辗祷?,不空返回0. 若表的總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除，但要求以最快的速度存取表中的元素，這時(shí)，但它的空間大小一經(jīng)定義，在程序整個(gè)運(yùn)行期間不會(huì)發(fā)生改變，因此，不易擴(kuò)充。原來的邏輯順序，因此不必移動(dòng)數(shù)據(jù)，只需修改它們的鏈接指針，修改效率較高。元素時(shí)，只能循鏈順序訪問，因此存取效率不高。動(dòng)改變、在此情況下，應(yīng)選用鏈接存儲(chǔ)表示。初始時(shí)因不知道哪。個(gè)表增長得快，必須平均分配空間。這個(gè)處理過程極其繁瑣和低效。還可以在以后動(dòng)態(tài)分配給其他的存儲(chǔ)申請(qǐng)要求，非常靈活方便。共存的情形，處理十分簡便和快捷。不到，則函數(shù)返回NULL。求最大值函數(shù)max：通過一趟遍歷在單鏈表中確定值最大的結(jié)點(diǎn)。統(tǒng)計(jì)函數(shù)number：統(tǒng)計(jì)單鏈表中具有給定值x的所有元素。素的次序相同，要求該程序的時(shí)間復(fù)雜性為O。

　　

【正文】 pclink != NULL ) pclinkdata = pclinkdata + temp //累加 else pclink = new Term (temp)。 //增加項(xiàng) , 事實(shí)上 , 每次 pa 變化 , 鏈結(jié)點(diǎn)要隨之增加 pc = pclink。 pb = pblink。 } pc = fc = fclink。 pa = palink。 //處理多項(xiàng)式 a 的下一 ai } pclink = NULL。 return *this。 1*6 1*6 1*7 1*8 1*9 1*7+2*6 1*8+2*7 1*9+2*8 2*9 1*6 1*7+2*6 1*8+2*7+3*6 1*9+2*8+3*7 2*9+3*8 3*9 1*6 1*7+2*6 1*8+2*7+3*6 1*9+2*8+3*7+4*6 2*9+3*8+4*7 3*9+4*8 4*9 1*6 1*8+2*7+3*6 1*9+2*8+3*7+4*6 2*9+3*8+4*7+5*6 1*7+2*6 3*9+4*8+5*7 4*9+5*8 5*9 第 3 章 鏈表 22 } 這個(gè)算法有一個(gè)二重循環(huán)，內(nèi)層循環(huán)中語句的重復(fù)執(zhí)行次數(shù)是 O(n*m)。其中， n 是第一個(gè)多項(xiàng)式的階數(shù)， m 是第二個(gè)多項(xiàng)式的階數(shù)。這是稠密多項(xiàng)式的情形。 對(duì)于稀疏多項(xiàng)式的情形請(qǐng)自行考慮。 39 計(jì)算多項(xiàng)式 Pn (x) = a0 xn + a1 xn1 + a2 xn2 + ?? + an1 x + an 的值，通常使用的方法是一種嵌套的方法。它可以描述為如下的迭代形式： b0 = a0 , bi+1 = x * bi + ai+1, i = 0, 1, ? , n1。 若設(shè) bn = pn （ x） . 則問題可以寫為如下形式： Pn (x) = x * Pn1 (x) + an ，此處， Pn1 (x) = a0 xn1 + a1 xn2 + ?? + an2 x + an1，這是問題的遞歸形式。試編寫一個(gè)遞歸函數(shù)，計(jì)算這樣的多項(xiàng)式的值。 【解答】 如果用循環(huán)鏈表方式存儲(chǔ)多項(xiàng)式，求解方法與 37 題相同。如果用數(shù)組方式存儲(chǔ)多項(xiàng)式，當(dāng)零系數(shù)不多時(shí)，可用順序存放各項(xiàng)系數(shù)的一維數(shù)組存儲(chǔ)多項(xiàng)式的信息，指數(shù)用數(shù)組元素的下標(biāo)表示 0 1 2 3 i n2 n1 coef a0 a1 a2 a3 ? ai ? an2 an1 多項(xiàng)式的類定義如下： struct Polynomal { double * coef。 int n。 } 這樣可得多項(xiàng)式的解法： double Polynomal :: Value ( int i, double x ) { //私有函數(shù)：遞歸求子多項(xiàng)式的值 if ( i == n1 ) return coef[n1]。 else return coef[i] + x * Value ( i+1, x )。 } double Polynomal :: Calc ( double x ) { //共有函數(shù)：遞歸求多項(xiàng)式的值 if ( n == 0 ) cout 0 endl。 else cout Value ( 0, x ) endl。 } 310 試設(shè)計(jì)一個(gè)實(shí)現(xiàn)下述要求的 Locate 運(yùn)算的函數(shù)。設(shè)有一個(gè)帶表頭結(jié)點(diǎn)的雙向鏈表 L，每個(gè)結(jié)點(diǎn)有 4 個(gè)數(shù)據(jù)成員：指向前驅(qū)結(jié)點(diǎn)的指針 prior、指向后繼結(jié)點(diǎn)的指針 next、存放數(shù)據(jù)的成員 data 和訪問頻度 freq。所有結(jié)點(diǎn) 的 freq 初始時(shí)都為 0。每當(dāng)在鏈表上進(jìn)行一次 Locate (L, x)操作時(shí)，令元素值為 x的結(jié)點(diǎn)的訪問頻度 freq 加 1，并將該結(jié)點(diǎn)前移，鏈接到與它的訪問頻度相等的結(jié)點(diǎn)后面，使得鏈表中所有結(jié)點(diǎn)保持按訪問頻度遞減的順序排列，以使頻繁訪問的結(jié)點(diǎn)總是靠近表頭。 【解答】 include //雙向循環(huán)鏈表結(jié)點(diǎn)的構(gòu)造函數(shù) DblNode (Type value, DblNodeType *left, DblNodeType *right ) : data ( value ), freq ( 0 ), lLink ( left ), rLink ( right ) { } DblNode (Type value ) : data ( value ), freq ( 0 ), lLink ( NULL ), rLink ( NULL ) { } 第 3 章 鏈表 23 template class Type DblListType :: DblList ( Type uniqueVal ) { first = new DblNodeType( uniqueVal )。 firstrLink = firstlLink = first。 //創(chuàng)建表頭結(jié)點(diǎn) current = NULL。 cout 開始建立雙向循環(huán)鏈表： \n。 Type value。 cin value。 while ( value != uniqueVal ) { //每次新結(jié)點(diǎn)插入在表頭結(jié)點(diǎn)后面 firstrLink = new DblNodeType( value, first, firstrLink )。 cin value。 } } template class Type void DblListType :: Locate ( Type amp。 x ) { //定位 DblNodeType *p = firstrLink。 while ( p != first amp。amp。 pdata != x ) p = prLink。 if ( p != first ) { //鏈表中存在 x p→ freq++。 //該結(jié)點(diǎn)的訪問頻度加 1 current = p。 //從鏈 表中摘下這個(gè)結(jié)點(diǎn) currentlLinkrLink = currentrLink。 currentrLinklLink = currentlLink。 p = currentlLink。 //尋找從新插入的位置 while ( p != first amp。amp。 currentfreq pfreq ) p = plLink。 currentrLink = prLink。 //插入在 p 之后 currentlLink = p。 prLinklLink = current。 prLink = current。 } else coutSorry. Not find!\n。 //沒找到 } 311 利用雙向循環(huán)鏈表的操作改寫 22 題，解決約瑟夫 (Josephus)問題。 【解答】 include include “” Template class Type void DblList Type :: Josephus ( int n, int m ) { DblNodeType p = first, temp。 for ( int i = 0。 i n1。 i++ ) { //循環(huán) n1 趟，讓 n1 個(gè)人出列 for ( int j = 0。 j m1。 j++ ) p = prLink。 //讓 p 向后移動(dòng) m1 次 cout “Delete person ” pdata endl。 第 3 章 鏈表 24 plLinkrLink = prLink。 //從鏈中摘下 p prLinklLink = plLink。 temp = prlink。 delete p。 p = temp。 //刪除 p 所指結(jié)點(diǎn)后 , p 改指下一個(gè)出發(fā)點(diǎn) } cout “The winner is ” pdata endl。 } void main ( ) { DblListint dlist。 //定義循環(huán)鏈表 dlist 并初始化 int n, m。 //n 是總?cè)藬?shù)， m 是報(bào)數(shù)值 cout “Enter the Number of Contestants?”。 cin n m。 for ( int i = 1。 i = n。 i++ ) (i)。 //建立數(shù)據(jù)域?yàn)?1, 2, ? 的循環(huán)鏈表 (n, m)。 //解決約瑟夫問題，打印勝利者編號(hào) } 312 試設(shè)計(jì)一個(gè)算法，改造一個(gè)帶表頭結(jié)點(diǎn)的雙向鏈表，所有結(jié)點(diǎn) 的原有次序保持在各個(gè)結(jié)點(diǎn)的 rLink域中，并利用 lLink 域把所有結(jié)點(diǎn)按照其值從小到大的順序連接起來。 【解答】 templateType void DblListType :: sort ( ) { DblNodeType * s = firstlink。 //指針 s 指向待插入結(jié)點(diǎn) , 初始時(shí)指向第一個(gè)結(jié)點(diǎn) while ( s != NULL ) { //處理所有結(jié)點(diǎn) pre = first。 p = firstlLink。 //指針 p 指向待比較的結(jié)點(diǎn) , pre 是 p 的前驅(qū)指針 while ( p != NULL amp。amp。 sdata pdata ) //循 lLink 鏈尋找結(jié)點(diǎn) *s 的插入位置 { pre = p。 p = plLink。 } prelLink = s。 slLink = p。 //結(jié)點(diǎn) *s 在 lLink 方向插入到 *pre 與 *p 之間 } }