⒈ 实验提示:
用静态链表来实现,结构定义如下: CONST maxsize=最大单元数; K=堆栈的个数; TYPE node=RECORD data:elemtp; next:0..maxsize END;
VAR s:ARRAY[1..maxsize] OF node; Top:ARRAY[1..K] OF 0..maxsize; Sp:0..maxsize;
⑴ 初始状态,将数组s构成一个静态链表,即用next域将1单元到maxsize单元连起来,将s看成为一个空闲单元栈,栈顶指针为sp,初始状态sp=1;
⑵ 每个堆栈的栈顶指针初值为零,即top[i]=0,I=1,2,3,…,k。当对第I个栈进行压栈时,先看空闲单元栈是否为空,也即sp是否为0,如果sp为0 ,则无空闲单元,产生上溢,否则,从空闲单元栈中分配一个单元给第i个栈,该单元作为第i个栈的新的栈顶;
⑶ 当对第i个栈进行弹栈操作时,若top[I]=0,则产生下溢,否则,从第 i个栈顶弹掉一个元素,并将空间释放到空闲单元堆栈中(空间的回收)。其它对堆栈的操作类似可以实现。
⒉ 思考题:如果采用动态链接结构实现堆栈,则对堆栈的压栈和弹栈操作有何特点,何时发生溢出,并比较这两种方法的各自特点。
实 验 四 模拟旅馆管理系统的一个功能——床位的分配与回收
题目:模拟旅馆管理系统的一个功能——床位的分配与回收
⒈ 问题描述:
某旅馆有n个等级的房间,第I等级有ai 个房间,每个等级有bi个床位(1≤I≤n)。试模拟旅馆管理系统中床位分配和回收的功能,设计能为单个旅客分配床位,在其离店便回收床位(供下次分配)的算法。
⒉ 基本要求 (1)输入数据
分配时,输入旅客姓名、年龄、性别、到达日期和所需房间等级。 回收时,输入房间等级、房间号和床位号。 2)输出数据
26
分配成功时打印旅客姓名、年龄、到达日期、房间等级、房间号码和床位号码。 分配不成功时,如所有等级均无床位,则打印“客满”信息;如旅客需要的等级均无空床位,则打印“是否愿意更换等级?”的询问信息。若旅客愿意更换,则重新输入有关信息,再进行分配,否则分配工作结束。
⒊ 实现提示
(1)数据结构
主要采用顺序结构链接结构的线性表及堆栈。 a) 性别 其中,性别:0表示房间为空状态 1表示房间分配给女旅客 2表示房间分配给男旅客 现有空床数:数据在0~床数为
每个房间用一个如下所示的具有五个字段的结点(房结点)表示: 房间号 现有空床数 BTOP RLINK bi 之间,其中bi是第I等级一个房间 的床位数,当现有空
bi时,表示房间为空;为0时,表示房间满。
RLINK:当房间空时,用作空房栈的连接;当房间不空时,指向下一个房结点。 BTOP:指向该房间的空床号栈栈顶。一个房间对应一个顺序表示的空床号栈。栈的容量为
bi,栈中存放空床号。分配时,从栈顶取出空床号,栈顶下移(BTOP=BTOP+1);
回收时,栈顶上移(BTOP=BTOP-1),将回收的空床号填入栈顶。
每一个等级中的空房间构成一个空房栈;已住旅客的房间构成一个链栈(简称房链),其头结点结构如下:
可分配女床位总数 可分配男床位总数 其中:
ai bi TTOP RLINK ai:第I等级中房间总数 bi第I等级中每个房间的床位数
ai*bi ,因为开始时所有房间和床位既可以分配
可分配男、女床位的总数的初值等于
给男旅客,也可以分配给女旅客。当在房链中分配一个床位给男(女)旅客,床位总数应减1;当从空房栈中取出一个房间作为男(女)旅客房间时,则可分配女(男)床位总数应减
bi,当回收一个男(女)床位时,则可分配男(女)床位总数应加1;当回收一个男
bi。
(女)空房至空房栈时,则可分配女(男)床位总数应加
27
TTOP:指向本级空房栈栈顶,当无空房间时,TTOP=^(NIL)。 RLINK:指向本级房链第一个顶点,当房链为空时,RLINK=^(NIL) 顺序表s=(
s0,s1,...,si,...,sm),其中,
s1~sn顺序存放第1~n等级房间的头结点;
s0 存放内容如下所示:
全店可分配女床总数 初始时,全店可分配男、女床总数相同,均为
全店可分配女床总数 0 0 ^ ^ ?aii*bi ,在分配或回收时,对各等
级可分配男(女)床位总数处理的同时也要对全店可分配男(女)床总数作相应处理,当全店可分配男(女)床总数等于零时,表示客满。
(2)算法设计思想(略)
实 验 五 串编辑
题目:串编辑
⒈问题描述:本题目中的串编辑要求对串实现以下三种功能:
⑴插入:把一个字符串插入到给定串的指定位置 ⑵删除:将串中某指定位置开始的若干字符从串中删除 ⑶置换:用一串字符置换给定串中某指定位置开始的若干字符 ⒉基本要求
⑴ 输入要求:首先输入功能标志符,表明要求实现何种功能,然后再输入有关数据
①输入I,表示要求输入;然后输入插入的起始位置和要插入的字符串 ②输入D,表示要求删除;然后输入删除的起始位置和删除长度
③输入R,表示要求置换 ;然后输入置换的起始位置、置换长度和将要换入的字符串
④输入E,结束串编辑。 ⑵ 输出数据:
功能不同输出的数据不同,主要有以下几种数据:功能标志符、起始位置、删除长度、插入或置换的字符串和经过运算后的字符串。
⒊实现提示 ⑴ 数据结构
① 结点结构:一个结点由DATA和LINK两个字段组成,如下所示:
28
DATA 在DATA字段中存放一个字符
LINK ② 字符串结构:用一个单循环链表表示一个字符串,如,T=‘ABCD’串可以由下面的单链循环表来表示:
A B C D T T指向循环链表的表尾。
③ 插入或置换子串的结构:用一个单链表表示要插入的子串,tp为头指阵,bn为尾指针,如:
④
1 2
tp
a)插入
·输入插入起始位置 ·构造插入子串
3 bn ⑵算法基本思想:算法开始时给出一个空串,用户可以在此基础上进行编辑。
·实现插入 ·打印输出插入后的子串 b) 删除
·输出删除起始位置和删除长度 ·实现删除 ·打印输出删除后的字符串 c)置换
·输入置项起始位置和被置换长度(类似删除长度) ·构造被置换子串(类似插入子串) ·调用删除过程,删除被置换的字符 ·调用插入过程,插入置换子串 d)结束串编辑,终止编辑过程
实 验 六 哈夫曼编码
题目:哈夫曼编码
29
1.问题描述
设某编码系统共有n个字符,使用频率分别为{w1,w2,?,wn},设计一个不等长的编码方案,使得该编码系统的空间效率最好。
2.基本要求 (1)设计数据结构; (2)设计编码算法;
(3)分析时间复杂度和空间复杂度。 3.设计思想
利用Huffman编码树求得最佳的编码方案。
根据哈夫曼算法,建立哈夫曼树时,可以将哈夫曼树定义为一个结构型的一维数组HuffTree,保存哈夫曼树中各结点的信息,每个结点包括权值、左孩子、右孩子和双亲,如图所示。由于哈夫曼树中共有2n-1个结点,并且进行n-1次合并操作,所以该数组的长度为2n-1。
weight lchild rchild parent 图 哈夫曼树的结点结构 构造哈夫曼树的伪代码如下: 伪代码
1.数组Huffrree初始化,所有元素结点的双亲、左右孩子都置为-1; 2.数组HufffTree的前n个元素的权值置给定权值w[n]; 3.进行n-1次合并
3.1在二叉树集合中选取两个权值最小的根结点,其下标分别为i1,i2; 3.2将二叉树i1、i2合并为一棵新的二叉树k;
在哈夫曼树中,设左分支为0。,右分支为1,从根结点出发,遍历整棵哈夫曼树,求得各
个叶子结点所表示字符的哈夫曼编码。
思考题:对于采用哈夫曼编码树进行的编码,如何设计解码算法?
实 验 七 交通问题系统
题目:交通问题系统
1.问题描述:
已知某市每条公共路线及沿途所经站名,试设计一个问路程序,用户可以在任一车站通过终端询问知道:
⑴ 是否有公共汽车到达指定的目的地?
30
百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读,免费范文网,提供经典小说综合文库数据结构实验指导书(6)在线全文阅读。
相关推荐: