群体类和群体数据

（二〇一一年十一月《面向对象的程序设计》实验报告学校代码：10128学号：题目：群体类和群体数据学生姓名：学院：理学院系别：数学系专业：信息与计算科学班级：任课教师：2一、实验目的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、将直接插入排序、直接选择排序、冒泡排序、顺序查找函数封装到第九章的数组类中，作为成员函数，实现并测试这个类。三、实验程序及结果1.程序一//9_5.h#ifndefNODE_CLASS#defineNODE_CLASS//类定义部分templateclassTclassNode{private:NodeT*next;//指向后继节点的指针public:Tdata;//数据域//构造函数Node(constT&item,NodeT*ptrnext=NULL);//在本节点之后插入一个同类节点pvoidInsertAfter(NodeT*p);//删除本节点的后继节点，并返回其地址NodeT*DeleteAfter(void);3//获取后继节点的地址NodeT*NextNode(void)const;};//类的实现部分//构造函数，初始化数据和指针成员templateclassTNodeT::Node(constT&item,NodeT*ptrnext):data(item),next(ptrnext){}//返回私有的指针成员templateclassTNodeT*NodeT::NextNode(void)const{returnnext;}//在当前节点之后插入一个节点ptemplateclassTvoidNodeT::InsertAfter(NodeT*p){p-next=next;//p节点指针域指向当前节点的后继节点next=p;//当前节点的指针域指向p}//删除当前节点的后继节点，并返回其地址templateclassTNodeT*NodeT::DeleteAfter(void){NodeT*tempPtr=next;//将欲删除的节点地址存储到tempPtr中if(next==NULL)//如果当前节点没有后继节点，则返回NULLreturnNULL;next=tempPtr-next;//使当前节点的指针域指向tempPtr的后继节点returntempPtr;//返回被删除的节点的地址}#endif//NODE_CLASS//Node.h#ifndefNODE_LIBRARY#defineNODE_LIBRARY#includeiostream#includecstdlib#include9_5.husingnamespacestd;//生成结点：创建一个结点，数据成员值为item，指向后继结点的指针值为nextPtrtemplateclassT4NodeT*GetNode(constT&item,NodeT*nextPtr=NULL){NodeT*newNode;//为新结点分配内存空间，然后将item和NextPtr传递给构造函数newNode=newNodeT(item,nextPtr);if(newNode==NULL)//如果分配内存失败，程序中止{cerrMemoryallocationfailure!endl;exit(1);}returnnewNode;}enumAppendNewline{noNewline,addNewline};//输出链表templateclassTvoidPrintList(NodeT*head,AppendNewlineaddnl=noNewline){//currPtr初始指向表头结点，用于遍历链表NodeT*currPtr=head;//输出结点数据，直到链表结束while(currPtr!=NULL){//如果换行标志addl==addNewline，则输出换行符if(addnl==addNewline)coutcurrPtr-dataendl;elsecoutcurrPtr-data;//使currPtr指向下一个结点currPtr=currPtr-NextNode();}}//查找结点//在指针head所指向的链表中查找数据域等于item的结点//找到则返回TRUE及其前趋结点的地址，否则返回FALSEtemplateclassTintFind(NodeT*head,T&item,NodeT*&prevPtr){NodeT*currPtr=head;//从第一个结点开始遍历prevPtr=NULL;//通过循环遍历链表，直到表尾while(currPtr!=NULL){//将item与结点的数据域比较，如果相等，则返回，否则继续处理下一个结点5if(currPtr-data==item)return1;prevPtr=currPtr;//记录下当前结点的地址currPtr=currPtr-NextNode();}return0;//找不到时}//在表头插入结点templateclassTvoidInsertFront(NodeT*&head,Titem){//建立新结点，使其指针域指向原链表头结点head，然后更新headhead=GetNode(item,head);}//在表尾添加结点templateclassTvoidInsertRear(NodeT*&head,constT&item){NodeT*newNode,*currPtr=head;//如果链表为空，则插入在表头if(currPtr==NULL)InsertFront(head,item);else{//寻找指针域为NULL的结点while(currPtr-NextNode()!=NULL)currPtr=currPtr-NextNode();//建立新结点并插入在表尾(在currPtr之后)newNode=GetNode(item);currPtr-InsertAfter(newNode);}}//删除链表的第一个结点templateclassTvoidDeleteFront(NodeT*&head){NodeT*p=head;//取得将被删除的结点的地址if(head!=NULL)//确认链表不空{head=head-NextNode();//将表头指针head移向第二个结点deletep;//删除原第一个结点}}//删除链表中第一个数据域等于key的结点6templateclassTvoidDelete(NodeT*&head,Tkey){//currPtr用于遍历链表，prevPtr跟随其后NodeT*currPtr=head,*prevPtr=NULL;//如果链表为空，则返回if(currPtr==NULL)return;//通过循环遍历链表，直到找到数据域为key的结点，或达到表尾while(currPtr!=NULL&&currPtr-data!=key){//currPtr前行，prevPtr跟随其后prevPtr=currPtr;currPtr=currPtr-NextNode();}//若currPtr!=NULL，则currPtr指向的结点数据域为keyif(currPtr!=NULL){if(prevPtr==NULL)//找到的是链表第一个结点head=head-NextNode();else//如果找到的是第二个以后的结点，调用前趋结点的成员函数删除之prevPtr-DeleteAfter();deletecurrPtr;//释放被删除的结点所占的内存空间}}//在有序链表中插入一个结点templateclassTvoidInsertOrder(NodeT*&head,Titem){//currPtr用于遍历链表，prevPtr跟随其后NodeT*currPtr,*prevPtr,*newNode;//prevPtr==NULL标志着应插入在表头prevPtr=NULL;currPtr=head;//通过循环遍历链表，寻找插入点while(currPtr!=NULL){//如果item当前结点数据，则插入点应在当前结点之前if(itemcurrPtr-data)break;//currPtr前行，prevPtr跟随其后prevPtr=currPtr;currPtr=currPtr-NextNode();7}//完成插入if(prevPtr==NULL)//如果插入点在表头InsertFront(head,item);else{//在prevPtr指向的结点之后插入新结点newNode=GetNode(item);prevPtr-InsertAfter(newNode);}}//清空链表--删除链表中的所有结点templateclassTvoidClearList(NodeT*&head){NodeT*currPtr,*nextPtr;//边遍历边删除结点currPtr=head;while(currPtr!=NULL){//记录下一个结点的地址，删除当前结点nextPtr=currPtr-NextNode();deletecurrPtr;currPtr=nextPtr;//使指针currPtr指向下一个结点}head=NULL;//将头结点置为NULL，标志着链表为空}#endif//NODE_LIBRARY//lab9_1.cpp#includeiostream#include9_5.h#includenode.husingnamespacestd;intmain(){//将表头指针置为NULLNodeint*head=NULL,*prevPtr,*delPtr;inti,key,item;//输入10个整数依次向表头插入for(i=0;i10;i++){cinitem;InsertFront(head,item);8}//输出链表coutList:;PrintList(head,noNewline);coutendl;//输入需要删除的整数cout请输入一个需要删除的整数:;cinkey;//查找并删除结点prevPtr=head;while(Find(head,key,prevPtr)!=NULL){if(prevPtr==NULL)//找到的是链表第一个结点head=head-NextNode();else//如果找到的是第二个以后的结点，调用前趋结点的成员函数删除之delPtr=prevPtr-DeleteAfter();deletedelPtr;}//输出链表coutList:;PrintList(head,noNewline);coutendl;//清空链表ClearList(head);}实验结果如下：2程序二//lab9_2.cpp#includelink.hintmain(){LinkedListintA,B;for(inti=0;i5;i++){A.InsertRear(2*i+1);B.Ins