实验八 泛型程序设计

1、实验八 泛型程序设计软件1502 杨成进 151303230一、实验目的1了解链表类的定义与实现，学习其使用方法。2了解栈类的定义与实现，学习其使用方法。3了解队列类的定义与实现，学习其使用方法。4了解C+标准模板库STL的使用方法。二、实验任务 1编写程序linkh，实现教材中例96的链表类。在测试程序lab91cpp中定义两个整型链表A和B，分别插入5个元素，然后把B中的元素加入A的尾部。 2编写程序queueh，用链表实现队列(或栈)类。在测试程序lab92cpp中定义一个整型队列(或栈)对象，插入5个整数，压人队列(或栈)，再依次取出并显示出来。 3使用C+标准模板库(STL)中的双向

2、队列类(deque)重新实现上一小题。三、实验步骤1参照教材C+语言程序设计中链表类LinkeclI。ist的定义(教材中的例程96h)，给出其实现，注意合理使用NodIe类(教材中的例程93h)的成员函数。在测试程序中定义整型链表A和B，分别插入5个元素，使用循环语句显示链表中的元素，然后把B中的元素加入A的尾部，再显示出来。2队列类的特点就是其元素的操作顺序为先入先出（FIFO），用上题中的链表类实现队列类，用链表类的成员函数实现队列的成员函数，在测试程序中定义一个整型队列对象，观察队列类中的元素先入先出的特点。3在程序中包含语句#include ,使用deque类的方法push_back

3、()、empty()、pop_front()完成上一小题的要求。程序名：lab9_3.cpp。、四、实验程序1、#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.EndOfList()cout B.Data() ;B.Nex

4、t();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 NULLconst int NULL = 0;#end

5、if / NULL#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); public: LinkedList(void); LinkedList(const LinkedList& L); Linke

6、dList(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&

7、 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

8、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

9、 = 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:Cle

10、arList(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)Cl

11、earList();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 (

12、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

13、 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

14、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; po

15、sition = 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

16、 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+

17、;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; posit

18、ion-; currPtr = p-NextNode(); FreeNode(p); size-;#endif2、#ifndef QUEUE_CLASS#define 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)

19、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&

20、 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.Res

21、et(); return queueList.Data();#endif#ifndef LINKEDLIST_CLASS#define LINKEDLIST_CLASS#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&

22、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

23、); 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:GetNo

24、de(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(

25、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 Linke

26、dList: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(cur

27、rPosition); 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;templat

28、e 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;tem

29、plate 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

30、 = 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 *newNod

31、e; 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 = newNo

32、de; 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

33、= 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 Linked

34、List: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.hint main()Queue A;for(int i=0;i5;i+)A.QInsert(2*i+1);cout 队

35、列A的元素为： ;while(!A.QEmpty()cout A.QFront() ;A.QDelete();cout endl;4、5、#include #include array1.husing 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(SortT

36、ype)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;elsecout SearchNum 是第 k+1 个数字 endl;#ifndef AR

37、RAY1_CLASS#define ARRAY1_CLASS#include #include using namespace std;#ifndef NULLconst int NULL = 0;#endifenum ErrorType invalidArraySize, memoryAllocationError, indexOutOfRange;char *errorMsg = Invalid array size, Memory allocation error, Invalid index: ;template class Array private: T* alist; int s

38、ize; 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 Bubb

39、leSort(); 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+