資料結構基礎—串
一、串型別定義
1.串的定義和相關概念
字串一般簡稱為串，其實就是由零個或多個字符組成的有限序列，邏輯結構和線性表極為相似，只是串的資料型別為字符型，
零個字符放入串稱為空串
串中任意連續字符組成的子序列稱為該串的子串
包含子串的串為主串
二、串的表示與實作
1.串的表示
串的表示分為三種分別是：定長順序，堆分配，塊鏈存盤
各個表示的注意事項:
- 定長順序：S[0]的值為串的長度
- 堆分配：動態鏈式的存盤，是從0開始的
- 每個節點就是一個串
2.串的基本操作(實作)
對串的操作，通常是”串為整體“操作，最基本的有六個操作
請見下方的代碼:
//求串長
int Strstrlen(char a[]){
int i = 1;
for(;a[i] !='\0';){
i++;
}
return i;
}
//復制S->T
void StrCopy(char(&T)[MaxSize+1],char S[]){
int i = 1;
T[0] = S[0];
while(i <= S[0]){
T[i] = S[i];
i++;
}
}
//賦值
void StrAssige(char(&S)[MaxSize+1],char a[]){
if(Strstrlen(a) > MaxSize){
cout << "賦值失敗";
return;
}
S[0] = Strstrlen(a);
for(int i = 1;i <= Strstrlen(a);i++){
S[i] = a[i-1];
}
cout << "賦值成功\n";
}
//比較
int StrCompare(char s[],char T[]){//ok
int i;
for(i = 1;i <= T[0];i++){
if(s[i] != T[i]) return 1;
if(s[i] == '#') return 1;
}
return 0;
}
//求子串
void Substring(char S[],char(&s)[MaxSize+1],int pos,int len){
int i;
if(pos < 1|| pos > S[0] || len > S[0] - pos +1){//不和法，不求子串但還是給賦個值
s[i] = '#';
return ;
}
for(int i = 1;i <= len;i++){
s[i] = S[pos + i -1];
}
}
//聯接
void Concat(char(&New)[MaxSize+1],char V[]){
if(New[0]+V[0] > MaxSize){
cout << "發生截斷\n";//這里寫的比較簡單
return ;
}
int j = New[0];
for(int i = 1;i <= V[0];i++){//小于要接入的串長
New[j+i] = V[i];
}
New[0] = New[0] + V[0];
}
三、串的模式匹配演算法
問題描述
有兩個串T（模式串）,S（主串），T在S中第一次匹配的位置是哪里
1、簡單演算法(暴力列舉)
兩串逐一比較
- 相同：i++;j++;
- 失配：i 和 j 的位置更替，i：回溯再+1(i = i - j +2)；j =1;
匹配成功：j > n(n:子串的長度(T[0]))
2、首尾匹配
先比較子串的首位，最后比較第二個到n-1個...
3、KMP演算法
時間復雜度：O(m*n)->O(m+n)
若當前位置不匹配，且不匹配的位置不為1，但是在子串的當前位置的前面前面有與開頭相同的元素，則下次時，不需要比較這些相同的元素,即：
- 主串i位置不變(不需要回溯)
- 子串向右滑動>=1位(不一定回到第一個位置)
eg:T串為 a b c a c 時，在 c 的位置不匹配，則下次從 b 開始比較(即：j = 2)
j 如何移動(j的下一個位置)？
只與模式串有關，使用 next[j] 陣列來存放下一個位置
next的值的含義：
- next = 0，第一個元素
- next = 1，無相同的子串
- next = k ,在第 k 個位置前所有的子串與 k 后到 j(next值) 前所有子串相同（這個很重要，k相當于相同子串的分隔）
要計算當前next[j]的值則要根據前一位元素的next值來確定(需要一個計數的i(前一個位置)和判斷的 j = next[i] (next[i]位置，相同子串的分隔))
j == 0說明無相同子串(第0個位置，啥也沒有)，直接將當前的next賦值為1，并更新j,因讓 j == 1，以便于接下來的比較(如果第一個位置與模式串中第i位置相同，則說明有一個相同子串next值就等于2了，依次類推)
此圖為多次分割，顏色相同或是數字相同的元素代表了他們相同，便于理解
計算當前位置的next
由上述的說明可知要想求得當前位置的next只需比較第i個位置和第j(next[i])個位置的值是否相同,
-
若相同，則next = 前一位置的next+1,(前串已根據next[i判斷好])同時更新 i 和 j 的值（next[++i] = ++j）
-
若不相同，則讓 j = next[j] 的值（再分割），再與第i個元素比較，直到相同或是 j == 0;
遍歷結束，即完成
代碼如下：
//普通KMP演算法
void GetNext(char T[],int len,int next[]){
next[1] = 0;
int i = 1;
j = 0;
while(i <= len){
if( j == 0 || T[j] == T[i]){
next[++i] = ++j;
}
else{ j = next[j]; }
}
}
完整代碼：
#include<iostream>
#include<cstdlib>
#define MaxSize 30
using namespace std;
//求串長
int Strstrlen(char a[]){
int i = 1;
for(;a[i] !='\0';){
i++;
}
return i;
}
//賦值函式
void StrAssige(char(&S)[MaxSize+1],char a[]){
if(Strstrlen(a) > MaxSize){
cout << "賦值失敗";
return;
}
S[0] = Strstrlen(a);
for(int i = 1;i <= Strstrlen(a);i++){
S[i] = a[i-1];
}
cout << "賦值成功\n";
}
//獲取next的值
void GetNext(char T[],int len,int next[]){
next[1] = 0;
int i = 1;
int j = 0;
while(i <= len){
if( j == 0 || T[j] == T[i]){//第一個位置或是有相等
next[++i] = ++j;
}
else{ j = next[j]; } //分割處
}
}
int KMP(char *S,char *T){
int next[MaxSize+1];
GetNext(T,T[0],next);
cout << "next 的值為：";
for(int m = 1;m <= T[0];m++){
cout << next[m];
}
cout << endl;//next正常
int i = 1;
int j = 1;
while(i <= S[0] && j <= T[0]){
if(j == 0 || S[i] == T[j]){//不匹配位置 = 1或是匹配
i++;
j++;
} else{
j = next[j];
}
}
if(j > T[0]) return i-T[0];
return 0;
}
int main(){
char a[MaxSize+1];
//原串
char S[MaxSize+1];
cout << "請輸入原串(S)的串：";
gets(a);
StrAssige(S,a);
//模式串
char T[MaxSize+1];
cout << "請輸入模式串：";
gets(a);
StrAssige(T,a);
//匹配
int j;
j = KMP(S,T);
cout << j;
return 0;
}
next[j]取值的改進(了解)
將當前元素的next[j]值與模式串中 j 位置的值比較，
-
若相同，則還要與 j 位置next值位置的元素比較，直到next = 0或是不同.當前位置的next[j] = j 位置的next[j]值
- 若發現不同，則next[j] = 上一個next的值
- 若最后匹配到next = 0 則，next[j] = 0
-
若不同，則next[j]的值不變
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/517770.html
標籤：其他
下一篇：對CART決策樹剪枝程序的理解