实验一 使用数组

问题描述

根据老师给出的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,c₁,e₁,c₂,e₂,…,c_n,e_n,其中n是多项式的项数，ci和ei分别是第i项的系数和指数，序列按指数降序排列；

（3） 多项式a和b相加，建立多项式a+b；

（4） 多项式a和b相减，建立多项式a-b;

测试数据：

（1）(2x+5x³-3.1x¹¹) + (7-5x⁸+11x⁹) = (-3.1x¹¹+11x⁹+2x+7)

（2）(6x^-3-x+4.4x²-1.2x⁹) – (-6x^-3+5.4x²-x²+7.8x¹⁵) = (-7.8x¹⁵-1.2x⁹+12x^-3-x)

（3）(1+x+x²+x³+x⁴+x⁵) + (-x³-x⁴) = (1+x+x²+x³)

（4）(x+x³) + (-x-x³) = 0

（5）(x+x¹⁰⁰) + (x¹⁰⁰+x²⁰⁰) = (x+2x¹⁰⁰+x²⁰⁰)

（6）(x+x²+x³) + 0 = (x+x²+x³)

（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"。

实现提示

（1）用户界面可以设计为“菜单”方式：显示上述功能符号，再加上“Q”选项，表示退出（Quit）。用户可以键入一个选择功能符。此功能执行完毕后再显示此菜单，直至某次用户选择了“Q”为止。

（2）在程序的一次执行过程中，第一次执行I，D或C命令之后，哈夫曼树已经在内存了，不必再读入。每次执行中不一定执行I命令，因为文件hfmTree可能早已建好