实验三 串、数组和广义表
[toc]
- 掌握串、数组和广义表的逻辑结构定义和各种存储结构的实现。
- 熟练运用串、数组和广义表的各种存储结构以及各种基本操作。
- 根据实际问题的需要，选择串、数组和广义表适合的存储结构解决问题。
根据教材介绍的失效函数无效匹配问题，修改 KMP 算法中求失效值的函数，解决其中无效匹配问题，提高匹配效率。
在教材介绍的三元组顺序表中，增加加法运算符的重载函数，实现两个矩阵的加法运算。
在教材介绍的十字链表类模板中增加成员函数Transpose()，实现矩阵的转置运算。
在教材介绍的广义链表类模板中增加成员函数reversal()，实现广义表的转置运算。
参照教材中串的顺序存储的类String，设计并实现串的链式存储的类LinkString（简称链串）。在链串中字符串的信息存储在一个带头结点的单链表中。
完成串的定义（函数成员与顺序存储的类String类似）和实现，并完成串的相关函数在串类上的实现。
为了提高存储密度，考虑在链表的一个结点中存放多个字符（例如，放4个字符）。此时需要特别注意如何表示串结束的表示。
在稀疏矩阵的二元组表示中，用一个二元组表（TwElems）存放矩阵的非零元素，其中每个二元组只记录非零元素的列号（col）和元素值（item），且各二元组按行号递增的顺序排列。另外，设一个行指针数组（RowIndex），其第i个元素表示稀疏矩阵中第i行的第一
个非零元素在二元组表中的存放位置。
要求参照教材中三元组顺序表，完成稀疏矩阵的二元组表示类设计和实现。
模仿教材中稀疏矩阵十字链表的类模板 CrossList，设计并实现稀疏矩阵的十字循环 链表的类模板。
在稀疏矩阵的十字循环链表中，每个非零元素用一个结点表示，同一行的非零元素组成一个带头结点的行循环链表，同一列的非零元素组成一个带头结点的列循环链表。第 i 行的表头结点和第 i 列的表头结点可以共享一个结点，而且行、列表头结点也组成一个带头结点（总表头结点）的循环链表。
完成稀疏矩阵十字循环链表模板类的设计和实现，在函数成员中包括矩阵元素的存取，以及矩阵的相加运算。存放元素时，根据给定的下标 i、j，以及元素值 e 存放相应结点的内容；取元素时，根据给定的下标 i、j 到十字循环链表中取相应元素的值。
实现矩阵的相乘运算。
文学研究人员需要统计英文小说中某些词出现的次数和位置。试编写一个实现这一目标的文字统计系统，称为“文学研究助手”。
英文小说存于一个文本文件中，并假设小说中的单词一律不跨行，每行的长度不超过120个字符，待统计的词汇集合要一次输入完毕。要求对英文小说扫描一遍就完成统计工作。程序的输出结果是每个单词的出现次数和出现位置所在行的行号。其格式自行设计。
输入数据包括两部分，第一部分是要统计的单词，不超过 100 个，单词之间用空格分隔；第二部分是被统计的文章，可以考虑把这两部分内容放在一个文件中。
例如：以某一 C++源程序模拟英文小说，用 C++程序设计语言的保留字集作为待统计的词汇集。
对出现在文章中的要统计的单词，输出其在文章中出现的次数和所在的行号。
一个布尔矩阵，如果每一行和每一列的元素和都为偶数，那么这个矩阵就具有奇偶均势特性。下面这个$4\times 4$的矩阵就具有奇偶均势特性。其各行的和分别为：2,0,4 和 2，各列的和分别为：2,2,2 和 2。
编写程序判断矩阵是否具有奇偶均势特性。如果不是奇偶均势矩阵，则判断是否可以改变矩阵的一个元素使其具有奇偶均势特性。如果不是，矩阵被视为是退化的。
矩阵行（列）数
具有奇偶均势特性，则输出"OK"。
若可以通过改变一个元素使其具有奇偶均势特性，则输出"Change bit(i, j)"，其中(i, j)是要改变的行、列位置值。
否则输出"Corrupt"。
设计并实现 m 元多项式的表示和运算。具体功能如下：
- 输入功能，输入一个 m 元多项式，并在计算机上存储；
- 计算功能，对任意输入的一组 m 元值，能够计算出 m 元多项式的值；
- 加法功能，能够实现两个 m 元多项式的加法运算；
- 求导功能，实现 m 元多项式中对指定变元的一阶导数的运算。
- 显示功能，按常规显示 m 元多项式。
利用广义表实现 m 元多项式的表示，提供一个简易菜单方便对各种功能的调用。