群体类和群体数据.docx
- 文档编号:15730121
- 上传时间:2023-07-07
- 格式:DOCX
- 页数:58
- 大小:148.08KB
群体类和群体数据.docx
《群体类和群体数据.docx》由会员分享,可在线阅读,更多相关《群体类和群体数据.docx(58页珍藏版)》请在冰点文库上搜索。
群体类和群体数据
《面向对象的程序设计》实验报告
(
题目:
群体类和群体数据
学生姓名:
学院:
理学院
系别:
数学系
专业:
信息与计算科学
班级:
任课教师:
二〇一一年十一月
1、实验目的
1、了解节点类的声明和实现,学习其使用方法
2、了解链表类的声明和实现,学习其使用方法
3、了解栈类的声明和实现,学习其使用方法
4、了解队列类的声明和实现,学习其使用方法
5、掌握对数组元素排序的方法
6、掌握对数组元素查找的方法
2、实验内容
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、将直接插入排序、直接选择排序、冒泡排序、顺序查找函数封装到第九章的数组类中,作为成员函数,实现并测试这个类。
3、实验程序及结果
1.程序一
//9_5.h
#ifndefNODE_CLASS
#defineNODE_CLASS
//类定义部分
template
classNode
{
private:
Node
public:
Tdata;//数据域
//构造函数
Node(constT&item,Node
//在本节点之后插入一个同类节点p
voidInsertAfter(Node
//删除本节点的后继节点,并返回其地址
Node
//获取后继节点的地址
Node
};
//类的实现部分
//构造函数,初始化数据和指针成员
template
Node
:
Node(constT&item,Node
data(item),next(ptrnext)
{}
//返回私有的指针成员
template
Node
:
NextNode(void)const
{
returnnext;
}
//在当前节点之后插入一个节点p
template
voidNode
:
InsertAfter(Node
{
p->next=next;//p节点指针域指向当前节点的后继节点
next=p;//当前节点的指针域指向p
}
//删除当前节点的后继节点,并返回其地址
template
Node
:
DeleteAfter(void)
{
Node
if(next==NULL)//如果当前节点没有后继节点,则返回NULL
returnNULL;
next=tempPtr->next;//使当前节点的指针域指向tempPtr的后继节点
returntempPtr;//返回被删除的节点的地址
}
#endif//NODE_CLASS
//Node.h
#ifndefNODE_LIBRARY
#defineNODE_LIBRARY
#include
#include
#include"9_5.h"
usingnamespacestd;
//生成结点:
创建一个结点,数据成员值为item,指向后继结点的指针值为nextPtr
template
Node
{
Node
//为新结点分配内存空间,然后将item和NextPtr传递给构造函数
newNode=newNode
if(newNode==NULL)//如果分配内存失败,程序中止
{
cerr<<"Memoryallocationfailure!
"< exit (1); } returnnewNode; } enumAppendNewline{noNewline,addNewline}; //输出链表 template voidPrintList(Node { //currPtr初始指向表头结点,用于遍历链表 Node //输出结点数据,直到链表结束 while(currPtr! =NULL) { //如果换行标志addl==addNewline,则输出换行符 if(addnl==addNewline) cout< else cout< //使currPtr指向下一个结点 currPtr=currPtr->NextNode(); } } //查找结点 //在指针head所指向的链表中查找数据域等于item的结点 //找到则返回TRUE及其前趋结点的地址,否则返回FALSE template intFind(Node { Node prevPtr=NULL; //通过循环遍历链表,直到表尾 while(currPtr! =NULL) { //将item与结点的数据域比较,如果相等,则返回,否则继续处理下一个结点 if(currPtr->data==item) return1; prevPtr=currPtr;//记录下当前结点的地址 currPtr=currPtr->NextNode(); } return0;//找不到时 } //在表头插入结点 template voidInsertFront(Node { //建立新结点,使其指针域指向原链表头结点head,然后更新head head=GetNode(item,head); } //在表尾添加结点 template voidInsertRear(Node { Node //如果链表为空,则插入在表头 if(currPtr==NULL) InsertFront(head,item); else { //寻找指针域为NULL的结点 while(currPtr->NextNode()! =NULL) currPtr=currPtr->NextNode(); //建立新结点并插入在表尾(在currPtr之后) newNode=GetNode(item); currPtr->InsertAfter(newNode); } } //删除链表的第一个结点 template voidDeleteFront(Node { Node if(head! =NULL)//确认链表不空 { head=head->NextNode();//将表头指针head移向第二个结点 deletep;//删除原第一个结点 } } //删除链表中第一个数据域等于key的结点 template voidDelete(Node { //currPtr用于遍历链表,prevPtr跟随其后 Node //如果链表为空,则返回 if(currPtr==NULL) return; //通过循环遍历链表,直到找到数据域为key的结点,或达到表尾 while(currPtr! =NULL&&currPtr->data! =key) { //currPtr前行,prevPtr跟随其后 prevPtr=currPtr; currPtr=currPtr->NextNode(); } //若currPtr! =NULL,则currPtr指向的结点数据域为key if(currPtr! =NULL) { if(prevPtr==NULL)//找到的是链表第一个结点 head=head->NextNode(); else //如果找到的是第二个以后的结点,调用前趋结点的成员函数删除之 prevPtr->DeleteAfter(); deletecurrPtr;//释放被删除的结点所占的内存空间 } } //在有序链表中插入一个结点 template voidInsertOrder(Node { //currPtr用于遍历链表,prevPtr跟随其后 Node //prevPtr==NULL标志着应插入在表头 prevPtr=NULL; currPtr=head; //通过循环遍历链表,寻找插入点 while(currPtr! =NULL) { //如果item<当前结点数据,则插入点应在当前结点之前 if(item break; //currPtr前行,prevPtr跟随其后 prevPtr=currPtr; currPtr=currPtr->NextNode(); } //完成插入 if(prevPtr==NULL)//如果插入点在表头 InsertFront(head,item); else { //在prevPtr指向的结点之后插入新结点 newNode=GetNode(item); prevPtr->InsertAfter(newNode); } } //清空链表--删除链表中的所有结点 template voidClearList(Node { Node //边遍历边删除结点 currPtr=head; while(currPtr! =NULL) { //记录下一个结点的地址,删除当前结点 nextPtr=currPtr->NextNode(); deletecurrPtr; currPtr=nextPtr;//使指针currPtr指向下一个结点 } head=NULL;//将头结点置为NULL,标志着链表为空 } #endif//NODE_LIBRARY //lab9_1.cpp #include #include"9_5.h" #include"node.h" usingnamespacestd; intmain() { //将表头指针置为NULL Node inti,key,item; //输入10个整数依次向表头插入 for(i=0;i<10;i++) { cin>>item; InsertFront(head,item); } //输出链表 cout<<"List: "; PrintList(head,noNewline); cout< //输入需要删除的整数 cout<<"请输入一个需要删除的整数: "; cin>>key; //查找并删除结点 prevPtr=head; while(Find(head,key,prevPtr)! =NULL) { if(prevPtr==NULL)//找到的是链表第一个结点 head=head->NextNode(); else //如果找到的是第二个以后的结点,调用前趋结点的成员函数删除之 delPtr=prevPtr->DeleteAfter(); deletedelPtr; } //输出链表 cout<<"List: "; PrintList(head,noNewline); cout< //清空链表 ClearList(head); } 实验结果如下: 2程序二 //lab9_2.cpp #include"link.h" intmain() { LinkedList for(inti=0;i<5;i++) { A.InsertRear(2*i+1); B.InsertRear(2*i+2); } A.Reset(); cout<<"链表A的元素为: "; while(! A.EndOfList()) { cout< A.Next(); } cout< B.Reset(); cout<<"链表B的元素为: "; while(! B.EndOfList()) { cout< B.Next(); } cout< cout<<"把B中的元素插入A中..."< B.Reset(); while(! B.EndOfList()) { A.InsertRear(B.Data()); B.Next(); } A.Reset(); cout<<"此时,链表A的元素为: "; while(! A.EndOfList()) { cout< A.Next(); } cout< } //link.h #ifndefLINKEDLIST_CLASS #defineLINKEDLIST_CLASS #include #include usingnamespacestd; #ifndefNULL constintNULL=0; #endif//NULL #include"9-3.h template classLinkedList { private: //数据成员: //表头和表尾指针 Node //记录表当前遍历位置的指针,由插入和删除操作更新 Node //表中的元素个数 intsize; //当前元素在表中的位置序号。 由函数Reset使用 intposition; //函数成员: //生成新节点,数据域为item,指针域为ptrNext Node //释放节点 voidFreeNode(Node //将链表L拷贝到当前表(假设当前表为空)。 //被拷贝构造函数、operator=调用 voidCopyList(constLinkedList public: //构造函数 LinkedList(void); LinkedList(constLinkedList //析构函数 ~LinkedList(void); //重载赋值运算符 LinkedList //检查表的状态 intListSize(void)const;//返回链表中元素个数(size) intListEmpty(void)const;//size等于0时返回TRUE,否则返回FALSE //遍历表的函数 voidReset(intpos=0); //将指针currPtr移动到序号为pos的节点,prevPtr相应移动 //position记录当前节点的序号 voidNext(void);//使prevPtr和currPtr移动到下一个节点 intEndOfList(void)const; //currPtr等于NULL时返回TRUE,否则返回FALSE intCurrentPosition(void)const;//返回数据成员position //插入节点的函数: 插入一个数据域为item的节点 voidInsertFront(constT&item);//在表头插入 voidInsertRear(constT&item);//在表尾添加 voidInsertAt(constT&item);//在当前节点之前插入 voidInsertAfter(constT&item);//在当前节点之后插入 //删除节点,释放节点空间,更新prevPtr、currPtr和size TDeleteFront(void);//删除头节点 voidDeleteAt(void);//删除当前节点 //返回对当前节点成员data的引用(使数据域可以被使用或修改) T&Data(void); //清空链表: 释放所有节点的内存空间。 被析构函数、operator=调用 voidClearList(void); }; template Node : GetNode(constT&item, Node { Node p=newNode if(p==NULL) { cout<<"Memoryallocationfailure! \n"; exit (1); } returnp; } template voidLinkedList : FreeNode(Node { deletep; } //将L复制到当前链表 template voidLinkedList : CopyList(constLinkedList { //P用来遍历L Node intpos; //将L中的每一个元素插入到当前链表最后 while(p! =NULL) { InsertRear(p->data); p=p->NextNode(); } //如果链表空,返回 if(position==-1) return; //在新链表中重新设置prevPtr和currPtr prevPtr=NULL; currPtr=front; for(pos=0;pos! =position;pos++) { prevPtr=currPtr; currPtr=currPtr->NextNode(); } } //建立一个新链表,即: 将有关指针设置为空,size为0,position为-1 template LinkedList : LinkedList(void): front(NULL),rear(NULL), prevPtr(NULL),currPtr(NULL),size(0),position(-1) {} template LinkedList : LinkedList(constLinkedList { front=rear=NULL; prevPtr=currPtr=NULL; size=0; position=-1; CopyList(L); } template voidLinkedList : ClearList(void) { Node 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) { ClearList(); } template LinkedList
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 群体 数据