参考资料河南自考数据结构实验报告文档格式.docx
《参考资料河南自考数据结构实验报告文档格式.docx》由会员分享，可在线阅读，更多相关《参考资料河南自考数据结构实验报告文档格式.docx（20页珍藏版）》请在冰点文库上搜索。
orange（在第五个节点以后插入）
删除时：
blue
（一）、实验目的:
（二）、程序清单
/*******************LinkList******************************/
#include"
"
#defineN5
typedefstructnode{
chardata[8];
structnode*next;
}Listnode;
/*******函数挪用说明*******/
Listnode*CreateL（）;
Listnode*Getnode（）;
voidTraveL（）;
voidInsertL（）;
voidDeleteL（）;
/*******************主函数************************/
main（）
{intk,j;
Listnode*head,*p;
printf（“成立单链表：
\n”）;
head=CreateL（）;
do{
printf（”0.退出\n”）;
printf（"
1.遍历单链表\n"
）;
2.单链表的插入\n"
3.单链表的删除\n"
请选择：
scanf（“%d”,&
k）;
switch（k）
{case0:
exit（0）;
case1:
TravelL（head）;
break;
case2:
InsertL（head）;
break;
case3:
DeleteL（head）;
}
}while
（1）;
/*******************成立********************/
Listnode*CreateL（）
{intj;
Listnode*head,*s,*r;
head=（Listnode*）malloc（sizeof（Listnode））;
r=head;
r->
next=NULL;
printf（“\n请输入%d个字符串：
”，N）;
for（j=1;
j<
=N;
j++）
{printf（“字符串%d:
“,j）;
s=（Listnode*）malloc（sizeof（Listnode））;
scanf（“%s”,s->
data）;
next=s;
r=s;
}
returnhead;
/*******************遍历*******************/
voidTraveL（Listnode*head）
{Listnode*p;
p=head->
next;
;
while（p）
{printf（"
%s"
p->
p=p->
/********************插入******************/
voidInsertL（Listnode*head）
{charch[8];
intk;
Listnode*p,*s;
printf（“\n输入要插入的字符串：
”）;
scnaf（“%s”,ch）;
printf（“\n输入要插入的位置：
p=Getnode（head,k-1）;
if（p==NULL）
positionerror!
s=（Listnode*）malloc（sizeof（Listnode））;
strcpy（s->
data,ch）;
s->
next=p->
p->
/********************删除******************/
voidDeleteL（Listnode*head）
Listnode*p,*q;
printf（“\n输入要删除的字符串：
printf（“\n查找它之前的位置：
p=head;
whiel（p->
next）
{q=p->
if（!
strcmp（q->
data,ch））break;
p=q;
if（p->
next）{p->
next=q->
free（q）;
elseprintf（“notfound”）;
/******************查找*****************/
Listnode*Getnode（Listnode*head,inti）
Listnode*p;
p=head;
j=0;
while（p->
next&
&
i）
{p=p->
j++;
if（i==j）
returnp;
else
returnNULL;
/*************************************************************/
（三）、实验中显现的问题及解决的方式
要细心查看。
实验二图的遍历操作
采纳邻接矩阵存储方式的无向图的深度优先遍历和广度优先遍历算法的实现。
三、实验原理：
图的大体运算
四、实验设备:
本实验在586以上的微机上进行，运行环境为TurboC.
●成立一个极点信息是字符的无向图；
●输出深度优先遍历的结果；
●输出广度优先遍历的结果;
先输入极点数和边数，然后输入极点信息和每条边对应的两个极点的序号。
测试数据：
68
ABCDEF
11
03
4
12
14
23
34
45
45
六、选做内容：
编写一个途径遍历算法，求出从北京到哈尔滨途中不通过郑州的所有简单途径，测试数据为教科书中图，起点为北京。
七、图的遍历操作
（一）、实验目的
#include<
>
#defineMaxVerNum50
structedgenode
{
intendver;
intinform;
edgenode*edgenext;
};
structvexnode
charvertex;
edgenode*edgelink;
structGraph
vexnodeadjlists[MaxVerNum];
intvexnum;
intarcnum;
ertex;
G->
adjlists[i].edgelink=NULL;
cout<
<
开始输入边表信息:
endl;
for（k=0;
k<
G->
arcnum;
k++）
{
请输入边<
Vi,Vj>
对应的极点:
cin>
i>
j;
p1=newedgenode;
p1->
endver=j;
edgenext=G->
adjlists[i].edgelink;
adjlists[i].edgelink=p1;
p2=newedgenode;
p2->
endver=i;
adjlists[j].edgelink;
adjlists[j].edgelink=p2;
ertex<
"
visit[i]=1;
edgenode*p=newedgenode;
p=G->
if（G->
adjlists[i].edgelink&
!
visit[p->
endver]）
{
DFS（G,p->
endver,visit）;
voidDFStraversal（Graph*G,charc）ertex==c）ertex<
visit[e]=1;
edgenode*p=newedgenode;
adjlists[e].edgelink;
if（p）
intm=p->
endver;
if（m==0）
EnQueue（Q,m）;
while（visit[m]==0）
edgenext;
if（p==NULL）
m=p->
voidBFStraversal（Graph*G,charc）
该图的广度优先遍历结果为:
intvisited[MaxVerNum];
for（inti=0;
i<
vexnum;
i++）
visited[i]=0;
intm;
for（i=0;
if（G->
adjlists[i].vertex==c）
m=i;
BFS（G,i,visited）;
五、实验内容:
●随机输入假设干整数成立一个线性表，查找指定节点的位置；
●按升序输入假设干整数成立一个有序表查找指定节点的位置；
●随机输入假设干整数成立一个二叉排序树，查找指定节点的位置;
先输入表中结点的个数N，然后输入N整数。
（略）
六、数据查找
把握在线性表上进行顺序查找、二分查找的算法实现和在二叉排序树上的查找算法的实现。
intTSearch（SSTableST,intkey）{
ey）returnmid;
ey）high=mid-1;
ey=key;
printf（"
请输入第%d个数,大于%d\n"
n,[i-1].key）;
scanf（"
%d"
&
key）;
=i;
}printf（"
请输入要查的数:
\n"
postion=Search_Bin（T,key）;
此数的位置是：
%d\n"
postion）;
（三）、实验中显现的问题及解决方式：
随机输入假设干整数成立一个二叉排序树，查找指定节点的位置。
二叉树查找代码容易犯错。
实验四排序
二、实验目的：
把握对一批记录进行排序的各类算法，包括直接插入排序法、冒泡排序法、直接选择排序法和快速排序法。
排序的方式。
●随机输入假设干整数，按直接插入排序法排序并输出；
●输入假设干整数，按冒泡排序法排序并输出；
●随机输入假设干整数，按直接选择排序法排序并输出;
任意输入N整数。
六、选做题目：
对快速排序、希尔排序、堆排序进行比较。
把握对一批记录进行排序的各类算法，包括直接插入排序法、冒泡排序法、直接选择排序法和快速排序法。
#defineM20
/*****把排序之前的数输入到指定文件夹中*****/
Voidwritefile1（int*a,intn）
{FILE*fp;
inti;
charfilename[10];
请输入要输出的文件名称（包括后缀名）:
gets（filename）;
if（（fp=fopen（filename,"
w"
））==NULL）
fprintf（"
不能打开文件!
排序之前:
*****\n"
for（i=1;
=n;
%3d"
a[i]）;
/*****把用各类排序方式排序后的数输入到指定文件夹中*****/
voidwritefile2（int*a,intn）
{FILE*fp;
排序以后:
a[0]=-1;
voidcreate（int*a,int*b,int*n）
{inti,;
srand（（unsigned）time（NULL））;
for（i=0;
n;
{a[i]=rand（）;
b[i]=a[i];
printf（"
%8d"
}}
/***1*****插入排序**********/
voidinsertsort（int*a,intn）
{inti,j;
for（i=2;
{a[0]=a[i];
for（j=i-1;
a[0]<
a[j];
j--）
a[j+1]=a[j];
a[j+1]=a[0];
}}
voidxiersort（int*a,intn）
{intd[3]={5,3,1};
inti,j,k=0;
while（k<
3）
{for（i=d[k]+1;
for（j=i-d[k];
j>
0&
a[j]>
a[0];
j=j-d[k]）
a[j+d[k]]=a[j];
a[j+d[k]]=a[0];
}
k++;
}}
voidmaopaosort（int*a,intn）
{inti,j,change,t;
for（i=1;
{change=0;
for（j=1;
j<
=n-i;
j++）
if（a[j]>
a[j+1]）
{t=a[j];
a[j]=a[j+1];
a[j+1]=t;
change=1;
if（change==0）
voidquicksort（int*a,intt,intn）
{inti=t,j=n;
while（i<
j）
{if（i<
{a[0]=a[i];
j&
a[0]）
j--;
if（i<
{a[i]=a[j];
i++;
a[i]<
i++;
if（i<
{a[j]=a[i];
j--;
}
a[i]=a[0];
quicksort（a,1,i-1）;
quicksort（a,i+1,n）;
voidjiandansort（int*a,intn）
{inti,j,t;
{for（j=i+1;
if（a[i]>
a[j]）
{t=a[i];
a[i]=a[j];
a[j]=t;
}
}
voidadjust（int*a,intlow,inttop）
{intj;
a[0]=a[low];
for（j=2*low;
=top;
j*=2）
{if（j<
top&
if（a[j]<
{a[low]=a[j];
low=j;
a[low]=a[0];
voidduisort（int*a,intn）
{
for（i=n/2;
0;
i--）
adjust（a,i,n）;
for（i=n;
1;
--i）
{printf（"
%5d"
a[1]）;
a[1]=a[i];
adjust（a,1,i-1）;
voidmain（）
inta[M+1],b[M+1],n=0,i;
charch1='
y'
ch2;
create（a,b,&
n）;
while（ch1=='
||ch1=='
Y'
）
{printf（"
\n输入1————插入排序"
printf（"
\n输入2————希尔排序"
printf（"
\n输入3————冒泡排序"
\n输入4————快速排序"
\n输入5————简单排序"
\n输入6————堆排序"
\n输入C（c）———从头产生随机数"
\n输入N（n）———退出\n"
\n%c"
ch2）;
if（a[0]==-1）
a[i]=b[i];
switch（ch2）
{case'
1'
:
writefile1（a,n）;
insertsort（a,n）;
writefile2（a,n）;
case'
2'
writefile1（a,n）;
xiersort（a,n）;
3'
maopaosort（a,n）;
writefile2（a,n）;
4'
quicksort（a,1,n）;
writefile2（a,n）;
5'
jiandansort（a,n）;
6'
duisort（a,n）;
C'
case'
c'
create（a,b,&
N'
n'
:
ch1='
（三）、实验中显现的问题及解决方式
随机输入假设干整数模块要注意程序循环的排列，能够让结果按直接选择排序法排序并输出。
升级会员 