数据结构课程设计题目及规范说明.doc

数据结构课程设计规范一、课程设计教学目的1了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；2初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；3提高综合运用所学的理论知识和方法独立分析和解决问题的能力；4训练用系统的观点和软件开发一般规范进行软件开发。二、基本要求1. 每位学生从所给的两个项目的备选题目中分别选择1题，独立完成， 2. 在自身能力允许的范围内，鼓励学生多作题目，对完成规定2题基础上多作题的同学可以适当加分。3. 课程设计时间：1118周；上机时间：周一至周五下午3：006：00为规定时间，作为考勤依据，下午时间作为自由上机时间，机房免费开放；规定上机地点为实验中心。4. 遵守课程设计的时间、过程要求；遵守实验室有关规定。三、考核方法1.综合成绩（100分）设计报告（100分），2.最终，按照优（90-100分）、良（80-89分）、中（70-79分）、及格（60-69分）、不及格（60分以下）给出考核结论。四、课程设计过程规范1.遵守课程设计的各项要求。2.遵守实验中心的各项规定和要求。3.随时接受指导教师的提问，自查任务完成后主动申请指导教师提问和审查。五、课程设计报告的规范课程设计报告要求规范书写。应当包括如下六个部分：1、设计目的与内容。进行需求分析，确定每个模块的功能要求。即根据设计题目的要求，充分地分析和理解问题，明确问题要求做什么？（而不是怎么做？）2、算法的基本思想进行概要设计和详细设计。说明用到的数据结构定义、主程序的流程及各程序模块之间的调用关系。并用自然语言描述每个模块所涉及的算法。3、测试数据列出对于给定的输入所产生的输出结果。4、源程序及系统文件使用说明附上关键数据结构的定义及关键算法的源代码。5、心得体会谈谈课程设计过程的收获、遇到问题及解决问题过程的思考、程序调试能力的思考、对数据结构这门课程的思考、在课程设计过程中对数据结构课程的认识等内容。6、参考文献参考文献要注明作者、出版社、出版日期。六、最终需提交的内容1完整的程序系统（电子方式提交）（1）能够对输入产生相应的输出，并在输入输出做必要的提示。（2）该部分包括源代码和可执行文件两个部分。（3）所有以电子方式提交的文件全部存在一个目录中，并对其进行压缩（用Winrar或Winzip均可），压缩后的文件按规定格式进行命名，命名格式为：学号+姓名.rar（如200810010101某某.rar）。(4)将提交作品发送到邮箱5622725,邮件主题为:课程设计+班级+姓名(如课程设0某某).2课程设计报告（打印版）,字数不少于2000字七、课程设计题目项目一：课程中的数据结构分析与实现。要求在所学的问题中至少选作一个。题号项目名称内 容 提 要1*线性表（1）实现循环单链表的基本操作(插入，删除，合并)2*栈和队列（2）用栈/队列解Maze问题(用穷举法)或停车场管理问题(要求允许栈和队列中间的车辆提前驶出)3*数组(3)用数组解大数加法问题(递推法求Fibonacci数列第1500项)(4)实现Fibinary Number加法。（5）求出第1500个丑数的问题。4*二叉树(6)构建哈夫曼树并给出哈夫曼编码问题5*图（7）实现邻接矩阵和邻接表存储图结构（8）用程序实现图的遍历（深度优先和广度优先都必须实现）6查找（9）用折半查找按学号查找同学通讯录(按学号非递减有序)（10）用哈稀表查找同学通讯录(按姓名ASCII码除留余数法散列)7排序（11）用贪心法解背包问题（12）演示常用内排序算法比较项目二：实际问题的数据结构分析与实现。要求在下列题目中至少选作一个。1学生信息管理 要求每条学生信息至包含学号(xh)、姓名(xm)、性别(xb)、年龄(nl)、专业(zy)等，完成如下功能：（1）输入学生基本信息记录enter()（2）增加一名学生记录（可和功能1合并）insert()（3）删除指定（按姓名）学生的信息delete()（4）修改指定（按姓名）学生的信息）modify( )（5）查询符合条件的学生（按专业）search()（6）显示学生管理库中的信息display( )2计算一元稀疏多项式要求完成如下功能：（1） 输入并建立多项式creatpolyn()（2） 输出多项式，输出形式为整数序列，序列按指数升序排列printpolyn()（3） 多项式a和b相加，建立多项式a+b，输出相加的多项式addpolyn()（4） 多项式a和b相减，建立多项式a-b，输出相减的多项式subpolyn()用带表头结点的单链表存储多项式。测试数据：（1）(2x+5x8-3.1x11)+(7-5x8+11x9)（2） (6-3x+4.4x2-1.2x9)-(-6-3x+5.4x2+7.8x15)（3）(x+x2+x3)+0（4）(x+x3)-(-x-x-3)3通讯录的制作 要求每条信息至包含姓名（name ）城市（city）电话（tel）QQ号（qq），完成如下功能：（1） 输入信息 enter(); （2） 显示信息display( ); （3） 查找以姓名作为关键字 search( ); （4） 删除信息delete( ); （5） 存盘（将数据保存在文件中，此功能选做）save ( ); 4、运动会分数统计任务:参加运动会有n个学校,学校编号为1n.比赛分成m个男子项目,和w个女子项目.项目编号为男子1.m,女子m+1.m+w.不同的项目取前五名或前三名积分;取前五名的积分分别为:7、5、3、2、1，前三名的积分分别为：5、3、2；哪些取前五名或前三名由学生自己设定。（m=20,n=20）功能要求：1.可以输入各个项目的前三名或前五名的成绩；2.能统计各学校总分；3.可以按学校编号、学校总分、男女团体总分排序输出；4.可以按学校编号查询学校某个项目的情况；可以按项目编号查询取得前三或前五名的学校。规定：输入数据形式和范围：20以内的整数（如果做得更好可以输入学校的名称，运动项目的名称）输出形式：有中文提示，各学校分数为整形界面要求：有合理的提示，每个功能可以设立菜单，根据提示，可以完成相关的功能要求。存储结构：学生自己根据系统功能要求自己设计，但是要求运动会的相关数据要存储在数据文件中。5、学生成绩管理系统要求是这样的：1、用c语言编写一个简单的学生信息管理程序，能实现对学生信息的简单管理。2、具体要求：建立一个4个学生的信息登记表，每个学生的信息包括：学号，姓名，和3门课程的成绩（FOX,C,ENGLISH）。程序运行时显示一个简单的菜单，例如： （1）：信息输入（INPUT） （2）：总分统计（COUNT） （3）：总分排序（SORT） （4）：查询(QUERY） 其中： （1）：对4个学生的信息进行输入； （2）：对每个学生的3门课程统计总分； (3)：对4个学生的总分按降序排序并显示出来； (4)：查询输入一个学号后，显示出该学生的有关信息；6、用邻接矩阵解校园网络布线最小成本问题 (最小生成树)基本要求：1能够完成“网”的建立过程；2利用PRIM或克鲁斯卡尔算法求出最小生成树；3要求有完整的输入、输出，能够进行演示说明。7民航订票系统；任务：通过此系统可以实现如下功能：1录入可以录入航班情况（数据可以存储在一个数据文件中，数据结构、具体数据自定）2查询可以查询某个航线的情况（如，输入航班号，查询起降时间，起飞抵达城市，航班票价，票价折扣，确定航班是否满仓）；可以输入起飞抵达城市，查询飞机航班情况；3订票 （订票情况可以存在一个数据文件中，结构自己设定）可以订票，如果该航班已经无票，可以提供相关可选择航班；4退票 可退票，退票后修改相关数据文件；客户资料有姓名，证件号，订票数量及航班情况，订单要有编号。5修改航班信息：当航班信息改变可以修改航班数据文件。基本要求：1根据以上功能说明，设计航班信息，订票信息的存储结构，设计程序完成功能；2界面要求：有合理的提示，每个功能可以设立菜单，根据提示，可以完成相关的功能要求。根据系统功能要求，可以将问题解决分为以下步骤： a)写出需求分析（做什么） b)分析系统中的各个实体之间的关系及其属性和行为； c)根据问题描述，设计系统关系模型图。e)完成每个函数的定义； f)用户界面的设计 g)分析系统功能模块（系统流程图） h)代码编写 i)功能调试； j)完成系统总结报告以及系统使用说明书。 8. 文章编辑功能：输入一页文字，程序可以统计出文字、数字、空格的个数。静态存储一页文章，每行最多不超过80个字符，共N行；要求（1）分别统计出其中英文字母数和空格数及整篇文章总字数；（2）统计某一字符串在文章中出现的次数，并输出该次数；（3）删除某一子串，并将后面的字符前移。存储结构使用线性表，分别用几个子函数实现相应的功能；输入数据的形式和范围：可以输入大写、小写的英文字母、任何数字及标点符号。 输出形式：（1）分行输出用户输入的各行字符；（2）分4行输出全部字母数、数字个数、空格个数、文章总字数（3）输出删除某一字符串后的文章；9. 编写一个猜数字游戏，有一定的容错功能，界面友好，功能齐全。游戏规则：a，一个四位数，各位上的数字不重复,从1到9。b，按以下提示猜出这个四位数。c，每次猜测输入的数据给出类似的提示*A*B。d，其中A前的*代表你本次猜对了多少个数字。e，其中B前的*代表你本次猜对的数字并且位置正确的个数。10.设计一个日历系统功能要求 ： 1）输入任一年将显示出该年的所有月份日期，对应的星期2）注意闰年情况其显示格式要求如下：1）份：中文英文都可以，2）下一行显示星期，从周日到周六，中英文都可以3）下一行开始显示日期从1号开始，并按其是周几实际情况与上面的星期数垂直对齐当输入2004显示如下：Input the year:2004Input the file name:aThe calendar of the year 2004. Januray 1 February 2 Sun Mon Tue Wed Thu Fri Sat Sun Mon Tue Wed Thu Fri Sat 1 2 3 1 2 3 4 5 6 7 4 5 6 7 8 9 10 8 9 10 11 12 13 14 11 12 13 14 15 16 17 15 16 17 18 19 20 21 18 19 20 21 22 23 24 22 23 24 25 26 27 28 25 26 27 28 29 30 31 29 = = March 3 April 4 Sun Mon Tue Wed Thu Fri Sat Sun Mon Tue Wed Thu Fri Sat 1 2 3 4 5 6 1 2 3 7 8 9 10 11 12 13 4 5 6 7 8 9 10 14 15 16 17 18 19 20 11 12 13 14 15 16 17 21 22 23 24 25 26 27 18 19 20 21 22 23 24 28 29 30 31 25 26 27 28 29 30 = =11.家庭成员的管理问题问题描述 例如有这样的一对老夫妻（A、B），他们生有n男m女，其中，某个儿子（D）娶妻（C）生有x男y女，某个女儿（E）嫁夫（F）生有i男j女，其余的子女有可能婚嫁，也有可能单身，已婚的可能生有孩子若干，其孩子相继婚嫁数据对象是以上所有的家庭成员，要求建立他们之间的夫妻、子女等关系并方便查询。 测试数据 按时间顺序建立家庭关系；按姓名查询某个家庭成员及其配偶和孩子。12校园导航系统基本要求：程序使用无向图表示校园简图，采用邻接矩阵表示各点间的关系、距离，运用结构体记录各信息，通过迪杰斯特拉算法计算两个地点间的最短路径，运用算法记录点到各个点的最短路径、记录最短路径的上各个点。13全国交通咨询模拟1)提供对城市信息进行编辑（如：添加或删除）的功能。2)提供对列车时刻表进行编辑（增设或删除）的功能。3) 提供两种最优决策：最快到达和最省钱到达。4)旅途中耗费的总时间应该包括中转站的等候时间。5)咨询以用户和计算机的对话方式进行。由用户输入起始站、终点站、最优决策原则，输出信息：最快需要多长时间才能到达或者最少需要多少旅费才能到达，并详细说明于何时乘坐哪一趟列车到何地。测试数据：自行设计列车时刻表。14停车场管理设停车场是一个可停放n辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车停放在车场的最北端），若车场内已停满n辆汽车，则后来的汽车只能在门外的便道上等待，一旦有车开走，则排在便道上的第一辆车即可开入；当停车场内某辆车要离开时，在它之后进入的车辆必须先退出车场为它让路，待该辆车开出大门外，其他车辆再按原次序进入车场，每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用。试为停车场编制按上述要求进行管理的模拟程序。课程设计报告书写模版：数据结构课程设计报告项目1题目龙贝格算法的数据结构项目2题目日历系统的设计 班 级： 学 号： 姓 名： 时 间： 一、设计目的与内容1设计目的熟练掌握队列的顺序存储表示和基本操作的实现，能够利用队列设计算法解决简单的应用问题。2设计内容：利用循环队列编写一个简单的事件处理表。用户可以输入和保存一系列事件；当一个事件处理完毕后，它就会从事件处理表中被删除；还可以查询事件处理表中剩余的事件。二、算法的基本思想（此处可加框图描述基本功能模块）被处理事件的数目限定在100以内，并用宏MAX来表示。算法的主要思路是：1函数enter()用来输入事件，调用函数EnQueue()将事件字符串指针保存到事件队列中；基本思路如下：（1）提示并等待输入事件（2）若有事件输入，执行步骤3，否则执行步骤5（3）动态申请存放新事件串的空间，并将输入事件串复制到新申请的内存单元（4）调用EnQuue()函数将新事件插入到队尾（5）结束2函数review()用来显示还没有处理的事件；基本思路如下：（1）（2）（3） 3函数delete()将处理完毕的事件从事件队列中删除，并释放事件内容的存储空间，其中删除事件调用函数DeQueue()完成。基本思路如下：（1）（2）（3） 三、测试数据程序运行实例如下：*队列示例-事件表1-录入,2-显示,3-删除,4-退出*请选择(1-4)：1输入事件1：Marry have a math at 8:00.输入事件2：Marry will learn dancing at 1:00 pm.输入事件3：Marry will watch TV at 6:30 pm.输入事件4：请选择(1-4)：2事件1.Marry have a math at 8:00.事件2.Marry will learn dancing at 1:00 pm.事件3.Marry will watch TV at 6:30 pm.请选择(1-4)：3Marry have a math at 8:00.请选择(1-4)：2事件1.Marry will learn dancing at 1:00 pm.事件2.Marry will watch TV at 6:30 pm.请选择(1-4)：4四、源程序及系统文件使用说明1循环队列的基本操作函数放在seqqueue.h头文件中，程序清单如下：typedef structDataType dataMaxSize;int front, rear; SeqQueue;void QueueInit ( SeqQueue *q ) q-rear = q-front = 0;int QueueEmpty ( SeqQueue q ) if(q.rear = q.front)return 1; else return 0;int EnQueue ( SeqQueue *q, DataType x ) if (q-rear+1) % MaxSize = q-front) return 0; q-dataq-rear = x; q-rear = (q-rear+1) % MaxSize; return 1;int DeQueue ( SeqQueue *q, DataType *x ) if ( QueueEmpty (*q) ) return 0; *x = q-dataq-front; q-front = ( q-front+1) % MaxSize;return 1;2Shijianbiao.cpp文件代码清单如下：#include #include #include #define MaxSize 100typedef char* DataType;#include SeqQueue.h /*循环队列的基本操作函数*/void enter(SeqQueue *q);void review(SeqQueue q);void del(SeqQueue *q);void main() char ch; SeqQueue q; QueueInit(&q); system(cls); /调用系统的CLS清屏命令清屏 printf(n*); printf(n队列示例-事件表); printf(n1-录入,2-显示,3-删除,4-退出：); printf(n*); while(1) printf(n请选择(1-4)：); ch=getchar ();getchar(); sw