数据结构课程设计报告课案

广西科技大学鹿山学院课 程 设 计2015-2016 学年 第 2 学期课程名称： 数据结构课程设计 设计名称： 数据结构课程设计 系 别： 电气与计算机工程系 专业班级： 计软141班 姓 名： 邓康言 学 号： 指导教师： 俸学文 评阅成绩： 评阅人： 二一六年三月三十日 电气与计算机工程系实践教学管理中心广西科技大学鹿山学院课程设计目录一、任务书12.1.存储结构与基本运算的算法12.3.学生管理系统12.6.数据库管理系统23.2括号的匹配73.5马踏棋盘84.2 看病排队候诊问题94.4 停车场管理105.2 KMP算法125.4 大型整数计算127.2 线索二叉树的创建及遍历137.4电文的编码的译码147.5家族关系查询系统15二、课程设计总结16三、参考文献17一、任务书2.1.存储结构与基本运算的算法任务：用C语言描述顺序表和线性表 2.3.学生管理系统 任务：要求以学生成绩管理业务为背景，设计一个“学生管理系统”。主要对学生资料的录入、浏览、插入、和删除等基本功能的实现算法思路：管理学生的成绩适合用单链表，方便插入和删除学生记录实现动态管理。（1） 定义单链表的结构体模块（2） 单链表的建立模块（3） 单链表的结点插入模块（4） 单链表的结点删除模块（5） 单链表的结点数据输出模块（6） 主函数模块运行结果：算法心得：本程序为每一个处理功能都写了相应的函数模块。从而使得学生管理系统具有实用性。2.6.数据库管理系统 任务：设计一个数据库管理系统，用户可以自行定义和创建数据库，能够对数据库实现插入、浏览、浏览定位、条件定位、按条件修改、按条件排序、删除和全部删除等功能实现。并能保存数据库信息到指定文件以及打开并使用已存在的数据库文件，但数据库结构定义后不允许修改。算法思路：由于数据库是通用的，因此先定义一个通用数据库。用户 这个库结构上可以应用所需的多个字段类型，创建自己的 数据库。（1） 首先声明必要的变量和定义数据库结构（2） 显示帮助界面函数模块（3） 创建数据库函数模块（4） 打开数据库函数模块（5） 追加数据函数模块（6） 浏览数据库函数模块（7） 浏览定位函数模块（8） 按条件删除函数模块（9） 按条件定位模块（10） 按条件修改数据函数模块（11） 按字段排序函数模块（12） 关闭数据库函数模块（13） 主函数模块运行结果：以工资管理为例子显示帮助界面使用creat命令创建数据库并定义字段及其类型使用appe命令追加数据，根据提示一次输入相应数据使用brows 命令浏览数据库信息使用go命令进行定位，disp命令浏览定位信息使用delete for 命令，按条件删除使用sort on 命令。按字段进行排列，默认为升序排列使用change for命令，按条件修改数据使用zap命令删除数据库中全部数据使用/use命令关闭数据库使用quit命令退出系统算法心得：综合运用了线性表和文件等相关知识，实现了foxbase数 据库的基本功能，并且模拟仿真系统的设计和开发。加深了对数据库系统的认识和理解。并提高了自己的编程能力。3.2括号的匹配 任务：设计一个算数表达式中包括圆括号、方括号或花括号三种类型的括号、编写一个算法判断其中括号是否匹配。算法思路：使用一个运算符栈st，逐个读入字符，当遇到括号时判断 栈顶指针是否为匹配的括号，若不是，则括号不匹配。算 法结束。若是。则退栈，继续读取下一个字符，直所有字 符都读完为止。若栈是空。则说明括号时匹配的。否则 括号不匹配。运行结果：算法心得：括号匹配是栈的典型应用。算法简单易懂。上机的具体实 现。提高了自己的编程能力。3.5马踏棋盘 任务：设计一个国际象棋的马踏遍棋盘的演示程序算法思路：由用户指定一个马的初始位置。按照顺时针顺序，每次产 生一个新的路点，并验证此路点的可能性，需要考虑路点 是否超出了棋盘的范围和此路点是否已经走过。如果新路 点可用。则入栈，并执行下一步。重复进行如上步骤。直 到找到一个马能踏遍棋盘的行走路线并输出。运行结果：算法心得：马踏棋盘是一个相对复杂的问题，大多数初始位置都需要 运行很长时间。本程序采用的是栈的非递归回溯算法。让 我对这种算法加深了印象4.2 看病排队候诊问题任务：用队列模拟看病排队候诊。根据病人的病情规定不同的优先 级别，然后选择优先级别最高的病人进行诊治。算法思路：定义两个队列q1,q2.q1对应优先级别低的队列.q2对应优 先级别高的队列。当有新的病人加入队列候诊时。根据用 户从键盘敲入终端输入的优先级别，将该病人加入对应的 队列中。并同时生产一个病人ID。运行结果：算法心得：根据需求。懂得了运用链式队列来实现看病排队候诊的问题。4.4 停车场管理任务：设停车场内只有一个可停放n辆汽车的狭长甬道。且只有一个大门供汽车进入。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列。若停车场内已经停满n辆车。则后来的汽车只能在门外等候。一旦有车开走。则排在变道的第一辆车就可以开入。算法思路：使用栈和队列两种数据结构实现模拟停车场的管理。为了 模拟车辆收费的信息。定义车辆的信息结点类型。程序中 程序中单独实现两个函数。1. 模拟停车场进出需要输入车辆信息。包括车牌号及进出时间2. 当车辆离开，需打印输出车辆离开后的信息3. 车辆离开，另设一个栈，给离去让路而从停车场退出的汽车临时停放。车辆离开需检查便道是否有车等候。若有。则进行便道车进入停车场的操作。并输入时间并计费。运行结果：算法心得：掌握了使用栈和队列两种数据结构实现了停车场的管理5.2 KMP算法任务：求一个字符串在另一个字符串第一次出现的位置算法思路：利用键盘输入两个字符串。一个设为主串、另一个为子串利用顺序串来实现并求出子串在主串中第一次出现的位 位置。运行结果：算法心得：学会 了利用顺序串来实现串模式匹配的典型算法、5.4 大型整数计算任务: 实现大整数（200位以内的整数）加减乘除运算。算法思路：由于整型数据存储位数有限。因此将整型的字符串进行存储，利用字符串的一个字符存储打整数的一位数值。然后根据四则运算规则进行相对应运算。同时保持进位。从而实现大整数精确的运算。运行结果：算法心得：进一步加深对串运算的理解和应用。7.2 线索二叉树的创建及遍历任务：根据二叉树的先序遍历序列建立一科中序二叉树，并以中遍序 列输出算法思路：1.按先序遍历序列输入每个节点的值，建立中序线索二叉树 2.按中序遍历序列遍历线索二叉树。并输出结果运行结果：算法心得：了解了二叉树的线索化的递归算法的基本思想7.4电文的编码的译码任务：从键盘接受一串电文字符，输出对应的Huffman编码。同时，能翻译由Huffman编码生成的代码串。输出相对应的电文字符串。算法思路：1.构造一棵Huffman树。 2.实现Huffman编码，并用Huffman编码生成的代码串进行译码。运行结果：算法心得：懂得了利用顺序表存储哈弗曼树，能通过调用不同的函数有选择的实现编码和译码的两个功能。7.5家族关系查询系统任务：建立家族关系数据库，实现对家族成员关系的相对查询。算法思想：使用数控结构有树状结构和队列。树状结构采用三叉链表实现，队列采用链式队列实现（1）建立家族关系并储存到文件中 （2）实现家族成员的添加 （3）可以查询家族成员的双亲，祖先，兄弟，孩子和后代等信息运行结果：算法心得：掌握设计并使用数据结构的有树状结构的队列巧妙的将家族信息转换为二叉树信息，利用队列创建三叉链表，存储家族关系。二、课程设计总结 经过几个星期的奋战，终于完成了课程设计，感觉又进一步了解了数据结构这门课程，各个知识点都加强了。也许个