实验4 群体类和群体数据 吕恩在

（二〇一五年十二月《面向对象程序设计》实验报告学校代码：学号：题目：群体类和群体数据学生姓名：学院：系别：专业：班级：任课教师：群体类和群体数据一、实验目的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.（选做）声明course（课程）类，有属性：课程名charname[21]、成绩shortscore；在实验七的student类中增加属性；所修课程course，为课程类对象的链表。在测试程序中测试这个类，学生类与课程类关系如图5.将直接插入排序、直接选择排序、冒泡排序、顺序查找函数封装到第九章的数组类中，作为成员函数，实现并测试这个类三、实验内容：1.//9-5.h#ifndefNODE_CLASS#defineNODE_CLASStemplateclassTclassNode{private:NodeT*next;//指向后继节点的指针public:Tdata;//数据域Node(constT&item,NodeT*ptrnext=NULL);voidInsertAfter(NodeT*p);NodeT*DeleteAfter(void);NodeT*NextNode(void)const;};templateclassTNodeT::Node(constT&item,NodeT*ptrnext):data(item),next(ptrnext){}templateclassTNodeT*NodeT::NextNode(void)const{returnnext;}templateclassTvoidNodeT::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;templateclassTNodeT*GetNode(constT&item,NodeT*nextPtr=NULL){NodeT*newNode;newNode=newNodeT(item,nextPtr);if(newNode==NULL)//如果分配内存失败，程序中止{cerrMemoryallocationfailure!endl;exit(1);}returnnewNode;}enumAppendNewline{noNewline,addNewline};templateclassTvoidPrintList(NodeT*head,AppendNewlineaddnl=noNewline){NodeT*currPtr=head;while(currPtr!=NULL){if(addnl==addNewline)coutcurrPtr-dataendl;elsecoutcurrPtr-data;currPtr=currPtr-NextNode();}}templateclassTintFind(NodeT*head,T&item,NodeT*&prevPtr){NodeT*currPtr=head;//从第一个结点开始遍历prevPtr=NULL;while(currPtr!=NULL){if(currPtr-data==item)return1;prevPtr=currPtr;//记录下当前结点的地址currPtr=currPtr-NextNode();}return0;//找不到时}templateclassTvoidInsertFront(NodeT*&head,Titem){head=GetNode(item,head);}templateclassTvoidInsertRear(NodeT*&head,constT&item){NodeT*newNode,*currPtr=head;if(currPtr==NULL)InsertFront(head,item);else{while(currPtr-NextNode()!=NULL)currPtr=currPtr-NextNode();newNode=GetNode(item);currPtr-InsertAfter(newNode);}}templateclassTvoidDeleteFront(NodeT*&head){NodeT*p=head;//取得将被删除的结点的地址if(head!=NULL)//确认链表不空{head=head-NextNode();//将表头指针head移向第二个结点deletep;//删除原第一个结点}}templateclassTvoidDelete(NodeT*&head,Tkey){NodeT*currPtr=head,*prevPtr=NULL;if(currPtr==NULL)return;while(currPtr!=NULL&&currPtr-data!=key){//currPtr前行，prevPtr跟随其后prevPtr=currPtr;currPtr=currPtr-NextNode();}if(currPtr!=NULL){if(prevPtr==NULL)//找到的是链表第一个结点head=head-NextNode();elseprevPtr-DeleteAfter();deletecurrPtr;//释放被删除的结点所占的内存空间}}templateclassTvoidInsertOrder(NodeT*&head,Titem){NodeT*currPtr,*prevPtr,*newNode;prevPtr=NULL;currPtr=head;while(currPtr!=NULL){if(itemcurrPtr-data)break;//currPtr前行，prevPtr跟随其后prevPtr=currPtr;currPtr=currPtr-NextNode();}if(prevPtr==NULL)//如果插入点在表头InsertFront(head,item);else{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(){Nodeint*head=NULL,*prevPtr,*delPtr;inti,key,item;for(i=0;i10;i++){coutpleaseinputi+1numberToinsertaheader:endl;cinitem;InsertFront(head,item);}coutList:;PrintList(head,noNewline);coutendl;cout请输入一个需要删除的整数:;cinkey;prevPtr=head;while(Find(head,key,prevPtr)!=NULL){if(prevPtr==NULL)//找到的是链表第一个结点head=head-NextNode();elsedelPtr=prevPtr-DeleteAfter();deletedelPtr;}coutList:;PrintList(head,noNewline);coutendl;ClearList(head);}运行结果：pleaseinput1numberToinsertaheader:1pleaseinput2numberToinsertaheader:2pleaseinput3numberToinsertaheader:3pleaseinput4numberToinsertaheader:4pleaseinput5numberToinsertaheader:5pleaseinput6numberToinsertaheader:6pleaseinput7numberToinsertaheader:7pleaseinput8numberToinsertaheader:8pleaseinput9numberToinsertaheader:9pleaseinput10numberToinsertaheader:10List:10987654321请输入一个需要删除的整数:2List:10987654312.//link.h#ifndefLINKEDLIST_CLASS#defineLINKEDLIST_CLASS#includeiostream#includecstdlibusingnamespacestd;#ifndefNULLconstintNULL=0;#endif//NULL#include9_5.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;//返回链表中元素个数（size）int