概述
串：字符串的簡稱，串是一種特殊的線性表系枪，特殊在其數(shù)據(jù)元素都是一個字符曙砂。
數(shù)組和廣義表可以看做是線性表的擴充，即線性表的數(shù)據(jù)元素自身又是一個數(shù)據(jù)結構狐蜕。
1. 串 String
本結主要講述：串的存儲結構和基本操作
定義：主要是有0個或多個字符組成的序列宠纯。
存儲結構：順序存儲和鏈式存儲，但是串一般使用順序存儲結構层释。
順序存儲
typedef struct {
char *ch; //若為非空串婆瓜，則按串長分配存儲區(qū)，否則ch為null
int length; //串長度
}HString;
鏈式存儲：
#define CHUNKSIZE 80; //可有用戶定義的塊大小
typedef struct Chunk{
char ch[CHUNKSIZE ];
struck Chunk *next;
}Chunk;
typedef struct {
Chunk *head,*tail;//串的頭尾指針
int curlen; //串的當前長度
}LString;
串的存儲密度=串值所占的存儲位/實際分配的存儲位 密度小贡羔，運算處理才方便廉白；
串的模式匹配算法 子串的定位運算通常稱為串的模式匹配或串匹配个初。
應用場景：搜索引擎、拼音檢查蒙秒、語言翻譯勃黍、數(shù)據(jù)壓縮等。
eg：
有兩個字符串S-主串晕讲、T-子串（也稱模式）；
著名的模式匹配算法有兩種：BF和KMP算法：
- BF算法：最簡單直觀的模式匹配算法马澈，Brute-Force算法
int Indext(SString S,SString T,int pos){
int i=pos,j=1; //i指向主串瓢省，j指向子串
while(S[0]>=i && j<=T[0]){
if(S[i] == T[j]){
++i;
++j;
}else{
i=i-j+2;
j=1;
}
}
if(j>T[0]){
return i-T[0];
}else{
return 0;
}
}
主串長：N ，子串長：M
算法的時間復雜度：
- 在最好的情況下（N+M)1/2即O(N+M）
- 最壞的情況下：M(N-M+2)*1/2即O(N+M）痊班；
BF思路直觀簡明勤婚，但是時間復雜度高為：O(N+M），
2.KMP算法：由Kunth Morris Pratt共同設計所以稱為KMP算法涤伐；
特點：無需回溯主串的指針馒胆，當模式串與主串中存在許多“部分匹配”的情況下才顯得比BF快，所以BF至今任然被采用凝果。
時間復雜度：O（m+n）
int Indext_KMP(SString S,SString T,int pos){
//利用模式串T的next函數(shù)求T在主串S中第pos個字符之后的位置
//其中祝迂，T非空，1<=pos<=Strlength(S)
int i=pos,j=1; //i指向主串器净，j指向子串
while(S[0]>=i && j<=T[0]){
if(j==0 || S[i] == T[j]){
++i;
++j;
}else{
j=next[j]; //模式串向右移動
}
}
if(j>T[0]){
return i-T[0];
}else{
return 0;
}
}
T的Next函數(shù),算法時間復雜度為O(m)
void get_next(SString T,int next[]){
int i = 1;
next[1] = 0 ;
int j = 0 ;
while(i<T[0]){
if(j == 0 || T[i] == T[j]){
++i;
++j;
next[i] = j;
}else{
j=next[j];
}
}
}
上面的next算法有缺陷型雳，下面有修正版的：
void get_nextval(SString T,int nextval[]){
int i = 1;
nextval[1] = 0 ;
int j = 0 ;
while(i<T[0]){
if(j == 0 || T[i] == T[j]){
++i;
++j;
if(T[i] != T[j]){
nextval[i] = j;
}else{
nextval[i] = nextval[j];
}
}else{
j=nextval[j];
}
}
}
next函數(shù)修正值：
2. 數(shù)組
本結主要講述：數(shù)組的內(nèi)部實現(xiàn)和特殊的二維數(shù)組如何實現(xiàn)壓縮存儲。
定義：由類型相同的數(shù)據(jù)元素構成的有序集合山害。
- 一維數(shù)組可以看成線性表
- 二維數(shù)組是數(shù)據(jù)元素為線性表的線性表纠俭；
數(shù)組一般不做插入和刪除操作，所以一般采用順序存儲結構浪慌。
二維數(shù)組有兩種存儲方式：
- 列序為主序的存儲方式.
- 行序為主序的存儲方式冤荆。
Java、C权纤、Basic钓简、Pasical都是行序為主序的編程語言；
Fortran是以列序為主序的編程語言妖碉；
每個元素占L個存儲單元涌庭，二維數(shù)組A[0m-1,0n-1]（A[m,n]）中任一元素aij的存儲位置： LOC（i,j）=LOC(0,0)+(n x i+j)L;
由于計算各個元素存儲位置的時間相等，所以存取數(shù)組中任一元素的時間也相等欧宜，即數(shù)組是一種隨機存取結構坐榆。
矩陣的壓縮存儲
矩陣用二維數(shù)組來表示是最自然的。
壓縮存儲:指為多個值相同的元只分配一個存儲空間冗茸，對0元不分配空間席镀；
特殊矩陣：對值相同的元素或0元素在矩陣中的分布有一定規(guī)律匹中；
主要有三種特殊矩陣：對稱矩陣、三角矩陣豪诲、對角矩陣.
若n階矩陣A中的元滿足Aij=Aji顶捷，稱為n階對稱矩陣。
可將n^2個元素壓縮到n(n+1）/2個元的空間中屎篱。
設一維數(shù)組Sa[n(n+1)/2]作為矩陣A的存儲結構服赎，則sa[k]和矩陣元aij
的關系：
- k=i(i-1)/2+j-1 條件（i < j）
- k=j(j-1)/2+i-1 條件（i > j）
3. 廣義表
本結主要講述：廣義表的概念和存儲結構。 廣義表是線性表的推廣交播，也稱為列表重虑。 廣泛的用于人工智能領域的表處理語言LISP語言。 記為：LS=（a1,a2,a3,a4…..an)
//廣義表的頭尾鏈表存儲表示
typedef enum{
ATOM,LIST
}ElemTag;
typedef struct GLNode{
ElemTag tag;
union{
AtomType atom;
struct{
struct GLNode *hp;
struct GLNode *tp;
}ptr;
};
}*GList;
