2024级数据结构课程设计.docx

《2024级数据结构课程设计.docx》由会员分享，可在线阅读，更多相关《2024级数据结构课程设计.docx（30页珍藏版）》请在优知文库上搜索。

1、课程代号:41110130总学时（或周数）：1周适用专业：计算机科学与技术各专业先修课程：高级语言程序设计、数据结构一、课程设计（实践）目的本课程设计是数据结构课程的组成之一，也是它的接着和延长。采纳集中学习方法，分组完成一个小型应用系统。开设本课程的目的是使学生通过参与小型软件的开发过程，进一步了解并驾驭数据结构与算法的设计方法，具备初步的分析和设计实力；同时培育学生的创新实力和创新意识，熬炼他们的团队协作精神。二、课程设计（实践）要求1 .了解并驾驭数据结构与算法的设计方法，具备初步的分析和设计实力；2 .初步驾驭软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；3 .提高

2、综合运用所学的理论学问和方法独立分析和解决问题的实力；4 .训练用系统的观点和软件开发一般规范进行软件开发，培育软件工作者所应具备的科学的工作方法和作风。5 .设计的题目要求达到肯定工作量（500行以上代码），并具有肯定的深度和难度。6 .编写出课程设计说明书，说明书不少于10页（代码不算）。7 .学生必需细致阅读数据结构课程设计方案，细致主动完成课设的要求。有问题刚好主动通过各种方式与老师联系沟通。学生要发挥自主学习的实力，充分利用时间，支配好课设的时间支配，并在课程设过程中不断检测自己的支配完成状况。三、课程设计（实践）内容设计结束后要写出课程设计报告，以作为整个课程设计评分的书面依据和存

3、档材料设计报告以规定格式的电子文档书写、打印并装订，排版及图、表要清晰、工整。内容及要求如下：封面：题目、班级、姓名、学号、指导老师和完成日期。正文包括以下6个内容：1、分析问题和确定解决方案；以无歧义的陈述说明程序设计的任务，强调的是程序要做什么？并明确规定：（1）输入的形式和输入值的范围；（2）输出的形式；（3）程序所能达到的功能；（4）测试数据：包括正确的输入及其输出结果和含有错误的输入及其输出结果。（5）说明本程序中用到的全部抽象数据类型的定义、主程序的流程以及各程序模块之间的层次（调用）关系。2、具体设计；实现概要设计中定义的全部数据类型，对每个操作只须要写出伪码算法；对主程序和其他

4、模块也都须要写出伪码算法（伪码算法达到的具体程度建议为:依据伪码算法可以在计算机键盘干脆输入高级程序设计语言程序）；可采纳流程图等进行描述，画出函数和过程的调用关系图。3、系统调试与测试；内容包括：（1）列出你的测试结果，包括输入和输出。这里的测试数据应当完整和严格，最好多于需求分析中所列。（2）调试过程中遇到的问题是如何解决的4、结果分析；（1）算法的时空分析（包括基本操作和其他算法的时间困难度和空间困难度的分析）和改进设想；（2）阅历和体会等。5、参考文献；列出参考的相关资料和书籍。6、附录：原程序清单。设计题目：1 .航空订票系统功能要求：（1）录入：可以录入航班状况（数据可以存储在一个

5、数据文件中，数据结构、具体数据自定）（2）查询：可以查询某个航线的状况（如，输入航班号，查询起降时间，起飞抵达城市，航班票价，票价折扣，确定航班是否满仓）；可以输入起飞抵达城市，查询飞机航班状况；（3）订票：（订票状况可以存在一个数据文件中，结构自己设定）可以订票，假如该航班已经无票，可以供应相关可选择航班；（4）退票：可退票，退票后修改相关数据文件；客户资料有姓名，证件号，订票数量及航班状况，订单要有编号。（5）修改航班信息：当航班信息变更可以修改航班数据文件（6）人机界面自定义，要友好。（7）汉化人机界面2 .排序算法性能分析功能要求：（1）能进行各种排序算法运算，排序包括干脆插入、希尔排

6、序、冒泡排序、快速排序、堆排序、二路归并。（2）能对各种算法进行比较，（3）人机界面自定义，要友好。将排序的结果包括排序后的序列、算法关键字比较和移动的次数等。并列表比较。（4）测试数据要求：测试数据至少3组，每组数据个数10000。（5）汉化人机界面较高要求：实现图形化操作界面，在不同界面间可相互切换。3 .求城市之间的光纤网连接的最短电缆长度功能要求：（1）从文件cily.txt中读入一个图，文件cily.txt结构如下：第一行为整数m,n,其中m表示城市个数（顶点数），n表示边数；接着的m行每行都是一个字符串，表示城市名；接下来的n行每行代表一条边，其格式为“城市名城市名距离”。（2）要

7、求在全部城市之间建立光纤网，使所用光纤总长度最短。（3）输出城市建成的光纤网所用光缆的总长及每个连接的长度。4 .哈希表的设计与实现问题描述：设计哈希表实现电话号码查询系统。功能要求：（1）设每个记录有下列数据项：电话号码、用户名、地址；（2）从键盘输入各记录，分别以电话号码和用户名为关键字建立哈希表；（3）采纳再哈希法解决冲突；（4）查找并显示给定电话号码的记录；（5）查找并显示给定用户名的记录。（6）在哈希函数确定的前提下，尝试各种不同类型处理冲突的方法（至少两种），考察平均查找长度的变更。5 .文本格式化问题描述：（1）文本文件非空且以文本文件形式存放（为空没有格式化意义）。输入输出文件

8、名均由用户从键盘输入。（2）字的定义：由非（空格）的随意ASeIl码字符组成。（3）文本文件的定义：由字母字符，数字字符，空格和可以用ASCn代码显示的字符组成。只表示换行的意义。（空格）只表示一个字的结束的意义。（4）任何完整的字都没有被分割在两行:，行尾不齐没关系，但要实现左对齐。每行字符数不超过60（5）输出文件中字与字之间只留一个空格符，即实现多余空格符的压缩。（6）符号指示它后面的正文在格式化时应另起一段排放，段首缩入8个字符的位置。功能要求：（1）输出文件中字与字之间只留一个空格符，即实现多与空格符的压缩：（2）在输出文件中，任何完整的字仍不能分割在两行，行尾不齐没关系，但行首要对

9、齐（即左对齐）；（3）假如所要求的每页页底所空行数不少于3,即将页号印在页底空行中第2行中的中间位置上，否则不印；（4）版面要求的参数要包含：页长（PageLength）每页内文字（不计页号）的行数；页宽（PageWedth）每行内文字所占最大字符数；左空白（LeflMargin）每行文字前的固定空格数；头长（HeadingLengIh）每页页顶所空行数；脚长（FootingLength）每页页底所空行数；起始页号（StartingPageNumber）一首页的页号。见数据结构题集P1176 .哈夫熨编译码器问题描述：利用哈夫曼编码进行信息通信，要求在发送端通过一个编码系统对待传数据预先编码，

10、在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都须要一个完整的编/译码系统。试为这样的信息收发站写一个哈夫曼编/译码系统。功能要求：一个完整的系统应具有以下功能：（1） I：初始化（IniIialiZaliOn）。从终端读入字符集大小n,以及n个字符和n个权值，建立哈夫曼树，并将它存于文件hfmTree中。（2） E：编码（Encoding）。利用已建好的哈夫曼树（如不在内存，则从文件htmTree中读入），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。（3） D：译码（Decoding）。利用已建好的哈夫曼树将文件COde

11、File中的代码进行译码，结果存入文件TeXtFile中。（4） P：印代码文件（Print）。将文件COdeFile以紧凑格式显示在终端上，每行50个代码。同时将此字符形式的编码写入文件COdePrint中。（5） T：印哈夫曼树（TreePrintingK将已在内存中的哈夫曼树以直观的方式（树或凹入表形式）显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrim中。7 .教学支配编制问题功能要求：（1）包括：学期总数，一学期的学分上限，每门课的课程号（固定占3位的字母数字串）、学分和干脆先修课的课程号。（2）允许用户指定下列两种编排策略之一：是使学生在各学期中的学习负担尽量匀称；二

12、是使课程尽可能地集中在前几个学期中。（3）若是依据给定的条件问题无解，则报告适当的信息；否则将教学支配输出到用户指定的文件中。支配的表格格式自行设计。【输出要求】输出各门课程所对应的学分，以及每学期各门课程的支配。【更高要求】产生多种（例如5种）不同的方案，并使方案之间的差异尽可能的大。8 .校内导游询问（1）设计学校的校内平面图，所含景点不少于10个。以图中顶点表示学校各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等相关信息。（2）为来访客人供应图中随意景点的问路查询，即查询随意两个景点之间的一条最短的简洁路径。（3）自己编写程序，校内初始数据以文本文件保存，文件格式依据

13、须要自行定义。对应的地图初始化从文件中读出数据进行初始化。（4）查询的结果应供应屏幕和文件两种方式。有基础的同学尽量实现界面的可视化操作和动态显示。测试数据：由读者依据实际状况指定。9 .平衡二叉树功能要求：(1) 随意输入一个关键字序列，求其平衡二叉树并且用凹凸形式输出；(2) 计算等概率状况下查找胜利的平均查找长度；(3) 用多组测试数据进行测试(3组以上)：较高要求：能够实现依据给定关键字删除平衡二叉树中结点，并输出删除后的结果。10 .全国交通询问模拟问题描述：编制一个全国城市间的交通询问程序，为旅客供应两种或者三种最优决策的交通询问。功能要求：(1)供应对城市信息进行编辑(如：添加或

14、删除)的功能(2) 城市之间有两种交通工具：火车和飞机。供应对列车时刻表和飞机航班进行编辑(添加或删除)的功能。(3) 供应两种最优决策：最快到达或最省钱到达。全程只考虑一种交通工具。(4) 旅途中耗费的总时间应当包括中转站的等候时间。(5)询问以用户和计算机的对话方式进行。由用户输入起始站、终点站、最优决策原则和交通工具，输出信息：最快须要多长时间才能到达或者最少须要多少旅费才能到达，并具体说明一次于何时乘坐哪一趟列车或哪一次班机到何地。11 .稀疏矩阵运算器问题描述：实现一个能进行稀疏矩阵基本运算的运算器。功能要求：(1) 以三元组依次表表示稀疏矩阵，实现两个矩阵相加、相减和相乘的运算。(

15、2) 稀疏矩阵的输入形式采纳三元组表示，而运算结果的矩阵则以通常的阵列形式列出。四、课程设计(实践)进度支配1 .分析问题和确定解决方案：依据设计题目的要求，充分地分析和理解问题，明确问题要求做什么，限制条件是什么。在确定解决方案框架过程中，综合考虑系统功能，考虑怎样使系统结构清晰、合理、简洁和易于调试。最终确定系统的功能模块以及模块之间的调用关系。2 .具体设计：对问题描述中涉及的操作对象定义相应的数据类型，并依据以数据结构为中心的原则划分模块，定义主程序模块。逻辑设计的结果应写出每个抽象数据类型的定义(包括数据结构的描述和每个基本操作的功能说明)，各个主要模块的算法，定义相应的存储结构并写出伪码算法。基本操作的规格说明尽可能明确具体。确定每一个模块的算法流程，画出流程图。3 .编码：把具体设计的结果进一步求精为程序设计语言程序。同时加入一些注解和断言，使程序中逻辑概念清晰；4 .系统调试与测试：采纳自底向上，分模块进行，即先调试低层函数。能够娴熟驾驭调试工具的各种功能，设计测试数据确定疑点，通过修改程序来证明它或绕过它。调试正确后，细致整理源程序及其注释，形