数据结构课程设计(6)

if(i==0) {

printf(\数据结构基本内容\\n\\n\\n\ printf(\单链表基本操作\\n\\n\ printf(\二叉树基本操作\\n\\n\ printf(\表达式求值\\n\\n\

printf(\二叉排序树基本操作\\n\\n\ printf(\最小生成树\\n\\n\ printf(\拓扑排序\\n\\n\ printf(\ printf(\ } }

拓扑排序的头文件 #ifndef _TOPSORT_H #define _TOPSORT_H #define MaxVex 20 typedef struct node {

int vexw;

struct node*next; }JD;//邻接表结点 typedef struct tnode {

int vex; int in;

struct node*link; }TD;//表头结点

typedef struct ALGraph {

TD header[MaxVex]; int vexnum; int arcnum; }ALGraph;

typedef struct Stack2 {

int*base; int top; }Stack2;

void InitStack(Stack2 &s); int Empty(Stack2 s);

void Push(Stack2 &s,int e);

图\\n\\n\

退出程序。\\n\\n\\n\\n\24

void Pop(Stack2 &s,int &e); void CreateAlGraph(ALGraph &G); void TopoSort(ALGraph G); void TopSortmenu(); #endif

拓扑排序的源文件 #include #include #include\

void InitStack(Stack2 &s) {

s.base=(int*)malloc(MaxVex*sizeof(int)); s.top=-1; }

int Empty(Stack2 s) {

if(s.top==-1) return 1; return 0; }

void Push(Stack2 &s,int e) {

s.base[++s.top]=e; }

void Pop(Stack2 &s,int &e) {

e=s.base[s.top--]; }

void CreateAlGraph(ALGraph &G) {

int i,k; int v1,v2;

int point1,point2; JD*p;

printf(\输入有向图顶点个数：\\n\ scanf(\

printf(\输入有向图的弧个数：\\n\ scanf(\

printf(\输入图的顶点信息:\\n\ for(i=0;i

scanf(\ }

25

for(i=0;i

G.header[i].link=NULL; G.header[i].in=0; }

for(i=0;i

printf(\输入第%d条弧的弧尾和弧头:\ scanf(\ k=0;

while(k

if(v1==G.header[k].vex) {

point1=k; break; } k++; } k=0;

while(k

if(v2==G.header[k].vex) {

point2=k; break; } k++; }

G.header[point2].in++; p=(JD*)malloc(sizeof(JD)); p->vexw=point2;

p->next=G.header[point1].link; G.header[point1].link=p; } }

void TopoSort(ALGraph G) {

int i,e,n=0; JD*p; Stack2 s; InitStack(s);

for(i=0;i

26

if(G.header[i].in==0) Push(s,i); }

while(!Empty(s)) {

Pop(s,e);

printf(\ n++;

p=G.header[e].link; while(p) {

G.header[p->vexw].in--; if(G.header[p->vexw].in==0) Push(s,p->vexw); p=p->next; } }

if(n

printf(\该图为有向有环图。\ } }

拓扑排序的菜单文件 #include #include #include\void TopSortmenu() {

ALGraph G; int i; while(1) {

printf(\ printf(\你输入的是6功能: 拓扑排序基本内容\\n\

printf(\ printf(\拓扑排序\\n\\n\\n\ printf(\创建有向图\\n\\n\ printf(\拓扑排序\\n\\n\

printf(\退出程序。\\n\\n\\n\\n\ scanf(\ if(i==0) {

printf(\数据结构基本内容\\n\\n\\n\ printf(\单链表基本操作\\n\\n\

27

printf(\二叉树基本操作\\n\\n\ printf(\表达式求值\\n\\n\

printf(\二叉排序树基本操作\\n\\n\ printf(\最小生成树\\n\\n\ printf(\拓扑排序\\n\\n\ printf(\图\\n\\n\

printf(\退出程序。\\n\\n\\n\\n\ break; }

else if(i==1)CreateAlGraph(G); else if(i==2) {

printf(\拓扑排序为：\ TopoSort(G); } else

printf(\输入选择错误！请重新输入\\n \ } }

图的建立与遍历的头文件 #ifndef _GRAPH_H #define _GRAPH_H

#define MAX_VERTEX_NUM 20 #define maxqsize 20 typedef struct {

int*base; int front; int rear; }SqQueue;

typedef struct {

int vexs[MAX_VERTEX_NUM];

int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; //邻接矩阵 int vexnum; //图的顶点数 int arcnum; //图的弧数 }MGraph;

void InitQueue(SqQueue &Q); int EmptyQueue(SqQueue Q);

void EnQueue(SqQueue &Q,int e); void DeQueue(SqQueue &Q,int &e);

void CreateGraph(MGraph &G,int kind); void PrintGraph(MGraph G);

void BFSTraverse(MGraph G,int *visited);//图广度遍历

28