第9章 综合应用实例
9.1 上机实验要求及规范\r9.2 约瑟夫环问题\r9.3 迷宫问题\r9.4 短信促销活动\r9.5 保龄球记分系统 \r9.6 用静态栈数据结构实现表达式求值\r\r
9.1 上机实验要求及规范
9.1.1 上机实习的具体步骤\r 1.问题分析与系统结构设计\r 2．详细设计和编码 \r 3.上机准备及程序调试 \r 4.整理实验报告 \r
9.1.2 实验报告的基本要求
一般性、较小规模的上机实验，其实验报告可包括以下几项内容：\r（1） 实验名称，即每次实验的题目名称或编号。\r(2)实验内容和要求，即具体需要解决的问题，应明确输入、输出数据，基本格式及要求，实际操作中，任课教师可能给出的题目并不明确，但学生应该在充分理解题意的基础上明确以上要求，甚至自己提出一些设想。
（3） 设计说明，主要是给出数据结构和算法框架。数据结构应该完整描述出处理对象的逻辑关系，以及所选择的存储结构，算法可以用伪程序或流程图来描述其基本设计思想。\r（4） 调试分析，根据程序调试过程中的几组测试数据，记录其运行结果，写出调试过程中出现的问题和解决方法、途径与结果，并分析其原因，总结体会。\r（5） 程序清单（带有必要的注释）\r
9.2 约瑟夫环问题
[问题描述] 约瑟夫（Joseph）问题的一种描述：编号为1，2，……，n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数的上限值m，从第一个人开始按顺时针方向自1开始顺序报数,报到m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，…，如此下去，直到所有人全部出列为止。试设计一个程序求出出列顺序。
[基本要求] 可以利用单向循环链表存储结构模拟此过程，按照出列的顺序打印出，要求打印出各人的编号和密码。\r[实现提示] 用不带头结点的单循环链表表示一圈人的编号和密码，程序一开始，要求用户指定初始报数的上限值，然后依次输入各人的密码。\r[程序实现] 用一个结构体表示每个人的编号和密码，将结构体连起来构成循环单链表。
9.3 迷宫问题
[问题描述] 迷宫实验是取自心理学的一个古典实验。在该实验中，把一只老鼠从一个无顶大盒子的门放入，在盒子中设置了许多墙，对行进方向形成了多处阻挡。盒子仅有一个出口，在出口处放置一块奶酪，吸引老鼠在迷宫中寻找道路以到达出口。对同一只老鼠重复进行上述实验，一直到老鼠从入口到出口，而不走错一步。老鼠经过多次试验终于得到它学习走通迷宫的路线。设计一个计算机程序对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。
[基本要求] 要求程序输出：\r1、一条通路的二元组（i, j）数据序列，（i, j）表示通路上某一点的坐标。\r2、用一种标志（如数字8）在二维数组中标出该条通路，并在屏幕上输出二维数组。\r[实现提示] 可以利用一个二维数组maze[i][j]表示迷宫，其中1<=i<=m,1<=j<=n。数组元素值为1表示该位置是墙壁，不能通行；元素值为0表示该位置是通路。假定从maze[1][1]出发，出口位于maze[m][n]，移动方向可以是8个方向（东，东南，南，西南，西，西北，北和东北）。\r
[程序实现] 这里需用到一个栈，栈的元素是一个结构。为方便采用顺序栈。由于数组maze的每个位置最多被访问一次，所以至多有m*n个元素放入栈中，因此m*n作为栈的容量大小是个安全的值，但也是个保守的值。一般取m*n/2即可。程序见P165~169。
9.4 短信促销活动
[问题描述] 一超市庆祝开业10周年，特举行大型促销活动。为通知到每位贵宾，并节约成本，特采用时下流行的手机短信通知方式。该超市有10多万户完整的贵宾资料，分别存放在两个文本文件中（每行一条记录，以TAB键分隔每个域）：\r1．贵宾帐户文本。格式为“贵宾卡号 客户姓名 身份证号”\r2．贵宾资料文本。格式为“身份证号 手机号”\r
[基本要求] 短信通知采用上传接口文件方式，接口文件每行表示一条信息，格式为“手机号码 短信信息”，以TAB键分隔手机号和短信息。“短信信息”的内容为：“尊敬的＊＊＊贵宾，Ａ超市场为庆祝开业十周年，于5月1日至5月15日举行促销活动，凭贵宾卡（贵宾卡号）可享受全场9折，欢迎惠顾”。为了便于查看，要求上传文件以贵宾卡号升序排列。
[设计思路] 本题主要涉及到以下几个知识点：\r1、? 对文本文件的操作。包括文本的读取、文本行向结构化转换、文本文件生成。\r2、? 内存操作。包括结构指针的空间申请，赋值，空间回收等。\r3、? 结构数组的排序。其中贵宾帐户表以贵宾卡号排序，贵宾资料表以身份证号排序。建议采用快速排序或归并排序。\r4、已排好序的结构数组查找。在生成短信通知文件中，要根据身份证号从贵宾资料表中查找到手机号，采用折半查找方法。程序见P169~175。\r
9.5 保龄球记分系统
[问题描述]保龄球一局分十轮，每轮可滚球一次或多次，以击倒的球数为依据得分。一局得分为十轮得分之和，而每轮的得分不仅与本轮滚球情况有关，还可能与后续一两轮的滚球情况有关。即：某轮某次滚球击倒的球数不仅要记入本轮得分，还可能记入前一两轮得分。具体的滚球规则和记分规则如下：\r
（１）一轮的第一次滚球就击倒10个球，则本轮不再滚球（若是第十轮则还需另加两次滚球）。该轮的得分为本次击倒球数10与以后两次滚球所击倒球数之和；\r（２）?若某一轮的第一次滚球未击倒10个球，则可对剩下的球再击一次。如果两次击倒10个球，则本轮不再滚球（若是第十轮则还需另加一次滚球）。该轮的得分为本次击倒球数10与以后一次滚球所击倒球数之和；\r（3）若某一轮的两次滚球未击倒10个球，则本轮不再滚球。该轮的得分为本轮击倒的球数。
[实现要求]程序要求输出十轮中各轮的第一次得分和第二次得分，各轮得分和总分。\r[程序设计思想]程序交互地逐轮输入一次滚球击倒的球数ball1 和ball2，计算该轮得分score和累计得分total。为记录因一轮击倒10个球，还暂时不能计算该轮的得分和累计总分的情况，程序引入一个变量frame，用来记录当前已完成完整计算的轮次，程序每输入一次滚球击倒球数，就检查还未完成完整计算的轮次，并计算之。程序见P176~177。
9.6 用静态栈数据结构实现表达式求值?
[问题描述]当用户输入一个合法的表达式后，能够返回正确的结果。能够计算的运算符包括：加、减、乘、除、括号；能够计算的数要求在实数范围内。对于异常表达式给出错误提示。\r[基本需求]数据对象：D={ ai |ai∈ElemSet,i=1,2,3,……，n，n≥0}\r数据关系：R={