實(shí)驗(yàn)報(bào)告群體類和群體數(shù)據(jù)

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

2、k.h實(shí)現(xiàn)例9-6的鏈表類，在測(cè)試程序lab_2.cpp中聲明兩個(gè)整型鏈表A和B，分別插入5元素，然后把B中的元素加入A的尾部。3、編寫程序queue.h，用鏈表實(shí)現(xiàn)隊(duì)列（或棧），在測(cè)試程序lab9_3.cpp中聲明一個(gè)整型隊(duì)列（或棧）對(duì)象，插入5個(gè)整數(shù)，壓入隊(duì)列（或棧），再依次取出并顯示出來。4、（選做）聲明course（課程）類，有屬性：課程名char name21、成績(jī)short score；在實(shí)驗(yàn)七的student類中增加屬性；所修課程course，為課程類對(duì)象的鏈表。在測(cè)試程序中測(cè)試這個(gè)類，學(xué)生類與課程類關(guān)系如圖5、將直接插入排序、直接選擇排序、冒泡排序、順序查找函數(shù)封裝到第九章的數(shù)

3、組類中，作為成員函數(shù)，實(shí)現(xiàn)并測(cè)試這個(gè)類。3、 實(shí)驗(yàn)程序1、#ifndef NODE_CLASS#define NODE_CLASStemplate class Node private: Node *next; public: T data; Node (const T& item, Node* ptrnext = NULL); void InsertAfter(Node *p); Node *DeleteAfter(void); Node *NextNode(void) const;template Node:Node(const T& item, Node* ptrnext) : data

4、(item), next(ptrnext)template Node *Node:NextNode(void) const return next; template void Node:InsertAfter(Node *p)p-next = next; next = p;template Node *Node:DeleteAfter(void)Node *tempPtr = next; if (next = NULL) return NULL; next = tempPtr-next; return tempPtr; #endif#ifndef NODE_LIBRARY#define NO

5、DE_LIBRARY#include #include #include 9_5.husing namespace std;template Node *GetNode(const T& item, Node *nextPtr = NULL) Node *newNode; newNode = new Node(item, nextPtr); if (newNode = NULL) cerr Memory allocation failure! endl; exit(1); return newNode;enum AppendNewline noNewline,addNewline;templa

6、te void PrintList(Node *head, AppendNewline addnl = noNewline) Node *currPtr = head; while(currPtr != NULL) if(addnl = addNewline) cout data endl; else cout data NextNode(); template int Find(Node *head, T& item, Node* &prevPtr)Node *currPtr = head;prevPtr = NULL;while(currPtr != NULL) if (currPtr-d

7、ata = item) return 1; prevPtr = currPtr; currPtr = currPtr-NextNode();return 0;template void InsertFront(Node* & head, T item) head = GetNode(item,head);template void InsertRear(Node* & head, const T& item) Node *newNode, *currPtr = head; if (currPtr = NULL) InsertFront(head,item); else while(currPt

8、r-NextNode() != NULL) currPtr = currPtr-NextNode(); newNode = GetNode(item); currPtr-InsertAfter(newNode); template void DeleteFront(Node* & head) Node *p = head; if (head != NULL) head = head-NextNode(); delete p; template void Delete (Node* & head, T key) Node *currPtr = head, *prevPtr = NULL; if

9、(currPtr = NULL) return; while (currPtr != NULL & currPtr-data != key) prevPtr = currPtr; currPtr = currPtr-NextNode(); if (currPtr != NULL) if(prevPtr = NULL) head = head-NextNode(); else prevPtr-DeleteAfter(); delete currPtr; template void InsertOrder(Node* & head, T item) Node *currPtr, *prevPtr,

10、 *newNode; prevPtr = NULL; currPtr = head; while (currPtr != NULL) if (item data) break; prevPtr = currPtr; currPtr = currPtr-NextNode(); if (prevPtr = NULL) InsertFront(head,item); else newNode = GetNode(item); prevPtr-InsertAfter(newNode); template void ClearList(Node * &head) Node *currPtr, *next

11、Ptr; currPtr = head; while(currPtr != NULL) nextPtr = currPtr-NextNode(); delete currPtr; currPtr = nextPtr; head = NULL;#endif #include #include 9_5.h#include node.husing namespace std;int main() Node *head = NULL, *prevPtr, *delPtr; int i, key, item; for (i=0;i item; InsertFront(head, item); cout

12、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: ; PrintList(head,noNewline); cout endl; ClearList(head);2、#include link.hint main()Li

13、nkedList 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.EndOfList()cout B.Data() ;B.Next();cout endl;cout 把B中的元素插入A中. endl;B.Reset();while(!B.EndOfList()A.InsertRear(B.Da

14、ta();B.Next();A.Reset();cout 此時(shí)，鏈表A的元素為： ;while(!A.EndOfList()cout A.Data() ;A.Next();cout endl;#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

15、*prevPtr, *currPtr; int size; int position; Node *GetNode(const T& item,Node *ptrNext=NULL); void FreeNode(Node *p); void CopyList(const LinkedList& L); public: LinkedList(void); LinkedList(const LinkedList& L); LinkedList(void); LinkedList& operator= (const LinkedList& L); int ListSize(void) const;

16、 int ListEmpty(void) const; void Reset(int pos = 0); void Next(void); int EndOfList(void) const; int CurrentPosition(void) const; void InsertFront(const T& item); void InsertRear(const T& item); void InsertAt(const T& item); void InsertAfter(const T& item); T DeleteFront(void); void DeleteAt(void);

17、T& Data(void); 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;template void LinkedList:FreeNode(Node *p) delete p;template void LinkedList:CopyList(const Linke

18、dList& L) Node *p = L.front; int pos; while (p != NULL) InsertRear(p-data); p = p-NextNode(); if (position = -1) return; prevPtr = NULL; currPtr = front; for (pos = 0; pos != position; pos+) prevPtr = currPtr; currPtr = currPtr-NextNode(); template LinkedList:LinkedList(void): front(NULL), rear(NULL

19、), 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, *nextPosition; currPosition = front; while(currPos

20、ition != NULL) nextPosition = currPosition-NextNode(); FreeNode(currPosition); 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 =

21、 &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:Next(void) if (currPtr != NULL) prevPtr = currPtr; currPtr = currPtr-NextNode(); position+; templa

22、te 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 Reset: Invalid list position: pos NextNode(); prevPtr = front; startP

23、os = 1; for(position=startPos; position != pos; position+) prevPtr = currPtr; currPtr = currPtr-NextNode(); template T& LinkedList:Data(void) if (size = 0 | currPtr = NULL) cerr Data: invalid reference! data;template void LinkedList:InsertFront(const T& item) if (front != NULL) Reset(); InsertAt(ite

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

25、; 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; size+; template void LinkedList:InsertAfter(const T& item) Node *p; p = GetNode(item); if (front =

26、 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+;template T LinkedList:DeleteFront(void) T item; Reset(); if (front = NULL) cerr In

27、valid deletion! data; DeleteAt(); return item;template void LinkedList:DeleteAt(void) Node *p; if (currPtr = NULL) cerr Invalid deletion! NextNode(); else p = prevPtr-DeleteAfter(); if (p = rear) rear = prevPtr; position-; currPtr = p-NextNode(); FreeNode(p); size-;#endif3、#ifndef QUEUE_CLASS#define

28、 QUEUE_CLASS#include #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); int QLength(void) const; int QEmpty(void) const; void QClear(void);template Queue:Queue(void)template

29、 int Queue:QLength(void) const return queueList.ListSize();template int Queue:QEmpty(void) const return queueList.ListEmpty();template void Queue:QClear(void) queueList.ClearList();template void Queue:QInsert(const T& elt) queueList.InsertRear(elt);template T Queue:QDelete(void) if (queueList.ListEm

30、pty() cerr Calling QDelete for an empty queue! endl; exit(1); return queueList.DeleteFront();template T Queue:QFront(void) if (queueList.ListEmpty() cerr Calling QFront for an empty queue! endl; exit(1); queueList.Reset(); return queueList.Data();#endif#ifndef LINKEDLIST_CLASS#define LINKEDLIST_CLAS

31、S#include #include using namespace std;#ifndef NULLconst int NULL = 0;#endif#include 9-3.htemplate class LinkedList private: Node *front, *rear; Node *prevPtr, *currPtr; int size; int position; Node *GetNode(const T& item,Node *ptrNext=NULL); void FreeNode(Node *p); void CopyList(const LinkedList& L

32、); public: LinkedList(void); LinkedList(const LinkedList& L); LinkedList(void); LinkedList& operator= (const LinkedList& L); int ListSize(void) const; int ListEmpty(void) const; void Reset(int pos = 0); void Next(void); int EndOfList(void) const; int CurrentPosition(void) const; void InsertFront(con

33、st T& item); void InsertRear(const T& item); void InsertAt(const T& item); void InsertAfter(const T& item); T DeleteFront(void); void DeleteAt(void); T& Data(void); void ClearList(void);template Node *LinkedList:GetNode(const T& item, Node* ptrNext) Node *p; p = new Node(item,ptrNext); if (p = NULL)

34、 cout Memory allocation failure!n; exit(1); return p;template void LinkedList:FreeNode(Node *p) delete p;template void LinkedList:CopyList(const LinkedList& L) Node *p = L.front; int pos; while (p != NULL) InsertRear(p-data); p = p-NextNode(); if (position = -1) return; prevPtr = NULL; currPtr = fro

35、nt; for (pos = 0; pos != position; pos+) prevPtr = currPtr; currPtr = currPtr-NextNode(); template LinkedList: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

36、; size = 0; position = -1; CopyList(L);template void LinkedList:ClearList(void) Node *currPosition, *nextPosition; currPosition = front; while(currPosition != NULL) nextPosition = currPosition-NextNode(); FreeNode(currPosition); currPosition = nextPosition; front = rear = NULL; prevPtr = currPtr = N

37、ULL; 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 *this;template int LinkedList:ListSize(void) const return size;template int LinkedList:ListEmpty

38、(void) const return size = 0;template void LinkedList:Next(void) if (currPtr != NULL) prevPtr = currPtr; currPtr = currPtr-NextNode(); position+; template int LinkedList:EndOfList(void) const return currPtr = NULL;template int LinkedList:CurrentPosition(void) const return position;template void Link

39、edList:Reset(int pos) int startPos; if (front = NULL) return; if (pos size-1) cerr Reset: Invalid list position: pos NextNode(); prevPtr = front; startPos = 1;for(position=startPos; position != pos; position+) prevPtr = currPtr; currPtr = currPtr-NextNode(); template T& LinkedList:Data(void) if (size = 0 | currPtr = NULL) cerr Data: invalid reference! data;template void LinkedList:InsertFront(const T& item) if (front != NULL) Reset(); InsertAt(item);template void LinkedList:InsertRear(const T& item) Node *newNode; prevPtr = rea