《数 据 结 构》
课程设计报告书
设计题目： 安排教学计划
专 业: 计算机科学与技术(师范)
班 级： 10 级 1 班
姓 名： 关莹(李瑞男)
指导教师： 孙 蕾
目录
1、问题描述......................................................... 2
2、基本要求......................................................... 2
3、测试数据......................................................... 2
4、算法思想......................................................... 3
5、模块划分......................................................... 3
6、数据结构......................................................... 5
7、源程序............................................................ 5
8、界面设计....................................................... 14
9、运行与测试................................................... 14
10、总结............................................................ 19
11、思考与感悟.................................................. 19
1、问题描述
学校每个学期开设的课程是有先后顺序的，如计算机专业：开设《数据结构》课程之前，必须先开设《C语言程序设计》和《离散数学》课程，这种课程开设的先后顺序关系称为先行、后继课程关系。现在需要根据给定的课程信息及课程之间的先行、后继关系，合理安排出开设各门课程的先后顺序。
2、基本要求
1)对输入的课程先行、后继关系如果存在回路关系时应提示出现错误。
2)根据读入的课程信息及其先行、后继关系，计算出安排教学计划的序列。
3)输出教学计划的安排顺序或给出错误提示信息。
3、测试数据
正确结果：
输入：顶点数6，弧数7。
顶点为A、B、C、D、E、F。
顶点关系为 A B、A C、B C、C D、C E、D E、E F。
输出：A->B->C->D->E->F
错误结果
1）输入：顶点数1，弧数5。
输出：顶点数或弧数不正确，有向图建立失败！
2）输入：顶点数6，弧数8。
顶点为A、B、C、D、E、F。
顶点关系为A B、AG。
输出：顶点G不存在，有向图建立失败！
3）输入：顶点数6，弧数8。
顶点为A、B、C、D、E、F。
顶点关系为A B、A C、B C、C D、C E、D E、E F、F D。
输出：该有向图有回路，无法完成拓扑排序。
4、算法思想
1、采用邻接表存储结构实现有向图；有向图需通过顶点数、弧数、顶点以及弧等信息建立。
2、拓扑排序算法void TopologicalSort(ALGraph G) 中，先输出入度为零的顶点，然后输出新的入度为零的顶点，此操作利用栈实现。
3、拓扑排序算法void TopologicalSort(ALGraph G)，大体思想为：
1)遍历有向图各顶点的入度，将所有入度为零的顶点入栈；
2)栈非空时，输出一个顶点，并对输出的顶点数计数；
3)该顶点的所有邻接点入度减一，若减一后入度为零则入栈；
4)重复2)、3)，直到栈空，若输出的顶点数与图的顶点数相等则该图可拓扑排序，否则图中有环；
5、模块划分
1、顺序栈操作
1) void Initstack(ssqstack *S)
功能：初始化顺序栈
2) int emptystack(sqstack S)
功能：判断栈空。栈空返回 1；栈非空返回 0
3) int push(sqstack *S,ElemType e)
功能：元素入栈
4) int pop(sqstack *S,ElemType *e)
功能：元素出栈
2、有向图(DAG)邻接表存储结构(ALG)的操作
1) int LocateVex(ALGraph G,VertexType v)
功能：顶点在头结点数组中的定位
2) int CreateGraph(ALGraph *G)
功能：建立图。函数内包含了由用户输入顶点数、弧数、顶点以及弧的操作
错误判断：包含顶点数、弧数是否正确的判断；包含用户输入的弧的顶点是否存在的判断
3) void PrintGraph(ALGraph G)
功能：输出有向图
4) int CreateGraph2(ALGraph *G)
功能：建立预置课程图（输出函数内预置课程信息，并自动建立有向图）图建立成功返回1；图建立失败返回0
错误判断：包含顶点数、弧数是否正确的判断。包含弧的顶点是否存在的判断
3、拓扑排序
1) void TopologicalSort(ALGraph G)
功能：实现拓扑排序
错误判断：包含有向图是否有回路的判断
4、主函数
void main()
功能：主函数。利用while语句和switch语句实现菜单化调用函数
各模块之间的调用关系图：
6、数据结构
1、顺序栈的存储类型为：
typedef int ElemType;
typedef struct QNode
{ int top;
ElemType *base;
Int stacksize;
} QNode,sqstack;
理由：用栈来存储入度为0的顶点，符合栈先进后出的特点。
2、图的类型（邻接表存储结构）为：
typedef char VertexType[20];//顶点信息（名称）
typedef struct ArcNode//链表结点
{ int vexpos;//该弧所指向的顶点在数组中的位置
struct ArcNode *next;//指向当前起点的下一条弧的指针
} ArcNode;
typedef struct VNode//头结点
{ VertexType name;//顶点信息（名称）
int indegree;//顶点入度
ArcNode *firstarc;//指向当前顶点的第一条弧的指针
} VNode,AdjList[MAXVEX];
typedef struct
{ AdjList vexhead;//邻接表头结点数组
int vexnum,arcnum;//图的顶点数和弧数
} ALGraph;
理由：此程序的有向图为稀疏图，符合邻接表的特点。
7、源程序
(1)程序中包括的文件清单：1.c
(2)文件中包括的函数清单：
1）顺序栈：void Initstack(ssqstack *S)
2）有向图邻接表：void PrintGraph(ALGraph G)
int CreateGraph2(ALGraph *G)
3）拓扑排序：void TopologicalSort(ALGraph G)
(3)源程序
#include "stdlib.h"
#include "stdio.h"
#include "string.h"//字符数组
/*******************************************/
/* 以下为顺序栈操作 */
/*******************************************/
/* 定义顺序栈类型 */
#define MAXNUM 30
#define INITSIZE 100
typedef int ElemType;
typedef struct QNode
{ int top;
ElemType *base;
int stacksize;
} QNode,sqstack;
/* 1.初始化 */
void Initstack(sqstack *S)
{ S->base=(ElemType *)malloc(INITSIZE*sizeof(ElemType));
S->top=0;
S->stacksize=INITSIZE;
}
/* 2.判断栈空 */
int emptystack(sqstack S)
{ if(S.top==0)
return 1;
else
return 0; }
/* 3.入栈 */
int push(sqstack *S, ElemType e)
{
if(S->top>=S->stacksize);
{S->base=(ElemType *)realloc(S->base,(S->stacksize+1) *sizeof(ElemType));
if(!S->base) return 0;
S->stacksize++;
}
S->base[S->top++]=e;
return 1;
}
/* 4.出栈 */
int pop(sqstack *S,ElemType *e)//*e记录出栈元素的变量
{ //int i;
if(S->top==0) return 0;
*e=S->base[--S->top];
return 1;
}
/****************************************************/
/* 以下为有向图(DAG)邻接表存储结构(ALG)的操作 */
/****************************************************/
#define MAXVEX 30 //最大顶点个数
#define MAXNAME 20
typedef char VertexType[20]; //顶点信息（名称）
/* 图的类型定义（邻接表存储结构） */
typedef struct ArcNode //链表结点
{ int vexpos; //该弧所指向的顶点在数组中的位置
struct ArcNode *next; //指向当前起点的下一条弧的指针
} ArcNode;
typedef struct VNode //头结点
{ VertexType name; //顶点信息（名称）
int indegree; //顶点入度
ArcNode *firstarc; //指向当前顶点的第一条弧的指针
} VNode,AdjList[MAXVEX];
typedef struct
{ AdjList vexhead; //邻接表头结点数组
int vexnum,arcnum; //图的顶点数和弧数
} ALGraph;
/* 5.顶点在头结点数组中的定位 */
int LocateVex(ALGraph G,VertexType v)//G带操作的图；v要在图中定位的顶点
{ int i;
for(i=0;i<G.vexnum;i++)
if(strcmp(v,G.vexhead[i].name)==0) break;
return i; }//顶点存在则返回在头结点数组中的下标；否则返回图的定点数
/* 6.建立图（邻接表） */
int CreateGraph(ALGraph *G) //成功建立返回1，不成功则返回0
{ int i,j,k; VertexType v1,v2;ArcNode *newarc;
printf("\n输入有向图顶点数和弧数vexnum,arcnum:"); //输入顶点数和弧数
scanf("%d,%d",&(*G).vexnum,&(*G).arcnum); //输入并判断顶点数和弧数是否正确
if((*G).vexnum<0||(*G).arcnum<0||(*G).arcnum>(*G).vexnum*((*G).vexnum-1))
{ printf("\n顶点数或弧数不正确，有向图建立失败！\n");return 0; }
printf("\n输入 %d 个顶点:",(*G).vexnum); //输入顶点名称
for(i=0;i<(*G).vexnum;i++)
{ scanf("%s",(*G).vexhead[i].name); }
printf("\n顶点列表:\n共有%d个顶点: ",(*G).vexnum);//输出顶点名称
for(i=0;i<(*G).vexnum;i++)
printf("%s ",(*G).vexhead[i].name);
for(i=0;i<(*G).vexnum;i++) //邻接表初始化
{ (*G).vexhead[i].firstarc=NULL;
(*G).vexhead[i].indegree=0;}
printf("\n\n输入 %d 条边:vi vj\n",(*G).arcnum); //输入有向图的边
for(k=0;k<(*G).arcnum;k++)
{ scanf("%s%s",v1,v2); //v1是弧的起点（先决条件），v2是弧的终点
i=LocateVex(*G,v1);j=LocateVex(*G,v2); //定位顶点并判断顶点是否存在
if(i>=(*G).vexnum)
{ printf("顶点%s不存在，有向图建立失败！\n",v1);return 0; } if(j>=(*G).vexnum)
{ printf("顶点%s不存在，有向图建立失败！\n",v2);return 0; }
newarc=(ArcNode*)malloc(sizeof(ArcNode)); //前插法建顶点链表
newarc->vexpos=j;
if((*G).vexhead[i].firstarc==NULL)
{ newarc->next=NULL;
(*G).vexhead[i].firstarc=newarc; }
else
{ newarc->next=(*G).vexhead[i].firstarc->next;
(*G).vexhead[i].firstarc->next=newarc; }
(*G).vexhead[j].indegree++; //对应顶点入度计数加1
}
printf("\n有向图建立成功！\n");
return 1;
}
/* 7.按邻接表方式输出有向图 */
void PrintGraph(ALGraph G)
{ int i;ArcNode *p;
printf("\n输出有向图:\n");
for(i=0; i<G.vexnum; i++)
{ printf("\n顶点:%s ",G.vexhead[i].name);
printf("入度:%3d\n",G.vexhead[i].indegree);
p=G.vexhead[i].firstarc;
printf("邻接点:");
while(p!=NULL)
{ printf("%s ",G.vexhead[p->vexpos].name);
p=p->next; }
printf("\n");
}
}
//为避免演示时要输入过多数据，以下函数将课程编号、课程间的先后关系通过数组预置
/* 8.建立预置课程图（邻接表） */
int CreateGraph2(ALGraph *G) //成功建立返回1，不成功则返回0
{ int i,j,k; VertexType v1,v2; ArcNode *newarc;
VertexType SubjectName[12]={ "C1","C2","C3","C4", //课程名称
"C5","C6","C7","C8",
"C9","C10","C11","C12" },
RelationV1[16]={ "C1","C1","C2","C1", //基础课
"C3","C4","C11","C5",
"C3","C3","C6","C9",
"C9","C9","C10","C11"},
RelationV2[16]={ "C2","C3","C3","C4", //以上面课程为基础的课
"C5","C5","C6","C7",
"C7","C8","C8","C10",
"C11","C12","C12","C12",};
//********************************************************************
//system("PAUSE");
(*G).vexnum=12; (*G).arcnum=16;
if((*G).vexnum<0||(*G).arcnum<0||(*G).arcnum>(*G).vexnum*((*G).vexnum-1))
{ printf("\n课程数或先后关系不正确，有向图建立失败！\n");
return 0;} //判断课程数和弧数是否正确
for(i=0;i<(*G).vexnum;i++)
{ strcpy((*G).vexhead[i].name,SubjectName[i]); }
for(i=0;i<(*G).vexnum;i++) //邻接表初始化
{ (*G).vexhead[i].firstarc=NULL;
(*G).vexhead[i].indegree=0; }
for(k=0;k<(*G).arcnum;k++)
{ strcpy(v1,RelationV1[k]); strcpy(v2,RelationV2[k]);
i=LocateVex(*G,v1);j=LocateVex(*G,v2); //定位课程并判断课程是否存在
if(i>=(*G).vexnum)
{ printf("课程%s不存在，有向图建立失败！\n",v1);return 0; }
if(j>=(*G).vexnum)
{ printf("课程%s不存在，有向图建立失败！\n",v2);return 0; }
newarc=(ArcNode*)malloc(sizeof(ArcNode)); //前插法建课程链表
newarc->vexpos=j;
if((*G).vexhead[i].firstarc==NULL)
{ newarc->next=NULL;
(*G).vexhead[i].firstarc=newarc; }
else
{ newarc->next=(*G).vexhead[i].firstarc->next;
(*G).vexhead[i].firstarc->next=newarc; }
(*G).vexhead[j].indegree++; //对应课程入度计数加1
}
printf("\n有向图建立成功！\n");
return 1;
}
/**********************************/
/* 以下为拓扑排序算法 */
/**********************************/
/* 9.拓扑排序 */
void TopologicalSort(ALGraph G)
{ int i,k,count;ElemType e;ArcNode *p;//弧结点，指向边表结点的指针
sqstack S; /*定义栈*/
Initstack(&S);
for(i=0; i<G.vexnum; i++) //零入度课程入栈
if(!G.vexhead[i].indegree) push(&S,i);
count=0; //对输出课程计数变量初始化
printf("\n\n\n以上课程的一个拓扑排序序列为:\n");
while(!emptystack(S))
{ pop(&S,&e); //先将入度为零的课程输出
printf("%s->",G.vexhead[e].name);
count++; //对输出的顶点计数
for(p=G.vexhead[e].firstarc;p;p=p->next) //遍历当前课程的邻接点
{ k=p->vexpos; //邻接点位置
if(!(--G.vexhead[k].indegree)) //每个邻接点入度减1后若为零则入栈
push(&S,k);
}
}
printf("\n");
if(count<G.vexnum)
{ printf("\n该有向图有回路，无法完成拓扑排序！\n"); }
}
void main()
{ ALGraph G; int menu;
while(1){
printf("\n **********************************************\n");
printf(" * 1.建立有向图并求一个拓扑排序序列 *\n");
printf(" * 2.清屏 *\n");
printf(" * 3.退出 *\n");
printf(" **********************************************\n");
printf(" 请输入你的选择:");
scanf("%d",&menu);
switch(menu){
case 1:
if(CreateGraph(&G)) //有向图建成则执操作
{ system("PAUSE");//暂停，等待用户按键
PrintGraph(G);system("PAUSE");//按邻接表方式输出有向图
TopologicalSort(G); }//拓扑排序
break;
case 2:
system("CLS");//清屏
break;
case 3:
return;//退出当前函数，返回调用点
}
}
}
8、界面设计
运行程序后显示菜单，选择1建立有向图并求出一个拓扑排序序列。根据提示输入有向图定点数和弧数vexnum,arcnum。输入顶点，然后再输入边。程序会根据用户所输入的数据输出每个定点的入度、邻接点及拓扑排序结果。选择2为清屏，选择3为退出程序。
9、运行与测试
1. 主界面
2.选择1建立有向图并求一个拓扑排序序列，输入顶点并输出。
3.输入有向图的弧，有向图建立成功。
4.输出各顶点的入度及邻接点
5.根据用户的输入信息输出一个拓扑排序序列
6.若输入错误的顶点和弧数信息
7.若输入弧的顶点不存在
8.若存在回路
10、总结
(1) 邻接表：占用空间少，节省空间。有向图容易求顶点出度。求入度不容易，要遍历整个表。
拓扑排序：可以让许多混乱无序的点变得容易扩展。
(2)邻接表：T(n)=O(e) S(n)=O(n+e)
(3)还可以用队列来存储入度为0的点，利用邻接矩阵存储邻接点；
(4)功能拓展：可以输出有向图各个顶点及其入度数与邻接点，让用户一目了然。
(5)帮助：让用户自己输入一个拓扑序列，程序对其正确与否进行检测。
11、思考与感悟
刚开始不知道从哪里入手，后来根据老师给的提示，自己也查阅了一些有关拓扑排序的资料，渐渐地理出了头绪。有时候错误很多，但只要改对一个地方就没有错误了。
通过课程设计，我们对图的概念、拓扑排序有了新的认识。无论是从学习上还是从自身角度，都得到了很大的提高。发现了许多在理论学习中无法发现的问题。同时，通过自己的努力，顺利的解决了这些问题，这也是一种磨砺。
这次课程设计，为我们提供了与众不同的学习方法和学习机会。通过c语言完成课程设计，让我们从传统上的被动授学，转变为主动求学。形成了在实践中学习的能力，增强了领悟能力和解决问题能力。