数据结构课程设计参考答案c组.docx
- 文档编号:13360627
- 上传时间:2023-06-13
- 格式:DOCX
- 页数:90
- 大小:38.13KB
数据结构课程设计参考答案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;i for(j=0;j chess[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;i if(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(count return-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(max 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;i printf("顶点: %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
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 课程设计 参考答案