理工大学数据结构实验报告Word文件下载.docx
《理工大学数据结构实验报告Word文件下载.docx》由会员分享，可在线阅读，更多相关《理工大学数据结构实验报告Word文件下载.docx（20页珍藏版）》请在冰点文库上搜索。
stdio.h>
#include<
stdlib.h>
voidInsert（int*p,intlength,intn）{
inti,j;
intflag=0;
if（n>
=p[length-1]）{
p[length]=n;
flag=1;
}
else{
for（i=length-2;
i>
=0;
i--）{
if（n>
=p[i]）{
for（j=length;
j>
=i+2;
j--）{
p[j]=p[j-1];
}
p[i+1]=n;
flag=1;
break；
}
if（flag==0）{
for（j=length;
=1;
p[j]=p[j-1];
}
p[0]=n；
}
intmain（）{
intL[10]={2,5,8,11,14,17,20};
intlength=7;
inti,x;
printf（"
charuqiandeshunxubiaowei：
\n"
）;
for（i=0;
i<
length;
i++）{
printf（"
%4d"
L[i]）;
}
\nqingshuruyaocharudezhengshu：
scanf（"
%d"
&
x）;
Insert（L,length,x）;
charu%dhoudeshunxubiaowei：
x）;
=length;
system（"
pause"
return0;
实验结果
实验心得与体会
本次实验是数据结构的第一个实验，虽然已经学过C语言，也用过vc++6.0，但是实验中还是不可避免的遇到许多问题，不过经过自己上网了解和同学与老师的帮助，问题都得到了解决，其中在运行代码后出现了“预编译头文件找不到”的错误，多次运行都出现这种错误，于是上网查询后，才知道是头文件错误，加上“#include<
”之后程序顺利运行。
通过本实验我对线性表有了更深的的认识，弄懂了一些上课时没能理解的知识点，对我以后的学习有很大的帮助。
实验二树
熟悉树的各种表示方法和各种遍历方式，掌握有关算法的实现，了解树在计算机科学及其它工程技术中的应用。
1．编写递归算法，计算二叉树中叶子结点的数目。
按先序序列输入二叉树ABD..EH…CF.I..G..
二叉树叶子节点数目为4
采用二叉链表存储
求二叉树中叶子结点个数，即求二叉树的所有结点中左、右子树均为空的结点个数之和。
可以将此问题转化为遍历问题，在遍历中“访问一个结点”时判断该结点是不是叶子，若是则将计数器累加。
实验代码：
malloc.h>
intcount=0;
structnode{
charinfo;
structnode*llink,*rlink;
};
typedefstructnodeNODE;
NODE*creat（）{
charx;
NODE*p;
%c"
if（x!
='
.'
）{
p=（NODE*）malloc（sizeof（NODE））;
p->
info=x;
llink=creat（）;
rlink=creat（）;
p=NULL;
returnp;
voidrun（NODE*t）{
if（t）{
run（t->
llink）;
rlink）;
t->
info）;
if（（（t->
llink）==NULL）&
&
（（t->
rlink）==NULL））
count++;
voidmain（）
{
NODE*T;
请输入一个树:
T=creat（）;
if（!
T）
这是一个空二叉树"
else
{printf（"
遍历后的结果:
\n"
run（T）;
\n总共有叶子节点数%d"
count）;
运行结果
本次实验是关于树的相关练习，树这一节在本书中算是一个重点内容，不过它并不是一个难点，相比其他单元的内容来说已经算是简单的了，所以本次实验相比前几次实验容易同时也顺利多了。
源代码一次就运行成功。
通过本次实验我对树有了更深的了解，对我以后的学习有很大的帮助。
实验三图
熟悉图的存储结构，掌握有关算法的实现，了解图在计算机科学及其他工程技术中的应用。
1．试基于图的深度优先搜索策略编写一程序，判别以邻接表方式存储的有向图中是否存在有顶点Vi到Vj顶点的路径（i≠j）。
图的顶点个数N，以及以V1、V2、V3、V4为弧尾的所有的弧，并以-1结束。
还有你要判断是否连通的两个顶点。
若A到B无路径，则输出“不是连通的”,否则输出A到B路径上各顶点。
图采用邻接矩阵的方式存储。
算法的基本思想：
采用深度优先搜索的方法，从顶点A开始，依次访问与A邻接的顶点VA1,VA2,...,VAK,访问遍之后,若没有访问B，则继续访问与VA1邻接的顶点VA11,VA12,...,VA1M，再访问与VA2邻接顶点...，如此下去，直至找到B，最先到达B点的路径，一定是边数最少的路径。
在访问顶点过程中，每次把当前顶点的序号作为与其邻接的未访问的顶点的前驱顶点记录下来。
程序代码：
#include<
Windows.h>
intn;
typedefstructarcNode
intposition;
structarcNode*next;
}ArcNode,*ArcNode_;
typedefstructvNode
intmark;
//在程序中用来标识是否被访问过
ArcNode*first;
//存储连接到该结点的第一个弧信息的地址
}VNode,*VNode_;
//函数声明部分
VNode_Structure（）;
//构造一个图
voidDFS（VNode_Chart,intt）;
voidInitialize（VNode_Chart）;
voidEnd（VNode_Chart）;
inti=0;
intcount=0;
intw,v;
VNode_Chart=Structure（）;
//创建图
请输入要查询的顶点w,v\n"
%d,%d"
&
w,&
v）;
DFS（Chart,w-1）;
if（Chart[v-1].mark）
{
顶点V%d，与顶点V%d之间连通。
"
w,v）;
顶点顶点V%d，与顶点V%d之间不连通。
\n\n"
End（Chart）;
//构造一个图的过程
VNode_Structure（）
VNode_Chart;
inti,j,k;
ArcNode_p,q;
下面进行构造图的过程，请按照提示输入信息完成构造图的过程！
\n请输入要构造的图的顶点总数.\n"
n）;
//将用户输入的总的顶点数保存
//对输入数据进行判断
while（n<
1）
录入的数据有误！
请重新输入。
scanf（"
Chart=（VNode_）malloc（n*sizeof（VNode））;
Initialize（Chart）;
//初始化申请出来的空间
请按照下面的提示构造图。
i<
n;
++i）
请输入指向'
V%d'
顶点的所有顶点，结束请输入0\n"
i+1）;
k）;
if（k!
=0）
{
q=（ArcNode_）malloc（sizeof（ArcNode））;
q->
position=k-1;
（Chart+i）->
first=q;
p=q;
scanf（"
while（k!
{
q=（ArcNode_）malloc（sizeof（ArcNode））;
q->
p->
next=q;
p=q;
scanf（"
p->
next=NULL;
else
Chart[i].first=NULL;
returnChart;
voidDFS（VNode_Chart,intt）
ArcNode_q;
if（Chart[t].mark==0）
Chart[t].mark=1;
for（q=Chart[t].first;
q!
=NULL;
q=q->
next）
DFS（Chart,q->
position）;
voidInitialize（VNode_Chart）
inti;
i<
n;
i++）
（Chart+i）->
mark=0;
voidEnd（VNode_Chart）
i++）
p=Chart[i].first;
while（p!
=NULL）
q=p;
p=p->
next;
free（q）;
}
free（Chart）;
这次实验让我对图有了更加深厚的了解，实验中依然遇到了许多问题，实验代码明明写对了但是运行不能通过，在网上查询后调整了vc++6.0的相关设置，最后程序顺利运行。
实验中，粗心大意的情况已然发生了，例如程序中的“{}”,经常写了前一半而忘写后一半。
在以后的实验中我一定要细心认真，不能再出现这种情况。
实验四查找
通过本次实验，掌握查找表上的有关查找方法，并分析时间复杂度。
1.试将折半查找的算法改写成递归算法。
输入有序表
要查找元素的位置
数组存储
将n个元素分成个数大致相同的两半，取a[n/2]与欲查找的x作比较，如果x=a[n/2]则找到x，算法终止。
如果x<
a[n/2]，则我们只要在数组a的左半部继续搜索x（这里假设数组元素呈升序排列）。
如果x>
a[n/2]，则我们只要在数组a的右半部继续搜索x。
递归调用这个算法。
#defineMAXNUM20
typedefstructsSTable
inta[MAXNUM+1];
intlenth;
}SSTable,*SSTable_;
voidStructure（SSTable_ST）;
intBinsearch（SSTableST,intkey,intlow,inthigh）;
intt;
SSTableST;
Structure（&
ST）;
请输入要查找的数"
t）;
if（Binsearch（ST,t,1,ST.lenth））
查找成功！
！
voidStructure（SSTable_ST）
以下为构造一个数组的过程，用0作为结束输入的标识。
\
\n由于程序限定输入数组长度不能超过%d个并且数组元素从第1个开始。
MAXNUM）;
ST->
lenth=0;
while（t!
ST->
a[ST->
lenth+1]=t;
++ST->
lenth;
intBinsearch（SSTableST,intkey,intlow,inthigh）
intmid;
mid=（low+high）/2;
if（low<
=high）
if（key==ST.a[mid]）returnmid;
elseif（key<
ST.a[mid]）i=Binsearch（ST,key,low,mid-1）;
elsei=Binsearch（ST,key,mid+1,high）;
returni;
运行结果：
实验心得与体会：
本次实验是关于查找的，查找在数据结构中具有重要地位，内容繁多，而且不易理解，在实验中我就遇到了许多问题，例如规定数组的长度如何辨别已经输入完毕等，但是经过上网查阅相关文档最终解决了问题，达到了实验的要求，并将源代码运行成功，由于实验室机器的问题，当实验进行一半时电脑突然死机然后重启，导致写到一半的程序全没了，这也告诉了我们要做好代码的备份，以防出现意外。
实验五内排序
通过本次实验，掌握线性表的排序方法，并分析时间复杂度。
1.对N个关键字取整数的记录进行整序，以使所有关键字为非负数的记录排在关键字为负数的记录之前，要求使用最少的附加空间，且算法的时间复杂度为O（N）。
输入：
一组数据。
非负数排在负数之前。
顺序存储。
由于问题仅要求非负数排在负数之前，所以提取非负数插在前面即可。
#defineMAX100
inta[MAX];
inti,j,n;
请输入记录的总个数。
请输入各记录（仅输入关键字）\n"
for（i=1;
=n;
a[i]）;
a[0]=a[1];
i=1;
j=n;
while（i<
j）
while（i<
j&
a[j]<
=0）--j;
a[i]=a[j];
a[i]>
=0）++i;
a[j]=a[i];
a[i]=a[0];
=n;
a[i]）;
本次实验是数据结构的最后一个实验，多次的实验已经让我积累了许多编程的经验与数据结构的思想，这对我以后的学习有很大的帮助，培养数据结构思想也正是我们这门课程的目的和要求，规范化的编程对于以后的工作更是有巨大的用处。
总结前几次实验的失败和教训本次实验较为顺利，通过编程是我对内部排序有了更深的理解和认识。
升级会员 