实验3预习报告.doc

数据结构实验预习报告实验三图的存储与应用一、实验目的: 1. 掌握图的两种存储结构( 邻接矩阵和邻接表) 的表示方法; 2. 图的基本运算及应用。二、实验内容拓扑排序:已知有九门课程,依次编号为 C0 至 C8 ,在图一中给出了给出了各门课程之间先后关系。例如: C0 是 C2 和 C6 的前序课程, 而在选修 C8 之前, 必须已经选修过 C3 和 C7 。要求存储该拓扑结构图,当用户从键盘输入任意课程的编号时,可打印出该课程的所有的前序课程。图一九门课程的拓扑结构图拓扑排序程序: #include <> #include <> #include <> typedef struct Node { int adjvex; // 该弧所指向的顶点的位置 struct Node *next; // 指向下一个条弧的指针}ode; typedef struct Vertex { int indegree; // 存放顶点的入度 ode *first_arc; // 指向第一条依附该顶点的弧的指针}VNode; int iarray[100]; // 用数组存储拓扑序列 typedef struct { int *base; int *top; }Stack; Stack S; // 用栈暂存所有入度为 0 的顶点 void InitStack(Stack *S) { 数据结构实验预习报告 S->base = (int *)malloc(10 * sizeof(int)); S->top = S->base; } void Push(Stack *S, int e) { *S->top++ = e; } void Pop(Stack *S, int *e) { *e= *--S->top; } void create_graph(VNode *vlist, int n) // 用邻接表构造图{ int i, position; ode *p, *q; for (i= 0;i != n; ++i) { // 为每个顶点建立单链表 vlist[i].first_arc = 0; vlist[i].indegree = 0; printf(" 输入%d 号顶点的邻接点(以-1 结束) \n", i); scanf("%d", &position); while (position != -1) {q= (ode *)malloc(sizeof(ode)); if (!q) { printf(" 内存分配失败"); return; } q->adjvex = position; q->next = 0; if (0 == vlist[i].first_arc) { vlist[i].first_arc = q; } else { p->next = q; }p= q; scanf("%d", &position); }} 数据结构实验预习报告} void get_indegree(VNode *vlist, int n) // 得到每个顶点的入度{ int i; ode *p; for (i= 0;i != n; ++i) { for (p= vlist[i].first_