09级数据结构课程设计题目.docVIP

停车场模拟管理程序的设计与实现 1．设计目的 理解线性表的逻辑结构和存储结构，进一步提高使用理论知识指导解决实际问题的能力。 2．问题描述 设停车场只有一个可停放几辆汽车的狭长通道，只有一个大门可供汽车进出。汽车在停车场内按车辆到达的先后顺序依次排列，若车场内已停满几辆汽车，则后来的汽车只能在门外的便道上等候，一旦停车场内有车辆开走，则排在便道上的第一辆汽车即可进入；当停车场内某辆汽车要开走时，由于停车场是狭长的通道，在它之后开入的车辆必须先推出车场为他让路，待车辆开出大门，为他让路的车辆再按原次序进入车场。试设计这样一个停车场模拟管理程序。 3．数据结构设计 （1）为了便于区分每辆汽车并了解每辆车当前所处的位置，需要记录汽车的牌照号码和汽车当前的状态。 （2）为了便于停车场的管理，要为每个车位分配一个固定的编号。 （3）当停车场的停车位上都已停满了汽车，又有新的汽车到来时要把它调度到便道上，便道上的车辆要按照进入便道的先后顺序顺次序放在便道上，为便道上的每个位置分配一个固定的编号。当有车从停车位上离开后，便道上的第一辆汽车就立即进入停车位上的某个车位。 （4）当某辆车离开停车场的时候，比他后进停车位的车要为他让路，而且当他开走之后让路的车还要按照原来的停放次序再次进入停车位的某个车位上，为完成这项功能，定义一个结构体。 4．功能（函数）设计 本程序从总体上分为四个功能模块，分别为： （1）程序功能介绍和操作提示模块 （2）汽车进入停车位的管理模块 （3）汽车离开停车位的管理模块 （4）查看停车场状态的查询模块 5．界面设计 6．编码实现 7．运行与测试 （1）连续有7辆汽车到来，牌照号分别为CF001、CF002、CF003、CF004、CF005、CF006、CF007，前5辆车应该进入停车位1－5车位，第6、7辆车应停入便道的1、2位置上。 （2）上面（1）中的情况发生后，让牌照CF003的汽车从停车场开走，应显示CF005、CF004的让路动作和CF006从便道到停车位的动作。 （3）随时检查停车位和便道的状态，不应该出现有空位而便道上还有车的情况。 （4）其它正常操作的一般情况。 8．设计完成后的思考 哈夫曼编/译码的设计与实现 实验目的： 通过对简单哈夫曼编/译码系统的设计与实现来熟练掌握树型结构在实际问题中的应用。 问题描述： 利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码。系统应该具有如下的几个功能：接收原始数据、编码、译码、打印编码规则。 数据结构设计： 构造哈夫曼树时使用顺序表作为哈夫曼树的存储结构。 求哈夫曼编码时使用一维结构数组作为哈夫曼编码信息的存储。 功能（函数）设计 初始化功能模块 模块的功能为从键盘接收字符集大小n，以及n个字符和n个权值。 建立哈夫曼树的功能模块 此模块功能为使用1中得到的数据按照构造哈夫曼树的算法构造哈夫曼树，即将HuffNode数组中的各个位置的各个域都添上相关的值，并将这个结构体数组存于文件中。 建立哈夫曼编码的功能模块 此模块功能为从文件中读入相关的字符信息进行哈夫曼编码，然后将结果存入，同时将字符与0、1代码串的一一对应关系打印到屏幕上。 译码的功能模块 此模块功能为接收需要译码的0、1代码串，按照3中建立的哈夫曼编码规则将其翻译成字符集中的字符所组成的字符串形式，存入文件，同时将翻译的结果在屏幕上打印输出。 界面设计 编码实现 运行与测试 利用下列数据调试程序：令叶子结点个数n为4，权值集合为{1,3,5,7}，字符集合为{A,B,C,D}，并有如下对应关系，A——1、B——3、C——5、D——7，调用初始化功能模块可以正确接收这些数据；调用建立哈夫曼树的功能模块，构造静态链表HuffNode的存储；调用建立哈夫曼编码的功能模块，在屏幕上显示如下对应关系： A——111、B——110、C——10、D——0；调用译码的功能模块，输入代码串“111110100”后，屏幕上显示译码结果：111110100——ABCD 2、 用下表给出的字符集和频度的实际统计数据建立哈夫曼树，并实现以下报文的编码和译码：“THE 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