系列文章
第一章：基礎(chǔ)知識
第二章：線性表
第三章：棧和隊列
第四章：字符串和數(shù)組
第五章：樹和二叉樹
第六章：圖
目錄 —— 第四章：字符串和數(shù)組
第一節(jié) ：串
1.1 串的基本概念
1.2 串的基本運算
1.3 串的存儲結(jié)構(gòu)
第二節(jié)： 數(shù)組
2.1 數(shù)組的邏輯結(jié)構(gòu)和基本操作
2.2 數(shù)組的存儲結(jié)構(gòu)
2.3 稀疏矩陣
本章總結(jié)
第四章：字符串和數(shù)組
字符串簡稱串纽谒，是一種特殊的線性表，其特殊性在于數(shù)據(jù)元素僅由一個個字符組成。作為一種基本數(shù)據(jù)類型雏掠，字符在計算機信息處理中意義非同一般匹颤，計算機非數(shù)值處理的對象經(jīng)常是字符串?dāng)?shù)據(jù)蘸劈。另外鸥滨，串還具有自身的特性鸥咖，常常把一個串作為一個整體來處理舍败，因此招狸，把串作為獨立結(jié)構(gòu)的概念加以研究是非常有必要的敬拓。本章簡單介紹了串的存儲結(jié)構(gòu)及基本運算。
數(shù)組可視為線性表的推廣裙戏，其特點是表中數(shù)據(jù)元素仍然是一個表乘凸。從本質(zhì)上看，維數(shù)大于1的數(shù)組中數(shù)據(jù)元素之間不再是簡單的一對一關(guān)系累榜，因此营勤，嚴(yán)格地說多維數(shù)組是非線性的。然而壹罚，由于數(shù)組中數(shù)據(jù)元素類型的一致性和其內(nèi)部結(jié)構(gòu)上的同一性葛作，在實際處理數(shù)組時可以借助線性表的方法來實現(xiàn)數(shù)組及其運算。本章將會介紹數(shù)組的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)猖凛、稀疏矩陣及其壓縮存儲等內(nèi)容赂蠢。
第一節(jié) ：串
1.1 串的基本概念
串（String）是由零個或多個任意字符串組成的字符序列。記做：s ="a1a2··an"辨泳，其中虱岂，s是串名。a1（1<=i <=n）是一個任意字符菠红，i是該元素在整個串中的序號第岖；n為串的長度，表示串中所包含的字符個數(shù)途乃，當(dāng)n=0時绍傲，稱為空串。
子串和主串：串中任意連續(xù)的字符組成的子序列稱為該串的子串耍共；包含子串的串相應(yīng)地稱為主串烫饼。
子串的位置：子串的第一個字符在主串中的序號稱為子串在主串中的位置。
串相等：若兩個串的長度相等且每一個對應(yīng)字符都相等试读，就稱這兩個串是相等的杠纵。
1.2 串的基本運算
求串長：StrLength(s);
串賦值：StrAssign(s1,s2); // 將s2的串值賦予s1
連接運算：StrConcat(s1,s2,s) 或 StrConcat(s1,s2).//在s1后面連接s2的串值，產(chǎn)生新串s
求子串：SubStr(s,i,len)钩骇；//返回s的第i至len個字符的子串值比藻。len=0為空串。例如：SubStr("abcdefg",2,3) = "bcd"
串比較：StrComp(s1,s2)倘屹；//若s1 =s2 ,操作返回值為0银亲；s1<s2，返回值<0纽匙；反之>0
串定位：StrIndex(s,t);//若t被包含于s中务蝠，則返回值為t的位置，反之值為-1
串插入：StrInsert(s,i,t);//將串t插入到s的第i個字符位置上
串刪除：StrDelete(s,i,len);//刪除串t中第i至len個字符的子串
串修改：StrRep(s,t,r);//用串r替換s中出現(xiàn)的所有與串t相等且不重疊的子串
1.3 串的存儲結(jié)構(gòu)
因為串是數(shù)據(jù)元素類型為字符的線性表烛缔，所有線性表的存儲方式仍適用于串馏段，也因為字符的特殊性和字符串經(jīng)常作為一個整體來處理的特點轩拨，串在存儲時還有一些與一般線性表不同的地方。
1院喜、串的定長順序存儲結(jié)構(gòu)：
類似于順序表亡蓉，可以用一組地址連續(xù)的存儲單元存儲串值中的字符串序列，所謂定長是指按預(yù)定義的大小為每一個串變量分配固定長度的存儲區(qū)喷舀。如下砍濒，串的最大長度不能超過256。
#define MAXSIZE 256
char s[MAXSIZE]
標(biāo)識實際長度的常用方法有三種：
第一種：類似順序表硫麻，用一個指針來指向最后一個字符梯影，這樣表示的串描述如下：
typedef struct{
char data[MAXSIZE];
int curlen;
}SeqString;
SeqString s;//串變量
這種存儲方式可以直接得到串的長度：s.curlen+1 。
第二種：在串尾存儲一個不會在串中出現(xiàn)的特殊字符串作為串的終結(jié)符庶香，以此表示串的結(jié)尾。例如简识，C語言中處理定長串的方法就是這一點赶掖，它用“\0”來表示串的結(jié)束。這種存儲方法不能直接得到串的長度七扰，根據(jù)當(dāng)前字符是否是“\0”來確定串是否結(jié)束奢赂，從而計算出串的長度。
第三種：設(shè)定串長存儲空間：chars[MAXSIZE+1]颈走，用s[0]來存放串實際長度膳灶，而串值存放在s[1]~s[MAXSIZE]中，字符的序號和存儲位置一致立由，應(yīng)用更為方便轧钓。
2、堆分配存儲結(jié)構(gòu)
在順序串上的插入锐膜、刪除操作并不方便毕箍，必須移動大量的字符，而且當(dāng)操作中出現(xiàn)串值序列的長度超過上界MAXSIZE時道盏，只能用截尾法處理而柑。要克服這個弊病，只有不限定串的最大長度荷逞，動態(tài)分配串值的存儲空間媒咳。
堆分配存儲結(jié)構(gòu)的特點是：仍以一組地址連續(xù)的存儲單元存放串的字符序列，但其存儲空間是在算法執(zhí)行過程中動態(tài)分配得到的种远。在C語言中涩澡，由動態(tài)分配函數(shù)malloc（）和free（）來管理。利用函數(shù)malloc（）為每一個新產(chǎn)生的串分配一塊實際需要的存儲空間院促，若分配成功筏养，則返回一個指針斧抱，指向串的起始地址。串的對分配存儲結(jié)構(gòu)如下：
typedef struct{
char *ch;
int len;
}HSTRING:
由于堆分配存儲結(jié)構(gòu)的串既有順序存儲結(jié)構(gòu)的特點渐溶，在操作中又沒有串長的限制辉浦，顯得很靈活，因此茎辐，在串處理的應(yīng)用程序中常被選用宪郊。
3、定長順序串基本運算的實現(xiàn)
串連接：把兩個串s1和s2首尾連接成一個新串s拖陆，即s<-s1+s2
int StrConcat(s1,s2,s)
char s1[],s2[],s[];//將串s1弛槐，s2合并到串s，合并成功返回1依啰，否則返回0
{
int i =0,j,len1,len2;
len1 = StrLength(s1);
len2 = StrLength(s2);
if(len1+len2>MAXSIZE-1) return 0; //s 長度不夠
j = 0 ;
while(s1[j]! ="\0"){
s[i] = s1[j];
i++;
j++;
}
while(s2[j]! ="\0"){
s[i] = s2[j];
i++;
j++;
}
s[i] = "\0";
return 1;
}
求子串：
int StrSub(char *t ,char *s,int i , in len){
//用t返回串s中第i個字符串開始的長度為len的子串乎串，1<=i串長
int slen;
slen = StrLength(s);
if(i<1 || i>slen || len<0 || len>slen-i+1){
return 0;
}
for(j =0 ; j<len ; j++){
t[j] =s[i+j-1];
t[j] ="\0";
return 1;
}
}
串比較：
int StrComp(char *s1 ,char *s2){
int i =0;
while(s1[i] == s2[i] && s1[i]!="\0"){
i++;
}
return (s1[i] -s2[i]);
}
串定位：
int StrIndex(char *s ,char *t)
//返回子串t在主串s中的位置，若不存在則返回-1
{
int i=0, j = 0;
while(s[i] !="\0" && t[j] !="\0"){
if(s[i] == t[j]){//匹配成功速警，繼續(xù)比較下一個字符
++i;
++j;
}else{ //否則主串換一個起始位置叹誉，子串重0開始
i = i-j+1;
j =0;
}
if( t[j] == "\0") { //匹配成功，返回匹配的第一個字符位置
return i -j;
}else{
return -1;
}
}
子串的定位操作通常稱做串的模式匹配闷旧，是各種串處理系統(tǒng)中最重要的操作之一长豁。上面的算法是一種簡單的帶回溯的匹配算法，該算法思路比較簡單忙灼，容易理解匠襟，但其視覺復(fù)雜度較高，最壞情況下為O(slen*slen)该园。
第二節(jié)： 數(shù)組
2.1 數(shù)組的邏輯結(jié)構(gòu)和基本操作
數(shù)組（Array）是一種數(shù)據(jù)結(jié)構(gòu)酸舍，高級語言一般都支持?jǐn)?shù)組這種數(shù)據(jù)類型爬范。特點是結(jié)構(gòu)中的元素本身可以是具有某種結(jié)構(gòu)的數(shù)據(jù)父腕，但屬于同一數(shù)據(jù)類型。從邏輯結(jié)構(gòu)上青瀑，可以把數(shù)組看做一般線性表的擴充璧亮。例如，一維數(shù)組就是一個線性表斥难，二維數(shù)組就是"數(shù)據(jù)元素是一維數(shù)組"的一維數(shù)組枝嘶。以此類推，即可得到多維數(shù)組的定義哑诊。
如有一個m行n列的二維數(shù)組：
可以把二維數(shù)組看成是一個線性表：A=(a1,a2····群扶，an)，其中aj(1<=j<=n）本身也是一個線性表，稱為列向量（Column Vector）竞阐，即aj=(a1j,a2j···缴饭，amj）。同樣還可以將數(shù)組A看成另外一個線性表：B={B1,B2,···骆莹，Bm),其中Bi(1<=i<=n）本身也是一個線性表颗搂，稱為行向量（Row Vector），即Bi=（ai1,ai2,····aim）幕垦。
在二維數(shù)組中丢氢，元素aij處在第i行和第j列的交叉處，即元素aij同時有兩個線性關(guān)系約束先改，aij既是同行元素aij-1 的“行后繼”疚察，又是同列元素ai-1j的“列后繼”，又是同列元素ai-1j的“列后繼”仇奶。同理貌嫡，三維數(shù)組可以看成這樣的一個線性表，即其中每個數(shù)據(jù)元素均是一個二維數(shù)組该溯，即三維數(shù)組中每個元素同時有三個線性關(guān)系約束衅枫，推廣之，n維數(shù)組就是“數(shù)據(jù)元素為n-1維數(shù)組”的線性表朗伶。
由數(shù)組的結(jié)果可以看出，數(shù)組中的每一個元素由一個值和一組下表來描述步咪。值表示數(shù)組中元素的數(shù)據(jù)信息论皆，下標(biāo)用來描述該元素咋數(shù)組中的相對位置。數(shù)組的維數(shù)不同猾漫，描述其相對位置的下標(biāo)的個數(shù)也不同点晴。例如，在二維數(shù)組中悯周，元素aij由兩個下標(biāo)i粒督、j來描述，其中i表示該元素的行號禽翼，j表示該元素的列號屠橄。
數(shù)組是一個具有固定格式和數(shù)量的數(shù)據(jù)有序集，即闰挡，一旦定義了數(shù)組的維數(shù)和每維的上锐墙、下限，數(shù)組的元素個數(shù)就固定了长酗，而且數(shù)組中的每一個元素也由唯一的一組下標(biāo)來標(biāo)識溪北。因此，在數(shù)組上一般不能做插入、刪除數(shù)據(jù)元素的操作之拨。對數(shù)組的操作通常只有下面兩類茉继。
（1）取值操作：給定一組下標(biāo)，讀其對應(yīng)的數(shù)據(jù)元素蚀乔。
（2）賦值操作：給定一組下標(biāo)烁竭，存儲或修改與其相對應(yīng)的數(shù)據(jù)元素。
因此乙墙，數(shù)組的操作注意是數(shù)據(jù)元素的定位颖变，即給定元素的下標(biāo)，得到該元素在計算機中的存儲位置听想。其本質(zhì)就是地址計算問題腥刹。接下來以二維數(shù)組展開說明，因為二維數(shù)組是應(yīng)用最廣泛的汉买，也是最基本的衔峰，對于大于二維的多維數(shù)組的存儲和操作方法可以類推。
2.2 數(shù)組的存儲結(jié)構(gòu)
由于數(shù)組的特點是數(shù)組中數(shù)據(jù)元素的個數(shù)固定且其結(jié)構(gòu)不變化蛙粘，數(shù)組操作基本就是取值垫卤、賦值運算，因此出牧，對于數(shù)組而言穴肘，采用順序存儲結(jié)構(gòu)表示比較合適。對于一維數(shù)組可以直接按其下標(biāo)順序分配內(nèi)存空間舔痕；而對于多維數(shù)組评抚，必須按某種次序?qū)?shù)組中元素排成一個線性序列，然后按該序列將數(shù)據(jù)元素存放在一維的內(nèi)存空間中伯复。
存儲二維數(shù)組時慨代，一般有兩種存儲方式：第一種是以行序為主序（先行后列）的順序存儲方式，即從第一行開始存放啸如，一行存放完了接著存放下一行侍匙，直到最后一行為止；另一種是以列序為主序（先列后行）的順序存儲方式叮雳，即一列一列的存儲想暗。
以行序為主序的存儲分配的規(guī)律是：最右邊的下標(biāo)先變化，即最右下標(biāo)從小到大帘不，循環(huán)一遍后江滨，右邊第二個下標(biāo)再變，···厌均，從右向左唬滑，最后是左下標(biāo)。以列序為主序存儲分配的規(guī)律恰好相反：最左邊的下標(biāo)先變化，即最左下標(biāo)從小到大晶密，循環(huán)一遍后擒悬，左邊第二個下標(biāo)再變，···稻艰，從左向右懂牧，最后是右下標(biāo)。例如尊勿，一個2X3的二維數(shù)組僧凤，以行序為主序的分配順序為：a1,a2,a3 | a4,a5,a6 ；以列序為主序的分配順序為：a1,a4 | a2 ,a5| a3,a6 元扔。
設(shè)有m × n 二維數(shù)組Amn ,按元素的下標(biāo)求存儲地址：
以行序為主序為例：設(shè)數(shù)組的基址為LOC(a11）,每個數(shù)組元素占據(jù)L個地址單元躯保，那么aij的物理地址可用一線性尋址函數(shù)計算：LOC(aij) = LOC(a11)+((i-1)× n+j-1) ×L 。因為數(shù)組元素aij的前面有i-1行澎语，每一行的元素個數(shù)為n途事，在第i行中它的前面還有j-1個數(shù)組元素。在C語言中擅羞，數(shù)組中每一維的下屆定義為0尸变，則：LOC(aij) = LOC(a00) +(i×n+j）×L。
推廣到一般二維數(shù)組A[c1···d1][c2···d2]减俏，則aij的物理地址計算函數(shù)為：LOC(aij) = LOC(ac1c2) +((i-c1) ×(d2-c2+1)+(j-c2))×L召烂。同理，對于三維數(shù)組Amnp娃承，即m×n×p數(shù)組骑晶，數(shù)組元素aijk的物理地址為：LOC(aijk) = LOC(a111）+（(i-1)×n×p+(j-1）×p+k-1）×L。
2.3 稀疏矩陣
稀疏矩陣（Sparse Matrix）是指矩陣中大多數(shù)元素為零元素的矩陣草慧，即設(shè)m×n矩陣中有t個非零元素且t<<m×n ，則稱之為稀疏矩陣匙头。
很多科學(xué)管理及工程計算中漫谷，常會遇到階數(shù)很高的大型稀疏矩陣。如果按常規(guī)分配方法蹂析，順序分配在計算機內(nèi)舔示，那將是相當(dāng)浪費內(nèi)存的。為此提出另外一種存儲方法电抚，僅存放非零元素惕稻。但對于這類矩陣，通常零元素分布沒有規(guī)律蝙叛，為了能找到相應(yīng)的元素俺祠，僅存儲非零元素的值是不夠的，還要記下它所在的行和列。于是采取如下方法：非零元素所在的行疤苹、列及它的值構(gòu)成一個三元組（i弦蹂，j澜术，v），然后按某種規(guī)律存儲這些三元組腿准，這種方法可以大大節(jié)約存儲空間。
1拾碌、稀疏矩陣的三元組表存儲
將三元組按行優(yōu)先的順序吐葱，同一行中列號從小到大的規(guī)律排列成一個線性表，稱為三元組表校翔，采用順序存儲方法存儲該表弟跑。如下圖：
這種存儲結(jié)構(gòu)的具體實現(xiàn)如下：
#define SMAX 1024 //足夠大的空間
typedef struct{
int i ,j ; //非零元素的行、列
datatype v; //非零元素值
}SPNode; //三元組類型
typedef struct{
int mu,nu,tu; //行列及非零元素個數(shù)
SPNode data[SMAX];//三元組表
}SPMatrix; //三元組表的存儲類型
//定義一個稀疏矩陣的變量：
SPMatrix M;
稀疏矩陣的轉(zhuǎn)置運算：
設(shè)A為一個m×n的稀疏矩陣展融，則其轉(zhuǎn)置矩陣B就是一個n×m的稀疏矩陣窖认，因此它們可以采用相同的數(shù)據(jù)類型，即：
SPMatrix A告希，B;
轉(zhuǎn)置運算需要完成的工作包括：A的行扑浸、列分別轉(zhuǎn)化成B的列、行燕偶；將A.data中每一個三元組的行與列交換后復(fù)制到B.data中喝噪。以上兩點完成之后，似乎完成了B指么，但實際上沒有酝惧。因為前面規(guī)定的三元組表是按行從小到大且同一行中的元素按列號從小到大的規(guī)律順序存放的，因此轉(zhuǎn)置后的矩陣B也必須按此規(guī)律排列伯诬。算法思路如下：
（1）A的行晚唇、列轉(zhuǎn)行成B的列、行盗似；
（2）在A.data中依次找第一列的哩陕、第二列的直到最后一列的三元組，并將找到的每個三元組的行赫舒、列交換后順序存儲到B.data中即可悍及。
void TransM1(SPMatrix *A){
SPMatrix *B;
int p,q,col;
B = malloc(sizeof(SPMatrix));//申請存儲空間
B ->mu =A ->nu;
B ->nu =A ->mu;
B ->tu =A ->tu;//稀疏矩陣的行、列接癌、元素個數(shù)
if(B->tu>0){
q=0;
for(col =1 ;col <=(A->nu);col++){//掃描整個三元組數(shù)
for(p=1;p<(A->nu);col++){
if(A->data[p].j == col）{
B->data[q].i = A ->data[p].j;
B->data[q].j = A ->data[p].i;
B->data[q].v = A ->data[p].v;
q++;
}
}
}
}
if(B->tu > 0){
return B心赶；
}
}
分析該算法，其時間主要耗費在col和p的二重循環(huán)上缺猛，所以時間復(fù)雜性為O(n×t)（設(shè)m缨叫、n是原矩陣的行椭符、列數(shù)，他是稀疏矩陣的非零元素個數(shù)）弯汰，顯然艰山，當(dāng)非零元素的個數(shù)t和m×n同數(shù)量級時，算法的時間復(fù)雜度為O(m×n2）咏闪，和通常存儲方式下矩陣轉(zhuǎn)置算法相比曙搬，可能節(jié)約了一定量的存儲空間，但算法的時間復(fù)雜度更差了一些鸽嫂。
算法改進(jìn)：上面算法低效率的原因是算法要從A的三元組表中尋找第一列纵装、第二列、···据某，要反復(fù)查找A橡娄，若能直接確定A中每一三元組在B中的位置，則對A的三元組表掃描一次即可癣籽。這是可以做到的挽唉，因為A中第一列的第一個非零元素一定存儲在B.data[1]中，如果還知道第一列的非零元素的個數(shù)筷狼，那么第二列的第一個非零元素在B.data中的位置便等于第一列的第一個非零元素在B.data中位置加上第一列的非零元素的個數(shù)瓶籽。以此類推，因為A中三元組的存放順序是先行后列埂材，對同一行來說塑顺，必定先遇到列號小的元素，這樣只需掃描一遍A.data即可俏险。
根據(jù)上面的想法严拒，需要引入兩個向量來實現(xiàn)：num[n+1]和cpot[n+1]，num[col]表示矩陣A中第col列的非零元素的個數(shù)（為了方便均從1單元用起）竖独，cpot[col]初始值表示矩陣A中的第col列的第一個非零元素在B.data中位置裤唠。于是cpot的初始值為：cpot[1] =1 ；cpot[col] = cpot[col-1]+num[col -1]; 2<=col<=n 莹痢。
SPMatrix *TransM2(SPMatrix *A){
SPMatrix *B;
int i,j,l;
int num[n+1],cpot[n+1];
B = malloc(sizeof(SPMatrix));//申請空間
//稀疏矩陣行列元素個數(shù)
B->mu = A ->nu;
B->nu =A ->mu;
B ->tu =A ->tu;
if(B->to > 0){
for(i=1;i<=A->nu;i++){
num[i] = 0;
}
for(i=1 ;i<=A ->tu ;i++){
j=A->data[i].j;
num[j]++;
}
cpot[1] =1; //求矩陣A中每一列第一個非零元素在B.data中的位置
for(i =2 ;i<A->nu;i++){
cpot[i] =cpot[i-1]+num[i-1];
}
for(i =1 ;i<(A->tu);i++){ // 掃描三元組表
j =A->data[i].j;
k =cpot[j];
B->data[k].i = A->data[i].j;
B->data[k].j = A ->data[i].i;
B->data[k].v = A->data[i].v;
}
return B;
}
分析這個算法的時間復(fù)雜度：這個算法中有四個循環(huán)种蘸，分別執(zhí)行了n、t格二、n-1、t次竣蹦，在每一個循環(huán)中顶猜，每次迭代的實際是一個常量，因此總的時間復(fù)雜度是O(n+t)痘括。當(dāng)然长窄，它所需要的存儲空間比前一個算法多了兩個向量的存儲空間滔吠。
本章總結(jié)
（1）字符串作為一種線性表，其特殊性在于表中每個元素就是單個字符挠日。事實上疮绷，許多高級語言都提高了字符串操作的基本功能，在此希望肚子通過對本章的學(xué)習(xí)嚣潜，了解各種程序設(shè)計語言中在實現(xiàn)字符串操作時的具體實現(xiàn)方法冬骚。
（2）理解數(shù)組的特點：1，n維數(shù)組可看成是這樣一個線性表懂算，其中每個元素均是一個n-1維的數(shù)組只冻；2，數(shù)組是一組有固定個數(shù)的元素的集合计技，即給出數(shù)組的維數(shù)和每一維的上下界喜德，數(shù)組中的元素個數(shù)就固定了；3垮媒，數(shù)組采用順序存儲結(jié)構(gòu)舍悯，其主要操作是元素定位操作，因此要求掌握一維數(shù)組睡雇、二維數(shù)組的地址計算方法萌衬。
（3）稀疏矩陣是一種常見的數(shù)據(jù)結(jié)構(gòu)，利用三元組表存儲它的非零元素可由極大地壓縮存儲空間入桂。
（4）在算法設(shè)計方面奄薇，要求掌握字符串的合并、數(shù)組中數(shù)據(jù)元素的原地逆置及矩陣的轉(zhuǎn)置運算等抗愁。
原文鏈接：https://blog.csdn.net/csdn_aiyang/java/article/details/84959056
