专业课程设计任务书

1、电脑科学与技术专业课程设计任务书学生专业班级学号题目图的遍历课题性质其他课题来源自拟课题指导教师同组主要内容建立图的存储结构输出两种遍历任务要求对任息给正的图顶点数和边数自正义，建立匕的邻接表输出，然后利用栈的五种基本运算活空堆栈，压栈，弹出，取栈顶元素，判空栈实现图的深度搜索遍历和广度优先搜素遍历算法参考文献1 谭浩强，C程序设计第二版，北京,清华大学出版社,2005年1月2 严蔚敏，吴伟民，数据结构C语言版，北京，清华大学出版社,2005年10月3 许卓群，杨冬青等，数据结构与算法，高等教育出版社,20044 朱战立，数据结构，西安电子科技大学出版社,2003审查意见指导教师签字：教研室主

2、任签字：年月日说明：本表由指导教师填写，由教研室主任审核后下达给选题学生，装订在设计论文首页课程设计课程设计名称：数据结构专业班级：学生姓名：学号：指导教师：课程设计时间:一、需求分析对任意给定的图顶点数和边数自定义，建立它的邻接表输出，然后利用栈的五种基本运算活空堆栈，压栈，弹出，取栈顶元素，判空栈实现图的深度搜索遍历和广度优先搜素遍历算法二、概要设计邻接表是图的一种链式存储结构为，类似丁树的孩子链表表法。在邻接表中，对图中每个顶点建立一个单链表，n个顶点，就要建n个链表。对丁无向图，第i个单链表中的结点表示依赖丁顶点Vi的边。对丁有向图是以顶点Vi为尾的弧,这个单链表称为顶点Vi的单链表（

3、即V的邻接表）。单链表中每一个结点称为表结点，应包括两个域：邻接点域，用以存放与Vi相邻接的顶点序号；链域用以指向民Vi邻接的下一个结点。另外，每一个单链表设一个表头结点。每一个表头结点有两个域，一个用来存放顶点vi的信息；另一个域用来指向Vi的邻接表中的第一个结点。为了便丁管理和随机访问任一顶点的单链表，将所有单链表的头结点组织成一个一维数组。vertexlinkadjvexnext顶点顶点链头链针地址邻接表的表头和表结点形式typedefstructnode（intadjvex;/弧指向顶点的位置structnode*next;/指向下一条弧的指针edgenode;/表结点typedefs

4、truct/头结点charvertex;/顶点信息edgenode*link;/指向第一条依附该顶点的弧的指针vexnode,AdjListmaxvertexnum;建立邻接表的方法是：首先将邻接表表头数组初始化，第i个表头的vertex初始化为i,;link初始化为NULL然后读入顶点对<i.j>,产生一个表结点，将j放入到该结点的adjvex域，将该结点链到邻接表的表头的T第i个表头的link域上。2. 深度优先遍历算法输出起始顶点，同时置起始顶点已访问的标记a取当前栈顶顶点b假设栈顶顶点存在未被访问的邻接结点，则选择一个顶点进行一下步骤:输出该顶点置该顶点已访问标记将该顶点进

5、栈c否测当前顶点退栈存储结构typedefstruct/栈int*data;/栈底指针3. int*top;/栈顶指针seqstack;广度优先遍历算法置起始顶点已访问标记，并将该顶点入队a取对头顶点b依次访问与顶点相邻的未被访问的顶点访问该顶点置该顶点为已被访问的标记，并将它入队c当前对头元素顶点出队d重复进行直到对空时结束三、运行环境软、硬件环境四、开发工具和编程语言开发工具和编程语言：数据结构C语言数据结构c语言五、详细设计#include<stdio.h>#include<stdlib.h>#include<malloc.h>#defineFalse

6、0#defineTrue1#defineNull0#definemaxsize20/队歹U的最大空间#definemaxvertexnum20/最大顶点数typedefstructnodeintadjvex;/弧指向顶点的位置structnode*next;/指向下一条弧的指针edgenode;/表结点typedefstruct/头结点charvertex;/顶点信息edgenode*link;/指向第一条依附该顶点的弧的指钉vexnode,AdjListmaxvertexnum;typedefstruct/图AdjListadjlist;intn,e;/n顶点数，e边数Graph;typed

7、efstruct/栈int*data;/栈底指针int*top;/栈顶指针seqstack;/全局变量vexnodegmaxvertexnum;/先定义后使用vexnode,邻接表g为全程变量intvisitedmaxvertexnum;/定义visit为全程向量voidCreatAdjList(Graph&G)inti,j,k;/i,j为邻接点序号edgenode*s;charc;printf("请输入定点数和边数：n");scanf("%d,%d”,&G.n,&G.e);c=getchar();printf("请输入顶点信息(

8、顶点号):n");for(i=1;i<=G.n;i+)/建立有n个顶点的顶点表printf("第朴顶点为",i);scanf("%c",&G.adjlisti.vertex);c=getchar();G.adjlisti.link=NULL;printf("请输入边的信息():n");for(k=1;k<=G.e;k+)/建立边表printf(-请输入请输入第d>边起始顶点编号：n",k);scanf("%d",&i);printf(-请输入请输入第d>边

9、终顶点编号:n",k);scanf("%d",&j);s=(edgenode*)malloc(sizeof(edgenode);/分配顶点空间s->adjvex=j;s->next=G.adjlisti.link;G.adjlisti.link=s;voidDisplayAdjList(GraphG)inti;edgenode*q;for(i=1;i<=G.n;+i)q=G.adjlisti.link;printf("%d",i);while(q!=NULL)printf("->%d",q-&

10、gt;adjvex);q=q->next;printf("n");voidDFSAL(GraphG)edgenode*p;seqstacks;inti=1,t;for(i=1;i<=G.n;i+)visitedi=0;printf(-这是深度优先遍历，遍历顺序为:n");/输出起始顶点s.data=(int*)malloc(maxsize*sizeof(seqstack);s.top=s.data;/初始化栈for(i=1;i<=G.n;i+)/考虑到图可能不连通p=G.adjlisti.link;t=i；if(p=NULL)/p=NULL时，即

11、该结点没有邻结点(if(!visitedt)(printf("%c”,G.adjlistt.vertex);/如果此时该结点没有被访问过，则访问visitedt=True;continue;/即该结点没有邻结点，本次循环结束doif(p=NULL)/即到了图的最底层s.top-;/没有下个邻接点，则退回前一个顶点p=G.adjlist*s.top.link;if(p!=NULL)t=p->adjvex;elseif(!visitedt)/该结点中p!=NULL且其没有被访问过printf("%c",G.adjlistt.vertex);/输出该顶点visit

12、edt=True;/置为已访问if(G.adjlistt.link=NULL)continue;*s.top=t;s.top+;/进栈p=G.adjlistt.link;/p指针指到以G.adjlistt.vertex为起点的第一条边，如果/p=NULLif(p=NULL)/如果该结点没有邻接点则输出之if(!visitedt)printf("%c",G.adjlistt.vertex);elset=p->adjvex;/如果该结点有邻接点，则把其邻接点的顶点号赋值给telse/如果该结点被访问过，且有邻结点，p指向以当前结点的邻接点为起点的边/也可能P=NULL(p

13、=p->next;if(p!=NULL)t=p->adjvex;/如果该邻接点有邻接点，则记下其邻接点的位置while(s.top!=s.data);voidBFSAL(GraphG)(intv,Qmaxsize;edgenode*w;printf(-这是广度优先遍历，遍历顺序为:n");intfront=0,rear=0;/辅助队歹U置空for(v=1;v<=G.n;v+)visitedv=0;for(v=1;v<=G.n;v+)if(!visitedv)(visitedv=1;printf("%c",G.adjlistv.vertex)

14、;Qrear=v;rear+;/入队while(front!=rear)(/队不空front+;出队w=G.adjlistv.link;while(w)(if(!visitedw->adjvex)(visitedw->adjvex=1;/访问w;printf("%c”,G.adjlistw->adjvex.vertex);Qrear=w->adjvex;rear+;w=w->next;voidmain()(GraphG;intchoice;charch;printf("-创建邻接表存储的图");CreatAdjList(G);prin

15、tf("已创建一个图了邻接表n");DisplayAdjList(G)while(ch!='n')(printf("n请选择操作：");printf("n1-深度优先遍历：");printf("n2-广度优先遍历");printf("n3-退出n");scanf("%d",&choice);switch(choice)(case1:DFSAL(G);break;case2:BFSAL(G);break;case3:ch='n'break

16、;default:ch='n'六、调试分析在图的创建过程中就遇到了问题，应为少了接受字符的getchar()函数，使得再输入顶点信息字符型后无法再执行CreatAdjlist()中剩下的语句，导致创建失败！再经同学提醒后成功创建了图。在图的深度和广度遍历时，由于其出的思路不够活晰，导致在写时漏考虑了一些情况致使无法得出想要的结果。在参阅了一些资料后，将思路搞活楚后，利用非递归得到了想要的结果！七、测试结果八、参考文献在“课程设计报告”的最后应附上所参考的相关文献,参考文献的书写格式如下：书籍：作者，书名，版本，出版地，出版者，出版年，引用内容所在页码论文：作者，论文篇名，刊物名

17、，年月卷，论文在刊物中的页码要求：必须独立完成，不能互相抄袭。设计完成后，将所完成的工作交由老师检查。并写出一份详细的实习报告。数据结构课程设计总结“要想学好一门语言，就要多用它！”虽然老师课上讲一些算法的思路彳艮活楚，但是光靠课堂上的一些理论的知识远远不够的。那些只是一个基础，只有通过自己上机调试发现问题，解决问题才能更好，更深入的学好这门语言，运用好这门语言！就拿这次的课程设计来说，课程设计的目的是培养学生综合运用所学知识，发现，提出，分析和解决实际问题，锻炼实践能力的重要环节，是对学生实际工作能力的具体训练和考察过程.从拿到题目到完成整个编程，才短短一个星期。可是却学到很多很多的东西，同

18、时不仅可以稳固了以前所学过的知识，而且增强了自己的分析和调试能力。这次我抽到的题目是图的遍历，这是之前的一道上机题，只是要求有点不同罢了。因此，开始准备实验比较晚，觉得即使实验中遇到困难了，到时问一下同学一会就能解决的。而且在写程序过程中一直把重点放在深度优先遍历和广度优先遍历那部分，觉得那才是整个课题的重点。可是令我没想到的是，在用邻接表创建图的过程中就出现问题了，在CreatAdjList()函数中，在进入创建顶点信息的for循环之后，直接跳出了CreatAdjList()函数。本能的去查看循环条件可是当确定循环条件没错时，真的对它素手无册了。请教了几个同学，在那调试了半天也没结果。后来在

19、机房一位经常调试程序的同学，一眼便看出了问题所在。是因为少了一个接受字符的getchar:函数。照他说的在一些地方增加了getchar函数，调试了一下，真的能顺利创建了。小小高兴了一番！回去时忘保存修改稿，于是在自己的电脑上改，可是怎么都创建不成功。于是就在程序中瞎试，几乎把getchar在哪都试了，最后搞了半天也不成。就在网上拼命找getchar函数的用法，“getchar；的用法很多：一种就是你这个程序用到的活空回车符这种情况一般发生在在循环中涉及到输入的情况；还有一种是某些编译平台IDE)在运行程序时并没有在程序运行后给人看结果的时间这时候在程序最后加上getchar就能造成程序的暂停给程序员度结果的时机”,在了解了大致的用法后，再改，可是还是不行。后来才发现是安装了近一年但却从未运行过的运行环境出问题了。可是通过这次的经历让我了解到了，其实如果要学好一门语言，平常的一些小的知识点自己也要多留意，不能无视。因为一些看似不起眼的小知识点的残缺就有可能导致你的程序整