数据结构课程设计图的建立与输出




数结构课程设计


设计题目：图建立输出




系 ： 电子信息工程学院
专 业： 电子信息工程
班 级： 级班
姓 名：
学 号：
指导教师：








2011年 X 月 X日

目录
设计题目（选）…………………………………………3
二运行环境（软硬件环境）……………………………………3
三算法设计思想…………………………………………………3
四算法流程图……………………………………………………3
五算法设计分析……………………………………………………4
六源代码……………………………………………………………4
七运行结果分析……………………………………………………14
八收获体会………………………………………………………16


























设计题目（选）
图建立输出
务：建立图存储结构（图类型图图网网学生选两种类型）够输入图顶点边信息存储相应存储结构中输出图邻接矩阵
二运行环境（软硬件环境）
硬件环境：
CPU：1000MHz
存：256MB
硬盘：60G
软件环境：
系统台：Windows 2000 Windows XP Windows Vista Windows 7
运行环境：TC 30 Microsoft Visual C++ 60
三算法设计思想
1存储结构邻接矩阵 邻接表
2遍历方式：深度优先搜索（DFS） 广度优先搜索(BFS) 邻接矩阵界表直接输出：中DFS算法通递实现BFS算法通队列实现
3拓扑排序生成树（Prime算法）具体实现见代码
四算法流程图

五算法设计分析
首先建图图网区图没权值（里固定值1代）网权值存储区图输入a[i][j]存储a[i][j]图存储a[j][i]
次功实现邻接表遍历邻接矩阵遍历简单存储结构次输出顶点邻接顶点时间复杂度分O(n+e)O(n2)
DFS算法通函数递实现采存储结构式邻接表找邻接点需时间O(e)中e图边数图弧数时间复杂度O(n+e)
BFS算法队列实现顶点进次队列遍历图程实质通边弧找邻接点程广度优先搜索遍历图时间复杂度深度优先搜索遍历相两者处仅仅顶点访问序
拓扑排序建立项顶点入度时间复杂度O(e)建零入度顶点栈时间复杂度O(n)拓扑排序程中图环顶点进次栈出次栈入度减1操作while语句中总执行e次总时间复杂度O(n+e)
Prime算法生成树假设网中n顶点第进行初始化循环语句频度n第二循环语句频度n1二重新选择具代价边频度nPrime算法时间复杂度O(n2)网中边数关适求边稠密网生成树
六源代码
#include
#include
#include
#include
#include
#include
#include
using namespace std
#define MAX_VERTEX_NUM 20
#define MAX 1000
#define DG 1
#define DN 2
#define UDG 3
#define UDN 4
typedef enum{DGDNUDGUDN} GraphKind
typedef char VertexType
typedef int VRType
typedef char InfoType
struct Close {
VertexType data顶点元素
VRType lowcost
int j
}closedge[MAX_VERTEX_NUM] prime算法秋生成树辅助数组
typedef struct ArcNode{
int adjvex 该弧指顶点位置
struct ArcNode *nextarc指条弧指针
int adj 权图0 1带权图权值
InfoType *info 该弧相关信息指针
}ArcNodeAdjMartrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]简便起见邻接矩阵元素类型时部分元素
typedef struct VNode{
int outdegreeindegree
VertexType data顶点信息
ArcNode *firstarc指第条附该顶点弧指针
}VNodeAdjList[MAX_VERTEX_NUM]

typedef struct Graph{
AdjList vertices 邻接表
AdjMartrix arcs 邻接矩阵
int vexnumarcnum 顶点数边数量
int kind 图类型
}ALGraph
int cmp(const void *aconst void *b)
{

if( *(char *)a*(char *)b>0)
return 1

return 1
}
int LocateVex(ALGraph & G VertexType e ){
for(int i1i if(Gvertices[i]datae)
return i
return 0
}
void Input_V(AdjList & verint n)
{
bool ffalse
char str[30]
memset(str0sizeof(str))
printf(输入顶点：字母数字 ABCDEF 表示六顶点)
while(f&&gets(str)){
int lenstrlen(str)
if(len){ printf(＼t＼t没输入数请输入数) continue}
if(len for(int i0i ver[i+1]datastr[i]
for( i0i if((str[i]>＇a＇&&str[i]<＇z＇||str[i]>＇A＇&&str[i]<＇Z＇||str[i]>＇0＇&&str[i]<＇9＇))
break
if(i qsort(strlensizeof(char)cmp)
for(i0i if(str[i]str[i+1]) break
if(i ftrue
memset(str0sizeof(str))
puts(str)
}
}
void initGraph( ALGraph & G) 初始化图 包括 输入顶点弧数目初始化邻接表数组
{
int a1b1
char str[23]
printf(＼t＼t输入顶点数弧数：)
do{
scanf(dd*c&a&b)
if(a1||b1) {
gets(str)
printf(＼t＼t输入合法请重新输入：)
}
else break
}while(1)
printf(d d ＼nab)
Gvexnuma Garcnumb
Input_V(GverticesGvexnum)
for(int i1i scanf(d&(Gvertices[i]data)) 构造顶点量
for(int j1j Garcs[i][j]adjMAX
Garcs[i][j]infoNULL
}
Gvertices[i]indegree0
Gvertices[i]outdegree0
Gvertices[i]firstarcNULL
}
}
void Input(char & v1char & v2int &d ALGraph & G)
{
char str[30]
int i
bool flagfalse
memset(str0sizeof(str))

while(flag&&gets(str)){
int length strlen(str)
for(i4i if(isalnum(str[0])||isalnum(str[2])) break
if(str[1]＇ ＇||str[3]＇ ＇) break
if(isdigit(str[i])) break
}
if(length<5||i
printf(d s＼nlengthstr)
for(i4d0i dd*10+str[i]＇0＇
if((Gkind1||Gkind3)&&d1) { printf(存合法字符输入格式错误 请重新输入＼n) continue}
v1str[0] v2str[2]
flagtrue
memset(str0sizeof(str))
}

}
int CreateDG_DN_UDG_UDN(ALGraph & G){ 图网图网邻接矩阵具体实现
VertexType v1v2
int weight
int flagGkind
initGraph(G)
int temGarcnum
printf(条边附两定点权值（>0）权输入1 A B 20 A B 1 ＼n)
while(tem){
Input(v1v2weightG)
int iLocateVex(Gv1) 定位v1 v2数组中位置
int jLocateVex(Gv2)
Garcs[i][j]adjflag1||flag31weight 建立邻接矩阵
if(flag3||flag4){
Garcs[j][i]adjflag31weight
}
ArcNode * q(ArcNode *)malloc(sizeof(ArcNode))
q>adjweight
q>adjvexj
q>nextarcNULL
if(Gvertices[i]outdegree0)
Gvertices[i]firstarcq
else{
ArcNode *pGvertices[i]firstarc
while(p>nextarc)
pp>nextarc
p>nextarcq
}
if(flag3||flag4){ if 语句创建图 网准备
ArcNode * q(ArcNode *)malloc(sizeof(ArcNode))
q>adjweight
q>adjvexi
q>nextarcNULL
if(Gvertices[j]outdegree0&&Gvertices[j]indegree0)
Gvertices[j]firstarcq
else{
ArcNode *pGvertices[j]firstarc
while(p>nextarc)
pp>nextarc
p>nextarcq
}
}
Gvertices[i]outdegree++
if(flag3||flag4) Gvertices[j]outdegree++
else
Gvertices[j]indegree++

}

return 0
}

void VisitDG_DN_UDG_UDN(ALGraph & Gint f){ 遍历邻接表
ArcNode *p
if(f){
printf(＼t＼t遍历邻接表 ＼n)
for(int i1i pGvertices[i]firstarc
printf(＼t＼t第d顶点c邻接顶点：iGvertices[i]data)
while(p){
printf(c Gvertices[p>adjvex]data)
pp>nextarc
}
if(Gkind3||Gkind4) printf(度数 d Gvertices[i]outdegree)
else printf(出度 d 入度 d Gvertices[i]outdegreeGvertices[i]indegree)
printf(＼n)
}
}
else{
printf(遍历邻接矩阵 ：＼n＼t＼t )
for(int i1i printf(c cGvertices[i]dataiGvexnum＇＼n＇＇ ＇)
printf(＼t＼t─┼────────────────＼n)
printf(─┼───────＼n │＼n │)
for( i1i printf(＼t＼tc │Gvertices[i]data)
for(int j1j printf(5dcGarcs[i][j]adjjGvexnum＇＼n＇＇ ＇)
if(Garcs[i][j]adjMAX) printf(∞ cjGvexnum＇＼n＇＇ ＇)
else printf(d cGarcs[i][j]adjjGvexnum＇＼n＇＇ ＇)
}
}
}

bool visit[MAX_VERTEX_NUM]深度优先搜索
void DFS(ALGraph & Gint i){
visit[i]true
printf(c Gvertices[i]data)
ArcNode * p
for(pGvertices[i]firstarcppp>nextarc){
if(visit[p>adjvex]) DFS(Gp>adjvex)

}
}
void DFSTraverse(ALGraph & G){
int i
printf(＼t＼t深度优先搜索 )
for( i0i visit[i]false
for( i1i if(visit[i]) DFS(Gi)
}

queue Q
void BFSTraverse(ALGraph & G) 广度优先搜索
{
int ij
printf(＼n＼t＼t广度优先搜索 )
for( i0i visit[i]false
for(i1i if(visit[i]){
visit[i]true
printf(c Gvertices[i]data)
Qpush(i)
while(Qempty()){
jQfront()
Qpop()
for(ArcNode *wGvertices[j]firstarcwww>nextarc)
if(visit[w>adjvex]){
visit[w>adjvex]true
printf(c Gvertices[w>adjvex]data)
Qpush(w>adjvex)
}
}
}
}
}

void MinSpanTree_PRIM(ALGraph GVertexType u) prim算法生成树
{
if(GkindUDN) {printf(没成树＼n)return}
int ijk
int mincost0
printf(＼n＼t＼tprim算法生成树 )
kLocateVex(Gu)
for(i1i closedge[i]dataGvertices[i]data
closedge[i]lowcostGarcs[k][i]adj
closedge[i]jk
}
closedge[k]lowcost0

for(i1i for(k1k printf((d d) cclosedge[k]dataclosedge[k]lowcostkGvexnum＇＼n＇＇ ＇)
k0
for(j1j if(closedge[j]lowcost0) continue
if(k0){kjcontinue}
if(closedge[k]lowcost>closedge[j]lowcost)
kj
}
for(int t1t printf((d d dc)＼ttclosedge[t]lowcostclosedge[t]jtGvexnum＇＼n＇＇ ＇)
if(k) printf((c c d) Gvertices[closedge[k]j]dataGvertices[k]dataclosedge[k]lowcost) 生成树顶点量值权
mincost+closedge[k]lowcost

closedge[k]lowcost0
for(j1j if(Garcs[j][k]adj closedge[j]dataGvertices[j]data
closedge[j]lowcostGarcs[j][k]adj
closedge[j]jk
}

}printf(＼n＼t＼t代价 ：d＼nmincost)
}

int TOpologicalSort(ALGraph & G)拓扑排序
{
stack S
int ijcount0
int indegree[30]
for(i1i indegree[i]Gvertices[i]indegree
if(Gkind3||Gkind4) {printf(图进行拓扑排序＼n)return 1}
printf(＼n拓扑排序：)
for(i1i if(Gvertices[i]indegree0)Spush(i)
while(Sempty()){
jStop() Spop()
count++
printf((d c) jGvertices[j]data)
for(ArcNode *pGvertices[j]firstarcppp>nextarc){
int kp>adjvex
int d(Gvertices[k]indegree)
if(d)Spush(k)
}
}
for(i1i Gvertices[i]indegreeindegree[i]
if(Gvexnumcount) {printf(＼n) return 1}
printf(失败＼n) return 0
}

void Choose(ALGraph &G){
int choiceGkind

char str[30]
do{
system(cls)
printf(＼n＼n＼t＼t▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄＼n)
printf(＼t＼t▌请选择操作：＼t＼t＼t＼t ▌＼n)
printf(＼t＼t▌1邻接矩阵遍历＼t4广度优先搜索＼t ▌＼n＼t＼t▌2邻接表遍历＼t5拓扑排序＼t ▌＼n)
printf(＼t＼t▌3深度优先搜索＼t6生成树＼t ▌＼n＼t＼t▌7返回＼t＼t8退出程序＼t＼t ▌＼n)
printf(＼t＼t ▲▲▲▲▲▲▲▲▲▲▲▲▲▲▲▲▲▲▲▲＼n＼n)
printf(＼t＼t请输入选择（17）：)
do{
memset(str0sizeof(str))
gets(str)
if(strlen(str)>1) choice1
else if(str[0]<＇1＇||str[0]>＇8＇) choice1
else choicestr[0]＇0＇
if(choice1) printf(＼t＼t输入合法请重新输入：)
else break
}while(1)
switch(choice){
case 1 VisitDG_DN_UDG_UDN(G0) break
case 2 VisitDG_DN_UDG_UDN(G1) break
case 3 DFSTraverse(G)break
case 4 BFSTraverse(G) break
case 5TOpologicalSort(G) break
case 6 MinSpanTree_PRIM(GGvertices[1]data)break
case 7return
case 8exit(0)
}
printf(＼n＼t＼t回车键继续) getchar()
}while(1)

}
void Menu(ALGraph &G){
bool ftrue
int choice1
char str[30]
do{
system(cls)
printf(＼n＼n＼t＼t╔════════════════════╗＼n)
printf(＼t＼t║＼t＼t＼t＼t＼t ║＼n)
printf(＼t＼t║＼t＼t图建立操作＼t＼t ║＼n)
printf(＼t＼t║＼t＼t＼t＼t＼t ║＼n)
printf(＼t＼t╚════════════════════╝＼n＼n)
printf(＼t＼t请选择建图方式：＼n)
printf(＼t＼t＼t1图＼t2网＼n)
printf(＼t＼t＼t3图＼t4网＼n＼t＼t＼t5退出＼n＼n)
printf(＼t＼t请输入选择（1－5）：)
do{
memset(str0sizeof(str))
gets(str)
if(strlen(str)>1) choice1
else if(str[0]<＇0＇||str[0]>＇9＇) choice1
else choicestr[0]＇0＇

if(choice<1||choice>5)
printf(＼t＼t输入合法请重新输入（1－5）：)
else
break
}while(1)
if(choice5) break
else{
Gkindchoice
CreateDG_DN_UDG_UDN(G)
system(cls)
printf(＼n＼n＼n＼n＼t＼t图已建立回车键继续操作)
getchar()
Choose(G)
}
}while(1)
}
int main()
{
ALGraph G
printf()
Menu(G)
return 0
}
七运行结果分析
测试数运行结果见截图
界面建立选择建立图输入数应严格求否法建立

邻接矩阵遍历边输出权值（网）1（图）边输出穷

邻接表遍历次输出顶点邻接点输出点出度入度

四截图分深度优先搜索广度优先搜索拓扑排序生成树运行结果均字符表示遍历操作序



测试数：
3
5 8
ABCDE
D E 1 C E 1 D C 1 A E 1 B E 1 B A 1 A D 1 B C 1
2
5 6
12345
1 2 1 1 3 1 2 3 1 4 5 1 5 2 1 4 3 1
八收获体会
进行次课程设计程中真正学教科书没者真正课知识样巩固旧知识掌握新知识数结构课程设计重中重提高专业知识实践相结合重手段
次课程设计进行结构化程序设计初步训练培养数抽象力实际操作程中遇问题通查书网查资料问老师问题解决程中课堂知识运实际通解决问题学课外知识引导激发数结构兴趣时培养搜索分析信息查阅帮助文档整理验编写文档合作交流力
课程设计中遇见难点方说 输入数时错误输入会程序崩溃仔细思考查阅资料请教学圆满解决然收获较点外觉程序仅功实现更重容错力机交互界面次课程设计较简单时间较充裕额外增加功程序容错力
通做课程设计数结构门课程更深步解感谢指导老师指点迷津感谢学院次课程设计机会机房理员私服务

文档香网(httpswwwxiangdangnet)户传

《香当网》用户分享的内容，不代表《香当网》观点或立场，请自行判断内容的真实性和可靠性！
该内容是文档的文本内容，更好的格式请下载文档