1、學(xué)校代碼： 10128學(xué) 號(hào)： 面向?qū)ο蟮某绦蛟O(shè)計(jì)實(shí)驗(yàn)報(bào)告（題 目：群體類(lèi)和群體數(shù)據(jù)學(xué)生姓名： 學(xué) 院：理學(xué)院系 別：數(shù)學(xué)系專(zhuān) 業(yè)：信息與計(jì)算科學(xué)班 級(jí)：任課教師： 二一一年 十 一月1 / 351、 實(shí)驗(yàn)?zāi)康?、 了解節(jié)點(diǎn)類(lèi)的聲明和實(shí)現(xiàn)，學(xué)習(xí)其使用方法2、 了解鏈表類(lèi)的聲明和實(shí)現(xiàn)，學(xué)習(xí)其使用方法3、 了解棧類(lèi)的聲明和實(shí)現(xiàn)，學(xué)習(xí)其使用方法4、 了解隊(duì)列類(lèi)的聲明和實(shí)現(xiàn)，學(xué)習(xí)其使用方法5、 掌握對(duì)數(shù)組元素排序的方法6、 掌握對(duì)數(shù)組元素查找的方法2、 實(shí)驗(yàn)內(nèi)容1.、編寫(xiě)程序Node.h實(shí)現(xiàn)例9-5的節(jié)點(diǎn)類(lèi)，并編寫(xiě)測(cè)試程序lab9_1.cpp，實(shí)現(xiàn)鏈表的基本操作2、編寫(xiě)程序link.h實(shí)現(xiàn)例9-6的鏈

2、表類(lèi)，在測(cè)試程序lab_2.cpp中聲明兩個(gè)整型鏈表A和B，分別插入5元素，然后把B中的元素加入A的尾部3、編寫(xiě)程序queue.h，用鏈表實(shí)現(xiàn)隊(duì)列（或棧），在測(cè)試程序lab9_3.cpp中聲明一個(gè)整型隊(duì)列（或棧）對(duì)象，插入5個(gè)整數(shù)，壓入隊(duì)列（或棧），再依次取出并顯示出來(lái)。4、將直接插入排序、直接選擇排序、冒泡排序、順序查找函數(shù)封裝到第九章的數(shù)組類(lèi)中，作為成員函數(shù)，實(shí)現(xiàn)并測(cè)試這個(gè)類(lèi)。3、 實(shí)驗(yàn)程序及結(jié)果1. 程序一/9_5.h#ifndef NODE_CLASS#define NODE_CLASS/類(lèi)定義部分template class Node private: Node *next; /指向

3、后繼節(jié)點(diǎn)的指針 public: T data; /數(shù)據(jù)域 / 構(gòu)造函數(shù) Node (const T& item, Node* ptrnext = NULL); / 在本節(jié)點(diǎn)之后插入一個(gè)同類(lèi)節(jié)點(diǎn)p void InsertAfter(Node *p); / 刪除本節(jié)點(diǎn)的后繼節(jié)點(diǎn)，并返回其地址 Node *DeleteAfter(void); / 獲取后繼節(jié)點(diǎn)的地址 Node *NextNode(void) const;/ 類(lèi)的實(shí)現(xiàn)部分/ 構(gòu)造函數(shù)，初始化數(shù)據(jù)和指針成員template Node:Node(const T& item, Node* ptrnext) : data(item), nex

4、t(ptrnext)/ 返回私有的指針成員template Node *Node:NextNode(void) const return next; / 在當(dāng)前節(jié)點(diǎn)之后插入一個(gè)節(jié)點(diǎn)p template void Node:InsertAfter(Node *p) p-next = next; /p節(jié)點(diǎn)指針域指向當(dāng)前節(jié)點(diǎn)的后繼節(jié)點(diǎn) next = p; /當(dāng)前節(jié)點(diǎn)的指針域指向p / 刪除當(dāng)前節(jié)點(diǎn)的后繼節(jié)點(diǎn)，并返回其地址template Node *Node:DeleteAfter(void)Node *tempPtr = next; /將欲刪除的節(jié)點(diǎn)地址存儲(chǔ)到tempPtr中 if (next =

5、 NULL) /如果當(dāng)前節(jié)點(diǎn)沒(méi)有后繼節(jié)點(diǎn)，則返回NULL return NULL; next = tempPtr-next; /使當(dāng)前節(jié)點(diǎn)的指針域指向tempPtr的后繼節(jié)點(diǎn) return tempPtr; /返回被刪除的節(jié)點(diǎn)的地址#endif / NODE_CLASS/Node.h#ifndef NODE_LIBRARY#define NODE_LIBRARY#include #include #include 9_5.husing namespace std;/ 生成結(jié)點(diǎn)：創(chuàng)建一個(gè)結(jié)點(diǎn)，數(shù)據(jù)成員值為item，指向后繼結(jié)點(diǎn)的指針值為nextPtrtemplate Node *GetNode(

6、const T& item, Node *nextPtr = NULL) Node *newNode; / 為新結(jié)點(diǎn)分配內(nèi)存空間，然后將item和NextPtr傳遞給構(gòu)造函數(shù) newNode = new Node(item, nextPtr); if (newNode = NULL) /如果分配內(nèi)存失敗，程序中止 cerr Memory allocation failure! endl; exit(1); return newNode;enum AppendNewline noNewline,addNewline;/ 輸出鏈表template void PrintList(Node *head

7、, AppendNewline addnl = noNewline) / currPtr初始指向表頭結(jié)點(diǎn)，用于遍歷鏈表 Node *currPtr = head; / 輸出結(jié)點(diǎn)數(shù)據(jù)，直到鏈表結(jié)束 while(currPtr != NULL) / 如果換行標(biāo)志addl = addNewline，則輸出換行符 if(addnl = addNewline) cout data endl; else cout data NextNode(); /查找結(jié)點(diǎn)/在指針head所指向的鏈表中查找數(shù)據(jù)域等于item的結(jié)點(diǎn)/找到則返回TRUE及其前趨結(jié)點(diǎn)的地址，否則返回FALSEtemplate int Find

8、(Node *head, T& item, Node* &prevPtr)Node *currPtr = head; /從第一個(gè)結(jié)點(diǎn)開(kāi)始遍歷prevPtr = NULL;/ 通過(guò)循環(huán)遍歷鏈表，直到表尾while(currPtr != NULL) /將item與結(jié)點(diǎn)的數(shù)據(jù)域比較，如果相等，則返回，否則繼續(xù)處理下一個(gè)結(jié)點(diǎn) if (currPtr-data = item) return 1; prevPtr = currPtr; /記錄下當(dāng)前結(jié)點(diǎn)的地址 currPtr = currPtr-NextNode();return 0; /找不到時(shí)/在表頭插入結(jié)點(diǎn)template void InsertFr

9、ont(Node* & head, T item) / 建立新結(jié)點(diǎn)，使其指針域指向原鏈表頭結(jié)點(diǎn)head，然后更新head head = GetNode(item,head);/在表尾添加結(jié)點(diǎn)template void InsertRear(Node* & head, const T& item) Node *newNode, *currPtr = head;/ 如果鏈表為空，則插入在表頭 if (currPtr = NULL) InsertFront(head,item); else / 尋找指針域?yàn)镹ULL的結(jié)點(diǎn) while(currPtr-NextNode() != NULL) currP

10、tr = currPtr-NextNode(); / 建立新結(jié)點(diǎn)并插入在表尾(在currPtr之后) newNode = GetNode(item); currPtr-InsertAfter(newNode); / 刪除鏈表的第一個(gè)結(jié)點(diǎn)template void DeleteFront(Node* & head) Node *p = head; /取得將被刪除的結(jié)點(diǎn)的地址 if (head != NULL) / 確認(rèn)鏈表不空 head = head-NextNode(); / 將表頭指針head移向第二個(gè)結(jié)點(diǎn) delete p; /刪除原第一個(gè)結(jié)點(diǎn) / 刪除鏈表中第一個(gè)數(shù)據(jù)域等于key的結(jié)點(diǎn)t

11、emplate void Delete (Node* & head, T key) / currPtr用于遍歷鏈表，prevPtr跟隨其后 Node *currPtr = head, *prevPtr = NULL; / 如果鏈表為空，則返回 if (currPtr = NULL) return; /通過(guò)循環(huán)遍歷鏈表，直到找到數(shù)據(jù)域?yàn)閗ey的結(jié)點(diǎn)，或達(dá)到表尾 while (currPtr != NULL & currPtr-data != key) / currPtr前行，prevPtr跟隨其后 prevPtr = currPtr; currPtr = currPtr-NextNode();

12、/若 currPtr != NULL，則currPtr指向的結(jié)點(diǎn)數(shù)據(jù)域?yàn)閗ey if (currPtr != NULL) if(prevPtr = NULL) /找到的是鏈表第一個(gè)結(jié)點(diǎn) head = head-NextNode(); else / 如果找到的是第二個(gè)以后的結(jié)點(diǎn)，調(diào)用前趨結(jié)點(diǎn)的成員函數(shù)刪除之 prevPtr-DeleteAfter(); delete currPtr; /釋放被刪除的結(jié)點(diǎn)所占的內(nèi)存空間 / 在有序鏈表中插入一個(gè)結(jié)點(diǎn)template void InsertOrder(Node* & head, T item) / currPtr用于遍歷鏈表，prevPtr跟隨其后

13、Node *currPtr, *prevPtr, *newNode; / prevPtr = NULL 標(biāo)志著應(yīng)插入在表頭 prevPtr = NULL; currPtr = head; / 通過(guò)循環(huán)遍歷鏈表，尋找插入點(diǎn) while (currPtr != NULL) / 如果item 當(dāng)前結(jié)點(diǎn)數(shù)據(jù)，則插入點(diǎn)應(yīng)在當(dāng)前結(jié)點(diǎn)之前if (item data) break; / currPtr前行，prevPtr跟隨其后 prevPtr = currPtr; currPtr = currPtr-NextNode(); / 完成插入 if (prevPtr = NULL) /如果插入點(diǎn)在表頭 Inser

14、tFront(head,item); else / 在prevPtr指向的結(jié)點(diǎn)之后插入新結(jié)點(diǎn) newNode = GetNode(item); prevPtr-InsertAfter(newNode); /清空鏈表-刪除鏈表中的所有結(jié)點(diǎn)template void ClearList(Node * &head) Node *currPtr, *nextPtr; / 邊遍歷邊刪除結(jié)點(diǎn) currPtr = head; while(currPtr != NULL) / 記錄下一個(gè)結(jié)點(diǎn)的地址，刪除當(dāng)前結(jié)點(diǎn) nextPtr = currPtr-NextNode(); delete currPtr; cur

15、rPtr = nextPtr; /使指針currPtr指向下一個(gè)結(jié)點(diǎn) head = NULL; /將頭結(jié)點(diǎn)置為NULL，標(biāo)志著鏈表為空#endif / NODE_LIBRARY/lab9_1.cpp#include #include 9_5.h#include node.husing namespace std;int main() / 將表頭指針置為 NULL Node *head = NULL, *prevPtr, *delPtr; int i, key, item; / 輸入10個(gè)整數(shù)依次向表頭插入 for (i=0;i item; InsertFront(head, item); /

16、輸出鏈表 cout List: ; PrintList(head,noNewline); cout endl; / 輸入需要?jiǎng)h除的整數(shù) cout key; / 查找并刪除結(jié)點(diǎn) prevPtr = head; while (Find(head,key,prevPtr) != NULL) if(prevPtr = NULL) /找到的是鏈表第一個(gè)結(jié)點(diǎn) head = head-NextNode(); else / 如果找到的是第二個(gè)以后的結(jié)點(diǎn)，調(diào)用前趨結(jié)點(diǎn)的成員函數(shù)刪除之 delPtr=prevPtr-DeleteAfter(); delete delPtr; / 輸出鏈表 cout List: ;

17、 PrintList(head,noNewline); cout endl;/清空鏈表 ClearList(head);實(shí)驗(yàn)結(jié)果如下：2程序二/lab9_2.cpp#include link.hint main()LinkedList A, B;for(int i=0;i5;i+)A.InsertRear(2*i+1);B.InsertRear(2*i+2);A.Reset();cout 鏈表A的元素為： ;while(!A.EndOfList()cout A.Data() ;A.Next();cout endl; B.Reset();cout 鏈表B的元素為： ;while(!B.EndOf

18、List()cout B.Data() ;B.Next();cout endl;cout 把B中的元素插入A中. endl;B.Reset();while(!B.EndOfList()A.InsertRear(B.Data();B.Next();A.Reset();cout 此時(shí)，鏈表A的元素為： ;while(!A.EndOfList()cout A.Data() ;A.Next();cout endl;/link.h#ifndef LINKEDLIST_CLASS#define LINKEDLIST_CLASS#include #include using namespace std;#i

19、fndef NULLconst int NULL = 0;#endif / NULL#include 9-3.htemplate class LinkedList private: /數(shù)據(jù)成員： / 表頭和表尾指針 Node *front, *rear; / 記錄表當(dāng)前遍歷位置的指針，由插入和刪除操作更新 Node *prevPtr, *currPtr; / 表中的元素個(gè)數(shù) int size; / 當(dāng)前元素在表中的位置序號(hào)。由函數(shù)Reset使用 int position; /函數(shù)成員： / 生成新節(jié)點(diǎn)，數(shù)據(jù)域?yàn)閕tem，指針域?yàn)閜trNext Node *GetNode(const T& it

20、em,Node *ptrNext=NULL); /釋放節(jié)點(diǎn) void FreeNode(Node *p); / 將鏈表L 拷貝到當(dāng)前表（假設(shè)當(dāng)前表為空）。 / 被拷貝構(gòu)造函數(shù)、operator=調(diào)用 void CopyList(const LinkedList& L); public: / 構(gòu)造函數(shù) LinkedList(void); LinkedList(const LinkedList& L); /拷貝構(gòu)造函數(shù) / 析構(gòu)函數(shù) LinkedList(void); / 重載賦值運(yùn)算符 LinkedList& operator= (const LinkedList& L); / 檢查表的狀態(tài) i

21、nt ListSize(void) const; /返回鏈表中元素個(gè)數(shù)（size） int ListEmpty(void) const; /size等于0時(shí)返回TRUE,否則返回FALSE / 遍歷表的函數(shù) void Reset(int pos = 0); /將指針currPtr移動(dòng)到序號(hào)為pos的節(jié)點(diǎn)，prevPtr相應(yīng)移動(dòng) / position記錄當(dāng)前節(jié)點(diǎn)的序號(hào) void Next(void); /使prevPtr和currPtr移動(dòng)到下一個(gè)節(jié)點(diǎn) int EndOfList(void) const; / currPtr等于NULL時(shí)返回TRUE,否則返回FALSE int CurrentP

22、osition(void) const; /返回?cái)?shù)據(jù)成員position / 插入節(jié)點(diǎn)的函數(shù)：插入一個(gè)數(shù)據(jù)域?yàn)閕tem的節(jié)點(diǎn) void InsertFront(const T& item); /在表頭插入 void InsertRear(const T& item); /在表尾添加 void InsertAt(const T& item); /在當(dāng)前節(jié)點(diǎn)之前插入 void InsertAfter(const T& item); /在當(dāng)前節(jié)點(diǎn)之后插入 / 刪除節(jié)點(diǎn)，釋放節(jié)點(diǎn)空間，更新prevPtr、currPtr和size T DeleteFront(void); /刪除頭節(jié)點(diǎn) void Del

23、eteAt(void); /刪除當(dāng)前節(jié)點(diǎn) / 返回對(duì)當(dāng)前節(jié)點(diǎn)成員data的引用（使數(shù)據(jù)域可以被使用或修改） T& Data(void); / 清空鏈表：釋放所有節(jié)點(diǎn)的內(nèi)存空間。被析構(gòu)函數(shù)、operator= 調(diào)用 void ClearList(void);template Node *LinkedList:GetNode(const T& item, Node* ptrNext) Node *p; p = new Node(item,ptrNext); if (p = NULL) cout Memory allocation failure!n; exit(1); return p;templ

24、ate void LinkedList:FreeNode(Node *p) delete p;/將L復(fù)制到當(dāng)前鏈表template void LinkedList:CopyList(const LinkedList& L) /P用來(lái)遍歷L Node *p = L.front; int pos; /將L中的每一個(gè)元素插入到當(dāng)前鏈表最后 while (p != NULL) InsertRear(p-data); p = p-NextNode(); /如果鏈表空,返回 if (position = -1) return; /在新鏈表中重新設(shè)置prevPtr和currPtr prevPtr = NUL

25、L; currPtr = front; for (pos = 0; pos != position; pos+) prevPtr = currPtr; currPtr = currPtr-NextNode(); /建立一個(gè)新鏈表,即:將有關(guān)指針設(shè)置為空,size為0,position為-1template LinkedList:LinkedList(void): front(NULL), rear(NULL), prevPtr(NULL),currPtr(NULL), size(0), position(-1)template LinkedList:LinkedList(const Linke

26、dList& L) front = rear = NULL; prevPtr = currPtr = NULL; size = 0; position = -1; CopyList(L);template void LinkedList:ClearList(void) Node *currPosition, *nextPosition; currPosition = front; while(currPosition != NULL) /取得下一結(jié)點(diǎn)的地址并刪除當(dāng)前結(jié)點(diǎn) nextPosition = currPosition-NextNode(); FreeNode(currPosition)

27、; currPosition = nextPosition; / 移動(dòng)到下一結(jié)點(diǎn) front = rear = NULL; prevPtr = currPtr = NULL; size = 0; position = -1;template LinkedList:LinkedList(void) ClearList();template LinkedList& LinkedList:operator= (const LinkedList& L) if (this = &L) / 不能將鏈表賦值給它自身 return *this; ClearList(); CopyList(L); return

28、 *this;template int LinkedList:ListSize(void) const return size;template int LinkedList:ListEmpty(void) const return size = 0;/將prevPtr和currPtr向前移動(dòng)一個(gè)結(jié)點(diǎn)template void LinkedList:Next(void) if (currPtr != NULL) prevPtr = currPtr; currPtr = currPtr-NextNode(); position+; / 如果已經(jīng)遍歷完鏈表則返回Truetemplate int L

29、inkedList:EndOfList(void) const return currPtr = NULL;/ 返回當(dāng)前結(jié)點(diǎn)的位置template int LinkedList:CurrentPosition(void) const return position;/將鏈表當(dāng)前位置設(shè)置為postemplate void LinkedList:Reset(int pos) int startPos; / 如果鏈表為空，返回 if (front = NULL) return; / 如果位置不合法，中止程序 if (pos size-1) cerr Reset: Invalid list posit

30、ion: pos NextNode(); prevPtr = front; startPos = 1; /移動(dòng)指針直到 position = pos for(position=startPos; position != pos; position+) / 向前移動(dòng)遍歷指針 prevPtr = currPtr; currPtr = currPtr-NextNode(); /返回一個(gè)當(dāng)前結(jié)點(diǎn)數(shù)值的引用template T& LinkedList:Data(void) / 如果鏈表為空或已經(jīng)完成遍歷則出錯(cuò) if (size = 0 | currPtr = NULL) cerr Data: inval

31、id reference! data;/ 將item插入在表頭template void LinkedList:InsertFront(const T& item) / 如果鏈表不空則調(diào)用Reset if (front != NULL) Reset(); InsertAt(item); / 在表頭插入/ 在表尾插入template void LinkedList:InsertRear(const T& item) Node *newNode; prevPtr = rear; newNode = GetNode(item);/ 創(chuàng)建新結(jié)點(diǎn) if (rear = NULL)/ 如果表空則插入在表頭

32、 front = rear = newNode; else rear-InsertAfter(newNode); rear = newNode; currPtr = rear; position = size; size+;/ 將item插入在鏈表當(dāng)前位置template void LinkedList:InsertAt(const T& item) Node *newNode; / 兩種情況: 插入在鏈表頭或鏈表之中 if (prevPtr = NULL) / 插入在鏈表頭，包括將結(jié)點(diǎn)插入到空表中 newNode = GetNode(item,front); front = newNode;

33、 else / 插入到鏈表之中. 將結(jié)點(diǎn)置于prevPtr之后 newNode = GetNode(item); prevPtr-InsertAfter(newNode); / 如果prevPtr = rear, 說(shuō)明正在向空表中插入， / 或者是插入到非空表的表尾；更新rear 和 position if (prevPtr = rear) rear = newNode; position = size; /更新currPtr并且使size增值 currPtr = newNode; size+; / 將item 插入到鏈表當(dāng)前位置之后template void LinkedList:Inser

34、tAfter(const T& item) Node *p; p = GetNode(item); if (front = NULL) / 向空表中插入 front = currPtr = rear = p; position = 0; else / 插入到最后一個(gè)結(jié)點(diǎn)之后 if (currPtr = NULL) currPtr = prevPtr; currPtr-InsertAfter(p); if (currPtr = rear) rear = p; position = size; else position+; prevPtr = currPtr; currPtr = p; size

35、+; / 使鏈表長(zhǎng)度增值/ 刪除表頭結(jié)點(diǎn)template T LinkedList:DeleteFront(void) T item; Reset(); if (front = NULL) cerr Invalid deletion! data; DeleteAt(); return item;/ 刪除鏈表當(dāng)前位置的結(jié)點(diǎn) template void LinkedList:DeleteAt(void) Node *p; / 如果表空或達(dá)到表尾則出錯(cuò) if (currPtr = NULL) cerr Invalid deletion! NextNode(); else / 分離prevPtr之后的

36、一個(gè)內(nèi)部結(jié)點(diǎn). 保存其地址 p = prevPtr-DeleteAfter(); / 如果表尾結(jié)點(diǎn)被刪除, 則新的表尾是prevPtr 并且position自減； / 否則position不變 if (p = rear) rear = prevPtr; position-; / 使currPtr越過(guò)被刪除的結(jié)點(diǎn) currPtr = p-NextNode(); / 釋放結(jié)點(diǎn)，并使鏈表長(zhǎng)度自減 FreeNode(p); size-;#endif / LINKEDLIST_CLASS實(shí)驗(yàn)結(jié)果如下：程序3：/queue.h#ifndef QUEUE_CLASS#define QUEUE_CLASS#i

37、nclude #include using namespace std;#include link.htemplate class Queue private: / 用于存放隊(duì)列的鏈表對(duì)象 LinkedList queueList; public: / 構(gòu)造函數(shù) Queue(void); / 隊(duì)列存取方法 void QInsert(const T& elt); T QDelete(void); / 隊(duì)列訪(fǎng)問(wèn) T QFront(void); / 隊(duì)列監(jiān)測(cè)方法 int QLength(void) const; int QEmpty(void) const; void QClear(void);/

38、構(gòu)造函數(shù)template Queue:Queue(void)/ 鏈表類(lèi)成員函數(shù)ListSize返回鏈表長(zhǎng)度template int Queue:QLength(void) const return queueList.ListSize();/ 鏈表類(lèi)成員函數(shù)ListEmpty測(cè)試隊(duì)列空否template int Queue:QEmpty(void) const return queueList.ListEmpty();/ 鏈表類(lèi)成員函數(shù)ClearList 清空隊(duì)列template void Queue:QClear(void) queueList.ClearList();/ 鏈表類(lèi)成員函數(shù)In

39、sertRear在隊(duì)尾插入一項(xiàng)template void Queue:QInsert(const T& elt) queueList.InsertRear(elt);/ 鏈表類(lèi)成員函數(shù)DeleteFront從隊(duì)首刪除一項(xiàng)template T Queue:QDelete(void)/ 測(cè)試隊(duì)列空否,若空則中止 if (queueList.ListEmpty() cerr Calling QDelete for an empty queue! endl; exit(1); return queueList.DeleteFront();/ 返回隊(duì)首元素的數(shù)值template T Queue:QFro

40、nt(void)/ 測(cè)試隊(duì)列空否,若空則中止 if (queueList.ListEmpty() cerr Calling QFront for an empty queue! endl; exit(1); / 重新設(shè)置隊(duì)頭并返回其值 queueList.Reset(); return queueList.Data();#endif / QUEUE_CLASS/link.h#ifndef LINKEDLIST_CLASS#define LINKEDLIST_CLASS#include #include using namespace std;#ifndef NULLconst int NULL = 0;#endif / NULL#include 9-3.htemplate class LinkedList private: /數(shù)據(jù)成員： / 表頭和表尾指針 Node *front, *rear; / 記錄表當(dāng)前遍歷位置的指針，由插入和刪除操作更新 Node *prevPtr, *currPtr; / 表中的元素個(gè)數(shù) int size; / 當(dāng)前元素在表中的位置序號(hào)。由函數(shù)Reset使用 int position; /函數(shù)成員： / 生成新節(jié)點(diǎn)，數(shù)據(jù)域?yàn)閕tem，指針域?yàn)閜trNext N