【数据结构-串-数组-广义表】

快速的过一遍数据结构中的串、数组、广义表,

1 串-理解

 顾名思义，串也称字符串，不过在数据结构里面处理的串和常规的字符串不一样，这里吧字符串当成一个整体进行处理：例如，在串中查找某个子串，求取一个子串，在串的某个位置上插入一个子串，以及删除一个子串等

1.1 串的抽象定义：-理解

1.2 串的存储结构-不断掌握

1.2.1 顺序存储结构：

 主要是有：串的定长存储结构、和串的串的堆式顺序存储结构

1.2.2 链式存储结构：

1.3 串的模式匹配算法：-掌握

1.3.1 BF暴力求解算法-代码 -掌握

1. BF（Brute Force，暴力搜索）串的模式匹配算法是一种简单直接的字符串匹配算法

#include <stdio.h>
#include <string.h>

int bfMatching(char *mainStr, char *patternStr)
{
    int mainLen = strlen(mainStr);
    int patternLen = strlen(patternStr);

    for (int i = 0; i < mainLen - patternLen + 1; i++)
    {
        if (strncmp(mainStr + i, patternStr, patternLen) == 0)
        {
            // 找到匹配返回起始位置
            return i;
        }
    }

    // 未找到匹配返回 -1
    return -1;
}

int main()
{
    char mainStr[] = "hello world example this is a example";
    char patternStr[] = "example";

    int result = bfMatching(mainStr, patternStr);
    if (result != -1)
    {
        printf("模式串在主串中首次出现的位置是：%d\n", result);
    }
    else
    {
        printf("未找到模式串\n");
    }

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

结果：

1.3.2 KMP求解算法-代码–掌握

2. KMP（Knuth-Morris-Pratt）算法是一种字符串匹配算法，用于在主字符串中查找模式字符串。该算法的时间复杂度为 O(n + m)，其中 n 和 m 分别是主串和模式串的长度。下面是一个用 C 语言实现 KMP 算法的示例代码：

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MAX_SIZE 255

typedef struct HString
{
    char zfc[MAX_SIZE];
    int length;
} HString;

// 获取 next 数组（部分匹配表）
void Get_Next(HString child, int *next)
{
    int i = 0, j = -1;
    next[0] = -1;

    while (i < child.length)
    {
        if (j == -1 || child.zfc[i] == child.zfc[j])
        {
            i++;
            j++;
            if (child.zfc[i] != child.zfc[j])
            {
                next[i] = j;
            }
            else
            {
                next[i] = next[j];
            }
        }
        else
        {
            j = next[j];
        }
    }
}

// 模式匹配函数
int bfMatching(char *mainStr, char *patternStr)
{
    HString parents;
    HString child;

    strcpy(parents.zfc, mainStr);
    parents.length = strlen(mainStr);
    strcpy(child.zfc, patternStr);
    child.length = strlen(patternStr);

    int *next = (int *)malloc(child.length * sizeof(int));
    Get_Next(child, next);

    int i = 0, j = 0;
    while (i < parents.length)
    {
        if (j == -1 || parents.zfc[i] == child.zfc[j])
        {
            i++;
            j++;
        }
        else
        {
            j = next[j];
        }
        if (j == child.length)
        {
            free(next);
            return i - j;
        }
    }

    free(next);
    return -1;
}

int main()
{
    char mainStr[] = "hello world example this is a example";
    char patternStr[] = "example";

    int result = bfMatching(mainStr, patternStr);
    if (result != -1)
    {
        printf("模式串在主串中首次出现的位置是：%d\n", result);
    }
    else
    {
        printf("未找到模式串\n");
    }

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93

结果：

2 数组-不断掌握

 主要是有数组类型定义，顺序存储结构，下标计算，对于数组而言，其下标之间的关系是一种线性关系，无论是几维数组

2.1 顺序存储结构

2.2 特殊矩阵压缩存储

 例如一些对称矩阵，我们不用把所有元素都存储，利用对称矩阵的性质，n阶矩阵只用存n(n+1)/2个数，而不用存n^2个数，还有一些其他的特殊矩阵和规则可以利用。

3 广义表

 顾名思义，广义表是线性表的推广，也称为列表。广泛地用千人工智能等领域的表处理语言LISP语言，把广义表作为基本的数据结构，就连程序也表示为一系列的广义表。
 广义表的定义是一个递归的定义，因为在描述广义表时又用到了广义表的概念。下面 列举一些广义表的例子