数据结构实验报告模板.docx
《数据结构实验报告模板.docx》由会员分享，可在线阅读，更多相关《数据结构实验报告模板.docx（26页珍藏版）》请在冰点文库上搜索。
数据结构实验报告模板
《数据结构》
实验报告书
专业班级
网133
学号
139074333
姓名
江文杰
教师
王喜凤
实验一：
用栈判断字符串是否回文
1.实验日期2015年4月11日
2.实验目的为了更好地理解栈的含义和应用
3.实验内容用栈判断字符串是否回文
4.设计思路利用栈的特殊储存方式来判断字符串是否回文；
5.主要程序代码#include
#include
usingnamespacestd;
classzhan
{
public:
chardata;
zhan*next;
zhan（）{next=NULL;}
};
classlinkzhan
{
public:
chara[100];
zhan*top;
linkzhan（）{top=NULL;}
voidcreate1（）;
intcreate2（）;
voidpaiduan（intnum）;
};
voidlinkzhan:
:
create1（）
{
inti=0;
zhan*p;
cout<<"请输入字符串（以#结束标志）"<cin>>a;
while（a[i]!
='#'）
{
p=newzhan;
p->data=a[i];
p->next=top;
top=p;
i++;
}
}
intlinkzhan:
:
create2（）
{
zhan*p;
inti=0,flag=1;
while（top->data!
=NULL）
{
p=newzhan;
p=top;
if（p->data!
=a[i]）
{
flag=0;
break;
}
top=top->next;
deletep;
i++;
}
returnflag;
}
voidmain（）
{
inta;
linkzhanl;
l.create1（）;
a=l.create2（）;
if（a==0）cout<<"该字符串不是回文结构"<elseif（a==1）cout<<"该字符串是回文结构"<}
6.运行与测试
心得或感想：
通过本次试验我从中熟悉掌握了栈和队列的特点，掌握与应用栈和队列的基本操作算法，训练和提高结构化程序设计能力及程序调试能力。
7.
实验二
1.实验日期2015年5月28日
2.实验目的理解树的结构
3.实验内容
1、求二叉树中度为1的结点数
2、求结点在二叉排序树中层次
3、判断此二叉树是否是二叉排序树
4.设计思路利用树的特性以及递归的思想进行解题。
每一个节点都可以看成一棵树。
5.主要程序代码
#include
#include
usingnamespacestd;
classbonde
{
public:
intdata;
bonde*lchild,*rchild;
bonde（）{lchild=NULL;rchild=NULL;}
};
classtree
{
public:
bonde*head;
tree（）{head=NULL;}
~tree（）{deletetree（head）;}
voiddeletetree（bonde*current）;
bonde*createtree（）;
intchazhao（bonde*p）;//求节点为一的节点
intcengci（bonde*p,charnum1）;//节点所在的层次
intpaixu（bonde*p）;//判断是否为二叉排序树；
intheight（bonde*p）;
intMAX（inta,intb）
{if（a>b）returna;
elsereturnb;
}
};
bonde*tree:
:
createtree（）
{
bonde*p;
charch;
cin>>ch;
if（ch=='0'）
p=NULL;
else
{p=newbonde;
p->data=ch;
p->lchild=createtree（）;
p->rchild=createtree（）;
}
head=p;
returnp;
}
voidtree:
:
deletetree（bonde*current）
{
if（current!
=NULL）
{
deletetree（current->lchild）;
deletetree（current->rchild）;
deletecurrent;
}
}
inttree:
:
chazhao（bonde*p）
{
intl,r;
if（p==NULL）return0;
//if（p->lchild==NULL&&p->rchild==NULL）return0;
l=chazhao（p->lchild）;
r=chazhao（p->rchild）;
if（p->lchild==NULL||p->rchild==NULL）
returnl+r+1;
}
inttree:
:
cengci（bonde*p,charnum1）
{
if（p==NULL）
return0;
else
{
if（p->data==num1）
returnMAX（cengci（p->lchild,num1）,cengci（p->rchild,num1））+1;
elsereturn0;
}
}
inttree:
:
paixu（bonde*p）
{
p=head;
if（head>p->lchild||headrchild||p!
=NULL）
return0;
else
{
paixu（p->lchild）;
paixu（p->rchild）;
}
return1;
}
voidmain（）
{intnum;
charnum1;
bonde*p=newbonde;
treel;
cout<<"请输入树:
"<l.head=l.createtree（）;
num=l.chazhao（l.head）;
cout<<"节点为1的"<cout<<"请输入你要查找的数"<cin>>num1;
l.cengci（p,num1）;
cout<<"该节点在第"<l.paixu（l.head）;
cout<<"该二叉树二叉排序树是"<}
6.运行与测试
7.心得或感想递归的步骤很多要仔细，编写是要注意递归与循环的互通之处。
实验三：
1.实验日期2015年6月1日
2.实验目的为了更好地理解各种排序算法和在数据很多的情况下所用的时间和二叉排序数
3.实验内容试编写程序：
从键盘随机输入（或随机产生）20个整数
（1）用顺序查找算法查找给定的某个数
（2）对20个排序后进行折半查找
（3）建立这20个数的二叉排序树，并进行查找。
从键盘输入（或随机数产生）20个数，试用下列算法进行排序
（1）直接插入排序
（2）直接选择排序
（3）快速排序
（4）归并排序
（5）堆排序（可选）
4.设计思路利用不同的排序实现
5.主要程序代码
#include
#include
#include
usingnamespacestd;
classadc
{
public:
intlength;
intdata[100];
intsuiji（）;
intzhijie（intk）;
voidpaixu1（）;//直接插入排序
voidpaixu2（）;//直接选择排序
voidpaixu3（intdata[100],intn）;//快速排序
voidpaixu4（intdata[100],intn）;//归并排序
voidpaixu5（）;//堆排序
intchaozhao（intk）;
intpartition（intdata[100],intlow,inthigh）;
voidqsort（intdata[100],ints,intt）;
voidmsort（intdata[100],ints,intt）;
};
intadc:
:
suiji（）
{
doublerandom（double,double）;
srand（unsigned（time（0）））;
for（inti=1;i<=20;i++）
{
data[i]=int（random（0,100））;
cout<<"No."<"<}
return0;
}
doublerandom（doublestart,doubleend）
{
returnstart+（end-start）*rand（）/（RAND_MAX+1.0）;
}
intadc:
:
zhijie（intk）
{
inti=1;
for（i=1;i<20;i++）
if（data[i]==k）{returni;}
return-1;
}
voidadc:
:
paixu1（）
{
inti,j;
for（i=2;i<=20;i++）
{
data[0]=data[i];
for（j=i-1;data[0]data[j+1]=data[j];
data[j+1]=data[0];
}
for（i=1;i<=20;i++）
cout<<"No."<"<}
intadc:
:
chaozhao（intk）
{
intlow,high,mid;
low=0;
high=20;
while（low<=high）
{
mid=（low+high）/2;
if（k==data[mid]）
returnmid;
elseif（khigh=mid-1;
else
low=mid+1;
}
return-1;
}
voidadc:
:
paixu2（）
{
inti,j;
for（i=1;i<=20;i++）
{
for（j=i+1;j<=20;j++）
{
if（data[j]{data[-1]=data[j];data[j]=data[i];data[i]=data[-1];}
}
}
for（i=1;i<=20;i++）
cout<<"No."<"<}
intadc:
:
partition（intdata[100],intlow,inthigh）
{
if（low==high）returnlow;
data[0]=data[low];
while（low{
while（low=data[0]）high--;
if（lowwhile（lowif（low}
data[low]=data[0];
returnlow;
}
voidadc:
:
qsort（intdata[100],ints,intt）
{
inti;
if（s>=t）return;
i=partition（data,s,t）;
qsort（data,s,i-1）;
qsort（data,i+1,t）;
}
voidadc:
:
paixu3（intdata[100],intn）
{
qsort（data,1,n）;
for（inti=1;i<=20;i++）
cout<<"No."<"<}
voidmer（intdata[100],intdata1[100],ints,intm,intt）
{
inti,j,k;
i=s;j=m+1;k=s;
while（i<=m&&j<=t）
if（data[i]<=data[j]）{data1[k]=data[i];i++;k++;}
else{data1[k]=data[j];j++;k++;}
while（i<=m）data1[k++]=data[i++];
while（j<=t）data1[k++]=data[j++];
}
voidadc:
:
msort（intdata[100],ints,intt）
{
intdata1[100];
intm;
if（s==t）return;
else
{
m=（s+t）/2;
msort（data,s,m）;
msort（data,m+1,t）;
mer（data,data1,s,m,t）;
mer（data1,data,s,t,t）;
}
}
voidadc:
:
paixu4（intdata[100],intn）
{
msort（data,1,n）;
for（inti=1;i<=20;i++）
cout<<"No."<}
intmain（）
{
intk,p;
adca;
a.suiji（）;
cout<<"输入查找的数"<cin>>k;
intl=a.zhijie（k）;
cout<<"在第No:
"<cout<<"排序之后"<a.paixu1（）;
cout<<"输入查找的数"<cin>>p;
cout<<"在第"<cout<<"随机产生20个数"<a.suiji（）;
cout<<"排序之后"<a.paixu3（a.data,20）;
cout<<"随机产生20个数"<a.suiji（）;
cout<<"排序之后"<a.paixu4（a.data,20）;
}
intmain（）
{
time_tst_t=time（NULL）,ed_t;
adca;
a.suiji（）;
a.paixu1（）;
ed_t=time（NULL）;
cout<<（double）（ed_t-st_t）/CLOCKS_PER_SEC<}
intmain（）
{
time_tst_t=time（NULL）,ed_t;
adca;
a.suiji（）;
a.paixu2（）;
ed_t=time（NULL）;
cout<<（double）（ed_t-st_t）/CLOCKS_PER_SEC<}
intmain（）
{
time_tst_t=time（NULL）,ed_t;
adca;
a.suiji（）;
a.paixu3（a.data,n）;
ed_t=time（NULL）;
cout<<（double）（ed_t-st_t）/CLOCKS_PER_SEC<}
intmain（）
{
time_tst_t=time（NULL）,ed_t;
adca;
a.suiji（）;
a.paixu4（a.data,n）;
ed_t=time（NULL）;
cout<<（double）（ed_t-st_t）/CLOCKS_PER_SEC<}
二叉排序树：
#include
usingnamespacestd;
classbinstreenode
{
public:
intdata;
binstreenode*lchild;
binstreenode*rchild;
binstreenode（）{lchild=NULL;rchild=NULL;}
};
classbinstree
{
public:
binstreenode*head;
binstree（）{head=NULL;}
binstreenode*serach（binstreenode*bt,intk,binstreenode*&p）;
voidinsert（binstreenode*&bt,intk）;
voidcreate（intnum）;
};
binstreenode*binstree:
:
serach（binstreenode*bt,intk,binstreenode*&p）
{
binstreenode*q;
q=bt;
while（bt）
{
q=bt;
if（bt->data==k）{p=bt;returnbt;}
elseif（bt->data>k）bt=bt->lchild;
elsebt=bt->rchild;
}
p=q;
returnbt=NULL;
}
voidbinstree:
:
insert（binstreenode*&bt,intk）
{
binstreenode*p=NULL,*q;
q=bt;
if（serach（q,k,p）==NULL）
{
binstreenode*r=newbinstreenode;
r->data=k;r->lchild=r->rchild=NULL;
if（p=NULL）bt=r;
elseif（p->data>k）p->lchild=r;
elsep->rchild=r;
}
}
voidbinstree:
:
create（intnum）
{
inti=1;
intk;
binstreenode*h=newbinstreenode;
while（num!
=0）
{
cout<<"请输入第"<cin>>k;
insert（head,k）;
i++;
num--;
}
}
intmain（）
{
binstreenode*p;
intnum,num1;
cout<<"请输入节点的个数"<cin>>num;
binstreeb;
b.create（num）;
cout<<"请输入要找的数"<cin>>num1;
b.serach（b.head,num1,p）;
return0;
}
6运行与测试
直接插入排序：
直接选择：
快速排序：
归并排序：
直接排序时间：
直接选择排序时间：
快速排序：
100000的：
直接插入排序：
直接选择排序
快速排序：
归并排序：
7.心得或感想通过本次排序，我学会了几种排序算法，有几种用到递归的算法，使我对递归有了一层新的认识。
实验中也有一些困难，通过自己看书和询问同学有了一些提高。
升级会员 