1、學校代碼： 10128學 號： 面向對象的程序設計實驗報告（題 目：群體類和群體數據學生姓名： 學 院：理學院系 別：數學系專 業(yè)：信息與計算科學班 級：任課教師： 二一一年 十 一月1 / 351、 實驗目的1、 了解節(jié)點類的聲明和實現(xiàn)，學習其使用方法2、 了解鏈表類的聲明和實現(xiàn)，學習其使用方法3、 了解棧類的聲明和實現(xiàn)，學習其使用方法4、 了解隊列類的聲明和實現(xiàn)，學習其使用方法5、 掌握對數組元素排序的方法6、 掌握對數組元素查找的方法2、 實驗內容1.、編寫程序Node.h實現(xiàn)例9-5的節(jié)點類，并編寫測試程序lab9_1.cpp，實現(xiàn)鏈表的基本操作2、編寫程序link.h實現(xiàn)例9-6的鏈

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

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

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

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

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

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

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

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

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

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

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

13、Node *currPtr, *prevPtr, *newNode; / prevPtr = NULL 標志著應插入在表頭 prevPtr = NULL; currPtr = head; / 通過循環(huán)遍歷鏈表，尋找插入點 while (currPtr != NULL) / 如果item 當前結點數據，則插入點應在當前結點之前if (item data) break; / currPtr前行，prevPtr跟隨其后 prevPtr = currPtr; currPtr = currPtr-NextNode(); / 完成插入 if (prevPtr = NULL) /如果插入點在表頭 Inser

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

15、rPtr = nextPtr; /使指針currPtr指向下一個結點 head = NULL; /將頭結點置為NULL，標志著鏈表為空#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個整數依次向表頭插入 for (i=0;i item; InsertFront(head, item); /

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

17、 PrintList(head,noNewline); cout endl;/清空鏈表 ClearList(head);實驗結果如下：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 此時，鏈表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: /數據成員： / 表頭和表尾指針 Node *front, *rear; / 記錄表當前遍歷位置的指針，由插入和刪除操作更新 Node *prevPtr, *currPtr; / 表中的元素個數 int size; / 當前元素在表中的位置序號。由函數Reset使用 int position; /函數成員： / 生成新節(jié)點，數據域為item，指針域為ptrNext Node *GetNode(const T& it

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

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

22、osition(void) const; /返回數據成員position / 插入節(jié)點的函數：插入一個數據域為item的節(jié)點 void InsertFront(const T& item); /在表頭插入 void InsertRear(const T& item); /在表尾添加 void InsertAt(const T& item); /在當前節(jié)點之前插入 void InsertAfter(const T& item); /在當前節(jié)點之后插入 / 刪除節(jié)點，釋放節(jié)點空間，更新prevPtr、currPtr和size T DeleteFront(void); /刪除頭節(jié)點 void Del

23、eteAt(void); /刪除當前節(jié)點 / 返回對當前節(jié)點成員data的引用（使數據域可以被使用或修改） T& Data(void); / 清空鏈表：釋放所有節(jié)點的內存空間。被析構函數、operator= 調用 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復制到當前鏈表template void LinkedList:CopyList(const LinkedList& L) /P用來遍歷L Node *p = L.front; int pos; /將L中的每一個元素插入到當前鏈表最后 while (p != NULL) InsertRear(p-data); p = p-NextNode(); /如果鏈表空,返回 if (position = -1) return; /在新鏈表中重新設置prevPtr和currPtr prevPtr = NUL

25、L; currPtr = front; for (pos = 0; pos != position; pos+) prevPtr = currPtr; currPtr = currPtr-NextNode(); /建立一個新鏈表,即:將有關指針設置為空,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) /取得下一結點的地址并刪除當前結點 nextPosition = currPosition-NextNode(); FreeNode(currPosition)

27、; currPosition = nextPosition; / 移動到下一結點 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向前移動一個結點template void LinkedList:Next(void) if (currPtr != NULL) prevPtr = currPtr; currPtr = currPtr-NextNode(); position+; / 如果已經遍歷完鏈表則返回Truetemplate int L

29、inkedList:EndOfList(void) const return currPtr = NULL;/ 返回當前結點的位置template int LinkedList:CurrentPosition(void) const return position;/將鏈表當前位置設置為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; /移動指針直到 position = pos for(position=startPos; position != pos; position+) / 向前移動遍歷指針 prevPtr = currPtr; currPtr = currPtr-NextNode(); /返回一個當前結點數值的引用template T& LinkedList:Data(void) / 如果鏈表為空或已經完成遍歷則出錯 if (size = 0 | currPtr = NULL) cerr Data: inval

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

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

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

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

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

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

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

38、構造函數template Queue:Queue(void)/ 鏈表類成員函數ListSize返回鏈表長度template int Queue:QLength(void) const return queueList.ListSize();/ 鏈表類成員函數ListEmpty測試隊列空否template int Queue:QEmpty(void) const return queueList.ListEmpty();/ 鏈表類成員函數ClearList 清空隊列template void Queue:QClear(void) queueList.ClearList();/ 鏈表類成員函數In

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

40、nt(void)/ 測試隊列空否,若空則中止 if (queueList.ListEmpty() cerr Calling QFront for an empty queue! endl; exit(1); / 重新設置隊頭并返回其值 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: /數據成員： / 表頭和表尾指針 Node *front, *rear; / 記錄表當前遍歷位置的指針，由插入和刪除操作更新 Node *prevPtr, *currPtr; / 表中的元素個數 int size; / 當前元素在表中的位置序號。由函數Reset使用 int position; /函數成員： / 生成新節(jié)點，數據域為item，指針域為ptrNext N