数据结构课程设计图的存储与遍历报告

数据结构课程 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 图的存储与遍历报告 《数据结构》课程设计 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 目 图的存储与遍历 学生姓名 指导教师 学 院 专业班级 完成时间 目 录 第一章 课程设计目的 ??????????????????????????????????????????????????????????????? 2 第二章 课程设计 内容 财务内部控制制度的内容财务内部控制制度的内容人员招聘与配置的内容项目成本控制的内容消防安全演练内容 和要求 ???????????????????????????????????????????????????? 2 第三章 课程设计 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 ???????????????????????????????????????????????????????????????? 3 第四章 算法描述 ???????????????????????????????????????????????????????????????????????? 4 第五章 源代码 ????????????????????????????????????????????????????????????????????????????? 8 第六章 运行结果分析 ?????????????????????????????????????????????????????????????? 13 第七章 结束语 ??????????????????????????????????????????????????????????????????????????? 15 第八章 参考文献 ?????????????????????????????????????????????????????????????????????? 15 1 第一章 课程设计目的 本学期我们对《数据结构》这门课程进行了学习。这门课程是一门实践性非 常强的课程，为了让大家更好地理解与运用所学知识，提高动手能力，我们进行 了此次课程设计实习。这次课程设计不但要求实习者掌握《数据结构》中的各方 面知识，还要求实习者具备一定的C语言基础和编程能力。 具体说来，这次课程设计主要有两大方面目的。 一是让实习者通过实习掌握《数据结构》中的知识。对于《图的存储与遍历》 这一课题来说，所要求掌握的数据结构知识主要有：图的邻接表存贮结构、队列 的基本运算实现、邻接表的算法实现、图的广度优先搜索周游算法实现、图的深 度优先搜索周游算法实现。 二是通过实习巩固并提高实习者的C语言知识，并初步了解Visual C++的知 识，提高其编程能力与专业水平。 第二章 课程设计内容和要求 2.1课程设计内容 该课题要求以邻接表的方式存储图，输出邻接表，并要求实现图的深度、广 度两种遍历。 2.1.1图的邻接表的建立与输出 对任意给定的图（顶点数和边数自定），并且对有向图与无向图都应进行讨 论，根据邻接表的存储结构建立图的邻接表并输出之。尽量用图形化的方式输出 邻接表。 2.1.2 图的遍历的实现 图的遍历包括图的广度优先遍历与深度优先遍历。对于广度优先遍历应利用 队列的五种基本运算（置空队列、进队、出队、取队头元素、判队空）来实现。 首先建立一空队列，从初始点出发进行访问，当被访问时入队，访问完出队。并 以队列是否为空作为循环控制条件。对于深度优先遍历则采用递归或非递归算法 来实现。 2.2 运行环境 该程序的运行环境为Windows xp系统，Microsoft Visual C++6.0版本。 第三章 课程设计分析 3.1图的存储 本课题要求采取邻接表的存储结构。邻接表是一种链式的存储结构，在邻接 表中，对图中每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点Vi的边（对有向图是以顶点Vi为尾的弧）。每个结点由3个域组成，其中邻接点域（adjvex）指示与顶点Vi邻接的点在图中的位置，链域（nextarc）指示下一条 2 边或弧的结点；数据域（info）存储和边或弧相关的信息，如权值等。 所以一开始必须先定义邻接表的边结点类型以及邻接表类型，并对邻接表进 行初始化，然后根据所输入的相关信息，包括图的顶点数、边数、是否为有向， 以及各条边的起点与终点序号，建立图的邻接表。此时要分两种情况：有向图与 无向图。对于无向图，一条边的两的个顶点，互为邻接点，所以在存储时，应向 起点的单链表表头插入一边结点，即终点。同时将终点的单链表表头插入一边结 点，即起点。对于有向图，只能向起点的单链表的表头插入一个边结点，即终点。 但不能反过来。至于邻接表的输出，由于不了解C++中的绘图操作，故采用for语句输出各结点，并配合一些符号完成邻接表的输出。 3.2 图的遍历 3.2.1 图的深度优先遍历 假设初始状态是图中所有顶点未曾被访问，深度优先遍历可以从图的初始点 出发，访问初始点，然后依次从v未被访问的邻接点出发深度优先遍历图，直至 图中所有和v有路径相通的顶点都被访问到；若此时仍有顶点未被访问到，则从 另一个未被访问的顶点出发，重复上述过程，直至所有点都被访问到为止。这是 一个递归的过程。所以在实现深度优先遍历的过程中必须递归调用深度优先搜索 函数。而且在深度优先搜索函数中必须设一标志数组以标记结点是否被访问。 具体过程应为：先访问初始点Vi，并标志其已被访问。此时定义一指向边 结点的指针p，并建立一个while（）循环，以指针所指对象不为空为控制条件， 当Vi的邻接点未被访问时，递归调用深度优先遍历函数访问之。然后将p指针指向下一个边结点。这样就可以完成图的深度优先遍历了。 3.2.2 图的广度优先遍历 广度优先搜索遍历类似于树的按层次遍历的过程。假设从图中某顶点v出发，在访问了v之后访问它们的邻接点，并使“先被访问的顶点的邻接点”先于 “后被访问的顶点的邻接点的邻接点”被访问，直到图中所有已被访问的顶点的 邻接点都被访问到。若此时图中尙有顶点未被访问，则另选图中一个未曾被访问 的顶点作起始点，重复上述过程，直到图中所有顶点都被访问到为止。换句话说， 广度优先搜索遍历图的过程是以v为起始点，由近及远，依次访问和v有路径相通且路径长度为1，2，„„的顶点。 所以要实现算法必须先建立一个元素类型为整形的空队列，并定义队首与队 尾指针，同时也要定义一个标志数组以标记结点是否被访问。同样，也是从初始 点出发开始访问，访问初始点，标志其已被访问，并将其入队。当队列非空时进 行循环处理。当结点被访问时对其进行标志，并入队列。通过while（）循环，并以是否被访问为控制条件，访问所有结点，完成图的广度优先遍历。 第四章 算法（数据结构）描述 4.1 图的存储结构的建立。 4.1.1 定义邻接表的边结点类型以及邻接表类型 struct edgenode{ 3 int adjvex; //该弧所指向的顶点的位置 edgenode * next; //指向下条条弧的指针 }; //定义邻接表的边结点类型 typedef edgenode * * adjlist; //定义邻接表类型 4.1.2 初始化图的邻接表 需建立一个邻接表初始化函数对图的邻接表进行初始化。即建立一个所有边 结点都为空的邻接表。 void InitGAdjoin(adjlist&GL,int n) //初始化图的邻接表 { GL=new edgenode*[n]; for(int i=1;i<=n;i++)GL[i]=NULL; } 4.1.3 建立并输出图的邻接表 首先必须输入图的相关信息，包括图的顶点数、边数、各条边的起点和终点， 为保证输入数据的正确性，我在程序中设计了一个判断所输结点是否越界的函数 check（）当所输的顶点序号超出序号的范围时则报错，并要求重新输入。还有 就图是否有向，此时可定义一变量，图的是否有向，可用变量的值来表示。此处 定了变量m，当图为无向时，m等于0。图为有向时m等于1。用if（）语句判 断m的值，就可将图分有向和无向两种情况来进行分析了。对于无向图，各条 边的起点和终点互为邻接点。所以必须把起点添加到终点的邻接点域中，并把终 点添加到起点的邻接点域中。而对于有向图，只能是将弧头添加到弧尾的邻接点 域中。最后是输出邻接表，即对于每个顶点，输出其邻接点。由于不了解C++ 中绘图函数的用法，所以利用一些符号来达到图形化的效果。邻接表输出的相关 代码如下： cout<<"图的邻接表为:"<next) cout<<"|-|->|"<adjvex; cout<<"|^|"; cout<adjvex; //j为Vi的一个邻接点的序号 if(!visited[j]) dfsAdjoin(GL,visited,j,n); p=p->next; //使p指向Vi单链表的下一个边结点 } } 4.2.2 广度优先遍历图的邻接表 图的广度优先遍历是从初始点出发，访问初始点，再访问初始点的邻接点。 当初始点的所有邻接点都被访问过时，再依次访问各邻接点的邻接点。如此循环 下去。算法的实现必须依靠辅助队列，结点被访问后，对其进行标记，并将结点 入队列。 所以要实现算法必须先建立一个元素类型为整形的空队列，并定义队首与队 尾指针，同时也要定义一个标志数组bool*& visited以标记结点是否被访问。同样，也是从初始点Vi出发开始访问，访问初始点，标志其已被访问，并将已访 问过的初始点序号i入队。当队列非空时进行循环处理，删除队首元素，第一次 执行时k的值为i，即front=(front+1)%MaxLength。然后取Vk邻接表的表头指 5 针int k=q[front]; edgenode* p=GL[k]。当边结点指针p不为空时，通过while（） 循环，并以p是否为空为控制条件，依次搜索Vk的每一个结点。若Vj没有被 访问过则进行处理。访问完后，将p指向p->next。其中的while循环部分的代码 如下： while(p!=NULL){ //依次搜索Vk的每一个结点 int j=p->adjvex; //Vj为Vk的一个邻接点 if(!visited[j]){ //若Vj没有被访问过则进行处理 cout<next; } 这样就可以访问所有结点，完成图的广度优先遍历。 第五章 源代码 程序 图的存储与遍历 头文件 图.h #ifndef GRAPH_H #define GRAPH_H #define MAX_VRTEX_NUM 20 struct edgenode{ int adjvex; edgenode * next; }; //定义邻接表的边结点类型 typedef edgenode **adjlist; //定义邻接表类型 void InitGAdjoin(adjlist &GL,int n); //初始化图的邻接表 void CreateAdjoin(adjlist &GL,int n,int m); //建立图的邻接表 6 void dfsAdjoin(adjlist GL,bool*&visited,int i,int n); //从初始点出发深度优先搜索由邻接表GL表示的图 void bfsAdjoin(adjlist GL,bool*&visited,int i,int n); //从初始点出发广度优先搜索由邻接表GL表示的图 #endif 实现文件 图.cpp #include #include #include"图.h" void Check(int n,int& i,int& j); void InitGAdjoin(adjlist&GL,int n) //初始化图的邻接表 { GL=new edgenode*[n]; for(int i=1;i<=n;i++)GL[i]=NULL; } void CreateAdjoin(adjlist &GL,int n,int m) //建立图的邻接表 { int i,j,k,e; cout<<"输入图的总边数："; cin>>e; if(m==0){ //建立无向图 for(k=0;k>i>>j; Check(n,i,j); edgenode*p=new edgenode; p->adjvex=j; p->next=GL[i]; GL[i]=p; 7 //向序号为i的单链表的表头插入一个边结点 p=new edgenode; p->adjvex=i; p->next=GL[j]; GL[j]=p; //向序号为j的单链表的表头插入一个边结点 } cout<next) cout<<"|-|->|"<adjvex; cout<<"|^|"; cout<>i>>j; Check(n,i,j); //向序号为i的表头插入一个边结点 edgenode*p=new edgenode; p->adjvex=j; p->next=GL[i]; GL[i]=p; } cout<<"图的邻接表为:"<next) cout<<"|-|->|"<adjvex; cout<<"|^|"; cout<adjvex; //j为Vi的一个邻接点的序号 if(!visited[j]) dfsAdjoin(GL,visited,j,n); p=p->next; //使p指向Vi单链表的下一个边结点 } } void bfsAdjoin(adjlist GL,bool*& visited,int i,int n) //从初始点出发广度优先搜索邻接表 GL表示的图 { const int MaxLength=30; int q[MaxLength]={0}; //定义一个队列q,其元素类型为整形 int front=0,rear=0; 9 //定义队首和队尾指针 cout<adjvex; //Vj为Vk的一个邻接点 if(!visited[j]){ //若Vj没有被访问过则进行处理 cout<next; } } } void Check(int n,int & i,int & j) //检查输入的边序号是否越界，若越界则重输 { 10 while(1){ if(i<=0||i>n||j<=0||j>n) cout<<"输入有误,请重新输入！"; else return; cin>>i>>j; } } 主函数程序文件 主函数.cpp #include #include"图.h" void main() { int i,n,m; cout<<"=============="<>n; cout<<"输入是否有向（0为无，1为有）:"; cin>>m; bool*visited=new bool[n]; adjlist gl; InitGAdjoin(gl,n); CreateAdjoin(gl,n,m); cout<<"=============="<next!=NULL出了问题。将其改成p!=NULL后，邻接表便可顺利输出。下面就是经修改后以 有向图G1和无向图G2为例的程序运行结果。 V1 V2 V1 V2 V V V V V V3 V3 V4 V4 V5 V V 图1 G1 图2 G2 1.有向图G1的运行结果 图3 G1的运行结果 12 2．无向图G2的运行结果 图4 G2的运行结果 第七章 结束语 转眼，为期两周的《数据结构》课程设计实习即将结束了。在这次实习中， 自己的C语言知识和数据结构知识得到了巩固，编程能力也有了一定的提高。 同时也学会了解决问题的方法。 总结 初级经济法重点总结下载党员个人总结TXt高中句型全总结.doc高中句型全总结.doc理论力学知识点总结pdf 起来，自己主要有以下几点体会： 1.必须牢固掌握基础知识。由于C语言是大一所学知识，有所遗忘，且未掌握好这学期所学的《数据结构》这门课，所以在实习之初感到棘手。不知如何下 手，但在后来的实习过程中自己通过看书和课外资料，并请教其他同学，慢慢地 对C语言和数据结构知识有所熟悉。这时才逐渐有了思路。所以，这次实习之 后，我告诫自己：今后一定要牢固掌握好专业基础知识。 2.必须培养严谨的科学态度。自己在编程时经常因为一些类似于“少了分号” 的小错误而导致错误，不够认真细致，这给自己带来了许多麻烦。编程是一件十 分严谨的事情，容不得马虎。所以在今后自己一定要培养严谨的科学态度。我想 这不仅是对于程序设计，做任何事都应如此。 3.这次课程设计也让我充分认识到《数据结构》这门课的重要性。它给我们 一个思想和大纲，让我们在编程时容易找到思路，不至于无章可循。同时它也有 广泛的实际应用。 总之，在这次实习中，自己的C语言以及数据结构知识得到提高，编程能 13 力也得到了提高。 第八章 参考文献 1． 杨路明 C语言程序设计教程 北京邮电大学出版社 2． 徐孝凯 数据结构课程实验 清华大学出版社 3． 严蔚敏 吴伟民 数据结构（C语言版） 清华大学出版社 14