（二 一 五 年十一 月一、实验目的1、了解节点类的声明和实现 ， 学习其使用方法2、了解链表类的声明和实现，学习其使用方法3、了解栈类的声明和实现，学习其使用方法4、了解队列类的声明和实现，学习其使用方法5、掌握对数组元素排序的方法6、掌握对数组元素查找的方法二、实验内容1、编写程序 Node.h 实现例 9-5 的节点类，并编写测试程序lab9_1.cpp ，实现链表的基本操作。2、编写程序link.h实现例 9-6 的链表类，在测试程序lab_2.cpp中声明两个整型链表A和 B，分别插入 5 元素，然后把B中的元素加入A的尾部。3、编写程序 queue.h ，用链表实现队列（或栈） ，在测试程序lab9_3.cpp中声明一个整型队列（或栈）对象，插入5 个整数，压入队列（或栈） ，再依次取出并显示出来。4、 （选做）声明course （课程）类，有属性：课程名char name21、成绩 short score；面向对象程序设计实验报告学校代码：10128 题目 ： 群 体 类 和 群 体 数 据学 生 姓 名 ： 燕 飞学院 ： 理 学 院系别 ： 数 学 系专业 ： 信 息 与 计 算 科 学班级 ： 信 计1 2 - 2任 课 教 师 ： 侯 睿在实验七的 student类中增加属性；所修课程course ，为课程类对象的链表。在测试程序中测试这个类，学生类与课程类关系如图5、将直接插入排序、直接选择排序、冒泡排序、顺序查找函数封装到第九章的数组类中，作为成员函数，实现并测试这个类。三、实验程序1、#ifndef NODE_CLASS #define NODE_CLASS template 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(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 NODE_LIBRARY #include #include #include 9_5.h using 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; template 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-data = 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(currPtr-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 (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, *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, *nextPtr; currPtr = head; while(currPtr != NULL) nextPtr = currPtr-NextNode(); delete currPtr; currPtr = nextPtr; head = NULL; #endif #include #include 9_5.h #include node.h using namespace std; int main() Node *head = NULL, *prevPtr, *delPtr; int i, key, item; for (i=0;i item; InsertFront(head, item); 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: ; PrintList(head,noNewline); cout endl; ClearList(head); 2、#include link.h int 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.EndOfList() 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; #ifndef LINKEDLIST_CLASS #define LINKEDLIST_CLASS #include #include using namespace std; #ifndef NULL const int NULL = 0; #endif / NULL #include 9-3.h template 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); 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(const 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) 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 = front; 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; 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 = 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 *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+; 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 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 = 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; 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 = 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 Invalid 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-; #endif 3、#ifndef QUEUE_CLASS #define QUEUE_CLASS #include #include using namespace std; #include link.h template 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 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.ListEmpty() 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_CLASS #include #include using namespace std; #ifndef NULL const int NULL = 0; #endif #include 9-3.h template 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); 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(const 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) 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 = front; 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; 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 = 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 *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+; 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 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 = 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; 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 = 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 Invalid 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-; #endif / LINKEDLIST_CLASS #include queue.h int main() Queue A; for(int i=0;i5;i+) A.QInsert(2*i+1); cout 队列 A的元素为： ; while(!A.QEmpty() cout A.QFront() ; A.QDelete(); cout endl; 4、5、#include #include array1.h using namespace std; int main() Array A(10); int i,k; int SortType; int SearchNum; cout 请输入 10 个整数 endl; for(i=0;i10;i+) cout 输入第 i+1 Ai; cout 输入的数组为： endl; for(i=0;i10;i+) cout Ai ; cout endl; cout SortType; switch(SortType) case 1: A.InsertionSort(); break; case 2: A.SelectionSort(); break; case 3: A.BubbleSort(); break; default: cout 输入错误，程序退出!; exit(0); cout 排序后的数组为： endl; for(i=0;i10;i+) cout Ai ; cout endl; cout SearchNum; k= A.SeqSearch(SearchNum); if (k0) cout 没有找到数字 SearchNum endl; else cout SearchNum 是第 k+1 个数字 endl; #ifndef ARRAY1_CLASS #define ARRAY1_CLASS #include #include using namespace std; #ifndef NULL const int NULL = 0; #endif enum ErrorType invalidArraySize, memoryAllocationError, indexOutOfRange; char *errorMsg = Invalid array size, Memory allocation error, Invalid index: ; template class Array private: T* alist; int size; void Error(ErrorType error,int badIndex=0) const; public: Array(int sz = 50); Array(const Array& A); Array(void); Array& operator= (const Array& rhs); T& operator(int i); operator T* (void) const; int ListSize(void) const; void Resize(int sz); void InsertionSort(); void SelectionSort(); void BubbleSort(); int SeqSearch(T key); ; template void Array:Error(ErrorType error, int badIndex) const cerr errorMsgerror; if (error = indexOutOfRange) cerr badIndex; cerr endl; exit(1); template Array:Array(int sz) if (sz = 0) Error(invalidArraySize); size = sz; alist = new Tsize; if (alist = NULL) Error(memoryAllocationError); template Array:Array(void) delete alist; template Array:Array(const Array& X) int n = X.size; size = n; alist = new Tn; if (alist = NULL) Error(memoryAllocationError); T* srcptr = X.alist; T* destptr = alist; while (n-) *destptr+ = *srcptr+; template Array& Array:operator= (const Array& rhs) int n = rhs.size; if (size != n) delete alist; alist = new Tn; if (alist = NULL) Error(memoryAllocationError); size = n; T* destptr = alist; T* srcptr = rhs.alist; while (n-) *destptr+ = *srcptr+; return *this; template T& Array:operator (int n) if (n size-1) Error(indexOutOfRange,n); return alistn; template Array:operator T* (void) const return alist; template int Array:ListSize(void) const return size; template void Array:Resize(int sz) if (sz = 0) Error(invalidArraySize); if (sz = size) return; T* newlist = new Tsz; if (newlist = NULL) Error(memoryAllocationError); int n = (sz = size) ? sz : size; T* srcptr = alist; T* destptr = newlist; while (n-) *destptr+ = *srcptr+; delete alist; alist = newlist; size = sz; template void Array:InsertionSort() int i, j; T temp; for (i = 1; i 0 & temp alistj-1) alistj = alistj-1; j-; alistj = temp; template void Array:SelectionSort() int smallIndex; int i, j; for (i = 0; i size-1; i+) smallIndex = i; for (j = i+1; j size; j+) if (alistj alistsmallIndex) smallIndex = j; Swap(alisti, alistsmallIndex); template void Swap (T &x, T &y) T temp; temp = x; x = y; y = temp; template void Array:BubbleSort() int i,j; int lastExchangeIndex; i = size-1; while (i 0) lastExchangeIndex = 0; for (j = 0; j i; j+) if (alistj+1 alistj) Swap(alistj,alistj+1); lastExchangeIndex = j; i = lastExchangeIndex; template int Array:SeqSearch(T key) for(int i=0;i size;i+) if (alisti = key) return i;