數(shù)據(jù)結(jié)構(gòu)第3章鏈表

1、第3章 鏈表一、復(fù)習(xí)要點本章重點討論最簡單的鏈表結(jié)構(gòu)單鏈表。詳細(xì)地介紹了單鏈表的抽象數(shù)據(jù)類型，單鏈表的類定義，相應(yīng)操作的實現(xiàn)，引入了帶表頭結(jié)點的單鏈表結(jié)構(gòu)。進一步定義了用模板描述的單鏈表類。作為一種應(yīng)用，討論了一元多項式的類定義及其加法操作的實現(xiàn)。此外，討論了循環(huán)鏈表和雙向鏈表。在復(fù)習(xí)這一章時需要對C+ 語言中的指針和引用類型的使用有清楚的理解。對帶表頭結(jié)點的鏈表和不帶表頭結(jié)點的鏈表在插入、刪除、搜索時的差別有清楚的認(rèn)識。而且需要明確：鏈表是一種實現(xiàn)級的結(jié)構(gòu)。本章復(fù)習(xí)的要點：1、基本知識點單鏈表是一種線性結(jié)構(gòu)，鏈表各結(jié)點的物理存儲可以是不連續(xù)的，因此各結(jié)點的邏輯次序與物理存放次序可以不一致。必

2、須理解單鏈表的定義和特點，單鏈表的抽象數(shù)據(jù)類型和類定義，單鏈表成員函數(shù)，如構(gòu)造函數(shù)、搜索、插入、刪除等操作的實現(xiàn)，對比帶表頭結(jié)點單鏈表的搜索、插入、刪除操作，比較其優(yōu)缺點。其次是循環(huán)鏈表的定義和特點，它與單鏈表的差別，它的搜索、插入、刪除操作的實現(xiàn)。最后是雙向鏈表的定義，它的插入與刪除操作的實現(xiàn)。2、算法設(shè)計 單鏈表的迭代求解算法，包括統(tǒng)計鏈表結(jié)點個數(shù)，在鏈表中尋找與給定值value匹配的結(jié)點，在鏈表中尋找第i個結(jié)點，在鏈表中第i個位置插入新結(jié)點，刪去第i個結(jié)點，單鏈表各結(jié)點順序逆轉(zhuǎn)算法，在單鏈表中按從左到右和從右到左的順序遍歷的逆轉(zhuǎn)鏈算法。 帶表頭結(jié)點的單鏈表的迭代算法，包括統(tǒng)計鏈表結(jié)點個數(shù)

3、，在鏈表中尋找與給定值value匹配的結(jié)點，在鏈表中尋找第i個結(jié)點，在鏈表中第i個位置插入新結(jié)點，刪去第i個結(jié)點，連續(xù)刪除鏈表中含有value值的結(jié)點，兩個有序鏈表的合并。 單鏈表的遞歸算法，包括統(tǒng)計鏈表結(jié)點個數(shù)，在鏈表中尋找與給定值value匹配的結(jié)點，在鏈表中尋找第i個結(jié)點，求鏈表各結(jié)點值的和，求鏈表各結(jié)點的值的平均值。 循環(huán)鏈表的迭代算法：包括統(tǒng)計鏈表結(jié)點個數(shù)，在鏈表中尋找與給定值value匹配的結(jié)點，在鏈表中尋找第i個結(jié)點，在鏈表中第i個位置插入新結(jié)點，刪去第i個結(jié)點，將循環(huán)鏈表鏈入單鏈表的表頭。 多項式的建立，兩個多項式的相加，兩個多項式的相減。 用單鏈表實現(xiàn)字符串操作，每個結(jié)點僅存

4、一個字符。二、難點和重點1、單鏈表：單鏈表定義、相應(yīng)操作的實現(xiàn)。單鏈表的兩種定義方式(復(fù)合方式與嵌套方式) 單鏈表的搜索算法與插入、刪除算法 單鏈表的遞歸與迭代算法2、循環(huán)鏈表：單鏈表與循環(huán)鏈表的異同3、雙向鏈表：帶表頭結(jié)點的雙向循環(huán)鏈表雙向循環(huán)鏈表的定義，帶表頭結(jié)點的優(yōu)點雙向鏈表的搜索、插入與刪除算法4、多項式：多項式的定義、多項式的表示及加法多項式.的三種表示多項式鏈接表示的優(yōu)點多項式加法的實現(xiàn)(有序鏈表的合并算法)三、教材中習(xí)題的解析3-1線性表可用順序表或鏈表存儲。試問：(1) 兩種存儲表示各有哪些主要優(yōu)缺點?(2) 如果有n個表同時并存，并且在處理過程中各表的長度會動態(tài)發(fā)生變化，表的

5、總數(shù)也可能自動改變、在此情況下，應(yīng)選用哪種存儲表示？為什么？(3) 若表的總數(shù)基本穩(wěn)定，且很少進行插入和刪除，但要求以最快的速度存取表中的元素，這時，應(yīng)采用哪種存儲表示？為什么？【解答】(1) 順序存儲表示是將數(shù)據(jù)元素存放于一個連續(xù)的存儲空間中，實現(xiàn)順序存取或(按下標(biāo))直接存取。它的存儲效率高，存取速度快。但它的空間大小一經(jīng)定義，在程序整個運行期間不會發(fā)生改變，因此，不易擴充。同時，由于在插入或刪除時，為保持原有次序，平均需要移動一半(或近一半)元素，修改效率不高。鏈接存儲表示的存儲空間一般在程序的運行過程中動態(tài)分配和釋放，且只要存儲器中還有空間，就不會產(chǎn)生存儲溢出的問題。同時在插入和刪除時不

6、需要保持?jǐn)?shù)據(jù)元素原來的物理順序，只需要保持原來的邏輯順序，因此不必移動數(shù)據(jù)，只需修改它們的鏈接指針，修改效率較高。但存取表中的數(shù)據(jù)元素時，只能循鏈順序訪問，因此存取效率不高。(2) 如果有n個表同時并存，并且在處理過程中各表的長度會動態(tài)發(fā)生變化，表的總數(shù)也可能自動改變、在此情況下，應(yīng)選用鏈接存儲表示。如果采用順序存儲表示，必須在一個連續(xù)的可用空間中為這n個表分配空間。初始時因不知道哪個表增長得快，必須平均分配空間。在程序運行過程中，有的表占用的空間增長得快，有的表占用的空間增長得慢；有的表很快就用完了分配給它的空間，有的表才用了少量的空間，在進行元素的插入時就必須成片地移動其他的表的空間，以空

7、出位置進行插入；在元素刪除時，為填補空白，也可能移動許多元素。這個處理過程極其繁瑣和低效。如果采用鏈接存儲表示，一個表的存儲空間可以連續(xù)，可以不連續(xù)。表的增長通過動態(tài)存儲分配解決，只要存儲器未滿，就不會有表溢出的問題；表的收縮可以通過動態(tài)存儲釋放實現(xiàn)，釋放的空間還可以在以后動態(tài)分配給其他的存儲申請要求，非常靈活方便。對于n個表(包括表的總數(shù)可能變化)共存的情形，處理十分簡便和快捷。所以選用鏈接存儲表示較好。(3) 應(yīng)采用順序存儲表示。因為順序存儲表示的存取速度快，但修改效率低。若表的總數(shù)基本穩(wěn)定，且很少進行插入和刪除，但要求以最快的速度存取表中的元素，這時采用順序存儲表示較好。3-2 針對帶表

8、頭結(jié)點的單鏈表，試編寫下列函數(shù)。(1) 定位函數(shù)Locate：在單鏈表中尋找第i個結(jié)點。若找到，則函數(shù)返回第i個結(jié)點的地址；若找不到，則函數(shù)返回NULL。(2) 求最大值函數(shù)max：通過一趟遍歷在單鏈表中確定值最大的結(jié)點。(3) 統(tǒng)計函數(shù)number：統(tǒng)計單鏈表中具有給定值x的所有元素。(4) 建立函數(shù)create：根據(jù)一維數(shù)組an建立一個單鏈表，使單鏈表中各元素的次序與an中各元素的次序相同，要求該程序的時間復(fù)雜性為O(n)。(5) 整理函數(shù)tidyup：在非遞減有序的單鏈表中刪除值相同的多余結(jié)點?！窘獯稹繂捂湵淼慕Y(jié)點類(ListNode class)和鏈表類(List class)的類定義

9、。#ifndef LIST_H/將單鏈表定義在List.h#define LIST_Htemplate class List;/前視的類定義template class ListNode /鏈表結(jié)點類的定義friend class List;/List類作為友元類定義private: Type data;/數(shù)據(jù)域 ListNode *link;/鏈指針域public: ListNode ( ) : link (NULL) /僅初始化指針成員的構(gòu)造函數(shù) ListNode ( Type item, ListNode * next = NULL ) : data (item), link (next

10、) /初始化數(shù)據(jù)與指針成員的構(gòu)造函數(shù) ListNode * getLink ( ) return link; /取得結(jié)點的下一結(jié)點地址 Type getData ( ) return data; /取得結(jié)點中的數(shù)據(jù) void setLink ( ListNode * next ) link = next; /修改結(jié)點的link指針 void setData ( Type value ) data = value; /修改結(jié)點的data值;template class List /單鏈表類定義private: ListNode *first, *current;/鏈表的表頭指針和當(dāng)前元素指針pu

11、blic: List ( Type value ) first = current = new ListNode ( value ); /構(gòu)造函數(shù) List ( ) MakeEmpty ( ); delete first; /析構(gòu)函數(shù) void MakeEmpty ( );/將鏈表置為空表 int Length ( ) const;/計算鏈表的長度 ListNode * Find ( Type value );/搜索含value的元素并成為當(dāng)前元素 ListNode * Locate( int i );/搜索第i個元素并置為當(dāng)前元素 Type GetData ( ) return curren

12、t-data; /取出表中當(dāng)前元素的值 int Insert ( Type value );/將value插在當(dāng)前位置后并成為當(dāng)前元素 Type *Remove ( );/將表中當(dāng)前元素刪去, 填補者為當(dāng)前元素 ListNode * Firster ( ) current = first; return first; /當(dāng)前指針定位于表頭 Type First ( ) ;/當(dāng)前指針定位于表第一個元素并返回值 Type *Next ( );/將當(dāng)前指針進到表中下一個元素并返回值 int NotNull ( ) return current != NULL; /表中當(dāng)前元素空否？空返回1, 不空返

13、回0 int NextNotNull ( ) return current != NULL & current-link != NULL; ;/當(dāng)前元素的下一元素空否？空返回1, 不空返回0(1) 實現(xiàn)定位函數(shù)的算法如下：template ListNode * List : Locate ( int i ) /取得單鏈表中第i個結(jié)點地址, i從1開始計數(shù), i = 0時返回指針NULL if ( i = 0 ) return NULL;/位置i在表中不存在 ListNode * p = first; int k = 0;/從表頭結(jié)點開始檢測 while ( p != NULL & k link

14、; k+; /循環(huán), p = NULL表示鏈短, 無第i個結(jié)點 return p;/否則k = i, 返回第i個結(jié)點地址(2) 實現(xiàn)求最大值的函數(shù)如下：template ListNode * List : Max ( ) /在單鏈表中進行一趟檢測，找出具有最大值的結(jié)點地址, 如果表空, 返回指針NULL if ( first-link = NULL ) return NULL;/空表, 返回指針NULL ListNode * pmax = first-link, p = first-link-link;/假定第一個結(jié)點中數(shù)據(jù)具有最大值 while ( p != NULL ) /循環(huán), 下一個結(jié)

15、點存在 if ( p-data pmax-data ) pmax = p;/指針pmax記憶當(dāng)前找到的具最大值結(jié)點 p = p-link;/檢測下一個結(jié)點 return pmax;(3) 實現(xiàn)統(tǒng)計單鏈表中具有給定值x的所有元素的函數(shù)如下：template int List : Count ( Type& x ) /在單鏈表中進行一趟檢測，找出具有最大值的結(jié)點地址, 如果表空, 返回指針NULL int n = 0; ListNode * p = first-link;/從第一個結(jié)點開始檢測 while ( p != NULL ) /循環(huán), 下一個結(jié)點存在 if ( p-data = x ) n

16、+;/找到一個, 計數(shù)器加1 p = p-link;/檢測下一個結(jié)點 return n;(4) 實現(xiàn)從一維數(shù)組An建立單鏈表的函數(shù)如下：template void List : Create ( Type A , int n ) /根據(jù)一維數(shù)組An建立一個單鏈表，使單鏈表中各元素的次序與An中各元素的次序相同 ListNode * p; first = p = new ListNode;/創(chuàng)建表頭結(jié)點 for ( int i = 0; i link = new ListNode ( Ai );/鏈入一個新結(jié)點, 值為Ai p = p-link;/指針p總指向鏈中最后一個結(jié)點 p-link =

17、NULL;采用遞歸方法實現(xiàn)時，需要通過引用參數(shù)將已建立的單鏈表各個結(jié)點鏈接起來。為此，在遞歸地掃描數(shù)組An的過程中，先建立單鏈表的各個結(jié)點，在退出遞歸時將結(jié)點地址p（被調(diào)用層的形參）帶回上一層（調(diào)用層）的實參p-link。template void List : create ( Type A , int n, int i, ListNode *& p ) /私有函數(shù)：遞歸調(diào)用建立單鏈表 if ( i = n ) p = NULL; else p = new ListNode( Ai );/建立鏈表的新結(jié)點create ( A, n, i+1, p-link );/遞歸返回時p-link中放入

18、下層p的內(nèi)容 template void List : create ( Type A , int n ) /外部調(diào)用遞歸過程的共用函數(shù) first = current = new ListNode;/建立表頭結(jié)點 create ( A, n, 0, first-link );/遞歸建立單鏈表 (5) 實現(xiàn)在非遞減有序的單鏈表中刪除值相同的多余結(jié)點的函數(shù)如下：template void List : tidyup ( ) ListNode * p = first-link, temp;/檢測指針, 初始時指向鏈表第一個結(jié)點 while ( p != NULL & p-link != NULL

19、)/循環(huán)檢測鏈表 if ( p-data = p-link-data ) /若相鄰結(jié)點所包含數(shù)據(jù)的值相等 temp = p-first; p-link = temp-link; /為刪除后一個值相同的結(jié)點重新拉鏈 delete temp; /刪除后一個值相同的結(jié)點 else p = p-link;/指針p進到鏈表下一個結(jié)點3-3 設(shè)ha和hb分別是兩個帶表頭結(jié)點的非遞減有序單鏈表的表頭指針, 試設(shè)計一個算法, 將這兩個有序鏈表合并成一個非遞增有序的單鏈表。要求結(jié)果鏈表仍使用原來兩個鏈表的存儲空間, 不另外占用其它的存儲空間。表中允許有重復(fù)的數(shù)據(jù)?！窘獯稹?include template cl

20、ass List;template class ListNode friend class List;public:ListNode ( ) : link ( NULL ) /構(gòu)造函數(shù), 僅初始化指針成員ListNode ( Type item, ListNde * next = NULL ) : data ( item ), link ( next ) private:/構(gòu)造函數(shù), 初始化數(shù)據(jù)與指針成員Type data;ListNode *link;template class List private:ListNode *first, *last;public:List ( Type f

21、inishied ) first = last = new ListNode( finished ); /建立鏈表, 在表頭結(jié)點的data域中存放數(shù)據(jù)輸入結(jié)束標(biāo)志, 它是表中不可能出現(xiàn)的數(shù)據(jù)void Merge ( List &hb );/連接鏈表friend istream& operator ( istream& in, List inList ); /輸入鏈表friend ostream& operator ( ostream& out, List outList );/輸出鏈表istream& operator ( istream& in, List inList ) Type val

22、ue;ListNode *p, *q, *s; in value; while ( value != inList.first-data ) /循環(huán)建立各個結(jié)點 s = new ListNode( value ); q = first; p = inList.first-link; /尋找新結(jié)點插入位置 while ( p != NULL & p-data link; q-link = s; s-link = p;/在q, p間插入新結(jié)點 if ( p = NULL ) inList.last = s; in value;ostream& operator ( ostream& out, Li

23、st outList ) coutnThe List is : n; ListNode *p = outList.first-link; while ( p != NULL ) out data; if ( p != last ) out ; else out link; template void List : Merge ( List& hb ) /將當(dāng)前鏈表this與鏈表hb按逆序合并，結(jié)果放在當(dāng)前鏈表this中。ListNode *pa, *pb, *q, *p; pa = first-link; pb = hb.first-link;/檢測指針跳過表頭結(jié)點first-link = N

24、ULL;/結(jié)果鏈表初始化while ( pa != NULL & pb != NULL ) /當(dāng)兩鏈表都未結(jié)束時 if ( pa-data data ) q = pa; pa = pa-link; /從pa鏈中摘下 else q = pb; pb = pb-link; /從pb鏈中摘下 qlink = first-link; first-link = q;/鏈入結(jié)果鏈的鏈頭p = ( pa != NULL ) ? pa : pb;/處理未完鏈的剩余部分while ( p != NULL ) q = p; p = p-link; q-link = first-link; first-link =

25、 q;3-4 設(shè)有一個表頭指針為h的單鏈表。試設(shè)計一個算法，通過遍歷一趟鏈表，將鏈表中所有結(jié)點的鏈接方向逆轉(zhuǎn)，如下圖所示。要求逆轉(zhuǎn)結(jié)果鏈表的表頭指針h指向原鏈表的最后一個結(jié)點?！窘獯?】template void List : Inverse ( ) if ( first = NULL ) return; ListNode *p = first-link, *pr = NULL; while ( p != NULL ) first-link = pr;/逆轉(zhuǎn)first指針 pr = first; first = p; p = p-link;/指針前移 first-link = pr;【解答2】

26、template void List : Inverse ( ) ListNode *p, *head = new ListNode ( );/創(chuàng)建表頭結(jié)點, 其link域默認(rèn)為NULL while ( first != NULL ) p = first; first = first-link;/摘下first鏈頭結(jié)點 p-link = head-link; head-link = p;/插入head鏈前端 first = head-link; delete head;/重置first, 刪去表頭結(jié)點3-5 從左到右及從右到左遍歷一個單鏈表是可能的，其方法是在從左向右遍歷的過程中將連接方向逆轉(zhuǎn)

27、，如右圖所示。在圖中的指針p指向當(dāng)前正在訪問的結(jié)點，指針pr指向指針p所指結(jié)點的左側(cè)的結(jié)點。此時，指針p所指結(jié)點左側(cè)的所有結(jié)點的鏈接方向都已逆轉(zhuǎn)。(1) 編寫一個算法，從任一給定的位置(pr, p)開始，將指針p右移k個結(jié)點。如果p移出鏈表，則將p置為0，并讓pr停留在鏈表最右邊的結(jié)點上。(2) 編寫一個算法，從任一給定的位置(pr, p)開始，將指針p左移k個結(jié)點。如果p移出鏈表，則將p置為0，并讓pr停留在鏈表最左邊的結(jié)點上。【解答】(1) 指針p右移k個結(jié)點template void List : siftToRight ( ListNode *& p, ListNode *& pr,

28、int k ) if ( p = NULL & pr != first ) /已經(jīng)在鏈的最右端 cout 已經(jīng)在鏈的最右端，不能再右移。 endl; return; int i; ListNode *q; if ( p = NULL )/從鏈頭開始 i = 1; pr = NULL; p = first; /重置p到鏈頭也算一次右移 else i = 0; while ( p != NULL & i link; p-link = pr;/鏈指針plink逆轉(zhuǎn)指向pr pr = p; p = q; i+;/指針pr, p右移 cout 右移了 i 個結(jié)點。 endl;(2) 指針p左移k個結(jié)點t

29、emplate void List :siftToLeft ( ListNode *& p, ListNode *& pr, int k ) if ( p = NULL & pr = first ) /已經(jīng)在鏈的最左端 cout 已經(jīng)在鏈的最左端，不能再左移。 endl; return; int i = 0; ListNode *q; while ( pr != NULL & i link; pr-link = p;/鏈指針pr-link逆轉(zhuǎn)指向p p = pr; pr = q; i+;/指針pr, p左移 cout 左移了 i 個結(jié)點。 endl; if ( i k ) pr = p; p

30、= NULL; /指針p移出表外，重置p, pr3-6 試寫出用單鏈表表示的字符串類及字符串結(jié)點類的定義，并依次實現(xiàn)它的構(gòu)造函數(shù)、以及計算串長度、串賦值、判斷兩串相等、求子串、兩串連接、求子串在串中位置等7個成員函數(shù)。要求每個字符串結(jié)點中只存放一個字符?！窘獯稹?用單鏈表表示的字符串類string1的頭文件string1.h#include const int maxLen = 300;/字符串最大長度為300（理論上可以無限長）class string1 public: string1 ( );/構(gòu)造空字符串 string1 ( char * obstr );/從字符數(shù)組建立字符串 stri

31、ng1 ( );/析構(gòu)函數(shù) int Length ( ) const return curLen; /求字符串長度 string1& operator = ( string1& ob );/串賦值 int operator = ( string1& ob );/判兩串相等 char operator ( int i );/取串中字符 string1 operator ( ) ( int pos, int len );/取子串 string1& operator += ( string1& ob );/串連接 int Find ( string1& ob );/求子串在串中位置(模式匹配) fr

32、iend ostream& operator ( istream& is, string1& ob );private: ListNode*chList;/用單鏈表存儲的字符串 int curLen;/當(dāng)前字符串長度/單鏈表表示的字符串類string1成員函數(shù)的實現(xiàn)，在文件string1.cpp中#include #include string1.hstring1 : string1( ) /構(gòu)造函數(shù) chList = new ListNode ( 0 ); curLen = 0;string1 : string1( char *obstr ) /復(fù)制構(gòu)造函數(shù) curLen = 0; List

33、Node *p = chList = new ListNode ( *obstr ); while ( *obstr != 0 ) obstr+; p = p-link = new ListNode ( *obstr ); curLen+; string1& string1 : operator = ( string1& ob ) /串賦值 ListNode *p = ob.chList; ListNode *q = chList = new ListNode ( p-data ); curLen = ob.curLen; while ( p-data != 0 ) p = p-link; q

34、 = q-link = new ListNode ( p-data ); return this; int string1 : operator = ( string1& ob ) /判兩串相等 if ( curLen != ob.curLen ) return 0; ListNode *p = chList, *q = ob.chList; for ( int i = 0; i data != q-data ) return 0; else p = p-link; q = q-link; return 1; char string1 : operator ( int i ) /取串中字符 i

35、f ( i = 0 & i curLen ) ListNode *p = chList; int k = 0; while ( p != NULL & k link; k+; if ( p != NULL ) return p-data; return 0;string1 string1 : operator ( ) ( int pos, int len ) /取子串 string1 temp; if ( pos = 0 & len = 0 & pos curLen & pos + len - 1 curLen ) ListNode *q, *p = chList; for ( int k =

36、 0; k link;/定位于第pos結(jié)點 q = temp.chList = new ListNode ( p-data ); for ( int i = 1; i link; q = q-link = new ListNode ( p-data ); q-link = new ListNode ( 0 );/建立串結(jié)束符 temp.curLen = len; else temp.curLen = 0; temp.chList = new ListNode ( 0 ); return temp;string1& string1 : operator += ( string1& ob ) /串

37、連接 if ( curLen + ob.curLen maxLen ) len = maxLen - curLen; else len = ob.curLen;/傳送字符數(shù) ListNode *q = ob.chList, *p = chList; for ( int k = 0; k link;/this串的串尾 k = 0; for ( k = 0; k link = new ListNode ( q-data ); q = q-link; plink = new ListNode ( 0 ); return this;int string1 : Find ( string1& ob )

38、/求子串在串中位置(模式匹配) int slen = curLen, oblen = ob.curLen, i = slen - oblen; string1 temp = this; while ( i -1 ) if ( temp( i, oblen ) = ob ) break; else i- ; return i;3-7 如果用循環(huán)鏈表表示一元多項式，試編寫一個函數(shù)Polynomial : Calc(x)，計算多項式在x處的值。【解答】下面給出表示多項式的循環(huán)鏈表的類定義。作為私有數(shù)據(jù)成員，在鏈表的類定義中封裝了3個鏈接指針：first、last和current，分別指示鏈表的表頭結(jié)

39、點、鏈尾結(jié)點和最后處理到的結(jié)點。class Polynomal;/多項式前視類定義class Term /項類定義friend class Polynomal;private: double coef; /系數(shù) int expn;/指數(shù) Term *link;/項鏈接指針public: Term ( double c = 0, int e = 0, Term * next = NULL ) : coef (c), expn(e), link (next) class Polynomal /多項式類定義private: Term *first, *current;/頭指針, 當(dāng)前指針 int n

40、;/多項式階數(shù)public: Polynomal ( );/構(gòu)造函數(shù) Polynomal ( );/析構(gòu)函數(shù) int Length ( ) const;/計算多項式項數(shù) int IsEmpty ( ) return first-link = first; /判是否零多項式 int Find ( int value );/在多項式中尋找其指數(shù)值等于value的項 int getExpn ( ) const;/返回當(dāng)前項中存放的指數(shù)值 double getCoef ( ) const;/返回當(dāng)前項中存放的系數(shù)值 void Firster ( ) current = first; /將當(dāng)前指針置于頭

41、結(jié)點 int First ( );/將當(dāng)前指針指向鏈表的第一個結(jié)點 int Next ( );/將當(dāng)前指針指到當(dāng)前結(jié)點的后繼結(jié)點 int Prior ( );/將當(dāng)前指針指到當(dāng)前結(jié)點的前驅(qū)結(jié)點 void Insert ( const double coef, int expn );/插入新結(jié)點 void Remove ( );/刪除當(dāng)前結(jié)點 double Calc ( double x );/求多項式的值 friend Polynomial operator + ( Polynomial &, Polynomial & ); friend Polynomial operator * ( Pol

42、ynomial &, Polynomial & ); ;對于多項式Pn(x) = a0 + a1x + a2x2 + a3x3 + + an-1xn-1 + anxn，可用Horner規(guī)則將它改寫求值：Pn(x) = a0 + (a1x + ( a2 + ( a3 + + ( an-1 + an*x )*x )*x )*x )*x因為不是順序表，必須采用遞歸算法實現(xiàn)：返回求值Value(n) = a0 + Value(n-1)*xValue(n-1) = a1 + Value(n-2)*xValue(1) = an-1 + Value(0)Value(0) = an遞歸求解double Pol

43、ynomal : Value ( Term *p, double x ) /私有函數(shù)：遞歸求子多項式的值 if ( p-link = first ) return p-coef; else return p-coef + x * Value ( p-link, x );double Polynomal : Calc ( double x ) /共有函數(shù)：遞歸求多項式的值 Term * pc = first-link; return ( pc = first ) ? 0.0 : Value ( pc, x ); 但當(dāng)多項式中許多項的系數(shù)為0時變成稀疏多項式，如P50(x) = a0 + a13x

44、13 + a35x35 + a50x50，為節(jié)省存儲起見，鏈表中不可能保存有零系數(shù)的結(jié)點。此時，求值函數(shù)要稍加改變：#include double Polynomal : Value ( Term *p, double e, double x ) /私有函數(shù)：遞歸求子多項式的值。pow(x, y)是求x的y次冪的函數(shù), 它的原型在“math.h”中 if ( p-link = first ) return p-coef; else return p-coef + pow( x, p-expn e ) * Value ( p-link, p-expn, x );double Polynomal

45、: Calc ( double x ) /共有函數(shù)：遞歸求多項式的值 Term * pc = first-link; return ( pc = first ) ? 0.0 : Value ( pc, 0, x ); 3-8 設(shè)a和b是兩個用帶有表頭結(jié)點的循環(huán)鏈表表示的多項式。試編寫一個算法，計算這兩個多項式的乘積c = a*b，要求計算后多項式a與b保持原狀。如果這兩個多項式的項數(shù)分別為n與m, 試說明該算法的執(zhí)行時間為O(nm2)或O(n2m)。但若a和b是稠密的, 即其很少有系數(shù)為零的項, 那么試說明該乘積算法的時間代價為O(nm)。【解答】假設(shè)則它們的乘積為例如，a = 1 + 2x

46、+ 3x2 + 4x3 + 5x4, b = 6 + 7x + 8x2 + 9x3, 它們的乘積 c = (1+2x+3x2+4x3+5x4)*(6+7x+8x2+9x3) = = 1*6 + (1*7+2*6)x +(1*8+2*7+3*6)x2+(1*9+2*8+3*7+4*6)x3+ + (2*9+3*8+4*7+5*6)x4+ (3*9+4*8+5*7)x5+(4*9+5*8)x6+5*9x7在求解過程中，固定一個ai，用它乘所有bj，得到xi+j的系數(shù)的一部分。這是一個二重循環(huán)。1*61*71*81*9 i = 0 : 1*61*7+2*61*8+2*71*9+2*82*9 i = 1 : 1*61*7+2*61*8+2*7+3*61*9+2*8+3*72*9+3*83*9 i = 2 :1*61*7+2*61*8+2*7+3*61*9+2*8+3*7+4*62*9+3*8+4*73*9+4*84*9 i = 3 : 3*9+4*8+5*74*9+5*85*91*61*8+2*7+3