当前位置：文档库 › 实验报告：群体类和群体数据

实验报告：群体类和群体数据

（二〇

一五年

十一月

一、实

验目的

1、了解节

点类的声明和

实现，学习

其使

用方法 2、了解链表类的声明和实现，学习其使用方法

3、了解栈类的声明和实现，学习其使用方法

4、了解队列类的声明和实现，学习其使用方法

5、掌握对数组元素排序的方法

6、掌握对数组元素查找的方法

二、实验内容

1、编写程序实现例9-5的节点类，并编写测试程序，实现链表的基本操作。

2、编写程序实现例9-6的链表类，在测试程序中声明两个整型链表A 和B ，分别插入5元素，然后

把B 中的元素加入A 的尾部。

3、编写程序，用链表实现队列（或栈），在测试程序中声明一个整型队列（或栈）对象，插入5

个整数，压入队列（或栈），再依次取出并显示出来。

4、（选做）声明course （课程）类，有属性：课程名charname[21]、成绩shortscore ；在实验七

的student 类中增加属性；所修课程course ，为课程类对象的链表。在测试程序中测试这个类，学

生类与课程类关系如图

5、将直接插入排序、直接选择排序、冒泡排序、顺序查找函数封装到第九章的数组类中，作为成

员函数，实现并测试这个类。

三、实验程序

1、

#ifndefNODE_CLASS

#defineNODE_CLASS

《面向对象程序设计》实验报告学校代码：10128

学号：60

题目：群体类和群体数据学生姓名：燕飞学院：理学院系别：数学系专业：信息与计算科学班级：信计12-2 任课教师：侯睿

template

classNode

{

private:

Node*next;

public:

Tdata;

Node(constT&item,Node*ptrnext=NULL); voidInsertAfter(Node*p);

Node*DeleteAfter(void);

Node*NextNode(void)const;

};

template

Node::Node(constT&item,Node*ptrnext): data(item),next(ptrnext)

{}

template

Node*Node::NextNode(void)const

{

returnnext;

}

template

{

p->next=next;

next=p;

}

template

Node*Node::DeleteAfter(void)

{

Node*tempPtr=next;

if(next==NULL)

returnNULL;

next=tempPtr->next;

returntempPtr;

}

#endif

#ifndefNODE_LIBRARY

#defineNODE_LIBRARY

#include

#include""

usingnamespacestd;

template

Node*GetNode(constT&item,Node*nextPtr=NULL)

Node*newNode;

newNode=newNode(item,nextPtr);

if(newNode==NULL)

{

cerr<<"Memoryallocationfailure!"<

exit(1);

}

returnnewNode;

}

enumAppendNewline{noNewline,addNewline};

template

voidPrintList(Node*head,AppendNewlineaddnl=noNewline) {

Node*currPtr=head;

while(currPtr!=NULL)

{

if(addnl==addNewline)

cout<data<

else

cout<data<<"";

currPtr=currPtr->NextNode();

}

template

intFind(Node*head,T&item,Node*&prevPtr) {

Node*currPtr=head;

prevPtr=NULL;

while(currPtr!=NULL)

{

if(currPtr->data==item)

return1;

prevPtr=currPtr;

currPtr=currPtr->NextNode();

}

return0;

}

template

voidInsertFront(Node*&head,Titem)

{

head=GetNode(item,head);

}

template

voidInsertRear(Node*&head,constT&item) {

if(currPtr==NULL)

InsertFront(head,item);

else

{

while(currPtr->NextNode()!=NULL) currPtr=currPtr->NextNode(); newNode=GetNode(item);

currPtr->InsertAfter(newNode);

}

template

voidDeleteFront(Node*&head)

{

Node*p=head;

if(head!=NULL)

{

head=head->NextNode();

deletep;

}

template

voidDelete(Node*&head,Tkey)

Node*currPtr=head,*prevPtr=NULL;

if(currPtr==NULL)

return;

while(currPtr!=NULL&&currPtr->data!=key) {

prevPtr=currPtr;

currPtr=currPtr->NextNode();

}

if(currPtr!=NULL)

{

if(prevPtr==NULL)

head=head->NextNode();

else

prevPtr->DeleteAfter();

deletecurrPtr;

}

template

voidInsertOrder(Node*&head,Titem) {

Node*currPtr,*prevPtr,*newNode; prevPtr=NULL;

while(currPtr!=NULL)

{

if(itemdata) break;

prevPtr=currPtr;

currPtr=currPtr->NextNode(); }

if(prevPtr==NULL)

InsertFront(head,item);

else

{

newNode=GetNode(item);

prevPtr->InsertAfter(newNode); }

}

template

voidClearList(Node*&head) {

Node*currPtr,*nextPtr; currPtr=head;

while(currPtr!=NULL)

{

deletecurrPtr;

currPtr=nextPtr;

}

head=NULL;

}

#endif

#include

#include""

usingnamespacestd;

intmain()

{

Node*head=NULL,*prevPtr,*delPtr; inti,key,item;

for(i=0;i<10;i++)

{

cin>>item;

InsertFront(head,item);

}

cout<<"List:";

PrintList(head,noNewline);

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、

#include""

intmain()

{

LinkedListA,B;

for(inti=0;i<5;i++)

{

(2*i+2);

}

();

cout<<"链表A的元素为：";

while(!())

{

cout<<()<<"";

();

}

cout<

();

cout<<"链表B的元素为：";

while(!())

{

cout<<()<<"";

();

}

cout<

cout<<"把B中的元素插入A中..."<

();

while(!())

{

}

();

cout<<"此时，链表A的元素为：";

while(!())

{

cout<<()<<"";

();

}

cout<

}

#ifndefLINKEDLIST_CLASS

#defineLINKEDLIST_CLASS

#include

usingnamespacestd;

#ifndefNULL

constintNULL=0;

#endif接插入排序2.直接选择排序3.冒泡排序：";

cin>>SortType;

switch(SortType)

{

break;

case2:

();

break;

case3:

();

break;

default:

cout<<"输入错误，程序退出!";

exit(0);

}

cout<<"排序后的数组为："<

for(i=0;i<10;i++)

cout<

cout<<"请输入待查找的数字：";

cin>>SearchNum;

k=(SearchNum);

if(k<0)

cout<<"没有找到数字"<

}

#ifndefARRAY1_CLASS

#defineARRAY1_CLASS

#include

usingnamespacestd;

#ifndefNULL

constintNULL=0;

#endif

enumErrorType

{invalidArraySize,memoryAllocationError,indexOutOfRange}; char*errorMsg[]=

{

"Invalidarraysize","Memoryallocationerror", "Invalidindex:"

};

template

classArray

{

private:

T*alist;

intsize;

public:

Array(intsz=50);

Array(constArray&A);

~Array(void);

Array&operator=(constArray&rhs);

T&operator[](inti);

operatorT*(void)const;

intListSize(void)const;

voidResize(intsz);

voidInsertionSort();

voidSelectionSort();

voidBubbleSort();

intSeqSearch(Tkey);

};

template

voidArray::Error(ErrorTypeerror,intbadIndex)const {

cerr<

if(error==indexOutOfRange)

cerr<

exit(1);

template

Array::Array(intsz)

{

if(sz<=0)

Error(invalidArraySize);

size=sz;

alist=newT[size];

if(alist==NULL)

Error(memoryAllocationError);

}

template

Array::~Array(void)

{

delete[]alist;

}

template

Array::Array(constArray&X) {

intn=;

size=n;

alist=newT[n];

if(alist==NULL)

T*srcptr=;

T*destptr=alist;

while(n--)

*destptr++=*srcptr++;

}

template

Array&Array::operator=(constArray&rhs) {

intn=;

if(size!=n)

{

delete[]alist;

alist=newT[n];

if(alist==NULL)

Error(memoryAllocationError);

size=n;

}

T*destptr=alist;

T*srcptr=;

while(n--)

*destptr++=*srcptr++;

return*this;

template

T&Array::operator[](intn) {

if(n<0||n>size-1)

Error(indexOutOfRange,n); returnalist[n];

}

template

Array::operatorT*(void)const {

returnalist;

}

template

intArray::ListSize(void)const {

returnsize;

}

template

voidArray::Resize(intsz)

{

if(sz<=0)

Error(invalidArraySize);

return;

T*newlist=newT[sz];

if(newlist==NULL)

Error(memoryAllocationError); intn=(sz<=size)?sz:size;

T*srcptr=alist;

T*destptr=newlist;

while(n--)

*destptr++=*srcptr++;

delete[]alist;

alist=newlist;

size=sz;

}

template

voidArray::InsertionSort() {

inti,j;

Ttemp;

for(i=1;i

{

j=i;

temp=alist[i];

{

alist[j]=alist[j-1];

j--;

}

alist[j]=temp;

}

template

voidArray::SelectionSort()

{

intsmallIndex;

inti,j;

for(i=0;i

{

smallIndex=i;

for(j=i+1;j

if(alist[j]

smallIndex=j;

Swap(alist[i],alist[smallIndex]);

}

template