叮叮咚咚，新一期來襲，我還在吃桃子，吃桃子，吃桃子。。。串和python的字符串差不多,數(shù)組和廣義表像是python的list
串(string) - 字符串
概念及術(shù)語(yǔ)
-
定義： 零個(gè)或多個(gè)任意字符組成的有限序列，是一種內(nèi)容受限的線性表
-
子串 ： 串中任意個(gè)連續(xù)字符組成的子序列稱為該串的子串， 空串和串本身都是子串，不含本身的是真子串。
-
主串 ： 包含子串的串相應(yīng)地稱為主串。
-
字符位置 ： 字符在序列中的序號(hào)為該字符在串中的位置 。
-
子串位置 ： 子串第一個(gè)字符在主串中的位置 。
-
空格串 ： 由一個(gè)或多個(gè)空格組成的串 ， 與空串不同。
-
串相等 ： 當(dāng)且僅當(dāng)兩個(gè)串的長(zhǎng)度相等并且各個(gè)對(duì)應(yīng) 位置上的字符都相同時(shí) ， 這兩個(gè)串才是相等的 。
-
所有的空串是相等的。
串的類型定義
存儲(chǔ)結(jié)構(gòu)（同線性表）
-
順序串（順序存儲(chǔ)結(jié)構(gòu)）(更常用因不經(jīng)常插入刪除)
#define MAXLEN 255 typedef struct{ char ch[MAXLEN+1]; // 存儲(chǔ)串的一維數(shù)組,實(shí)際范圍0-255(0可能保留不用) int length; // 串的當(dāng)前長(zhǎng)度長(zhǎng)度 }SString; -
鏈串（鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)）
// 塊鏈結(jié)構(gòu) #define CHUNKSIZE 80 // 塊的大小可有客戶定義 typedef struct Chunk{ char ch[CHUNKSIZE]; struct Chunk *next; }Chunk; typedef struct LString{ Chunk *head,*tail; // 串的頭指針和尾指針 int curlen; //串的當(dāng)前長(zhǎng)度 }LString; //字符串的塊鏈結(jié)構(gòu)
串的模式匹配算法
確定主串中所含子串(模式串)第一次出現(xiàn)的位置（BF&KMP）
BF 算法
- (Brute-Force, 又稱古典的 、 經(jīng)典的 、 樸素的 、 窮舉的 ）
思路：從主串的每一個(gè)字符開始依次與模式串字符進(jìn)行比較
Index(S,T,pos)
-
將主串的第 pos 個(gè)字符和模式串的第一個(gè)字符比較 ，若相等，繼續(xù)逐個(gè)比較后續(xù)字符；
-
若不等，從主串的下一字符起(回溯) ， 重新與模式串的第一個(gè)字符比較
-
直到主串的一個(gè)連續(xù)子串字符序列與模式串相等。 返回值
為 S 中與 T 匹配的子序列第一個(gè)字符的序號(hào) ， 即匹配成功 。
否則 ， 匹配失敗 ， 返回值 0
int Index_BF(SString S, SString T, int pos){ int i=pos; j=1; // 主串i的位置從1開始pos>=1 while(i<=S.length&&j<=T.length){ if (S.ch[i]==T.ch[j]) {++i; ++j;} // 主串和子串依次匹配下一個(gè)字符 else {i=i-j+2; j=1} // 字符不相等，主串i回溯位置到（i-(j-1)+1）,j回到1 } if (j>T.length) return i-T.length; // 返回模式串匹配成功后主串對(duì)應(yīng)首字符的下標(biāo) else return 0; } -
時(shí)間復(fù)雜度為
(n-m)*m+m --> (n-m+1)*m--> O(n*m)(當(dāng)m<<n)
KMP算 法 （特點(diǎn)：速度快 ）
利用已經(jīng)部分匹配的結(jié)果而加快模式串的滑動(dòng)速度 ？
且主串 S 的指針 i 不必回溯 ！ 可提速到 O（ n+m ）
j的位置可以根據(jù)模式串來確定 ，定義next[j]函數(shù) ， 表明當(dāng)模式中剃個(gè)字符與主串中相應(yīng)字符 " 失配 " 時(shí) ， 在模式中需重新和主串中該字符進(jìn)行比較的字符的位置 。
int Index_KMP(SString S, SString T, int pos){
int i=pos; j=1; // 主串i的位置從1開始pos>=1
while(i<=S.length&&j<=T.length){
if (S.ch[i]==T.ch[j]) {++i; ++j;} // 主串和子串依次匹配下一個(gè)字符
else j=next[j] // 通過next[j]得到j(luò)的位置，i不用回溯
}
if (j>T.length) return i-T.length; // 返回模式串匹配成功后主串對(duì)應(yīng)首字符的下標(biāo)
else return 0;
}
void get_next(SString T, int &next[]){
i=1; next[1]=0; j=0;
while (i < T.length){
if (j==0 || T.ch[i]==T.ch[j]){
++i; ++j;
next[i]=j;
}
else j=next[j];
}
}
next[j]的改進(jìn)- nextval[j]
void get_nextval(SString T, int &nextval[]){
i=1; nextval[1]=0; j=0;
while (i < T.length){
if (j==0 || T.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];
}
}
數(shù)組
數(shù)組的定義
按一定格式排列起來的具有相同類型的數(shù)據(jù)元素的集合
一維數(shù)組
若線性表中的數(shù)據(jù)元素為非結(jié)構(gòu)的簡(jiǎn)單元素，則稱為一維數(shù)組 。
其邏輯結(jié)構(gòu)有線性結(jié)構(gòu)，定長(zhǎng)的線性表 。
聲明格式 ： 數(shù)據(jù)類型 變量名稱 [長(zhǎng)度]
二維數(shù)組
聲明格式： 數(shù)據(jù)類型變量名稱 [行數(shù)] [列數(shù)] ，eg: int num[5][8]
在 C 語(yǔ)言中 ，一個(gè)二維數(shù)組類型也可以定義為一維數(shù)組類型
（ 其分量類型為一維數(shù)組類型 ),
即 ：typedef elemtype array2[m][n];
等價(jià)于 ：
typedef elemtype array1[n];
typedef array1 array2[m];
三維數(shù)組 ： 若二維數(shù)組中的元素又是一個(gè)一維數(shù)組 ， 則稱作三維數(shù)組 。。。。
n維數(shù)組：若n-1維數(shù)組中的元素又是一個(gè)一維數(shù)組結(jié)構(gòu)則稱為n維數(shù)組 。
線性表是數(shù)組結(jié)構(gòu)的一個(gè)特例，數(shù)組結(jié)構(gòu)又是線性表結(jié)構(gòu)的擴(kuò)展。
數(shù)組特點(diǎn)
結(jié)構(gòu)固定(定以后維數(shù)和維界不再改變)，基本操作就是初始化，銷毀，取元素，修改元素 。
n維數(shù)組的數(shù)據(jù)類型定義
數(shù)組的順序存儲(chǔ)
一維數(shù)組存儲(chǔ)位置
二維數(shù)組存儲(chǔ)
-
以行優(yōu)先 - JAVA, C, BASIC ,COBOL ,PASCAL
-
以列優(yōu)先 - FORTRAN
三維數(shù)組 按頁(yè)行列存放，頁(yè)優(yōu)先的順序存儲(chǔ)
擴(kuò)展到n維數(shù)組存儲(chǔ)位置計(jì)算
特殊矩陣的壓縮存儲(chǔ)
-
壓縮存儲(chǔ)定義：若多個(gè)數(shù)據(jù)元素的值都相同 ， 則只分配一個(gè)元素值的存儲(chǔ)空間 ， 且
零元素不占存儲(chǔ)空間 。 -
特殊矩陣：對(duì)稱矩陣，對(duì)角矩陣，三角矩陣，稀疏矩陣(非零元素個(gè)數(shù)一般<5%)
對(duì)稱矩陣
只需存儲(chǔ)一半元素，存儲(chǔ)個(gè)數(shù)為每一行個(gè)數(shù)相加，即1+2+3+…+n=n(n+1)/2
任一個(gè)元素存在一維數(shù)組的位置aij的位置i(i-1)/2+(j-1) 原理：前面(i-1)行個(gè)數(shù)+本行的前(j-1)個(gè)元素
三角矩陣
對(duì)角矩陣
[ 特點(diǎn) ] 在n×n的方陣中，所有非零元素都集中在以主對(duì)角線為中心的帶狀區(qū)域中，區(qū)域外的值全為0 ，則稱為對(duì)角矩陣 。 常見的有三對(duì)角矩陣 、 五對(duì)角矩陣 、 七對(duì)角矩陣等 。(3/5/7條數(shù)據(jù))
稀疏矩陣
三元組(行,列,值) 和矩陣維數(shù)(總行,總列)來唯一確定一個(gè)元素的位置
-
三元組順序表又稱有序的雙下標(biāo)法。
-
優(yōu)點(diǎn)：非零元素在表中按行序有序存儲(chǔ)
-
缺點(diǎn)：不能隨機(jī)存儲(chǔ)，按行號(hào)存取某一行中的非零元素要從頭開始查找
十字鏈表 法存儲(chǔ)稀疏矩陣
廣義表
概念
廣義表（ 又稱列表 Lists) 是 n>=0 個(gè)元素 a0, a1, a2…an-1的有限序列 ， 其中每一個(gè)或者是原子 ， 或者是一個(gè)廣義表 。
性質(zhì)
廣義表和線性表的區(qū)別？
- 廣義表是線性表的推廣，線性表是廣義表的特例
- 廣義表的結(jié)構(gòu)相當(dāng)靈活 ， 在某種前提下 ， 它可以兼容線性表 、 數(shù)組 、
樹和有向圖等各種常用的數(shù)據(jù)結(jié)構(gòu) 。
基本運(yùn)算
GetHead(L): 求非空廣義表的第一個(gè)元素，可以是一個(gè)原子或者一個(gè)子表
GetTail(L):非空廣義表去掉表頭元素以外其他元素所構(gòu)成的表。
案例分析
病毒感染檢測(cè)(病毒RNA是環(huán)狀)
文章來源：http://www.zghlxwxcb.cn/news/detail-494318.html
文章來源地址http://www.zghlxwxcb.cn/news/detail-494318.html
TO BE CONTINUED…
到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)與算法基礎(chǔ)（青島大學(xué)-王卓）(5)的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
