實驗4群體類和群體數(shù)據(jù)

1、-. z.學校代碼： 學 號： 面向?qū)ο蟪绦蛟O(shè)計實驗報告題 目：群體類和群體數(shù)據(jù)學生*：學 院：系 別：專 業(yè)：班 級：任課教師：二一五年十二月群體類和群體數(shù)據(jù)實驗?zāi)康牧私夤?jié)點類的聲明和實現(xiàn)，學習其使用方法了解鏈表類的聲明和實現(xiàn)，學習其使用方法了解棧類的聲明和實現(xiàn)，學習其使用方法了解隊列類的聲明和實現(xiàn)，學習其使用方法掌握對數(shù)組元素排序的方法掌握對數(shù)組元素查找的方法二、實驗任務(wù)1.編寫程序Node.h實現(xiàn)例9-5的節(jié)點類，并編寫測試程序lab9_1.cpp，實現(xiàn)鏈表的根本操作2.編寫程序link.h實現(xiàn)例9-6的鏈表類，在測試程序lab_2.cpp中聲明兩個整型鏈表A和B，分別插入5元素，然后把

2、B中的元素參加A的尾部3.編寫程序queue.h，用鏈表實現(xiàn)隊列或棧，在測試程序lab9_3.cpp中聲明一個整型隊列或棧對象，插入5個整數(shù)，壓入隊列或棧，再依次取出并顯示出來。4.選做聲明course課程類，有屬性：課程名char name21、成績short score；在實驗七的student類中增加屬性；所修課程course，為課程類對象的鏈表。在測試程序中測試這個類，學生類與課程類關(guān)系如圖將直接插入排序、直接選擇排序、冒泡排序、順序查找函數(shù)封裝到第九章的數(shù)組類中，作為成員函數(shù)，實現(xiàn)并測試這個類三、實驗內(nèi)容：1. /9-5.h#ifndef NODE_CLASS#define NODE

3、_CLASStemplate class Node private: Node *ne*t; /指向后繼節(jié)點的指針 public: T data; /數(shù)據(jù)域 Node (const T& item, Node* ptrne*t = NULL); void InsertAfter(Node *p); Node *DeleteAfter(void); Node *Ne*tNode(void) const;template Node:Node(const T& item, Node* ptrne*t) : data(item), ne*t(ptrne*t) template Node *Node:N

4、e*tNode(void) const return ne*t;template void Node:InsertAfter(Node *p) p-ne*t = ne*t; /p節(jié)點指針域指向當前節(jié)點的后繼節(jié)點 ne*t = p; /當前節(jié)點的指針域指向ptemplate Node *Node:DeleteAfter(void)Node *tempPtr = ne*t; /將欲刪除的節(jié)點地址存儲到tempPtr中 if (ne*t = NULL) /如果當前節(jié)點沒有后繼節(jié)點，則返回NULL return NULL; ne*t = tempPtr-ne*t; /使當前節(jié)點的指針域指向tempPt

5、r的后繼節(jié)點 return tempPtr; /返回被刪除的節(jié)點的地址#endif / NODE_CLASS/Node.h#ifndef NODE_LIBRARY#define NODE_LIBRARY#include #include #include 9_5.husing namespace std;template Node *GetNode(const T& item, Node *ne*tPtr = NULL) Node *newNode; newNode = new Node(item, ne*tPtr); if (newNode = NULL) /如果分配內(nèi)存失敗，程序中止 ce

6、rr Memory allocation failure! endl; e*it(1); return newNode;enum AppendNewline noNewline,addNewline;template void PrintList(Node *head, AppendNewline addnl = noNewline) Node *currPtr = head; while(currPtr != NULL) if(addnl = addNewline) cout data endl; else cout data Ne*tNode(); template int Find(No

7、de *head, T& item, Node* &prevPtr) Node *currPtr = head; /從第一個結(jié)點開場遍歷 prevPtr = NULL; while(currPtr != NULL) if (currPtr-data = item) return 1; prevPtr = currPtr; /記錄下當前結(jié)點的地址 currPtr = currPtr-Ne*tNode(); return 0; /找不到時template void InsertFront(Node* & head, T item) head = GetNode(item,head);templat

8、e void InsertRear(Node* & head, const T& item) Node *newNode, *currPtr = head; if (currPtr = NULL) InsertFront(head,item); else while(currPtr-Ne*tNode() != NULL) currPtr = currPtr-Ne*tNode(); newNode = GetNode(item); currPtr-InsertAfter(newNode); template void DeleteFront(Node* & head) Node *p = hea

9、d; /取得將被刪除的結(jié)點的地址 if (head != NULL) / 確認鏈表不空 head = head-Ne*tNode(); / 將表頭指針head移向第二個結(jié)點 delete p; /刪除原第一個結(jié)點 template void Delete (Node* & head, T key) Node *currPtr = head, *prevPtr = NULL; if (currPtr = NULL) return; while (currPtr != NULL & currPtr-data != key) / currPtr前行，prevPtr跟隨其后 prevPtr = cur

10、rPtr; currPtr = currPtr-Ne*tNode(); if (currPtr != NULL) if(prevPtr = NULL) /找到的是鏈表第一個結(jié)點 head = head-Ne*tNode(); else prevPtr-DeleteAfter(); delete currPtr; /釋放被刪除的結(jié)點所占的內(nèi)存空間 template void InsertOrder(Node* & head, T item) Node *currPtr, *prevPtr, *newNode; prevPtr = NULL; currPtr = head; while (curr

11、Ptr != NULL) if (item data) break; / currPtr前行，prevPtr跟隨其后 prevPtr = currPtr; currPtr = currPtr-Ne*tNode(); if (prevPtr = NULL) /如果插入點在表頭 InsertFront(head,item); else newNode = GetNode(item); prevPtr-InsertAfter(newNode); template void ClearList(Node * &head) Node *currPtr, *ne*tPtr; currPtr = head;

12、 while(currPtr != NULL) ne*tPtr = currPtr-Ne*tNode(); delete currPtr; currPtr = ne*tPtr; /使指針currPtr指向下一個結(jié)點 head = NULL; /將頭結(jié)點置為NULL，標志著鏈表為空#endif / NODE_LIBRARY/lab9_1.cpp#include #include 9_5.h#include node.husing namespace std;int main() Node *head = NULL, *prevPtr, *delPtr; int i, key, item; for

13、 (i=0;i 10;i+) coutplease input i+1 number To insert a header :item; InsertFront(head, item); cout List: ; PrintList(head,noNewline); cout endl; cout key; prevPtr = head; while (Find(head,key,prevPtr) != NULL) if(prevPtr = NULL) /找到的是鏈表第一個結(jié)點 head = head-Ne*tNode(); else delPtr=prevPtr-DeleteAfter();

14、 delete delPtr; cout List: ; PrintList(head,noNewline); cout endl; ClearList(head);運行結(jié)果：please input 1 number To insert a header :1please input 2 number To insert a header :2please input 3 number To insert a header :3please input 4 number To insert a header :4please input 5 number To insert a header

15、 :5please input 6 number To insert a header :6please input 7 number To insert a header :7please input 8 number To insert a header : 8please input 9 number To insert a header :9please input 10 number To insert a header :10List: 10 9 8 7 6 5 4 3 2 1請輸入一個需要刪除的整數(shù): 2List: 10 9 8 7 6 5 4 3 12. /link.h#ifn

16、def LINKEDLIST_CLASS#define LINKEDLIST_CLASS#include #include using namespace std;#ifndef NULLconst int NULL = 0;#endif / NULL#include 9_5.htemplate class LinkedList private: Node *front, *rear; Node *prevPtr, *currPtr; int size; int position; Node *GetNode(const T& item,Node *ptrNe*t=NULL); void Fr

17、eeNode(Node *p); void CopyList(const LinkedList& L); public: LinkedList(void); LinkedList(const LinkedList& L); /拷貝構(gòu)造函數(shù) LinkedList(void); LinkedList& operator= (const LinkedList& L); int ListSize(void) const; /返回鏈表中元素個數(shù)size int ListEmpty(void) const; /size等于0時返回TRUE,否則返回FALSE void Reset(int pos = 0)

18、; void Ne*t(void); /使prevPtr和currPtr移動到下一個節(jié)點 int EndOfList(void) const; int CurrentPosition(void) const; /返回數(shù)據(jù)成員position void InsertFront(const T& item); /在表頭插入 void InsertRear(const T& item); /在表尾添加 void InsertAt(const T& item); /在當前節(jié)點之前插入 void InsertAfter(const T& item); /在當前節(jié)點之后插入 T DeleteFront(v

19、oid); /刪除頭節(jié)點 void DeleteAt(void); /刪除當前節(jié)點 T& Data(void); void ClearList(void);template Node *LinkedList:GetNode(const T& item, Node* ptrNe*t) Node *p; p = new Node(item,ptrNe*t); if (p = NULL) cout Memory allocation failure!n; e*it(1); return p;template void LinkedList:FreeNode(Node *p) delete p;tem

20、plate void LinkedList:CopyList(const LinkedList& L) Node *p = L.front; int pos; while (p != NULL) InsertRear(p-data); p = p-Ne*tNode(); if (position = -1) return; prevPtr = NULL; currPtr = front; for (pos = 0; pos != position; pos+) prevPtr = currPtr; currPtr = currPtr-Ne*tNode(); template LinkedLis

21、t:LinkedList(void): front(NULL), rear(NULL), prevPtr(NULL),currPtr(NULL), size(0), position(-1)template LinkedList:LinkedList(const LinkedList& L) front = rear = NULL; prevPtr = currPtr = NULL; size = 0; position = -1; CopyList(L);template void LinkedList:ClearList(void) Node *currPosition, *ne*tPos

22、ition; currPosition = front; while(currPosition != NULL) ne*tPosition = currPosition-Ne*tNode(); FreeNode(currPosition); currPosition = ne*tPosition; / 移動到下一結(jié)點 front = rear = NULL; prevPtr = currPtr = NULL; size = 0; position = -1;template LinkedList:LinkedList(void) ClearList();template LinkedList&

23、 LinkedList:operator= (const LinkedList& L) if (this = &L) / 不能將鏈表賦值給它自身 return *this; ClearList(); CopyList(L); return *this;template int LinkedList:ListSize(void) const return size; template int LinkedList:ListEmpty(void) const return size = 0;template void LinkedList:Ne*t(void) if (currPtr != NUL

24、L) prevPtr = currPtr; currPtr = currPtr-Ne*tNode(); position+; template int LinkedList:EndOfList(void) const return currPtr = NULL;template int LinkedList:CurrentPosition(void) const return position;template void LinkedList:Reset(int pos) int startPos; if (front = NULL) return; if (pos size-1) cerr

25、Reset: Invalid list position: pos Ne*tNode(); prevPtr = front; startPos = 1; for(position=startPos; position != pos; position+) prevPtr = currPtr; currPtr = currPtr-Ne*tNode(); template T& LinkedList:Data(void) if (size = 0 | currPtr = NULL) cerr Data: invalid reference! data;template void LinkedLis

26、t:InsertFront(const T& item) if (front != NULL) Reset(); InsertAt(item); / 在表頭插入template void LinkedList:InsertRear(const T& item) Node *newNode; prevPtr = rear; newNode = GetNode(item); / 創(chuàng)立新結(jié)點 if (rear = NULL) / 如果表空則插入在表頭 front = rear = newNode; else rear-InsertAfter(newNode); rear = newNode; cur

27、rPtr = rear; position = size; size+;template void LinkedList:InsertAt(const T& item) Node *newNode; if (prevPtr = NULL) newNode = GetNode(item,front); front = newNode; else newNode = GetNode(item); prevPtr-InsertAfter(newNode); if (prevPtr = rear) rear = newNode; position = size; currPtr = newNode;

28、size+; template void LinkedList:InsertAfter(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 = cur

29、rPtr; currPtr = p; size+; / 使鏈表長度增值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! Ne*tNode(); else p = prevPtr-DeleteAfter(); i

30、f (p = rear) rear = prevPtr; position-; currPtr = p-Ne*tNode(); FreeNode(p); size-;#endif / LINKEDLIST_CLASS/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.Ne*t(); cou

31、t endl; B.Reset(); cout 鏈表B的元素為： ; while(!B.EndOfList() cout B.Data() ; B.Ne*t(); cout endl; cout 把B中的元素插入A中. endl; B.Ret(); while(!B.EndOfList() A.InsertRear(B.Data(); B.Ne*t(); A.Reset(); cout 此時，鏈表A的元素為： ; while(!A.EndOfList() cout A.Data() ; A.Ne*t(); cout endl;3. /queue.h#ifndef QUEUE_CLASS#define QUEUE_CLASS#include #include using namespace std;#include link.htemplate c