大数据结构-实验六-报告材料

实用文案

实验报告

实验六 图的应用及其实现

一、实验目的

1．进一步功固图常用的存储结构。

2．熟练掌握在图的邻接表实现图的基本操作。

3．理解掌握AOV网、AOE网在邻接表上的实现以及解决简单的应用问题。

二、实验内容

一>.基础题目：(本类题目属于验证性的，要求学生独立完成)

[题目一]：从键盘上输入AOV网的顶点和有向边的信息,建立其邻接表存储结构,

然后对该图拓扑排序,并输出拓扑序列. 试设计程序实现上述AOV网的类型定义和基本操作,完成上述功能。

[题目二]：从键盘上输入AOE网的顶点和有向边的信息,建立其邻接表存储结构,输出其关键路径和关键路径长度。 试设计程序实现上述AOE网类型定义和基本操作,完成上述功能。

测试数据：教材图7.29

【题目五】连通 OR 不连通

描述：给定一个无向图，一共n个点，请编写一个程序实现两种操作： D x y 从原图中删除连接x，y节点的边。 Q x y 询问x，y节点是否连通 输入

第一行两个数n,m（5<=n<=40000,1<=m<=100000）

接下来m行，每行一对整数 x y （x,y<=n）,表示x,y之间有边相连。保证没有重复的边。

接下来一行一个整数 q（q<=100000） 以下q行每行一种操作，保证不会有非法删除。

标准文档

实用文案

输出

按询问次序输出所有Q操作的回答，连通的回答C，不连通的回答D 样例输入 3 3 1 2 1 3 2 3 5 Q 1 2 D 1 2 Q 1 2 D 3 2 Q 1 2 样例输出

C C D

【题目六】 Sort Problem

An ascending sorted sequence of distinct values is one in which some form of a

标准文档

实用文案

less-than operator is used to order the elements from smallest to largest. For example, the sorted sequence A, B, C, D implies that A < B, B < C and C < D. in this problem, we will give you a set of relations of the form A < B and ask you to determine whether a sorted order has been specified or not.

【Input】

Input consists of multiple problem instances. Each instance starts with a line containing two positive integers n and m. the first value indicated the number of objects to sort, where 2 <= n <= 26. The objects to be sorted will be the first n characters of the uppercase alphabet. The second value m indicates the number of relations of the form A < B which will be given in this problem instance. 1 <= m <= 100. Next will be m lines, each containing one such relation consisting of three characters: an uppercase letter, the character \<\ second uppercase letter. No letter will be outside the range of the first n letters of the alphabet. Values of n = m = 0 indicate end of input.

【Output】

For each problem instance, output consists of one line. This line should be one of the following three:

Sorted sequence determined: y y y… y. Sorted sequence cannot be determined. Inconsistency found.

标准文档

实用文案

y y y… y is the sorted, ascending sequence.

Sample Input Sample Output

4 6 Sorted sequence determined: A B C D. A

设计要求：

1、上机前，认真学习教材，熟练掌握AOV网、AOE网的构造和拓扑排序算法。

2、上机前，认真独立地写出本次程序清单，流程图，该程序包括图类型以及每一种操作的具体的函数定义和主函数。有关算法分别参阅讲义和

标准文档

实用文案

参考教材事例

三、实验步骤

㈠、数据结构与核心算法的设计描述 #define MAX_VERTEX_NUM 20

//变量声明

typedef struct ArcNode //弧结点定义 {

int adjvex; //该弧所指向的顶点的位置 struct ArcNode *nextarc;//指向下一条弧的指针 //InfoType *info;

}ArcNode;

typedef struct VNode //顶点结点定义 {

char data; //顶点信息

ArcNode *firstarc; //指向第一条依附该顶点的弧的指针

}VNode,AdjList[MAX_VERTEX_NUM]; typedef struct //图的定义 {

AdjList vertices;

int vexnum,arcnum; //图的当前顶点数和弧数 int kind; //图的种类标志

}ALGraph;

ALGraph G; //定义图变量

bool visited[MAX_VERTEX_NUM]; //访问标志数组 int indegree[MAX_VERTEX_NUM]； //入度数组 struct Stack //栈类型定义 { };

Stack stack; //定义一个栈

int s[21]; int top;

标准文档