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

数据结构课程设计报告撰写要求数据结构课程设计报告撰写要求 一 纸张与页面设置纸张与页面设置 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 1 1 2 1 1 3 等表示序号 六 正文正文 小四号宋体 两端对齐 1 5 倍行距 七 图 表图 表 1 表头包括 表标识及表名两部分 表头在表上 居中 用五号宋体字 2 图头包括 图标识及图名两部分 图头在图下 居中 用五号宋体字 八 参考文献 八 参考文献 格式 序号 作者 译者 书名 版本 出版社 出版时间 九 报告封页及模版见下页 沈阳航空工业学院 课课 程程 设设 计计 报报 告告 课程设计名称 数据结构课程设计数据结构课程设计 课程设计题目 PRIMPRIM 算法求最小生成树算法求最小生成树 院 系 计算机学院 专 业 计算机科学与技术 班 级 7401102班 学 号 200704011030 姓 名 指导教师 郑志勇 目目 录录 沈阳航空工业学院沈阳航空工业学院 2 1 1 需求分析需求分析 1 1 1 题目内容及要求 1 1 2 题目分析 1 2 系统设计系统设计 3 2 1 数据结构设计 3 2 2 函数设计 4 2 2 1 系统流程 5 Huitu GraphicVer prim main 结束 图 2 2 1 系统流程 5 2 2 2 PRIM 函数流程 5 2 2 3 Huitu 函数流程 6 2 2 4 GraphicVer 函数输出邻接矩阵 6 3 调试分析调试分析 7 3 1 调试初期 7 3 2 调试中期 7 3 3 调试后期 9 4 测试及运行结果测试及运行结果 10 4 1 欢迎界面 10 4 2 获取输入 绘制无向图 10 4 3 输出邻接矩阵 13 4 4 演示 PRIM 算法生成最小生成树 13 4 5 用户退出 14 参考文献参考文献 15 附附 录 关键部分程序清单 录 关键部分程序清单 16 1 1 需求分析需求分析 1 11 1 题目内容及要求题目内容及要求 以合适方便的方式输入一个带权值的无向图 采用合适的存储结构存储该无 向图 然后根据 PRIM 算法求该无向图的最小生成树并输出 要求 1 输入无向图的方法尽量简单方便 2 要能够形象方便地观察无向图的图形结构 3 要能够形象地演示 PRIM 算法求最小生成树的过程 1 21 2 题目分析题目分析 刚拿到题目 乍看一下题目很简短 貌似很简单 但是细看之后就发现了很 多隐藏在简短语句后的更深一层次的要求 首先是 以合适方便的方式输入 短短十个字就向你提出了两方面要求 首先是 输入 即代表你最好可以得到一种通用的算法让你对一定范围内的数 据进行运算后从而得到正确的结果 合适方便 即提示你要从输入方便且有利 于运算的输入数据的方法 采用合适的存储结构必然是本次课设当之无愧的重点 亦是此题目的第三方面要求 最后就是用 PRIM 算法求无向图的最小生成树 PRIM 算法在理解与实现方面不是很困难 但要求能够形象的演示该算法就不是那 么简单了 无论从算法角度 还是从输入方便 存储安全角度 数组都是此次课设的不 二选择 即采用邻接矩阵的存储方式来存储无向带权图 虽然邻接表的动态存储 可以令该算法使用更大规模的数据并在一定范围内比数组更加节省空间并有更高 的效率 但此次课设另一个重点就是演示算法而非真正的应用于实际问题 所以 只需要较少的数据量来完成 PRIM 算法的演示即可 故数组的便于操作及更加稳 定 方便的优势便凸显出来 在画图这个问题上 我曾一度找错了方向 刚拿到题目时 我只是望文生义 的认为我需要演示的是最小生成树一步一步的演示过程 这让我一度选择 VC 6 0 中的 MFC 来演示过程 但后来 当我因为 MFC 当量调用 WINDOWS 的程序并有较多 的头文件而焦头烂额的时候 重读课设要求的时候我才发现 过于注重细枝末节 的我竟没有抓住此题目真正要求 模拟 PRIM 算法最小生成树的过程 即是让 你显示 PRIM 算法在更接近计算机可以理解的方式上显示其具体过程 Turbo C 的超强的图像处理让我明白 它就是我这次课设的系统环境了 2 系统设计 2 12 1 数据结构设计数据结构设计 对于无向图的任何操作 无疑都必须依赖于数据的存储结构 这里的存储结 构不仅仅指的是数据在计算机中的物理内存 更多的是抽象程度更高的抽象数据 结构 图的存储结构主要有两种 邻接矩阵和邻接表 邻接表以一个一维数组作表 头节点存储图的顶点 然后利用表头引出所有以该点为箭尾的邻接边的信息 而 邻接矩阵则是单独建立一个一维数组来存储顶点的信息 并以顶点的个数来建立 一个相应的 N 阶对称矩阵 以二维数组存储单元来存储相应边的权值 由于 PRIM 算法需要多次修改 closeedge 中的 adjvex 和 lowcost 值 且 此次数据规模较小 只需达到演示部分数据即可 所以统一采用数组的存储结构 即亦采用邻接矩阵的存储结构来存储无向带权图更利于实现及操作 邻接矩阵的抽象数据结构定义 define INFINITY INT 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 NUM MAX VERTEX NUM Typedef struct VertexType vexs MAX VERTEX NUM 顶点向量 AdjMatrix arcs 邻接矩阵 int vexnum arcnum 图的当前顶点数和弧数 GraphKind kind 图的种类标志 Mgraph 2 22 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 Huitu GraphicVer prim main 结束 图 2 2 2 本系统的函数调用关系 2 2关键流程 流程图能直观和系统地把主函数的各个执行步骤和调用的子函数以及调用先 后表示出来 子函数中也有调用其他子函数的情况 画出子函数的流程图能清楚 地看出子函数中各步语句的执行 下面是关于主函数流程和关键的子函数流程图 的直观表示 2 2 12 2 1 系统流程系统流程 Huitu GraphicVer prim main 结束 图图 2 2 12 2 1 系统流程系统流程 2 2 2 PRIM 函数流程函数流程 声明 lowcost closes t 数组 初始化lowcost 并标记lowcost 1 在lowcost 中寻 找最小值并记录其 对应点 标记上一顶点 开始 更新lowcost 结束 输出两数组值 输出两数组值 表 2 2 2 PRIM 函数流程 2 2 32 2 3 HuituHuitu 函数流程函数流程 开始 图形初始化 定义变量 获取用户输入 坐标 顶点 在相应位置绘制圆 并涂上颜色 在圆 心处添加顶点 获取用户输入 坐标 顶点 判断用户输 入是否为0 退出 表 2 2 3 Huitu 函数流程 2 2 42 2 4 GraphicVerGraphicVer 函数输出邻接矩阵函数输出邻接矩阵 清屏 开始 输入顶点 数 边数 按顶点数初 始化二维数 组 按边数重复获取边权值 输入邻接矩阵内 输出矩阵内 的权值或无 穷大 结束 图 2 2 4 GraphicVer 函数输出邻接矩阵 3 调试分析 3 13 1 调试初期调试初期 由于编写的程序具有模块化的特性 且 VC 6 0 的调试显然由于 TC 及个人对 VC 的熟练程度远优于 TC 等方面 我选择先在 VC 6 0 环境下完成除图形化演示算 法过程函数的其他过程 由于数据结构选择的较合理 且对 PRIM 算法理解的较为深刻 所以在此环 境下的调试并没有太多困难 只是简单的笔误 添加了画图函数后 我就不得不使用 TC 编程环境 本人使用的是 vista 系统 刚运行 TC 就发现提示 该操作系统不支持 16 bit MS DOS 系统 上网查看帮助 安装了 DOSBOX 软件虚拟出 DOS 系统运行 才 开始之后的调试 3 23 2 调试中期调试中期 由于 Turbo C 2 0 不支持鼠标 更没有剪切 粘贴等常用快捷的操作 且本 人对计算机图形学 TC 的图形函数了解甚少 本人电脑更是不兼容 TC 全屏模式 所以这段时期成为最让本人备受煎熬的时期 首先 由于 TC 操作复杂 更因为本人变成习惯不好 导致经常一运行就死 机还没保存过的代码就又 恢复出厂化 让所见之人无不扼腕惋惜 本人亦是 痛心疾首 苦不堪言 编译过程出现过的错误有把自定义函数的名字与 TC 图形化函数其中一个的 关键字相同 TC 显示 该函数定义了多重特性 或 该函数数值过多 等类似提 示的错误 图 3 2 1 初始化错误 将自定义的 initgraph 函数重新命名为 void huitu 即可排除此错误 再次编译 又发现指针错误 图 3 2 2 指针错误 Outtextxy int x int y p 即要求最后一项为指向一字符串的指针 数组就是指针 如果这里出错 那只应该是我定义的 lowcose 存储的数不是字 符串 所以我曾试图用 strcpy 将数组内数据一一进行传拷贝到一指针 然后再 调用 outtextxy 但是结果依然错误 后来 在同学的帮助下 我终于弄明白是因为我数组内存储的是整数型数据 必然无法通过 strcpy 转换成指针 后来 我改用 vsprintf tmp d vexs MaxVertexNum intint edges MaxVertexNum MaxVertexNum edges MaxVertexNum MaxVertexNum intint v e v e Graph Graph charchar tmp 10 tmp 10 voidvoid Huitu Huitu 无向图的图形生成无向图的图形生成 charchar buffer 100 buffer 100 intint graphdrivergraphdriver DETECT DETECT graphmode graphmode intint i xbefore ybefore i xbefore ybefore intint x1 y1 x1 y1 charchar c c registerbgidriver EGAVGA driver registerbgidriver EGAVGA driver 使用使用 EGA VGAEGA VGA 显卡模式 分辨率为显卡模式 分辨率为 640 480 640 480 initgraph 图形初始化图形初始化 cleardevice cleardevice 清屏清屏 printf inputprintf input potpot 300 x 610 y 400 ninput 300 x 610 yv scanf d d for i 1 iv i for i 1 iv i for j 1 jv j for j 1 jv j if i j if i j G edges i j 0 G edges i j 0 elseelse G edges i j INF G edges i j INF 初始化矩阵 全部元素设为无穷大初始化矩阵 全部元素设为无穷大 for k 1 ke k for k 1 ke k printf input printf input dth dth edgeedge k k scanf d d d scanf d d d G edges v1 v2 G edges v2 v1 weight G edges v1 v2 G edges v2 v1 weight for i 1 iv i for i 1 iv i printf n printf n for j 1 jv j for j 1 jv j printf G edges i j INF t d t G edges i j printf G edges i j INF t d t G edges i j printf n printf n system pause system pause prim prim 算法生成最小生成树算法生成最小生成树 voidvoid prim Graphprim Graph G G intint lowcost MaxVertexNum closest MaxVertexNum lowcost MaxVertexNum closest MaxVertexNum intint i j k min i j k min for i 2 iv i for i 2 iv i n n 个顶点 个顶点 n 1n 1 条边条边 lowcost i G edges 1 i lowcost i G edges 1 i 初始化初始化 closest i 1 closest i 1 顶点未加入到最小生成树中顶点未加入到最小生成树中 lowcost 1 0 lowcost 1 0 标志顶点标志顶点 1 1 加入加入 U U 集合集合 for i 2 iv i for i 2 iv i 形成形成 n 1n 1 条边的生成树条边的生成树 min INF min INF k 0 k 0 for j 2 jv j for j 2 jv j 寻找满足边的一个顶点在寻找满足边的一个顶点在 U U 另另 一个顶点在一个顶点在 V V 的最小边的最小边 if lowcost j min min lowcost j k j k j printf d d 2d t closest k k min printf d d 2d t closest k k min 输出最小生成树输出最小生成树 的边及对应的权值的边及对应的权值 lowcost k 0 lowcost k 0 顶点顶点 k k 加入加入 U U for j 2 jv j for j 2 jv j 修改由顶点修改由顶点 k k 到其他顶点边的权值到其他顶点边的权值 if G edges k j edges k j edges k j lowcost j G edges k j closest j k closest j k printf n printf n voidvoid drawwapicture intdrawwapicture int lowcost intlowcost int closest intclosest int vex vex intint i 0 x 0 datax 0 i 0 x 0 datax 0 setviewport 150 140 630 310 1 setviewport 150 140 630 310 1 cleardevice cleardevice setcolor GREEN setcolor GREEN rectangle 10 10 470 160 rectangle 10 10 470 160 line 10 60 470 60 line 10 60 470 60 line 10 110 470 110 line 10 110 470 110 for i 0 i vex i for i 0 i vex i x 470 40 i datax 470 20 i x 470 40 i datax 470 20 i line x 10 x 160 line x 10 x 160 if vex i 0 if vex i 0 outtextxy datax 35 vex i 0 outtextxy datax 35 vex i 0 vsprintf tmp d vsprintf tmp d outtextxy datax 85 tmp outtextxy datax 85 tmp vsprintf tmp d vsprintf tmp d outtextxy datax 135 tmp outtextxy datax 135 tmp elseelse outtextxy datax 35 i 0 outtextxy datax 35 i 0 outtextxy datax 85 lowcost 0 outtextxy datax 85 lowcost 0 outtextxy datax 135 closest 0 outtextxy datax 135 closest 0 getche getche closegraph closegraph prim prim 算法生成最小生成树算法生成最小生成树 voidvoid primyanshi Graphprimyanshi Graph G G voidvoid drawwapicture intdrawwapicture int p int q int p int q int k k intint lowcost MaxVertexNum closest MaxVertexNum lowcost MaxVertexNum closest MaxVertexNum intint i j k min i j k min cleardevice cleardevice for i 2 iv i for i 2 iv i n n 个顶点 个顶点 n 1n 1 条边条边 lowcost i G edges 1 i lowcost i G edges 1 i 初始化初始化 closest i 1 closest i 1 顶点未加入到最小生成树中顶点未加入到最小生成树中 drawwapicture lowcost closest G v drawwapicture lowcost closest G v lowcost 1 0 lowcost 1 0 标志顶点标志顶点 1 1 加入加入 U U 集合集合 drawwapicture lowcost closest G v drawwapicture lowcost closest G v for i 2 iv i for i 2 iv i 形成形成 n 1n 1 条边的生成树条边的生成树 min INF min INF k 0 k 0 for j 2 jv j for j 2 jv j 寻找满足边的一个顶点在寻找满足边的一个顶点在 U U 另另 一个顶点在一个顶点在 V V 的最小边的最小边 if lowcost j min drawwapicture lowcost closest G v cprintf d d 2d t closest k k min cprintf d d 2d t closest k k min 输出最小生成输出最小生成 树的边及对应的权值树的边及对应的权值 lowcost k 0 lowcost k 0 顶点顶点 k k 加入加入 U U drawwapicture lowcost closest G v drawwapicture lowcost closest G v for j 2 jv j for j 2 jv j 修改由顶点修改由顶点 k k 到其他顶点边的权值到其他顶点边的权值 if G edges k j edges k j edges k j lowcost j G edges k j closest j k closest j k drawwapicture lowcost closest G v drawwapicture lowcost closest G v printf n printf n intint main main GraphGraph G NULL G NULL intint flag 1 flag 1 printf printf n n printf Welcomeprintf Welcome toto thethe worldworld ofof IRIS n IRIS n printf 200printf 200 704011030 n 704011030 n while flag 0 while flag 0 printf 1 Buildprintf 1 Build a a UndigraphUndigraph NetNet andand outputoutput thethe adjMatrix n adjMatrix n printf 2 Outputprintf 2 Output thethe Mini tree n Mini tree n printf 3 Displayprintf 3 Display thethe