数据结构实验指导与课程设计教程.docx

《数据结构实验指导与课程设计教程.docx》由会员分享，可在线阅读，更多相关《数据结构实验指导与课程设计教程.docx（80页珍藏版）》请在三一办公上搜索。

1、数据结构实验指导与课程设计教程第三编 课程设计 课程设计过程简介 本课程的是对软件设计的综合训练，包括问题分析、总体设计、用户界面设计、程序设计基本技能和技巧，多人合作，以至一套软件工作规范的训练和科学作风的培养。在数据结构实验中，完成的只是单一而“小”的算法，而本课程设计是对学生的整体编程能力的锻炼。在课程设计过程中,应该遵循软件工程的思想，按软件工程的流程来指导学生工作的开展。软件项目的开发软件工程的标准，这样可以提高软件开发的效率，减少软件开发与维护中的问题。典型的软件开发 一、问题的定义 依据市场调查分析，客户需求提出问题。明确项目的名称、背景、开发该系统的现状、项目的目标等。 二、可

2、行性研究 可行性研究的目的是用最小的代价在尽可能短的时间内确定问题是否能够解决。也就是说可行性研究的目的不是解决问题，而是确定问题是否值得去解，研究在当前的具体条件下，开发新系统是否具备必要的资源和其它条件。一般说来，应从经济可行性、技术可行性、运行可行性、法律可行性和开发方案可行性等方面研究可行性。可行性研究需要的时间长短取决于工程的规模。 可行性研究的步骤 1确定系统规模和目标 2分析目前正在使用的系统 3. 设计出新系统的高层逻辑模型 4. 评审系统模型 5设计和评价供选择的方案 6推荐一个方案并说明理由 7制定行动方针 8拟定开发计划并书写计划任务书 9编制可性报告并提交审查 三、需求

3、分析 需求分析的任务 需求分析是软件定义时期的最后一个阶段，它的基本任务是准确地回答“系统必须做什么？”这个问题。需求分析所要做的工作是深入描述软件的功能和性能，确定软件设计的限制和软件同其它系统元素的接口细节，定义软件的其它有效性需求。 通常软件开发项目是要实现目标系统的物理模型，即确定待开发软件系统的系统元素，并将功能和数据结构分配到这些系统元素中。它是软件实现的基础。 需求分析的任务不是确定系统如何完成它的工作，而是确定系统必须完成哪些工作，也就是对目标系统提出完整、准确、清晰、具体的要求。在这个阶段结束时交出的文档中应该包括详细的数据流图，数据字典和一组简明的算法描述。 需求分析阶段的

4、任务包括下述几方面。 1. 确定目标系统的具体要求 确定系统的运行环境要求；系统的性能要求；系统功能。 2分析系统的数据要求 分析系统的数据需求是由系统的信息流归纳抽象出数据元素组成、数据的逻辑关系、数据字典格式和数据模型。并以输入/处理/输出的结构方式表示。因此，必须分析系统的数据需求，这是软件需求分析的一个重要任务。 3建立目标系统的逻辑模型 就是在理解当前系统需要“怎样做”的基础上，抽取其“做什么”的本质。 4修正系统开发计划 5建立原型系统 6编写软件需求规格说明书及评审 需求分析的方法 结构化分析方法就是面向数据流自顶向下逐步求精进行需求分析的方法。 需求分析的过程或步骤 1 调查研

5、究 2 描述和分析系统的逻辑模型 应注意下述两条原则：第一，在分层细化时必须保持信息连续性，也就是说细化前后对应功能的输入输出数据必须相同；第二，当进一步细化将涉及如何具体地实现一个功能时，也就是当把一个功能进一步分解成子功能后，并将考虑为了完成这些子功能而写出其程序代码时，就不应该再分解了。 3编制文档 在这个阶段应该完成下述四种文档资料： 系统规格说明-用比较形式化的术语和表示对软件功能构成的详细描述，作用是：技术合同说明；设计和编码的基础；测试和验收的依据。 数据要求-数据结构、数据域、数据精度。 用户系统描述。 修正的开发计划。 4需求分析审查 需求分析的原则 1必须能够表达和理解问题

6、的数据域和功能域 2按自顶向下、逐层分解问题 3要给出系统的逻辑视图和物理视图 四、总体设计 概要设计任务 1系统分析员审查软件计划、软件需求分析提供的文档，提出候选的最佳推荐方案，用系统流程图，组成系统物理元素清单，成本效益分析，系统的进度计划，供专家审定，审定后进入设计。 2确定模块结构，划分功能模块，将软件功能需求分配给所划分的最小单元模块。确定模块间的联系，确定数据结构、文件结构、数据库模式，确定测试方法与策略。 3编写概要设计说明书，用户手册，测试计划，选用相关的软件工具来描述软件结构，结构图是经常使用的软件描述工具。选择分解功能与划分模块的设计原则，例如模块划分独立性原则，信息隐蔽

7、原则等。 4 概要设计后转入详细设计，其主要任务，根据概要设计提供的文档，确定每一个模块的算法，内部的数据组织，选定工具清晰正确表达算法。编写详细设计说明书，详细测试用例与计划用到如何确定程序的复杂程度的程序图，算法流程图的表述工具，如PAD图，N-S图等。 概要设计的过程 在概要设计过程中要先进行系统设计，复审系统计划与需求分析，确定系统具体的实施方案；然后进行结构设计，确定软件结构。一般步骤如下： S1：设计系统方案 S2：选取一组合理的方案 S3：推荐最佳实施方案 S4：功能分解 S5：软件结构设计 S6：数据库设计、文件结构的设计 S7：制定测试计划 S8：编写概要设计文档 S9：审查

8、与复审概要设计文档。 五、详细设计 详细设计的任务 详细设计的目的是为软件结构图中的每一个模块确定使用的算法和块内数据结构，并用某种选定的表达工具给出清晰的描述。 这一阶段的主要任务： 1为每个模块确定采用的算法，选择某种适当的工具表达算法的过程，写出模块的详细过程性描述； 2确定每一模块使用的数据结构； 3确定模块接口的细节，包括对系统外部的接口和用户界面，对系统内部其它模块的接口，以及模块输入数据、输出数据及局部数据的全部细节。 在详细设计结束时，应该把上述结果写入详细设计说明书，并且通过复审形成正式文档。交付给下一阶段的工作依据。 4要为每一个模块设计出一组测试用例，以便在编码阶段对模块

9、代码进行预定的测试，模块的测试用例是软件测试计划的重要组成部分，通常应包括输入数据，期望输出等内容。 详细设计的原则 1由于详细设计的蓝图是给人看的，所以模块的逻辑描述要清晰易读、正确可靠。 2采用结构化设计方法，改善控制结构，降低程序的复杂程度，从而提高程序的可读性、可测试性、可维护性。其基本内容归纳为如下几点。 (1)程序语言中应尽量少用GOTO语句，以确保程序结构的独立性。 (2)使用单人口单出口的控制结构，确保程序的静态结构与动态执行情况相一致。保证程序易理解。 (3)程序的控制结构一般采用顺序、选择、循环三种结构来构成，确保结构简单。 (4)用自顶向下逐步求精方法完成程序设计。结构化

10、程序设计的缺点是存储容量和运行时间增加10-20，但易读易维护性好。 (5)经典的控制结构为顺序，IF THEN ELSE分支，DO-WHILE循环。扩展的还有多分支CASE，DO-UNTIL循环结构，固定次数循环DOWHILE。 3.选择恰当描述工具来描述各模块算法。 详细设计的方法 详细设计的工具： 11图形工具 利用图形工具可以把过程的细节用图形描述出来。 22表格工具 可以用一张表来描述过程的细节，在这张表中列出了各种可能的操作和相应的条件。 33语言工具 用某种高级语言来描述过程的细节。 六、编码 编码就是把软件设计的结果翻译成计算机可以理解的形式,即用某种程序设计语言书写的程序。本

11、课程设计选用C语言实现详细设计。 七、软件测试 测试的原则如下： 测试前要认定被测试软件有错，不要认为软件设有错。 要预先确定被测试软件的测试结果。 要尽量避免测试自己编写的程序。 测试要兼顾合理输入与不合理输入数据。 测试要以软件需求规格说明书为标准。 要明确找到的新错与已找到的旧错成正比。 测试是相对的，不能穷尽所有的测试，要据人力物力安排测试，并选择好测试用例与测试方法。 测试用例留作测试报告与以后的反复测试用，重新验证纠错的程序是否有错。 软件测试技术 1. 软件测试的目标 测试的目标： 测试是为了发现程序中的错误而执行程序的过程； 好的测试方案是极可能发现迄今为止尚未发现的错误的测试

12、方案； 成功的测试是发现了至今为止尚未发现的错误的测试。 2. 测试方法 按照测试过程是否在实际应用环境中来分，有静态分析与动态测试。 测试方法有分析方法与非分析方法。白盒法是通过分析程序内部的逻辑与执行路线来设计测试用例，进行测试的方法，白盒法也称逻辑驱动方法。黑盒法是功能驱动方法，仅根据I/O数据条件来设计测试用例，而不管程序的内部结构与路径如何。白盒法的具体设计程序测试用例的方法有：语句覆盖、分支覆盖、条件覆盖、路径覆盖，主要目的是提高测试的覆盖率。黑盒法的具体设计程序测试用例的方法有：等价类划分法，边界值分析法，错误推测法，主要目的是设法以最少测试数据子集来尽可能多的测试软件程序的错误

13、。 静态分析技术 不执行被测软件，可对需求分析说明书、软件设计说明书、源程序做结构检查、流程分析、符号执行来找出软件错误。 动态测试技术 当把程序作为一个函数，输入的全体称为函数的定义域，输出的全体称为函数的值域，函数则描述了输入的定义域与输出值域的关系。这样动态测试的算法有： 选取定义域中的有效值，或定义域外无效值。 对已选取值决定预期的结果。 用选取值执行程序。 观察程序行为，记录执行结果。 将的结果与的结果相比较，不吻合则程序有错。 动态测试既可以采用白盒法对模块进行逻辑结构的测试，又可以用黑盒法做功能结枸的测试，接口的测试，都是以执行程序并分析执行结果来查错的。 黑盒测试和白盒测试 黑

14、盒测试法 黑盒测试法把程序看成一个黑盒子，完全不考虑程序的内部结构和处理过程。黑盒测试是在程序接口进行的测试，它只检查程序功能是否能按照规格说明书的规定正常使用，程序是否能适当地接收输入数据产生正确的输出信息，并且保持外部信息的完整性。黑盒测试又称为功能测试。 白盒测试法 白盒测试法的前提是可以把程序看成装在一个透明的白盒子里，也就是完全了解程序的结构和处理过程。这种方法按照程序内部的逻辑测试程序，检验程序中的每条通路是否都能按预定要求正确工作，白盒测试又称为结构测试。 八、维护 软件维护的定义、分类、特点 人们称在软件运行/维护阶段对软件产品所进行的修改就是维护。 1结构化维护与非结构化维护

15、的对比 2维护的代价 3维护的问题 软件维护步骤及组织 维护步骤 需要经历以下四个步骤。 分析和理解程序 修改程序 重新验证程序 维护组织 数据结构课程设计实施方案 一、设计要求: 本课程设计是为了配合数据结构课程的开设,通过设计一完整的程序,使学生掌握数据结构的应用,算法的编写,类C语言的算法转换成C程序并用TC上机调试的基本方法.要求如下: 1.要充分认识课程设计对自己的重要性,认真做好设计前的各项准备工作. 2.既要虚心接受老师的指导,又要充分发挥主观能动性.结合课题,独立思考,努力钻研,勤于实践,勇于创新. 3.独立按时完成规定的工作任务,不得弄虚作假,不准抄袭他人内容,否则成绩以不及

16、格计.4.无论在校外,校内,都要严格遵守学校和所在单位的学习和劳动纪律,规章制度,学生有事离校必须请假.课程设计期间,无故缺席按旷课处理;缺席时间达四分之一以上者,其成绩按不及格处理.5.在设计过程中,要严格要求自己,树立严肃,严密,严谨的科学态度,必须按时,按质,按量完成课程设计.6.小组成员之间,分工明确,但要保持联系畅通,密切合作,培养良好的互相帮助和团队协作精神. 二、适用专业 计算机科学与技术，电子信息工程等理工科专业。 三、课程设计的一般步骤(及时间安排) 课程设计大体分五个阶段: 1)选题与搜集资料:每人选择一题(或23人为一小组进行选题),进行课程设计课题的资料搜集.(周一上午

17、) 2)分析与概要设计:根据搜集的资料,进行程序功能与数据结构分析,并选择合适的数据结构,并在此基础上进行实现程序功能的算法设计.(周一下午,周二上午) 3)程序设计:运用掌握C语言编写程序,实现所程序的各个模块功能.(周二下午,周三上午) 4)调试与测试:自行调试程序,成员交叉测试程序,并记录测试情况.(周三下午,周四上午) 5)实习报告:编写实习报告(周四下午) 6)验收与评分:指导教师对每个小组的开发的系统,及每个成员开发的模块进行综合验收.(周五上午) 7)结合设计报告,根据课程设计成绩的评定方法,评出成绩.(周五下午) 四、本课程设计内容与要求： 掌握课程设计的每个步骤,在此基础上设

18、计出所要求的数据结构,功能模块和完整的主程序. 1.完整的问题描述 2.程序所要完成的基本要求 3.算法实现提示(算法思想) 4.程序实现(算法实现) 五、上机任务 1.选择合适的数据结构,并定义数据结构的结构体; 2.根据程序所要完成的基本要求和程序实现提示,设计出完整的算法; 3.设计出主程序(main函数),使其成为完整的程序. 六、考核方式与成绩评定 设计报告与程序源码作为考核的内容,成绩计分按优,良,中,差4级评定. 七、 注意事项 1.素材可从以下给出的参考的实例中选做一题,如有选同样内容的同学,程序不能完全相同,否则以不及格计. 2.最后要上交的内容有:数据结构实习报告(包含数据

19、结构的结构体定义,核心算法)程序. 3.时间安排:第16周.(截止到周五上午) 四设计题目 1、 一元多项式计算 *问题描述：能够按照指数降序排列建立并输出多项式； 能够完成两个多项式的相加、相减，并将结果输入； 在上交资料中请写明：存储结构、多项式相加的基本过程的算法 、源程序、测试数据和结果、算法的时间复杂度、另外可以提出算法的改进方法； 2、 订票系统 *问题描述：通过此系统可以实现如下功能： 1）录入： 可以录入航班情况 2）查询： 可以查询某个航线的情况； 可以输入起飞抵达城市，查询飞机航班情况； 3）订票： 可以订票，如果该航班已经无票，可以提供相关可选择航班； 4）退票： 可退票

20、，退票后修改相关数据文件； 客户资料有姓名，证件号，订票数量及航班情况，订单要有编号。 5）修改航班信息：当航班信息改变可以修改航班数据文件 *要求： 根据以上功能说明，设计航班信息，订票信息的存储结构，设计程序完成功能； 3、 迷宫求解 *问题描述：可以输入一个任意大小的迷宫数据，用非递归的方法求出一条走出迷宫的路径，并将路径输出； *要求： 在上交资料中请写明：存储结构、基本算法、源程序、测试数据和结果、算法的时间复杂度、另外可以提出算法的改进方法； 4、 文章编辑 *问题描述：输入一页文字，程序可以统计出文字、数字、空格的个数。 静态存储一页文章，每行最多不超过80个字符，共N行。 *要

21、求分别统计出其中英文字母数和空格数及整篇文章总字数；统计某一字符串在文章中出现的次数，并输出该次数；删除某一子串，并将后面的字符前移。 *存储结构使用线性表，分别用几个子函数实现相应的功能； *输入数据的形式和范围：可以输入大写、小写的英文字母、任何数字及标点符号。 *输出形式：分行输出用户输入的各行字符；分4行输出全部字母数、数字个数、空格个数、文章总字数输出删除某一字符串后的文章； 5、 joseph环 *问题描述：编号是1，2，,n的n个人按照顺时针方向围坐一圈，每个人只有一个密码。一开始任选一个正整数作为报数上限值m,从第一个仍开始顺时针方向自1开始顺序报数，报到m时停止报数。报m的人

22、出列，将他的密码作为新的m值，从他在顺时针方向的下一个人开始重新从1报数，如此下去，直到所有人全部出列为止。设计一个程序来求出出列顺序。 *要求：利用单向循环链表存储结构模拟此过程，按照出列的顺序输出各个人的编号。 *测试数据： m的初值为20，n=7 ,7个人的密码依次为3，1，7，2，4，7，4，首先m=6,则正确的输出是什么？ *输入数据：建立输入处理输入数据，输入m的初值，n ，输入每个人的密码，建立单循环链表。 *输出形式：建立一个输出函数，将正确的输出序列 6、 猴子选大王 *问题描述：一堆猴子都有编号，编号是1，2，3 .m ,这群猴子按照1-m的顺序围坐一圈，从第1开始数，每数

23、到第N个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。 *输入数据：输入m,n m,n 为整数，nm *输出形式：中文提示按照m个猴子，数n 个数的方法，输出为大王的猴子是几号 ，建立一个函数来实现此功能 7、 建立二叉树，层序、先序遍历 *问题描述： 要求能够输入树的各个结点，并能够输出用不同方法遍历的遍历序列；分别建立建立二叉树存储结构的的输入函数、输出层序遍历序列的函数、输出先序遍历序列的函数； 8、 赫夫曼树的建立 *问题描述：建立建立最优二叉树函数 *要求：可以建立函数输入二叉树，并输出其赫夫曼树 在上交资料中请写明：存储结构、 基本算法 、输入输出

24、、源程序、测试数据和结果、算法的时间复杂度、另外可以提出算法的改进方法； 9、 纸牌游戏 *问题描述：编号为1-52张牌，正面向上，从第2张开始，以2为基数，是2的倍数的牌翻一次，直到最后一张牌；然后，从第3张开始，以3为基数，是3的倍数的牌翻一次，直到最后一张牌；然后从第4张开始，以4为基数，是4的倍数的牌翻一次， 直到最后一张牌；.再依次5的倍数的牌翻一次，6的，7的 直到 以52为基数的 翻过。输出：这时正面向上的牌有哪些？ 10、图的建立及输出 *问题描述：建立图的存储结构，能够输入图的顶点和边的信息，并存储到相应存储结构中，而后输出图的邻接矩阵。 11、拓扑排序 *问题描述：编写函数

25、实现图的拓扑排序。 12、 各种排序 *问题描述：对30000个随机整数，利用插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序等排序方法进行排序，并统计每一种排序上机所花费的时间。 *输入的数据形式为任何一个正整数，大小不限。 *输出的形式：数字大小逐个递增的数列? 13、图的遍历 *问题描述：对任意给定的图，建立它的邻接表并输出，然后利用队列的五种基本运算实现图的广度优先搜索周游。 14、线性表的操作 *问题描述：利作链表的插入运算建立线性链表，然后利用链表的查找、删除、计数、输出等运算反复实现链表的这些操作，并能在屏幕上输出操作前后的结果。 15、长整数四则运算 *问题描

26、述：设计一个实现任意长的整数进行加法运算的演示程序。*基本要求：利用双向循环链表实现长整数的存储，每个结点含一个整形变量。任何整形变量的范围是 -(215 - 1) (215 - 1)。输入和输出形式：按中国对于长整数的表示习惯，每四位一组，组间用逗号隔开。 *测试数据： 0；0；应输出“0”。 -2345,6789；-7654,3211；应输出“-1,0000,0000”。 -9999,9999；1,0000,0000,0000；应输出“999 1,0001,0001；-1,0001,0001；应输出“0”。 1,0001,0001；-1,0001,0000；应输出“1”。 -9999,99

27、99,9999；-9999,9999,9999；应输出“1,9999,9999,9998”。 1,0000,9999,9999；1；应输出“1,0001,0000,0000”。 *实现提示： 每个结点中可以存放的最大整数为32767，才能保证两数相加不会溢出，但若这样存放，即相当于按32768进制存放，在十进制与32768进制数之间的转换十分不方便，故可以在每个结点中仅存十进制的4位，即不超过9999的非负整数，整个链表表示为万进制。 可以利用头结点数据域的符号代表长整数的符号。用其绝对值表示元素结 点数目。相加过程中不要破坏两个操作数链表。两操作数的头指针存于指针数组中是简化程序结构的一种方

28、法。不能给长整数位数规定上限。 16、马踏棋盘 *问题描述：将马随机放在国际象棋的8 8棋盘Bord88的某个方格中，马按走棋规则进行移动。要求每个方格上只进入一次，走遍棋盘上全部64个方格。编制非递归程序，求出马的行走路线 ，并按求出的行走路线，将数字1，2，64依次填入�个8 8的方阵，输出之。 *测试数据：由读者指定,可自行指定一个马的初始位置。 *实现提示：每次在多个可走位置中选择一个进行试探，其余未曾试探过的可走位置必须用适当结构妥善管理，以备试探失败时的“回溯”(悔棋)使用。 17、校园导游咨询 *问题描述： 设计你的学校的校园平面图，所含景点不少于10个。以图中顶点表示学校

29、各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等相关信息。 为来访客人提供图中任意景点的问路查询，即查询任意两个景点之间的一条最短的简单路径。 为来访客人提供图中任意景点相关信息的查询。 *测试数据：由读者根据实际情况指定。 *实现提示：一般情况下，校园的道路是双向通行的，可设校园平面图是一个无向网。顶点和边均含有相关信息。 18、编制一个求解迷宫通路的图形界面演示程序。 *问题描述： 1） 输入一个任意大小的迷宫，任设起点、终点、障碍，用栈求出一条走出迷宫的路径，并显示在屏幕上。 2） 根据用户界面提示，用键盘输入。Home键设置迷宫起点，End键设终点，上下左右箭头键移

30、动，Enter键添加墙，Del键删除墙，完成后按F9键演示，Esc键退出。 3）橙色的实心小圆圈表示起点，绿色实心圆圈表示终点，空心圆圈表示足迹，红色方块表示墙。 4）本程序只求出一条成功的通路，但若对求解函数MazePath稍加更改即可求得全部路径。此外，因受图形界面限制，不能保存或载入测试文件。 5）当未输入起点时，消息显示“Error： You must set Startplace.”；未输入终点时，显示“Error： You must set Endplace.” 找到路径时，屏幕显示足迹，并在消息框出现Path found，否则消去足迹，显示Path not found. 19一元

31、稀疏多项式计算器 *问题描述：一元多项式简单计算器的基本功能是：输入并建立多项式；输出多项式，输出形式为整数序列n,c1,e1,c2,e2,cn,en，其中n是多项式的项数，ci和ei分别是第I项的系数和指数，序列指指数降序排列；多项式a和b相加，建立多项式a+b；多项式a和b相减，建立多项式a-b。 *实现提示：用带头结点的单链表存储多项式，多项式的项数存在头结点。 20算术表达式求值演示 *问题描述：表达式求值是实现程序设计语言的基本问题之一，也是栈的应用的一个典型例子。设计一个程序，演示用算符优先法对算术表达式求值的过程。 *基本要求：以字符序列的形式从终端上输入语法正确的、不含变量的整

32、数表达式。利用教材中给出的算符优先关系，实现对算术四则混合运算表达式的求值，并仿照教材例3-1演示在求值中运算符栈、运算数栈、输入字符和主要操作的变化过程。 *实现提示：设置运算栈和运算数栈辅助分析算符优先关系。在输入表达式的字符序列的同时，完成运算符和运算数的识别处理，以及相应的运算。在识别出运算数的同时，要将其字符序列形式转换成整数形式。 *选作内容：扩充运算符集，如增加乘方、单目减、赋值等运算；运算量可以是变量；运算量可以是实数类型；计数器的功能和仿镇界面。 21稀疏矩阵运算器 *问题描述：稀疏矩阵是指那些多数元素为0的矩阵。利用“稀疏”特点进行存储和计算可以大大节省存储空间，提高计算效

33、率。实现一个能进行稀疏矩阵基本原酸的运算器。 *基本要求：以“带行逻辑链接信息”的三元组顺序表示稀疏矩阵，实现两个矩阵相加、相减和相乘的运算。稀疏矩阵的输入形式采用三元组表示，而运算结构的矩阵则以通常的阵列形式列出。 *实现提示：首先应输入矩阵的行数和列数，并判别给出的两个矩阵的行、列数对于所要求作的运算是否匹配。可设矩阵的行数和列数均不超过20。程序可以对三元组的输入顺序加以限制，例如，按行优先。注意研究教科书中的算法，以便提高计算效率。在用三元组表示稀疏矩阵时，相加或相减所得结果矩阵应该另生成，乘积矩阵也可以用二维数组存放。 22图书管理 *问题描述：图书管理基本业务活动包括：对一本书的采

34、编入库、清除库存、借阅和归还等等。试设计一个图书管理系统，将上述业务活动借助于计算机系统完成。 *基本要求： 每种书的登记内容至少包括书号、书名、作者、现存量和总库存量等五4。 作为演示系统，不必使用文件，全部数据可以都在内存存放。但是由于上述四项基本业务活动都是通过书号进行的，所以要用B树对书号尽力索引，以获得高效率。 系统应实现的操作及功能定义如下：采编入库：新购入一种书，经分类和确定书号后登记到图书帐目中去。如果这种书在帐目中已有，则只将总库存量增加。清除库存：某种书已无保留价值，将它从图书帐目中注销。某种书的现存量大于零，则借出一本，登记借阅者的图书证号和归还期限。归还：注销对借阅者的

35、登记，改变该书的现存量。显示：以凹入表的形式显示B树。这个操作是为了调试和维护的目的而设置的。下列B树的打印格式如下所示： 五、参考书目 1 严蔚敏，数据结构 C语言，清华大学出版社 2 严蔚敏，数据结构习题，清华大学出版社 3 谭浩强，数据结构， 高教出版社 4 李春保，数据结构习题， 清华大学出版社 5 李春葆数据结构习题与解析清华大学出版社课程设计一 线性表 本章课程设计的主要任务是使用有关线性表的操作来实现管理信息系统的管理。设计的主要目的在于训练初学者的基本编程能力，了解管理信息系统的开发流程。 1. 通讯录管理系统 1.1问题描述 通讯录是人们日常生活中经常要用到的通讯管理工具，它

36、以文件的方式保存用户录入的数据，并提供查询的功能供用户查询和使用通讯录信息。本节介绍用C语言实现的简易通讯录管理系统，它支持基本的录入、删除、查找、修改和文件读写功能。 1.2功能描述 通讯录要求实现最基本的功能，包括录入、删除、查找和修改，为此需要首先定义记录项的格式，其基本属性包括编号、姓名、性别、住址、联系电话等。 整个系统由如下几大功能模块组成： 1. 通讯录的建立。该模块主要完成将数据存入数组中的工作。记录可以从文本形式存储的数据文件中读入，也可以从键盘逐个输入记录。 2. 通讯录的查询。用户可以按照联系人的姓名或电话号码查询。若找到满足查询条件的记录，则以表格的形式显示出此记录的信

37、息；否则，显示未找到记录的提示信息。 3. 通讯录的维护。实现对记录的修改，删除，插入和排序操作。 4. 通讯录的输出。实现屏幕显示和将数组中存储的记录信息写入数据文件中。 1.3 设计 1.3.1程序总体结构 程序主要包括三大模块：输入输出模块、管理模块和文件操作模块。输入输出模块的主要功能是人机交互，包括程序界面显示、用户输入响应、结果输出等；管理模块从输入输出模块读取用户命令并进行相应的操作，包括录入、删除、修改、查找、列表等；文件操作模块获取管理模块中的数据或命令，然后进行存储文件的读写，最后将结果返回给管理模块。 图1-1通讯录系统运行示意图 1.3.2界面设计 程序的主界面是一个文

38、本方式的菜单，用户通过键盘输入数字，选取相应的操作指令。 1.3.3重要数据结构设计 通讯录中的记录项用结构体telebook表示，包含4个属性。num属性是记录项的唯一编号，name、phonenum、address分别代表用户的姓名、联系电话和地址。 typedef struct telebook char num 4; char name 10; char phonenum 15; char address 20; TELEBOOK; 1.3.4 功能函数设计 通讯录程序采用了结构化程序设计的思想。程序中除了主函数外，共设计了12个函数。 1) printheader ( ) 函数原型v

39、oid printheader( ) 功能：用于在以表格形式显示记录时，打印输出表头信息。 2) printdata ( ) 函数原型void printdata ( TELEBOOK pp) 功能：用于在以表格形式显示记录时，打印输出单个数组元素pp中的记录信息。 3) Disp ( ) 函数原型void Disp(TELEBOOK temp ,int n) 功能：用于显示temp数组中存储的n条记录，内容为telebook结构中定义的内容。 4) stringinput ( ) 函数原型void stringinput (char*t,int lens, char*notice) 功能：s

40、tringinput函数用于输入字符串，并进行字符串长度验证，t用于保存输入的字符串，因为是以指针形式传递的，所以t相当于该函数的返回值。notice用于保存printf中输出的提示信息。 5) Locate ( ) 函数原型int Locate(TELEBOOK temp,int n,char findmess,char nameorphonenum) 功能：Locate函数用于单位数组中符合要求的元素，并返回该数组元素的下标值。参数findmess保存要查找的家庭内容，nameorphonenum表示按姓名或电话号码字段在数组temp中查找。 6) Add ( ) 函数原型int Add(

41、TELEBOOK temp,int n) 功能：Add函数用于在数组temp中增加电话簿记录，并返回数组中的当前记录数。 7) Qur ( ) 函数原型void Qur (TELEBOOK temp,int n) 功能：Qur函数用于在数组temp中按姓名或电话号码查找满足条件的记录，并显示出来。 8) Del ( ) 函数原型int Del(TELEBOOK temp,int n) 功能：Del函数用于在数组temp中找到满足条件的记录，然后删除该记录。 9) Modify ( ) 函数原型void Modify(TELEBOOK temp,int n) 功能：Modify函数用于在数组te

42、mp中修改记录。 10) Insert( ) 函数原型:：int Insert(TELEBOOK temp,int n) 功能：Insert 函数用于在数组temp中插入记录，并返回数组中的当前记录数。 11) SelectSort ( ) 函数原型void SelectSort(TELEBOOK temp,int n) 功能：SelectSort函数用于在数组temp中完成利用选择排序算法实现数组的升序排序。 12) Save ( ) 函数原型void Save(TELEBOOK temp,int n) 功能：Save函数用于将保存联系人电话簿的数组temp中的n个元素写入磁盘的数据文件中。

43、 1.4 程序实现 为节省篇幅，这里仅列出了函数名称(详细源程序清单见本书光盘)。读者只需按如下顺序输入程序，即可进行编译，调试，运行。 1)程序预处理 包括加载头文件，定义结构体，常量和变量，并对它们进行初始化。 2)主菜单界面 用户进入成绩管理系统时，显示主菜单，提示用户进行选择，完成相应任务。 在此处输入函数void menu 的源代码。 3)表格形式显示记录 由于显示操作经常进行，为减少代码的重复输入，这部分编成函数供程序调用。源代码编辑过程如下。 输入函数void printheader( )。 输入函数void printdata(TELEBOOK pp)。 输入函数void Di

44、sp(TELEBOOK temp,int n)。 输入函数void Wrong( )，功能是输出按键错误信息。 输入函数void Nofind( )，功能是输出未查找此记录的信息。 4)记录查找定位 输入函数int Locate(TELEBOOK temp,int n,char findmess,char nameorphonenum)。 作用：用于定位数组中符合要求的记录，并返回保存该记录的数组元素下标值。 参数：findmess保存要查找的具体内容; nameorphonenum保存按什么在数组中查找。 5)格式化输入数据 输入函数void stringinput(char *t,int

45、lens,char *notice)。 在此电话簿管理系统中，要求用户输入的只有字符型数据，所以我们设计了下面这个函数来单独处理，并对输入的数据进行检验。调用stringinput(char *t,int lens ,char *notice)函数，它将提示用户输入字符串，并对用户输入的字符串进行长度验证。 6) 增加记录 输入函数int Add(TELEBOOK temp,int n)。 调用Add(TELEBOOK temp,int n)函数，完成在数组temp中添加电话簿记录的功能。在刚进入电话簿管理系统时，若默认的数据文件为空，则从头部开始增加记录；否则，将此记录添加在数组的尾部。 7

46、)查询记录 输入函数void Qur(TELEBOOK temp,int n)。 调用Qur(TELEBOOK temp,int n)函数，完成在数组temp中查询电话簿记录的功能。当用户执行查询任务时，系统会提示用户进行查询字段的选择，即根据联系人姓名或电话号码进行查询。若此记录存在，则会以表格的形式打印输出此条记录信息。 /*按编号或姓名，查询电话簿记录*/ 8)删除记录 输入函数int Del(TELEBOOK temp,int n)。 调用Del(TELEBOOK temp,int n)函数，完成数组temp中删除电话簿记录的功能。在删除操作中，系统会先按用户要求找到该记录元素的下标值，然后从数组中删除该数组元素。 9)修改记录 输入函数void Modify(TELEBOOK temp,int n)。 调用Modify(TELEBOOK temp,int n)函数，完成数组temp中修改电话簿记录的功能。在修改记录操作中，系统会先按用户输入的联系人姓名查找到该记录，然后提示用户修改此记录