《实验八 泛型程序设计.doc》由会员分享，可在线阅读，更多相关《实验八 泛型程序设计.doc（41页珍藏版）》请在三一文库上搜索。
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 LinkedList:DeleteAt(void) Node *p; if (currPtr = NULL) cerr Invalid deletion! NextNode(); else p = prevPtr-DeleteAfter(); if