C程序設(shè)計(jì)習(xí)題答案

1、第七章 動(dòng)態(tài)內(nèi)存分配習(xí)題一、基本概念與基礎(chǔ)知識(shí)自測(cè)題7.1 填空題7.1.1 C/C+定義了4個(gè)內(nèi)存區(qū)間： （1） 、 （2） 、 （3） 和 （4） 。答案：（1）代碼區(qū)，存放程序代碼； （2）全局變量與靜態(tài)變量區(qū)，存放全局變量或?qū)ο螅òo態(tài)）；（3）局部變量區(qū)即棧（stack）區(qū)，存放局部變量；（4）自由存儲(chǔ)區(qū)（free store），即動(dòng)態(tài)存儲(chǔ)區(qū)或堆（heap）區(qū)。7.1.2 靜態(tài)定義的變量和對(duì)象用標(biāo)識(shí)符命名，稱為 （1） ；而動(dòng)態(tài)建立的稱為 （2） ，動(dòng)態(tài)建立對(duì)象的初始化是通過(guò) （3） 實(shí)現(xiàn) （4） 。答案：（1）命名對(duì)象（2）無(wú)名對(duì)象（3）初始化式(initializer) （4）

2、顯式初始化7.1.3 在用new運(yùn)算符建立一個(gè)三維數(shù)組15*30*10時(shí)，使用了 （1） 個(gè)下標(biāo)運(yùn)算符，對(duì)應(yīng)的用delete運(yùn)算符注銷這個(gè)三維數(shù)組時(shí)使用了 （2） 個(gè)下標(biāo)運(yùn)算符。new返回的指針是指向 （3） 的指針。答案：（1）3個(gè)（2）1個(gè)（3）30行10列的2位數(shù)組7.1.4 當(dāng)動(dòng)態(tài)分配失敗，系統(tǒng)采用 （1） 來(lái)表示發(fā)生了異常。如果new返回的指針丟失，則所分配的自由存儲(chǔ)區(qū)空間無(wú)法收回，稱為 （2） 。這部分空間必須在 （3） 才能找回，這是因?yàn)闊o(wú)名對(duì)象的生命期 （4） 。答案：（1）返回一個(gè)空指針（NULL）（2）內(nèi)存泄漏（3）重新啟動(dòng)計(jì)算機(jī)后（4）并不依賴于建立它的作用域7.1.5

3、按語(yǔ)義的默認(rèn)復(fù)制構(gòu)造函數(shù)和默認(rèn)復(fù)制賦值操作符實(shí)現(xiàn)的復(fù)制稱為 （1） ，假設(shè)類對(duì)象obj中有一個(gè)數(shù)據(jù)成員為指針，并為這個(gè)指針動(dòng)態(tài)分配一個(gè)堆對(duì)象，如用obj1按成員語(yǔ)義拷貝了一個(gè)對(duì)象obj2，則obj2對(duì)應(yīng)指針指向 （2） 。答案：（1）淺拷貝（2）同一個(gè)堆對(duì)象7.1.6 單鏈表的結(jié)點(diǎn)包含兩個(gè)域： （1） 和 （2） 。使用鏈表的最大的優(yōu)點(diǎn)是 （3） ，即使是動(dòng)態(tài)數(shù)組也做不到這一點(diǎn)。答案：（1）數(shù)據(jù)域（2）指針域（3）用多少空間，開(kāi)多少空間7.1.7 進(jìn)入單鏈表必須通過(guò)單鏈表的 （1） ，如果它丟失則 （2） ，內(nèi)存也 （3） ，在單鏈表中進(jìn)行的查找只能是 （4） 。答案：（1）頭指針（2）鏈表整

4、個(gè)丟失（3）會(huì)發(fā)生泄漏（4）順序查找7.1.8 對(duì)鏈棧，鏈的生成必須是向 （1） 生成，最新壓棧的元素（結(jié)點(diǎn)），放在 （2） 位置，彈出時(shí)從 （3） 刪除結(jié)點(diǎn)。對(duì)鏈隊(duì)，采用向 （4） 生成，新入隊(duì)的結(jié)點(diǎn)放在鏈的 （5） ，出隊(duì)操作在 （6） 位置。答案：（1）向前（2）鏈表頭的位置（3）鏈表頭（4）向后（5）尾部（6）鏈表頭7.1.9 在計(jì)算機(jī)中進(jìn)行表達(dá)式的計(jì)算，為解決優(yōu)先級(jí)和運(yùn)算的結(jié)合性，必須使用 （1） 和 （2） 。在中綴表達(dá)式中，每個(gè)雙目運(yùn)算符放在 （3） 。答案：（1）數(shù)棧（2）運(yùn)算符棧（3）它的兩個(gè)運(yùn)算符之間7.1.10 為了能重復(fù)利用一個(gè)隊(duì)空間，要求把隊(duì)說(shuō)明成一個(gè)邏輯上的 （1）

5、 。答案：（1）循環(huán)隊(duì)列7.1.11 二叉樹(shù)的特點(diǎn)是： （1） 和 （2） 。答案：（1）每個(gè)結(jié)點(diǎn)最多有兩個(gè)孩子（2）子樹(shù)有左右之分7.1.12 二叉樹(shù)的遍歷是按 （1） 分類，所謂中序遍歷是 （2） 。答案：（1）訪問(wèn)子樹(shù)根節(jié)點(diǎn)次序（2）先遍歷該子樹(shù)根結(jié)點(diǎn)的左子樹(shù)回來(lái)后，接著再訪問(wèn)根結(jié)點(diǎn)，最后遍歷右子樹(shù)7.1.13 二叉排序樹(shù)又稱 （1） 或 （2） 。其左子樹(shù)上的所有結(jié)點(diǎn)均小于根結(jié)點(diǎn)的數(shù)據(jù)值，而右子樹(shù)上的所有結(jié)點(diǎn)均大于根結(jié)點(diǎn)的數(shù)據(jù)值時(shí)，采用 （3） 就可以得到一個(gè) （4） 。答案：（1）二叉搜索樹(shù)（2）樹(shù)表（3）中序遍歷（4）升序序列7.2 簡(jiǎn)答題7.2.1 new運(yùn)算符為一個(gè)變量或?qū)ο蠓?/p>

6、配存儲(chǔ)空間和為一個(gè)數(shù)組分配存儲(chǔ)空間，使用方法上有什么不同？對(duì)應(yīng)的delete運(yùn)算符使用有什么不同？答：為一個(gè)變量或?qū)ο蠓峙浯鎯?chǔ)空間其使用的格式如下：指針變量名=new 類型名(初始化式)；對(duì)于數(shù)組進(jìn)行動(dòng)態(tài)分配和撤銷的格式為：指針變量名=new 類型名下標(biāo)表達(dá)式;后者多一個(gè)下標(biāo)表達(dá)式，同時(shí)不能進(jìn)行初始化。對(duì)應(yīng)的delete運(yùn)算符使用分別為：delete 指針名;delete 指向該數(shù)組的指針變量名;后者多一個(gè)方括號(hào)，如果delete語(yǔ)句中少了方括號(hào)，因編譯器認(rèn)為該指針是指向數(shù)組第一個(gè)元素的指針，會(huì)產(chǎn)生回收不徹底的問(wèn)題（只回收了第一個(gè)元素所占空間），加了方括號(hào)后就轉(zhuǎn)化為指向數(shù)組的指針，回收整個(gè)數(shù)組

7、。delete 的方括號(hào)中不需要填數(shù)組元素?cái)?shù)，系統(tǒng)自知。即使寫(xiě)了，編譯器也忽略。7.2.2 用delete刪除p所指向的無(wú)名對(duì)象時(shí)，p指針也同時(shí)被刪除了，對(duì)不對(duì)？為什么？答：不對(duì)。注意這時(shí)釋放了p所指向的無(wú)名對(duì)象占用的內(nèi)存空間，也就是撤銷了該無(wú)名對(duì)象，稱動(dòng)態(tài)內(nèi)存釋放（dynamic memory deallocation），但指針p本身并沒(méi)有撤銷，它仍然存在，該指針?biāo)純?nèi)存空間并未釋放。7.2.3 為什么動(dòng)態(tài)建立類對(duì)象數(shù)組時(shí)，類的定義一定要有缺省的構(gòu)造函數(shù)？答：new后面類（class）類型也可以有參數(shù)。這些參數(shù)即構(gòu)造函數(shù)的參數(shù)。但對(duì)創(chuàng)建數(shù)組，沒(méi)有參數(shù)，只能調(diào)用缺省的構(gòu)造函數(shù)。7.2.4 要實(shí)

8、現(xiàn)深拷貝，自定義的拷貝構(gòu)造函數(shù)應(yīng)該怎樣設(shè)計(jì)？答：如果類中有一個(gè)數(shù)據(jù)成員為指針，該類的一個(gè)對(duì)象中的這個(gè)指針p，指向了動(dòng)態(tài)分配的一個(gè)堆對(duì)象。深拷貝時(shí)要給新建立的對(duì)象獨(dú)立分配一個(gè)堆對(duì)象。這時(shí)拷貝的構(gòu)造函數(shù)應(yīng)該設(shè)計(jì)為：先拷貝對(duì)象主體，再為新建對(duì)象的指針?lè)峙湟粋€(gè)堆對(duì)象，最后用原對(duì)象的堆對(duì)象拷貝新對(duì)象的堆對(duì)象。即分三步完成。7.2.5 在單鏈表模板中為什么要把List類說(shuō)明成Node的友元類？答：為了直接訪問(wèn)結(jié)點(diǎn)的私有成員數(shù)據(jù)，以簡(jiǎn)化程序。7.2.6 雙向鏈表與單向鏈表相比，操作上有什么優(yōu)點(diǎn)?答：雙向鏈表可以很方便地找到表結(jié)點(diǎn)的前驅(qū)和后繼。單鏈表只能找后繼。如要找前驅(qū)，必須從表頭開(kāi)始搜索，并一般要用兩個(gè)工

9、作指針。7.2.7 對(duì)比順序棧與鏈棧各自的長(zhǎng)處和短處。答：順序?？梢噪S機(jī)訪問(wèn)其中的元素，而鏈棧只能順序訪問(wèn)。順序棧必須先開(kāi)一定大小內(nèi)存空間，執(zhí)行起來(lái)簡(jiǎn)單，速度快，但可能溢出。鏈棧內(nèi)存空間隨用隨開(kāi)，不會(huì)溢出，但執(zhí)行復(fù)雜（不斷地動(dòng)態(tài)分配），速度慢。7.2.8 寫(xiě)出二叉樹(shù)的定義。答：二叉樹(shù)是結(jié)點(diǎn)的一個(gè)有限集合，該集合或?yàn)榭眨蚴怯梢粋€(gè)根結(jié)點(diǎn)及兩棵分別稱為左子樹(shù)和右子樹(shù)的（注意有左右之分）互不相交的二叉樹(shù)組成，其中左右子樹(shù)分別可以為空子樹(shù)或均為空樹(shù)。7.2.9 什么是二叉樹(shù)的遍歷？答：所謂二叉樹(shù)的遍歷（binary tree traversal），就是遵從某種次序，查巡二叉樹(shù)的所有結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)都被訪

10、問(wèn)一次，而且僅訪問(wèn)一次。所謂“訪問(wèn)”指對(duì)結(jié)點(diǎn)施行某些操作，但不破壞它原來(lái)的數(shù)據(jù)結(jié)構(gòu)。二、編程與綜合練習(xí)題7.3 給單鏈表類模板增加兩個(gè)成員函數(shù)：刪除鏈表中所有數(shù)據(jù)域?yàn)橹付ㄖ档慕Y(jié)點(diǎn)和取出鏈表中第K個(gè)元素（從1開(kāi)始計(jì)數(shù)）。解：這兩個(gè)成員函數(shù)添在單鏈表類模板中（ep7_3.h）本例數(shù)據(jù)域用了標(biāo)準(zhǔn)類string，也可以使用整數(shù)型。/ep7_3.h#include<iostream>using namespace std;/首先看結(jié)點(diǎn)組織，采用結(jié)點(diǎn)類，凡與結(jié)點(diǎn)數(shù)據(jù)和指針操作有關(guān)函數(shù)作為成員函數(shù)template<typename T>class List;template<t

11、ypename T>class NodeT info; /數(shù)據(jù)域Node<T> *link; /指針域public:Node(); /生成頭結(jié)點(diǎn)的構(gòu)造函數(shù)Node(const T & data);/生成一般結(jié)點(diǎn)的構(gòu)造函數(shù)void InsertAfter(Node<T>* P); /在當(dāng)前結(jié)點(diǎn)后插入一個(gè)結(jié)點(diǎn)Node<T>* RemoveAfter(); /刪除當(dāng)前結(jié)點(diǎn)的后繼結(jié)點(diǎn)，返回該結(jié)點(diǎn)備用T & Getinfo();/增加取數(shù)據(jù)域函數(shù)friend class List<T>/以List為友元類，List可直接訪問(wèn)Node的

12、私有函數(shù)，與結(jié)構(gòu)一樣方便，但更安全;template <typename T> Node<T>:Node()link=NULL;template <typename T> Node<T>:Node(const T & data)info=data;link=NULL;template<typename T>void Node<T>:InsertAfter(Node<T>* p)p->link=link;link=p;template<typename T>Node<T>*

13、Node<T>:RemoveAfter()Node<T>* tempP=link;if(link=NULL) tempP=NULL; /已在鏈尾,后面無(wú)結(jié)點(diǎn)else link=tempP->link;return tempP;template<typename T> T & Node<T>:Getinfo()return info;/增加取數(shù)據(jù)域函數(shù)/再定義鏈表類，選擇常用操作：包括建立有序鏈表、搜索遍歷、插入、刪除、取數(shù)據(jù)等template<typename T>class ListNode<T> *hea

14、d,*tail;/鏈表頭指針和尾指針public:List(); /構(gòu)造函數(shù)，生成頭結(jié)點(diǎn)(空鏈表)List(); /析構(gòu)函數(shù)void MakeEmpty(); /清空一個(gè)鏈表，只余表頭結(jié)點(diǎn)Node<T>* Find(T data); /搜索數(shù)據(jù)域與data相同的結(jié)點(diǎn)，返回該結(jié)點(diǎn)的地址int Length(); /計(jì)算單鏈表長(zhǎng)度void PrintList(); /打印鏈表的數(shù)據(jù)域 void InsertFront(Node<T>* p); /可用來(lái)向前生成鏈表，在表頭插入一個(gè)結(jié)點(diǎn)void InsertRear(Node<T>* p); /可用來(lái)向后生成鏈表，

15、在表尾添加一個(gè)結(jié)點(diǎn)void InsertOrder(Node<T> *p); /按升序生成鏈表Node<T>*CreatNode(T data); /創(chuàng)建一個(gè)結(jié)點(diǎn)(孤立結(jié)點(diǎn))Node<T>*DeleteNode(Node<T>* p); /刪除指定結(jié)點(diǎn)Node<T>*RemoveAll(T &); /刪除鏈表中所有數(shù)據(jù)域?yàn)橹付ㄖ档慕Y(jié)點(diǎn)Node<T>*GetNode(int); /取出鏈表中第K個(gè)元素（從1開(kāi)始計(jì)數(shù)）;template<typename T>List<T>:List()head

16、=tail=new Node<T>();template<typename T>List<T>:List()MakeEmpty();delete head;template<typename T>void List<T>:MakeEmpty()Node<T> *tempP;while(head->link!=NULL)tempP=head->link;head->link=tempP->link; /把頭結(jié)點(diǎn)后的第一個(gè)節(jié)點(diǎn)從鏈中脫離delete tempP; /刪除(釋放)脫離下來(lái)的結(jié)點(diǎn)tail=h

17、ead; /表頭指針與表尾指針均指向表頭結(jié)點(diǎn)，表示空鏈template<typename T> Node<T>* List<T>:Find(T data)Node<T> *tempP=head->link;while(tempP!=NULL&&tempP->info!=data) tempP=tempP->link;return tempP; /搜索成功返回該結(jié)點(diǎn)地址，不成功返回NULLtemplate<typename T>int List<T>:Length()Node<T>

18、;* tempP=head->link;int count=0;while(tempP!=NULL)tempP=tempP->link;count+;return count;template<typename T>void List<T>:PrintList()Node<T>* tempP=head->link;while(tempP!=NULL)cout<<tempP->info<<'t'tempP=tempP->link;cout<<endl;template<ty

19、pename T>void List<T>:InsertFront(Node<T> *p)p->link=head->link;head->link=p;if(tail=head) tail=p;template<typename T>void List<T>:InsertRear(Node<T> *p)p->link=tail->link;tail->link=p;tail=p;template<typename T>void List<T>:InsertOrder(

20、Node<T> *p)Node<T> *tempP=head->link,*tempQ=head; /tempQ指向tempP前面的一個(gè)節(jié)點(diǎn)while(tempP!=NULL)if(p->info<tempP->info)break; /找第一個(gè)比插入結(jié)點(diǎn)大的結(jié)點(diǎn)，由tempP指向tempQ=tempP;tempP=tempP->link;tempQ->InsertAfter(p); /插在tempP指向結(jié)點(diǎn)之前，tempQ之后if(tail=tempQ) tail=tempQ->link;template<typenam

21、e T>Node<T>* List<T>:CreatNode(T data)/建立新節(jié)點(diǎn)Node<T>*tempP=new Node<T>(data);return tempP;template<typename T>Node<T>* List<T>:DeleteNode(Node<T>* p)Node<T>* tempP=head;while(tempP->link!=NULL&&tempP->link!=p) tempP=tempP->link

22、;if(tempP->link=tail) tail=tempP;return tempP->RemoveAfter(); /本函數(shù)所用方法可省一個(gè)工作指針template<typename T> Node<T>* List<T>:RemoveAll(T &p)/利用已有的DeleteNode()bool b=false;Node<T>*TempP=head->link,*TempR;while(TempP!=NULL) /也可以利用尾指針if(TempP->info=p) TempR=DeleteNode(Tem

23、pP);TempP=TempP->link;return TempR;template<typename T> Node<T>* List<T>:GetNode(int i)/取出鏈表中第K個(gè)元素(從1計(jì)數(shù))Node<T>*TempP=head->link;int j=1;if(i<0) return NULL;if(i=0) return head;while(TempP!=NULL&&j<i)TempP=TempP->link;j+;return TempP;/ep7_3.cpp#include&

24、quot;ep7_3.h"#include<string>using namespace std;int main()const int h=9;int i;List<string> list1;Node<string> *n1,*P1;string m("東南大學(xué)"),sph="南京大學(xué)","東南大學(xué)","交通大學(xué)","清華大學(xué)","天津大學(xué)","東南大學(xué)","復(fù)旦大學(xué)","浙江

25、大學(xué)","同濟(jì)大學(xué)"cout<<"按原始數(shù)據(jù)次序輸出："<<endl;for(i=0;i<h;i+) cout<<spi<<'t'cout<<endl;for(i=0;i<h;i+)P1=list1.CreatNode(spi);list1.InsertFront(P1); /向前生成list1cout<<"輸出向前生成的鏈表："<<endl;list1.PrintList();list1.RemoveAll(m)

26、;cout<<"輸出刪除所有指定結(jié)點(diǎn)后的鏈表："<<endl;list1.PrintList();cout<<"要求尋找第幾個(gè)節(jié)點(diǎn)？"<<endl;cin>>i;n1=list1.GetNode(i);cout<<n1->Getinfo();return 0;7.4 為單鏈表類模板增加一個(gè)拷貝構(gòu)造函數(shù)和拷貝賦值運(yùn)算符（=）。解：為簡(jiǎn)單數(shù)據(jù)域使用整數(shù)型。注意：從7.3開(kāi)始逐題完善單鏈表類模板，即前一題增加的成員函數(shù)在本題中全部保留。拷貝構(gòu)造函數(shù)先建立一個(gè)頭結(jié)點(diǎn)，再以原鏈表的各結(jié)點(diǎn)

27、的數(shù)據(jù)域來(lái)構(gòu)造新鏈表的各對(duì)應(yīng)結(jié)點(diǎn)。如果看不懂拷貝構(gòu)造函數(shù)請(qǐng)畫(huà)一個(gè)空鏈表，逐步跟蹤拷貝過(guò)程，只要跟蹤幾個(gè)結(jié)點(diǎn)就可以理解。/ep7_4.h#include<iostream>using namespace std;/首先看結(jié)點(diǎn)組織，采用結(jié)點(diǎn)類，凡與結(jié)點(diǎn)數(shù)據(jù)和指針操作有關(guān)函數(shù)作為成員函數(shù)template<typename T>class List;template<typename T>class NodeT info; /數(shù)據(jù)域Node<T> *link; /指針域public:Node(); /生成頭結(jié)點(diǎn)的構(gòu)造函數(shù)Node(const T &

28、; data); /生成一般結(jié)點(diǎn)的構(gòu)造函數(shù)void InsertAfter(Node<T>* P); /在當(dāng)前結(jié)點(diǎn)后插入一個(gè)結(jié)點(diǎn)Node<T>* RemoveAfter(); /刪除當(dāng)前結(jié)點(diǎn)的后繼結(jié)點(diǎn)，返回該結(jié)點(diǎn)備用T & Getinfo(); /增加取數(shù)據(jù)域函數(shù)friend class List<T>/以List為友元類，List可直接訪問(wèn)Node的私有函數(shù)，與結(jié)構(gòu)一樣方便，但更安全;template <typename T> Node<T>:Node()link=NULL;template <typename T&g

29、t; Node<T>:Node(const T & data)info=data;link=NULL;template<typename T>void Node<T>:InsertAfter(Node<T>* p)p->link=link;link=p;template<typename T>Node<T>* Node<T>:RemoveAfter()Node<T>* tempP=link;if(link=NULL) tempP=NULL; /已在鏈尾,后面無(wú)結(jié)點(diǎn)else link=t

30、empP->link;return tempP;template<typename T> T & Node<T>:Getinfo()return info;/增加取數(shù)據(jù)域函數(shù)/再定義鏈表類，選擇常用操作：包括建立有序鏈表、搜索遍歷、插入、刪除、取數(shù)據(jù)等template<typename T>class ListNode<T> *head,*tail;/鏈表頭指針和尾指針public:List(); /構(gòu)造函數(shù)，生成頭結(jié)點(diǎn)(空鏈表)List(List<T> &); /拷貝構(gòu)造函數(shù)List(); /析構(gòu)函數(shù)List&

31、amp; operator=(List<T>&);void MakeEmpty(); /清空一個(gè)鏈表，只余表頭結(jié)點(diǎn)Node<T>* Find(T data); /搜索數(shù)據(jù)域與data相同的結(jié)點(diǎn)，返回該結(jié)點(diǎn)的地址int Length(); /計(jì)算單鏈表長(zhǎng)度void PrintList(); /打印鏈表的數(shù)據(jù)域 void InsertFront(Node<T>* p); /可用來(lái)向前生成鏈表，在表頭插入一個(gè)結(jié)點(diǎn)void InsertRear(Node<T>* p); /可用來(lái)向后生成鏈表，在表尾添加一個(gè)結(jié)點(diǎn)void InsertOrder(N

32、ode<T> *p); /按升序生成鏈表Node<T>*CreatNode(T data); /創(chuàng)建一個(gè)結(jié)點(diǎn)(孤立結(jié)點(diǎn))Node<T>*DeleteNode(Node<T>* p); /刪除指定結(jié)點(diǎn)Node<T>*RemoveAll(T &);/*刪除鏈表中所有數(shù)據(jù)域?yàn)橹付ㄖ档慕Y(jié)點(diǎn)*/Node<T>*GetNode(int);/*取出鏈表中第K個(gè)元素（從1開(kāi)始計(jì)數(shù)）*/;template<typename T>List<T>:List()head=tail=new Node<T>

33、();template<typename T>List<T>:List(List<T> & ls) /拷貝構(gòu)造函數(shù)Node<T>* TempP=ls.head->link,*P1;head=tail=new Node<T>();while(TempP!=NULL)P1=new Node<T>(TempP->info);P1->link=tail->link;/向后生成list1tail->link=P1;tail=P1;TempP=TempP->link;template<

34、typename T>List<T>:List()MakeEmpty();delete head;template<typename T>List<T>& List<T>:operator=(List<T>& ls)Node<T>* TempP=ls.head->link,*P1;head=tail=new Node<T>();while(TempP!=NULL)P1=new Node<T>(TempP->info);P1->link=tail->lin

35、k;/向后生成list1tail->link=P1;tail=P1;TempP=TempP->link;return *this;template<typename T>void List<T>:MakeEmpty()Node<T> *tempP;while(head->link!=NULL)tempP=head->link;head->link=tempP->link; /把頭結(jié)點(diǎn)后的第一個(gè)節(jié)點(diǎn)從鏈中脫離delete tempP; /刪除(釋放)脫離下來(lái)的結(jié)點(diǎn)tail=head; /表頭指針與表尾指針均指向表頭結(jié)點(diǎn)，表示

36、空鏈template<typename T> Node<T>* List<T>:Find(T data)Node<T> *tempP=head->link;while(tempP!=NULL&&tempP->info!=data) tempP=tempP->link;return tempP; /搜索成功返回該結(jié)點(diǎn)地址，不成功返回NULLtemplate<typename T>int List<T>:Length()Node<T>* tempP=head->link;in

37、t count=0;while(tempP!=NULL)tempP=tempP->link;count+;return count;template<typename T>void List<T>:PrintList()Node<T>* tempP=head->link;while(tempP!=NULL)cout<<tempP->info<<'t'tempP=tempP->link;cout<<endl;template<typename T>void List<

38、T>:InsertFront(Node<T> *p)p->link=head->link;head->link=p;if(tail=head) tail=p;template<typename T>void List<T>:InsertRear(Node<T> *p)p->link=tail->link;tail->link=p;tail=p;template<typename T>void List<T>:InsertOrder(Node<T> *p)Node<

39、T> *tempP=head->link,*tempQ=head; /tempQ指向tempP前面的一個(gè)節(jié)點(diǎn)while(tempP!=NULL)if(p->info<tempP->info)break; /找第一個(gè)比插入結(jié)點(diǎn)大的結(jié)點(diǎn)，由tempP指向tempQ=tempP;tempP=tempP->link;tempQ->InsertAfter(p);/插在tempP指向結(jié)點(diǎn)之前，tempQ之后if(tail=tempQ) tail=tempQ->link;template<typename T>Node<T>* List

40、<T>:CreatNode(T data)/建立新節(jié)點(diǎn)Node<T>*tempP=new Node<T>(data);return tempP;template<typename T>Node<T>* List<T>:DeleteNode(Node<T>* p)Node<T>* tempP=head;while(tempP->link!=NULL&&tempP->link!=p) tempP=tempP->link;if(tempP->link=tail) t

41、ail=tempP;return tempP->RemoveAfter(); /本函數(shù)所用方法可省一個(gè)工作指針，與InsertOrder比較template<typename T> Node<T>* List<T>:RemoveAll(T &p)/*利用已有的DeleteNode()*/bool b=false;Node<T>*TempP=head->link,*TempR;while(TempP!=NULL)/*也可以利用尾指針*/if(TempP->info=p) TempR=DeleteNode(TempP);Te

42、mpP=TempP->link;return TempR;template<typename T> Node<T>* List<T>:GetNode(int i)/取出鏈表中第K個(gè)元素(從1開(kāi)始)Node<T>*TempP=head->link;int j=1;if(i<0) return NULL;if(i=0) return head;while(TempP!=NULL&&j<i)TempP=TempP->link;j+;return TempP;/ep7_4.cpp#include "

43、ep7_4.h"int main()Node<int> * P1;List<int> list1;int a16,i;cout<<"請(qǐng)輸入16個(gè)整數(shù)"<<endl;for(i=0;i<16;i+)cin>>ai; /隨機(jī)輸入16個(gè)整數(shù)for(i=0;i<16;i+)P1=list1.CreatNode(ai);list1.InsertRear(P1); /向前生成list1cout<<"輸出list1："<<endl;list1.PrintList(

44、);List<int> list2(list1),list3;list3=list1;list1.MakeEmpty(); /清空原鏈表，看是否深拷貝cout<<"如無(wú)輸出list1已清空："<<endl;list1.PrintList();cout<<"輸出list2："<<endl;list2.PrintList();cout<<"輸出list3："<<endl;list3.PrintList();return 0;7.5 試為單鏈表類模板設(shè)計(jì)一個(gè)

45、將鏈表逆轉(zhuǎn)的成員函數(shù)。要求不刪除原結(jié)點(diǎn)，也不另建一個(gè)鏈表來(lái)取代，而是通過(guò)改變指針域的鏈接方向來(lái)逆轉(zhuǎn)鏈表。解：逆轉(zhuǎn)鏈表函數(shù)在ep7_5.h的最后。逆轉(zhuǎn)鏈表的成員函數(shù)對(duì)空鏈表和單結(jié)點(diǎn)鏈表不處理。對(duì)多結(jié)點(diǎn)鏈表，用尾指針指向第一個(gè)結(jié)點(diǎn)，找到該尾鏈表最后一個(gè)結(jié)點(diǎn)重新鏈到原頭結(jié)點(diǎn)后面；再找到該尾鏈表最后一個(gè)結(jié)點(diǎn)，并如此向后生成鏈表，就可以逆轉(zhuǎn)鏈表。也可以用尾鏈表第一個(gè)結(jié)點(diǎn)重新鏈到原頭結(jié)點(diǎn)后面，并如此向前生成鏈表，同樣可以逆轉(zhuǎn)鏈表。/ep7_5.h#include<iostream>using namespace std; /首先看結(jié)點(diǎn)組織，采用結(jié)點(diǎn)類，請(qǐng)參看習(xí)題7.3template<t

46、ypename T>class List;template<typename T>class Node;/再定義鏈表類，凡是習(xí)題7.34中已給出的成員函數(shù)不再重復(fù) template<typename T>class ListNode<T> *head,*tail;/鏈表頭指針和尾指針public:List(); /構(gòu)造函數(shù)，生成頭結(jié)點(diǎn)(空鏈表)void Reverse();/翻轉(zhuǎn)鏈表;template<typename T> void List<T>:Reverse() /鏈表翻轉(zhuǎn)函數(shù)Node<T>*p1,*p2,*

47、p3;if(head=tail|head->link=tail) return; /空鏈表和單結(jié)點(diǎn)鏈表不必處理tail=head->link; /尾指針指向第一個(gè)元素p3=head;dop1=tail; /以tail開(kāi)始的鏈，最后一個(gè)元素取下來(lái)，鏈到新鏈的尾部dop2=p1;p1=p1->link;while(p1->link!=NULL); /找到以tail開(kāi)始的鏈的鏈尾p3->link=p1; /取下鏈尾，鏈到新鏈上p3=p1;p2->link=NULL;while(tail!=p2); /以tail開(kāi)始的鏈只剩一個(gè)元素則停止p3->link=ta

48、il;tail->link=NULL;/ep7_5.cpp#include "ep7_5.h"int main()Node<int> * P1;List<int> list1;int a16,i;cout<<"請(qǐng)輸入16個(gè)整數(shù)"<<endl;for(i=0;i<16;i+) cin>>ai; /隨機(jī)輸入16個(gè)整數(shù),有重復(fù)的for(i=0;i<16;i+)P1=list1.CreatNode(ai);list1.InsertRear(P1); /向前生成list1cout<

49、<"輸出list1："<<endl;list1.PrintList();list1.Reverse();cout<<"輸出逆轉(zhuǎn)后的list1："<<endl;list1.PrintList();return 0;7.6 為單鏈表重載“+”運(yùn)算符，實(shí)現(xiàn)兩個(gè)單鏈表對(duì)象的連接，但要去除數(shù)據(jù)域相同的結(jié)點(diǎn)。可用友元函數(shù)。解：為了實(shí)現(xiàn)ls3=ls1+ls2,需重載=和+兩個(gè)運(yùn)算符。=運(yùn)算符先清空左邊的鏈表，再模仿拷貝構(gòu)造函數(shù)的編法編程。+運(yùn)算符先建立一個(gè)局部鏈表，拷入被加鏈表，再以加鏈表的數(shù)據(jù)域生成局部鏈表后面的結(jié)點(diǎn)，最后去

50、除數(shù)據(jù)域相同的結(jié)點(diǎn)。/ep7_6.h#include<iostream>using namespace std; template<typename T>class List;template<typename T>class Nodepublic:Node<T>*Getlink()return link;/取指針域;template<typename T>class ListNode<T> *head,*tail;/鏈表頭指針和尾指針public:List(); /構(gòu)造函數(shù)，生成頭結(jié)點(diǎn)(空鏈表)List<T>

51、 & operator=(List<T> &); /重載=運(yùn)算符friend List<T> operator+(List<T> & ,List<T> & ); /重載+運(yùn)算符;template<typename T>List<T> & List<T>:operator=(List<T> & ls)/重載=運(yùn)算符Node<T>* TempP=ls.head->link,*P1;MakeEmpty(); /清空后tail= head w

52、hile(TempP!=NULL)P1=new Node<T>(TempP->info);P1->link=tail->link; /向后生成list1tail->link=P1;tail=P1;TempP=TempP->link;return *this;template<typename T>List<T> operator+(List<T> & ls1,List<T> & ls2)/重載+運(yùn)算符List<T> ls(ls1); /新鏈表，生命期僅在本函數(shù)域中Node<

53、;T>* P1=ls2.head->Getlink(),*P2,*P3;/雖然本函數(shù)是List的友元，而List是Node的友類，但還是不能訪問(wèn)Node的私有成員while(P1!=NULL)P2=ls.CreatNode(P1->Getinfo();ls.InsertRear(P2); /向后生成list1P1=P1->Getlink();P1=ls.head->Getlink();/刪去重復(fù)的結(jié)點(diǎn)。while(P1!=NULL)P2=P1->Getlink();while(P2!=NULL)/與后面結(jié)點(diǎn)逐個(gè)比較if(P1->Getinfo()=P2

54、->Getinfo()/有重復(fù)的就刪去；P3=P2->Getlink();/刪去后P2空懸ls.DeleteNode(P2);P2=P3;P2=P2->Getlink();/到后面一個(gè)結(jié)點(diǎn)P1=P1->Getlink();/再用第二個(gè)./先用第一個(gè)結(jié)點(diǎn)，與后面結(jié)點(diǎn)逐個(gè)比較，有重復(fù)的就刪去；再用第二個(gè).return ls;/為保證返回時(shí)用拷貝構(gòu)造函數(shù)復(fù)制一個(gè)鏈表返回，返回類型不能是引用，/ep7_6.cpp#include "ep7_6.h"int main()Node<int> * P1;List<int> list1,lis

55、t2,list;int a16=1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,i;for(i=0;i<16;i+)P1=list1.CreatNode(ai);list1.InsertRear(P1);/向后生成list1cout<<"輸出list1："<<endl;list1.PrintList();for(i=0;i<16;i+)P1=list2.CreatNode(ai+10);list2.InsertRear(P1);/向后生成list1cout<<"輸出list2："

56、;<<endl;list2.PrintList();list=list1+list2;cout<<"輸出合并成的list："<<endl;list.PrintList();return 0;7.7 將兩個(gè)有序的雙向鏈表合并為一個(gè)有序的雙向鏈表，刪去相同結(jié)點(diǎn)。解：算法類似6.6的歸并。函數(shù)為：void Merge(DblList<T> & ,DblList<T> &); #include<iostream>using namespace std;template<typename T

57、> class DblList;template<typename T> class DblNode /結(jié)點(diǎn)類T info; /數(shù)據(jù)域DblNode<T> *llink,*rlink; /前驅(qū)（左鏈）、后繼（右鏈）指針public:DblNode(T data);DblNode();T Getinfo()return info;friend class DblList<T>template<typename T> DblNode<T>:DblNode()llink=rlink=NULL;template<typename T> DblNode<T>:DblNode(T data)info=data;llink=NULL;rlink=NULL;template<typename T>class DblL