《数据结构》课程设计计划书

《数据结构》课程设计计划书班级：2012信计专业授课教师：马阿曼一、课程设计目的《数据结构》课程是计算机科学与技术专业的核心专业基础课。本课程设计的目的是将数据结构理论和实践结合起来，锻练学生编写程序过程中的数据结构使用和分析、解决实际问题的能力。1、使学生进一步理解和掌握课堂上所学各种基本抽象数据类型的逻辑结构、存储结构和操作实现算法，以及它们在程序中的使用方法。2、使学生掌握软件设计的基本内容和设计方法，并培养学生进行规范化软件设计的能力。3、使学生掌握使用各种计算机资料和有关参考资料，提高学生进行程序设计的基本能力。二、课程设计内容

《数据结构》课程设计包含以下主要内容：

1、查阅相关资料确定课题；

2、课题所设计的数据结构设计、算法设计；

3、编写代码并调试；

4、完成课程设计报告；5、进行课设答辩。三、设计地点及时间安排地点：瑞樟6-402时间：2014年6月3、4、5、6、7、8号时间安排课程设计计划3号布置课题和要求：课题内容介绍，课程设计安排、课程设计纪律，注意事项学生选题，做好课题的前期准备工作4号需求分析：根据所选课题进行总体设计，确定数据结构，确定主要功能模块（函数）和采用的算法等。选择和准备原始数据确定输入和输出方式5号—8号编码实现：主要功能模块的功能实现输入和输出数据方式的整合调试和测试程序的功能检验程序是否完整，结果是否符合要求，对程序进行验收进行课程设计答辩撰写课程设计报告并打印，整理源代码一并上交四、课程设计报告的书写格式1、问题描述：描述要求编程解决的问题。2、基本要求：给出程序要达到的具体的要求。3、测试数据：设计测试数据，或具体给出测试数据。要求测试数据能全面地测试所设计程序的功能。4、算法思想：描述解决相应问题算法的设计思想。5、模块划分：描述所设计程序的各个模块（即函数）功能。6、数据结构：给出所使用的基本抽象数据类型,所定义的具体问题的数据类型,以及新定义的抽象数据类型。7、算法设计分析：给出算法的设计分析和算法流程图。8、源程序：给出所有源程序清单，要求程序有充分的注释语句，至少要注释每个函数参数的含义和函数返回值的含义。9、测试情况：给出程序的测试情况，并分析运行结果。10、收获及体会：写出此次课程设计过程中的收获及体会。五、评分标准程序运行结果（30%）设计报告（30%）设计考勤，平时上机成绩，教师不定期检查（10%）学生根据自己设计报告对教师的提问可以熟练的解释（10%）设计课题的难易程度（20%）六、参考设计题目课程设计题一：学生成绩管理系统

设计目的：掌握线性链表的建立。掌握线性链表的基本操作。掌握查找的基本算法。设计内容：

利用线性链表实现学生成绩管理系统，具体功能：输入、输出、插入、删除、查找、追加、读入、显示、保存、拷贝、排序、索引、分类合计、退出，并能在屏幕上输出操作前后的结果。

设计要求：写出系统需求分析,并建模。编程实现,界面友好。输出操作前后的结果。

课程设计题二：停车场管理系统

设计目的：掌握栈和队列的建立。掌握栈和队列的基本操作。3、深入了解栈和队列的特性,以便在解决实际问题中灵活运用它们。4、加深对栈和队列的理解和认识。设计内容：

设有一个可以停放n辆汽车的狭长停车场,它只有一个大门可以供车辆进出。车辆按到达停车场时间的早晚依次从停车场最里面向大门口处停放(最先到达的第一辆车放在停车场的最里面)。如果停车场已放满n辆车,则后来的车辆只能在停车场大门外的便道上等待,一旦停车场内有车开走,则排在便道上的第一辆车就进入停车场。停车场内如有某辆车要开走,在他之后进入停车场的车都必须先退出停车场为它让路,待其开出停车场后,这些车辆在依原来的次序进场。每辆车在离开停车场时,都应依据它在停车场内停留的时间长短交费。如果停留在便道上的车未进停车场就要离去,允许其离去,不收停车费,并且仍然保持在便道上等待的车辆的次序。编制一程序模拟该停车场的管理。

设计要求：以栈模拟停车场,以队列模拟车场外的便道,按照从终端读入的输入数据序列进行模拟管理。每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码以及到达或离去的时刻。对每一组输入数据进行操作后的输出信息为：若是车辆到达,则输出汽车在停车场或便道上的停车位置；若是车辆离去,则输出汽车在停车场内停留的时间和应交纳的费用(在便道上停留的时间不收费，功能可自己添加)。

课程设计题三：约瑟夫(Joseph)环

设计目的：掌握单向循环链表的建立。掌握单向循环链表的操作。设计内容：

编号是1,2,……,n的n个人按照顺时针方向围坐一圈,每个人只有一个密码(正整数)。一开始任选一个正整数作为报数上限值m,从第一个仍开始顺时针方向自1开始顺序报数,报到m时停止报数。报m的人出列,将他的密码作为新的m值,从他在顺时针方向的下一个人开始重新从1报数,如此下去,直到所有人全部出列为止。请设计一个程序求出出列顺序。

设计要求：利用单向循环链表存储结构模拟此过程,按照出列的顺序输出各个人的编号。测试数据：m的初值为20,n=7,7个人的密码依次为3,1,7,2,4,7,4,首先m=6,则正确的输出是什么？输入数据：建立输入函数处理输入的数据,输入m的初值n,输入每个人的密码,建立单向循环链表。输出形式：建立一个输出函数,将正确的出列顺序输出。

课程设计题四：文学研究助手的实现

设计目的：熟悉串类型的实现方法和文本匹配方法。熟悉一般文字处理软件的设计方法。设计内容：

文学研究人员需要统计某篇英文小说中某些形容词的出现次数和位置。试写一个实现这一目标的文字统计系统,称为“文学研究助手”。

设计要求：英文小说存于一个文本文件中。待统计的词汇集合要一次输入完毕。3、程序的输出结果是每个词的出现次数和出现位置所在行的行号,格式自行设计。

课程设计题五：一元稀疏多项式计算器

设计目的：掌握稀疏矩阵的相关运算。掌握广义表的操作。设计内容：

设计一个一元稀疏多项式简单计算器。

设计要求：

一元稀疏多项式简单计算器的基本功能是：输入并建立多项式；输出多项式,输出形式为整数序列：n,c1,e1,,c2,e2……cn,en,其中n是多项式的项数,ci和ei分别是第i项的系数和指数,序列按指数降序排列。多项式a和b相加,建立多项式a+b多项式a和b相减,建立多项式a-b

课程设计题六：哈夫曼树及其应用

设计目的：熟悉树的各种存储结构及其特点。掌握建立哈夫曼树和哈夫曼编码的方法及带权路径长度的计算。设计内容：

欲发一封内容为AABBCAB……(共长100字符,其中:A、B、C、D、E、F分别有7、9、12、22、23、27个)的电报报文,实现哈夫曼编码。

设计要求：分析系统需求。建立哈夫曼树。进行哈夫曼编码,并求出平均编码长度。编程实现2、3步骤。

课程设计题七：哈夫曼编/译码器

设计目的：掌握建立哈夫曼树和哈夫曼编码的方法。掌握哈夫曼编码的实际应用方法。设计内容：

利用哈夫曼编码进行通信可以大大提高信道利用率,缩短信息传输时间,降低传输成本。但是,这要求在发送端通过一个编码系统对待传数据预先编码,在接收端将传来的数据进行译码。对于双工信道(即可以双向传输信息的信道),每端都需要一个完成的编\译码系统。试为这样的信息收发站写一个哈夫曼的编\译码系统。

设计要求：初始化。从终端读入字符集大小n,以及n个字符和n个权值,建立哈夫曼树。编码。利用已建好的哈夫曼树,对正文进行编码。译码。对编码好的内容进行译码。打印编码。打印哈夫曼树。

课程设计题八：图的遍历演示

设计目的：理解图的基本概念,熟悉图的各种存储结构及其构造算法。掌握图的遍历方法。设计内容：

实现图的深度优先、广度优先遍历算法,并输出原图结构及遍历结果。

设计要求：两种遍历方法必须都要实现,写出画图的思路。界面友好,函数功能要划分合理。总体设计应画一流程图。程序要加必要的注释。5、提供程序测试方案。

课程设计题九：交通咨询系统设计

设计目的：熟练掌握迪杰斯特拉算法和费洛伊德算法,能够利用它们解决最短路径问题。能够解决工程项目实施过程中的关键路径问题。设计内容：

设计一个交通咨询系统,能让旅客咨询从任一个城市定点到另一个城市定点之间的最短路径或最低花费或最少时间等问题。对于不同的咨询要求、可输入城市间的路程或所需时间或所需花费。

设计要求：1、建立交通网络网的存储结构。2、总体设计要画流程图。提供程序测试方案。界面友好。

课程设计题十：航班信息的查询与检索

设计目的：深刻理解排序的定义和各种排序方法的特点,并能灵活的应用；掌握描述查找过程的判定树的构造方法。设计内容：

设计民航售票处的计算机系统可以为客户提供下列各项服务：1.

查询航线：根据旅客提出的终点站名输出下列信息：航班号、飞机号、星期几飞行、最近一天航班的日期和余票额；