数据结构课程设计报告撰写要求

1、精选优质文档-倾情为你奉上数据结构课程设计报告撰写要求（一）纸张与页面设置 1采用国际标准A4型打印纸或复印纸，纵向打印。 2页边距：上3.5cm、下2.5cm、左边距3.0cm，右边距2.5cm。3页眉2.5cm、页脚1.8cm、对称页边距。（二）页眉“沈阳航空工业学院课程设计报告”，五号楷体，居中。（三）页脚 标页码，五号宋体，居中。（四）题目、摘要、关键词 题目：小二号黑体，居中。（五）标题 一级标题，三号粗宋体，居中，用“1 ”、“2 ”、“3 ”等表示序号。 二级标题，小三号粗宋体，左对齐，用“1.1”、“1.2”、“1.3”等表示序号。 三级标题，四号粗宋体，左对齐，用“1.1.1

2、”、“1.1.2”、“1.1.3”等表示序号。（六）正文小四号宋体，两端对齐，1.5倍行距。（七）图、表 1表头包括：表标识及表名两部分，表头在表上，居中，用五号宋体字。2图头包括：图标识及图名两部分，图头在图下，居中，用五号宋体字。 （八）参考文献 格式：序号作者.译者.书名.版本.出版社，出版时间 （九）报告封页及模版见下页 沈阳航空工业学院课 程 设 计 报 告课程设计名称：数据结构课程设计课程设计题目：PRIM算法求最小生成树院（系）：计算机学院专 业：计算机科学与技术班 级： 班学 号： 0姓 名：指导教师： 郑志勇专心-专注-专业目 录 1 需求分析1.1 题目内容及要求以合适方便

3、的方式输入一个带权值的无向图，采用合适的存储结构存储该无向图。然后根据PRIM算法求该无向图的最小生成树并输出。要求：1.输入无向图的方法尽量简单方便 2.要能够形象方便地观察无向图的图形结构 3.要能够形象地演示PRIM算法求最小生成树的过程1.2 题目分析刚拿到题目，乍看一下题目很简短，貌似很简单，但是细看之后就发现了很多隐藏在简短语句后的更深一层次的要求。首先是“以合适方便的方式输入”，短短十个字就向你提出了两方面要求：首先是“输入”，即代表你最好可以得到一种通用的算法让你对一定范围内的数据进行运算后从而得到正确的结果；“合适方便”即提示你要从输入方便且有利于运算的输入数据的方法；采用合

4、适的存储结构必然是本次课设当之无愧的重点，亦是此题目的第三方面要求；最后就是用PRIM算法求无向图的最小生成树。PRIM算法在理解与实现方面不是很困难，但要求能够形象的演示该算法就不是那么简单了。无论从算法角度，还是从输入方便、存储安全角度，数组都是此次课设的不二选择，即采用邻接矩阵的存储方式来存储无向带权图。虽然邻接表的动态存储可以令该算法使用更大规模的数据并在一定范围内比数组更加节省空间并有更高的效率，但此次课设另一个重点就是演示算法而非真正的应用于实际问题，所以只需要较少的数据量来完成PRIM算法的演示即可。故数组的便于操作及更加稳定、方便的优势便凸显出来。在画图这个问题上，我曾一度找错

5、了方向。刚拿到题目时，我只是望文生义的认为我需要演示的是最小生成树一步一步的演示过程，这让我一度选择VC 6.0中的MFC来演示过程。但后来，当我因为MFC当量调用WINDOWS的程序并有较多的头文件而焦头烂额的时候，重读课设要求的时候我才发现，过于注重细枝末节的我竟没有抓住此题目真正要求！“模拟PRIM算法最小生成树的过程”即是让你显示PRIM算法在更接近计算机可以理解的方式上显示其具体过程。Turbo C 的超强的图像处理让我明白，它就是我这次课设的系统环境了。2 系统设计2.1数据结构设计对于无向图的任何操作，无疑都必须依赖于数据的存储结构。这里的存储结构不仅仅指的是数据在计算机中的物理

6、内存，更多的是抽象程度更高的抽象数据结构。图的存储结构主要有两种:邻接矩阵和邻接表。邻接表以一个一维数组作表头节点存储图的顶点，然后利用表头引出所有以该点为箭尾的邻接边的信息；而邻接矩阵则是单独建立一个一维数组来存储顶点的信息，并以顶点的个数来建立一个相应的N阶对称矩阵，以二维数组存储单元来存储相应边的权值。由于PRIM算法需要多次修改closeedge 中的adjvex和lowcost 值，且此次数据规模较小，只需达到演示部分数据即可，所以统一采用数组的存储结构，即亦采用邻接矩阵的存储结构来存储无向带权图更利于实现及操作。邻接矩阵的抽象数据结构定义：#define INFINITY INT_

7、MAX /最大值#define MAX_ERTEX_NUM 20 /最大顶点数typedef enum DG , DN , UDG , UDN GraphKind;/ 有向图，有向网，无向网，无向图typedef struct Arc Cell VRType adj ; / VRType 是顶点关系的类型。对无权图，用1和0表示相邻否；对/带权图则为权值类型 InfoType * info; /该弧相关信息的指针ArcCell , AdjMatrix MAX_VERTEX_NUMMAX_VERTEX_NUM；Typedef struct VertexType vexs MAX_VERTEX_N

8、UM ; /顶点向量 AdjMatrix arcs ; / 邻接矩阵int vexnum , arcnum ; /图的当前顶点数和弧数GraphKind kind ; / 图的种类标志Mgraph ;2.2函数设计本系统所使用的函数见表2.2.1表2.2.1 本系统所使用的函数函数名称函数原型功能描述main()int main(void)系统调用主函数Huiru()Void Huitu ()绘制无向图GraphicVer()void GraphicVer(Graph *G)输出邻接矩阵prim()void prim(Graph *G)PRIM算法演示本系统所调用函数调用的关系见图2.2.2图

9、2.2.2 本系统的函数调用关系2.2 关键流程流程图能直观和系统地把主函数的各个执行步骤和调用的子函数以及调用先后表示出来，子函数中也有调用其他子函数的情况，画出子函数的流程图能清楚地看出子函数中各步语句的执行，下面是关于主函数流程和关键的子函数流程图的直观表示。2.2.1系统流程图2.2.1 系统流程2.2.2 PRIM 函数流程表2.2.2 PRIM 函数流程2.2.3 Huitu函数流程表2.2.3 Huitu函数流程2.2.4 GraphicVer函数输出邻接矩阵图2.2.4 GraphicVer函数输出邻接矩阵3 调试分析3.1 调试初期由于编写的程序具有模块化的特性，且VC 6.

10、0 的调试显然由于TC及个人对VC的熟练程度远优于TC等方面，我选择先在VC 6.0环境下完成除图形化演示算法过程函数的其他过程。由于数据结构选择的较合理，且对PRIM算法理解的较为深刻，所以在此环境下的调试并没有太多困难，只是简单的笔误。添加了画图函数后，我就不得不使用TC编程环境。本人使用的是vista 系统，刚运行TC就发现提示：该操作系统不支持16 bit MS-DOS 系统。上网查看帮助，安装了DOSBOX软件虚拟出DOS系统运行，才开始之后的调试。3.2调试中期由于Turbo C 2.0 不支持鼠标，更没有剪切、粘贴等常用快捷的操作，且本人对计算机图形学、TC的图形函数了解甚少，本

11、人电脑更是不兼容TC全屏模式，所以这段时期成为最让本人备受煎熬的时期。首先，由于TC 操作复杂，更因为本人变成习惯不好，导致经常一运行就死机还没保存过的代码就又“恢复出厂化”，让所见之人无不扼腕惋惜，本人亦是痛心疾首，苦不堪言。编译过程出现过的错误有把自定义函数的名字与TC 图形化函数其中一个的关键字相同，TC显示“该函数定义了多重特性”或“该函数数值过多”等类似提示的错误图3.2.1 初始化错误将自定义的initgraph函数重新命名为void huitu( ),即可排除此错误。再次编译，又发现指针错误：图3.2.2 指针错误Outtextxy(int x ,int y ,*p)，即要求最后

12、一项为指向一字符串的指针。数组就是指针，如果这里出错，那只应该是我定义的lowcose 存储的数不是字符串。所以我曾试图用strcpy()将数组内数据一一进行传拷贝到一指针，然后再调用outtextxy（）。但是结果依然错误！后来，在同学的帮助下，我终于弄明白是因为我数组内存储的是整数型数据，必然无法通过strcpy( )转换成指针。后来，我改用vsprintf(tmp,"%d",&lowcostvex-i)，即现将整型转化为字符串，此错误即可排除。 3.3 调试后期图3.3 连接错误这是经过多次修改后，最后一个编译错误。该名定义是你所使用的视频显示模式，影响的是图

13、形化后的屏幕像素及可支持的最大色彩。经试验，此程序在另一台XP电脑上可编译成功，故本人认为是由于VISTA的兼容性导致TC无法调用该定义，即使使用虚拟机也无法排除。考虑到此语句对输出结果影响不大，故将此语句删除，即使得TC自动获取其他可用的视频模式。编译成功！4 测试及运行结果4.1 欢迎界面运行程序，首先进入用户的欢迎界面。模拟界面向导IRIS采用互动式的方法提示用户进入PRIM算法演示界面。首先IRIS会先询问用户是否愿意看PRIM算法演示，若此时用户选择“y”，用户即可顺利进入模拟PRIM 的程序（见图4.1.1）；图4.1.1 用户欢迎界面及正常进入算法演示界面否则,向导友情提示可以直

14、接退出程序，其效果图见图4.1.2。图4.1.2 用户选择退出算法演示的界面4.2获取输入，绘制无向图创建无向图，动态显示在屏幕上，并输出其存储结构，即无向网的邻接矩阵。首先按照提示，收入先要创建顶点的坐标及其名。其效果图见图4.2.1图4.2.2 动态建立无向图输入时需要注意的是，由于该程序时默认添加一点则连接相应的直线，所以在一点多线的时候，像例子中的A点，就要重新返回A后再连接其他点。具体操作见图4.2.3。图4.2.3 建立一点多线时的具体操作方法图4.2.4 创建无线图的最终效果图4.3 输出邻接矩阵向导可以自动进入输出邻接矩阵的界面图4.3.1 邻接矩阵的开始界面由于“”无法被TC

15、识别，故该位置改用可以识别的其他特殊符号“-”。图4.3.2 输入边信息 图4.3.3 邻接矩阵的输出4.4. 演示PRIM算法生成最小生成树向导先输出对该算法的介绍，然后提示用户开始算法的演示。图4.4.1 PRIM算法的介绍用户确认后开始算法的每个步骤。其生成过程见图图4.4.2 第一次查找后lowcost和closest 数组值的变化图4.4.3 第二次查找后lowcost和closest 数组值的变化图4.4.3 第三次查找后lowcost和closest 数组值的变化图4.4.4 相关算法4.5 用户退出演示完成后，向导可提示自动退出。图4.5 退出界面参考文献1 严蔚敏，吴伟民.数

16、据结构(C语言版)M.北京:清华大学出版社,20062 吕国英.算法设计与分析M.北京:清华大学出版社,20063 李兰友.Turbo C 实用图形程序设计M.北京.科技翻译出版公司，19944 侯风巍.数据结构要点精析C语言版M.北京：北京航空航天大学出版社，20075亦欧.TURBO C+ 运行库函数源程序与参考大全M.北京.学院出版社，19936谢明与.Borland C+/Turbo C+ 编程实例剖析M.北京.科学出版社.19937卫宁.Turbo C+ for DOS 入门.M. 北京.学院出版社，1994附 录（关键部分程序清单）#include<graphics.h>

17、;#include <stdio.h>#include <string.h>#include <stdlib.h>#include <conio.h>#define MaxVertexNum 50#define INF 32767typedef struct Graphicchar vexsMaxVertexNum;int edgesMaxVertexNumMaxVertexNum;int v,e;Graph;char tmp10;void Huitu() /*无向图的图形生成*/ char buffer100;int graphdriver =

18、 DETECT, graphmode;int i,xbefore,ybefore;int x1,y1; char c;/*registerbgidriver(EGAVGA_driver);*/ /*使用EGAVGA显卡模式，分辨率为640*480*/initgraph(&graphdriver, &graphmode, ""); /*图形初始化*/cleardevice(); /*清屏*/printf("input pot (300<x<610,y<400):ninput 0 to halt!n");setfillsty

19、le(1,WHITE);setcolor(WHITE);scanf("%d,%d,%s",&xbefore,&ybefore,buffer);circle(xbefore,ybefore,15);floodfill(xbefore,ybefore,WHITE);setcolor(BLUE);outtextxy(xbefore, ybefore, buffer);setcolor(WHITE);moveto(xbefore,ybefore);while(1)scanf("%d,%d,%s",&x1,&y1,buffer);i

20、f(x1=0) break;circle(x1,y1,15);floodfill(x1,y1,WHITE);setcolor(BLUE);outtextxy(x1, y1, buffer);setcolor(WHITE);line(xbefore,ybefore,x1,y1);xbefore=x1;ybefore=y1;system("pause");void GraphicVer(Graph *G) /*build and output the adjMatrix*/int i,j,k,weight;int v1,v2; printf("input vertex

21、's and edges's number :"); scanf("%d,%d",&G->v,&G->e); for(i=1;i<=G->v;i+) for(j=1;j<=G->v;j+) if(i=j) G->edgesij=0; else G->edgesij=INF; /*初始化矩阵，全部元素设为无穷大 */ for(k=1;k<=G->e;k+) printf("input %dth edge :",k); scanf("%d,%d,%

22、d",&v1,&v2,&weight); G->edgesv1v2=G->edgesv2v1=weight; for(i=1;i<=G->v;i+) printf("n"); for(j=1;j<=G->v;j+) printf(G->edgesij=INF)?"t":"%dt",G->edgesij); printf("n"); system("pause");/*prim 算法生成最小生成树*/void pri

23、m(Graph *G)int lowcostMaxVertexNum,closestMaxVertexNum; int i,j,k,min; for(i=2;i<=G->v;i+) /*n个顶点，n-1条边 */ lowcosti=G->edges1i; /*初始化*/ closesti=1; /*顶点未加入到最小生成树中 */ lowcost1=0; /*标志顶点1加入U集合*/ for(i=2;i<=G->v;i+) /*形成n-1条边的生成树 */min=INF; k=0; for(j=2;j<=G->v;j+) /*寻找满足边的一个顶点在U,另

24、一个顶点在V的最小边 */if(lowcostj<min)&&(lowcostj!=0)min=lowcostj; k=j; printf("(%d,%d)%2dt",closestk,k,min); /*输出最小生成树的边及对应的权值*/ lowcostk=0; /*顶点k加入U*/ for(j=2;j<=G->v;j+) /*修改由顶点k到其他顶点边的权值*/if(G->edgeskj<lowcostj)lowcostj=G->edgeskj; closestj=k; printf("n");voi

25、d drawwapicture(int lowcost,int closest,int vex) int i=0,x=0,datax=0;setviewport(150,140,630,310,1);cleardevice();setcolor(GREEN);rectangle(10,10,470,160); line(10,60,470,60);line(10,110,470,110);for(i=0;i<vex;i+)x=470-40*i;datax=470-20*i;line(x,10,x,160);if(vex-i)!=0)outtextxy(datax,35,"(ve

26、x-i)0"); vsprintf(tmp,"%d",&lowcostvex-i); outtextxy(datax,85,tmp); vsprintf(tmp,"%d",&closestvex-i);outtextxy(datax,135,tmp);elseouttextxy(datax,35,"i0");outtextxy(datax,85,"lowcost0");outtextxy(datax,135,"closest0");getche();closegraph

27、();/*prim 算法生成最小生成树*/void primyanshi(Graph *G) void drawwapicture(int *p,int*q,int k);int lowcostMaxVertexNum,closestMaxVertexNum; int i,j,k,min;cleardevice(); for(i=2;i<=G->v;i+) /*n个顶点，n-1条边 */ lowcosti=G->edges1i; /*初始化*/ closesti=1; /*顶点未加入到最小生成树中 */drawwapicture(lowcost,closest,G->v

28、); lowcost1=0; /*标志顶点1加入U集合*/ drawwapicture(lowcost,closest,G->v); for(i=2;i<=G->v;i+) /*形成n-1条边的生成树 */ min=INF; k=0; for(j=2;j<=G->v;j+) /*寻找满足边的一个顶点在U,另一个顶点在V的最小边 */if(lowcostj<min)&&(lowcostj!=0)min=lowcostj; k=j; drawwapicture(lowcost,closest,G->v); cprintf("(%d

29、,%d)%2dt",closestk,k,min); /*输出最小生成树的边及对应的权值*/ lowcostk=0; /*顶点k加入U*/drawwapicture(lowcost,closest,G->v); for(j=2;j<=G->v;j+) /*修改由顶点k到其他顶点边的权值*/if(G->edgeskj<lowcostj)lowcostj=G->edgeskj; closestj=k; drawwapicture(lowcost,closest,G->v); printf("n");int main()Graph *G=NULL;int flag=1; printf("/*/n");printf("/*Welcome to the world of IRIS*/n");printf("/*0*/n"); while(flag!=0) printf("1:Build a Undigraph Net an