串、數組和廣義表

1. 串

1.1 串的定義

串(string)是由零個或多個字符組成的有限序列。一般記為

$$S=a_1{a}_2...a_n(n\ge 0)$$

其中，S是串名，單引號括起來的字符序列是串的值，$a_i$可以是字母、數字或其他字符；串中字符的個數n稱為串的長度。n=0時的串稱為空串(用表示)。

1.2 串的模式匹配

1.2.1 樸素模式匹配

使用暴力求解的方法，一直遍歷，但時間復雜度過高。

int ViolentMatch(string &s, string &t)
{int i = 0, j = 0;while (i < s.size() && j < t.size()){if (s[i] == t[j]){i++;j++;}else{i = i - j + 1;j = 0;}}if (j == t.size())return i - j;elsereturn -1;
}

1.2.2 KMP算法

vector<int> make_next(const string &s)
{int i = 0, j = -1;vector<int> next(s.size() + 1, 0); // Initialize the vector with the correct sizenext[0] = -1;                      // Set the first element to -1while (i < s.size()){if (j == -1 || s[i] == s[j]){i++;j++;next[i] = j;}elsej = next[j];}return next;
}
int KMP(const string &s, const string &t)
{int i = 0, j = 0;vector<int> next = make_next(t);while (i < s.size() && j < (int)t.size()){if (j == -1 || s[i] == t[j]) // Fix the logic error here{i++;j++;}elsej = next[j];}if (j == t.size())return i - j;return -1;
}

2. 數組和廣義表

2.1 數組

2.1.1 數組的定義

數組是由n(n>1)個相同類型的數據元素構成的有限序列，每個數據元素稱為一個數組元素，每個元素在n個線性關系中的序號稱為該元素的下標，下標的取值范圍稱為數組的維界。

數組與線性表的關系：數組是線性表的推廣。一維數組可視為一個線性表;二維數組可視為其元素是定長數組的線性表，以此類推。數組一旦被定義，其維數和維界就不再改變。因此，除結構的初始化和銷毀外，數組只會有存取元素和修改元素的操作。

2.1.2 數組的存儲結構

大多數計算機語言都提供了數組數據類型，邏輯意義上的數組可采用計算機語言中的數組數據類型進行存儲，一個數組的所有元素在內存中占用一段連續的存儲空間。

以一維數組 A[0…n-1]為例，其存儲結構關系式為

$$LOC(a_{i,j})=LOC(a_{0,0})+i\times L(0\le i\le n)$$

其中L是每個存儲單元的大小。

對于多維數組，有兩種映射方法:按行優先和按列優先。以二維數組為例，按行優先存儲的基本思想是:先行后列，先存儲行號較小的元素，行號相等先存儲列號較小的元素。設二維數組的行下標與列下標的范圍分別為[0,$h_1$]與[0,$h_2$]，則存儲結構關系式為

$$LOC(a_{i,j})=LOC(a_{0,0})+[i\times (h_2+1)+j)\times L$$

2.2 特殊矩陣的壓縮存儲

壓縮存儲：指為多個值相同的元素只分配一個存儲空間，對零元素不分配空間。

特殊矩陣：指具有許多相同矩陣元素或零元素，并且這些相同矩陣元素或零元素的分布有一定規律性的矩陣。常見的特殊矩陣有對稱矩陣、上(下)三角矩陣、對角矩陣等。

特殊矩陣的壓縮存儲方法：找出特殊矩陣中值相同的矩陣元素的分布規律，把那些呈現規律性分布的、值相同的多個矩陣元素壓縮存儲到一個存儲空間中。

2.2.1 對稱矩陣

對于矩陣$A$元素滿足性質 $a_{i,j}=a_{j,i}?$，則其為對稱矩陣。

由于其上三角與下三角元素相同，使用二維數組會浪費空間，故使用一維數組存儲來壓縮空間。如下圖所示，數組下標從0開始。

2.2.2 三角矩陣

下三角矩陣：

上三角矩陣：

2.2.3 三對角矩陣

2.2.4 稀疏矩陣