数据结构课程设计方案

1/50《数据结构》课程设计指导书课程代号：41110130总学时或周数）：1周适用专业：计算机科学与技术各专业先修课程：高级语言程序设计、数据结构一、课程设计实践）目的本课程设计是《数据结构》课程的组成之一，也是它的继续和延伸。采用集中学习方法，分组完成一个小型应用系统。开设本课程的目的是使学生通过参加小型软件的开发过程，进一步了解并掌握数据结构与算法的设计方法，具备初步的分析和设计能力；同时培养学生的创新能力和创新意识，锻炼他们的团队协作精神。二、课程设计实践）要求1.了解并掌握数据结构与算法的设计方法，具备初步的分析和设计能力；2.初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；3.提高综合运用所学的理论知识和方法独立分析和解决问题的能力；4.训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。5.设计的题目要求达到一定工作量500行以上代码），并具有一定的深度和难度。2/506.编写出课程设计说明书，说明书不少于10页代码不算）。7.学生必须仔细阅读《数据结构》课程设计方案，认真主动完成课设的要求。有问题及时主动通过各种方式与教师联系沟通。学生要发挥自主学习的能力，充分利用时间，安排好课设的时间计划，并在课程设过程中不断检测自己的计划完成情况。三、课程设计实践）内容设计结束后要写出课程设计报告，以作为整个课程设计评分的书面依据和存档材料。设计报告以规定格式的电子文档书写、打印并装订，排版及图、表要清楚、工整。内容及要求如下：封面：题目、班级、姓名、学号、指导教师和完成日期。正文包括以下6个内容：1、分析问题和确定解决方案；以无歧义的陈述说明程序设计的任务，强调的是程序要做什么？并明确规定：(1输入的形式和输入值的范围；(2输出的形式；(3程序所能达到的功能；(4测试数据：包括正确的输入及其输出结果和含有错误的输入及其输出结果。(5说明本程序中用到的所有抽象数据类型的定义、主程序的流程以及各程序模块之间的层次(调用关系。3/502、详细设计；实现概要设计中定义的所有数据类型，对每个操作只需要写出伪码算法；对主程序和其他模块也都需要写出伪码算法(伪码算法达到的详细程度建议为：按照伪码算法可以在计算机键盘直接输入高级程序设计语言程序；可采用流程图等进行描述，画出函数和过程的调用关系图。3、系统调试与测试；内容包括：1）列出你的测试结果，包括输入和输出。这里的测试数据应该完整和严格，最好多于需求分析中所列。2）调试过程中遇到的问题是如何解决的4、结果分析；1）算法的时空分析(包括基本操作和其他算法的时间复杂度和空间复杂度的分析和改进设想；2）经验和体会等。5、参考文献；列出参考的相关资料和书籍。6、附录：原程序清单。设计题目：1.航空订票系统4/50功能要求：（1）录入：可以录入航班情况数据可以存储在一个数据文件中，数据结构、具体数据自定）（2）查询：可以查询某个航线的情况如，输入航班号，查询起降时间，起飞抵达城市，航班票价，票价折扣，确定航班是否满仓）；可以输入起飞抵达城市，查询飞机航班情况；（3）订票：订票情况可以存在一个数据文件中，结构自己设定）可以订票，如果该航班已经无票，可以提供相关可选择航班；（4）退票：可退票，退票后修改相关数据文件；客户资料有姓名，证件号，订票数量及航班情况，订单要有编号。（5）修改航班信息：当航班信息改变可以修改航班数据文件（6）人机界面自定义，要友好。（7）汉化人机界面2.排序算法性能分析功能要求：（1）能进行各种排序算法运算，排序包括直接插入、希尔排序、冒泡排序、快速排序、堆排序、二路归并。（2）能对各种算法进行比较，5/50（3）人机界面自定义，要友好。将排序的结果包括排序后的序列、算法关键字比较和移动的次数等。并列表比较。（4）测试数据要求：测试数据至少3组，每组数据个数10000。（5）汉化人机界面较高要求：实现图形化操作界面，在不同界面间可相互切换。3．求城市之间的光纤网连接的最短电缆长度功能要求：（1）从文件city.txt中读入一个图，文件city.txt结构如下：第一行为整数m，n，其中m表示城市个数顶点数），n表示边数；接着的m行每行都是一个字符串，表示城市名；接下来的n行每行代表一条边，其格式为“城市名城市名距离”。（2）要求在所有城市之间建立光纤网，使所用光纤总长度最短。（3）输出城市建成的光纤网所用光缆的总长及每个连接的长度。4.哈希表的设计与实现问题描述：设计哈希表实现电话号码查询系统。功能要求：（1）设每个记录有下列数据项：电话号码、用户名、地址；（2）从键盘输入各记录，分别以电话号码和用户名为关键字建立哈希表；（3）采用再哈希法解决冲突；6/50（4）查找并显示给定电话号码的记录；（5）查找并显示给定用户名的记录。（6）在哈希函数确定的前提下，尝试各种不同类型处理冲突的方法至少两种），考察平均查找长度的变化。5.文本格式化问题描述：（1）文本文件非空且以文本文件形式存放为空没有格式化意义）。输入输出文件名均由用户从键盘输入。（2）字的定义：由非‘@’，‘’(空格）的任意ASCII码字符组成。（3）文本文件的定义：由字母字符，数字字符，空格和可以用ASCII代码显示的字符组成。‘@’只表示换行的意义。‘’(空格只表示一个字的结束的意义。（4）任何完整的字都没有被分割在两行:，行尾不齐没关系，但要实现左对齐。每行字符数不超过60（5）输出文件中字与字之间只留一个空格符，即实现多余空格符的压缩。（6）符号‘@’指示它后面的正文在格式化时应另起一段排放，段首缩入8个字符的位置。功能要求：（1）输出文件中字与字之间只留一个空格符，即实现多与空格符的压缩；7/50（2）在输出文件中，任何完整的字仍不能分割在两行，行尾不齐没关系，但行首要对齐即左对齐）；（3）如果所要求的每页页底所空行数不少于3，即将页号印在页底空行中第2行中的中间位置上，否则不印；（4）版面要求的参数要包含：①页长PageLength）—每页内文字不计页号）的行数；②页宽PageWedth）—每行内文字所占最大字符数；③左空白LeftMargin）—每行文字前的固定空格数；④头长HeadingLength）—每页页顶所空行数；⑤脚长FootingLength）—每页页底所空行数；⑥起始页号StartingPageNumber）—首页的页号。见《数据结构题集》P1176.哈夫曼编译码器问题描述：利用哈夫曼编码进行信息通信，要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码复原）。对于双工信道即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站写一个哈夫曼编/译码系统。功能要求：一个完整的系统应具有以下功能：8/50（1）I：初始化Initialization）。从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件hfmTree中。（2）E：编码Encoding）。利用已建好的哈夫曼树如不在内存，则从文件htmTree中读入），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。（3）D：译码Decoding）。利用已建好的哈夫曼树将文件CodeFile中的代码进行译码，结果存入文件TextFile中。（4）P：印代码文件Print）。将文件CodeFile以紧凑格式显示在终端上，每行50个代码。同时将此字符形式的编码写入文件CodePrint中。（5）T：印哈夫曼树TreePrinting）。将已在内存中的哈夫曼树以直观的方式树或凹入表形式）显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrint中。7.教案计划编制问题功能要求：（1）包括：学期总数，一学期的学分上限，每门课的课程号固定占3位的字母数字串）、学分和直接先修课的课程号。（2）允许用户指定下列两种编排策略之一：是使学生在各学期中的学习负担尽量均匀；二是使课程尽可能地集中在前几个学期中。9/50（3）若是根据给定的条件问题无解，则报告适当的信息；否则将教案计划输出到用户指定的文件中。计划的表格格式自行设计。【输出要求】输出各门课程所对应的学分，以及每学期各门课程的安排。【更高要求】产生多种(例如5种不同的方案，并使方案之间的差异尽可能的大。8.校园导游咨询（1）设计学校的校园平面图，所含景点不少于10个。以图中顶点表示学校各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等相关信息。（2）为来访客人提供图中任意景点的问路查询，即查询任意两个景点之间的一条最短的简单路径。（3）自己编写程序，校园初始数据以文本文件保存，文件格式根据需要自行定义。对应的地图初始化从文件中读出数据进行初始化。（4）查询的结果应提供屏幕和文件两种方式。有基础的同学尽量实现界面的可视化操作和动态显示。测试数据：由读者根据实际情况指定。9.平衡二叉树功能要求：（1）任意输入一个关键字序列，求其平衡二叉树并且用凹凸形式输出；10/50（2）计算等概率情况下查找成功的平均查找长度；（3）用多组测试数据进行测试3组以上）；较高要求：能够实现根据给定关键字删除平衡二叉树中结点，并输出删除后的结果。10.全国交通咨询模拟问题描述：编制一个全国城市间的交通咨询程序，为旅客提供两种或者三种最优决策的交通咨询。功能要求：（1）提供对城市信息进行编辑如：添加或删除）的功能（2）城市之间有两种交通工具：火车和飞机。提供对列车时刻表和飞机航班进行编辑添加或删除）的功能。（3）提供两种最优决策：最快到达或最省钱到达。全程只考虑一种交通工具。（4）旅途中耗费的总时间应该包括中转站的等候时间。（5）咨询以用户和计算机的对话方式进行。由用户输入起始站、终点站、最优决策原则和交通工具，输出信息：最快需要多长时间才能到达或者最少需要多少旅费才能到达，并详细说明一次于何时乘坐哪一趟列车或哪一次班机到何地。11．稀疏矩阵运算器问题描述：11/50实现一个能进行稀疏矩阵基本运算的运算器。功能要求：（1）以三元组顺序表表示稀疏矩阵，实现两个矩阵相加、相减和相乘的运算。（2）稀疏矩阵的输入形式采用三元组表示，而运算结果的矩阵则以通常的阵列形式列出。四、课程设计实践）进度安排1.分析问题和确定解决方案：根据设计题目的要求，充分地分析和理解问题，明确问题要求做什么，限制条件是什么。在确定解决方案框架过程中，综合考虑系统功能，考虑怎样使系统结构清晰、合理、简单和易于调试。最后确定系统的功能模块以及模块之间的调用关系。2.详细设计：对问题描述中涉及的操作对象定义相应的数据类型，并按照以数据结构为中心的原则划分模块，定义主程序模块。逻辑设计的结果应写出每个抽象数据类型的定义(包括数据结构的描述和每个基本操作的功能说明，各个主要模块的算法，定义相应的存储结构并写出伪码算法。基本操作的规格说明尽可能明确具体。确定每一个模块的算法流程，画出流程图。3.编码：把详细设计的结果进一步求精为程序设计语言程序。同时加入一些注解和断言，使程序中逻辑概念清楚；12/504.系统调试与测试：采用自底向上，分模块进行，即先调试低层函数。能够熟练掌握调试工具的各种功能，设计测试数据确定疑点，通过修改程序来证实它或绕过它。调试正确后，认真整理源程序及其注释，形成格式和风格良好的源程序清单和结果；根据系统功能选择有代表性的数据进行测试，发现系统存在的不足并逐步改进。5.结果分析：程序运行结果包括正确的输入及其输出结果和含有错误的输入及其输出结果。算法的时间、空间复杂性分析；6.完成课程设计报告.课程设计按照教案要求需要一周时间完成，一周中每天按每周5天）至少要有6学时的上机来调试C语言设计的程序。整体设计和详细设计1.5天编代码1天调试和测试1.5天设计论文书写0.5天演示软件和答辩1天五、使用教材与参考资料1《数据结构》c语言描述），