《数据结构课程设计报告中国行政区域图染色与信息查询（可编辑） .doc》由会员分享，可在线阅读，更多相关《数据结构课程设计报告中国行政区域图染色与信息查询（可编辑） .doc（33页珍藏版）》请在三一办公上搜索。
1、 课 程 设 计 报 告题目： 中国行政区域图染色与信息查询 课程名称： 数据结构课程设计 专业班级：计算机科学与技术 班学 号： 姓 名： 指导教师： 报告日期： 2012年10月10日 计算机科学与技术学院目 录1 绪言22 系统设计方案的研究2.1 系统的控制特点与性能要求32.2 系统设计方案选择及分析33 系统的设计及实现3.1 染色模块的设计63.2 管道铺设模块设计83.3 省份信息查询模块设计93.4 其他模块设计93.5 其他设计94 系统结果分析125 总结18参考文献19附录201 绪言数据结构是计算机科学技术与信息安全等专业的一门重要专业基础课，牢固掌握数据结构的基础知
2、识，熟练地运用数据结构的思想与技术方法解决实际应用问题是是本课程学习的基本任务与目标。而课程设计是重要组成部分MFC是微软封装了的API是面向对象程序设计与Application framework的完美结合，将传统的API进行了分类封装，并且创建了程序的一般框架。Visual C+6.0由Microsoft开发它不仅是一个C+?编译器，而且是一个基于Windows操作系统的可视化集成开发环境。Visual C+6.0由许多组件组成，包括编辑器、调试器以及程序向导AppWizard、类向导Class Wizard等开发工具。图2.1 窗口结构设计在主窗口中进行地图的显示以及进行与图形相关的操作
3、，信息查询显示则在新窗口中进行，这样安排使得不同的操作各自独立进行，防止了相互间的干扰，同时也简化了单个函数的长度，使得程序条理更加清晰，也方便用户的使用。程序采用模块化设计方案，即先设定好主程序，子程序，子过程框架，并定义好各个框架之间的输入，输出链接关系，逐步求精得到以功能块为单位的算法描述。模块化设计具有降低程序复杂度，使程序设计、调试和维护等操作简单化的优点。在主窗体中设有5个功能按钮，分别对应程序5个功能。按钮事件分别对应窗口类中的5个成员函数，关系如图2.2所示。图2.2 主窗口类中功能实现函数除了窗口类的成员函数，我还自定义了一些辅助功能函数，这些函数在新建的头文件my_h.h中
4、进行声明。辅助功能函数有：Status InitQueue LinkQueue &Q ; /初始化队列Status Enqueue LinkQueue &Q,CPoint &e ; /入队列CPoint Dequeue LinkQueue &Q,CPoint &e ; /出队列BOOL QisEmpty LinkQueue &Q ; /判断队列是Q否为空BOOL InitRelation int v32 ; /载入邻接矩阵到int vvoid SetColor int lin32,int v ; /对每个省份进行颜色分配void InitPoint CPoint p ; /初始化各省份坐标vo
5、id InitProName CString n ; /在省份查询窗口中对各省份名称初始化void InitProInfo proinfo pro_i ; /载入省份信息到pro_i至此，整个程序框架已经完成了，如图2.3所示。图2.3 模块化程序框架在文件方面，我将邻接矩阵直接存放在linjiejuzhen.txt文件中，初始化时直接将文件中内容读取到二位整形数组中，这样大大简化了读文件操作，同时也免去了邻接矩阵初始化时不必要的操作。与常规的邻接矩阵不同的是，我将邻接矩阵中表示结点相邻的1直接用两结点的权值代替，这使得构建无向网操作得以简化同时也提高了文件的利用率。在另一个文件proinfo
6、.txt中保存着各个省份信息，在读取信息时一次将所有信息读取到一个pro_info结构体数组中，这样便于数据的处理。3 系统设计及实现3.1 染色模块的设计首先在功能函数OnZhuose 中定义一个二维整型数组linjie3232来存放邻接矩阵，由四色问题的证明可知“任何一张地图只用四种颜色就能使具有共同边界的国家着上不同的颜色”。故我们可定义一个整形数组pro_color33来存放对每个省份分配的颜色，颜色用整数表示，1表示洋红色,2表示黄色，3表示青色，4表示绿色。在将邻接矩阵数据载入后，我先将矩阵中的非0值全部改成1，即将二维数组linjie 变成严格意义上的邻接矩阵，再使用SetCol
7、or 函数对数组数据进行分析同时在pro_color 中分配各省份的颜色值。在SetColor 函数中，定义有三个变量area 区域号 ，colornum 染色号 ，k 已着色区域号 。首先将1号区域染1色 即pro_color1 1 ，对当前区域进行判断，如果k区域与当期区域不相邻或相邻而不重色则对下一个区域进行判断。如果相邻且重色则改变colornum的值。流程图如图3.1所示。图3.1 SetColor 流程图对各省颜色分配完后就进行地图染色，在OnZhouse 函数中定义了一个CPoint类型的数组并用进行初始化，在数组中保存着各个省份省会城市在地图中的坐标信息，每个省份的染色就从这个
8、坐标开始。地图染色使用的回溯法。定义一个个队列Q，队列中结点在头文件my_h.h中定义如下：typedef struct QNode CPoint data;struct QNode *next; QNode,*QueuePtr;/定义一个队列typedef struct QueuePtr front;QueuePtr rear; LinkQueue;Q中保存即将染色的点。开始绘色时先将各省初始化的坐标入队，再进行循环。循环开始时定义一个CPoint变量pt，Q进行出队操作，pt保存出队结果。对pt进行判断，如果该点颜色为白色则将该点染色，并依次判断该点的上下左右四个点，如果哪个点颜色为白色则
9、将该点入队。流程图如图3.2所示。图3.2 单个省份染色流程3.2 管道铺设模块设计在OnButton3 函数中，首先进行邻接矩阵的载入以及各省坐标的初始化。管道铺设分为两个步骤：绘出无向网和求出最小生成树。绘制无向网相对简单，只需遍历整个邻接矩阵，对相邻的两个省份的省会坐标之间绘制一条线即可。求最小生成树我采用Prim算法，这也是较为经典的求最小生成树算法。为实现这个算法需附设一个辅助结构数组closedge，结构体在头文件my_h.h中定义如下：typedef struct int adjvex; /最小代价边依附的点int lowcost; /最小代价边的权 CE;还要将无向网中不相邻的
10、两个顶点距离设为无穷大，无穷大为头文件my_h.h中定义的一个宏：#define INFINITY 32768Prim算法类C语言表示如下：void MiniSpanTree_PRIM CE closedge_VERTEX_NUM;k 0;for j 0; j PRO_N; j+ /辅助数组初始化if j ! k closedgej k , linjiekj ;closedgek.lowcost 0; /初始距离为0for i 1; i PRO_N; i+ /选择其余顶点 k minimum closedge /求出T的下一个结点：第k结点MoveTo pro_pointk ;LineTo p
11、ro_pointclosedgek.adjvex ; /绘出生成树的边closedgek.lowcost 0;/第k顶点并入U集for j 0; j PRO_N; j+ if linjiekj ! 0 & linjiekj closedgej.lowcost /新顶点并入U后重新选择最小边closedgej.adjvex k ，linjiekj ; / MiniSpanTree3.3 省份信息查询模块设计省份查询是在一个新弹出的对话框中进行操作，在窗口类InfoDlg的初始化函数中对下拉列表载入各省份条目，用户选择一个条目后点击“确定”按钮显示该省份信息。存放单个省份信息的结构体在头文件my_
12、h.h中的定义如下：typedef struct char shenghui10;/省会 char quhao5;/区号 float renkou;/人口 char weizhi50;/位置 float mianji;/面积 proinfo;在函数OnOK 中首先定义一个CString数组info5来保存每一项的显示内容，一个proinfo结构数组pro_i32保存从文件读入的各省份信息。读取用户选择的省份条目，将该省份的信息格式化写入到info中再将info内容依次显示在对话框中。每次显示前进行清屏操作擦除上次显示的内容。3.4 其他模块设计还原模块的的功能主要是使程序回到最初状态。用户在管
13、道铺设后已将各省份特征坐标点染色，这样染色操作就无法进行，再者用户在染色操作过程中如果出现程序异常或者是将已染色区域擦除，就可以通过还原使程序回到初始状态而重新进行操作。还原函数的实现是将空白地图重新载入窗口，覆盖原先的图像即可。关于模块显示系统信息以及作者信息。点击主窗口中的“关于”按钮即弹出一个对话框，这个对话框是根据MFC自动生成的关于窗口修改而成的。3.5 其他设计为了程序设计的方便以及程序使用中具有良好的操作性，在程序中我还加入了一些其他设计元素。 1 在头文件中定义的宏和typedef声明：#define OK 1/用于函数返回值#define PRO_N 32/地图中需处理省份个
14、数typedef int Status; 2 为了使得邻接关系中省份表示更加直观，我依照矩阵中存储的省份顺序定义了一个枚举类型：enum province beijing,/北京tianjin,/天津hebei,/河北shanxi,/山西neimeng,/内蒙古liaoning,/辽宁jilin,/吉林heilongjiang,/黑龙江shanghai,/上海jiangsu,/江苏zhejiang,/浙江anhui,/安徽jiangxi,/江西shandong,/山东henan,/河南hubei,/湖北hunan,/湖南guangdong,/广东guangxi,/广西hainan,/海南cho
15、ngqing,/重庆sichuan,/四川guizhou,/贵州yunnan,/云南xizang,/西藏shaanxi,/陕西gansu,/甘肃ningxia,/宁夏xinjiang,/新疆qinghai,/青海taiwan/台湾 ;这样一来如果想读取邻接矩阵中某个省份的数据就可以直接将省份名作为数组下标，如判断湖北省与湖南省相邻关系则判断linjiehubeihunan的值。 3 在窗口类CMyDDlg中定义了两个整形成员变量：int is_colored ;/判断染色是否完成int is_tubed ;/判断管道铺设是否完成如果is_colored等于1则表示一次染色完成，反之则表示没进行
16、染色，同理如果is_tubed等于1则表示管道已铺设，反之则表示没有铺设管道。在CMyDDlg类的构造函数中将两个变量均置为0，着色函数开始时先判断is_colored和is_tubed的值，若有一个不为0则表示当前无法染色，程序会提示用户先进行还原操作。着色程序最后将is_colored置为1，管道铺设函数最后将is_tubed置为1。还原函数最后将is_colored和is_tubed都置为0。4 系统结果分析系统运行后结果如图4.1所示。图4.1 系统运行最初界面点击“开始着色”按钮后运行结果如图4.2所示。图4.2 染色进行时染色完成后结果如图4.3所示。图4.3 染色结果再点击“铺设
17、管道”按钮进行管道铺设，如图4.4所示。图4.4 管道铺设结果点击“还原”按钮使程序回到初始状态，如图4.5所示。图4.5 还原结果程序初始化后再进行管道铺设操作，如图4.6所示。图4.6 程序初始化后进行管道铺设点击“省份信息”按钮显示信息查询窗口，如图4.7所示。图4.7 省份信息查询窗口选择省份并点击“确定”按钮显示相应省份信息，如图4.8所示。图4.8 查询省份信息点击“关于”按钮显示系统和作者信息，如图4.9所示。图4.9 关于VC+6.0 中类、资源和源文件的组织如图4.10所示。图4.10 IDE中类、资源和源文件组织由以上结果可以看出该系统可以得到在所给条件下的正确结果，并且完
18、成了系统所要求的功能。在系统运行过程中没有出现死机或者自动关闭的情况。然而在测试过程中我也发现了一些不尽如人意的地方，如当其他窗口覆盖程序窗口后，染色区域和管道铺设结果会被擦除；染色过程中用户只能进行等待，如果鼠标在窗口内点击可能会使得染色停止；在Windows 7操作系统下程序运行变慢，而且窗口大小比例发生了变化，图4.11所示。图4.11 Windows 7环境下程序初始界面5 总结当初选择这个题目感觉这个题目比较有趣，实际在做的过程中才发现有很多东西需要学习。就拿MFC来说，MFC本身十分庞杂，学习起来有一定难度，我就有选择地学习，先学习基本的对系统的设计有用的方面，经过一段时间的自学算
19、是对MFC入门了，但是这只是很表面的东西，如果以后要做功能更复杂的系统需要更加深入地学习。再有平时学习数据结构中的图和图的算法仅仅是停留在概念层面，自己从来没有真正实现过，这次就我自己进行实现需要透过概念将理论转化为实际可行的代码，这其中就有思想的转化，也让我对数据结构基本理论有了更直观的理解。这次的系统设计在正确完成了所要求的功能之外，我认为还有以下优点： 1 界面简洁直观。在程序设计之初我计划使用带有菜单的窗口作为主窗口，但是加入菜单后使得程序复杂度和操作性都增加，而且类较多，使得程序结构变得松散，最后换成对话框编程以上问题得以解决。 2 操作简单。相关操作就简化为几个按钮，用户操作方便了
20、很多。而且用户只是使用鼠标操作，这在一定程度上减少了误操作，提高了程序的健壮性。当然，此次课程设计还有一些不足的地方： 1 显示的问题。当窗口被其他窗口遮盖后会将染色和管道铺设结果擦除，需要还原后重新绘制。 2 数据是单向的。系统只提供了数据的查询显示而没有修改、删除功能，缺乏与用户的交互。在染色颜色设定和管道设定方面也没有给用户提供选择的余地。 3 染色相对较慢。每个省份从一点开始逐点向外染色花费时间较长，这在运行过程中就可以明显体现出来，而且程序没有提供中断染色功能，染色时用户只能等待。 4 由于程序是在Windows XP系统下编译调试的，在Windows 7系统中运行时窗口大小比例以及
21、运行效率上都发生了一点偏差。以上问题是我现有知识不能解决的，在以后学习中我还需要不断学习，努力提高自己编程能力，做出功能更加完善，实用性更强的系统。参考文献1 严蔚敏, 吴伟民. 数据结构. 北京: 清华大学出版社, 1997.2 曹计昌, 卢萍, 李开. C语言程序设计. 北京: 科学出版社, 2008.3 孙鑫. VC+深入详解. 北京: 电子工业出版社, 2006.4 余祥宣, 崔国华, 邹海明. 计算机算法基础 第三版 . 武汉: 华中科技大学出版社, 2006.5 URL: 0.投稿赚钱 附录 部分代码/从文件中载入邻接矩阵BOOL InitRelation int v32 FILE
22、 *fp;int i,j;if fp fopen linjiejuzhen.txt,rt NULL return FALSE; for i 0;i PRO_N;i+ for j 0; j PRO_N; j+ fscanf fp,%dt,&vij ;fscanf fp,n ; fclose fp ;return TRUE; /从文件中载入各省份信息void InitProInfo proinfo pro_i FILE *fp;fp fopen proinfo.txt,rt ;for int i 0; i 32; i+ fscanf fp,%s %s %f %s %fn,pro_ii.shengh
23、ui,pro_ii.quhao,&pro_ii.renkou,pro_ii.weizhi,&pro_ii.mianji ; fclose fp ; /着色函数void CMyDDlg:OnZhuose int linjie3232, pro_color33;/邻接矩阵和各省份所分配的颜色int i,j;CClientDC dc this ;CPoint pro_point32,point4;/各省份标记坐标，point数组保存点的上下左右四点COLORREF m_color, m_color1, ColorBox4;memset pro_color,0,sizeof pro_color ;if
24、 is_tubed 1 | is_colored 1 /判断能否进行染色 MessageBox 请先还原! ;return; InitRelation linjie ;/载入矩阵InitPoint pro_point ;/初始化各省份标记坐标for i 0;i 32;i+ /对矩阵进行变换for j 0; j 32; j+ linjieij linjieij 0 ? 1 : 0;SetColor linjie, pro_color ;/为每个省份分配颜色ColorBox0 RGB 255,0,255 ;/染色所需的四种颜色ColorBox1 RGB 255,255,0 ;ColorBox2 R
25、GB 0,255,255 ;ColorBox3 RGB 0,255,0 ;for i 0; i 32; i+ /地图开始染色 switch pro_colori+1 case 1:m_color ColorBox0;break;case 2:m_color ColorBox1;break;case 3:m_color ColorBox2;break;case 4:m_color ColorBox3;break;default:m_color RGB 0,0,0 ;break; LinkQueue Q;InitQueue Q ;Enqueue Q,pro_pointi ;while !QisEm
26、pty Q CPoint pt;Dequeue Q,pt ;if GetPixel dc,pt.x,pt.y RGB 255,255,255 SetPixel dc,pt.x,pt.y,m_color ;point0.x pt.x+1;point0.y pt.y;point1.x pt.x-1;point1.y pt.y;point2.y pt.y+1;point2.x pt.x;point3.y pt.y-1;point3.x pt.x;for int j 0;j 4;j+ m_color1 GetPixel dc,pointj.x,pointj.y ; if m_color1 RGB 25
27、5,255,255 Enqueue Q,pointj ; is_colored 1;/is_colored设为1表示完成了染色 /为各省份分配颜色void SetColor int lin32, int v int area,colornum,k;v1 1; / 1号区域染1色area 2;colornum 1; / area为区域号，colornum为染色号while colornum 4 & area 32 k 1; / k表示已经着色的区域号while k area & vk*linarea-1k-1! colornum k+;/ 若不相邻，或若相邻且不重色，对下一个区域判断.if k
28、area colornum+; /相邻且重色else varea colornum;area+;colornum 1; /相邻且不重色if colornum 4 area-;colornum varea+1; /管道铺设void CMyDDlg:OnButton3 int linjie3232;/邻接矩阵int k beijing;/铺设从beijing开始int i,j,min;CPoint pro_point32;/各省份的标记坐标CE closedge32;/辅助数组InitRelation linjie ;/载入邻接矩阵InitPoint pro_point ;/初始化省份的标记坐标C
29、ClientDC dc this ;CPen pen1 PS_DASH,1,RGB 0,0,255 , pen2 PS_SOLID,1,RGB 255,0,0 ;/定义两种画笔CPen *pOld dc.SelectObject &pen1 ;CFont font;for i 0; i 32; i+ /绘制无向网 for j 0; j 32; j+ if linjieij ! 0 dc.MoveTo pro_pointi ;dc.LineTo pro_pointj ; dc.SelectObject &pen2 ;for i 0; i 32; i+ /对无向网的邻接关系进行设定for j 0;
30、 j 32; j+ if linjieij 0 linjieij INFINITY;/Prim算法求最小生成树for j 0; j 32; j+ /辅助数组初始化 if j ! k closedgej.adjvex beijing;closedgej.lowcost linjiekj; closedgek.lowcost 0;/第k顶点并入U集for i 1; i 32; i+ /选择其余顶点 min INFINITY;for j 0; j 32; j+ /求出T的下一个结点：第k结点 if closedgej.lowcost ! 0 & closedgej.lowcost min min c
31、losedgej.lowcost;k j; dc.MoveTo pro_pointk ;dc.LineTo pro_pointclosedgek.adjvex ;/绘出生成树的边closedgek.lowcost 0;for j 0; j 32; j+ /新顶点并入U后重新选择最小边 if linjiekj ! 0 & linjiekj closedgej.lowcost closedgej.adjvex k;closedgej.lowcost linjiekj; is_tubed 1;/is_tubed设为1标志已经进行了管道铺设dc.SelectObject pOld ;font.Crea
32、tePointFont 120, 宋体 ;dc.SelectObject font ;dc.TextOut 5,10,蓝色线表示所有可能路线，红色线表示最终路线 ; /初始化一个队列Status InitQueue LinkQueue &Q Q.front QueuePtr malloc sizeof QNode ;if !Q.front exit -1 ;Q.front- next NULL;Q.rear Q.front;return OK; /元素入队Status Enqueue LinkQueue &Q,CPoint &e QNode *p;p QueuePtr malloc sizeo
33、f QNode ;if !p exit -1 ;p- data e;p- next NULL;Q.rear- next p;Q.rear p;return OK; /出队CPoint Dequeue LinkQueue &Q,CPoint &e QNode *p;p Q.front- next;e p- data;Q.front- next p- next;if Q.rear p Q.rear Q.front;free p ;return e; /判断队列是否为空BOOL QisEmpty LinkQueue &Q if Q.front Q.rear return true;else retu
34、rn false; /省份信息显示void InfoDlg:OnOK proinfo pro_iPRO_N;CString info5;info0 省会：;info1 区号：;info2 人口：;info3 地理位置：;info4 面积：;InitProInfo pro_i ;UpdateData ;int index;index CComboBox * GetDlgItem IDC_COMBO1 - GetCurSel ;CClientDC dc this ;CFont font;font.CreatePointFont 120, 宋体 ;dc.SelectObject font ;TEXT
35、METRIC tm;dc.GetTextMetrics &tm ;char renkou20;char mianji20;sprintf renkou,%.1f万人,pro_iindex.renkou ;sprintf mianji,%.2f万平方公里,pro_iindex.mianji ;info0+ pro_iindex.shenghui;info1+ pro_iindex.quhao;info2+ renkou;info3+ pro_iindex.weizhi;info4+ mianji;Invalidate ;UpdateWindow ;/清屏dc.SetBkMode 0 ;/设置笔刷
36、为空for int i 0; i 5; i+ dc.TextOut 30,80+i* tm.tmHeight+2 ,infoi ; /还原函数void CMyDDlg:OnButton4 CClientDC dc this ;CBitmap bitmap;bitmap.LoadBitmap IDB_BITMAP1 ;BITMAP bmp;bitmap.GetBitmap &bmp ;CDC dcCompatible;dcCompatible.CreateCompatibleDC &dc ;dcCompatible.SelectObject &bitmap ;/从新载入空白地图dc.BitBlt
37、 0,1,bmp.bmWidth,bmp.bmHeight,&dcCompatible,0,0,SRCCOPY ;is_colored 0;/is_colored和is_tubed置为0is_tubed 0; 17主程序省份信息查询主窗体信息查询窗口关于窗口地图染色管道铺设CMyDDlgOnZhuose 进行地图染色OnChaxun 省份信息查询OnButton3 管道铺设OnButton4 窗口还原OnAbout 关于主程序染色模块管道铺设模块查询模块窗口还原模块关于模块InitRelation InitPoint SetColor 与Queue相关InitRelation InitPoint OnButton3 InitProInfo 完成开始colornum 4pro_color1 1 area 2colornum 1colornum 4& area 32k areak area &pk*larea-1k-1! colornumk+colornum+k 1parea colournumcolournum 1area+area-colournum parea+1YYYYNNNN开始pro_pointi入队Q为空？Q出队pt是白色？对pt点染色对pt点上下左右四点判断并入队结束YYNN
