沈阳工程学院-数据结构课设报告(8)

沈阳工程学院课程设计 第四章 系统功能实现

ArcNode *p= new ArcNode;//建立结点 if(!p) return ERROR;

p->adjvex=w-1;

p->nextarc=G.vertices[v-1].firstarc;//顶点v的链表 G.vertices[v-1].firstarc=p;//添加到最左边

}

return OK; }

当输入课程数目大于12时，系统显示错误并要求重新输入课程数目；输入课程间的先后关系数即弧的数目；如图4.4所示。

图4.4输入课程数目和输入课程间的先后关系数目

输入课程的代表值即课程编号如图4.5所示。

图4.5输入课程的代表值

输入课程的代表值即课程间两两的先后关系即输入弧，如图4.6所示。

图4.6输入课程的代表值即课程间两两的先后关系

4.2.4求图的入度函数

本功能模块主要是通过源程序的编写实现的。对使用者在使用该软件时进行提示如下。本程序为求图的入度函数，初始化图后需要求出图中各个地点的入度数，并将结果保存到整型数组indegree中，为拓扑排序做准备。具体代码如下：

23

沈阳工程学院课程设计 第四章 系统功能实现

//求图的入度

void FindInDegree(ALGraph G)

{

ArcNode* p;

for(int i=0;i

{

p=G.vertices[i].firstarc;//取出第i个顶点，将由该顶点所出发的弧所对应的弧尾结点的入度加1

while(p) {

for(int j=0;j

if(p->adjvex==j) indegree[j]++; p=p->nextarc; } } }

4.2.5拓扑排序函数

本功能模块主要是通过源程序的编写实现的。对使用者在使用该软件时进行提示如下。本程序为拓扑排序过程，首先将入度为i（初始i=0）的顶点入栈S1并对输出顶点计数，然后在栈不为空的情况下输出入度为i的顶点对应的编号及课程名，再把顶点压入栈S2 ；计数；对i号顶点的每个邻接点的入度减1，若入度减为0,则压入栈S1...重复循环；判断若有向图有回路则返回ERROR，反知无回路则返回OK。具体代码如下：

//拓扑排序

Status TopologicalSort(ALGraph G) {

//有向图G采用邻接表存储结构

SqStack S1,S2; ArcNode* p; int i,count,k; FindInDegree(G); InitStack(S1); InitStack(S2);

for(i=0;i

Push(S1,i); //把入度为i的压入栈S1

24

沈阳工程学院课程设计 第四章 系统功能实现

count=0; //对输出顶点计数 while(!StackEmpty(S1)) {

while(!StackEmpty(S1)) {

Pop(S1,i);

printf(\

printf(\输出i号顶点 Push(S2,i); //把i号顶点压入栈S2 }

count++; //计数

while(!StackEmpty(S2)) {

Pop(S2,i);

for(p=G.vertices[i].firstarc;p;p=p->nextarc) {

k=p->adjvex; //对i号顶点的每个邻接点的入度减1 if(!(--indegree[k])) //若入度减为0,则入栈 Push(S1,k); } }

}

if(count

4.2.6主函数和菜单函数

主函数是程序的入口，采用模块化设计。本功能模块主要是通过源程序的编写实现的主函数菜单界面。先对string（字符串赋值）赋予课程名。然后调用CreateDG函数开始以建立邻接表建立。再调用TopologicalSort函数，经拓扑排序来实现教学计划安排的算法。对使用者在使用该软件时进行提示如何进行操作。对使用者在使用该软件时进行提示如何进行操作。主要程序代码如下：

//主函数 int main() {

ALGraph G;

25

沈阳工程学院课程设计 第四章 系统功能实现

printf(\┏━━━━━━━━━━━━━━━━━━━━━━━━━━━┓\\n\ printf(\┃ ★ ☆欢迎使用教学计划安排系统☆★ ┃\\n\ printf(\┣━━━━━━┳━━━━━━━━━┳━━━━━━━━━━┫\\n\ printf(\┃【课程编号】┃ 【课程名】 ┃ 【先决条件】 ┃\\n\ printf(\┣━━━━━━╋━━━━━━━━━╋━━━━━━━━━━┫\\n\ printf(\┃ C1 ┃ 程序设计基础 ┃ 无 ┃\\n\ printf(\┃ C2 ┃ 离散数学 ┃ C1 ┃\\n\ printf(\┃ C3 ┃ 数据结构 ┃ C1, C2 ┃\\n\ printf(\┃ C4 ┃ 汇编语言 ┃ C1 ┃\\n\ printf(\┃ C5 ┃ 语言的设计和分析 ┃ C3, C4 ┃\\n\ printf(\┃ C6 ┃ 计算机原理 ┃ C11 ┃\\n\ printf(\┃ C7 ┃ 编译原理 ┃ C5, C3 ┃\\n\ printf(\┃ C8 ┃ 操作系统 ┃ C3, C6 ┃\\n\ printf(\┃ C9 ┃ 高等数学 ┃ 无 ┃\\n\ printf(\┃ C10 ┃ 线性代数 ┃ C9 ┃\\n\ printf(\┃ C11 ┃ 普通物理 ┃ C9 ┃\\n\ printf(\┃ C12 ┃ 数值分析 ┃ C9, C10, C11 ┃\\n\ printf(\┗━━━━━━┻━━━━━━━━━┻━━━━━━━━━━┛\\n\ printf(\望使用上述课程编号及课程名！\\n\ strcpy(G.vertices[0].string, \程序设计基础\ strcpy(G.vertices[1].string, \离散数学\

strcpy(G.vertices[2].string, \数据结构\ strcpy(G.vertices[3].string, \汇编语言\

strcpy(G.vertices[4].string, \语言的设计和分析\ strcpy(G.vertices[5].string, \计算机原理\ strcpy(G.vertices[6].string, \编译原理\ strcpy(G.vertices[7].string, \操作系统\ strcpy(G.vertices[8].string, \高等数学\ strcpy(G.vertices[9].string, \线性代数\ strcpy(G.vertices[10].string, \普通物理\ strcpy(G.vertices[11].string, \数值分析\ printf(\初始化完成！\ CreateDG(G);

TopologicalSort(G); system(\ return 0; }

26

沈阳工程学院课程设计 第四章 系统功能实现

功能实现图及主菜单运行界面如图4.7所示。

图4.7 主菜单运行界面

按给定的课程编号，课程名，先决条件输入如图4.8所示。

图4.8输入所有条件

27