首页 考试资料幻灯片工程技术公务员考试小学教学中学教学大学教学外语资料
数据结构实验书


file

%s",Fname);

"%d%s",&temp.arrive,&temp.treat);

/*约定每轮循环,处理一位客户*/ if(front==NULL && have==2){ /*等待队列为空,但还有客户*/

dwait+=temp.arrive-clock; /*累计业务员总等待时间*/ clock=temp.arrive; /*时钟推进到暂存变量中的客户的到达时间*/ /* 暂存变量中的客户信息进队*/

EnQueue(&front,&rear,temp); have=fscanf(fp, } count++;

"%d%d",&temp.arrive,&temp.treat);

/*累计客户人数*/

DeQueue(&front,&rear,&curr);/*出队一位客户信息*/ wait+=clock-curr.arrive; /*累计到客户的总等待时间*/

finish=clock+curr.treat;/*设定业务办理结束时间;*/ while(have==2 && temp.arrive<=finish){

/*下一位客户的到达时间在当前客户处理结束之前*/ EnQueue(&front,&rear,temp);/* have=fscanf(fp, } clock=finish; }while(have==2 || /* 时钟推进到当前客户办理结束时间*/ 暂存变量中的客户信息进队*/

"%d%d",&temp.arrive,&temp.treat);

front!=NULL);

printf("结果:业务员等待时间%dn 客户平均等待时间%fn",dwait, (double)wait/count); printf("模拟总时间:%d,n 客户人数:%d,n 总等待时间:%dn",clock, count,wait); getch(); }/*main_end*/’ 【测试数据】

设数据装在一个数据文件 data.dat 中,内容为:10 6 显示结果为:enter 结果:业务员等待时间 10 客户平均等待时间 1.5 模拟总时间:24,客户人数:2, 【说明】 总等待时间:3 file name:data.dat

13 8

在计算程序中,程序按模拟环境中的事件出同顺序逐一处理事件:当一个事件结束时,下一个事 件隔一段时间才发生,则程序逻辑的模拟时钟立即推进到下一事件的发生时间;如一个事件还未处理结束 之前,另有其他事件等待处理,则这些事件就应依次排队等候处理。 【实验题】 进行医务室模定。假设只有一个医生,在一小时内随机地来几个病人,每个病人所需处理时间为 1—9 分钟 之间某个随机数。要求程序模拟统计在设定时间内,医生的总空闲时间和病人的平均等待时间。

第五节 思考题

1. 背包问题。假设有一个背包可装入总重量为 T 的物件。现在 n 个物件,其重量分别为 w1,w2,?,wn,问 能否从这 n 个物件中选择若干件放入背包,使它们的重量之和恰为 T。若能找到满足上述条件的一组解, 则称此问题有解,否则无解。 【简要分析】此题有两种解法,可用递归算法或非递归算法。 可以采用这样的选取方法:n 个物件中选取一个 wi,得到剩下的重量为:S=T-wi,则判断 S 的值,若 S=0, 则已找到一种解,完成;若 S<0,则此种解法造成无解,则不选刚才的物件,重选未选取的物件,重新操作; 若 S>0,并且还有未选取的物件,则再选取下一未选取的物件,并按前面的方法继续执行。 对递归算法,若函数 bb(s,n)为背包问题的解法,则不包含物件 wn 时,bb(s,n)的解是 bb(s,n-1),即重量 (指背包中余下的重量)不变,选下一物件;若选取中包含物件 wn 时,bb(s,n)的解是 bb(s-wn,n-1),即 重量减少,并再去选取下一物件。 对非递归算法,需建一堆栈空间,从第一物件选起,选中的就进栈保存,未选中的就跳过,再选下一个合 适的物件进栈。直到使 S 为零,并输出堆栈中的结果,否则输出无解。 2. 操作系统作业调度模拟。 【简要分析】假设有几个作业运行。如果都需要请求 CPU,则可以让作业按先后顺序排队,每当 CPU 处是 完一个作业后,就可以接受新的作业,这时队列中队头的作业先退出进行处理。后来的作业排在队尾。此

题算法跟模拟服务台前的排队现象问题相似,假定只有一个 CPU,但为了防止一个作业占用 CPU 太久,可 规定每个作业一次最长占用 CPU 的时间(称时间片),如果时间片到,作业未完成,则此作业重新进入等 待队列,等到下次占有 CPU 时继续处理。 3. 已知 Ackermann 函数定义如下:

(1)写出 Ack(2,1)的计算过程。 (2)写出计算的非递归算法。 (北京航空航天大学 1999 年硕士生入学考试) )可用(m,n)表示。这样一直循环下去,直到 n=0,则再将(m-1,1)进栈,又循环操作,直到 m=0,则可计 算出栈顶结点的值(即 B=n+1),退栈(栈顶减 1),并将 B 回填到新的栈顶结点。这样按同样的方法去循 环,直到栈空,则最后一次的 B 值就是我们的计算结果。?,n?-1),实际操作时, (m,n)已进栈,则结点(m?, n?)进栈,再求出 Ack(m?,n?= n-1),则又要先将(m?= m,n?)(其中 m?,n?【简要分析】我们借助于栈

来实现非递归算法。栈的作用是:保存调用函数前的实参值,并保存计算出来的各中间值。令要求的结点 为(m,n),则函数 Ack(m,n)求解时,要先求出 Ack(m,n-1),则先将结点(m,n)进栈,而要求解 Ack(m, n-1)函数时,令新结点为(m

第四章
【实验目的】

字符串的应用

1. 熟练掌握字符串的数据类型定义以及字符串的五种基本操作的定义, 并能利用这些基本操作实现字符串 的其他基本操作的方法。 2. 熟练掌握字符串串的定长顺序存储结构上实现字符串的各种操作的方法。 3. 理解字符串的堆分配存储表示以及在其上实现字符串操作的基本方法。 4. 熟练掌握串的基本操作类型的实现方法,其中文本模式匹配方法是一个难点,在掌握了 BF 算法的基础 上理解改进的 KMP 算法。 5. 了解一般文字处理软件的设计方法。

第一节 知识准备
一、 有关串几个重要概念 1. 串(字符串):零个或多个字符组成的有限序列。一般记作 s="a1a2 2. 长度:串中字符的数目 3. 空串:零个字符的串,其长度为零 4. 子串和主串:串中任意个连续的字符组成的子序列称为该串的子串;包含子串的串相应地称为主串,字 符在序列中的序号为该字符在串中的位置。 5. 当两个串的长度相等,并且各个对应位置的字符都相等时称为两串相等。 6. 空格串:由一个或多个空格组成的串‘ ’,同空串是完全不同的。 ?an"(n≥0)

二、 串的抽象数据类型定义 ADT String{ ∈CharacterSet, >| , ∈D, i=1,2,...,n, i=2,...,n} n>=0}

数据对象:D={ | 数据关系:R1={< , 基本操作:

Assign(&s,t) 将串 t 的值赋给串 s Create(&s,ss) 将串 s 的值设定为字符序列 ss Equal(s,t) 判定串 s 和串 t 是否相等 Length(s) 求串 s 的长度

123456789101112131415161718192021222324252627282930

 


 

  【Top

最新搜索

 


 

热点推荐