2022年数据结构课程方案报告样本.docx

《2022年数据结构课程方案报告样本.docx》由会员分享，可在线阅读，更多相关《2022年数据结构课程方案报告样本.docx（26页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选学习资料 - - - - - - - - - 个人资料整理 仅限学习使用这是最终提交的文档资料格式,必需包含几个部分,假如是四到五个人完成要求文档不少于 70 页, 3-4 个人完成要求不少于 50 页；数据结构课程设计题 目图的储备与遍历同学姓名指导老师学 院专业班级完成时间名师归纳总结 - - - - - - -第 1 页,共 15 页精选学习资料 - - - - - - - - - 个人资料整理 仅限学习使用目 录要求自动生成 ）第一章 课程设计目的 2 其次章 课程设计内容和要求 2 第三章 课程设计分析 3 第四章 算法描述 4 第五章 源代码 8 第六章 运行结果分析 13 第

2、七章 终止语 15 第八章 参考文献 15名师归纳总结 - - - - - - -第 2 页,共 15 页精选学习资料 - - - - - - - - - 个人资料整理 仅限学习使用第一章 课程设计目的本学期我们对数据结构这门课程进行了学习；这门课程是一门实践性 特别强的课程,为了让大家更好地懂得与运用所学学问,提高动手才能,我们 进行了此次课程设计实习；这次课程设计不但要求实习者把握数据结构中的各方面学问,仍要求实习者具备肯定的C 语言基础和编程才能；详细说来,这次课程设计主要有两大方面目的；一是让实习者通过实习把握数据结构中的学问；对于图的储备与遍 历这一课题来说,所要求把握的数据结构学问

3、主要有：图的邻接表存贮结构、队列的基本运算实现、邻接表的算法实现、图的广度优先搜寻周游算法实 现、图的深度优先搜寻周游算法实现；二是通过实习巩固并提高实习者的C 语言学问,并初步明白Visual C+的学问,提高其编程才能与专业水平；其次章 课程设计内容和要求2.1 课程设计内容组成员名称和分工谁负责了哪个部分 ）该课题要求以邻接表的方式储备图,输出邻接表,并要求实现图的深度、广度两种遍历；2.1.1 图的邻接表的建立与输出对任意给定的图 顶点数和边数自定）,并且对有向图与无向图都应进行讨 论,依据邻接表的储备结构建立图的邻接表并输出之；尽量用图形化的方式输 出邻接表；2.1.2 图的遍历的实

4、现图的遍历包括图的广度优先遍历与深度优先遍历；对于广度优先遍历应利 用队列的五种基本运算 置空队列、进队、出队、取队头元素、判队空）来实 现；第一建立一空队列,从初始点动身进行拜访,当被拜访时入队,拜访完出 队；并以队列是否为空作为循环掌握条件；对于深度优先遍历就采纳递归或非 递归算法来实现；2.2 运行环境该程序的运行环境为3.1 图的储备Windows xp 系统, Microsoft Visual C+6.0 版本；第三章 课程设计分析名师归纳总结 本课题要求实行邻接表的储备结构；邻接表是一种链式的储备结构,在邻第 3 页,共 15 页接表中,对图中每个顶点建立一个单链表,第i 个单链表

5、中的结点表示依附于顶点 Vi 的边对有向图是以顶点Vi 为尾的弧）；每个结点由3 个域组成,其中邻接点域 adjvex）指示与顶点Vi 邻接的点在图中的位置,链域nextarc）指示- - - - - - -精选学习资料 - - - - - - - - - 个人资料整理 仅限学习使用下一条边或弧的结点；数据域info）储备和边或弧相关的信息,如权值等；所以一开头必需先定义邻接表的边结点类型以及邻接表类型,并对邻接表 进行初始化,然后依据所输入的相关信息,包括图的顶点数、边数、是否为有 向,以及各条边的起点与终点序号,建立图的邻接表；此时要分两种情形：有 向图与无向图；对于无向图,一条边的两的个

6、顶点,互为邻接点,所以在储备 时,应向起点的单链表表头插入一边结点,即终点；同时将终点的单链表表头 插入一边结点,即起点；对于有向图,只能向起点的单链表的表头插入一个边 结点,即终点；但不能反过来；至于邻接表的输出,由于不明白 C+中的绘图 操作,故采纳 for 语句输出各结点,并协作一些符号完成邻接表的输出；3.2 图的遍历3.2.1 图的深度优先遍历假设初始状态是图中全部顶点未曾被拜访,深度优先遍历可以从图的初始点动身,拜访初始点,然后依次从v 未被拜访的邻接点动身深度优先遍历图,直至图中全部和 v 有路径相通的顶点都被拜访到；如此时仍有顶点未被拜访 到,就从另一个未被拜访的顶点动身,重复

7、上述过程,直至全部点都被拜访到为止；这是一个递归的过程；所以在实现深度优先遍历的过程中必需递归调用 深度优先搜寻函数；而且在深度优先搜寻函数中必需设一标志数组以标记结点 是否被拜访；详细过程应为：先拜访初始点Vi,并标志其已被拜访；此时定义一指向边p结点的指针p,并建立一个while ）循环,以指针所指对象不为空为掌握条件,当 Vi 的邻接点未被拜访时,递归调用深度优先遍历函数拜访之；然后将指针指向下一个边结点；这样就可以完成图的深度优先遍历了；3.2.2 图的广度优先遍历广度优先搜寻遍历类似于树的按层次遍历的过程；假设从图中某顶点 v 出 发,在拜访了 v 之后拜访它们的邻接点,并使“ 先被

8、拜访的顶点的邻接点” 先于“ 后被拜访的顶点的邻接点的邻接点” 被拜访,直到图中全部已被拜访的顶 点的邻接点都被拜访到；如此时图中尙有顶点未被拜访,就另选图中一个未曾 被拜访的顶点作起始点,重复上述过程,直到图中全部顶点都被拜访到为止；换句话说,广度优先搜寻遍历图的过程是以v 为起始点,由近及远,依次拜访和 v 有路径相通且路径长度为 1,2, 的顶点；所以要实现算法必需先建立一个元素类型为整形的空队列,并定义队首与队尾指针,同时也要定义一个标志数组以标记结点是否被拜访；同样,也是从初始点动身开头拜访,拜访初始点,标志其已被拜访,并将其入队；当队列非空时进行循环处理；当结点被拜访时对其进行标志

9、,并入队列；通过 while）循环,并以是否被拜访为掌握条件,拜访全部结点,完成图的广度优先遍历；第四章 算法 /初始化图的邻接表 GL=new edgenode*n；forint i=1 ；iGLi=NULL； 4.1.3 建立并输出图的邻接表 第一必需输入图的相关信息,包括图的顶点数、边数、各条边的起点和终 点,为保证输入数据的正确性,我在程序中设计了一个判定所输结点是否越界 的函数 check）当所输的顶点序号超出序号的范畴时就报错,并要求重新输 入；仍有就图是否有向,此时可定义一变量,图的是否有向,可用变量的值来 m,当图为无向时, m 等于 0；图为有向时 m 等于 1；用 表示；此

10、处定了变量 if ）语句判定 m 的值,就可将图分有向和无向两种情形来进行分析了；对于无 向图,各条边的起点和终点互为邻接点；所以必需把起点添加到终点的邻接点 域中,并把终点添加到起点的邻接点域中；而对于有向图,只能是将弧头添加 到弧尾的邻接点域中；最终是输出邻接表,即对于每个顶点,输出其邻接点；由于不明白 C+中绘图函数的用法,所以利用一些符号来达到图形化的成效；邻接表输出的相关代码如下：cout图的邻接表为 :endl；fori=1 ；i edgenode*p=GLi；couti-1 |Vnext cout|adjvex ；cout|；coutendl； / 输出邻接表名师归纳总结 - -

11、 - - - - -第 5 页,共 15 页精选学习资料 - - - - - - - - - 个人资料整理 仅限学习使用4.2 图的遍历4.2.1 深度优先遍历图的邻接表假设初始状态是图中全部顶点未曾被拜访,深度优先遍历可以从图的初始点动身,拜访初始点,然后依次从v 未被拜访的邻接点动身深度优先遍历图,直至图中全部和 v 有路径相通的顶点都被拜访到；如此时仍有顶点未被拜访 到,就从另一个未被拜访的顶点动身,重复上述过程,直至全部点都被拜访到 为止；这是一个递归的过程；所以在实现深度优先遍历的过程中必需递归调用 深度优先搜寻函数；而且在深度优先搜寻函数中必需设一标志数组以标记结点 是否被拜访；详

12、细过程应为：在深度优先遍历函数的参数中定义一个标志数组 bool*& visited,当某结点已被拜访时,标志数组的值为关键字 ture,未被拜访时其值为 关键字 false；先拜访初始点 Vi,并标志其已被拜访；此时定义一指向边结点的 指针 p,并建立一个 while /从初始点动身深度优先搜寻邻接表 GL 表示的图 couti int j=p-adjvex ； /j 为 Vi 的一个邻接点的序号 if.visitedj dfsAdjoinGL,visited,j,n ；p=p-next； /使 p 指向 Vi 单链表的下一个边结点 4.2.2 广度优先遍历图的邻接表 图的广度优先遍历是从初

13、始点动身,拜访初始点,再拜访初始点的邻接 点；起初始点的全部邻接点都被拜访过时,再依次拜访各邻接点的邻接点；如 此循环下去；算法的实现必需依靠帮助队列,结点被拜访后,对其进行标记,并将结点入队列；所以要实现算法必需先建立一个元素类型为整形的空队列,并定义队首与队尾指针,同时也要定义一个标志数组bool*& visited 以标记结点是否被拜访；名师归纳总结 - - - - - - -第 6 页,共 15 页精选学习资料 - - - - - - - - - 同样,也是从初始点 拜访过的初始点序号个人资料整理仅限学习使用Vi 动身开头拜访,拜访初始点,标志其已被拜访,并将已 i 入队；当队列非空时

14、进行循环处理,删除队首元素,第一次执行时 k 的值为 i,即 front=front+1%MaxLength ；然后取 Vk 邻接表的表头指针 int k=qfront ； edgenode* p=GLk ；当边结点指针 p 不为空时,通过while /依次搜寻 Vk 的每一个结点p 指向 p-next；其中的 while 循环int j=p-adjvex ； /Vj 为 Vk 的一个邻接点 if.visitedj / 如 Vj 没有被拜访过就进行处理coutj%MaxLength；qrear=j； p=p-next； 这样就可以拜访全部结点,完成图的广度优先遍历；第五章 源代码 源代码必需给

15、注释,代码由谁写的请在相应的代码后写明组成员名称）程序 图的储备与遍历头文件 图.h #ifndef GRAPH_H #define GRAPH_H #define MAX_VRTEX_NUM 20 struct edgenode int adjvex； edgenode * next； ； /定义邻接表的边结点类型 ；名师归纳总结 - - - - - - -第 7 页,共 15 页精选学习资料 - - - - - - - - - 个人资料整理 仅限学习使用/初始化图的邻接表 void CreateAdjoinadjlist &GL,int n,int m ；/建立图的邻接表 void dfs

16、Adjoinadjlist GL,bool*&visited,int i,int n；/从初始点动身深度优先搜寻由邻接表 GL 表示的图；void bfsAdjoinadjlist GL,bool*&visited,int i,int n /从初始点动身广度优先搜寻由邻接表 GL 表示的图 #endif 实现文件 图.cpp #include #include #include图.h void Checkint n,int& i,int& j ；void InitGAdjoinadjlist&GL,int n /初始化图的邻接表 GL=new edgenode*n；forint i=1 ；iG

17、Li=NULL； void CreateAdjoinadjlist &GL,int n,int m /建立图的邻接表 int i,j,k,e ；coute；ifm=0 /建立无向图 fork=0；k cout输入第 k 条边的起点和终点序号！ij ；Checkn,i,j； edgenode*p=new edgenode；名师归纳总结 - - - - - - -第 8 页,共 15 页精选学习资料 - - - - - - - - - 个人资料整理 仅限学习使用 p-adjvex=j； p-next=GLi ； GLi=p ； /向序号为 i 的单链表的表头插入一个边结点 p=new edgeno

18、de； p-adjvex=i； p-next=GLj ； GLj=p ； /向序号为 j 的单链表的表头插入一个边结点 coutendl=endl ； cout图的邻接表为 :endl； fori=1；i edgenode*p=GLi； couti-1 |Vnext cout|adjvex； cout|； cout/ 建立有向图 fork=1；k cout输入第 k 条边的起点和终点序号！ij ；Checkn,i,j； /向序号为 i 的表头插入一个边结点 edgenode*p=new edgenode；p-adjvex=j ；p-next=GLi ；GLi=p ；名师归纳总结 - - - -

19、 - - -第 9 页,共 15 页精选学习资料 - - - - - - - - - 个人资料整理 仅限学习使用 cout图的邻接表为 :endl； fori=1；i edgenode*p=GLi； couti-1 |Vnext cout|adjvex； cout|； cout /从初始点动身深度优先搜寻邻接表 GL 表示的图 couti int j=p-adjvex ； /j 为 Vi 的一个邻接点的序号 if.visitedj dfsAdjoinGL,visited,j,n ；p=p-next；/使 p 指向 Vi 单链表的下一个边结点 void bfsAdjoinadjlist GL,b

20、ool*& visited,int i,int n /从初始点动身广度优先搜寻邻接表 GL 表示的图 const int MaxLength=30；名师归纳总结 - - - - - - -第 10 页,共 15 页精选学习资料 - - - - - - - - - 个人资料整理 仅限学习使用int qMaxLength=0 ； /定义一个队列 q,其元素类型为整形 int front=0,rear=0； /定义队首和队尾指针 couti /当队列非空时进行循环处理 front=front+1%MaxLength ； /删除队首元素,第一次执行时 k 的值为 i int k=qfront ； ed

21、genode* p=GLk； /取 Vk 邻接表的表头指针 whilep.=NULL /依次搜寻 Vk 的每一个结点 int j=p-adjvex ；/Vj 为 Vk 的一个邻接点 if.visitedj /如 Vj 没有被拜访过就进行处理 coutj%MaxLength；qrear=j； p=p-next； 名师归纳总结 - - - - - - -第 11 页,共 15 页精选学习资料 - - - - - - - - - 个人资料整理 仅限学习使用void Checkint n,int & i,int & j /检查输入的边序号是否越界,如越界就重输 while1 ifin|jn couti

22、j ； 主函数程序文件 主函数 .cpp #include #include图.h void main int i,n,m ； cout=endl ；coutn；cout输入是否有向 m；bool*visited=new booln ； adjlist gl；InitGAdjoingl,n ； CreateAdjoingl,n,m； cout=endl ；cout图的深度优先遍历序列 :endl；fori=1 ；ivisitedi=false ；dfsAdjoingl,visited,1,n ；coutendl=endl ； cout图的广度优先遍历序列 :endl；fori=1 ；ivisi

23、tedi=false ；名师归纳总结 - - - - - - -第 12 页,共 15 页精选学习资料 - - - - - - - - - 个人资料整理 仅限学习使用bfsAdjoingl,visited,1,n ；coutendl； 第六章 运行结果分析由于实习之初对邻接表的储备结构明白不是很清晰,所以在运行出了一个小错误,即在输出邻接表时,每个结点都少了一个邻接点；通过认真分析,发现是输出 邻接表 的语 句不对, 其中的 fornext.=NULL 出了问题；将其改成 p.=NULL 后,邻接表便可顺当输出；下面就是经修改后以有向图 G1 和无向图 G2 为例的程序运行结果；V1V2 V1

24、V2 V V V VV3 VVVV3V4 V4V5 图 1 G1 图 2 G21.有向图 G1 的运行结果名师归纳总结 - - - - - - -第 13 页,共 15 页精选学习资料 - - - - - - - - - 个人资料整理 仅限学习使用图 3 G1 的运行结果2无向图 G2的运行结果图 4 G2 的运行结果第七章 终止语转瞬,为期两周的数据结构课程设计实习即将终止了；在这次实习 中,自己的 C 语言学问和数据结构学问得到了巩固,编程才能也有了肯定的提 高；同时也学会明白决问题的方法；总结起来,自己主要有以下几点体会：1.必需坚固把握基础学问；由于 C 语言是大一所学学问,有所遗忘,

25、且未 把握好这学期所学的数据结构这门课,所以在实习之初感到麻烦；不知如 何下手,但在后来的实习过程中自己通过看书和课外资料,并请教其他同学,渐渐地对 C 语言和数据结构学问有所熟识；这时才逐步有了思路；所以,这次 实习之后,我警告自己：今后肯定要坚固把握好专业基础学问；2.必需培育严谨的科学态度；自己在编程时常常由于一些类似于“ 少了分 号” 的小错误而导致错误,不够认真细致,这给自己带来了很多麻烦；编程是 一件特别严谨的事情,容不得马虎；所以在今后自己肯定要培育严谨的科学态 度；我想这不仅是对于程序设计,做任何事都应如此；名师归纳总结 - - - - - - -第 14 页,共 15 页精选学习资料 - - - - - - - - - 个人资料整理 仅限学习使用3.这次课程设计也让我充分熟识到数据结构这门课的重要性；它给我 们一个思想和大纲,让我们在编程时简单找到思路,不至于无章可循；同时它也有广泛的实际应用；总之,在这次实习中,自己的 力也得到了提高；C 语言以及数据结构学问得到提高,编程能第八章参考文献 要求不少于5 篇,可以是论文,可以是专著 ）名师归纳总结 1 杨路明 C 语言程序设计教程北京邮电高校出版社第 15 页,共 15 页2 徐孝凯数据结构课程试验清华高校出版社3 严蔚敏 吴伟民数据结构 C 语言版）清华高校出版社- - - - - - -