资源描述
课程设计报告数据结构学院名称专业年级学生姓名学号任课教师二一五年三月吉林财经大学管理科学与信息工程学院数据结构课程设计期末成绩评分表学生姓名课程设计题目评价指标平时实验实验报告程序质量现场答辩专业班级学 号数据库管理系统大整数计算器电文的编码和译码校园导航评价要点分值评分（）保证出勤；（）认真调试程序； （）不做与课程设计无关的工作；（）虚心与同学讨论问题（）文字表达流畅； （）论文格式符合规范要求； （）论文中有检测数据；（）篇幅符合要求； （）书写格式规范（）程序符合模块化设计思想； （）代码中注释清晰； （）程序整体装配合理； （）利用外部文件存储数据（）自述程序功能（）程序功能演示（）回答教师问题（）临时突发问题解决能力总分学术道德本项指标实行一票否决制：凡经认定为抄袭、雷同，论文即按不及格处理评价等级：教师签名：年月日第一题课题内容和要求课题内容当今计算机技术飞速发展，信息管理领域日益扩大，数据库已被广泛应用于各个领域，它用科学的方法管理和处理数据，给人们的生活带来了巨大变化。用户建立自己的数据库，更能提高管理工作的效率，综合运用数据结构和语言知识，建立一个数据库管理系统，能够让用户自己定义、创建和控制数据库。课题要求设计一个数据库管理系统，用户可以使用特定的命令自行定义和创建数据库，能够对数据库实现插入（追加）、浏览、浏览定位、按条件修改、按条件排序、删除和全部删除等功能，并能保存数据库信息到指定文件以及打开并使用已存在的数据库文件，但库结构定义后不允许修改 。课题设计思想数据库管理系统对数据实行追加、浏览、按条件删除等命令都是按次序来进行的，由此可以判断我们可以用单链表的数据结构来设计本套数据库管理系统。使用的单链表的数据结构为：定义单链表的节点类型存放单链表的元素值* 指向后继节点;执行各种命令时都可以将特定的指针定位到相应的位置，可以对相应位置的字段进行相应的操作，例如追加字段就是将指针定位到最后一个字段，删除字段就是将指针定位到特定字段内容处等等。问题分析主要思想首先定义一个单链表的结构用来存储数据库结构的每一条字段，然后再定义一个结构体数组以便在调用操作函数时用这个结构体数组来进行其他灵活操作。接下来编写主函数，在主函数的函数体中，首先调用（）函数，以便展示数据库管理系统的各种操作命令，然后出现让用户输入命令的提示符。用户输入命令后可以进入各个编写的函数模块，对自己的数据库系统进行操作。当输入命令时退出数据库管理系统。数据结构的伪代码为：*定义数据库的类型*存储输入的数据 * 存储输入的数据类型*;数据库的建立和存储数据库管理系统由数据库的结构和数据库的内容组成。由于呈现在我们眼前的数据库的数据是类似一个表的形式，所以我们可以定义一个字符型二维数组来存储。这样，二维数组的第行存储数据库管理系统的结构，即数据库的表头。其中，二维数组自动存储字段名为“编号”的字符。时间复杂度为： （）数据库数据的添加当输入“”命令时，主函数调用添加函数，此时，需要在二维数组的最后一行进行存储和各种操作，程序执行时显示每一行对应的表头，后面就可以输入可添加的数据。每输入一行，编号值自动加。时间复杂度为：( ）数据库数据的查找先用命令定位到指定编号的字段，再用命令来展示隶属该编号下所有字段的值。时间复杂度为：( ）数据库信息筛选信息筛选主要靠命令，执行该命令时， 将命令划分成部分，分别是、和后面对应的字段。设计要求中有很多命令的执行都是同一种结构，即“命令字段名“字段内容”。所以首先要对命令进行筛选，看执行的是哪种命令，然后看输入的命令符不符合命令的格式，所以就划分了后面两个部分。再进行对应的筛选，先找到对应的字段名，再在对应的字段名下的字段进行筛选，如果遇到符合条件的字段则打印出来。时间复杂度为： （ * ）数据库信息删除执行命令的过程和信息筛选的差不多，只是最后遇到符合条件的字段不是将它打印出来，而是直接删除掉。时间复杂度为： （） * ）；数据库信息的修改执行命令的过程和删除的差不多，但是最后遇到符合条件的字段时略有不同，当遇到符合条件的字段时，先进入该字段的存储，分别修改对应的字段名下字段的值，修改完毕后，打印修改成功。时间复杂度为： （） * ）；数据库信息的排序该命令运行时，也要将命令行字符划分为部分，分别是、字段名和 (或）。先判断输入的命令，然后寻找对应的字段名，如果没有对应的字段名，则打印没有对应字段名。接下来再进行判断是要进行升序操作还是降序操作，最后再进行排序。时间复杂度为： （ * ）数据库文件的打开和关闭运用文件的相关函数将创建数据库文件。时间复杂度为： （）概要设计伪代码描述如下：1) 构建一个二维数组 来存储数据库的数量：2) 屏幕上显示数据库的操作；3) 手动生成数据库的结构；4) 建立数据库的节点结构，用于存储数据库的节点；5) 建立完成后实现对数据库的各种操作；本程序包含以下几个函数：1. ( ) *把数字转换为字符数组 *2.()* 输出执行操作的各项命令，帮助用户正确使用各项命令*3.( * *)* 建立数据库的结构 *4.( * * , )*打开数据库文件并且将文件中的数据存入结构体二维数组中 *5.( *, *)* 追加记录 *6.(*)* 浏览写进数组中的数据 *7. ( * *)*浏览指定位置的数据 *8.(*)* 删除函数 *9.(*)*筛选特定字段的函数 *10.(*)*修改字段的函数 *11.( *)*排序函数 *12.( * *)*判断是升序还是降序的函数 *13.(*)*关闭函数 *流程图开始复制“编号”字段进入 database数组输入字段名是 $N输入字段的Y类型打印“您输入的Y字段有误，请重新输入”打印数据库库结构Int ？double ？N没有构建成功字段Char？结束图 数据库的创建和存储流程图开始Max=第一个字符串的长度I行数NYI行数N结束NI+YI+Ni 列数YimaxNMax=原字符串长YK=该位置字符串长度Max=该字符串长KmaxY打印空格图 浏览数据库内容流程图开始行的值大于 1按表头添加数据库么？结构值将最后一列的编号值转化为整型按表头添加数据库结构值结束图 数据库内容添加流程图开始输入定位编号输出表头输出编号所在一行的库内容结束图 浏览定位内容流程图开始输入命令及所要删除的字段内容在库结构中寻找删除的字段名在字段名中寻找要删除的字段名称结束图 删除字段函数流程图开始输入命令及所要定位的字段内容在库结构中寻找定位的字段名在字段名中寻找筛选出来的字段名称输出筛选出来的字段结束图筛选定位函数执行流程图开始输入命令及所要修改的字段内容在库结构中寻找修改的字段名在字段名中寻找字段名称修改字段，并输出结束图修改字段函数执行流程图伪代码描述:()数据库 ;( )：$、$；“” ;()显示全部信息( )添加或追加信息( ) )“”显示当前行信(字段名 字段内容 )定位(字段名 字段内容 )删除行()全部删除(字段名 字段内容 )更改信息(字段名 降序:字段名)排序()帮助测试和分析1. 帮助界面：2. 当使用函数时会出现如下界面： ：3. 使用命令追加数据时，会出现如下界面：4. 使用命令浏览数据库信息时，会出现如下界面：5.）使用命令进行定位，并使用命令浏览定位信息时会出现如下界面：6. 使用 命令，按条件定位数据。界面如下：7. 使用命令 , 按条件删除数据时，会出现如下界面，再用命令显示结果：8.使用 命令 , 按字段进行排序时会出现如下界面，注意默认为升序排序：9. 降序排序界面：10. 使用 命令，按条件修改数据时，会出现如下界面，按提示修改即可：11.使用命令删除数据库中的全部数据时会出现如下界面：12. 使用命令关闭数据库：13. 使用命令退出系统。界面如下：出现问题程序运行时，添加命令当编号大于时，会出现重复编号的情况；删除命令时，当出现两个相同的字段时，只会删除第一个字段，而不会删除第二个字段。第二题课题内容设计一个计算器，范围是位以内的整数。课题要求设计程序实现两个大整数的四则运算，输出这两个大整数的和、差、积、商及余数课题设计思想由于计算的整数范围太大，有些整数计算机无法表示，故我们可以使用字符型数组存储计算后得到的结果。整数计算的过程和对顺序串操作的过程有一些类似，所以可以用顺序串的数据结构，即： ; ;来编写相关程序。问题分析：本题是进行位以内的整数的相关计算，由于数值太大，所以可以创建三个数组，分别用来存储第一个整数，第二个整数和两个整数运算后得出的结果。有些整数太大，计算机计算出结果后并不能显示，所以我们可以将输入的一个数的每一位数当成字符存储起来，两个整数位位进行运算，这样就可以显得方便许多。所用数据结构的伪代码为：加法运算程序本程序运行时，进行两数的相加，由于整数太大，所以我们可以位位进行相加，加出结果后，可以将得出的进位，即除得到的数加到下一对数的运算。需要注意的是，再程序的开始对输入的两个整数进行长度的比较，取的是长度较小的数的长度，这样方便运算，可以让输入的两个数在做完同等长度的数值运算再做剩余的位数的运算，这样保证了运算的简便性，不用纠结在运算时取多大的长度。时间复杂度为： （）；减法运算程序程序运行时同加法运算的过程差不多，只不过从位位加变成位位减，这时候判断大小的函数派上用场，可以使用它来判断得出的结果是正的还是负的。时间复杂度为： （）乘法运算程序运算程序的过程同加减法差不多，按位加变成按位乘。时间复杂度为： （ * ）；除法运算程序除法运算的过程略有不同，从最大位开始，每一位和除数做运算，做完运算得到的余数和下一位的数连接起来，再做运算，直到运算到被除数的最后一位为为止。时间复杂度为 ();程序包含的函数如以下：1.( * *) 判断输入的数中有没有小数2.( *) 两个整数长度比较的函数3.( *,*,*, *) 除法运算函数4.( *,*,*) 乘法运算函数5.( *,*,*) 减法运算函数6.(*)加法运算函数流程图开始输入第一个整数输入第二个整数逆序复制两个整数进两个不同的数组按位逆序相加，并只存储个位进位值加到下一组值中逆序存储相加后得到的和。结束图加法算法流程图开始输入第一个整数输入第二个整数逆序复制两个整数进两个不同的数组按位逆序相减，若有借位，下一组数值相减得到的差再减1逆序存储相减后得到的差。结束图减法算法流程图开始输入第一个整数输入第二个整数逆序复制两个整数进两个不同的数组按位逆序相乘，只存储个位，进位加到下一组数值的积中逆序存储相乘后得到的结果结束图乘法算法流程图开始输入第一个整数输入第二个整数第一个整数的每位和第二个整数做除法每位存储得到的余数和下一位连接上，再做除法存储得到的结果结束图除法算法流程图伪代码加法加数与被加数字符串逆序存储、于求较长的字符串的长度 逆序存储于返回减法减数与被减数字符串逆序存储于判断减数与被减数谁大被减数小于减数的对应字符相减，存于 的对应字符相减，存于 返回乘法乘数与被乘数字符串、结果为使结果为 乘数的长度进位被乘数的长度*获取最后一个进位去掉多余的逆序存储相应结果左移调用加法函数前后相加返回结果除法除数与被除数字符串 逆序存储每一位数使值为空被除数长度接上被除数的一位数,改变当前余数调用减法函数连减试商记录每一位得到的商值使的值为空，去掉多余的返回结果分析和测试第三题课题内容从键盘接收一串电文字符，输出对应的编码。同时， 能翻译由编码生成的代码串，输出对应的电文字符串。课题要求构造一棵树。实现编码，并用编码生成的代码串进行译码。程序中字符和权值是可变的，实现程序的灵活性。设计思想题目明显意见，我们可以使用哈夫曼的相关函数和变量来对题目的相关要求进行实现。哈夫曼树结点的结构; 数据用字符表示;权值;双亲;左孩子;右孩子;哈夫曼编码的存储结构存放编码位串;编码的起始位置;问题分析本题可利用哈夫曼树的相关函数来完成此题的相关要求。建立哈夫曼树该算法执行的时间复杂度为：（）哈夫曼编码该算法执行的时间复杂度为：（）哈夫曼译码：该算法执行的时间复杂度为：（）；程序实现的相关函数如下：( *) 建立哈夫曼树( )哈夫曼编码( )哈夫曼译码流程图图建立哈夫曼树算法流程图图 哈夫曼编码流程图译码过程是编码的逆过程，算法流程图此处省略。伪代码测试和分析1. 建立哈夫曼树：2. 哈夫曼编码：3. 哈夫曼译码：第四题课题内容当我们参观某校园时，就会遇到这样一个问题：从当前所处的位置出发去校园另外某个位置，要走什么样的路线距离最近（或最省时）？本课程设计实例在给出校园各主要建筑的名称信息及有路线连通的建筑之间的距离（或行进时间）的基础上，利用校园导航系统计算出给定的起点到终点之间距离最近（或进行时间最短）的行进路线。课题要求从地图文件中读取校园主要建筑信息及建筑间的距离（或行进时间）信息。计算给出定的起点到终点之间距离最近（或行进时间最短）的行进路线。输出该路线（包含路过哪些建筑）及其总距离（或总行进时间）。若输入错误，则给出提示信息。问题分析本题可利用狄克斯特拉算法算法的相关函数来完成此题的相关要求。读入校园网要求执行时需要建立个文档文件，并置文件属性为可读，并将文件中的字符读入到文件中。执行该算法的时间复杂度为：（）最短路径查找迪克斯特拉算法的执行。该算法的时间复杂度为：（ )程序实现的相关函数如下：( *)初始化有向网 ,读入校园地图文件( *, ) 狄克斯特拉算法的执行流程图开始读入校园地图相关信息文件将相关信息复制入新建数组结束图 校园网读入新建数组流程图图 狄克斯特拉算法流程图伪代码;* 图的顶点个数*; *顶点信息文字* 边信息* ;* 保存最短路径的结构体* 最短路径长度*前一顶点*;“”读入网的顶点个数构造顶点向量初始化邻接矩阵算法在文件中查找路径测试和分析经过测试得知该程序查找正确。总程序、问题描述将四个题目放在一个大程序中完成、设计要求程序中要有菜单选择进入各个子功能，最好做到两级以上的菜单。能够利用文件处理的一定要用文件进行数据的存储。、解题分析设计界面，并调用各个功能模块的主调用函数。、数据结构描述():();:();:();:();:();、算法流程图描述、算法复杂度分析主函数的时间复杂度为() 。、测试数据（）主界面：（）：选择功能界面：附录程序清单总程序();();();();();(*请选择要进行的操作* );(*:程序功能选择* );(*:退出* );()();()( 程序功能输入有误，请再输入一次。);();()(*请选择要进行的功能* );(*:数据库管理系统* );(*:大整数计算器* );(*:电文的译码和编码 * );(*:校园导航* );();()( 您的输入有误，请重新输入！);();():();:();:();:();()();();第一题* 文件相关函数*; * 存储当前指向的记录的编号值 * 定义数据库的类型 * 存储输入的数据* 存储输入的数据类型*;*定义结构体型的二维数组以便用来与文件进行交互*;* 分别存储文件的每一行，再复制给数组;* 分别接收文件的每一个字符*;* 数组的行数，也就是数据库中的记录数目;*; * 记录的列数 *;* 自动生成的编号转换为相对应的字符串*;* 反向存储数组*;( )* 把数字转换为字符数组*;()* 把数转化为相应的字符串并存放到数组中*() ;* （） 显示帮助界面函数输出 命令一览表 ，帮助用户正确使用命令。*()(* 命令一览表 *);(* , 创建数据库命令语法格式*);(* , 追加字段的命令 *);(* , 浏览数据库中所有字段命令 *);(* 命令语法格式 ( )定位浏览字段 ,用浏览定位的字段 *);(* , 条件定位命令语法格式字段名 字段内容 *);(* , 按条件删除命令语法格式字段名 字段内容 *);(* , 全部删除命令 *);(* , 按条件修改命令 字段名 字段内容 *);(* , 按条件排序命令 升序 :字段名 降序 :字段名 *);(* , 打开帮助文档命令 *);(* ，打开已创建的数据库文件 文件名 ( )*);(* , 关闭已打开的数据库文件 *);(* , 退出数据库管理系统 *);* （）创建数据库函数模块首先为数据库分配内存，输入第个字段为 编号 ，以后每追加一条数据，都自动对其进行编号，方便之后进行定位， 、删除等操作。编写一个无限循环，引导用户定义字段，包括输入字段名和定义字段类型，直至输入 $结束，跳出循环。字段类型可为： ，。用户每输入一个字段类型，程序调转执行到，也是一个无限循环，判断字段类型是否规范。规范的字段类型包括：，。所有字段定义结束后，输出定义的全部字段及其类型，方便用户使用。*( * *)*建立数据库类型* 编号;* 建立库结构时候自动建立编号字段;( *)();();* 建立编号字段*(,);* 建立库结构 *(. 请输入字段的名称以 $结束输入 ,*);(.);();(,$)( 数据库没有构建成功！);(. 请输入字段的类型 ( , ) ,*);();()(,)(,)(,)* 判断结构类型*;( 您输入的类型非法！请重新输入);(. 请输入字段的类型 ( , ) ,*);();()* 循环输入库结构类型以 $ 结束输入*(); ;*( *)();(*);(*);*;(. 请输入字段的名称以 $结束输入 ,*);(.);();(,$) ;(. 请输入字段的类型 ( , ) ,*);(); * 如果输入的类型不匹配则跳转到*();* 输入结束时输出数据库字段和类型* （） 打开数据库函数模块以读写模式打开已经存在的文件，将其中数据读到数组中，然后将获得的数据按行存入二维数组中，。其中，以空格为字段值的分隔符，以回车为行的分隔符。*(*,)* 打开数据库文件并且将文件中的数据存入结构体二维数组中*;(,();* 开始字符型数组初始化*(,();* 开始字符型数组初始化*(,();* 开始字符型数组初始化*(,);*打开相应的数据库文件*();*获得文件中的每一个字符一直到文件末尾*()*把获取的字符按行存入到数组里*( )*如果遇到空格就把复制到的一个单元中*(*);*;(,();* 把复制到的一行后初始化数组*;()* 如果遇见回车则结束的一行，开始存储下一行*;*; *列恢复 *;*把在数据库文件中读出的一行存放在数组中*;();* 获取文件的下一个字符*;*每存完一行行数自加* （） 追加数据函数模块首先为追加的数据自动生成编号：若数据库中已存在记录，则追加的数据标号为其上一个数据的编号。因此，先取出上一条数据的编号（字符型） ，将其转化成型，然后，即为追加的数据的编号，再将其转化成字符型，存入数据库。若数据库中没有数据，则追加数据编号为，存入数据库。其次，编辑循环，引导用户输入对应字段的数据信息，将其存入数据库，追加数据操作完成。 *(*,*)*追加记录 *;(,()* 初始化数组的值*(*) * 自动生成编号的值*(*);()* 将数据库最后一条记录的编号值转化为整型*(*)*;*; *追加记录的编号为其最后一条记录的编号加*();();* 将其编号的值转化为相对应的字符串*;(,();();();* 因为转化的字符串为该编号的逆序所以将其反向存贮*;(*);(*) * 分别最加各条记录的值*( 请输入：);(*);*;*追加成功后行数自加*( 该数据添加成功！);* （） 浏览数据库函数模块此模块功能为：格式输出数据库中数据，起到浏览数据功能。首先编写嵌套循环，记录每个字段值中最长的字段的长度。然后，再用嵌套循环输出数据库中数据，按照最长的字段格式输出，不足的字段，以空格补充，使得浏览输出的数据整齐清晰。*( * *)*浏览写进数组中的数据*;(,();(*) * 记录每个字段值中最大的程度以便调整输出的格式 * ()是输出的格式的标准 输出的星号的个数是字段中含字符个数最多的字段的字符个数值(*)* 输出中所有的字段内容*(*)();()( );();();* （） 浏览定位函数模块浏览定位的数据，为浏览定位编号。浏览数据时，首先记录最长字段的长度，以便调整输出格式。然后，以调整好的格式输出第一行，也就是输出数据库的字段名。最后，格式输出指定的编号为 的一行数据。 *(*)*函数*;(*)*记录每个字段值中最大的程度以便调整输出的格式 * ();();(*)*输出第一行，也就是数据库类型行*();()( );();();(*)*格式化输出所指的字段值*();()( );();();* （） 按条件删除函数模块删除的命令格式为：字段名 字段内容 ，先将命令第二个字符串存入，对比是否为，若不是，提示命令错误；若为，再用循环将 字段名 字段内容 存入数组，遍历该数组，通过比对 ，取出 号前面的字段名，存入数组。类似的，比对双引号 ，取出两个双引号之间的字符串，即为字段内容，存入数组，若没有 ，同样提示命令错误。在数据库中字段中匹配，若不存在，提示数据库没有该字段；若存在，定位这个字段，将这个字段下所有的值与对比。若存在，依次将它后面的数据依次前移，覆盖掉需要删除的字段，实现删除功能。*(*)*删除函数*;* 接收输入的命令为接收所要删除的字段的名称和内容数组为接收要查找的字段，为要查找字段的内容 *;(); * 接收输入的 *(); * 接受输入的后面的字符串*();(); ;(,();(,();(,();() *获取要查找的字段名称 *(); (, )( 您输入的命令有语法错误！);()()* 遇见第一个双引号记录下标*;();* 遇见最后一个双引号记录下标并退出;*()*如果没有遇见一对引号说明输入的语法错误*( 您输入的命令语法有错误！);()*把双引号之间的字符存入到中*;(*) * 在中匹配，如果匹配成功记录其列坐标*();()( 数据库没有该字段的值!);(*) * 如果匹配到该行，则变量定位到该行*();()( 数据库中没有符合该条件的字段！);(*)* 删除其匹配成功的字段并删除*(*)();* 删除该行后除编号字段，后面所有字段所对应数据向上移动一行*;*删除后总行数减*( 删除成功！ );: ;* （） 按条件定位模块的命令格式为字段名 字段内容 先用数组接受 字符串，然后进行判断数组中接受的字符串是否为 ，如果不是，输出语法错误，用命令跳到函数末尾；如果是 则用 接受输入的条件字符串。然后用接受中 号以前的字符，如果没有 则输出语法错误，跳到函数末尾。用数组接受双引号之间的字符，如果没有出现双引号则输出语法错误，用命令跳到函数末尾，否则在数组中符合的那一列中匹配和数组中内容相符的那一行。然后用进行浏览，然后再用命令查找符合条件的下一行，再用进行浏览。如果中没有符合条件的字段，则输出 数据库没有符合该条件的字段。 *(*)* 筛选特定字段的函数*;(); * 存放字符串 *(); * 存放后面的字符串*();*测量数组的长度*();*测量数组的长度* ;(,();* 初始化数组 *(,();* 初始化字段数组*(,();* 初始化要匹配的内容数组()*();*末尾赋予结束标识(, )* 如果没有与* 匹配成功则说明命令语法有错误*( 您输入的命令有语法错误！);* 跳到指向的位置，也就是函数末尾*()()* 找到第一个指向其下标*;*说明已经找到第一个*()*如果找到了第二个 并且则指向第二个的下标*;*与都找到后跳出循环体*()*如果或者没有全部找到则说明命令有错误*( 您输入的命令语法有错误！);* 跳到指定的位置，也就是函数末尾*()* 将数组中与之间的字符赋给数组*;* 数组末尾加上结束标识*(*)()*如果要查找的字段在数组中存在的话则指向该字段;()* 如果说明在数据库中不存在要查找的字段*( 数据库没有该字段的值!);*跳到指向的位置，也就是函数末尾*(*) * 记录每个字段值中最大的程度以便调整输出的格式 * ();();(*) * 输出第一行，也就是数据库类型行*();()( );();(*) * 在匹配成功的字段中查找满足条件的内容的行的位置*()* 如果找到则等于该行所在的位置*(*) * 格式化输出所指的字段值*();()( );();: ;* （） 按条件修改数据函数模块用相同的方法， 取出需要修改的字段名和字段值。 将得到的字段名与数据库里的字段名对比，若不一致， 则显示命令错误。 之后将需要修改的数据的值与数据库中该字段的所有数据对比，若存在，提示用户根据字段依次输入新的数据；若不存在，显示没有符合该条件的字段。*(*)* 修改字段的函数*;(); * 存放字符串 *(); * 存放后面的字符串*();*测量数组的长度*();*测量数组的长度* ;*将数组末尾追加一个空格以便匹配;*追加空格后末尾打上结束标识* *(,();* 初始化数组 *(,();* 初始化字段数组*(,();* 初始化要匹配的内
展开阅读全文