数据结构B实验报告刘浩Word格式文档下载.docx
《数据结构B实验报告刘浩Word格式文档下载.docx》由会员分享，可在线阅读，更多相关《数据结构B实验报告刘浩Word格式文档下载.docx（18页珍藏版）》请在冰点文库上搜索。
三、主要仪器设备
计算机Win-TC
四、操作方法与实验步骤
#include<
stdio.h>
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--）
=p[i]）
for（j=length;
j>
=i+2;
j--）
p[j]=p[j-1];
p[i+1]=n;
break;
if（flag==0）
=1;
p[0]=n;
}
intmain（）{
intL[10]={1,3,5,7,10,17,21};
intlength=7;
inti,x;
printf（"
InputaLinktable<
astring>
:
\n"
）;
for（i=0;
i<
length;
i++）
{printf（"
%4d"
L[i]）;
\nPleaseinputafigureyouwanttoinsert:
scanf（"
%d"
&
x）;
Insert（L,length,x）;
Afterinsert'
sLinkis:
\n"
x）;
=length;
i++）{
getch（）;
五、实验数据记录和处理
六、实验结果与分析
优点：
可以将任意整数插入到已知表中，简介，明了。
缺点：
插入或删除元素时不方便，需要移动大量的元素，这个程序只能在固定的整数顺序表中插入整数，不方便。
时间复杂度为：
O（n）。
七、讨论、心得
通过这次实验，使我加深了对线性顺序表的存储结构，顺序表的插入，删除等操作的理解和应用，对课本上的内容更加理解透彻，认识到知识运用到实践中是多么的神奇。
虽然实验中遇到一些困难，但在老师的帮助和我们的讨论中已经解决，同时对我的操作能力有了很大的提升。
实验二树
熟悉树的各种表示方法和各种遍历方式，掌握有关算法的实现，了解树在计算机科学及其它工程技术中的应用。
要求仔细阅读并理解下列例题，上机通过，并观察其结果，然后独立完成后面的实习题.
二、实验内容和原理
编写递归算法，计算二叉树中叶子结点的数目。
[输入]：
输入叶子结点的计数m。
一棵二叉树的结点若无子树，则可将其子树看作“.”，输入时，按照前序序列的顺序输入该结点的内容。
对下图，其输入序列为ABD..EH...CF.I..G..。
[输出]:
若为空二叉树，则输出：
Thisisaemptybinarytree.m=0。
若二叉树不空,则输出叶子结点的个数m（m>
0）.
[存储结构]:
采用二叉链表存储。
[算法的基本思想]
在原实验的基础上进行修改即可实现该题的要求：
计数叶子结点的个数。
在例题的基础上在输入一个计数器m,赋予初值m=0，当一个结点的左子树和右子树都为空时，则此结点为叶子结点，m相应的加1.依次遍历二叉树的各个结点即可。
alloc.h>
structnode{
charinfo;
structnode*llink,*rlink;
};
typedefstructnodeNODE;
intm=0;
NODE*creat（）{
charx;
NODE*p;
scanf（"
%c"
printf（"
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）;
if（!
（t->
llink）&
&
!
rlink））
{m++;
main（）
NODE*T;
PLeaseinputatree:
T=creat（）;
T）
Thisisaemptybinarytree.m=0"
run（T）;
TheLeafNoteis%d"
m）;
程序简洁易懂，只是在例题的基础稍微加以修改即可。
耗费时间空间、效率低。
该程序的时间复杂度：
O（n）；
该程序的空间复杂度：
通过这次实验，我对于树结构有了更为清晰的认识。
基于自身我对树这一部分更感兴趣，这些实验让我增长了不少见识。
且在我在程序设计方面经过不断的思考和操作，也有一定的提高。
当然还是不足多一些，有些东西一下子想不到，这也需要在这方面更加的锻炼，多看一些资料，多练练题，学学别人的思路，构思很重要。
实验三图
熟悉图的存储结构，掌握有关算法的实现，了解图在计算机科学及其他工程技术中的应用。
2、实验要求：
采用邻接表存储结构，编写一个求无向图的连通分量个数的算法。
[输入]请输入无向图的顶点数:
4
请顺序输入每条弧头（以空格作为间隔,-1为结束）:
245-1
254-1
452-1
542-1
[输出]无向图G的连通分量的个数
[存储结构]图。
[算法的基本思想]
算法基本思想：
这题主要还是用到深度优先搜索，先从任意一个顶点开始进行深度优先搜索，搜索完后，连通分量个数增1。
然后再从没有遍历过的顶点找一个出来进行深度优先搜索，搜索完后，连通分量个数增1。
一直到所有的顶点都被遍历过。
intn;
structVNode{
intposition;
structVNode*next;
};
structArcNode{
intmark;
structVNode*first;
voidDFS（structArcNode*v,structArcNode*w）{
structVNode*L;
w->
mark=1;
L=w->
first;
while（L!
=NULL）{
if（（v+（L->
position））->
mark==0）{
DFS（v,（v+L->
position））;
L=L->
next;
inti,j,k;
intnum=0;
structArcNode*p;
structVNode*temp;
structVNode*flag;
wuxiangtudingdiannumber:
n）;
while（n<
1）{
errorinputagain:
p=（structArcNode*）malloc（n*sizeof（structArcNode））;
PS:
1.Viisnumberidingdian,weizhiisi-1\n"
2.biankekanweishuangxiang\n"
3.inputV1huweidehu（<
V1,V3>
and<
V1,V2>
）\n"
input:
32-1（inputhead,endwith-1）\n"
for（i=0;
n;
inputV%dweihuweidehu.endwith-1\n"
i+1）;
k）;
if（k==-1）{
p[i].mark=0;
p[i].first=NULL;
else{
temp=（structVNode*）malloc（sizeof（structVNode））;
temp->
position=k;
next=NULL;
p[i].first=temp;
flag=temp;
while（k!
=-1）{
flag->
next=temp;
}
i=0;
while（p[i].mark==0）{
DFS（p,（p+i））;
num++;
while（p[i].mark!
=0&
n）{
i++;
liantongnumber:
%d\n"
num）;
getch（）;
改程序可以自由的输入无向图的定点数，可有求到很多无向图的连通分量。
改程序耗费时间空间、效率低。
我认为图相对于树来说程序更加复杂了，通过这次实验，对于图结构我有了更深的了解，对于连通分量的个数的算法计算过程也有了更清晰的认识，对于课本的概念也更为了解，自己的编程能力依旧不足，还得需要老师同学的指导才能完成作业，还需要继续努力。
实验四查找
1、实验目的：
通过本次实验，掌握查找表上的有关查找方法，并分析时间复杂度。
试将折半查找的算法改写成递归算法。
[输入]：
有序表（2，5，13，17，34，38，78,98）及待查找记录34.
[输出]：
显示34在表中的位置。
[存储结构]：
集合折半查找
将34与顺序表中的第一个元素进行比较，若不相等，用递归算法与剩余元素比较。
intSearch（int*a,intk,intlow,inthight）{
intmid;
if（low>
hight）{
return0;
mid=（low+hight）/2;
if（a[mid]==k）{
return（mid+1）;
elseif（a[mid]>
k）{
returnSearch（a,k,low,mid-1）;
returnSearch（a,k,mid+1,hight）;
int*p;
inti,n,key,position;
datanumberis:
p=（int*）malloc（n*sizeof（int））;
inputalinksmalltobig:
p[0]）;
for（i=1;
p[i]）;
while（p[i]<
p[i-1]）{
serch'
snumber:
key）;
position=Search（p,key,0,n-1）;
if（position==0）{
Nothisdata!
thenumberis%dposition!
position）;
效率高，速度快，很方便。
只适用于有序表，不适用于无序表,不是很全面。
查找成功的平均查找长度为ASL=1/8（1*1+2*2+3*4+5*1）=2.75。
O（8）。
通过这次实验，我对于查找有了进一步的认识，原来二叉树也可以用来进行查找，二叉排序树是如此的有用，知识间是互相包容的，以后得多多复习前面的知识，知识间互相联系的紧，也发现了折半查找在有序表中的高效率，实验之后，对于各种查找方法也有了更多的看法以及各种查找方法的对比。
这次实验对我学习查找这一章有着深刻的影响。
实验五内排序
通过本次实验，掌握线性表的排序方法，并分析时间复杂度。
对N个关键字去整数的记录进行整序，以使所有关键字为非负数的记录排在关键字为负数的记录之前，要求使用最少的附加空间，且算法的时间复杂度为O（N）
[输入]:
待排序记录个数，各关键字的值。
关键字从正负分开，正数在前，负数在后。
[存储结构]:
待排序记录顺序存储。
快速排序算法每次任取一个记录的关键字为标准，将其余记录分为两组将，N个关键字去整数的记录进行整序，以使所有关键字为非负数的记录排在关键字为负数的记录之前。
voidSort（int*a,intm）{
inti=0;
intj=m-1;
inttemp;
while（i<
=j）{
m&
a[i]>
=0）{
while（j>
a[j]<
0）{
j--;
if（i<
j）{
temp=a[i];
a[i]=a[j];
a[j]=temp;
intn,i;
int*p;
datanumber（>
1）:
2）{
inputlist:
Sort（p,n）;
aftercompositorlist:
%-4d"
p[i]）;
可以任意输入序列。
只能将正负排开，但不能进行排序。
O（7）。
通过本次实验，掌握了线性表的排序方法，采用顺序存储的方式进行输入数据。
根据图中数据可以清晰明了的看出原本无顺序的数的有序排列，让人一目了然。
升级会员 