数学与计算机学院 数据结构 实验报告

年级 09数计 学号 2009432125 姓名 刘宝 成绩 专业 数电 实验地点 主楼401 指导教师 苗秀芬 实验项目 拓扑排序 实验日期 10年12月24日

一、实验目的

1掌握图的存储结构及其基本操作，学会定义图的邻接表存储结构，并能在实际问题中灵活运用。

2掌握拓扑排序算法。

3、通过本实验的具体应用实例，灵活运用拓扑排序并进一步巩固队列/栈的运用。

二、实验问题描述

1简介：用邻接表形式存储实验中的有向无环图，此有向无环图称为：AOV网，若网中每一个顶点都在他的拓扑排序中，则说明不存在环。

2步骤：

?从AOV网中选出一个没有前驱的结点，并输出他；

?从网中删除此结点，并且删除从该顶点发出的所有有向边（邻接点的入度-1） ?重复以上两步，直到途中不存在入度为0的顶点为止

三、实验步骤

1、实验问题分析

（1） 顶点表

typedef struct//顶点表结点

{

int in;//入度

int vertex;//顶点域

edgenode * firstedge;//边表头指针

}vertexnode;

（2） 边表

typedef struct node //边表结点

{

int adjvex;//邻接点域

struct node * next;//指向下一个邻接点的指针域 }edgenode;

（3） 以邻接表类型存储的图类型

typedef struct{

Adjlist adjlist; //邻接表

int vnum,Enum; //顶点数和边数

}Algraph;

2、功能（函数）设计

（1）建立一个以邻接表存储的有向图

函数原型：

void creatalgraph(Algraph *G)

（2）拓扑排序

函数原型：

void TopoSort(Algraph *G)

四、实验结果（程序）及分析

1、 实验主要模块代码（带注释！）或模块的流程图

(1) 建立一个以邻接表存储的有向图

void creatalgraph(Algraph *G)//创建邻接链表

{

int i,k,j;

edgenode *s;

cout<<"该AOV网的顶点数和边数："<<endl;

cin>>G->vnum>>G->Enum; //读入顶点数和边数

cout<<"请输入顶点信息："<<endl;

for(i=0;i<G->vnum;i++) //建立有vnum个顶

点的顶点表

{

cin>>G->adjlist[i].vertex; //读入顶点信息

G->adjlist[i].in=0;

G->adjlist[i].firstedge=NULL; //顶点

的边表头指针设为空

}

cout<<"请输入边的信息："<<endl; //

for(k=0;k<G->Enum;k++) //建立边表

{

cout<<"依次输入每一条边："<<endl;

cout<<"从";cin>>i;cout<<"邻接到";cin>>j;cout<<endl;

//读入边<vi,vj>的顶点对应的序号

s=new edgenode; //生成新的边表结点

s->adjvex=j; //邻接点的序号为j

s->next=G->adjlist[i].firstedge; //将

新边表结点s插入到顶点vi的边表头部

G->adjlist[i].firstedge=s; }

}

(2) 拓扑排序

int toposort(Algraph *G)

{

int i,j,k;

int m=0,top;

edgenode *ptr;

top=-1;

for(i=0;i<G->vnum;i++)

if(G->adjlist[i].in==0)

{ G->adjlist[i].in=top;

top=i;}

while(top!=-1)

{

j=top;

top=G->adjlist[top].in;

cout<<G->adjlist[j].vertex<<endl;

m++;

ptr=G->adjlist[j].firstedge;

while(ptr!=NULL)

{

k=ptr->adjvex;

G->adjlist[k].in--;

if(G->adjlist[k].in==0){

G->adjlist[k].in=top;

top=k;

}

ptr=ptr->next; //头插入

}

}

if(m<G->vnum)

{

cout<<"此图中存在环！无法进行拓扑排序"<<endl;

return 0;//返回错误代码0

}

else

return 1;//成功返回1

}

2、测试数据

3、调试过程中出现的问题以及解决策略

第二篇：数据结构-拓扑排序-实验报告与代码

实验报告七----拓扑排序

一．需求分析

1、采用邻接表法的存储结构来定义有向图

2、实现有向图的创建、遍历

3、实现栈的创建及其基本操作（进栈、退栈、判空）

4、求图中顶点的入度

二．算法设计

本程序中采用的数据模型，用到的抽象数据类型的定义，程序的主要算法流程及各模块之间的层次调用关系

拓扑排序的基本思想是以下两点：

1、在有向图中选一个没有前驱的顶点且输出之。

2、从图中删除该顶点何所有以它为尾的弧。

3、 查邻接表中入度为零的顶点，并进栈。当栈为空时，进行

拓扑排序。

（a）退栈，输出栈顶元素V。

（b）在邻接表中查找Vj的直接后继Vk，将Vk的入度减

一，并令入度减至零的顶点进栈。

4、重复上述两步，直至全部顶点均已输出。如每输出完，则证明有环。

程序基本结构：

设定栈的抽象数据类型定义：

ADT Stack {

数据对象：D={|∈CharSet，i=1,2,3,…..,n,n＞=0;}

数据关系：R={＜， ＞|，∈D,i=2,…,n}

存储结构：

(1)表结点

typedef struct ArcNode

{

int adjvex;

struct ArcNode *nextarc;

}ArcNode;

(2)链表的存储结构

typedef struct VNode

{

int data;

ArcNode *firstarc;

}VNode,AdjList[MAX_VEXTEX_NUM];

(3)图的存储结构

typedef struct

{

AdjList vertices;

int vexnum, arcnum;

}ALGraph;

(4)栈的存储结构

typedef struct

{

ElemType *base;

ElemType *top;

int stacksize;

}SqStack;

三．程序设计

根据算法设计中给出的有关数据和算法，选定物理结构，详细设计需求分析中所要求的程序。包括：人机界面设计、主要功能的函数设计、函数之间调用关系描述等。

1界面设计

1）欢迎界面

2）输入顶点与边的关系，并得到拓扑排序

2主要功能

1）初始化栈

void InitStack(SqStack *S)//初始化栈

{

S-＞base = (ElemType *) malloc(STACK_INIT_SIZE * sizeof (ElemType));

if (!S-＞base) {

printf("memory allocation failed, goodbye");

exit(1);

}

S-＞top = S-＞base;

S-＞stacksize = STACK_INIT_SIZE;

}

2）出栈操作

int Pop(SqStack *S, ElemType *e)//出栈操作

{

if (S-＞top == S-＞base) {

return ERROR;

}

*e = *--S-＞top;

return 0;

}

3）进栈操作

void Push(SqStack *S, ElemType e)//进栈操作

{

if (S-＞top - S-＞base ＞= S-＞stacksize) {

S-＞base = (ElemType *) realloc(S-＞base, (S-＞stacksize + STACKINCREMENT) * sizeof (ElemType));

if (!S-＞base) {

printf("memory allocation failed, goodbye");

exit(1);

}

S-＞top = S-＞base + S-＞stacksize;

S-＞stacksize += STACKINCREMENT;

}

*S-＞top++ = e;

}

4）判断栈是否为空

int StackEmpty(SqStack *S)//判断栈是否为空

{

if (S-＞top == S-＞base)

return OK;

else

return ERROR;

}

5）构建图与欢迎界面

void CreatGraph(ALGraph *G)//构建图

{

int m, n, i;

ArcNode *p;

printf("************************************************\n");

printf(" 欢迎使用拓扑排序\n");

printf(" 制作者：----\n");

printf("************************************************\n");

printf("请输入顶点数和边数:");

scanf("%d%d", &G-＞vexnum, &G-＞arcnum);

for (i = 1; i ＜= G-＞vexnum; i++) {

G-＞vertices[i].data = i;

G-＞vertices[i].firstarc = NULL;

}

for (i = 1; i ＜= G-＞arcnum; i++) //输入存在边的点集合

{

printf("\n请输入存在边的两个顶点的序号:");

scanf("%d%d", &n, &m);

while (n ＜ 0 || n ＞ G-＞vexnum || m ＜ 0 || m ＞ G-＞vexnum) {

printf("输入的顶点序号不正确 请重新输入:");

scanf("%d%d", &n, &m);

}

p = (ArcNode*) malloc(sizeof (ArcNode));

if (p == NULL) {

printf("memory allocation failed,goodbey");

exit(1);

}

p-＞adjvex = m;

p-＞nextarc = G-＞vertices[n].firstarc;

G-＞vertices[n].firstarc = p;

}

}

6）找入度为零的结点

void FindInDegree(ALGraph G, int indegree[])//找入度为零的节点

{

int i;

for (i = 1; i ＜= G.vexnum; i++) {

indegree[i] = 0;

}

for (i = 1; i ＜= G.vexnum; i++) {

while (G.vertices[i].firstarc) {

indegree[G.vertices[i].firstarc-＞adjvex]++;

G.vertices[i].firstarc = G.vertices[i].firstarc-＞nextarc;

}

}

}

7）进行拓扑排序

void TopologicalSort(ALGraph G) //进行拓扑排序

{

int indegree[M];

int i, k, n;

int count = 0;

ArcNode *p;

SqStack S;

FindInDegree(G, indegree);

InitStack(&S);

for (i = 1; i ＜= G.vexnum; i++) {

if (!indegree[i])

Push(&S, i);

}

printf("进行拓扑排序输出顺序为:\n"); //输出结果

while (!StackEmpty(&S)) {

Pop(&S, &n);

printf("%4d", G.vertices[n].data);

count++;

for (p = G.vertices[n].firstarc; p != NULL; p = p-＞nextarc) {

k = p-＞adjvex;

if (!(--indegree[k])) {

Push(&S, k);

}

}

}

printf("\n");

if (count ＜ G.vexnum) {

printf("该有向图有回路");

} else {

printf("排序成功\n");

}

}

3函数调用

四．测试与分析

1、不知道怎么选择储存结构

2、在写代码的过程中，没有弄清使用指针与引用之后，结构体如何使用。当使用指针的时候要使用‘.’，当使用引用或数的时候，要使用‘-＞’。

3、出栈入栈的条件很混乱，不知道该怎么去使用栈。

经验与体会：这个程序，要求我们想的要尽量全面，要将所有情况考虑清楚，不仅有图的知识，还有对栈的灵活应用记。在程序的全面性与健壮性上，我做的还不够好。因为书上有代码，所以不是太难，在栈的那部分比较混乱，又复习了一遍，现在更好的掌握了栈的基本操作几项基本操作，也对拓扑序列有了更清楚的认识。

源程序：

#include＜STDIO.H＞

#include＜STDLIB.H＞

#define MAX_VEXTEX_NUM 20 //最大顶点个数#define M 20

#define STACK_INIT_SIZE 100

#define STACKINCREMENT 10

#define OK 1

#define M 20

#define ERROR 0

typedef int ElemType;

typedef struct ArcNode //定义表结点结构

{

int adjvex; //与vi相邻接的顶点编号

struct ArcNode *nextarc; //指向下一条弧(边)的指针

} ArcNode;

typedef struct VNode //定义表头结点结构

{

int data;

ArcNode *firstarc; //指向第一条弧（边）的指针

} VNode, AdjList[MAX_VEXTEX_NUM];

typedef struct //定义邻接表结构

{

AdjList vertices; //表头结点数组

int vexnum, arcnum; //顶点和弧（边）的个数

} ALGraph;

typedef struct //构件栈

{

ElemType *base;

ElemType *top;

int stacksize;

} SqStack;

void InitStack(SqStack *); //函数声明

int Pop(SqStack *, ElemType *);

void Push(SqStack *, ElemType);

int StackEmpty(SqStack *);

void CreatGraph(ALGraph *);

void FindInDegree(ALGraph, int *);

void TopologicalSort(ALGraph);

void InitStack(SqStack *S)//初始化栈

{

S-＞base = (ElemType *) malloc(STACK_INIT_SIZE * sizeof (ElemType));

if (!S-＞base) {

printf("memory allocation failed, goodbye");

exit(1);

}

S-＞top = S-＞base;

S-＞stacksize = STACK_INIT_SIZE;

}

int Pop(SqStack *S, ElemType *e)//出栈操作

{

if (S-＞top == S-＞base) {

return ERROR;

}

*e = *--S-＞top;

return 0;

}

void Push(SqStack *S, ElemType e)//进栈操作

{

if (S-＞top - S-＞base ＞= S-＞stacksize) {

S-＞base = (ElemType *) realloc(S-＞base, (S-＞stacksize + STACKINCREMENT) * sizeof (ElemType));

if (!S-＞base) {

printf("memory allocation failed, goodbye");

exit(1);

}

S-＞top = S-＞base + S-＞stacksize;

S-＞stacksize += STACKINCREMENT;

}

*S-＞top++ = e;

}

int StackEmpty(SqStack *S)//判断栈是否为空

{

if (S-＞top == S-＞base)

return OK;

else

return ERROR;

}

void CreatGraph(ALGraph *G)//构建图

{

int m, n, i;

ArcNode *p;

printf("************************************************\n");

printf(" 欢迎使用拓扑排序\n");

printf(" 制作者：---\n");

printf("************************************************\n");

printf("请输入顶点数和边数:");

scanf("%d%d", &G-＞vexnum, &G-＞arcnum);

for (i = 1; i ＜= G-＞vexnum; i++) {

G-＞vertices[i].data = i;

G-＞vertices[i].firstarc = NULL;

}

for (i = 1; i ＜= G-＞arcnum; i++) //输入存在边的点集合

{

printf("\n请输入存在边的两个顶点的序号:");

scanf("%d%d", &n, &m);

while (n ＜ 0 || n ＞ G-＞vexnum || m ＜ 0 || m ＞ G-＞vexnum) {

printf("输入的顶点序号不正确 请重新输入:");

scanf("%d%d", &n, &m);

}

p = (ArcNode*) malloc(sizeof (ArcNode));

if (p == NULL) {

printf("memory allocation failed,goodbey");

exit(1);

}

p-＞adjvex = m;

p-＞nextarc = G-＞vertices[n].firstarc;

G-＞vertices[n].firstarc = p;

}

}

void FindInDegree(ALGraph G, int indegree[])//找入度为零的节点

{

int i;

for (i = 1; i ＜= G.vexnum; i++) {

indegree[i] = 0;

}

for (i = 1; i ＜= G.vexnum; i++) {

while (G.vertices[i].firstarc) {

indegree[G.vertices[i].firstarc-＞adjvex]++;

G.vertices[i].firstarc = G.vertices[i].firstarc-＞nextarc;

}

}

}

void TopologicalSort(ALGraph G) //进行拓扑排序

{

int indegree[M];

int i, k, n;

int count = 0;

ArcNode *p;

SqStack S;

FindInDegree(G, indegree);

InitStack(&S);

for (i = 1; i ＜= G.vexnum; i++) {

if (!indegree[i])

Push(&S, i);

}

printf("进行拓扑排序输出顺序为:\n"); //输出结果

while (!StackEmpty(&S)) {

Pop(&S, &n);

printf("%4d", G.vertices[n].data);

count++;

for (p = G.vertices[n].firstarc; p != NULL; p = p-＞nextarc) {

k = p-＞adjvex;

if (!(--indegree[k])) {

Push(&S, k);

}

}

}

printf("\n");

if (count ＜ G.vexnum) {

printf("该有向图有回路");

} else {

printf("排序成功\n");

}

}

int main(void) //主函数

{

ALGraph G;

CreatGraph(&G);

TopologicalSort(G);

system("pause");

return 0;

}