Java教程

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

本文主要是介绍数据结构与算法-线性结构:串、数组和广义表,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

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);

}
这篇关于数据结构与算法-线性结构:串、数组和广义表的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!