计算机应用 | 古代文学 | 市场营销 | 生命科学 | 交通物流 | 财务管理 | 历史学 | 毕业 | 哲学 | 政治 | 财税 | 经济 | 金融 | 审计 | 法学 | 护理学 | 国际经济与贸易
计算机软件 | 新闻传播 | 电子商务 | 土木工程 | 临床医学 | 旅游管理 | 建筑学 | 文学 | 化学 | 数学 | 物理 | 地理 | 理工 | 生命 | 文化 | 企业管理 | 电子信息工程
计算机网络 | 语言文学 | 信息安全 | 工程力学 | 工商管理 | 经济管理 | 计算机 | 机电 | 材料 | 医学 | 药学 | 会计 | 硕士 | 法律 | MBA
现当代文学 | 英美文学 | 通讯工程 | 网络工程 | 行政管理 | 公共管理 | 自动化 | 艺术 | 音乐 | 舞蹈 | 美术 | 本科 | 教育 | 英语 |

通过图的邻接矩阵实现图的搜索实现(一)-通信工

2013-06-25 01:21
导读:通信工程论文毕业论文,通过图的邻接矩阵实现图的搜索实现(一)-通信工在线阅读,教你怎么写,格式什么样,科教论文网提供各种参考范例: 摘 要  本课程设计主要解决图的搜索实现,

摘 要  本课程设计主要解决图的搜索实现,通过图的邻接矩阵实现深度优先搜索和广度优先搜索。图是一种较线形表和树更复杂的数据结构,其应用极为广泛,目前已渗入到语言学,逻辑学,物理,化学以及计算机科学等诸多领域中。在本课程设计中,系统开发平台为Windows xp,程序设计设计语言主要采用C语言,程序运行平台为Windows 2000/XP。程序开始后,通过输入各结点与边的相关数据,可以得出相应的深度优先和广度优先搜索结果。

关键词  程序设计;C语言;图的邻接矩阵;图的深度优先搜索、广度优先搜索
 
1 引  言
图是一种较复杂的数据结构,图的搜索在图书索引,城市道路建设,人工智能等领域中发挥着重要作用。图的搜索有深度优先搜索和广度优先搜索,我们可以通过图的邻接矩阵或邻接表实现图的这两种搜索。
本次程序设计我们通过C语言编写程序实现图的搜索。在编写过程中我们将图定义为邻接矩阵类型,通过深度优先搜索遍历和广度优先搜索遍历分别实现图的搜索。
    我们学习两年的有关C语言和数据结构的相关知识,而课程设计是将我们把所学的理论和生产实践相结合的重要环节, 通过这次课程设计,可以使我们所学的专业技能得到巩固、扩大、深入和系统化;培养综合运用所学知识解决图的搜索的能力,初步掌握数据结构程序设计的方法和步骤;使我们进一步提高编写程序的效率;提高我们独立钻研问题的能力,培养严肃认真,实事求是,刻苦钻研的工作作风。

2 开发工具介绍
C 语言是1972年由美国的Dennis Ritchie设计发明的, 并首次在UNIX操作系统DEC PDP-11 计算机上使用。 它由早期的编程语言 BCPL( Basic Combind Programming Language) 发展演变而来。在1970年, AT&T 贝尔实验室的 Ken Thompson根据BCPL语言设计出较先进的并取名为 B的语言, 最后导了C 语言的问世。 随着微型计算机的日益普及, 出现了许多C语言版本。由于没有统一的标准, 使得这些C 语言之间出现了一些不一致的地方。为了改变这种情况, 美国研究所(ANSI)为C 语言制定了一套ANSI标准,成为现行的C语言标准。 (科教作文网 zw.nseac.com整理)
C语言具有强大的功能,它具有以下特点:
1. C是中级语言
它把高级语言的基本结构和语句与低级语言的实用性结合起来。C 语言可以象汇编语言一样对位、字节和地址进行操作, 而这三者是计算机最基本的工作单元。
2. C是结构式语言
结构式语言的显著特点是代码及数据的分隔化, 即程序的各个部分除了必要的信息交流外彼此独立。这种结构化方式可使程序层次清晰, 便于使用、维护以及调试。C
语言是以函数形式提供给用户的, 这些函数可方便的调用, 并具有多种循环、条件语句控制程序流向, 从而使程序完全结构化。
3. C语言功能齐全
C 语言具有各种各样的数据类型, 并引入了指针概念, 可使程序效率更高。另外C 语言也具有强大的图形功能,
支持多种显示器和驱动器。而且计算功能、逻辑判断功能也比较强大, 可以实现决策目的。
4. C语言适用范围大
C 语言还有一个突出的优点就是适合于多种操作系统, 如DOS、UNIX,也适用于多种机型。
 3 相关知识
  
 图的概念:图是一种较线形表和树更复杂的数据结构,是一种数据元素间为多对多关系的数据结构,加上一组基本操作构成的抽象数据类型,图作为一种非线性数据结构,被广泛应用于多个技术领域,诸如系统工程、化学分析、统计力学遗传学、控制论、计算机的人工智能、编译系统等领域。
 图的基本操作:创建、插入、删除、查找等。
 图的几种存储结构类型:图的邻接矩阵表示法,图的邻接表表示法

(转载自科教范文网http://fw.nseac.com)


 深度优先搜索(DFS):a、深度优先搜索类似于树的前序遍历,也是一遇到顶点就进行访问。其特点是尽可能先对纵深方向进行搜索,因此很容易用递归算法实现。如果将遍历过程中走过的边连接起来,即可得到深度优先遍历生成树。b、深度优先搜索遍历图的算法:首先访问指定的起始顶点v0,从v0出发,访问v0的一个未被访问过的邻接顶点w1,再从w1出发,访问w1的一个未被访问过的顶点w2,然后从w2出发,访问w2的一个未被访问过的邻接顶点w3。依次类推,直到一个所有邻接顶点都被访问过为止。
 广度优先搜索(BFS):广度优先搜索类似于树的按层次遍历。首先访问指定的起始点v0,从v0出发,访问v0的所有未被访问过的邻接顶点w1,w2,… wk,然后再依次从w1,w2,… wk出发,访问它们的所有未被访问过的邻接顶点,依次类推,直到图中所有未被访问过的邻接顶点都被访问过为止。广度优先遍历的特点是尽可能进行横向搜索,即最先访问的顶点其邻接点也被先访问。因此,借助一个队列来保存已被访问过的顶点序列。访问一个顶点vi时(出队),同时将vi相邻的其余结点入队。每个顶点只能入队一次。

                     

 

 

 

 

 

4 程序的设计与实现
4.1 程序相关算法伪代码[3]
 图的深度优先搜索算法伪代码:
 DFS(v)//访问由v到达的所有顶点
 1.  Visited(v)=1;
 2.  for邻接于v的每个顶点w  do
 3.   if Visited(w)=0 then
 4.      DFS(w);
 5.    endif
 6.  endfor  
 7.end DFS


 
图的广度优先搜索算法伪代码:
 BFS(v) //宽度优先搜索G,从顶点v开始执行
     // 所有已搜索的顶点i都标记为Visited(i)=1.
     //Visited的初始分量值全为0
 1. Visited(v)=1; u=v;
 2. Q=[];//将Q初始化为空队列
 3. loop
 4.   for 邻接于u的所有顶点w  do
 5.     if Visited(w)=0 then
 6.       AddQ(w,Q); //将w放于队列Q之尾
 7.       Visited(w)=1;
 8
上一篇:DDS的杂散对比与级联方案的研究(一)-通信工程毕 下一篇:研究通讯卫星上的开关设置问题(一)-通信工程毕