算法设计与分析实验1.4

实验内容

​ 本次实验考察的是给你一段伪代码，从中提取出有效信息，并且用可运行代码完成

伪代码如下

具体代码如下

#define  _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#define N 100
char letter[26] = { 'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','S','Y','Z' };
struct ArcNode {//表结点
	struct ArcNode* next;//下一个结点的指针
	int vertex;//编号
};
struct verNode {//头节点
	int vertex;//编号
	struct ArcNode* first;//第一个结点指针
};
struct Stack {
	int top=-1;//top从-1开始
	int a[N];
};
void Initial(int n);
void crtGraph(int ver, int arc);
void dfs_travel(int n);
void dfs(int i);
void push(int data);
int  pop();
struct verNode Ver[N];//头节点数组
int visited[N];//判断是否遍历
struct Stack newStack;
int main(void) {

	int n, e;// 边的数量和结点的数量
	int ver, arc;//头节点，表结点
	scanf("%d %d", &n, &e);
	Initial(n);
	for (int i = 0; i < e; i++) {
		scanf("%d %d", &ver, &arc);//输入头节点坐标和表结点坐标
		crtGraph(ver, arc);
	}
	dfs_travel(n);
	while (newStack.top!=-1) {//依次出栈直到栈为空
		int i = pop();
		printf("%c ", letter[i]);//按字符输出
	}

	return 0;
}
void Initial(int n) {//初始化头节点数组
	for (int i = 0; i < n; i++) {
		Ver[i].first = NULL;
		Ver[i].vertex = i;//编号
	}
}
void crtGraph(int ver, int arc) {//创建邻接表
	struct ArcNode* q = (struct ArcNode*)malloc(sizeof(struct ArcNode));
	q->vertex = arc;//表结点初始化
	q->next = NULL;
	if (Ver[ver].first == NULL) Ver[ver].first = q;
	else {
		struct ArcNode* pTemp = Ver[ver].first;
		while (pTemp->next != NULL) {//找到该链表倒数第二个结点
			pTemp = pTemp->next;
		}
		pTemp->next = q;
	}
}
void dfs_travel(int n) {
	for (int i = 0; i < n; i++) {
		if (!visited[i]) dfs(i);
	}
}
void dfs(int i) {
	visited[i] = 1;
	struct ArcNode* p = Ver[i].first;
	while (p != NULL) {
		if (!visited[p->vertex]) {
			dfs(p->vertex);//如果该节点没有被访问过,dfs递归该节点
		}
		p = p->next;
	}
	push(i);//该节点编号入栈
}
void push(int data) {
	newStack.a[++newStack.top] = data;
}
int pop() {
	return newStack.a[newStack.top--];
}