数据结构与数据库课程设计指导书.doc

数据结构与数据库课程设计指导书一、课程设计的目的、要求和任务本课程设计通过设计完整的程序，使学生掌握数据结构的应用、算法的编写等基本方法。掌握数据库应用程序设计的步骤和方法。1.课程的目的（1）使学生进一步理解和掌握课堂上所学各种基本抽象数据类型的逻辑结构、存储结构和操作实现算法，以及它们在程序中的使用方法。（2）使学生掌握数据库设计的基本内容和设计方法，并培养学生进行规范化软件设计的能力。（3）使学生掌握使用各种计算机资料和有关参考资料，提高学生进行程序设计的基本能力；2.课程的基本要求与任务（1）巩固和加深对数据结构基本知识的理解，提高综合运用所学课程知识的能力。（2）培养学生自学参考书籍，查阅手册、图表和文献资料的能力。（3）通过实际课程设计，初步掌握简单软件的分析方法和设计方法。（4）了解与课程有关的工程技术规范，能正确解释和分析实验结果。（5）题目具有足够的工作量。（6）有能力的同学可以按照数据库的原理设计数据库表逻辑结构，通过数据结构的方法用C+/Java/C语言编写程序实现表中数据的插入、删除、查找等操作。二、课程设计的一般步骤选题与搜集资料： 分析与概要设计：根据搜集的资料，进行程序功能与数据结构分析，并选择合适的数据结构、并在此基础上进行实现程序功能的算法设计。程序设计：运用掌握C+/Java/C语言编写程序，实现程序的各个模块功能。调试与测试：调试程序，并记录测试情况。完成课程设计报告。验收与评分：指导教师对每个同学的开发的系统进行综合验收。三、课程设计报告的规范课程设计报告（3000字以上，数据结构题目1000字以上，数据库题目2000字以上）数据结构题目要求规范书写，应当包括如下8个部分：（1）问题描述：描述要求编程解决的问题。（2）基本要求：给出程序要达到的具体的要求。（3）算法思想：描述解决相应问题算法的设计思想。（4）模块划分：描述所设计程序的各个模块（即函数）功能。（5）数据结构：给出所使用的基本抽象数据类型,所定义的具体问题的数据类型,以及新定义的抽象数据类型。（6）源程序：给出所有源程序清单，要求程序有充分的注释语句，至少要注释每个函数参数的含义和函数返回值的含义。（7）测试数据：设计测试数据，或具体给出测试数据。要求测试数据能全面地测试所设计程序的功能。（8）测试情况：给出程序的测试情况，并分析运行结果（9）总结和体会数据库要求规范书写，应当包括如下6个部分：（1）系统概述（2）需求分析（3）概念结构设计（4）逻辑设计（5）物理设计（6）实现数据库（7）总结和体会四、成绩评定标准学生成绩以优、良、中、及格和不及格5个等级评定。（1）学生编写的实际软件和运行结果，占总成绩50%；（2）设计报告，占总成绩50%。五、数据库题目及要求一、题目按照学号的尾号选择以下系统之一:1、工资管理系统2、药品管理系统3、学生宿舍管理系统4、图书管理系统5、网上销售管理系统6、酒店管理系统7、物业管理系统8、人事管理系统9、学生成绩管理系统10、教室排课管理系统二、要求（一）数据库设计1、对系统进行需求分析。2、对系统进行概念结构设计。（画出局部和全局E_R图）3、对系统进行逻辑结构设计（转换成关系模型）4、对系统进行物理结构设计：（1）用T-SQL语句创建数据库（2）用T-SQL语句创建所有的表及设置主键（3）用T-SQL语句给需要设外键的表设置外键（4）用T-SQL语句给表加上check约束、UNIQUE约束、DEFAULT约束5、使用insert语句初始化数据库（给每个表至少插入5条记录）（二）任务描述需求分析、概念结构设计、逻辑结构设计物理设计、初始化数据（插入记录）流程控制语句与函数、视图、索引、游标数据查询存储过程、触发器、数据备份、课程设计报告的整理和编写六、数据结构课程设计参考题目类型一 线性表、栈、队列与递归算法设计1约瑟夫环问题描述约瑟夫（Joeph）问题的一种描述是：编号为1,2,n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。基本要求利用单向循环链表存储结构模拟此过程，按照出列的顺序印出各人的编号。测试数据m的初值为20；密码：3，1，7，2，4，8，4（正确的结果应为6，1，4，7，2，3，5）。实现提示程序运行后首先要求用户指定初始报数上限值，然后读取各人的密码。设n30。2、长整数运算问题描述设计一个程序实现两个任意长的整数求和运算。基本要求利用双项循环链表实现长整数的存储，每个结点含一个整型变量。任何整型变量的范围是-（215-1）（215-1）。输入和输出形式：按中国对于长整数的表示习惯，每四位一组，组间用逗号隔开。测试数据（1） 0；0；应输出“0”。（2） -2345,6789；-7654,3211；应输出“-1,0000,0000”。（3） -9999,9999；1,0000,0000,0000；应输出“9999,0000,0001”。（4） 1,0001,000；-1,0001,0001；应输出“0”。（5） 1,0001,0001；-1,0001,0000；应输出“1”。实现提示（1） 每个结点中可以存放的最大整数为215-1=32767，才能保证两数相加不会溢出。但若这样存，即相当于按32768进制数存，在十进制数与32768进制数之间的转换十分不方便。故可以在每个结点中仅存十进制数的4位，即不超过9999的非负整数，整个链表视为万进制数。（2） 可以利用头结点数据域的符号代表长整数的符号。用其绝对值表示元素结点数目。相加过程中不要破坏两个操作数链表。两操作数的头指针存于指针数组中是简化程序结构的一种方法。不能给长整数位数规定上限。选作内容修改上述程序，使它在整型量范围是-（2n-1）（2n-1）的计算机上都能有效地运行。其中，n是由程序读入的参量。输入数据的分组方法可以另行规定。3、多项式链式存储结构及其代数运算问题描述设计并建立一个链式存储分配系统来表示和操作多项式。为了避免对零和非零多项式进行不同的处理，使用带头结点的循环链表。为了充分利用多项式中不再使用的结点，维护一个可用空间表avail,把不再使用的多项式的结点链入其中。当需要一个新结点时，就查看这个单链表avail。如果表非空，那么可以使用它的一个结点。只有当该表为空时，才使用动态存储分配来创建新结点。基本要求设计多项式的存储结构，编写并测试下列函数：a) get_node和ret_node，从/向可用空间表申请和插入一个多项式结点。b) pread，读取一个多项式，并将其转换成循环存储表示。返回指向该多项式的头结点的指针。c) pwrite，输出多项式，采用能够清楚显示的形式。d) padd，计算d = a+b。不改变a和b。e) psub，计算d = a-b。不改变a和b。f) pmult，计算d = a*b。不改变a和b。g) eval，计算多项式在某点a的值，其中a是一个浮点型常量。返回结果为浮点数。h) perase，把存储表示为循环链表的多项式返还给可用空间表。实现提示为了进一步简化加法算法，把多项式的头结点的指数域设为-1。4、稀疏矩阵的完全链表表示及其运算问题描述稀疏矩阵的每个结点包含down，right，row，col和value五个域。用单独一个结点表示一个非零项，并将所有结点连接在一起，形成两个循环链表。使得第一个表即行表，把所有结点按照行序（同一行内按列序）用right域链接起来。使得第二个表即列表，把所有结点按照列序（同一列内按行序）用down链接起来。这两个表共用一个头结点。另外，增加一个包含矩阵维数的结点。稀疏矩阵的这种存储表示称为完全链表表式。实现一个完全链表系统进行稀疏矩阵运算，并分析下列操作函数的计算时间和额外存储空间的开销。（2）设计目的认识和掌握稀疏矩阵的完全链表表示；能够建立并运用这种存储结构(3) 基本要求建立一个用户友好、菜单式系统进行下列操作，并使用合当的测试数据测试该系统。读取一个稀疏矩阵建立其完全链表表示输出一个稀疏矩阵的内容删除一个稀疏矩阵两个稀疏矩阵相加两个稀疏矩阵相减两个稀疏矩阵相乘稀疏矩阵的转置（4）实现提示链表上的操作。5、实现简单数字图像处理问题描述一幅图像就是一个从位置集到颜色集的变换。考虑二维图像，位置集实际上就是一个矩阵，此时一幅图像实际上就是一个内容为颜色矩阵。如果颜色为0-255间的整数，表示该位置的灰度等级，0为黑色，255为白色，此时的图像称为灰度图。而图像的处理就是在该矩阵进行相关计算。一种常见的计算就是通过一点和周围8个点的信息共同决定该点的新值：如一点的新值为该点和周围8点颜色值之和的均值，这一操作可用下图表示。1/91/91/91/91/91/91/91/91/9图像平滑模板显然这样处理后，图像会变得平滑，因此称为平滑操作。显然将上述操作变为下图时，就成为锐化操作。-1-1-1-19-1-1-1-1图像锐化模板要求实现若干基本的图像处理操作。基本要求熟悉Windows下BMP文件的格式，能够实现其读写(只考虑灰度图像)。实现图像的平滑和锐化操作，其它处理操作选做。需用VC+作为语言。6、回文判断问题描述试写一个算法，判断依次读入的一个以为结束符的字母序列，是否为形如序列1&序列2模式的字符序列。其中序列1和序列2中都不含字符&，且序列2是序列1的逆序列。例如，a+b&b+a是属该模式的字符序列，而+&则不是。实现提示首先，序列1进栈，然后序列1出栈并与序列2比较。测试数据由学生依据软件工程的测试技术自己确定。注意测试边界数据，如序列1和序列2均为空串。7、商品货架管理问题描述商品货架可以看成一个栈，栈顶商品的生产日期最早，栈底商品的生产日期最近。上货时，需要倒货架，以保证生产日期较近的商品在较下的位置。基本要求针对一种特定商品，实现上述管理过程。实现提示用栈模拟货架和周转空间。测试数据由学生依据软件工程的测试技术自己确定。注意测试边界数据，如空栈。8、停车场管理问题描述设停车场内只有一个可停放n辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车停放在车场的最北端），若车场内已停满n辆汽车，则后来的汽车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车即可开入；当停车场内某辆车要离开时，在它之后开入的车辆必须先退出车场为它让路，待该辆车开出大门外，其它车辆再按原次序进入车场，每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用。试为停车场编制按上述要求进行管理的模拟程序。测试数据设n=2,输入数据为：（A，1，5），（A，2，10），（D，1，15），（A，3， 20）， （A，4，25），（A，5，30），（D，2，35），（D，4，40），（E，0，0）。每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码及到达或离去的时刻，其中，A表示到达；D表示离去，E表示输入结束。基本要求以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟管理。每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码及到达或离去的时刻，对每一组输入数据进行操作后的输出数据为：若是车辆到达，则输出汽车在停车场内或便道上的停车位置；若是车离去；则输出汽车在停车场内停留的时间和应交纳的费用（在便道上停留的时间不收费）。栈以顺序结构实现，队列以链表实现。实现提示需另设一个栈，临时停放为给要离去的汽车让路而从停车场退出来的汽车，也用顺序存储结构实现。输入数据按到达或离去的时刻有序。栈中每个元素表示一辆汽车，包含两个数据项：汽车的牌照号码和进入停车场的时刻。9、电梯运行仿真程序问题描述办公大楼有若干层（例如，十层），每层有电梯，同时有步行楼梯；全楼有若干部（例如，不多于10部）电梯同时供使用，电梯容量为24人，速度每上下一层需5秒，在某一层停下至少15秒。其运行状态可分：向上、向下、停止，当前乘客数，当前所在层数。它设有一个“按钮数组”，例如第五层的按钮按下，意味着有乘客在第5层到达目标层，等等。在楼的每一层，有电梯数，有按钮表示有人等待向上或向下，由若干人在等待，有若干电梯在本层停下，等等。在大楼中（包括进出）的总人数不超过500 人，每个人站在电梯前有个目标层，他有一个最大的忍受等待时间，因为他可以选择电梯或是步行走楼梯，等等。还有下面若干假设：在每个时间段要进大楼的人数在0199 之间随机取值；用电梯的每个人的目标层在110 之间取值；一个人在进电梯或改走楼梯之前的等待时间在180360 秒范围内随机发生；一个人到达目标层后第二次再乘电梯中间的工作时间在4006600 秒间随机取值。基本要求编写一个程序，模拟办公大楼中全部电梯的工作过程。这个仿真程序可以用来监测系统运行情况，改善大楼管理，它也可以看成是一种游戏程序。屏幕显示的布局设计类型二 串及其应用1、文学研究助手问题描述文学研究人员需要统计某篇英文小说中某些形容词的出现次数和位置。试写一个实现这一目标的文字统计系统，称为“文学研究助手”。基本要求英文小说存于一个文本文件中。待统计的词汇集合要一次输入完毕，即统计工作必须在程序的一次运行之后就全部完成。程序的输出结果是每个词的出现次数和出现位置所在行的行号，格式自行设计。测试数据以你的源程序模拟英文小说，程序语言保留字集作为待统计的词汇集。实现提示设小说中的词汇一律不跨行。这样，每读入一行，就统计每个词在这行中的出现次数。出现位置所在行的行号可以用链表存储。若某行中出现了不止一次，不必存多个相同的行号。类型三 树、图及其应用1、二叉树的建立与遍历问题描述建立一棵二叉树，并对其进行遍历（先序、中序、后序），打印输出遍历结果。基本要求 从键盘接受输入（先序），以二叉链表作为存储结构，建立二叉树（以先序来建立），并采用递归算法对其进行遍历（先序、中序、后序），将遍历结果打印输出。测试数据ABCDEGF（其中表示空格字符）则输出结果为：先序：ABCDEGF中序：CBEGDFA后序：CGBFDBA选作内容采用非递归算法实现二叉树遍历。2、打印二叉树结构问题描述按凹入表形式横向打印二叉树结构，即二叉树的根在屏幕的最左边，二叉树的左子树在屏幕的下边，二叉树的右子树在屏幕的上边。测试数据由学生依据软件工程的测试技术自己确定。注意测试边界数据，如空二叉树。3、打印树结构问题描述按凹入表形式打印树形结构。测试数据由学生依据软件工程的测试技术自己确定。注意测试边界数据，如空树。实现提示（1）利用树的先根遍历方法；（2）利用结点的深度控制横向位置。 4、图遍历的演示问题描述很多涉及图上操作的算法都是以图的遍历操作为基础的。试写一个程序，演示无向图的遍历操作。基本要求以邻接表为存储结构，实现连通无向图的深度优先和广度优先遍历。以用户指定的结点为起点，分别输出每种遍历下的结点访问序列和相应生成树的边集。测试数据由学生依据软件工程的测试技术自己确定。注意测试边界数据，如单个结点。实现提示设图的结点不超过30个，每个结点用一个编号表示（如果一个图有n个结点，则它们的编号分别为1,2,n）。通过输入图的全部边输入一个图，每个边为一个数对，可以对边的输入顺序作出某种限制。注意，生成树的边是有向边，端点顺序不能颠倒。5、学生选课系统 问题描述大学里实行学分制。每门课都有一定的学分。每个学生均需要修满规定数量的课程才能毕业。其中有些课程可以直接修读，有些课程需要一定的基础知识，必须在选了其他一些课程的基础上才能修读。例如，数据结构必须在选修了程序设计基础之后才能选修。我们称程序设计基础是数据结构的“先修课”。假定每门课的直接先修课至多只有一门，两门课可能存在相同的先修课。例如： 课程号 先修课号 学分1 0 12 1 13 2 34 0 35 2 4上例中，1是2的先修课，即如果要选修2，则1必定被选。基本要求学生不可能学完大学里开设的所有课程，因此每个学生必须在入学时选定自己要学的课程。每个学生所修的学分数的下限是给定的。现在编写一个“学生选课系统”，任意给定一种课程体系（总课程数，课程之间的修读先后制约关系，学生毕业要求修的课程学分数），该系统能帮助学生找出一种选课方案，使得他所选课程数目最少，并获得毕业所需学分，并且必须满足先修课程优先的原则。具体功能如下：1.将课程体系存放为课程体系文件 CourseHierarchy.txt ； 2.将课程体系文件 CourseHierarchy.txt 转换左孩子右兄弟二叉树表示； 3.在此基础上对二叉树进行先序、中序、后序遍历。 4. 给出选课方案。6、设计一个哈夫曼码的编/译码系统基本要求该系统应具有以下功能：（1） I：初始化（Initialization）。从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件hfmTree中。（2） E：编码（Encoding）。利用已建好的哈夫曼树（如不在内存，则从文件hfmTree中读入），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。（3） D：译码（Decoding）。利用已建好的哈夫曼树将文件CodeFile中的代码进行译码，结果存入文件TextFile中。（4） P：打印代码文件（Print）。将文件CodeFile以紧凑格式显示在终端上，每行50个代码。同时将此字符形式的编码文件写入文件CodePrin中。（5） T：打印哈夫曼树（Tree printing）。将已在中的哈夫曼树以直观的方式（树或凹入表形式）显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrint中。实现提示（1） 编码结果以文本方式存储在文件CodeFile中。（2） 用户界面可以设计为“菜单”方式：显示上述功能符号，再加上“Q”，表示退出运行Quit。请用户键入一个选择功能符。此功能执行完毕后再显示此菜单，直至某次用户选择了“Q”为止。（3） 在程序的一次执行过程中，第一次执行I，D或C命令之后，哈夫曼树已经在内存了，不必再读入。每次执行中不一定执行I命令，因为文件hfmTree可能早已建好。测试数据（1）利用下面这道题中的数据调试程序。某系统在通信联络中只可能出现八种字符，其概率分别为0.25，0.29，0.07，0.08，0.14，0.23，0.03，0.11，试设计哈夫曼编码。（2）用下表给出的字符集和频度的实际统计数据建立哈夫曼树，并实现以下报文的编码和译码：“THIS PROGRAM IS MY FAVORITE”。7、校园导游咨询系统问题描述设计一个校园导游程序， 为来访的客人提供信息查询服务。基本要求（1）设计学校的校园平面图，所含景点不少于10个，以图中顶点表示校内各景点，存放景点名称、代号、简介等信息，以边表示路径，存放路径长度等相关信息。（2）为来访客人提供图中任意景点相关信息的查询；（3）为来访客人提供从校门口到图中任意景点的问路查询；8、推销员问题：问题描述有一个推销员要到N（N0）个城市去推销产品，他从某个城市出发，经历每个城市，且每个城市只能去一次，然后回到初始城市，以距离作为代价，他希望找出一个最佳路径。这N个城市相互都有道路可通，但距离各不相同，城市个数和各个城市的相通距离可由学生自己设定。基本要求（1）可以输入城市个数（不少于10个）、输入城市信息和城市之间的距离（为整数）；（2）按照输入出发城市，根据城市的距离最短给出路径选择。（3）界面要求：有合理的提示和人机交互。9、全国交通咨询模拟问题描述处于不同目的的旅客对交通工具有不同的要求。例如，因公出差的旅客希望在旅途中的时间尽可能的短，出门旅游的游客则期望旅费尽可能省，而老年旅客则要求中转次数最少。编制一个全国城市间的交通咨询程序，为旅客提供最优决策的交通咨询。 基本要求 （1）提供对城市信息进行编辑（如：添加或删除）的功能；（2）城市之间有两种交通工具：火车或飞机，提供对全国城市交通图和列车时刻表及飞机航班表进行编辑的功能。（信息的输入方式可以是文件输入和键盘输入两种方式） （3）提供两种最优决策：最快到达和最省钱到达。（选作：旅途中转次数最少的最优决策）（4）旅途中耗费的总时间应该包括中转站的等候时间。 （5）咨询以用户和计算机的对话方式进行。a）由用户输入起始站、终点站、最优决策原则和交通工具；b）输出信息：最快需要多长时间才能到达或者最少需要多少旅费才能到达，并详细说明依次于何时乘坐哪一趟列车或哪一次班机到何地。10、关键路径问题问题描述设计一个程序求出完成整项工程至少需要多少时间以及整项工程中的关键活动。基本要求（1）对一个描述工程的AOE网，应判断其是否能够顺利进行。（2）若该工程能顺利进行，输出完成整项工程至少需要多少时间，以及每一个关键活动所依附的两个顶点、最早发生时间、最迟发生时间。类型四 查找和排序1、二叉排序树问题描述从键盘读入一组数据，建立二叉排序树并对其进行查找、遍历、格式化打印等有关操作。基本要求建立二叉排序树并对其进行查找，包括成功和不成功两种情况，并给出查找长度。测试数据由学生依据软件工程的测试技术自己确定。注意测试边界数据。选作内容实现二叉排序树的插入、删除操作。2、内部排序算法比较问题描述各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶，或大概执行时间。试通过随机的数据比较各算法的关键字比较次数和关键字移动次数，以取得直观感受。基本要求（1）对以下10种常用的内部排序算法进行比较：直接插入排序；折半折入排序；二路插入排序；希尔排序；起泡排序；快速排序；简单选