数据结构与算法要点总结（4）：数组、矩阵、字符串、广义表

目录

1、总体概述

2、数组

前驱后继个数

计算存储位置：

​n维推广

 3、特殊矩阵

对称矩阵

计算存放位置：

三对角矩阵

稀疏矩阵

 4、字符串

串的模式匹配

朴素模式匹配

KMP算法

 5、广义表

笔试考点：

取出特定元素：

广义表深度：

---

1、总体概述

一维数组与一位数组的推广：一维数组与多维数组、特殊矩阵、稀疏矩阵。

线性表的运用：字符串。

广义表：一种递归形式的表。

2、数组

前驱后继个数

 二维数组a在存储器中有两种地址映射方式： 行优先、列优先

计算存储位置：

n维推广

 3、特殊矩阵

对称矩阵

为节约存储，只存对角线及对角线以上的元素，或者只存对角线或对角线以下的元素。前者称为上三角矩阵，后者称为下三角矩阵

计算存放位置：

考试时要注意i,j的大小关系，以及是从零开始，还是从一开始。

技巧：若是选择题，可以举几个例子，带入算算看。 

三对角矩阵

矩阵A中元素 A[i][j] 在 B 中位置为 k = 2*i + j。

稀疏矩阵

在存储稀疏矩阵时，为节省存储空间，应只存储非零元素。

三元组表示（数组存储）

注意存储顺序，普通转置算法，快速转值算法。

用正交链表表示稀疏矩阵

 4、字符串

注意：空串和空白串不同，例如" "和""分别表示长度为1的空白串和长度为0的空串。

串的模式匹配

朴素模式匹配

KMP算法

可以观看代码中左神的视频。。

#include<iostream>
#include<string>
using namespace std;
 
/*   https://www.bilibili.com/video/BV13g41157hK/?p=13&spm_id_from=333.1007.top_right_bar_window_history.content.click&vd_source=b35eaf7c60912cc5b98163708d14772c  */
 
int* getNextArray(const string& p) {
    int m = p.length();
    int* next = new int[m];
    next[0] = -1;
    if (m == 1) {
        return next;
    }
    next[1] = 0;
    int i = 2, cn = 0;
    while (i < m) {
        if (p[i - 1] == p[cn]) {
            next[i++] = ++cn;
        } else if (cn > 0) {
            cn = next[cn];
        } else {
            next[i++] = 0;
        }
    }
    // next数组 ----> 第 n 位存储的是 0 ~ (n - 1) 这串字符 前缀 和 后缀 相等的最长的串的长度,注意前后缀都不能取整体
    // for (int i = 0; i < m; i++) {
    //     cout << next[i] << " ";
    // }
    // cout << endl;
    return next;
}
 
int KMP(const string& str1, const string& str2) {
    if (str1.length() < str2.length() || str2.length() < 1 || str1.length() < 1) {
        return -1;
    }
    int i1 = 0, i2 = 0;
    int* nextArr = getNextArray(str2);
    while (i1 < str1.length() && i2 < str2.length()) {
        if (str1[i1] == str2[i2]) {
            i1++;
            i2++;
        } else if (i2 == 0) {  // nextArr[i2] == -1
            i1++;
        } else {
            i2 = nextArr[i2];
        }
    }
    delete[] nextArr;
    return i2 == str2.length() ? i1 - i2 : -1;
}
 
int main() {
    string str1 = "aaaaaabaaaaaaab";
    string str2 = "abcabcabcd";
    cout << KMP(str1, str2) << endl;
    system("pause");
    return 0;
}
 

 5、广义表

笔试考点：

深度，长度，表头，表尾

特别注意：表尾是一个表，需要额外自己加一层括号

取出特定元素：

广义表深度：

笔试的时候找括号层数最多的就可以了 。