目录
快速的过一遍数据结构中的串、数组、广义表,
1 串-理解
顾名思义，串也称字符串，不过在数据结构里面处理的串和常规的字符串不一样，这里吧字符串当成一个整体进行处理：例如，在串中查找某个子串，求取一个子串，在串的某个位置上插入一个子串，以及删除一个子串等
1.1 串的抽象定义：-理解
1.2 串的存储结构-不断掌握
1.2.1 顺序存储结构：
主要是有：串的定长存储结构、和串的串的堆式顺序存储结构
1.2.2 链式存储结构：
1.3 串的模式匹配算法：-掌握
1.3.1 BF暴力求解算法-代码 -掌握
- 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.3.2 KMP求解算法-代码–掌握
- 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;
}
结果：
2 数组-不断掌握
主要是有数组类型定义，顺序存储结构，下标计算，对于数组而言，其下标之间的关系是一种线性关系，无论是几维数组
2.1 顺序存储结构
2.2 特殊矩阵压缩存储
例如一些对称矩阵，我们不用把所有元素都存储，利用对称矩阵的性质，n阶矩阵只用存n(n+1)/2个数，而不用存n^2个数，还有一些其他的特殊矩阵和规则可以利用。
3 广义表
顾名思义，广义表是线性表的推广，也称为列表。广泛地用千人工智能等领域的表处理语言LISP语言，把广义表作为基本的数据结构，就连程序也表示为一系列的广义表。
广义表的定义是一个递归的定义，因为在描述广义表时又用到了广义表的概念。下面 列举一些广义表的例子
