各位学长学姐:
你们好,我们这周要交三个实验的编译程序,关于数组、链表和树,麻烦你们帮我看看,如果能编出来,我真是感激涕零呀,周四就要交,十万火急!!!
实验一 使用数组
问题描述
根据老师给出的Array和SeqList基于模板的类的说明,编写主程序使用该抽象类。
实验目的
熟悉C++语言的基本编程,学习并理解模板类,掌握集成编译环境的基本使用。
基本要求
1 读懂给出的Array和SeqList抽象类。
2 编写主程序生成SeqList类的实例数组。
3 编写程序使用SeqList的各个成员函数,完成下述功能。
测试数据
1 向空表中依次添加数据1、2、3、4、5、6、7、8、9、10,打印表中数据。
2 删除第3、6个数据,打印表中数据。
3 在第3和第6个位置后分别添加数据11、12,打印表中数据。
4 在表中搜索值为7和13的数据,并打印该数据在表中的下标。
5 从表尾向表头方向依次删除数据,每删除一个数据打印一次表中数据,直到表空为止。
选作内容
以上的每一步都使用调试器跟踪正在处理的数据所处的内存地址,加深对数组和内存的相关关系的理解。
实验二 链表
问题描述
设计一个一元稀疏矩阵多项式简单计算器。(提示:用带表头节点的单链表存储多项式,多项式的项数存放在头节点。)
实验目的
掌握链表的使用(重点掌握指针的使用)。
基本要求
一元稀疏多项式简单计算器的基本功能是:
(1) 输入并建立多项式;
(2) 输出多项式,输出形式为整数序列:n,c1,e1,c2,e2,…,cn,en,其中n是多项式的项数,ci和ei分别是第i项的系数和指数,序列按指数降序排列;
(3) 多项式a和b相加,建立多项式a+b;
(4) 多项式a和b相减,建立多项式a-b;
测试数据:
(1)(2x+5x3-3.1x11) + (7-5x8+11x9) = (-3.1x11+11x9+2x+7)
(2)(6x-3-x+4.4x2-1.2x9) – (-6x-3+5.4x2-x2+7.8x15) = (-7.8x15-1.2x9+12x-3-x)
(3)(1+x+x2+x3+x4+x5) + (-x3-x4) = (1+x+x2+x3)
(4)(x+x3) + (-x-x3) = 0
(5)(x+x100) + (x100+x200) = (x+2x100+x200)
(6)(x+x2+x3) + 0 = (x+x2+x3)
(7)互换以上各组数据中的前后两个多项式
选作内容
(1) 计算多项式在x处的值
(2) 求多项式a的导数
(3) 多项式相乘
实验三 树(哈夫曼编/译码器)
问题描述
利用哈夫曼编码进行通信可以大大提高信道利用率,缩短信息传输时间,降低传输成本。但是,这要求在发送端通过一个编码系统对待传数据预先编码,在接收端将传来的数据进行译码。对于双工信道(即可以双向传输信息的信道),每端都需要一个完整的编/译码系统。试为这样的信息收发站写一个哈夫曼码的编/译码系统。
基本要求
一个完整的系统应具有以下功能:
(1)I:初始化(Initialization)。从终端读入字符集大小n,以及n个字符和n个权值,建立哈夫曼树,并将它存于文件hfmTree中。
(2)E:编码(Encoding)。利用已经建好的哈夫曼树(如不在内存,则从文件hfmTree中读入),对文件ToBeTran中的正文进行编码,然后将结果存入文件CodeFile中。
(3)D:译码(Decoding)。利用已经建好的哈夫曼树将文件CodeFile中的代码进行译码,结果存入文件TextFile中。
(4)P:打印代码文件(Print)。将文件CodeFile以紧凑格式显示在终端上,每行50个代码。同时将此字符形式的编码文件写入文件CodePrint中。
(5)T:显示哈夫曼树(Treeprinting)。将已经在内存中的哈夫曼树以直观的方式(树或凹入表形式)显示在终端上,同时将此字符形式的哈夫曼树写入文件TreePrint中。
测试数据
用下表给出的字符集和频度的实际统计数据建立哈夫曼树,并实现以下报文的编码和译码:“I LOVE DATA STRUCTURE, I LOVE PROGRAMING"。
字符 |
A B C D E F G H I J K L M |
频度 |
186 64 13 22 32 103 2l 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 5l 80 23 8 18 1 16 l |
实现提示
(1)用户界面可以设计为“菜单”方式:显示上述功能符号,再加上“Q”选项,表示退出(Quit)。用户可以键入一个选择功能符。此功能执行完毕后再显示此菜单,直至某次用户选择了“Q”为止。
(2)在程序的一次执行过程中,第一次执行I,D或C命令之后,哈夫曼树已经在内存了,不必再读入。每次执行中不一定执行I命令,因为文件hfmTree可能早已建好