《数据结构课程设计要求及题目.doc》由会员分享，可在线阅读，更多相关《数据结构课程设计要求及题目.doc（5页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数据结构课程设计任务及要求 本课程设计要求针对以具有一定规模和复杂性，以数据结构及算法设计为核心的程序设计类问题，从问题建模、数据结构设计、算法设计与实现、系统测试等环节综合应用所学知识，完成课题任务，撰写规范的课程设计报告。数据结构课程设计同时也是对软件开发全过程的基础训练，重在实际动手编写、调试中等程度复杂程序的能力训练。从以下4题中选择一个，建立完整的系统框架，划分各个模块，确定模块的功能以及模块间的相互联系方式，分步骤编写、调试程序，对系统进行综合测试，最后把各方面的资料整理成相应的文档。一、考核方式及要求课程设计作为与数据结构课程相配合、同时又是独立设置的综合性训练，最终的考核以学生
2、设计完成的程序系统以及课程设计报告作为考核依据,要求所完成的系统现场运行及报告。1、提交电子文档：l 课程设计报告；l 源程序文件；l 可执行系统文件l 相应测试用例数据文件以上文档压缩打包提交打包后文档名：st_ds.rar2、交时间及方式：课程设计周内：周四五机房实验课内，实验室现场运行报告后提交3、分组：每组人数2人注明组长与分工；课程设计报告电子文档独立提交4、 实验报告构成:见示例文档二、设计课题1 超长整数运算【问题描述】编程实现无符号超长整数的算术运算（加、减、乘、除）。【基本要求】加法运算结果可能产生进位；减法运算结果可以为负；如果被乘数分别为m、n位，则乘积可能为m+n位；除
3、法运算要求输出整数商和余数。运算数据可以由键盘输入或者随机产生，但位数不限，且其中不得包含数字以外的其它符号。如果输入的数据不正确则显示“Input error.”。系统运行界面自行设计。例如:输入数据是：X=和Y=则显示结果为：X+Y=X-Y=X*Y=53110X div Y=X mod Y=【测试要求】测试用例应该覆盖：1)两个数等长，不等长；2)加法结果有进位、无进位；3）减法结果为0、=0、0，结果位数减少、不减少4）乘法位数(n+m)和=(n+m),以及结果为0;5) 除法商0及非0,可整除和不可整除，除数为0和非0；6）输入数据合法和不合法【可选扩展】 实现无符号超长浮点数的算术运
4、算（加、减、乘、除），这里整数和小数位数不限，加、减、乘结果为精确结果，除法如果不能除尽，则输出精度可以任意指定。2、程序文档分析系统【问题描述】输入指定C程序源码，统计该程序总行数，其中的代码行、注释行、空行行数，程序员自定义函数个数及个函数体行数和平均行数；利用以上统计信息给出该程序风格评价。系统运行界面自行设计。【基本要求及约定】(1) 仅考虑标准C源程序文件作为文本或者流文件输入；(2) 设输入文件不含C编码语法错误。(3) 程序文件按行边输入，边识别统计代码行、注释行、空行、函数头行、函数体的开始与结束以便实现相应统计；(4) 不考虑一句代码书写多行的情况；(5) 空行不含任何可显示
5、字符(6) 注释行分两种情况：a) 以/*开始，*/结束，可以一行，也可多行；b) 以/开始的当前行c) 不考虑代码行后接/开始的注释情况（如果出现视作代码行）(7) 每个代码行最多只有一个、switch、struct，typedef；(8) 每个函数的代码行数不含该函数体内的空行和注释行；(9) 外部宏语句(如#include、#define等)、外部类型定义及说明、外部变量定义视作代码行，但不能计入任何函数体行长。(10)程序风格评价为代码、注释、空行三方面，每方面分四个等级，评价标准如下表。A级B级C级D级代码(函数体平均行数)1015行89或者1620行57或者2124行24行注释(占
6、程序总行数百分比)1525%1014或者2630%59或者3135%35%空行(占程序总行数百分比)1525%1014或者2630%59或者3135%35%例如，输入源程序文件”example.c”，分析报告示例：源程序exmaple.c风格分析报告：总代码行数：180， 代码行/总行=61%注释行数： 63， 注释行/总行=21%空行数： 52， 空行/总行=13%本程序含9个函数，各函数体行长：FunctionA(): 17行FunctionB(): 9行main()： 12行函数体平均长度：12.9行 综合评价：函数规模控制：A注释风格评价：A适当空行评价: B【测试要求】测试先从典型小
7、程序文件开始，用例应该覆盖以上(1)(10)各种情况。看是否能够输出预期报告。程序能够正确运行后，对你所开发的程序本身进行分析评价。【可选扩展】(1)输出报告中增加源程序用户自定义标识符一览表。给出每个标识符出现的行号和所在函数体(或者外部).注意：一个标识符可以在多行出现。(2)报告本程序文件中自定义函数的调用序列，如果为递归函数给予标识（包括直接递归和间接递归）。3、导航路径规划【问题描述】给定全国公路网络系统(参照教材图7.33)，根据导航策略（时间最短，里程最短、公路通行费用最省）给出路径规划。系统运行界面自行设计。【基本要求及约定】(1) 参照图7.33点各城市间道路做适当添加，使得
8、有些城市之间的道路可以有高速公路、普通公路，对图中所有道路必须标识是高速还是普通公路。(2) 两个城市之间可以有高速和普通公路同时存在，且各自里程数可以不同。(3) 约定：两城市之间有高速则高速通行时间最短；全国高速收费标准统一(￥0.5元/km)；普通公路不收费。(4) 用户以人机对话方式输入旅行起始、终止城市名（或者代码）,选择导航策略(缺省策略是里程最短)，程序输出从起点到终点的路径，总路径长度和所需通行费用(5) 任意两个城市之间的通行路径都是存在的(可以有多条)。(6) 必须考虑某些城市之间只有一条道路（高速或者普通公路）的情况；(7) 全国公路网络数据以文件方式输入，但系统可以实现
9、对道路信息的编辑修改（增加、删除、修改道路属性(类型、里程数)例如，输入起点:北京 终点:乌鲁木齐 策略：里程最短输出：规划路径：北京呼和浩特(668km,普通公路)；呼和浩特兰州(1145km,普通公路)；兰州乌鲁木齐(1892km,高速公路)；总里程：3605km通行费用：￥946元【测试要求】测试先从局部小区域公路网络开始，用例应该覆盖以上(1)(6)要求。【可选扩展】增加策略如下：(1) 规划路径中通过城市最少；(2) 输入所驾驶车辆平均油耗及油价(设油价x元/升,y升/100km)，规划通行费用最省路径。通行费用=高速收费+油费4 排序算法实验分析【问题描述】数据结构教材中讨论的各种
10、编排序算法的时间复杂性分析结果仅仅是基于数学理论的估计值。本设计要求通过不同规模的随机数据排序中关键字比较和数据移动的实验统计来分析比较在不同规模下各种排序时间复杂性。【基本要求及约定】(1)实现直接插入、直接选择、冒泡排序、Shell排序、快速排序、堆排序、二路归并排序等7种排序算法(2)1）被排序样本为由计算机产生长度为n的随机整数序列，这里n分别取20，100，500，1000。随机整数值的范围：11000,数据可重复。(3)要求程序实现对同一随机数序列样本的不同排序算法，并统计各排序过程中的数据比较和移动次数。(4)最后对各组数据运行结果进行分析比较，包括不同规模下各种排序方法的时间复杂性的性状和统计结果波动范围。【测试要求】测试数据由随机数发生器产生。程序调试中先对小样本数据运行，以保证排序算法的有效性。然后再对大样本数据进行实验统计【可选扩展】(1) 增加折半插入排序，优化的冒泡排序，基数排序(2) 外排序实验分析对长度为100、1000、10000的随机整数数据文件，实现简单二路归并排序，三带二路归并排序和四带三路归并排序，统计数据移动次数和文件读写趟数。