3.数据结构-串、数组和广义表

3.1串

串是由零个或多个字符组成的有限序列，一般记为$s="a_1{a}_2...a_n"(n\ge 0)$，其中s是串的名，用双引号括起来的字符序列是串的值；$a_i(1\le i\le n)$可以是字母、数字或其他字符；串中字符的数目n称为串的长度。零个字符的串称为空串，其长度为0。

串中任意个连续的字符组成的子序列称为该串的子串。包含子串的串相应地称为主串。通常称字符在序列中的序号为该字符在串中的位置。

称两个串是相等的，当且仅当这两个串的值相等，也就是说，只有当这两个串的长度相等并且各个对应位置的字符都相等时才相等。而由一个或多个空格组成的串“ ”称为空格串。

3.1.1串的类型定义、存储结构及其运算

串的顺序存储

类似于线性表的顺序存储结构，用一组地址连续的存储单元存储串值的字符序列。按照预定义的大小，为每个定义的串变量分配一个固定长度的存储区，可以用定长数组描述：

typedef struct{char ch[MAXLEN+1];int length; //字符串当前长度
}SString;

完整操作

#include<iostream>#define MAXLEN 255
#define QElemType int
#define Status intusing namespace std;typedef struct{char ch[MAXLEN+1];int length;
}SString;void StrAssign(SString &T, string chars){//将chars的值赋给Tint len = T.length < MAXLEN ? T.length : MAXLEN;for(int i = 0; i < len; i ++){T.ch[i] = chars[i];}T.length = len;T.ch[len] = '\0';  // 确保以空字符结尾
}void StrCopy(SString &T, SString &S){//由串S复制得串Tint len = S.length < MAXLEN ? S.length : MAXLEN;for(int i = 0; i < len; i ++){T.ch[i] = S.ch[i];}T.length = S.length;T.ch[len] = '\0';  // 确保以空字符结尾
}bool StrEmpty(SString T){return T.length > 0;
}Status StrCompare(SString &T, SString &S){//若S>T返回值>0,S=T返回0,S<T返回<0int minLength = (T.length < S.length) ? T.length : S.length;// 逐字符比较for (int i = 0; i < minLength; i++) {if (T.ch[i] != S.ch[i]) {return T.ch[i] - S.ch[i];  // 返回 ASCII 差值}}// 若前面字符都相等，则比较长度return T.length - S.length;
}int main()
{SString T, S;string chars;getline(cin, chars);StrAssign(S, chars);cout << S.ch << endl;StrCopy(T, S);cout << T.ch << endl;cout << StrEmpty(T) << endl;cout << StrCompare(S, T) << endl;return 0;} 

这种存储方式是静态的存储的大小是固定了的，而在实际过程中我们需要动态的分配和释放字符数组空间。

串的堆式顺序存储结构

在C语言中，存在一个称之为**“堆（Heap）”**的自由存储区，可以为每个新产生的串动态分配一块实际串长所需要的存储空间，若分配成功，则返回一个指向起始地址的指针，作为串的基址。

typedef struct{char *ch; //若为非空串，则按串长分配存储区，否则ch为NULLint length; //串的当前长度
}HString;

完整操作

#include<iostream>
#include<cstring>#define MAXLEN 255
#define QElemType int
#define Status intusing namespace std;typedef struct{char *ch; //若为非空串，则按串长分配存储区，否则ch为NULLint length; //串的当前长度
}HString;void StrAssign(HString &T, string chars) {// 释放 T 原有的内存，避免内存泄漏if (T.ch != NULL) {delete[] T.ch;T.ch = NULL;}// 获取 chars 长度T.length = chars.length();// 若 chars 为空，则 T.ch 设为 NULLif (T.length == 0) {T.ch = NULL;return;}// 动态分配空间存储 chars，并复制字符串T.ch = new char[T.length + 1];  // +1 预留 '\0' 结尾符strcpy(T.ch, chars.c_str());    // 拷贝字符串
}// 复制串 S 到 T
void StrCopy(HString &T, HString &S) {// 先释放 T 原有的内存，避免内存泄漏if (T.ch != NULL) {delete[] T.ch;T.ch = NULL;}// 复制长度T.length = S.length;// 若 S 为空串，则 T 也设为空串if (S.length == 0 || S.ch == NULL) {T.ch = NULL;return;}// 分配新空间并复制内容T.ch = new char[T.length + 1]; // 额外 +1 以存放 '\0'strcpy(T.ch, S.ch);  // 拷贝字符串
}Status StrCompare(HString &T, HString &S) {int minLength = (T.length < S.length) ? T.length : S.length;  // 找到最短的长度// 逐字符比较for (int i = 0; i < minLength; i++) {if (T.ch[i] != S.ch[i]) {return T.ch[i] - S.ch[i];  // 返回字符 ASCII 差值}}// 如果前面所有字符都相等，则比较字符串的长度return T.length - S.length;  // 长度更长的字符串较大
}int main()
{HString T, S;T.ch = NULL, S.ch = NULL;T.length = 0, S.length = 0;string chars;getline(cin, chars);StrAssign(S, chars);cout << S.ch << endl;StrCopy(T, S);cout << T.ch << endl;return 0;} 

串的链式存储

顺序串的插入和删除操作都不方便，需要移动大量的字符。因此，可采用单链表方式存储，每一个结点可以存放一个字符，也可以放多个字符。当结点大小大于1时，由于串长不一定是结点大小的整数倍，则链表中的最后一个结点不一定全倍串值占满，此时通常补上**“#”**或其他的非串值字符。
为了便于进行串的操作，当以链表存储串值时，除头指针外，还可以附设一个尾指针指示链表中的最后一个结点，并给出当前串的长度。

typedef struct Chunk{char ch[MAXLEN];struct Chunk *next;
};typedef struct{Chunk *head, *tail;int length; //串的当前长度
}LString;

完整操作

#include<iostream>
#include<cstring>#define MAXLEN 255
#define QElemType int
#define Status intusing namespace std;typedef struct Chunk{char ch[MAXLEN];struct Chunk *next;
};typedef struct{Chunk *head, *tail;int length; //串的当前长度
}LString;void StrAssign(LString &T, string chars) {// 初始化链表, T.head = T.tail = nullptr;T.length = 0;int charsLeft = chars.length();int currentIndex = 0;// 分段将字符串 chars 存入链表while (charsLeft > 0) {// 计算当前块存储的字符数量（最多 MAXLEN）int chunkLength = (charsLeft > MAXLEN) ? MAXLEN : charsLeft;// 创建新的 ChunkChunk *newChunk = new Chunk;for (int i = 0; i < chunkLength; ++i) {newChunk->ch[i] = chars[currentIndex + i]; // 填充字符}newChunk->ch[chunkLength] = '\0'; // 确保以 '\0' 结尾newChunk->next = nullptr; // 最后一个块的 next 指向 nullptr// 将 newChunk 加入链表if (T.tail == nullptr) {T.head = T.tail = newChunk; // 链表为空时，head 和 tail 都指向 newChunk} else {T.tail->next = newChunk;  // 将 newChunk 添加到尾部T.tail = newChunk;         // 更新尾指针}// 更新剩余字符数, chars可能会大于MAXLEN,但是每个字节最多存储MAXLEN,所以要分段currentIndex += chunkLength;charsLeft -= chunkLength;T.length += chunkLength; // 更新链表的总长度}
}void PrintLString(LString &T) {Chunk *current = T.head;while (current != nullptr) {cout << current->ch; // 打印当前 Chunk 存储的字符current = current->next; // 移动到下一个 Chunk}cout << endl;
}void StrInsert(LString &S, int pos, LString T) {if (pos < 0 || pos > S.length) {cout << "插入位置无效！" << endl;return;}// 如果要插入的位置是0，直接将 T 插入到 S 的开头if (pos == 0) {T.tail->next = S.head;S.head = T.head;if (S.tail == nullptr) { // 如果 S 本来是空链表，更新尾指针S.tail = T.tail;}S.length += T.length;return;}// 定位到插入位置前的节点Chunk *current = S.head;int currentPos = 0;while (current != nullptr && currentPos < pos - 1) {current = current->next;currentPos++;}// 插入操作if (current != nullptr) {// 将 S 的第 pos 位置分成两部分Chunk *nextChunk = current->next;// 插入 T 到当前节点后面current->next = T.head;T.tail->next = nextChunk;// 如果插入的位置是链表末尾，更新 S 的尾指针if (nextChunk == nullptr) {S.tail = T.tail;}S.length += T.length;}
}void StrDelete(LString &S, int pos, int len) {// 检查删除位置是否合法if (pos < 0 || pos >= S.length || pos + len > S.length) {cout << "删除位置无效！" << endl;return;}Chunk *current = S.head;Chunk *prev = nullptr;int currentPos = 0;// 遍历到要删除的起始位置while (current != nullptr && currentPos < pos) {prev = current;current = current->next;currentPos++;}// `prev` 现在是待删除部分前一个节点，`current` 是待删除部分的第一个节点Chunk *deleteStart = current;// 遍历到删除的结束位置while (current != nullptr && currentPos < pos + len) {Chunk *temp = current;current = current->next;delete temp;  // 释放当前节点的内存currentPos++;}// 连接删除后的部分if (prev != nullptr) {prev->next = current;  // 如果删除的不是从头开始，更新前一个节点的指针} else {S.head = current;  // 如果删除的是从头开始，更新头指针}// 如果删除的部分在尾部，需要更新尾指针if (current == nullptr) {S.tail = prev;}// 更新链表的长度S.length -= len;
}int main()
{LString S, T;string chars;getline(cin, chars);StrAssign(S, chars);PrintLString(S);// 	StrInsert(T, 1, S);
// 	PrintLString(T);StrDelete(S, 1, 3);PrintLString(S);return 0;} 

3.1.2 串的模式匹配算法

子串的定位运算通常称为串的模式匹配或串匹配。
串的模式匹配设有两个字符串S和T，设S为主串，也称正文串；设T为子串，也称为模式。在主串S中查找与模式T相匹配的子串，如果匹配成功，确定相匹配的子串中的第一个字符在主串S中出现的位置。

BF算法

模式匹配不一定是从主串的第一个位置开始，可以指定主串中查找的起始位置pos。如果采用字符串顺序存储结构，可以写出不依赖于其他串操作的匹配算法。
【算法步骤】
1.分别利用计数指针i和j指示主串S和模式T中当前正待比较的字符位置，i初值为pos，j的初值为；
2.如果两个串均未比较到串尾，即i和j均分别小于等于S和T的长度时，则循环执行一下操作：

• S[i].ch和T[j].ch比较，若相等，则i和j分别指示串中下个位置，继续比较后续字符
• 若不等，指针后退重新开始匹配，从主串的下一个字符$(i=i-j+2)$起再重新和模式的第一个字符$(j=1)$比较。（为什么是$(i=i-j+2)$，因为从i开始长度为j的这段子串与模式T是不匹配的，直接从这个子串的下一个字符开始比较）

3.如果j>T.length，说明模式T中的每个字符依次和主串S中的一个连续的字符序列相等，则匹配成功，返回和模式T中第一个字符相等的字符在主串S中的序号$(i-T.length)$；否则匹配不成功。

#include<iostream>#define MAXLEN 255
#define QElemType int
#define Status intusing namespace std;typedef struct{char ch[MAXLEN+1];int length;
}SString;void StrAssign(SString &T, string chars){//将chars的值赋给Tint len = chars.length();for(int i = 0; i < len; i ++){T.ch[i] = chars[i];}T.length = len;T.ch[len] = '\0';  // 确保以空字符结尾
}int Index_BF(SString S, SString T, int pos){int i = pos, j = 0;while(i < S.length && j < T.length){if(S.ch[i] == T.ch[j]){++i, ++j;}else{i = i - j + 1;j = 0;}}if(j >= T.length) return i-T.length;else return -1;
}int main()
{SString T, S;string chars;getline(cin, chars);StrAssign(S, chars);getline(cin, chars);StrAssign(T, chars);int indexx = 0;for(int i = 0; i < S.length; i ++){indexx = Index_BF(S, T, i);if(indexx+1 > 0){cout << indexx+1 << endl;break;}}return 0;} 

代码与上述描述不一样的$i-j+2$是因为描述时默认下标为1开始，实际是从0开始的。
BF算法最快的情况下就是$O(n+m)$，最坏的情况下的平均时间复杂度则是$O(n\ast m)$，可以看出时间复杂度还是较高，接下来介绍另一种改进的模式匹配算法。

*KMP算法（待更新）

此算法可以在$O(n+m)$的时间数量级完成串的模式匹配操作。其改进在于：每当一趟匹配过程中出现字符比较不等时，不需要回溯$i$指针，而是利用已经得到的“部分匹配”的结果将模式向右“滑动”尽可能远的一段距离，继续进行比较。

博主也看了很久才逐渐明白，起始本质就是求最长前后公共缀。看完书后然后找了一个博客很有参照性链接: 如果没懂强烈推荐去看

void get_next(string T, int next[])
{int i = 1;next[1] = 0;int j = 0;while (i < T.length()){if (j == 0 || T[i] == T[j]){++i;++j;next[i] = j;}elsej = next[j];}
}void get_nextval(string T, int nextval[])
{int i = 1;nextval[1] = 0;int j = 0;while (i < T.length()){if (j == 0 || T[i] == T[j]){i++;j++;if (T[i] != T[j])nextval[i] = j;elsenextval[i] = nextval[j];}elsej = nextval[j];}
}int Index_KMP(string S, string T, int pos)
{//利用模式串T的next函数求T在主串S中第pos个字符之后的位置//其中T非空，1<=pos<=S.lengthint i = pos; int j = 1;while (i <= S.length() && j <= T.length()){if (j == 0 || S[i] == T[j])//匹配成功，继续比较后续字符{++i;++j;}elsej = next[j];//模式串右移}if (j > T.length())return i - T.length();//匹配成功elsereturn 0;//匹配失败
}

3.2数组

数组是由类型相同的数据元素构成的有序集合，每个元素称为数组元素，每个元素受n个线性关系的约束。数组可以看成是线性表的推广，其特点是结构中的元素本身可以具有某种结构的数据，但属于同一数据类型。
例如：一维数组可以看成是一个线性表，二维数组可以看成数据元素是线性表的线性表。

3.2.1数组的顺序存储

由于数组一般不做插入或删除操作，也就是说，一旦简历数组，则结构中的数据元素个数和元素之间的关系就不再发生变动。因此采用顺序存储结构表示数组比较合适。在C语言中用的都是行序为主序的存储结构。

3.2.2特殊矩阵的压缩存储

矩阵用二维数组来表示是最自然的方法。但是，在数值分析中经常出现一些阶数很高的矩阵，同时矩阵中有很多值相同的元素或者是零元素。有时为了节省存储空间，可以对这类矩阵进行压缩存储。所谓压缩存储，是指多个值相同的元只分配一个存储空间，对零元不分配空间。

对称矩阵

若n阶矩阵A中的元满足$a_{ij}=a_{ji},1\le i,j\le j$w，则称为n阶对称矩阵。

对于对称矩阵，可以为每一对对称元分配一个存储空间，则可将$n^2$个元压缩到$n(n+1)/2$个元的空间中，可以行序为主序存储其下三角（包括对角线）中的元。
假设一维数组sa[ $n(n+1)/2$ ]作为n阶对称矩阵A的存储结构，则sa[k]和矩阵元$a_{ij}$之间存在着一一对应的关系
$$k=\{\begin{array}{c}\frac{i(i-1)}{2}+j-1i\ge j\\ \frac{j(j-1)}{2}+i-1i<j\end{array}$$

三角矩阵

以主对角线划分，三角矩阵有上三角和下三角矩阵两种。**上三角矩阵是指矩阵下三角（不包含对角线）**中的元均为常数c或领的n阶矩阵，下三角矩阵与之相反。对三角矩阵进行压缩存储时，除了和对称矩阵一样，只存储上下三家中的元素之外，再加一个存储常数c的存储空间即可。
上三角矩阵
sa[k]和矩阵元$a_{ij}$之间的对应关系：
$$k=\{\begin{array}{c}\frac{(2n-i+2)(i-1)}{2}+j-ii\le j\\ \frac{n(n+1)}{2}i>j\end{array}$$
下三角矩阵
sa[k]和矩阵元$a_{ij}$之间的对应关系：
$$k=\{\begin{array}{c}\frac{i(i-1)}{2}+j-1i\ge j\\ \frac{n(n+1)}{2}i<j\end{array}$$

对角矩阵

对角矩阵所有的非零元素都集中在主对角线为中心的带状区域，即主对角线上和直接在对角线上、下方若干条对角线上的元之外，所有其他的元皆为零。这种矩阵，也可以按某个原则（以行为主，或以对角线的顺序）将其压缩存储到一维数组上。

3.3广义表

广义表是线性表的推广，也称为列表。广泛运用于人工智能等领域的表处理语言LISP语言，把广义表作为基本的数据结构。
广义表一般记作：
$$LS=(a_1,a_2,...,a_n)$$
n为其长度。在线性表中，$a_i$只限于是单个元素。而在广义表的定义中，$a_i$可以是单个元素，也可以是广义表，分别称为广义表LS的原表和子表。习惯上，大写字母表示广义表名称，小写字母表示原子。

图中源泉表示广义表，方块表示原子，值得提醒的是广义表()和(())不同。前者为空表，长度n=0；后者长度n=1，可分解得到其表头、表尾均为空表（）。

*案例病毒感染检测

#include<iostream>
#include<fstream>
#include<cstring>#define MAXLEN 255
#define QElemType int
#define Status intusing namespace std; typedef struct{char ch[MAXLEN+1];int length; //字符串当前长度
}SString;int Index_BF(SString S, SString T, int pos){int i = pos, j = 1;while(i <= S.length && j <= T.length){if(S.ch[i] == T.ch[j]){++i, ++j;}else{i = i - j + 2;j = 1;}}if(j > T.length) return i-T.length;else return 0;
}int main()
{SString Virus, Person, temp; ifstream inFile("bug.txt");ofstream outFile("result.txt");int num;inFile >> num;while(num--){inFile >> Virus.ch + 1;inFile >> Person.ch + 1;Person.length = strlen(Person.ch + 1);Virus.length = strlen(Virus.ch + 1);string Vir(Virus.ch + 1, Virus.length);bool flag = false;int m = Virus.length;for(int i = m+1, j = 1; j <= m; j ++){Virus.ch[i++] = Virus.ch[j]; //将病毒字符串扩长度大两遍 }Virus.ch[2*m+1] = '\0';for(int i = 0; i < m; i ++){for(int j = 1; j <= m; j ++) temp.ch[j] = Virus.ch[i+j];temp.ch[m+1] = '\0';temp.length = m;flag = Index_BF(Person, temp, 1);if(flag) break;}if(flag) outFile << Vir << "        " << Person.ch+1 << "        " << "YES" << endl;else outFile << Vir << "        " << Person.ch+1 << "        " << "NO" << endl;}return 0;
} 

输入：

输出：