数据结构与算法专题实验报告文档格式.docx
- 文档编号:4482709
- 上传时间:2023-05-03
- 格式:DOCX
- 页数:31
- 大小:969.16KB
数据结构与算法专题实验报告文档格式.docx
《数据结构与算法专题实验报告文档格式.docx》由会员分享,可在线阅读,更多相关《数据结构与算法专题实验报告文档格式.docx(31页珍藏版)》请在冰点文库上搜索。
3.约瑟夫环中人员相继有规律的出列其实质是在单链表中连续删除结点直至剩余最后一个结点,当然它还满足一定的条件,那就是每删除一个结点后,下一个待删除的结点是从删除的结点的下一个结点开始计数,数到删除的结点的数据时,再次删除结点。
4.用文件输出则直接调用文件读取函数即可实现文件输出。
4算法描述:
step1:
定义单链表数据结构;
step2:
creat()函数//创建但链表,默认第i个结点的序号为i;
a.输入总的结点数
n,,并判断其是否在允许的范围内,如果不在,则返回,重新输入;
b.for(i<
n){申请空间,输入密码,判断其是否在[0,MAX]范围内,如不在,返回,重新输入;
}
step3:
Disp(Yoseph*L)//出列函数,实现题设要求
while(p的下已个结点不是p)
{if(初始密码为1)则输出第i个结点,带回p->
code并删除该结点,p=p->
next
else,从第i个结点计数,数到第m个结点,带回p->
next;
step4:
fopen("
t.out"
"
w"
)实现文件的输出;
step5:
主函数
5程序流程图:
6源程序:
//用循环链表实现Yoseph环:
#include<
fstream.h>
//实现文件输出的头文件
stdlib.h>
stdio.h>
#defineNUM50
staticinta[NUM];
//用来存放人数和初始密码值及出队序列
intj=2,n;
structYoseph//定义单链表数据结构
{intnum;
intcode;
Yoseph*next;
};
Yoseph*creat()//创建单链表
{inti,k=0;
Yoseph*L,*p,*q;
intn;
printf("
请输入总人数:
\n"
);
scanf("
%d"
&
n);
a[0]=n;
L=p=(structYoseph*)malloc(sizeof(Yoseph));
p->
num=1;
请输入第1个人手中所持的密码:
p->
code);
while(p->
code<
1||p->
code>
30)//设置密码的范围
{
输入错误!
请重新输入:
}
a[j]=p->
code;
j++;
for(i=2;
i<
=n;
++i)
{q=(structYoseph*)malloc(sizeof(Yoseph));
//为循环单链表申请空间
q->
num=i;
next=q;
p=q;
请输入第%d个人手中所持的密码:
i);
q->
while(q->
1||q->
20)
请重新输入:
//纠错功能
a[j]=q->
next=L;
returnL;
}
voidDisp(Yoseph*L)//输出出队序列
{intk,m;
structYoseph*p=L,*q;
请输入初始值:
\n"
m);
a[1]=m;
出列顺序如下:
"
next!
=p)//直到剩下最后一个结点才退出
{if(m==1)
printf("
%3d"
p->
num);
a[j++]=p->
num;
next=p->
next;
m=p->
p=p->
else
{for(k=1;
k<
m;
++k)//计数到第m个将此结点删除
{q=p;
//带回被删除的结点的数据,即出列的人手中的密码
出列完毕!
voidmain()//主函数
{intj;
Yoseph*L;
FILE*fpt;
L=creat();
Disp(L);
fpt=fopen("
//调用文件输出语句,实现将结果存放在名为t.out的文件当中
fprintf(fpt,"
总人数为:
%3d\n"
a[0]);
初始密码为:
a[1]);
前%d个为密码,后%d个为出列人序号:
for(j=2;
j<
n+2;
j++)//输出程序运行完毕后出列序列
a[j]);
for(j=n+2;
NUM;
j++)
{if(a[j]!
=0)
fclose(fpt);
返回
第2题大数阶乘
求N!
(N>
10)
1.掌握大数的处理方法
2.编程实现时应该考虑边界条件的处理。
1.为实现大数阶乘,我们来看下面的分析:
0!
=1;
1!
2!
=1+1;
(1!
加2次)
3!
=2+2+2;
(2!
加3次)
4!
=6+6+6+6;
(3!
加4次)
n!
=(n-1)!
+(n-1)!
+……+(n-1)!
((n-1)!
加n次)
2!
3!
4!
…………
=(n-1!
)!
+……+(n-1)!
(加n次)
算n!
要先算(n-1)!
然后再把它相加n次,可以用类似竖式加法实现。
a[MAX]……a[3]a[2]a[1]a[0]
+a[MAX]……b[3]b[2]b[1]b[0]
2.还要考虑边界条件,负数无法求阶乘,太大的数求阶乘太耗时间,故确定范围[0,NUM],在此范围内程序继续执行,超出这个范围,则返回重新输入。
3.对一个数来说最高位不可能为0,设置从a[MAXnumber]开始扫描,遇到第一个不为0的数位时开始输出。
定义数组的最大位数,定义存放最后结果和分布结果的数组a和b;
step2:
输入并判断,符合,则继续,不符合,返回重新输入;
step3:
while(0<
n<
MAXnumber)
a.初始化两个数组,a[0]=1,,输入所要求阶乘的那个数n;
b.for语句(j<
n){把每次求得的一个中间结果从a数组中复制到b数组中,for语句(m<
j)实现把b数组中所得的结果相加j次得j!
step4:
输出,从a数组的最后一个元素向前扫描,遇到第一个不为0的数字开始输出。
#include<
iostream.h>
#defineMAXnumber3000//定义数组的最大长度
voidmain()
{inta[MAXnumber],b[MAXnumber];
//定义存放结果的数组
inti,j,m,k,r,n;
charch='
y'
;
while(ch!
='
n'
)
{cout<
<
请输入你所想求阶乘的那个数:
endl;
cin>
>
n;
if(n>
1000)//设置大数的边界条件,大数求阶乘比较慢
{
cout<
你所输入的数字太大,请重新输入!
while(n<
0)//设置边界条件,负数无法求阶乘
对不起,输入错误,请重新输入!
for(i=1;
MAXnumber;
a[i]=0;
a[0]=1;
++j)
{for(i=0;
b[i]=a[i];
for(m=1;
m<
j;
++m)
for(i=0;
++i)//用类似于竖式加法实现阶乘
{r=a[i]+b[i];
if(r>
9)
a[i+1]++;
a[i]=r%10;
}
k=MAXnumber-1;
//从数组末一个元素开始扫描,当遇到第一个不为0的元素时开始输出
while(a[k]==0)
--k;
cout<
!
="
for(i=k;
i>
=0;
--i)
a[i];
输入继续吗?
是请键入“y”,退出键入“n”!
ch;
第3题图的遍历
1题目
现用Diskstra算法实现求最短路径
2目标
1.结点部少于30;
2.可以从键盘或从文件输入结点数据,包括顶点信息、边、权等。
3.从用户指定的顶点为起始点,输出该结点到其余各顶点的最短路径长度机器路径。
3设计思想
1.我采用二维数组实现输出图的邻接矩阵,对应行和列为顶点序号。
2.在创建图时,设置顶点个数范围,设置顶点,权值,边数的范围。
3.再输入边时采用以0,0,0结束,就是当我们把顶点,顶点,权值都输入0时,输入结束。
4.最短路径设置双重循环,求得最短路径。
定义顶点最大个数,无穷大时的权值为10000,存放边的n维数组cost[MAX][MAX],最短路径dist[MAX];
定义无向图数据结构;
creatgraph()//创建无向图
a.输入图的顶点个数,并判断0<
=MAX,如果不是,则返回重新输入;
b.while(s!
=0||e!
=0||len!
=0)输入顶点,顶点,权值,并判断s>
=0&
&
s<
n&
e>
e<
len>
0,如果不是,则返回,重新输入,最后以0,0,0结束输入;
shortdjs()//求最短路径
a.for语句(i<
n)
{初始化权值,设置一个最短路径的起始点经过边数}
b.for语句(i<
{
for语句(j<
n)寻找第I个结点到V0的直接路径;
for语句(i<
n)寻找V0到第j个结点的所有路径并把最小的放到dist[i]中;
step5:
dispath()//输出最短路径
step6:
直接调用creatgraph(),shortdjs(),dispath()三个函数。
//无向图的最短路径
#include<
#defineMAX30//顶点的最大个数
#defineup1000//当两顶点之间的权值为无穷大时,输出1000
intcost[MAX][MAX];
//邻接表
intdist[MAX],n;
//最短路径
struct
intnum;
intpnode[MAX];
//途中经过的顶点
}path[MAX];
voidcreatgraph()//创建无向图
inti,j,s,e,len,contin=1;
请输入图的顶点个数:
"
if(n<
1||n>
=MAX)//纠错功能
输入错误,请重新输入"
cin>
for(i=0;
i++)//初始化无向图
{
for(j=0;
cost[i][j]=cost[j][i]=up;
cost[i][i]=0;
cout<
输入各边,以0,0,0表示结束:
i=1;
while(contin==1)//设置输入条件
\t第"
条边->
顶点,顶点,权值:
s>
len;
if(s==0&
e==0&
len==0)//当它们都为0时就退出输入
contin=0;
elseif(s>
0)
cost[s][e=cost[e][s]=len;
//实现无向图的操作
i++;
\t\t边值错误,请重新输入!
voidshortdjs()//寻找最短路径的算法函数的实现
ints[MAX];
intmindis,dis,i,j,v0=0,u;
i++)
dist[i]=cost[v0][i];
path[i].pnode[0]=v0;
path[i].num=0;
s[i]=0;
s[v0]=1;
for(i=1;
mindis=up;
for(j=1;
if(s[j]==0&
dist[j]<
mindis)
u=j;
mindis=dist[j];
s[u]=1;
//当s[u]=1时表示权值为无穷大
for(j=1;
if(s[j]==0)
dis=dist[u]+cost[u][j];
if(dist[j]>
dis)
dist[j]=dis;
path[j].num++;
path[j].pnode[path[j].num]=u;
path[i].num++;
path[i].pnode[path[i].num]=i;
voiddispath()//输出最短路径
inti,j;
endl<
从v0到各顶点的最短路径长度如下:
\t(起点->
终点)最短长度最短路径"
\t(V0->
V"
):
;
if(dist[i]<
up)
dist[i]<
("
else
10000("
for(j=0;
path[i].num;
path[i].pnode[j]<
path[i].pnode[path[i].num]<
)"
voidmain()//主函数
creatgraph();
//直接调用三个函数就行
shortdjs();
dispath();
第4题最短路径
创建一个具有n(n≥1)个顶点的无向图的邻接矩阵,并对其按照“深度优先搜索”和“广度优先搜索”方法进行遍历。
1.编写C程序予以实现。
2.程序要求能输入图的顶点数、边数以及边的关系,并自动生成邻接矩阵。
3.结果输出邻接矩阵和遍历的路径。
4.熟悉无向图的两种遍历算法。
1.考虑用一个n维数组来存放无向图,若两个结点之间有边,则n维数组对应下标的那个元素值为1,否则为0;
2.在输入图的顶点数和边数时我充分考虑了边界条件,顶点数G.vexnum在[0,MAXV]范围内,边数在[0,G.vexnum*(G.vexnum-1)/2]范围内,在这个范围内,程序继续向下执行,否则返回重新输入;
3.输出邻接矩阵的实质是输出n维数组,我用两重循环来实现;
4.深度优先遍历我采用迪杰特斯拉算法,不过要在此算法中间加一个判断,所有的结点是否都已经遍历过,如果是就退出,如果不是,则按顺序从序号小的开始向大的寻找,找到一个没有遍历过的结点继续调用深度优先遍历算法;
5.广度优先遍历我采用了非递归算法,其实质和深度优先遍历算法相同;
6.在主函数中直接调用CreatGraph(G),DispMatrix(G),DepthDisp(G,v),WidthDisp(G)函数即可。
设置无向图最多的顶点数//这个设置为了更好的输出邻接矩阵;
定义无向图的数据结构;
实现生成无向图函数CreatGraph(G)
a.输入顶点数n,判断它是否在允许的范围内,不在则返回重新输入;
b.输入无向图的边数G.arcnum,判断它是否在允许的范围内,不在则返回重新输入;
c.输入边,for语句(k=1toG.arcnum){输入两顶点v,w,判断v!
=w&
0<
v<
=Gverxnum&
w<
=Gverxnum,如果是在n维数组中第v行第w列和第w行第v列元素都为1,否则返回重新输入;
实现输出邻接矩阵函数DispMatrix(Graph&
G),双重for循环实现输出无向图的邻接矩阵;
实现深度优先遍历的递归算法函数DepthDisp(Graph&
G,intv)
a.从v开始遍历,设置计数器num=0,并置顶点v已访问;
b.for语句(i=1toG.vexnum)判断G.arcs[v][i]!
visited[i]==0,如果是递归调用深度优先遍历的递归算法函数DepthDisp(G,i),如果不是则退出;
c.用for和if语句判断是否所有的顶点都已经遍历完,
ifnum<
G.vexnum
for(i=1toG.vexnum)
if(visited[i]==1)i++
如果不是,则继续调用深度优先遍历的递归算法函数DepthDisp(G,i);
实现广度优先遍历的非递归算法函数WidthDisp(Graph&
G)
a.输入广度优先遍历的出发点m,判断0<
G.vexnum,如果不是,则返回重新输入;
b.for(i=1toG.vexnum)
{判断第i个顶点与第m之间是否有边,有边则输出,k++,判断k=G.vexnum,等于,则退出,遍历完毕,不等于,转到与m有边的顶点继续遍历,要是有边的都已经遍历过,继续找一个没有遍历的顶点,继续;
step7:
主函数直接调用CreatGraph(G),DispMatrix(G),DepthDisp(G,v),WidthDisp(G)函数即可;
1.创建无向图函数的流程图如下:
2.深度优先遍历函数实现的流程图如下:
3.实现广度优先遍历的流程图如下:
6源程序
//二,不带权值的无向图的遍历:
#include<
#defineMAXV20//定义顶点的最大个数
structGraph//定义无向图的数据结构
{intvexs[MAXV];
intarcs[MAXV][MAXV];
intvexnum,arcnum;
staticintvisited[MAXV];
voidCreatGraph(Graph&
G)//实现创建无向图的函数
{inti,j,k,v,w;
请输入顶点数:
cin>
G.vexnum;
while(G.vexnum>
MAXV)
{cout<
图的顶点数超限,请重新输入:
//纠错功能
请输入边数:
G.arcnum;
while(G.arcnum>
G.vexnum*(G.vexnum-1)/2)//V个顶点最多V(V-1)/2个顶点
图的边数超限,请重新输入:
=G.vexnum;
for(j=0;
G.arcs[i][j]=0;
for(k=1;
=G.arcnum;
k++)
请输入第"
条边所连接的两个顶点:
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 算法 专题 实验 报告