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

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

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

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

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

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

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

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

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

9、。#ifndef LIST_H/將單鏈表定義在List.h#define LIST_Htemplate class List;/前視的類定義template class ListNode /鏈表結(jié)點(diǎn)類的定義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é)點(diǎn)的下一結(jié)點(diǎn)地址 Type getData ( ) return data; /取得結(jié)點(diǎn)中的數(shù)據(jù) void setLink ( ListNode * next ) link = next; /修改結(jié)點(diǎn)的link指針 void setData ( Type value ) data = value; /修改結(jié)點(diǎn)的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;/計(jì)算鏈表的長度 ListNode * Find ( Type value );/搜索含value的元素并成為當(dāng)前元素 ListNode * Locate( int i );/搜索第i個(gè)元素并置為當(dāng)前元素 Type GetData ( ) return curren

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

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

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

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

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

17、NULL;采用遞歸方法實(shí)現(xiàn)時(shí)，需要通過引用參數(shù)將已建立的單鏈表各個(gè)結(jié)點(diǎn)鏈接起來。為此，在遞歸地掃描數(shù)組An的過程中，先建立單鏈表的各個(gè)結(jié)點(diǎn)，在退出遞歸時(shí)將結(jié)點(diǎn)地址p（被調(diào)用層的形參）帶回上一層（調(diào)用層）的實(shí)參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é)點(diǎn)create ( A, n, i+1, p-link );/遞歸返回時(shí)p-link中放入

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

19、)/循環(huán)檢測鏈表 if ( p-data = p-link-data ) /若相鄰結(jié)點(diǎn)所包含數(shù)據(jù)的值相等 temp = p-first; p-link = temp-link; /為刪除后一個(gè)值相同的結(jié)點(diǎn)重新拉鏈 delete temp; /刪除后一個(gè)值相同的結(jié)點(diǎn) else p = p-link;/指針p進(jìn)到鏈表下一個(gè)結(jié)點(diǎn)3-3 設(shè)ha和hb分別是兩個(gè)帶表頭結(jié)點(diǎn)的非遞減有序單鏈表的表頭指針, 試設(shè)計(jì)一個(gè)算法, 將這兩個(gè)有序鏈表合并成一個(gè)非遞增有序的單鏈表。要求結(jié)果鏈表仍使用原來兩個(gè)鏈表的存儲(chǔ)空間, 不另外占用其它的存儲(chǔ)空間。表中允許有重復(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é)點(diǎn)的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)建立各個(gè)結(jié)點(diǎn) s = new ListNode( value ); q = first; p = inList.first-link; /尋找新結(jié)點(diǎn)插入位置 while ( p != NULL & p-data link; q-link = s; s-link = p;/在q, p間插入新結(jié)點(diǎn) 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é)點(diǎn)first-link = N

24、ULL;/結(jié)果鏈表初始化while ( pa != NULL & pb != NULL ) /當(dāng)兩鏈表都未結(jié)束時(shí) 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è)有一個(gè)表頭指針為h的單鏈表。試設(shè)計(jì)一個(gè)算法，通過遍歷一趟鏈表，將鏈表中所有結(jié)點(diǎn)的鏈接方向逆轉(zhuǎn)，如下圖所示。要求逆轉(zhuǎn)結(jié)果鏈表的表頭指針h指向原鏈表的最后一個(gè)結(jié)點(diǎn)?！窘獯?】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é)點(diǎn), 其link域默認(rèn)為NULL while ( first != NULL ) p = first; first = first-link;/摘下first鏈頭結(jié)點(diǎn) p-link = head-link; head-link = p;/插入head鏈前端 first = head-link; delete head;/重置first, 刪去表頭結(jié)點(diǎn)3-5 從左到右及從右到左遍歷一個(gè)單鏈表是可能的，其方法是在從左向右遍歷的過程中將連接方向逆轉(zhuǎn)

27、，如右圖所示。在圖中的指針p指向當(dāng)前正在訪問的結(jié)點(diǎn)，指針pr指向指針p所指結(jié)點(diǎn)的左側(cè)的結(jié)點(diǎn)。此時(shí)，指針p所指結(jié)點(diǎn)左側(cè)的所有結(jié)點(diǎn)的鏈接方向都已逆轉(zhuǎn)。(1) 編寫一個(gè)算法，從任一給定的位置(pr, p)開始，將指針p右移k個(gè)結(jié)點(diǎn)。如果p移出鏈表，則將p置為0，并讓pr停留在鏈表最右邊的結(jié)點(diǎn)上。(2) 編寫一個(gè)算法，從任一給定的位置(pr, p)開始，將指針p左移k個(gè)結(jié)點(diǎn)。如果p移出鏈表，則將p置為0，并讓pr停留在鏈表最左邊的結(jié)點(diǎn)上?！窘獯稹?1) 指針p右移k個(gè)結(jié)點(diǎn)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 個(gè)結(jié)點(diǎn)。 endl;(2) 指針p左移k個(gè)結(jié)點(diǎn)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 個(gè)結(jié)點(diǎn)。 endl; if ( i k ) pr = p; p

30、= NULL; /指針p移出表外，重置p, pr3-6 試寫出用單鏈表表示的字符串類及字符串結(jié)點(diǎn)類的定義，并依次實(shí)現(xiàn)它的構(gòu)造函數(shù)、以及計(jì)算串長度、串賦值、判斷兩串相等、求子串、兩串連接、求子串在串中位置等7個(gè)成員函數(shù)。要求每個(gè)字符串結(jié)點(diǎn)中只存放一個(gè)字符?！窘獯稹?用單鏈表表示的字符串類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;/用單鏈表存儲(chǔ)的字符串 int curLen;/當(dāng)前字符串長度/單鏈表表示的字符串類string1成員函數(shù)的實(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é)點(diǎn) 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)鏈表表示一元多項(xiàng)式，試編寫一個(gè)函數(shù)Polynomial : Calc(x)，計(jì)算多項(xiàng)式在x處的值。【解答】下面給出表示多項(xiàng)式的循環(huán)鏈表的類定義。作為私有數(shù)據(jù)成員，在鏈表的類定義中封裝了3個(gè)鏈接指針：first、last和current，分別指示鏈表的表頭結(jié)

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

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

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

42、ynomial &, Polynomial & ); ;對(duì)于多項(xiàng)式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因?yàn)椴皇琼樞虮?，必須采用遞歸算法實(shí)現(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ù)：遞歸求子多項(xiàng)式的值 if ( p-link = first ) return p-coef; else return p-coef + x * Value ( p-link, x );double Polynomal : Calc ( double x ) /共有函數(shù)：遞歸求多項(xiàng)式的值 Term * pc = first-link; return ( pc = first ) ? 0.0 : Value ( pc, x ); 但當(dāng)多項(xiàng)式中許多項(xiàng)的系數(shù)為0時(shí)變成稀疏多項(xiàng)式，如P50(x) = a0 + a13x

44、13 + a35x35 + a50x50，為節(jié)省存儲(chǔ)起見，鏈表中不可能保存有零系數(shù)的結(jié)點(diǎn)。此時(shí)，求值函數(shù)要稍加改變：#include double Polynomal : Value ( Term *p, double e, double x ) /私有函數(shù)：遞歸求子多項(xiàng)式的值。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ù)：遞歸求多項(xiàng)式的值 Term * pc = first-link; return ( pc = first ) ? 0.0 : Value ( pc, 0, x ); 3-8 設(shè)a和b是兩個(gè)用帶有表頭結(jié)點(diǎn)的循環(huán)鏈表表示的多項(xiàng)式。試編寫一個(gè)算法，計(jì)算這兩個(gè)多項(xiàng)式的乘積c = a*b，要求計(jì)算后多項(xiàng)式a與b保持原狀。如果這兩個(gè)多項(xiàng)式的項(xiàng)數(shù)分別為n與m, 試說明該算法的執(zhí)行時(shí)間為O(nm2)或O(n2m)。但若a和b是稠密的, 即其很少有系數(shù)為零的項(xiàng), 那么試說明該乘積算法的時(shí)間代價(jià)為O(nm)?！窘獯稹考僭O(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在求解過程中，固定一個(gè)ai，用它乘所有bj，得到xi+j的系數(shù)的一部分。這是一個(gè)二重循環(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