数据结构课程设计参考答案c组.docx
《数据结构课程设计参考答案c组.docx》由会员分享，可在线阅读，更多相关《数据结构课程设计参考答案c组.docx（90页珍藏版）》请在冰点文库上搜索。
数据结构课程设计参考答案c组
/*
马的遍历及其复杂性分析
*/
#include
#defineMAX16
intstep=0,count=0;
/*chess[MAX][MAX]用来表示棋盘；step是步骤数；count是运算次数；
chess[i][j]==-1表示该单元格非当前棋盘的有效位置；
chess[i][j]==0表示该单元格尚未经过马的遍历；
chess[i][j]>=1表示马遍历时经过该单元格时的步骤；
*/
/*nextStepNum（）函数用来计算（x，y）处可以跳的方向数*/
intnextStepNum（intchess[][MAX],intx,inty）
{
intsum=0;
if（chess[x-1][y-2]==0）
sum++;
if（chess[x-2][y+1]==0）
sum++;
if（chess[x+2][y+1]==0）
sum++;
if（chess[x+2][y-1]==0）
sum++;
if（chess[x-2][y-1]==0）
sum++;
if（chess[x-1][y+2]==0）
sum++;
if（chess[x+1][y-2]==0）
sum++;
if（chess[x+1][y+2]==0）
sum++;
return（sum）;/*每找到一个位置sum++，最后返回sum值就是在（x,y）处可走的位置数*/
}
/*jump函数测试第step步为（x,y）位置的情况下，是否可以走完棋盘，如果可以返回1，否则返回0*/
intjump（intchess[][MAX],introwNum,intcolNum,intx,inty）
{
ints[9],a[9];
intmin,i,j,k;
count++;
step++;
chess[x][y]=step;
/*如果已经走到了rowNum×colNum的话，表示满足结束条件，返回1*/
if（step==rowNum*colNum）
return1;
/*计算（x，y）处下一步的八个位置上，每个位置上可以继续进行跳跃的方向数*/
s[1]=nextStepNum（chess,x-2,y+1）;
s[2]=nextStepNum（chess,x-1,y+2）;
s[3]=nextStepNum（chess,x+1,y+2）;
s[4]=nextStepNum（chess,x+2,y+1）;
s[5]=nextStepNum（chess,x+2,y-1）;
s[6]=nextStepNum（chess,x+1,y-2）;
s[7]=nextStepNum（chess,x-1,y-2）;
s[8]=nextStepNum（chess,x-2,y-1）;
/*对下一步的八个位置上可以继续进行跳跃的方向数从小到大排序*/
//s数组的下标即为方向编号，a数组中存储的即为各个方向编号
for（j=1;j<=8;j++）
{
min=9;
a[j]=1;
for（i=1;i<=8;i++）
if（s[i]{
min=s[i];
a[j]=i;//将s数组的下标（即方向编号）存入依次存入a数组中
k=i;
}
s[k]=9;
}
//按可以进一步跳跃方向数从小到大的顺序，决定首先跳转的方向（贪心算法的思想）
//依次测试八个跳跃方向
for（i=1;i<=8;i++）
{
switch（a[i]）
{
case1:
//方向1可以跳跃，并且跳通了，则返回1，表示后面的方向不同再看；
//方向1不可跳跃，或者没有跳通，则直接break，执行下一次循环测试下一个方向。
if（chess[x-2][y+1]==0&&jump（chess,rowNum,colNum,x-2,y+1）==1）
return1;
break;
case2:
if（chess[x-1][y+2]==0&&jump（chess,rowNum,colNum,x-1,y+2）==1）
return1;
break;
case3:
if（chess[x+1][y+2]==0&&jump（chess,rowNum,colNum,x+1,y+2）==1）
return1;
break;
case4:
if（chess[x+2][y+1]==0&&jump（chess,rowNum,colNum,x+2,y+1）==1）
return1;
break;
case5:
if（chess[x+2][y-1]==0&&jump（chess,rowNum,colNum,x+2,y-1）==1）
return1;
break;
case6:
if（chess[x+1][y-2]==0&&jump（chess,rowNum,colNum,x+1,y-2）==1）
return1;
break;
case7:
if（chess[x-1][y-2]==0&&jump（chess,rowNum,colNum,x-1,y-2）==1）
return1;
break;
case8:
if（chess[x-2][y-1]==0&&jump（chess,rowNum,colNum,x-2,y-1）==1）
return1;
}
}
/*如果某个位置的八个方向都无法走了，则回退到上一个位置，测试上一个位置的下一个方向是否能走通*/
step--;
/*恢复棋盘中该位置的状态为0，并返回0表示该路没有走通*/
chess[x][y]=0;
return0;
}
voidmain（）
{
intchess[MAX][MAX];
introwNum=0,colNum=0;
inti,j,row,col;
while
（1）
{
printf（"\n*****************欢迎使用马的棋盘遍历系统****************\n"）;
/*初始化棋盘*/
for（i=0;ifor（j=0;jchess[i][j]=-1;
/*设置棋盘的大小*/
printf（"\n请输入棋盘的行数和列数（均小于15，格式：
行数列数）：
"）;
scanf（"%d%d",&rowNum,&colNum）;
for（i=1;i<=rowNum;i++）
for（j=1;j<=colNum;j++）
chess[i][j]=0;
printf（"\n请输入马的起始位置的行列坐标：
"）;
scanf（"%d%d",&row,&col）;
if（（row>=1&&row<=rowNum）&&（col>=1&&col<=colNum））//判断输入是否有效
{
printf（"遍历进行中，请稍等……\n"）;
if（jump（chess,rowNum,colNum,row,col）==1）
{
printf（"马遍历该棋盘的路径如下：
\n"）;
for（i=0;i<=colNum;i++）
printf（"%4d",i）;
printf（"\n"）;
for（i=1;i<=rowNum;i++）
{
printf（"%4d",i）;
for（j=1;j<=colNum;j++）
printf（"%4d",chess[i][j]）;
printf（"\n"）;
}
}
else
{
printf（"马不能对该棋盘进行完整遍历，请重新输入棋盘大小!
\n"）;
}
}
else
{
printf（"\n马的起始行列号输入错误，请重新输入!
\n"）;
}
}
}
/*
求AOE网的关键路径
*/
#include
#include
#include
#defineMAX10//顶点的个数
//定义弧结点
typedefstructArcNode1
{
inttailvex,headvex;//弧的尾和头顶点位置
floatweight;
structArcNode1*hlink,*tlink;//分别为弧头相同弧尾相同的弧的链域
}ArcNode;
typedefstructtype
{
charr[3];//顶点值
}VertexType;
typedefstructVexNode
{
VertexTypedata;
ArcNode*firstin,*firstout;//分别指向该顶点第一条入弧和出弧
}VexNode;
//定义十字链表类型
typedefstruct
{
VexNodexlist[MAX];//表头结点
intvexnum,arcnum;//有向图的当前顶点数和弧数
}OLGraph;
//确定vex顶点在图中的位置
intlocate（OLGraphG,VertexTypevex）
{
inti;
for（i=0;iif（strcmp（vex.r,G.xlist[i].data.r）==0）
returni;
return-1;
}
//判断输入的AOE网中是否存在环，得到拓扑序列
inttopoSort（OLGraphG,intindegree[],inttopo[]）
{
ArcNode*q;
intvisited[MAX];
inti,flag=1,count=0;
//初始化顶点访问数组，未输出设置为0，已输出设置为1
for（i=0;i{
visited[i]=0;
}
//拓扑排序
while（flag）
{
for（i=0;i{
if（visited[i]==0&&indegree[i]==0）
{
//输出该顶点，标记该顶点为已输出，已输出顶点的个数加1
topo[count++]=i;
visited[i]=1;
q=G.xlist[i].firstout;
while（q!
=NULL）
{
indegree[q->headvex]--;
q=q->tlink;
}
flag=1;
break;//这个break必不可少，否则程序逻辑上将会有漏洞！
}
else
flag=0;
}
}
if（countreturn-1;
else
return1;
}
//销毁十字链表
voiddestroy（OLGraphG）
{
ArcNode*p;
inti;
for（i=0;i{
G.xlist[i].firstin=NULL;
p=G.xlist[i].firstout;
while（p）
{
G.xlist[i].firstout=p->tlink;
free（p）;
p=G.xlist[i].firstout;
}
}
G.vexnum=-1;
G.arcnum=-1;
}
//创建AOE网的十字链表存储结构
voidcreateDG（OLGraph&G,intindegree[],inttopo[]）
{
inti,k;
floatweight;
intvextailpoi,vexheadpoi;
VertexTypevertail,verhead;
ArcNode*p;
//如果输入的图不是AOE网，则反复输入，直到输入正确为止
while
（1）
{
do
{
printf（"分别输入顶点和弧的个数（用空格键隔开）：
"）;
scanf（"%d%d",&G.vexnum,&G.arcnum）;
if（（G.vexnum<=0）||（G.vexnum>10））
printf（"\t\tAOE网的顶点数必须属于【1-10】，请重新输入！
\n"）;
}while（（G.vexnum<=0）||（G.vexnum>10））;
for（i=0;i{
printf（"输入第%d个顶点的值:
",i+1）;
scanf（"%s",&G.xlist[i].data）;
G.xlist[i].firstin=NULL;
G.xlist[i].firstout=NULL;
indegree[i]=0;
}
for（k=0;k{
printf（"输入第%d条弧的始点、终点和权值（用空白符隔开）：
",k+1）;
scanf（"%s%s%f",vertail.r,verhead.r,&weight）;
vextailpoi=locate（G,vertail）;
vexheadpoi=locate（G,verhead）;
p=（ArcNode*）malloc（sizeof（ArcNode））;//申请弧空间
p->tailvex=vextailpoi;
p->headvex=vexheadpoi;//对弧结点赋值
p->weight=weight;
p->hlink=G.xlist[vexheadpoi].firstin;
p->tlink=G.xlist[vextailpoi].firstout;
G.xlist[vextailpoi].firstout=p;//完成在入弧和出弧链头的插入
G.xlist[vexheadpoi].firstin=p;
indegree[vexheadpoi]++;//弧头结点的入度自增
}
printf（"\n\tAOE网输入结束，十字链表存储结构创建成功！
\n"）;
//如果可以拓扑排序，则break；否则，应回收该十字链表，并再次输入该AOE网
if（1==topoSort（G,indegree,topo））
break;
else
{
printf（"\n该十字链表表示的图中存在环，为其分配的内存空间已回收，请重新输入正确的AOE网！
\n\n"）;
destroy（G）;
}
}
}
/*输出AOE网的十字链表存储结构*/
voidprintfOLGraph（OLGraph&G）//输出函数
{
inti;
ArcNode*q;
if（G.vexnum>0）
{
printf（"十字链表为：
\n"）;//输出十字链表
for（i=0;i{
printf（"\n以顶点%s为弧尾的弧：
",G.xlist[i].data.r）;
q=G.xlist[i].firstout;//q指向表头结点中各结点的岀弧链
while（q）
{
printf（"%s-->%s的权值%.1f；",G.xlist[q->tailvex].data.r,G.xlist[q->headvex].data.r,q->weight）;
q=q->tlink;
}
printf（"\n以顶点%s为弧头的弧：
",G.xlist[i].data.r）;
q=G.xlist[i].firstin;//q指向表头结点中各结点的入弧链
while（q）
{
printf（"%s-->%s的权值%.1f；",G.xlist[q->tailvex].data.r,G.xlist[q->headvex].data.r,q->weight）;
q=q->hlink;
}
}
printf（"\n"）;
}
else
printf（"AOE网尚未输入，请先输入AOE网！
\n"）;
}
//求AOE网的关键路径并输出
voidsearchKeyPath（OLGraphG,inttopo[]）
{
inti;
floatve[MAX],vl[MAX];//顶点的最早发生时间和最晚发生时间
floatmax,min;//活动的时间余量
intarcHeadPoi,arcRearPoi;
ArcNode*p;
if（G.vexnum>0）
{
//顶点的最早发生时间=max（弧尾顶点的最早发生时间+弧长）
//如果没有以该顶点为弧头的弧，则该顶点的最早发生时间为0
for（i=0;i{
arcHeadPoi=topo[i];
p=G.xlist[arcHeadPoi].firstin;
if（p）
{
max=ve[p->tailvex]+p->weight;
p=p->hlink;
while（p）
{
if（maxtailvex]+p->weight）
max=ve[p->tailvex]+p->weight;
p=p->hlink;
}
ve[arcHeadPoi]=max;
}
else
ve[arcHeadPoi]=0;
}
//顶点的最晚发生时间=min（弧头顶点的最晚发生时间-弧长）
//如果没有以该顶点为弧尾的弧，则该顶点的最晚发生时间即为其最早发生时间
for（i=G.vexnum-1;i>=0;i--）
{
arcRearPoi=topo[i];
p=G.xlist[arcRearPoi].firstout;
if（p）
{
min=vl[p->headvex]-p->weight;
p=p->tlink;
while（p）
{
if（min>vl[p->headvex]-p->weight）
min=vl[p->headvex]-p->weight;
p=p->tlink;
}
vl[arcRearPoi]=min;
}
else
vl[arcRearPoi]=ve[arcRearPoi];
}
//输出所有顶点的最早和最晚发生时间
for（i=0;iprintf（"顶点:
%s，最早发生时间:
%.1f，最晚发生时间:
%.1f\n",G.xlist[i].data.r,ve[i],vl[i]）;
//遍历十字链表中的所有弧结点
//如果弧尾的最早发生+弧的权值==弧头的最晚发生，则该弧属于关键路径上的弧
printf（"\nAOE网的关键路径为：
\n"）;
for（i=0;i{
p=G.xlist[i].firstout;
while（p）
{
arcRearPoi=p->tailvex;
arcHeadPoi=p->headvex;
//找到一个符合条件的弧结点，则输出该弧
if（ve[arcRearPoi]+p->weight==vl[arcHeadPoi]）
printf（"%c-->%c\n",G.xlist[arcRearPoi].data,G.xlist[arcHeadPoi].data）;
p=p->tlink;//p指向同弧尾的下一个弧结点
}
}
}
else
printf（"AOE网尚未输入，请先输入AOE网！
\n"）;
}
//菜单
voidmenu（）
{
printf（"\n\t\t求AOE网的关键路径"）;
printf（"\n\t\t**************************************************"）;
printf（"\n\t\t*1输入AOE网*"）;
printf（"\n\t\t*2输出AOE网的十字链表存储结构*"）;
printf（"\n\t\t*3求AOE网的关键路径并输出*"）;
printf（"\n\t\t*0退出程序*"）;
printf（"\n\t\t**************************************************"）;
}
voidmain（）
{
OLGraphG;
intselect;
intindegree[MAX];
inttopo[MAX];
//初始化AOE网的十字链表结构
G.vexnum=-1;
while
（1）
{
men
升级会员 