数据结构课程设计

计算机科学与技术学院。

课程设计报告。

一、需求分析。

1)设计目的。

数据结构是计算机专业的核心课程，是一门实践性很强的课程。课程设计是加强学生实践能力的一个强有力手段，要求学生掌握数据结构的应用、算法的编写、类c语言的算法转换成c（c++）程序并上机调试的基本方法，还要求学生在完成程序设计的同时能够写出比较规范的设计报告。严格实施课程设计这一环节，对于学生基本程序设计素养的培养和软件工作者工作作风的训练，将起到显著的促进作用。

2)设计内容。

本次数据结构的课程设计有两个题目：

第一题是要设计一个一元多项式的计算器，功能包括（1）输入并建立多项式（一个多项式最多不超过20项），可以从文件中读取相关数据；（2）输出多项式，输出形式可以是图形方式，也可以是文本方式；（3）实现两个多项式相加，并输出和多项式；（4）实现两个多项式相减，并输出差多项式；（5）实现两个多项式相乘，并输出乘积多项式；（6）计算并输出多项式在指定x处的值。

第二题是已知中国地图，请设计地图着色软件，对各省进行着色，要求相邻省所使用的颜色不同，并保证使用的颜色最少。

3)程序已完成。

本次设计基本实现了两题所要求的功能，诸如加减乘、着色。但限于本人的所学的知识和设计时间的限制，还有部分功能未能实现，如当输入格式与程序要求不符时，程序无法纠错；还有程序用的c语言编的，不是用visual ｃ＋编的，所以程序所实现的外观，实不敢恭维，确实是本设计的大败笔。

二、详细设计。

1）程序函数构成。

一元多项式：

数据结构定义：typedef struct elemtype;

/带头结点的线性链表类型。

typedef struct lnode ;

函数：locateelem（**确定位置返回前驱。

orderinsert（**插到相应的位置。

compare（**比较两插入值的指数值。

creatpolyn（**创建多项式。

printpolyn（**打印多项式。

addpolyn（**加法。

subpolyn（**减法。

mulpolyn（**乘法。

valuepolyn（**赋x值。

地图着色。数据结构定义：typedef struct;

函数： locatevex（**点是否在图中。

createfag（**采用邻接矩阵存储。

display（**输出矩阵。

color（**着色函数。

print输出着色。

2)设计思路。

①对于多项式的计算器，即首先要完成多项式的输入输出，然后再完成加减乘、输出x的值。

综上所述，本设计的功能为：

采用orderinsert将结点合并到升序链表的适当位置的思路，对于输入，可用orderinsert插入空链表；对于加法，可以用orderinsert将两个链表循环输入；对于减法，可以先将被减链表取反，然后执行加法；对于乘法，可以内外循环来做加法。

地图着色。如图所示：如果对地图4着色，可选择已涂色的区域，如果与图4相邻（图1、图3），则继续判断与图4相邻的图是否与图4的颜色相同，如果不相同，则可以对相邻图赋色；如果相同，则继续换一种颜色判断，直至试出不相同的颜色赋色。

最后输出图的颜色。

三、调试分析。

略。四、用户手册。

1）对于一元多项式，用户可参照详细的菜单进行操作。

另外，在程序文件夹内，有两个txt文件pol1和pol2，他们是保存多项式的文件。对于多项式的输入可采用“系数-空格-指数”形式输入，如“2 3”代表2ⅹ3 。

2）对于地图着色。

修改程序文件夹里的里的点数目、边数目、点、边。

五、测试结果。

一元多项式。

地图着色。六、课程设计小结。

对于本次课程设计，在时间上还是颇为紧张的，因为还有另一个课程设计：数字系统设计的存在。不过还好，最终还是做出来了，所以还是给我增加了许多信心的。

对于一元多项式的计算器，由于《数据结构》一书39面2.4节已对此题有了一定的介绍，所以就用了书上的思想来做这个设计了。另外还有老师曾经留下的数据结构程序的c语言范例，正好一并借用参考了。

其实感觉这个程序的骨架做的蛮熟悉的，使用switch语句做的还是基本完成所要的功能。只不过，不好防止输入错误，另外，一直使用switch语句，颇无新意的。

不过通过这个题目，我还是学会了很多东西，书上没有的很多的编程细节。另外，也增加了我对编程恐惧的免疫力，因为数据结构的的程序的确不好看，一个大屏幕下全是字符，的确看的人发慌。

对于地图着色，刚看到这个题目时，我有点懵懵懂懂了，以前我们做的全是已经数字化的东西，现如今突然给了一个生活中的题目，还真让人吃不消。不得已，只好去查资料，还好，在《算法与数据结构考研试题精选》第360面发现了这个算法，还真是惊天地泣鬼神，这个算法成功的把生活问题转化为数字问题，采用..来标记颜色，然后以某图及其相邻的图比较，不相同，则赋色；相同，没关系，则换下一种颜色，加1而已。

还是啰嗦的说一句，用c语言编的程序外观太丑了。

对于这次课程设计，虽然两题的算法均不是我的，但通过编译、调试两题，还是让我学到不少的东西，对于以后的学习很有益处。同时由于程序还存在很大的缺陷，还有待在以后学习中改进。

七、参考文献。

1）《数据结构清华大学出版社。

2）《算法与数据结构考研试题精选》机械工业出版社。

八、附录。1）一元多项式计算器部分程序。

status locateelem(linklist l,elemtype e,position &q,int(*compare)(elemtype,elemtype))

//若升序链表l中存在与e满足判定函数compare()取值为0的元素，则q指示l中。

// 第一个值为e的结点的位置，并返回true；否则q指示第一个与e满足判定函数。

// compare()取值》0的元素的前驱的位置。并返回false。（用于一元多项式）

link p=

dowhile(p&&(compare(p->data,e)<0));没到表尾且p-><

if(!p||compare(p->data,e)>0) /到表尾或compare(p->data,e)>0

else //找到。

status orderinsert(linklist &l,elemtype e,int(* compare)(elemtype,elemtype))

//将值为e的结点合并到升序链表l的适当位置。

position la,lb;

if(locateelem(l,e,la,compare)) l中存在该指数项。

la-> 改变当前结点系数的值。

数据结构课程设计

数据结构课程设计

数据结构课程设计

数据结构课程设计

其他用户还读了