串是内容受限的线性表(字符)。数组、广义表是线性结构的推广
串：任意字符组成的有限序列
? ? ? ? 子串：任意连续的字符组成的子序列（子集）
? ? ? ? 串的顺序存储结构
#define MAXLEN255
typedef struct{
char ch[MAXLEN+1];//一维数组
int length;//串长
}SString? ? ? ? 串的链式存储结构
#define SIZEX 80
typedef struct Chunk{
char ch[SIZEX];
struct Chunk *next;
}Chunk;
typedef struct{
Chunk *head,*tail;
int curlen;
}Lstring? ? ? ? 串的模式匹配算法
? ? ? ? BF算法（暴力穷举）
int IndexBF(string S,string T){
int i=1,i=1;
while(i<=S.length && j<=T.length){
if(S[i] == T[i]){ ++i;++j; }//进入下一个匹配
else {i=i-j+2; j=1;}//主串和子串回溯到初始位置准备下次匹配
}
if(j>=T.length) return i-T.length;//成功，返回第一个字母的下标
else return 0;//匹配不成功
}? ? ? ? ? ? ? ? 总比较次数为：(n-m)*m+m = (n-m+1)*m
? ? ? ? ? ? ? ? 若m<<n则算法复杂度为O(n*m)
? ? ? ? KMP算法（原理是不需要回溯）
int IndexKMP(string S,string T,int pos){
i=pos,j=1;
while(i<S.length && j<T.length){
if(j==0|S.ch[i] == T.ch[j]){ i++; j++;}
else
j=next[j];//i不后退，j后退
}
if(j>T.length) return i-T.length;//匹配成功
else return 0;
}
void getNext(string T,int &next[]){
i=1; next[1]=0; j=0;
while( i<T.length){
if(j==0 || ch[i]==T.ch[j]){
++i; ++j;
}
else
j=next[j];
}
}
void getNextVal(string T,int &next[]){
i=1; next[1]=0; j=0;
while( i<T.length){
if(j==0 || ch[i]==T.ch[j]){
++i; ++j;
if(T.ch[i]!=T.ch[j]) nextval[i]=j;
else nextval[i]=nextval[j];
}
else
j=nextval[j];
}
}? ? ? ? ? ? ? ? 获取next序列、value序列
?数组
? ? ? ? 相同类型的数据元素的集合。线性表是数组结构的特例，数组结构是线性表的扩展
? ? ? ? 特点：结构固定--定义后，维组和维界不再改变。
? ? ? ? 多维数组本质上是多个一维数组连续存储（图例为行序为主语言<C、cpp、java>）
? ? ? ? 特殊矩阵的压缩存储
? ? ? ? ? ? ? ? 常规存储：二维数组。特点：元素可以随机存取，矩阵运算简单；存储密度为1。
? ? ? ? ? ? ? ? 如果零元素较多/相同元素较多->矩阵的压缩存储
? ? ? ? ? ? ? ? 特殊矩阵如：对称矩阵，对角矩阵，三角矩阵，稀疏矩阵（非零元素低于5%）可以进行压缩
? ? ? ? ? ? ? ? 对称矩阵的压缩：只存储半个三角（上三角/下三角），占用空间n(n+1)/2
? ? ? ? ? ? ? ? ????????压缩后元素的下标为n(n+1)/2-1
? ? ? ? ????????三角矩阵的压缩存储（只有半个三角），占用空间同对称矩阵
? ? ? ? ? ? ? ? ?对角矩阵的压缩存储（使用二维数组存储）
? ? ? ? ? ? ? ? ?稀疏矩阵的压缩存储（三元组顺序表）
? ? ? ? ? ? ? ? ?????????三元组顺序表优点：便于进行依行顺序处理矩阵
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?????????缺点：不能随机存取
? ? ? ? ? ? ? ? 稀疏矩阵的十字链表压缩：
? ? ? ? ? ? ? ? ? ? ? ? 十字链表的结点如下：
| row | col | value | down | right |
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? right指向同行中下一个非零元素，down指向同列中下一个非零元素
广义表
? ? ? ? 有限序列，每一个元素都可以是一个原子（单一元素），也可以是一个广义表（子表）
? ? ? ? ? ? ? ? 通常记作LS=(a1,a2...an)????????<大写字母表示广义表、小写字母表示原子>
? ? ? ? ? ? ? ? 表头：head(LS)=a1????????(可以是原子，也可以是子表)
? ? ? ? ? ? ? ? 表尾：tail(LS)=(a2,...an)? ? ? ? （表尾不是最后一个元素、而是一个子表）
? ? ? ? ? ? ? ? 长度：最外层括号中包含的元素个数
? ? ? ? ? ? ? ? 深度：广义表展开后所包含的所有括号的重数（原子深度为0，空表深度为1）
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 例：A=(b,c)深度为1，B=(A,d)深度为2，C=（f,B,h）深度为3
? ? ? ? ? ? ? ? 广义表可以与其他广义表共享：B=(A)
? ? ? ? ? ? ? ? 广义表可以是一个递归表：F=（a, F?=(a,(a,...))）递归表深度是无穷值，长度有限(2)
? ? ? ? ? ? ? ? 广义表是多层次结构（可以用树表示）
? ? ? ? 广义表基本运算：? ? ? ? GetHead(L)
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?GetTail(L)
????????