第4章 字串、陣列和特殊矩陣
目錄- 一、字串
- 1.1 字串的基本概念
- 1.2 字串類的定義
- 1.3 字串的存盤及其實作
- 1.3.1 順序串
- 1.3.1.1 順序串的存盤結構
- 1.3.2 鏈式串
- 1.3.2.1 鏈式串的存盤結構
- 1.3.1 順序串
- 二、字串的模式匹配
- 2.1 樸素的模式匹配演算法
- 2.2 模式匹配演算法（KMP演算法）
- 2.2.1 next陣列求解
- 三、陣列 （大綱未規定）
- 3.1 陣列和陣列元素
- 3.2 陣列類的定義
- 3.3 陣列的順序存盤及實作
- 四、特殊矩陣
- 4.1 對稱矩陣的壓縮存盤
- 4.2 三角矩陣的壓縮存盤
- 4.2.1 下三角矩陣
- 4.2.2 上三角矩陣
- 4.3 帶狀矩陣的壓縮存盤
- 五、稀疏矩陣
- 5.1 稀疏矩陣類的定義
- 5.2 稀疏矩陣的順序存盤及其實作
- 5.2.1 稀疏矩陣順序存盤（三元組）存盤結構
- 5.3 稀疏矩陣的鏈式存盤及實作（大概率不考）
- 5.3.1 稀疏矩陣鏈式存盤（十字鏈法）存盤結構
- 六、演算法設計題
- 七、錯題集
一、字串
1.1 字串的基本概念
- 字串：由 \(0\) 個或多個字符構成的有限序列，元素型別為字符型的特殊線性表
1.2 字串類的定義
- 略
1.3 字串的存盤及其實作
- 順序存盤字串：順序串
- 鏈式存盤字串：鏈式串
1.3.1 順序串
- 順序串常用操作：
- 順序串的插入演算法
- 順序串的洗掉演算法
- 順序串的連接運算演算法
- 求順序串子串的演算法
1.3.1.1 順序串的存盤結構
#define MAXSIZE 100
typedef struct{
char str[MAXSIZE];
int length;
} seqstring;
1.3.2 鏈式串
- 鏈式串的常用操作：
- 鏈式串的創建演算法
- 鏈式串的插入演算法
- 鏈式串的洗掉演算法
- 鏈式串的連接演算法
- 求鏈式串子串的演算法
1.3.2.1 鏈式串的存盤結構
typedef struct node{
char data;
struct node *next; // 用于存放字串中的每個字符
} linkstrnode; // 用于指向本字符的下一個字符對應的結點的指標
typedef linkstrnode * linkstring;
二、字串的模式匹配
2.1 樸素的模式匹配演算法
- 注：暴力求解，逐個匹對，時間復雜度 \(O(nm)\)，\(n\) 是正文的長度，\(m\) 是模式串的長度
2.2 模式匹配演算法（KMP演算法）
-
演算法步驟（大概率不考）
-
圖kmp模式匹配流程：
2.2.1 next陣列求解
- \(next\) 陣列求解步驟：
- 第 \(1\) 位：\(-1\)
- 第 \(2\) 位：\(0\)
- 第 \(n\) 位：比較前 \(n-1\) 位，得出最長前后綴長度為 \(k\)，填 \(k\)
三、陣列 （大綱未規定）
3.1 陣列和陣列元素
- 略
3.2 陣列類的定義
- 略
3.3 陣列的順序存盤及實作
- 略
四、特殊矩陣
- 特殊矩陣：對稱矩陣、三角矩陣、帶狀矩陣、稀疏矩陣
4.1 對稱矩陣的壓縮存盤
- 對稱矩陣元素位置的計算（\(L\) 為每個元素占用存盤空間的長度）：
4.2 三角矩陣的壓縮存盤
4.2.1 下三角矩陣
- 下三角矩陣元素位置的計算（\(L\) 為每個元素占用存盤空間的長度）：
4.2.2 上三角矩陣
- 上三角矩陣元素位置的計算（\(L\) 為每個元素占用存盤空間的長度）：
- 注：\((n+(n-1)+(n-2)+\cdots+(n-(i-1)))\) 表示 \(a_{ij}\) 前面的 \(i\) 行所有元素占用的空間；\(j-i\) 表示 \(a_{ij}\) 所在行的 \(a_{ij}\) 前面的元素所占用的空間
4.3 帶狀矩陣的壓縮存盤
- 帶狀矩陣：除第 \(1\) 行和最后一行外，每行都分配 \(2b+1\) 個元素的空間，但是把帶狀區域的所有元素存盤于 \(((2b+1)*n-2b)*L\) 個存盤單元中
- 帶狀矩陣元素位置的計算（\(L\) 為每個元素占用存盤空間的長度）：
- 注：\((i*(2b+1)-b)\) 表示 \(a_{ij}\) 前面的 \(i\) 行所有元素占用的空間；\((j-(i-b)))\) 表示 \(a_{ij}\) 所在行的 \(a_{ij}\) 前面的元素所占用的空間
五、稀疏矩陣
5.1 稀疏矩陣類的定義
- 略
5.2 稀疏矩陣的順序存盤及其實作
- 稀疏矩陣的順序存盤方法：三元組表示法、帶輔助行向量的二元組表示法、偽地址表示法
- 三元組表示法：\((i,j,value)\)，其中 \(i\) 表示行，\(j\) 表示列，\(value\) 表示值
- 注：三元組矩陣中第一行一般體現稀疏矩陣的行數、列數和所含非零元素的總個數
- 稀疏矩陣順序存盤常用操作：
- 產生稀疏矩陣的三元組表示
- 稀疏矩陣三元組表示下轉置運算的實作
5.2.1 稀疏矩陣順序存盤（三元組）存盤結構
typedef struct {
int data[100][100]; // 存放稀疏矩陣的二維陣列
int m, n; // 分別存放稀疏矩陣的行數和列數
} matrix;
typedef int spmatrix[100][3]; // 存放三元組
5.3 稀疏矩陣的鏈式存盤及實作（大概率不考）
-
稀疏矩陣的鏈式存盤方法：十字鏈表表示法、帶行指標向量的單鏈表表示法、行_串列示法
-
非零元素結點的結構中有 \(5\) 個域：行域（\(row\)）、列域（\(col\)）、資料的值域（\(val\)）、指向同一列下一個非零元素的指標域（\(down\)）、指向同一行下一個非零元素的指標域（\(right\)）
-
表頭結點的結構中有 \(5\) 個域：行域（\(row\)）默認為 \(0\)、列域（\(col\)）默認為 \(0\)、指向下一個表頭的指標域（\(next\)）、指向同一列下一個非零元素的指標域（\(down\)）、指向同一行下一個非零元素的指標域（\(right\)）
-
稀疏矩陣的鏈式存盤常用操作：
- 創建稀疏矩陣的十字鏈表表示
- 稀疏矩陣十字鏈表的查找演算法
-
稀疏矩陣的十字鏈表存盤方法如下圖所示：
-
圖稀疏矩陣的十字鏈表表示法：
5.3.1 稀疏矩陣鏈式存盤（十字鏈法）存盤結構
typedef struct matrixnode {
int row, col;
struct matrixnode *right, *down;
union {
int val;
struct matrixnode *next;
} tag;
} matrixnode;
typedef matrixnode *spmatrix;
typedef spmatrix headspmatrix[100]; // 指標陣列，每個元素指向一個表頭結點
六、演算法設計題
- 略
七、錯題集
- 稀疏矩陣常用的壓縮存盤方法有三元組順序存盤和十字鏈表兩種
- 設有一個 \(10×10\) 的對稱矩陣 \(A\) 采用壓縮方式進行存盤，存盤時以按行優先的順序存盤其下三角陣，假設其起始元素\(a_{00}\) 的地址為 \(1\)，每個資料元素占 \(2\) 個位元組，則 \(a_{65}\) 的地址為 \(53\)（元素 \(a_{00}\) 的地址為 \(1\)，不是 \(2\)）
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/155048.html
標籤：其他
上一篇：Go Micro 微服務搭建
下一篇：神經網路超引數貝葉斯優化