摘要:本文主要向大家介绍了C/C++知识点之C语言程序试题-01,通过具体的内容向大家展示,希望对大家学习C/C++知识点有所帮助。
本文主要向大家介绍了C/C++知识点之C语言程序试题-01,通过具体的内容向大家展示,希望对大家学习C/C++知识点有所帮助。
一个无向连通图G点上的哈密尔顿(Hamiltion)回路是指从图G上的某个顶点出发,经过图上所有其他顶点一次且仅一次,最后回到该顶点的路劲。一种求解无向图上哈密尔顿回路算法的基础私下如下:
假设图G存在一个从顶点V0出发的哈密尔顿回路V1——V2——V3——...——Vn-1——V0。算法从顶点V0出发,访问该顶点的一个未被访问的邻接顶点V1,接着从顶点V1出发,访问V1一个未被访问的邻接顶点V2,..。;对顶点Vi,重复进行以下操作:访问Vi的一个未被访问的邻接接点Vi+1;若Vi的所有邻接顶点均已被访问,则返回到顶点Vi-1,考虑Vi-1的下一个未被访问的邻接顶点,仍记为Vi;知道找到一条哈密尔顿回路或者找不到哈密尔顿回路,算法结束。
【C代码】
下面是算法的C语言实现。
(1)常量和变量说明
n :图G中的顶点数
c[][]:图G的邻接矩阵
k:统计变量,当期已经访问的定点数为k+1
x[k]:第k个访问的顶点编号,从0开始
visited[x[k]]:第k个顶点的访问标志,0表示未访问,1表示已访问
(2)C程序
1 #include
2 #include
3 #define MAX 100
4
5 void Hamilton(int n,int x[MAX,int c[MAX][MAX]){
6 in t ;
7 in t visited[MAX];
8 int k;
9 /*初始化x数组贺visited数组*/
10 for(i=0:i<n;i++){
11 x[i]=0;
12 visited [i]=0;
13 }
14 /*访问起始顶点*/
15 k=0;
16 (visited[0]=1);
17 x[0]=0;
18 k=k+1;
19 /*访问其他顶点*/
20 while(k>=0){
21 x[k]=x[k]+1;
22 while(x[k]><n){
23 if(visited[x[k]]==0) &&c[x-[k-1]][x[k]=1){/*邻接顶点x[k]未被访问过*/
24 break;
25 }else{
26 x[k] = x[k] +1;
27 }
28 }
29 if(x[k] <n-1&&(visited[x[k]]==1){ /*找到一条哈密尔顿回路*/
30 for(k=0;k<n;k++){
31 prinf(〝%d--〝,x[k] ; /*输出哈密尔顿回路*/
32 }
33 prinf(〝%d--〝,x[0] ;
34 return;
35 }else if x[k]<n&&k<n-1){/*设置当期顶点的访问标志,继续下一个顶点*/
36 (visited[x[k]]=1);37 k=k+1;
38 }else{/*没有未被访问过的邻接顶点,回退到上一个顶点*/
39 x[k]=0;
40 visited x[k]=0;
41 (k=k-1);
42 }
43 }
44 }
【问题1】(10分)
根据题干说明。填充C代码中的空(1)~(5).
答案:代码中标注红色的即为答案!
【问题2】(5分)
根据题干说明和C代码,算法采用的设计策略为(6),该方法在遍历图的顶点时,采用的是(7)方法(深度优先或广度优先)。
答案:
6:回溯法
7:深度优先
本文由职坐标整理并发布,希望对同学们有所帮助。了解更多详情请关注职坐标编程语言C/C+频道!
您输入的评论内容中包含违禁敏感词
我知道了
请输入正确的手机号码
请输入正确的验证码
您今天的短信下发次数太多了,明天再试试吧!
我们会在第一时间安排职业规划师联系您!
您也可以联系我们的职业规划师咨询:
版权所有 职坐标-一站式IT培训就业服务领导者 沪ICP备13042190号-4
上海海同信息科技有限公司 Copyright ©2015 www.zhizuobiao.com,All Rights Reserved.
沪公网安备 31011502005948号