专业课程设计论文图的遍历.doc

内蒙古科技大学
本科生课程设计论文

题 目：C++课程设计
-------图遍历
学生姓名：王刚
学 号：
专 业：计算机09级
班 级：（2）班
指引教师：丁雨

6月13日~6月24日

内蒙古科技大学课程设计任务书
课程名称
数据构造课程设计
设计题目
图遍历
指引教师
丁雨
时间
-6-23
一、教学规定
1. 掌握数据构造与算法设计办法，具备初步独立分析和设计能力
2. 初步掌握软件开发过程问题分析、系统设计、程序编码、测试等基本办法和技能
3. 提高综合运用所学理论知识和办法独立分析和解决问题能力
4. 训练用系统观点和软件开发普通规范进行软件开发，培养软件工作者所应具备科学工作办法和作风
二、设计资料及参数
每个学生在教师提供课程设计题目中任意选取一题，独立完毕，题目选定后不可更换。
图遍历
以数组表达法或邻接表表达图，在此基本上实现对图遍历。
规定设计类（或类模板）来描述图，包括必要构造函数和析构函数，以及其她可以完毕如下功能成员函数：
v 输入图、输出图
v 求图中顶点V第一种邻接点
v 求图中顶点V下一种邻接点
v 深度优先遍历图
v 广度优先遍历图
并设计主函数测试该类（或类模板）。
三、设计规定及成果
1. 分析课程设计题目规定
2. 写出详细设计阐明
3. 编写程序代码，调试程序使其能对的运营
4. 设计完毕软件要便于操作和使用
5. 设计完毕后提交课程设计报告
四、进度安排
资料查阅与讨论（1天）
系统分析（2天）
系统开发与测试（5天）
编写课程设计阐明书和验收（2天）
五、评分原则
1. 依照平时上机考勤、体现和进度，教师将每天点名和检查
2. 依照课程设计完毕状况，必要有可运营软件。
3. 依照课程设计报告质量，如有雷同，则所有雷同所有人均判为不及格。
4. 依照答辩状况，应可以以清晰思路和精确、简洁语言论述自己设计和回答教师提问
六、建议参照资料
1．《数据构造 （C语言版）》严蔚敏、吴伟民 主编 清华大学出版社 .11
2．《数据构造课程设计案例精编（用C/C++描述）》，李建学 等 编著，清华大学出版社 .2
3.《数据构造:用面向对象办法与C++语言描述》，殷人昆 主编， 清华大学出版社 .6
一、前言
1.1课程设计目与意义………………………………………………4
1.2对课程设计功能需求分析…………………………………………4
二、算法思想…………………………………………………………………5
三、数据构造…………………………………………………………………5
四、模块划分…………………………………………………………………6
node* creategraph()//建立邻接表，完毕无向图输入
void DepthFirstSearch(node *list)//深度优先搜索
void BreadthFirstSearth(node *list)//广度优先搜索
void PathSearth(node *list)//途径搜索
void AdjacencyListDelete(node *list)//释放邻接表空间
AdjacencyListDelete(list);//释放邻接表空间
五、系统概要设计
1、系统功能模块图…………………………………………………………9
六、源程序……………………………………………………………………10
七、程序调试分析以及测试成果
1、程序调试测试成果…………………………………………………………20
八、附录
1、附录一
心得……………………………………………………………………………21
2、参照文献…………………………………………………………………22

一、前言
1.1课程设计目与意义
上学期咱们对《数据构造》这门课程进行了学习。这门课程是一门实践性非常强课程，为了让人们更好地理解与运用所学知识，提高动手能力，咱们进行了本次课程设计实习。这次课程设计不但规定咱们掌握《数据构造》中各方面知识，还规定咱们具备一定C++语言基本和编程能力。
通过实践咱们掌握《数据构造》中知识。对于《图遍历》这一课题来说，所规定咱们掌握数据构造知识重要有：图存储构造、队列基本运算实现、图深度优先遍历算法实现、图广度优先遍历算法实现。
对于咱们学生来讲，本次课程设计是为了让咱们训练自己实际设计能力，通过设计实践，去真正获得此项目管理和团队协作等方面基本训练和工作经验。
通过课程设计一系列训练，咱们能提高如何综合运用所学知识解决实际问题能力，以及获得此项目管理和团队协作等等众多方面详细经验，增强对有关课程详细内容理解和掌握能力，培养对整体课程知识综合运用和融会贯通能力。
1.2对课程设计功能需求分析
图遍历并不需要是一种过于复杂工作环境，普通来说：最适当才是最佳。软件设计必要符合咱们使用实际状况需要。依照规定，图遍历重要功能如下：
1、顾客可以随时建立一种有向图或无向图；
2、顾客可以依照自己需要，对图进行深度遍历或广度遍历；
3、顾客可以依照自己需要对图进行修改；
4、在整个程序中,顾客可以不断按照不同方式对图进行遍历,若不继续,顾客也可以随时跳出程序,同步,如果顾客输入序号错误,程序会提示顾客重新输入序号;

二、算法思想
本课题本人所采用是邻接表方式存储图，实现图深度、广度两种遍历，并将每种遍历成果输出来。并且能寻找途径。
2.1.1图邻接矩阵建立
对任意给定图（顶点数和边数自定），，依照邻接表存储构造建立图邻接表。
2.1.2 图遍历实现
邻接表是图一种链式存储构造，在邻接表中，对图中每一种顶点建立一种单链表，普通以顺序构造存储，以便随机访问任意一顶点。
图深度遍历，假设初始状态是图中所有顶点都未曾被访问，则深度优先遍历可从图中某个顶点v出发，访问此顶点，依次从v未被访问邻接点出发深度优先遍历图，直至图中和v有途径想通顶点都被访问到；若此时图中尚有未被访问节点，则另选图中一种未被访问顶点做起始点，直至所有节点都被访问。
图广度优先遍历，是以v为起始点，由近及远依次访问和v有途径相通且途径长度为1、2、…顶点。

三、数据构造
#define t true
#define f false
#include
struct node//定义一种构造作为节点类型
{
int data;
bool sign;//标志位,用来标示与否遍历过
node *next;
};

四、模块划分
node* creategraph()//建立邻接表，完毕无向图输入
};
0
4

1
0

2
1

3
2

4
3

输入节点数
动态分派节点数组内存
边
边

表4.1邻接表建立
void DepthFirstSearch(node *list)//深度优先搜索

void DepthFirstSearch(node *list)

cin>>k;

a[i]=k

list[k].sign=t;

i++

list[k].sign==t

k=p->data;

真
p=p->next;

i++
非零 零

if(list[k].sign!=f)

结束程序

图4.2 深度优先遍历流程图

void BreadthFirstSearth(node *list)//广度优先搜索

BreadthFirstSearthth

搜索起始节点

cin>>k;

list[k].sign=t;

p=list[a[m]].next;

真

if(list[k].sign==f)
r+标记

p=p->next;

I++

程序结束

for(int i=1;i<=n;i++)//恢复原邻接表
list[i].sign=f;

表4.3图广度遍历
void PathSearth(node *list)//途径搜索
void AdjacencyListDelete(node *list)//释放邻接表空间
AdjacencyListDelete(list);//释放邻接表空间
五、系统概要设计
main() /*包括某些调用和控制语句*/
进入菜单选取
顾客登录

图信息录入
途径收索
广度优先遍历图
深度优先遍历图

退出程序

图5.1系统功能模块图
六、某些源程序
#define t true
#define f false
#include
struct node//定义一种构造作为节点类型
{
int data;
bool sign;//标志位,用来标示与否遍历过
node *next;
};
node* creategraph()//建立邻接表，完毕无向图输入
{
int l,m,n;
bool g;
cout<<"请输入节点数：";
cin>>n;
node *adjacencylist=new node[n+1];//动态分派节点数组内存
adjacencylist[0].data=n;//0地址存储为节点数
adjacencylist[0].next=NULL;
for(int i=1;i<=n;i++)//给各顶点域赋初值
{
adjacencylist[i].data=0;
adjacencylist[i].next=NULL;
adjacencylist[i].sign=f;//表达未遍历
}
cout<<"请依次输入各条边始点和尾点:（以0表达结束）"<>l;
if(l!=0)//判断输入边与否结束
g=t;
while(g==t)
{
cin>>m;
if((l>0)&&(l<=n)&&(m>0)&&(m<=n))//判断输入顶点与否对的
{
node *p,*q,*top;
p=(node *)new(node);//分派边一种顶点内存
p->data=m;
p->next=NULL;
if(adjacencylist[l].next==NULL)//为每个节点创立邻接链表
adjacencylist[l].next=p;
else
{
top=adjacencylist[l].next;
while(top->next!=NULL)
top=top->next;
top->next=p;
}
adjacencylist[l].data++;//记录邻接点个数
q=(node *)new(node);//分派边另一种顶点内存
q->data=l;
q->next=NULL;
if(adjacencylist[m].next==NULL)//构建邻接表
adjacencylist[m].next=q;
else
{
top=adjacencylist[m].next;
while(top->next!=NULL)
top=top->next;
top->next=q;
}
adjacencylist[m].data++;//记录邻接点个数
}
else
cout<<"边"<>l;
if(l==0)//边输入结束
g=f;
}
return adjacencylist;//返回邻接表
};
void DepthFirstSearch(node *list)//深度优先搜索
{
int m,n=list[0].data,k,*a=new int[n];//设立一种数组用于存储节点
node *p;
cout<<"采用深度优先搜索："<>k;
for(int i=0;i while(p!=NULL)//找出list[k]链表中未遍历节点
{
k=p->data;
p=p->next;
if(list[k].sign==f)
break;
}
m++;
if(list[k].sign!=f)//判断与否是p=NULL跳出while循环
{
if(i无节点可回溯
{
cout<<"该图为非连通图!"</输出遍历成果
cout<>k;
a[0]=n;
a[1]=k;
list[k].sign=t;//标记遍历第一种节点
m=0;
r=1;
while(m!=r)
{
m++;
p=list[a[m]].next;
while(p!=NULL)
{
k=p->data;
if(list[k].sign==f)
{
r++;
a[r]=k;//遍历到节点存入数组
list[k].sign=t;//标记已经遍历过节点
}
p=p->next；
}
}
for(int i=1;i<=n;i++)//恢复原邻接表
list[i].sign=f;
cout<<"广度优先搜索遍历顺序为：";
for(i=1;i<=n;i++)//输出遍历
cout< int *a,c,d,m,k,n=list[0].data;
cout<<"请输入起始点：";
cin>>k;
cout<<"请输入尾节点：";
cin>>c;
cout<<"请输入要找途径长度：";
cin>>d;
d=d+1;
if(d>n)
cout<<"不存在这样简朴途径！"<
a[i]=0;
a[0]=k;
node *p;
int x;
list[a[0]].sign=t;
i=1;
while(a[d-1]!=c)
{
while(i m=p->data;
if(i==d-1&&m==a[0]&&a[0]==c)//途径存在且为回路
{
cout<<"该途径为一条回路！"<//与否为已经判断过错误途径
{
a[i]=m;
list[a[i]].sign=t;//标记走过节点
i++;
break;
}
if(a[i]==m)//设立错误途径标记
x=0;
}
else
{
a[i]=m;
list[a[i]].sign=t;//标记走过节点
i++;
break;
}
}
p=p->next；
}
if(p==NULL)
{
a[i]=0;
i--;//由此节点往下途径不存在,回溯
list[a[i]].sign=f； //还原标记符
}
if(i==0)//无法回溯,途径不存在,跳出循环
{
cout<<"不存在这样简朴途径！"<//无法回溯,途径不存在,跳出循环
break;
if(a[d-1]!=c)//途径不是所要找
{
i--；//回溯
if(i>=0)
list[a[i]].sign=f;//还原标记符
}
}
if(a[d-1]==c)//判断途径与否找到并输出
{
cout<<"从节点"<//输出途径
cout< ";
cout<t[i].next;
while(p!=NULL)
{
q=p->next;
delete p;//释放链表节点空间
p=q;
}
}
delete list;//释放邻接表空间
};
void main()
{
node *list;
list=creategraph();//以邻接表形式建立一种无向图
char a,b;
cout<<"请选取遍历办法：（d:深度优先搜索;b:广度优先搜索）";
for(int i=1;i<2;i++)
{
cin>>a
switch(a)
{
case 'd':
case 'D'： DepthFirstSearch(list);
cout<<"与否采用广度优先搜索重新遍历？（y:是;n:否）";
cin>>b;
if((b=='y')||(b=='Y'))
BreadthFirstSearth(list);
break;
case 'b':
case 'B'： BreadthFirstSearth(list);
cout<<"与否采用深度优先搜索重新遍历？（y:是;n:否）";
cin>>b;
if((b=='y')||(b=='Y'))
DepthFirstSearch(list);
break;
default： cout<<"输入错误！请重新输入！"<>a;
if((a=='y')||(a=='Y'))
PathSearth(list);
else if((a=='n')||(a=='N'))
break;
else
cout<<"输入错误！"<不断完善某些细节方面，并对输入参数进行多方面变化，以保证程序对的性。
在整个程序运营无误基本上，在竭力对某些函数进行优化，加强程序可读性，以便性。
通过这次课程设计让我收获了不少东西，只要有如下几种方面。
1）对于基于C++语言数据构造，C++语言掌握状况是能否学好这样课程一种重要因素，因此在进行课程设计时候又对C++语言进行了某些复习。
2）在调试过程中懂得了，学习严谨性，特别对于编程题目。“差之毫厘，谬之千里”。固然这也不但仅在学习方面，生活中也是样。
3）在这个项目中也提示了自己在平时除了自己专业知识外应当积累更多知识，技能。只有这样在进行各项事情过程中才干更加顺利。
4）“理论联系实践”，实践是建立在学习基本之上，而又在其中不断学习过程。平时上课听讲觉得容易接受，淡然无味，但在实现算法时候才发现本来一切并非如此。数据构造这门课程比较抽象并且如果自己只是看看书话主线就不可以学好，并且数据构造这门课程也应用非常广泛，特别是在计算机许多语言中都可以看到数据构造思想。
八、附录
5.1、课程设计心得体会
心得体会
通过这近一种星期数据构造课程设计实践，我学到了诸多东西。本次课程设计对我来说正是一种提高自己能力机会，我好好抓住机会，努力做好每一步，完善每一步。
自己C语言知识和数据构造知识得到了巩固，编程能力也有了一定提高。同步也学会理解决问题办法。总结起来，自己重要有如下几点体会：
1.必要牢固掌握基本知识。由于C语言是大一所学知识，有所遗忘，且未掌握好上学期所学《数据构造》这门课，因此在实践之初感到棘手。不知如何下手，但在日后实习过程中自己通过看书和课外资料，并请教其她同窗，慢慢地对C语言和数据构造知识有所熟悉，这时才逐渐有了思路。因此，这次课程之后，我告诫自己：此后一定要牢固掌握好专业基本知识。
2.必要培养严谨态度。自己在编程时经常由于某些类似于“少了分号”小错误而导致错误，不够认真细致，这给自己带来了许多麻烦。编程是一件十分严谨事情，容不得马虎。因此在此后自己一定要培养严谨态度。我想这不但是对于程序设计，做任何事都应如此。
3.这次课程设计也让我充分结识到《数据构造》这门课重要性。它给咱们一种思想和大纲，让咱们在编程时容易找到思路，不至于无章可循。同步它也有广泛实际应用。
在实践过程中，我和成员分工合伙，敢于提出问题，解决难题，在实践中，我遇到了许多困难，但都一一克服了。最后我圆满完毕本次课程设计，学到了诸多东西。同步，程序还存在着某些缺陷，就是不能输出原图，存在某些局限性，但是我会继续努力思考，完善程序，做到最佳。
本次实验，教师对我指引是至关重要，在此我非常感谢教师，从她那我学到了诸多关于c语言知识，为后来学习打下了一定基本。
总来说，本次课程设计，不但我知识面有所提高，此外我综合素质也有所提高，，例如说：团队精神、提问能力、思考能力等等。这次课程设计为我后来更好学习和使用c语言打下了基本。

参照文献
1．《数据构造 （C语言版）》严蔚敏、吴伟民 主编 清华大学出版社 .11
2．《数据构造课程设计案例精编（用C/C++描述）》，李建学 等 编著，清华大学出版社 .2
3.《数据构造:用面向对象办法与C++语言描述》，殷人昆 主编， 清华大学出版社 .6