计算机复试上机试题（c语言版）

introduction

the project will read flight data from an input file andflight path requests from another input file and output the requiredinformation.

?

your task

your program should determine if aparticular destination airport can be reached from a particular originatingairport within a particular number of hops.

a hop (leg of a flight) is a flight from one airport to anotheron the path between an originating and destination airports.

for example, the flight plan from pvg to pek might be pvg→ can → pek. so pvg → can would be a hop and can → pek would be a hop.

?

input data files

path inputfile(pathinput.txt)

this input file will consist of a number of single origination/destinationairport pairs (direct flights). the first line of the file will contain aninteger representing the total number of pairs in the rest of the file.

6

[pvg, can]

[can, pek]

[pvg, ctu]

[ctu, dlc]

[dlc, hak]

[hak, lxa]

?

pathrequest file(pathrequest.txt)

this input file will contain a sequence of pairs oforigination/destination airports and a max number of hops. the first line ofthe file will contain an integer representing the number of pairs in the file.

2

[pvg, dlc, 2]

[pvg, lxa, 2]

?

outputfile(output.txt)

for each pair in the path request file, your programshould output the pair followed by “yes” or “no” indicating that it is possible to get from the origination to destinationairports within the max number of hops or it is not possible,respectively.

[pvg, dlc, yes]

[pvg, lxa, no]

assumptions youcan make:

you may make the following simplifying assumptions inyour project:

l? c/c++ is allowed to be used.

l? all airport codes will be 3 letters and will be in allcaps

l? origination/destination pairs are unidirectional. toindicate that both directions of flight are possible, two entries would appearin the file. for example, [pvg, pek] and [pek, pvg] would have to be present inthe file to indicate that one could fly from shanghaito beijing and from beijingto shanghai.

题意理解：

给定一个图，任意输入图中两点，输出这两个点是否能在给定最大跳数内连通

 

例如

[pvg, dlc, 2] 给定最大跳数是2，实际跳数是2 未超过最大跳数 输出yes
[pvg, lxa, 2]给定最大跳数是2，实际跳数是4 超过最大跳数 输出no

由于不会从文件中直接读取

6
[pvg, can]
[can, pek]
[pvg, ctu]
[ctu, dlc]
[dlc, hak]
[hak, lxa]
2
[pvg, dlc, 2]
[pvg, lxa, 2]
这样的数据
所以只能模拟文件读取后的输入状态即：
6
pvg can
can pek
pvg ctu
ctu dlc
dlc hak
hak lxa
3
pvg dlc 2
pvg lxa 2

输出结果
[pvg, dlc, yes]

[pvg, lxa, no]

这个题算法不难就是个dfs，就是图结点是字符，有点坑

下面给出程序，不一定对，程序使用方法

输入数据

6
pvg can
can pek
pvg ctu
ctu dlc
dlc hak
hak lxa
3
pvg dlc 2

pvg lxa 2

输出数据

[pvg, dlc, yes]

[pvg, lxa, no]

#include
#include 

struct nodeinfo
{
	char no[10];//结点的名称；
	char joint[100][10];//与该结点相连的所有结点的集合
	int num_edge=0;//结点的度数
	int visited;//访问标志位 
}node[500];

int num_node=0,flag;// num_node是图中结点的个数 

int ni(char a[])//找出字符结点在结构体数组中的位置 
{
	for(int i=0;i<num_node;i++) if(!strcmp(node[i].no,a))="" return="" i;="" -1;="" 点不存在置为-1="" }="" bool="" islink(char="" a[],char="" b[])="" 判断两结点是否连通="" {="" int="" i="ni(a);" for(int="" j="0;j