您好,欢迎访问三七文档
当前位置:首页 > 电子/通信 > 综合/其它 > 实验八 泛型程序设计
实验八泛型程序设计软件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个整数,压人队列(或栈),再依次取出并显示出来。3.使用C++标准模板库(STL)中的双向队列类(deque)重新实现上一小题。三、实验步骤1.参照教材《C++语言程序设计》中链表类LinkeclI。ist的定义(教材中的例程9—6.h),给出其实现,注意合理使用NodIe类(教材中的例程9—3.h)的成员函数。在测试程序中定义整型链表A和B,分别插入5个元素,使用循环语句显示链表中的元素,然后把B中的元素加入A的尾部,再显示出来。2.队列类的特点就是其元素的操作顺序为先入先出(FIFO),用上题中的链表类实现队列类,用链表类的成员函数实现队列的成员函数,在测试程序中定义一个整型队列对象,观察队列类中的元素先入先出的特点。3.在程序中包含语句#includedeque,使用deque类的方法push_back()、empty()、pop_front()完成上一小题的要求。程序名:lab9_3.cpp。、四、实验程序1、#includelink.hintmain(){LinkedListintA,B;for(inti=0;i5;i++){A.InsertRear(2*i+1);B.InsertRear(2*i+2);}A.Reset();cout链表A的元素为:;while(!A.EndOfList()){coutA.Data();A.Next();}coutendl;B.Reset();cout链表B的元素为:;while(!B.EndOfList()){coutB.Data();B.Next();}coutendl;cout把B中的元素插入A中...endl;B.Reset();while(!B.EndOfList()){A.InsertRear(B.Data());B.Next();}A.Reset();cout此时,链表A的元素为:;while(!A.EndOfList()){coutA.Data();A.Next();}coutendl;}#ifndefLINKEDLIST_CLASS#defineLINKEDLIST_CLASS#includeiostream#includecstdlibusingnamespacestd;#ifndefNULLconstintNULL=0;#endif//NULL#include9-3.htemplateclassTclassLinkedList{private:NodeT*front,*rear;NodeT*prevPtr,*currPtr;intsize;intposition;NodeT*GetNode(constT&item,NodeT*ptrNext=NULL);voidFreeNode(NodeT*p);voidCopyList(constLinkedListT&L);public:LinkedList(void);LinkedList(constLinkedListT&L);~LinkedList(void);LinkedListT&operator=(constLinkedListT&L);intListSize(void)const;intListEmpty(void)const;voidReset(intpos=0);voidNext(void);intEndOfList(void)const;intCurrentPosition(void)const;voidInsertFront(constT&item);voidInsertRear(constT&item);voidInsertAt(constT&item);voidInsertAfter(constT&item);TDeleteFront(void);voidDeleteAt(void);T&Data(void);voidClearList(void);};templateclassTNodeT*LinkedListT::GetNode(constT&item,NodeT*ptrNext){NodeT*p;p=newNodeT(item,ptrNext);if(p==NULL){coutMemoryallocationfailure!\n;exit(1);}returnp;}templateclassTvoidLinkedListT::FreeNode(NodeT*p){deletep;}templateclassTvoidLinkedListT::CopyList(constLinkedListT&L){NodeT*p=L.front;intpos;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();}}templateclassTLinkedListT::LinkedList(void):front(NULL),rear(NULL),prevPtr(NULL),currPtr(NULL),size(0),position(-1){}templateclassTLinkedListT::LinkedList(constLinkedListT&L){front=rear=NULL;prevPtr=currPtr=NULL;size=0;position=-1;CopyList(L);}templateclassTvoidLinkedListT::ClearList(void){NodeT*currPosition,*nextPosition;currPosition=front;while(currPosition!=NULL){nextPosition=currPosition-NextNode();FreeNode(currPosition);currPosition=nextPosition;}front=rear=NULL;prevPtr=currPtr=NULL;size=0;position=-1;}templateclassTLinkedListT::~LinkedList(void){ClearList();}templateclassTLinkedListT&LinkedListT::operator=(constLinkedListT&L){if(this==&L)return*this;ClearList();CopyList(L);return*this;}templateclassTintLinkedListT::ListSize(void)const{returnsize;}templateclassTintLinkedListT::ListEmpty(void)const{returnsize==0;}templateclassTvoidLinkedListT::Next(void){if(currPtr!=NULL){prevPtr=currPtr;currPtr=currPtr-NextNode();position++;}}templateclassTintLinkedListT::EndOfList(void)const{returncurrPtr==NULL;}templateclassTintLinkedListT::CurrentPosition(void)const{returnposition;}templateclassTvoidLinkedListT::Reset(intpos){intstartPos;if(front==NULL)return;if(pos0||possize-1){cerrReset:Invalidlistposition:posendl;return;}if(pos==0){prevPtr=NULL;currPtr=front;position=0;}else{currPtr=front-NextNode();prevPtr=front;startPos=1;for(position=startPos;position!=pos;position++){prevPtr=currPtr;currPtr=currPtr-NextNode();}}}templateclassTT&LinkedListT::Data(void){if(size==0||currPtr==NULL){cerrData:invalidreference!endl;exit(1);}returncurrPtr-data;}templateclassTvoidLinkedListT::InsertFront(constT&item){if(front!=NULL)Reset();InsertAt(item);}templateclassTvoidLinkedListT::InsertRear(constT&item){NodeT*newNode;prevPtr=rear;newNode=GetNode(item);if(rear==NULL)front=rear=newNode;else{rear-InsertAfter(newNode);rear=newNode;}currPtr=rear;position=size;size++;}templateclassTvoidLinkedListT::InsertAt(constT&item){NodeT*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++;}templateclassTvoidLinkedListT::InsertAfter(constT&item){NodeT*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++;}templateclassTTLinkedListT::DeleteFron
本文标题:实验八 泛型程序设计
链接地址:https://www.777doc.com/doc-6959849 .html