实验八泛型程序设计

《实验八泛型程序设计》由会员分享，可在线阅读，更多相关《实验八泛型程序设计（42页珍藏版）》请在金锄头文库上搜索。

1、实验八 泛型程序设计软件 1502 杨成进 151303230一、 实验目的1. 了解链表类的定义与实现，学习其使用方法。2. 了解栈类的定义与实现，学习其使用方法。3.了解队列类的定义与实现，学习其使用方法。4. 了解 C+而准模板库 STL 的使用方法。二、 实验任务1.编写程序 link.h，实现教材中例 9-6 的链表类。在测试程序 lab9 1.cpp 中定义两个整型链 表A 与 B,分别插入 5 个元素，然后把 B 中的元素加入 A 的尾部。2.编写程序 queue.h，用链表实现队列（或栈）类。在测试程序 lab9 2.cpp 中定义一个整型队列（或栈）对象，插入 5 个整数，压

2、人队列（或栈），再依次取出并显示出来。3. 使用 C+标准模板库（STL 巾的双向队列类（deque）重新实现上一小题。三、 实验步骤1.参照教材C+语言程序设计中链表类LinkeclI。ist 的定义（教材中的例程 96.h），给出其实现,注意合理使用 Nodle 类（教材中的例程 9- 3.h）的成员函数。在测试程序中定义整型链表A 与 B，分别插入 5 个元素，使用循环语句显示链表中的元素，然后把 B 中的元素加入 A 的尾部,再显示出来。2.先入先出用链表类的成员函数实现队列的成员函数中的元素先入先出的特点。3. 在程序中包含语句 #include ，使用 deque 类的方法 pus

3、h_back（）、empty（）、pop_front（）完成上一小题的要求。程序名四、 实验程序队列类的特点就就是其元素的操作顺序为（FIFO ）用上题中的链表类实现队列类，在测试程序中定义一个整型队列对象，观察队列类：lab9_3、cpp。、1、#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()

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

5、 LINKEDLIST_CLASS#include #include using namespace std;#ifndef NULLconst int NULL = 0;#endif / NULL#include 9-3、htemplate ;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

6、);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);

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

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

9、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);tem

10、plate 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:Lin

11、kedList(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

12、(void)(if (currPtr != NULL)prevPtr = currPtr;currPtr = currPtr-NextNode();position+;template int LinkedList:EndOfList(void) constreturn currPtr = NULL;template int LinkedList:CurrentPosition(void) constreturn position;template void LinkedList:Reset(int pos)int startPos;if (front = NULL)return;if (po

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

14、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;elserear-InsertAfter(newNode);rear = newNode;currPtr = rear;position = size;size

15、+;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

16、(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;elseposition+;prevPtr = currPtr;currPtr = p;size+;template T LinkedList:DeleteFront(void)(

17、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();elsep = prevPtr-DeleteAfter();if (p = rear)(rear = prevPtr;position-;currPtr = p-NextNode();FreeNode(p);size-;#end

18、if2、#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 Q

19、ueue:Queue(void)(template int Queue:QLength(void) const(return queueList、ListSize();template int Queue:QEmpty(void) constreturn queueList、ListEmpty();template void Queue:QClear(void)(queueList、ClearList();template void Queue:QInsert(const T& elt)(queueList、 InsertRear(elt);template T Queue:QDelete(v

20、oid)(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#def

21、ine LINKEDLIST_CLASS#include #include using namespace std;#ifndef NULLconst 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

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

23、nst 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 Mem

24、ory 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;

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

26、-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;temp

27、late 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) constreturn size;template int LinkedList:ListEmpty(void) constreturn size = 0;template vo

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

29、 = 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 referenc

30、e! 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 = r

31、ear;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 voi

32、d 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;elseposition+;prevPtr = currPtr;currPtr = p;size+;template T Linked

33、List: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();elsep = prevPtr-DeleteAfter();if (p = rear)(rear = prevPtr;position-;currPtr = p-NextNode()

34、;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() 1A、QDelete();cout endl;4、5、#include #include arrayl、husing namespace std;int main()Array A(10);int i,k;int SortType;int SearchNum;cout

35、 请输入 10 个整数 endl;for(i=0;i10;i+)cout 输入第 i+1 Ai;cout 输入的数组为: endl;for(i=0;i10;i+)cout Ai ;cout endl;cout SortType;2、直接选择排序3、冒泡排序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+

36、)cout Ai cout endl;cout SearchNum;k= A、SeqSearch(SearchNum);if (k0)cout 没有找到数字 SearchNum endl;elsecout SearchNum 就是第 k+1 个数字 endl;#ifndef ARRAY1_CLASS#define ARRAY1_CLASS#include #include using namespace std;#ifndef NULLconst int NULL = 0;#endifenum ErrorTypeinvalidArraySize, memoryAllocationError,

37、indexOutOfRange;char *errorMsg=Invalid array size, Memory allocation error,Invalid index:;template class Arrayprivate: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);

38、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) constcerr errorMsgerror;if (error = indexOutOfRange)cerr badIndex;cerr endl;exit(1);template

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

40、 = 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+;r

41、eturn *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* ne

42、wlist = new Tsz;if (newlist = NULL)Error(memoryAllocationError);int n = (sz = size) ? sz : size;T* srcptr = alist;T* destptr = newlist;*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-

43、;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;Si, alistsmallindex);template void Swap (T &x, T &y)(T temp;temp = x;x = y;y = temp;template void Array:BubbleSort()

44、(int i,j;int lastExchangeindex;i = size-1;while (i 0)(lastExchangelndex = 0;for (j = 0; j i; j+)if (alistj+1 alistj)(Sj,alistj+1);lastExchangeIndex = j;i = lastExchangeIndex;template int Array:SeqSearch(T key)(for(int i=0;i size;i+)if (alisti = key)return i;return -1;#endif3、#include #include using namespace std;typedef dequeINTDEQUE;int main()(INTDEQUE A;for(int i=0;i5;i+)(A、push_back(2*i+1);cout 队列 A 的元素为：”while(!A、empty()(cout A、front() A、pop_front();cout endl;