数据结构课程报告书Word文档下载推荐.docx
《数据结构课程报告书Word文档下载推荐.docx》由会员分享，可在线阅读，更多相关《数据结构课程报告书Word文档下载推荐.docx（19页珍藏版）》请在冰点文库上搜索。
该有向图有回路，无法完成拓扑排序。
4、算法思想
1、采用邻接表存储结构实现有向图；
有向图需通过顶点数、弧数、顶点以及弧等信息建立。
2、拓扑排序算法voidTopologicalSort（ALGraphG）中，先输出入度为零的顶点，然后输出新的入度为零的顶点，此操作利用栈实现。
3、拓扑排序算法voidTopologicalSort（ALGraphG），大体思想为：
1）遍历有向图各顶点的入度，将所有入度为零的顶点入栈；
2）栈非空时，输出一个顶点，并对输出的顶点数计数；
3）该顶点的所有邻接点入度减一，若减一后入度为零则入栈；
4）重复2）、3），直到栈空，若输出的顶点数与图的顶点数相等则该图可拓扑排序，否则图中有环；
5、模块划分
1、顺序栈操作
1）voidInitstack（ssqstack*S）
功能：
初始化顺序栈
2）intemptystack（sqstackS）
判断栈空。
栈空返回1；
栈非空返回0
3）intpush（sqstack*S,ElemTypee）
元素入栈
4）intpop（sqstack*S,ElemType*e）
元素出栈
2、有向图（DAG）邻接表存储结构（ALG）的操作
1）intLocateVex（ALGraphG,VertexTypev）
顶点在头结点数组中的定位
2）intCreateGraph（ALGraph*G）
建立图。
函数内包含了由用户输入顶点数、弧数、顶点以及弧的操作
错误判断：
包含顶点数、弧数是否正确的判断；
包含用户输入的弧的顶点是否存在的判断
3）voidPrintGraph（ALGraphG）
输出有向图
4）intCreateGraph2（ALGraph*G）
建立预置课程图（输出函数内预置课程信息，并自动建立有向图）图建立成功返回1；
图建立失败返回0
包含顶点数、弧数是否正确的判断。
包含弧的顶点是否存在的判断
3、拓扑排序
1）voidTopologicalSort（ALGraphG）
实现拓扑排序
包含有向图是否有回路的判断
4、主函数
voidmain（）
主函数。
利用while语句和switch语句实现菜单化调用函数
各模块之间的调用关系图：
6、数据结构
1、顺序栈的存储类型为：
typedefintElemType;
typedefstructQNode
{inttop;
ElemType*base;
Intstacksize;
}QNode,sqstack;
理由：
用栈来存储入度为0的顶点，符合栈先进后出的特点。
2、图的类型（邻接表存储结构）为：
typedefcharVertexType[20];
//顶点信息（名称）
typedefstructArcNode//链表结点
{intvexpos;
//该弧所指向的顶点在数组中的位置
structArcNode*next;
//指向当前起点的下一条弧的指针
}ArcNode;
typedefstructVNode//头结点
{VertexTypename;
intindegree;
//顶点入度
ArcNode*firstarc;
//指向当前顶点的第一条弧的指针
}VNode,AdjList[MAXVEX];
typedefstruct
{AdjListvexhead;
//邻接表头结点数组
intvexnum,arcnum;
//图的顶点数和弧数
}ALGraph;
此程序的有向图为稀疏图，符合邻接表的特点。
7、源程序
（1）程序中包括的文件清单：
1.c
（2）文件中包括的函数清单：
1）顺序栈：
voidInitstack（ssqstack*S）
2）有向图邻接表：
voidPrintGraph（ALGraphG）
intCreateGraph2（ALGraph*G）
3）拓扑排序：
voidTopologicalSort（ALGraphG）
（3）源程序
#include"
stdlib.h"
stdio.h"
string.h"
//字符数组
/*******************************************/
/*以下为顺序栈操作*/
/*定义顺序栈类型*/
#defineMAXNUM30
#defineINITSIZE100
ElemType*base;
intstacksize;
/*1.初始化*/
voidInitstack（sqstack*S）
{S->
base=（ElemType*）malloc（INITSIZE*sizeof（ElemType））;
S->
top=0;
stacksize=INITSIZE;
}
/*2.判断栈空*/
intemptystack（sqstackS）
{if（S.top==0）
return1;
else
return0;
}
/*3.入栈*/
intpush（sqstack*S,ElemTypee）
{
if（S->
top>
=S->
stacksize）;
{S->
base=（ElemType*）realloc（S->
base,（S->
stacksize+1）*sizeof（ElemType））;
if（!
S->
base）return0;
stacksize++;
base[S->
top++]=e;
return1;
/*4.出栈*/
intpop（sqstack*S,ElemType*e）//*e记录出栈元素的变量
{//inti;
top==0）return0;
*e=S->
base[--S->
top];
/****************************************************/
/*以下为有向图（DAG）邻接表存储结构（ALG）的操作*/
#defineMAXVEX30//最大顶点个数
#defineMAXNAME20
//顶点信息（名称）
/*图的类型定义（邻接表存储结构）*/
typedefstructArcNode//链表结点
//该弧所指向的顶点在数组中的位置
//指向当前起点的下一条弧的指针
typedefstructVNode//头结点
//顶点入度
//指向当前顶点的第一条弧的指针
//邻接表头结点数组
//图的顶点数和弧数
/*5.顶点在头结点数组中的定位*/
intLocateVex（ALGraphG,VertexTypev）//G带操作的图；
v要在图中定位的顶点
{inti;
for（i=0;
i<
G.vexnum;
i++）
if（strcmp（v,G.vexhead[i].name）==0）break;
returni;
}//顶点存在则返回在头结点数组中的下标；
否则返回图的定点数
/*6.建立图（邻接表）*/
intCreateGraph（ALGraph*G）//成功建立返回1，不成功则返回0
{inti,j,k;
VertexTypev1,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"
return0;
\n输入%d个顶点:
（*G）.vexnum）;
//输入顶点名称
（*G）.vexnum;
{scanf（"
%s"
（*G）.vexhead[i].name）;
\n顶点列表:
\n共有%d个顶点:
"
//输出顶点名称
printf（"
%s"
i++）//邻接表初始化
{（*G）.vexhead[i].firstarc=NULL;
（*G）.vexhead[i].indegree=0;
\n\n输入%d条边:
vivj\n"
（*G）.arcnum）;
//输入有向图的边
for（k=0;
k<
（*G）.arcnum;
k++）
%s%s"
v1,v2）;
//v1是弧的起点（先决条件），v2是弧的终点
i=LocateVex（*G,v1）;
j=LocateVex（*G,v2）;
//定位顶点并判断顶点是否存在
if（i>
=（*G）.vexnum）
{printf（"
顶点%s不存在，有向图建立失败！
v1）;
}if（j>
v2）;
newarc=（ArcNode*）malloc（sizeof（ArcNode））;
//前插法建顶点链表
newarc->
vexpos=j;
if（（*G）.vexhead[i].firstarc==NULL）
{newarc->
next=NULL;
（*G）.vexhead[i].firstarc=newarc;
else
next=（*G）.vexhead[i].firstarc->
next;
（*G）.vexhead[i].firstarc->
next=newarc;
（*G）.vexhead[j].indegree++;
//对应顶点入度计数加1
}
\n有向图建立成功！
/*7.按邻接表方式输出有向图*/
ArcNode*p;
\n输出有向图:
i<
i++）
\n顶点:
G.vexhead[i].name）;
printf（"
入度:
%3d\n"
G.vexhead[i].indegree）;
p=G.vexhead[i].firstarc;
邻接点:
while（p!
=NULL）
G.vexhead[p->
vexpos].name）;
p=p->
//为避免演示时要输入过多数据，以下函数将课程编号、课程间的先后关系通过数组预置
/*8.建立预置课程图（邻接表）*/
intCreateGraph2（ALGraph*G）//成功建立返回1，不成功则返回0
ArcNode*newarc;
VertexTypeSubjectName[12]={"
C1"
"
C2"
C3"
C4"
//课程名称
C5"
C6"
C7"
C8"
C9"
C10"
C11"
C12"
},
RelationV1[16]={"
//基础课
},
RelationV2[16]={"
//以上面课程为基础的课
};
//********************************************************************
//system（"
PAUSE"
（*G）.vexnum=12;
（*G）.arcnum=16;
\n课程数或先后关系不正确，有向图建立失败！
return0;
}//判断课程数和弧数是否正确
{strcpy（（*G）.vexhead[i].name,SubjectName[i]）;
{strcpy（v1,RelationV1[k]）;
strcpy（v2,RelationV2[k]）;
//定位课程并判断课程是否存在
课程%s不存在，有向图建立失败！
if（j>
//前插法建课程链表
//对应课程入度计数加1
/**********************************/
/*以下为拓扑排序算法*/
/*9.拓扑排序*/
{inti,k,count;
ElemTypee;
//弧结点，指向边表结点的指针
sqstackS;
/*定义栈*/
Initstack（&
S）;
i++）//零入度课程入栈
if（!
G.vexhead[i].indegree）push（&
S,i）;
count=0;
//对输出课程计数变量初始化
\n\n\n以上课程的一个拓扑排序序列为:
while（!
emptystack（S））
{pop（&
S,&
e）;
//先将入度为零的课程输出
%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）;
if（count<
G.vexnum）
\n该有向图有回路，无法完成拓扑排序！
{ALGraphG;
intmenu;
while
（1）{
\n**********************************************\n"
*1.建立有向图并求一个拓扑排序序列*\n"
*2.清屏*\n"
*3.退出*\n"
**********************************************\n"
请输入你的选择:
%d"
menu）;
switch（menu）{
case1:
if（CreateGraph（&
G））//有向图建成则执操作
{system（"
//暂停，等待用户按键
PrintGraph（G）;
system（"
//按邻接表方式输出有向图
TopologicalSort（G）;
}//拓扑排序
break;
case2:
system（"
CLS"
//清屏
case3:
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语言完成课程设计，让我们从传统上的被动授学，转变为主动求学。
形成了在实践中学习的能力，增强了领悟能力和解决问题能力。
升级会员 