数据结构与算法-线性结构：串、数组和广义表

2022-12-28 12:29:26

4.0内容总览

对于整体知识架构比较重要的概念：

串的元素只能是字符；
数组中的元素是线性表；
广义表中的元素又是广义表。
严格来说，数组和广义表不是线性结构，他们是线性结构的推广。

4.1串

4.1.1串的基本概念

4.1.2串的实际应用

4.1.3串的类型定义、存储结构及运算

4.1.3.1串的顺序存储结构

由于串很少进行插入和删除操作，所以顺序存储结构更常用。

4.1.3.2串的链式存储结构

注：块的英文单词为chunk.

4.1.3.3串的模式匹配算法——BF

由于串的算法在高级语言中都学过，下面主要讲解串的模式匹配算法.

模式（子串）匹配BF算法

举例说明

注意：串结构中的数组的[0]位置并没有存储元素，而是从[1]位置开始存储的，所以这里的i和j都是从1开始。
回溯：匹配失败后，i=i-j+2，可以分为两步理解，首先是i-j-1让i退回到刚才起点的位置，然后+1，是到刚才起点的下一个位置。

算法思想总结

算法描述

串结构中的数组的[0]位置并没有存储元素，而是从[1]位置开始存储的，所以这里的i和j都是从1开始。

如果需要从任意位置pos开始查找

疑问倒数第二行代码if语句中是否不用加=号？

时间复杂度分析
最好时m，最坏是n*m，分析如下：

4.1.3.3串的模式匹配算法——KMP

举例说明next[j]的情况

KMP算法描述

其中，T代表模式串，S代表主串。

上面没看懂 老师说的是：该算法比较难理解，能看懂，会用就行。

4.2数组

4.2.1数组的基本概念

4.2.2 数组的顺序存储结构

一维数组的存储方式和地址

二维数组的存储方式和地址

例题

4.2.3特殊矩阵的压缩存储

4.稀疏矩阵

三元组法

三元组法的特点：

三元组法的缺点，不能随机存取，首先在存的时候只能顺序存入，没有存前面的元素，就不会知道现在这个元素应该存在哪儿。其次，在取值的时候，只能从头到尾的搜索该值的信息。

补充：随机存取、顺序存取
1、随机存取就是直接存取，可以通过下标直接访问到元素的位置，与存储位置无关，时间复杂度永远为O(1)，例如数组。存取第N个数据时，不需要访问前（N-1）个数据，直接就可以对第N个数据操作（array）。
2、顺序存取，不能通过下标访问，在存取第N个数据时，必须先访问前（N-1）个数据，例如链表。

十字链表

老师并没有讲代码，之后自己学习

4.3广义表

4.3.1广义表的基本概念

原子：单一元素

广义表通常用链表来存储

4.4案例：病毒感染

程序实现：

// 线性结构_串_模式（子串）匹配问题_病毒感染.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include<stdlib.h>
using namespace std;


typedef struct {
    char ch[11];
    int length;
}SString;

void CreatS(SString& S) {
    int i = 1;
    while(1) {
        cin >> S.ch[i]; //输入字符时，一定要用空格隔开，不然就是字符串了。
        i++;
        if (cin.get() == '\n') break;
    }
    S.length = i-1;
}

void DoubleS(SString& S) {
    for (int i = 1; i <= S.length; i++) {
        S.ch[i + S.length] = S.ch[i];
    }
    S.length = S.length * 2;
}

SString GetSS(SString& T, int n) {
    SString T_temp;
    for (int i = 1; i <= T.length/2; i++) {
        T_temp.ch[i] = T.ch[n];
        n++;
    }
    T_temp.length = T.length / 2;
    return T_temp;
}

bool index_BF(SString S, SString& T) {
    DoubleS(T);
    for (int n = 0; n < T.length / 2; n++) {
        SString T_temp = GetSS(T, n);
        int i = 1; int j = 1;
        while (i <= S.length && j <= T_temp.length) {
            if (S.ch[i] == T.ch[j]) {
                i++; j++;
            }
            else {
                i = i - j + 2; j = 1;
            }
        }
        if (j >= T_temp.length) {
            return true;
            break;
        }
    }
    return false;
}

void Show(SString S) {
    for (int i = 1; i <= S.length; i++) {
        cout << S.ch[i] << "  ";
    }
    cout << endl;
}

int main()
{
    SString S, T;
    CreatS(S);    
    CreatS(T);
    cout << "输入结果：" << endl;
    Show(S);
    Show(T);
    
    cout <<"是否感染："<< index_BF(S, T);

}

码农公寓