(此文为王道数据结构学习笔记，只供个人后续复习使用，若有错误，还望指出我改正，谢谢）
特殊矩阵的压缩存储
普通矩阵，可用一个二维数组存储 Array[M][N]
特殊矩阵：对称矩阵、三角矩阵、三对角矩阵、稀疏矩阵
对称矩阵的压缩空间：
对称矩阵：Aij=Aji
故可以只存储? 主对角线+下三角区?
可以按照行优先存储方式存储一个对称矩阵：
{A11，A21，A22，A31，A32，A33，A41，A42，A43，... ...，An1，An2，... ...，An n-1 Ann}
数组的长度为（1+2+3+4+5+6+...+n）
可以使用映射函数
Array[ i*(i-1)/2+j-1 ] 即为Aij号元素（要注意数组从0开始）
三角矩阵：除了三角区和对角线，其余为相同元素
思路和对称矩阵一致，只需存储 三角区+主对角线 ，再用一个位置存储其余相同元素的值即可
三对角矩阵：又称带状矩阵，当 | i - j | > 0 时，Aij = 0 ，即只有中间三条对角线有数据，其余为0
除了第一行与最后一行，其余行均有三个元素，即Ai i-1，Ai i，Ai i+1，思路也是利用行优先原则，存储每一行的非0元素
稀疏矩阵：非0元素远少于为0元素个数
压缩存储策略1：
使用顺序存储，存一个三元组 < 行，列，数值 >? ，只存非0元素
压缩存储策略2：
链式存储——十字链表法
?每个元素存放 < 行，列，数值 > 数值，同时存放两个指针：行指针和列指针，行指针用于指向同一行下一个元素的位置，列指针用于指向同一列下一个元素的位置，同时初始化时建立行列头指针，用于指向该行或者该列的首个非0元素。
串
串的定义：即字符串，有0或多个字符组成的有限序列，数据对象受限的线性表（字符集）
子串：串中任意连续的字符子序列
主串：即整个串
字符在主串的位置：字符在串中的序号
子串在主串的位置：子串的第一个字符在主串的位置
StrAssign(&T, chars ); 把chars赋值给串T
StrCopy(&T,S);由串S复制得到串T
StrEmpty(T);判断串空
StrLength(T);求串长
ClearString(&T);清空串（空间仍在）
DestroyString(&T);销毁串（空间还给系统）
Concat(&T, S1, S2);串连接，由S1和S2连接得到串T
SubString(&Sub, T, pos, len);求子串。用Sub返回串T中第pos个字符起长度为len的子串
Index(T, Sub);如果主串T存在与Sub相同的子串，返回第一次出现的位置，否则返回0
StrCompara(S, T);比较两个字符串的大小，按照a<b<c...<z挨个字符比较；若S>T，返回值>0；若S<T，返回值<0；若S=T，返回值=0
ASCII码：A-65, Z-90? ?a-97，z-122
字符集：英文ASCII字符集，中英文Unicode字符集，同一字符集可以有多种编码方案，例如有UTF-8,UTF-16方法等。
乱码即编码规则使用错误，导致解码出错。
串的存储结构：
顺序存储：
即数据为char的顺序表
链式存储：即数据域为char的链表
子串在主串中定位操作：(Index函数)模式匹配
int Index(SString S, SString T){
int i=1, n=StrLength(S), m=StrLength(T);
SString sub;//用于暂存子串
while(i<=n-m+1){
SubString(sub, S, i, m);
if(SubCompara(Sub, T)!=0)
i++;
else
return i;//返回子串在主串中的位置
}
return 0;//S中不存在与T相等的子串
}朴素模式匹配算法：（简单模式匹配算法）
即比对每一个和子串长度相等的主串中的子串
int Index(SString S, SString T){
int k=1;
int i=k, j=1;
while(i<=S.length && j<=T.length){
if(S.ch[i]==T.ch[j]){
++i;
++j;
}//继续比较后续字符
else{
k++;//检查下一个子串
i=k;
j=1;
}
}
if(j>T.length)
return k;
else
return 0;
}m为子串长，n为主串长：
匹配成功的最好时间复杂度：O(m)? ? ??匹配成功的最坏时间复杂度：O(nm)
匹配失败的最好时间复杂度：O(n)? ? ? ?匹配失败的最坏时间复杂度：O(nm)
KMP算法（优化朴素模式匹配算法）：
引入next数组，长度为模式长度一致，用于存放匹配信息
int Index_KMP(SString S, SString T, int next[]){
int i=1, j=1;
while(i<=S.length&&j<=T.length){
if(j==0||S.ch[i]==T.ch[j]){
++i;
++j;//继续比较后继字符
}
else
j=next[j];//模式串向右移动
}
if(j>T.length)
return i-T.length;//匹配成功
else
return 0;
}