数据结构(C语言版)9综合应用实例.ppt_第1页
数据结构(C语言版)9综合应用实例.ppt_第2页
数据结构(C语言版)9综合应用实例.ppt_第3页
数据结构(C语言版)9综合应用实例.ppt_第4页
数据结构(C语言版)9综合应用实例.ppt_第5页
已阅读5页,还剩15页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

第9章 综合应用实例,9.1 上机实验要求及规范 9.2 约瑟夫环问题 9.3 迷宫问题 9.4 短信促销活动 9.5 保龄球记分系统 9.6 用静态栈数据结构实现表达式求值,9.1 上机实验要求及规范,9.1.1 上机实习的具体步骤 1.问题分析与系统结构设计 2详细设计和编码 3.上机准备及程序调试 4.整理实验报告,9.1.2 实验报告的基本要求,一般性、较小规模的上机实验,其实验报告可包括以下几项内容: (1) 实验名称,即每次实验的题目名称或编号。 (2)实验内容和要求,即具体需要解决的问题,应明确输入、输出数据,基本格式及要求,实际操作中,任课教师可能给出的题目并不明确,但学生应该在充分理解题意的基础上明确以上要求,甚至自己提出一些设想。,(3) 设计说明,主要是给出数据结构和算法框架。数据结构应该完整描述出处理对象的逻辑关系,以及所选择的存储结构,算法可以用伪程序或流程图来描述其基本设计思想。 (4) 调试分析,根据程序调试过程中的几组测试数据,记录其运行结果,写出调试过程中出现的问题和解决方法、途径与结果,并分析其原因,总结体会。 (5) 程序清单(带有必要的注释),9.2 约瑟夫环问题,问题描述 约瑟夫(Joseph)问题的一种描述:编号为1,2,n的n个人按顺时针方向围坐一圈,每人持有一个密码(正整数)。一开始任选一个正整数作为报数的上限值m,从第一个人开始按顺时针方向自1开始顺序报数,报到m的人出列,将他的密码作为新的m值,从他在顺时针方向上的下一个人开始重新从1报数,如此下去,直到所有人全部出列为止。试设计一个程序求出出列顺序。,基本要求 可以利用单向循环链表存储结构模拟此过程,按照出列的顺序打印出,要求打印出各人的编号和密码。 实现提示 用不带头结点的单循环链表表示一圈人的编号和密码,程序一开始,要求用户指定初始报数的上限值,然后依次输入各人的密码。 程序实现 用一个结构体表示每个人的编号和密码,将结构体连起来构成循环单链表。,9.3 迷宫问题,问题描述 迷宫实验是取自心理学的一个古典实验。在该实验中,把一只老鼠从一个无顶大盒子的门放入,在盒子中设置了许多墙,对行进方向形成了多处阻挡。盒子仅有一个出口,在出口处放置一块奶酪,吸引老鼠在迷宫中寻找道路以到达出口。对同一只老鼠重复进行上述实验,一直到老鼠从入口到出口,而不走错一步。老鼠经过多次试验终于得到它学习走通迷宫的路线。设计一个计算机程序对任意设定的迷宫,求出一条从入口到出口的通路,或得出没有通路的结论。,基本要求 要求程序输出: 1、一条通路的二元组(i, j)数据序列,(i, j)表示通路上某一点的坐标。 2、用一种标志(如数字8)在二维数组中标出该条通路,并在屏幕上输出二维数组。 实现提示 可以利用一个二维数组mazeij表示迷宫,其中1=i=m,1=j=n。数组元素值为1表示该位置是墙壁,不能通行;元素值为0表示该位置是通路。假定从maze11出发,出口位于mazemn,移动方向可以是8个方向(东,东南,南,西南,西,西北,北和东北)。,程序实现 这里需用到一个栈,栈的元素是一个结构。为方便采用顺序栈。由于数组maze的每个位置最多被访问一次,所以至多有m*n个元素放入栈中,因此m*n作为栈的容量大小是个安全的值,但也是个保守的值。一般取m*n/2即可。程序见P165169。,9.4 短信促销活动,问题描述 一超市庆祝开业10周年,特举行大型促销活动。为通知到每位贵宾,并节约成本,特采用时下流行的手机短信通知方式。该超市有10多万户完整的贵宾资料,分别存放在两个文本文件中(每行一条记录,以TAB键分隔每个域): 1贵宾帐户文本。格式为“贵宾卡号 客户姓名 身份证号” 2贵宾资料文本。格式为“身份证号 手机号”,基本要求 短信通知采用上传接口文件方式,接口文件每行表示一条信息,格式为“手机号码 短信信息”,以TAB键分隔手机号和短信息。“短信信息”的内容为:“尊敬的贵宾,超市场为庆祝开业十周年,于5月1日至5月15日举行促销活动,凭贵宾卡(贵宾卡号)可享受全场9折,欢迎惠顾”。为了便于查看,要求上传文件以贵宾卡号升序排列。,设计思路 本题主要涉及到以下几个知识点: 1、 对文本文件的操作。包括文本的读取、文本行向结构化转换、文本文件生成。 2、 内存操作。包括结构指针的空间申请,赋值,空间回收等。 3、 结构数组的排序。其中贵宾帐户表以贵宾卡号排序,贵宾资料表以身份证号排序。建议采用快速排序或归并排序。 4、已排好序的结构数组查找。在生成短信通知文件中,要根据身份证号从贵宾资料表中查找到手机号,采用折半查找方法。程序见P169175。,9.5 保龄球记分系统,问题描述保龄球一局分十轮,每轮可滚球一次或多次,以击倒的球数为依据得分。一局得分为十轮得分之和,而每轮的得分不仅与本轮滚球情况有关,还可能与后续一两轮的滚球情况有关。即:某轮某次滚球击倒的球数不仅要记入本轮得分,还可能记入前一两轮得分。具体的滚球规则和记分规则如下:,()一轮的第一次滚球就击倒10个球,则本轮不再滚球(若是第十轮则还需另加两次滚球)。该轮的得分为本次击倒球数10与以后两次滚球所击倒球数之和; () 若某一轮的第一次滚球未击倒10个球,则可对剩下的球再击一次。如果两次击倒10个球,则本轮不再滚球(若是第十轮则还需另加一次滚球)。该轮的得分为本次击倒球数10与以后一次滚球所击倒球数之和; (3)若某一轮的两次滚球未击倒10个球,则本轮不再滚球。该轮的得分为本轮击倒的球数。,实现要求程序要求输出十轮中各轮的第一次得分和第二次得分,各轮得分和总分。 程序设计思想程序交互地逐轮输入一次滚球击倒的球数ball1 和ball2,计算该轮得分score和累计得分total。为记录因一轮击倒10个球,还暂时不能计算该轮的得分和累计总分的情况,程序引入一个变量frame,用来记录当前已完成完整计算的轮次,程序每输入一次滚球击倒球数,就检查还未完成完整计算的轮次,并计算之。程序见P176177。,9.6 用静态栈数据结构实现表达式求值,问题描述当用户输入一个合法的表达式后,能够返回正确的结果。能够计算的运算符包括:加、减、乘、除、括号;能够计算的数要求在实数范围内。对于异常表达式给出错误提示。 基本需求数据对象:D= ai |aiElemSet,i=1,2,3,,n,n0 数据关系:R=| ai-1,ai D, i=2,3,,n约定a1为栈底,an 为栈顶。基本操作:Push(&s,e) 初始条件:栈s已经存在。 操作结果:插入元素e为新的栈顶元素 Pop(&s,&e) 初始条件:栈s已经存在且非空。 操作结果:删除s的栈顶元素,并用e返回其值 开始 读下一个字符算法 实现提示 程序流程图(图9-3程序流程图),读入下一字符,建立栈,存放操作字符,存放数据,表达式求值算法,结束,计算,开始,factor算法,9.7 哈夫曼编译码器,问题描述利用哈夫曼编码进行通信可以大大提高信道利用率,缩短信息传输时间,降低传输成本。但是,这要求在发送端通过一个编码系统对待传数据预先编码,在接收端将传来的数据进行译码(复原)。对于双工信道(即可以双向传输信息的信道),每端都需要一个完整的编/译码系统。试为这样的信息收发站写一个哈夫曼码的编/译码系统。,基本要求一个完整的系统应具有以下功能: 1:初始化(Initialization)。从终端读入字符集大小n,以及n个字符和n个权值,建立哈夫曼树,并将它存于文件hfmTree中。 2:编码(Encoding)。利用已建好的哈夫曼树(如不在内存,则从文件hfmTree中读入),对文件ToBeTrans.txt(若原来该文件不存在,则可先手工建立该文件,其内容是要编码的字符串,如下面的的“THIS PROGRAM IS MY FAVORITE”)正文进行编码,然后将结果存入文件CodeFile中。 3:译码(Decoding)。利用已建好的哈夫曼树将文件CodeFile中的代码进行译码,结果存入文件TextFile中。 4:印代码文件(Print)。将文件CodeFile以紧凑格式显示在终端上,每行50个代码。同时将此字符形式的编码文件写入文件CodePrin中。 5:印哈夫曼树(Tree printing)。将已在内存中的哈夫曼树以直观的方式(树或凹入表形式)显示在终端上,同时将此字符形式的哈夫曼树写入文件TreePrint中。,实现提示 (1)利用下面这道题中的数据调试程序。 某系统在通信联络中只可能出现八种字符,其概率分别为0.25,0.29,0.07,0.08,0.14,0.23,0.03,0.11,试设计哈夫曼编码。 (2)用下表给出的字符集和频度的实际统计数据建立哈夫曼树,并实现以下报文的编码和译码:“THIS PROGRAM IS MY FAVORITE”。 字符 空格 A B C D E F G H I J K L M 频度 186 64 13 22 32 103 21 15 47 57 1 5 32 20 字符 N O P Q R S T U V W X Y Z 频度 57 63 15 1 48 51 80 23 8 18 1 16 1

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论