数据结构课程设计任务书

15161学期《数据结构》课程设计任务书一、设计目的数据结构课程设计是一个独立的实践环节，是对数据结构课程教学理论的延伸和补充，是对数据结构抽象理论知识的综合应用。它有助于学生进一步掌握程序设计的技能与方法，初步感受软件开发过程的项目管理方法与规范，更重要的目的是培养学生分析问题、解决问题、编写程序、动手操作的能力以及锻炼学生的设计创新能力。二、设计要求1、通过课程设计，要求在数据结构的逻辑特性和物理表示、数据结构的选择应用、算法的设计及其实现等方面加深对课程基本内容的理解。同时，在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。2、学生必须仔细研读《数据结构》课程设计要求，以学生自学为主、指导教师指导为辅，认真、独立地完成课程设计的任务，有问题及时主动与指导教师沟通。3、本次课程设计按照教学要求需要在两周时间内独立完成，学生要发挥自主学习的能力，充分利用时间，安排好课设的时间计划，并在课设过程中不断检测自己的计划完成情况，及时地向指导教师汇报。4、编程语言任选。三、设计选题选题说明：同学们可以有两个选择：（1）不带*号的，至少做两个；（2）后面题目*越多难度越大，带*号的至少做一个。根据实际选做题目的难度和数量以及实现程序的完善性可以适当加减分。代码要求：（1）源文件头部应进行注释，列出整个程序的功能（针对一个题目，如有未实现的功能，需明确）、主要函数及其功能；（2）每个函数头部应进行注释，列出此函数的功能、调用参数的意义、返回值的意义。四、题目及要求1、一元稀疏多项式的计算【问题描述】能够按照指数降序排列建立并输出多项式；能够完成两个多项式的相加、相减，并将结果输出。【基本要求】以链式存储结构实现多项式。2、随机整数排序问题【问题描述】针对随机产生2000个以上的整数，采用多种方法进行排序，并显示排序结果，比较各种算法的效率。【基本要求】为了提高效率，所产生的随机整数可以用文件保存，供各排序算法共用；为了更好地进行比较，采用3种以上方法实现排序，并分别保存排序结果；记录每种排序所耗费的时间。3、表达式求值问题【问题描述及要求】从键盘中输入一串四则运算表达式，由计算机求出表达式的运算结果；所输入表达式为以字符序列的形式输入的、语法正确的、不含变量的操作数的整数的算术表达式。4、魔方阵【问题描述】魔方阵是一个古老的智力问题，它要求在一个m*n的矩阵中填入1〜m2的数字（m为奇数），使得每一行、每一列、每条对角线的累加和都相等，如下图所示：

【基本要求】1•输入魔方阵的行数m要求m为奇数，程序对所输入的m作简单的判断，如m有错，能给出提示信息；实现魔方阵；输出魔方阵。5、线索二叉树【问题描述及要求】1．建立中序线索二叉树，并且中序遍历；求中序线索二叉树上已知结点中序的前驱和后继；插入结点到指定位置；4．删除指定结点。6、停车场管理【问题描述】设停车场是一个可以停放n辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次有北向南排列（大门在最南端，最先到达的第一车停放在车场的最北端），若车场内已停满n辆车，那么后来的车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车即可开入；当停车场内某辆车要离开时，在它之后进入的车辆必须先退出车场为它让路，待该辆车开出大门外，其他车辆再按原次序进入车场，每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用。试为停车场编制按上述要求进行管理的模拟程序。【基本要求】以栈模拟停车场，以队列模拟车场外的便道。每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码以及到达或离去的时刻。对每一组输入数据进行操作后的输出信息为：若是车辆到达，则输出汽车在停车场内或便道上的停车位置；若是车辆离去，则输出汽车在停车场内停留的时间和应交纳的费用（在便道上停车不收费）。栈以顺序存储结构实现，队列以链表结构实现。7、迷宫求解（*）【问题描述】以一个n*n（n>=10）的方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。【基本要求】首先实现一个栈类型，然后编写一个求解迷宫的非递归程序。求得的通路以三元组（ij,d）的形式输出，其中（ij）指示迷宫中的一个坐标，d表示走到下一坐标的方向。8、文章编辑（**）【问题描述】输入一页文字，程序可以统计出文字、数字、空格的个数；静态存储一页文章，每行最多不超过80个字符，共N行。【基本要求】分别统计出其中英文字母数和空格数及整篇文章总字数；统计某一字符串在文章中出现的次数，并输出该次数；删除某一子串，并将后面的字符前移。存储结构使用线性表，分别用几个子函数实现相应的功能；输入数据的形式和范围：可以输入大写、小写的英文字母、任何数字及标点符号。输出形式：分行输出用户输入的各行字符；分4行输出"全部字母数"、"数字个数"、"空格个数"、"文章总字数"；输出删除某一字符串后的文章。9、数独游戏（**）【问题描述】在9X9的矩阵中，使行、列的单位元素都为1到9的数字，不得有重复，并且把矩阵从左到右，从上到下平分成9个块，每块3X3,每块的元素也是1到9的数字，不得有重复。每个矩阵的答案是唯一的。可能的输入如下图所示：392158578262217675482356183910、数制转换（***）【问题描述】在日常生活中，常常使用各种编码，如身份证号码、电话号码和邮政编码等，这些编码都是由十进制数组成的。同理，在计算机中采用由若干位二进制数组成的编码来表示字母、符号、汉字和颜色等非数值信息。十进制数N和其他进制数的转换是计算机实现计算的基本算法，数制间转换的实质是进行基数的转换。【基本要求】设计实现任意进制（十六进制、十进制、八进制和二进制）之间的数制转换程序，要求进行某种数制转换后，输入相应的格式正确的数值（也可以是混合小数的形式），程序按照设定的算法执行，给出相对应的进制数数值，对于输入数据的合法性可以不做检查。11、稀疏矩阵运算器（***）【问题描述】实现一个能进行稀疏矩阵基本运算（包括加、减、乘）的运算器。【基本要求】以三元组顺序表表示稀疏矩阵，实现两个矩阵相加、相减、相乘的运算；稀疏矩阵的输入形式为三元组表示，运算结果则以通常的阵列形式列出；首先提示用户输入矩阵的行数和列数，并判断给出的两个矩阵行、列数对于所要求做的运算是否相匹配。可设矩阵的行数和列数均不超过20；程序需给出菜单项，用户按照菜单提示进行相应的操作。12、二叉树基本操作演示程序（***）【问题描述】设计一个与二叉树基本操作相关的演示程序。【基本要求】创建二叉树。按照用户需要的二叉树，构建二叉树；将创建的二叉树，以树状形式输出；分别以先序、中序、后序、层次四种遍历访问二叉树；输出二叉树的叶子结点及叶子结点的个数；输出二叉树的高度。13、宿舍管理查询系统（***）【问题描述】为宿舍管理人员编写一个宿舍管理查询系统。【基本要求】采用交互工作方式；可以增加、删除、修改信息；建立数据文件，数据文件按关键字（姓名、学号、房号）进行排序；查询（按姓名、学号、房间号查询）；打印任一查询结果（可以连续操作）。14、 身份证信息管理系统（****）【问题描述】建立一个身份证信息管理系统，能够进行身份证信息的录入、查找，要求考虑查找效率。【基本要求】采用二叉排序树进行身份证信息的存储；能够进行身份证号码及相关信息的录入，相关信息包括姓名、地址和手机号；能够快速进行身份证号码的查询，并输出相关信息；可以修改身份证号码对应的其他信息，如姓名、地址；可以完成身份证信息的删除。15、 大整数计算器（****）【问题描述】实现大整数（200位以内的整数）的加、减、乘、除运算。【基本要求】设计程序实现两个大整数的四则运算，输出这两个大整数的和、差、积、商及余数。五、成绩考核根据完成任务的情况（必须进行系统验收+提问）、课程设计报告书的质量和课程设计过程中的工作态度等按照50%、30%、20%加