搜索
课程设计(论文)任务书学院专业班一、课程设计(论文)题目数据结构课程设计(A)二、课程设计(论文)工作自2009年12月22日起至2011年12月23日止。三、课程设计(论文)地点:软件工程实训中心四、课程设计(论文)内容要求：1．本课程设计的目的（1）使学生熟练掌握抽象数据类型的组织和定义；（2）使学生熟练掌握数据类型的定义和实现；（3）培养学生组织和分析数据的能力；（4）培养学生分析和应用基于不同数据结构的算法的能力；（5）提高学生的科技论文写作能力。2．基本要求：每位同学在以下题目中任选一题（在方框中打勾），独立完成课程设计：□停车场管理：参见《数据结构题集》P96。□哈希表设计：参见《数据结构题集》P166。□校园导游咨询：参见《数据结构题集》P151。3．课程设计论文编写要求（1）要按照书稿的规格打印誊写课设报告；（2）报告分为封面、任务书（本文档）、正文、课程设计体会和参考文献四部分；学生签名：2009年12月日课程设计(论文)评审意见（1）题目分析（20分）：优（）、良（）、中（）、一般（）、差（）；（2）流程分析（30分）：优（）、良（）、中（）、一般（）、差（）；（3）数据定义（30分）：优（）、良（）、中（）、一般（）、差（）；（4）代码编写（10分）：优（）、良（）、中（）、一般（）、差（）；（5）创新能力（10分）：优（）、良（）、中（）、一般（）、差（）；（6）格式规范性、设计态度及考勤是否降等级：是（）、否（）评阅人：职称：讲师2010年1月5日3正文一、数据结构定义1.抽象数据类型本设计中用到的数据结构ADT定义如下：ADTGraph{数据对象：V是具有相同特性的数据元素的集合，成为顶点集。数据关系：R={VR}VR={v,w|v,w∈V且P(v,w)，v,w表示从v到w的弧，谓词P(v,w)定义了v,w之间关系的意义或信息。}基本操作P:intcreatgragh(mgraph&c)操作结果：构造图的邻接矩阵intnewgraph(mgraph&c)操作结果：更新图的部分信息。返回值:1intenarc(mgraph&c)操作结果：增加一条边。返回值：1intenvex(mgraph&c)操作结果：增加一个结点。返回值：1intdelvex(mgraph&c)操作结果：删除图的一个顶点。返回值：1intdelarc(mgraph&c)操作结果：删除图的一条边。返回值：1voidprintmatrix(mgraphc)操作结果：输出图的邻接矩阵的值intchangegraph(mgraph&c)4操作结果：图操作的主调函数。返回值：1voidshortestpath_floyd(mgraphc)操作结果：查询两景点间的最短路径voidseeabout(mgraphc)操作结果：查询景点的信息voidbrowsecompus(mgraphc)操作结果：显示所有景点信息}ADTGraph2.存储结构定义数据存储结构的C语言定义如下：typedefstructarcell｛//边的权值信息intadj;//权值}arcell,adjmatrix[MaxVertexNum][MaxVertexNum];//图的邻接矩阵类型typedefstructvexsinfo｛//顶点信息intposition;//景点的编号charname[32];//景点的名称charintroduction[256];//景点的介绍}vexsinfo;typedefstructmgraph｛//图结构信息vexsinfovexs[MaxVertexNum];//顶点向量(数组)adjmatrixarcs;//邻接矩阵intvexnum,arcnum;//分别指定顶点数和边数}mgraph;3.基本操作数据结构的基本操作实现如下：mgraphinitgraph(){//(1)对图初始化5inti=0,j=0;mgraphc;c.vexnum=12;//顶点个数c.arcnum=14;//边的个数for(i=0;ic.vexnum;i++)//依次设置顶点编号c.vexs[i].position=i;//依次输入顶点信息strcpy(c.vexs[0].name,北区大门);strcpy(c.vexs[0].introduction,出门左转20米有公交车站直达市区);strcpy(c.vexs[1].name,十五栋综合楼);strcpy(c.vexs[1].introduction,北区最大综合楼);strcpy(c.vexs[2].name,34~36栋，运动馆);strcpy(c.vexs[2].introduction,学生宿舍，室内运动馆包括篮球场、网球场等);strcpy(c.vexs[3].name,42~44栋);strcpy(c.vexs[3].introduction,学生宿舍);strcpy(c.vexs[4].name,北区礼堂);strcpy(c.vexs[4].introduction,礼堂);strcpy(c.vexs[5].name,北区食堂);strcpy(c.vexs[5].introduction,1~3楼为食堂，3楼食堂全天开放，四楼运动场);strcpy(c.vexs[6].name,37~41栋);strcpy(c.vexs[6].introduction,学生宿舍);strcpy(c.vexs[7].name,室内游泳馆);strcpy(c.vexs[7].introduction,较偏僻，暂未投入使用);strcpy(c.vexs[8].name,足球场,田径场);strcpy(c.vexs[8].introduction,田径场刚建成还不错);strcpy(c.vexs[9].name,二十二栋、北区篮球场);6strcpy(c.vexs[9].introduction,继续教育学院、若干篮球场一个排球场);strcpy(c.vexs[10].name,交大驾校);strcpy(c.vexs[10].introduction,学车方便);strcpy(c.vexs[11].name,北区招待所);strcpy(c.vexs[11].introduction,北区招待所);for(i=0;ic.vexnum;i++)//依次输入边上的权值信息for(j=0;jc.vexnum;j++)c.arcs[i][j].adj=Infinity;//先初始化图的邻接矩阵c.arcs[0][1].adj=1;c.arcs[0][2].adj=5;c.arcs[0][3].adj=10;//部分弧长c.arcs[1][5].adj=2;c.arcs[2][4].adj=1;c.arcs[2][5].adj=5;c.arcs[2][11].adj=6;c.arcs[3][9].adj=11;c.arcs[4][9].adj=5;c.arcs[5][6].adj=2;c.arcs[6][7].adj=3;c.arcs[8][11].adj=2;c.arcs[8][10].adj=9;c.arcs[9][11].adj=3;for(i=0;ic.vexnum;i++)//邻接矩阵是对称矩阵，对称赋值for(j=0;jc.vexnum;j++)c.arcs[j][i].adj=c.arcs[i][j].adj;returnc;}//initgraphintlocatevex(mgraphc,intv){//(2)查找景点在图中的序号inti;for(i=0;ic.vexnum;i++)7if(v==c.vexs[i].position)returni;//找到，返回顶点序号ireturn-1;//否则，返回-1}voidpath(mgraphc,intm,intn,intk){//(3)打印序号为m,n景点间的长度不超过8个景点的路径ints,x=0;intt=k+1;//t记载路径上下一个中间顶点在d[]数组中的下标if(d[k]==n&&k8){//d[k]存储路径顶点。若d[k]是终点n且景点个数=8，则输出该路径for(s=0;sk;s++)//递归出口，找到一条路径printf(%s---,c.vexs[d[s]].name);//输出该路径。s=0时为起点mprintf(%s,c.vexs[d[s]].name);//输出最后一个景点名(即顶点n的名字，此时s==k)printf(\n\n);}else{s=0;while(sc.vexnum){//从第m个顶点，试探至所有顶点是否有路径if((c.arcs[d[k]][s].adjInfinity)&&(visited[s]==0)){//初态：顶点m到顶点s有边，且未被访问visited[s]=1;d[k+1]=s;//存储顶点编号s至d[k+1]中path(c,m,n,t);//求从下标为t=k+1的第d[t]个顶点开始的路径(递归调用)，同时打印出一条m至n的路径visited[s]=0;//将找到的路径上顶点的访问标志重新设置为0，以用于试探新的路径8}s++;//试探从下一个顶点s开始是否有到终点的路径}//endwhile}//endelse}//endpathintallpath(mgraphc){//(4)打印两景点间的景点个数不超过8的所有路径。调用(3)intk,i,j,m,n;printf(\n\n请输入你要查询的两个景点编号:\n\n);scanf(%d%d,&i,&j);printf(\n\n);m=locatevex(c,i);//调用(2)，确定该顶点是否存在。若存在，返回该顶点编号n=locatevex(c,j);d[0]=m;//存储路径起点m(intd[]数组是全局变量)for(k=0;kc.vexnum;k++)//全部顶点访问标志初值设为0visited[k]=0;visited[m]=1;//第m个顶点访问标志设置为1path(c,m,n,0);//调用(3)。k=0，对应起点d[0]==m。k为d[]数组下标return1;}voidshortestpath_dij(mgraphc){//(5)用迪杰斯特拉算法，求出一个景点到其他景点间的最短路径，并打印//迪杰斯特拉算法，求从顶点v0到其余顶点的最短路经及其带权长度d[v]//若p[v][w]为1，则w是从v0到v的最短路经上的顶点//final[v]类型用于设置访问标志intv,w,i,min,t=0,x,flag=1,v0;//vo为起始景点的编号9intfinal[35],d[35],p[35][35];printf(\n请输入一个起始景点的编号：);scanf(%d,&v0);printf(\n\n);while(v00||v0c.vexnum){printf(\n你所输入的景点编号不存在\n);printf(请重新输入：);scanf(%d,&v0);}//whilefor(v=0;vc.vexnum;v++){final[v]=0;//初始化各顶点访问标志d[v]=c.arcs[v0][v].adj;//v0到各顶点v的权值赋值给d[v]for(w=0;wc.vexnum;w++)//初始化p[][]数组，各顶点间的路径全部设置为空路径0p[v][w]=0;if(d[v]Infinity){//v0到v有边相连，修改p[v][v0]的值为1p[v][v0]=1;p[v][v]=1;//各顶点自己到自己要连通}}//ford[v0]=0;//自己到自己的权值设为0final[v0]=1;//v0的访问标志设为1，v属于s集for(i=1;ic.vexnum;i++){//对其余c.vexnum-1个顶点w，依次求v到w的最短路径10min=Infinity;for(w=0;wc.vexnum;w++)//在未被访问的顶点中，查找与v0最近的顶点vif(!final[w