数据结构 4 串、数组和线性表

本文最后更新于：2023年12月24日 晚上

b站王卓老师课程学习

P67待补充

啊啊啊

4.1 串

串(string)：由零个或多个字符组成的有限序列

所谓序列说明串的相邻字符之间具有前驱和后继关系

串

子串：一个串中任意个连续字符组成的子序列（含空串）称为该串的子串。

例如，"abcde’的子串有：““、”a“、”ab“、“abcd” 和 “abcde” 等

真子串是指不包含自身的所有子串。

主串：包含子串的串相应地称为主串

字符位置：字符在序列中的序号为该字符在串中的位置、

子串位置：子串第一个字符在主串中的位置

空格串：由一个或多个空格组成的串，与空串不同，空格串：“ ”，空串：“”

一个例子

a在d中的位置：5

串相等：当且仅当两个串的长度相等并且各个对应位置上的字符都相同时，这两个串才是相等的

所有空串都是相等的

4.2 案例引入

8888

之后有一个字符串的经典问题，字符串的匹配

4.3 串的类型定义、存储结构、算法

4.3.1 串的抽象数据类型的定义

image-20231224171848757

4.3.2 串的存储结构

串中元素逻辑关系与线性表的相同，串可以采用与线性表相同的存储结构。

串的存储结构

串的逻辑结构与线性表相似，区别仅在于串的数据对象约束为字符集

串的基本操作和线性表的差别：在线性表的操作中，多以“单个元素”作为操作对象，在串的操作中，多以“串的整体”作为对象

1. 定长顺序存储结构

固定长度的顺序表来存储字符串。

这种用的最多

我们知道，顺序表通常使用数组来实现，数组的创建方式有两种，分别是静态数组和动态数组。以 C 语言为例，静态数组指的就是长度固定的数组，动态数组指的是调用 malloc() 函数创建的数组，例如：

1
2
3
4
// 静态数组
char str[30] = "http://data.biancheng.net"；
// 动态数组
char* str = (char*)malloc(30 * sizeof(char));

对于定义好的静态数组，它的长度是无法修改的；动态数组则不同，它的长度是可变的，定义后还可以调用 realloc() 函数扩容。

串的定长顺序存储既然用固定长度的顺序表来实现，就限定了只能用静态数组实现，不能用动态数组。

🍧🍧🍧其实就是说这里的定长顺序存储结构是静态数组实现，第二种方法堆分配存储结构是动态数组实现

1
2
3
4
5
6
//定长顺序存储结构
#define MAXLEN 255  //预定义最大串长为255
typedef struct{
    char ch[MAXLEN+1];//存储串的一维数组，下标为0-255，一般0号位置闲置不用，从1号位置开始
    int length; //串的当前长度
}SString;
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
//Vscode简单实现
#include <stdio.h>
#include <string.h>

#define MAXLEN 255

typedef struct {
    char ch[MAXLEN + 1];
    int length;
} SString;

// 初始化 SString 的函数
void initSString(SString *s, const char *str) {
    s->length = strlen(str);
    strncpy(s->ch + 1, str, MAXLEN);  // 假设字符串从1开始索引
    s->ch[s->length + 1] = '\0';  // 在字符串末尾添加空字符
}

// 打印 SString 内容的函数
void printSString(const SString *s) {
    printf("字符串：%s\n", s->ch + 1);  // 从索引1开始打印
    printf("长度：%d\n", s->length);
}

int main() {
    SString myString;
    
    // 示例：用字符串初始化 SString
    initSString(&myString, "你好，世界！");

    // 示例：打印 SString 的内容
    printSString(&myString);

    return 0;
}

代码运行结果

这里解释一下上面的initSString函数：

void initSString(SString *s, const char *str) {}

  • SString *s：这是一个指向 SString 结构体的指针，表示函数将会修改传递给它的 SString 对象。
  • const char *str：这是一个指向常量字符的指针，表示函数将会接受一个 C 字符串作为参数，这个 C 字符串是以 '\0' 结尾的。

s->length = strlen(str);：

  • strlen(str) 返回输入字符串 str 的长度，不包括结尾的空字符 ('\0')。
  • s->length 被赋值为字符串的长度，即存储在 SString 结构体中的 length 成员。

strncpy(s->ch + 1, str, MAXLEN);：

  • strncpy 函数用于复制字符串。它接受三个参数：目标字符串、源字符串和要复制的最大字符数。
  • s->ch + 1 是目标字符串的起始位置，表示从数组 ch 的索引 1 开始复制，因为这里假设字符串从索引 1 开始。
  • str 是源字符串。
  • MAXLEN 是要复制的最大字符数。
  • 这行代码的作用是将源字符串的内容复制到 SString 结构体的 ch 成员中，从索引 1 开始，最多复制 MAXLEN 个字符。

s->ch[s->length + 1] = '\0';：

  • 这行代码在字符串的末尾添加了一个空字符 '\0'，以确保字符串正确终止。
  • s->length 是字符串的长度，所以 s->length + 1 是字符串的下一个位置，用于放置空字符。

总体而言，initSString 函数的作用是接受一个常规的 C 字符串（以 '\0' 结尾），计算其长度并将其复制到自定义的字符串结构体 SString 中。这个函数假设字符串是从索引 1 开始的，并在复制过程中保留了一个空字符作为字符串的结尾。

2. 堆分配存储结构

堆分配存储是指的是用一整块适当大小的堆内存空间来存储字符串。

所谓堆内存，就是堆区的内存空间。以 C 语言为例，程序运行时占用的内存空间会分成很多大小不等的块（区域），它们通常被称为堆区、栈区、常量区、全局数据区、代码区等。这些区域各有分工，比如全局数据区用来存储全局变量和静态变量，代码区用来存储要运行的程序指令等。

和内存的其它区域相比，堆区最大的特点就是：不会自动分配和回收，必须由程序员手动申请，使用完后再手动释放。

在 C 语言中，申请堆内存的操作可以调用 malloc() 或者 calloc() 函数来完成，例如：

1
char * a = (char *)malloc(5 * sizeof(char));

如果 malloc() 函数执行成功，我们就申请了能存储 5 个字符的堆内存空间。

如果申请的堆内存空间不够用，还可以调用 realloc() 函数扩容，例如：

1
a = (char *)realloc(a, 10 * sizeof(char));

realloc() 函数执行成功，原本只能存 5 个字符的堆内存，扩容成能存储 10 个字符。

堆内存使用完后，需要手动调用 free() 函数释放，例如：

1
free(a);

强调：堆内存必须及时手动释放，否则会造成内存泄漏。

1
2
3
4
5
//串的堆分配存储结构，可以用如下的结构体来表示：
typedef struct {
    char* ch;  //ch 用来指向申请好的堆空间，以便存储字符串；
    int length; //length 用来记录串的长度。
}HString;

3. 块链存储表示

串的链式存储结构：

串的链式存储结构
  • 优点：操作方便
  • 缺点：存储密度较低

\(存储密度=串值所占的存储/实际分配的存储\)

可将多个字符存放在一个结点中，以克服其缺点，这就是串的链式存储结构---块链结构

串的链式存储结构---块链结构
  • 优点：不需要大块连续空间；
  • 缺点：占用存储量大，操作复杂，不如顺序存储方式方便
  • 块链结点大小≥1
1
2
3
4
5
6
7
8
9
10
11
12
#define CHUNKSIZE 80 //块的大小由用户定义
typedef struct Chunk{
    char ch[CHUNKSIZE] ;
    struct Chunk *next;
}Chunk ;

typedef struct{
    Chunk *head, *tail; //串的头指针和尾指针，设置根据实际需要
    int curlen;  //串的当前长度
}Lstring; //字符串的块链结构


这部分可以再参考一下：串的块链存储结构（C语言）详解 (biancheng.net)

4.3.3 串的模式匹配算法

老师说串的基本操作在c语言里面都学过了，所以就讲了这一个（我学你的内阁😡

算法目的：确定主串中所含子串(模式串)第一次出现的位置 (定位)

算法应用：搜索引擎、拼写检查、语言翻译、数据压缩

算法种类：

  • BF算法（Brute-Force，又称古典的、经典的、朴素的、穷举的）
  • KMP算法（特点：速度快）

1. BF算法

Brute-Force简称为BF算法，亦称简单匹配算法。采用穷举法的思想

主串：正文串

子串：模式串

BF算法

算法的思路是从S的每一个字符开始依次与T的字符进行匹配

下图展示了模式串T = “abcac”和主串S的匹配过程

BF算法过程

Index(S,T,pos)

  • 将主串的第pos个字符和模式串的第一个字符比较
  • 若相等，继续逐个比较后续字符
  • 若不等，从主串的下一字符起，重新与模式串的第一个字符比较
  • 直到主串的一个连续子串字符序列与模式串相等。返回值为S中与T匹配的子序列第一个字符的序号，即匹配成功。
  • 否则，匹配失败，返回值 0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// BF算法
int Index_BF(SString S, SString T){
    int i = 1, j = 1;
	while(i <= S.length && j <= T.length){
		if(S.ch[i] == T.ch[j]){
			++i; ++j;	//继续比较后继字符
		}else{
			i = i-j+2;
            //对i = i-j+2我的理解：
            //原因是我们循环是从1开始计数的，如果我们是从0开始计数，其实很好理解，直接i-j+1，i前移一个
            //但我们是从1开始计数的，再加个1，就是i-j+2
			j = 1;
		}
	}
	if(j > T.length){
		return i - T.length; // 返回匹配的第一个字符的下标
	}else{
		return 0;  // 模式比匹配不成功
	}
}

1
2
3
4
5
6
7
// BF算法，课本上的
int Index_BF(SString S, SString T, int pos){
    int i = pos, j = 1;

    //后面代码都一样，书上的意思是不从第一个字符来比，而是从第pos个字符来比
    ……

BF算法复杂度分析

BF算法复杂度分析

2. KMP算法

Knuth Morris Pratt 算法

草，听了半天有点难听懂啊😴😴😴

KMP算法是D.E.Knuth、J.H.Morris和VR.Pratt共同提出的，简称KMP算法

该算法较BF算法有较大改进，从而使算法效率有了某种程度的提高.

好像期末考试不考，之后再来补这个坑😬😬

KMP算法完全攻略（C语言实现） (biancheng.net)

4.4 数组

4.4.1 数组的定义和特点

数组：按一定格式排列起来的具有相同类型的数据元素的集合

一维数组：若线性表中的数据元素为非结构的简单元素，则称为一维数组

一维数组的逻辑结构：线性结构。是一个定长的线性表

声明格式：数据类型变量名称[长度]

例：int num[5] ={0，1，2，3，4};

二维数组

二维数组

二维数组：若一维数组中的数据元素又是一维数组结构，则称为二维数组

二维数组的逻辑结构：

  • 非线性结构：每一个数据元素既在一个行表中又在一个列表中。
  • 线性结构：该线性表的每个数据元素也是一个定长的线性表

声明格式：数据类型 变量名称[行数] [列数]

例：int num[5] [8]，一个五行八列的数组

在C语言中，一个二维数组类型也可以定义为一维数组类型（其分量类型为一维数组类型）

即：typedef elemtype array2[m][n]

等价于：

1
2
typedef elemtype array1[n];
typedef array1 array2[m];

三维数组：若二维数组中的元素又是一个一维数组， 则称作三维数组

n维数组：若n-1维数组中的元素又是一个一维数组结构则称作n维数组

结论：线性表结构是数组结构的一个特例，而数组结构又是线性表结构的扩展

  • 数组特点：结构固定——定义后，维数和维界不再改变。
  • 数组基本操作：除了结构的初始化和销毁之外只有取元素和修改元素值的操作

4.4.2 数组的抽象数据类型定义

数组的抽象数据类型定义
二维数组的抽象数据类型定义

4.4.3 数组的顺序存储

因为：

  • 数组特点：结构固定维数和维界不变

  • 数组基本操作：初始化、销毁、取元素、修改元素值。一般不做插入和删除操作

所以：

一般都是采用顺序存储结构来表示数组

注意：数组可以是多维的但存储数据元素的内存单元地址是一维的，因此，在存储数组结构之前，需要解决将多维关系映射到一维关系的问题

1. 一维数组

例，有数组定义： int a[5];

一维数组

2. 二维数组

二维数组

存储单元是一维结构，而数组是个多维结构，则用一组连续存储单元存放数组的数据元素就有个次序约定问题

以行序为主序
以列序为主序
二维数组的存储方式
计算公式
  • 一个例题
例题

4.4.4 特殊矩阵的压缩存储

矩阵：一个由 m*n个元素排成的 m 行n 列的表

矩阵的常规存储：将矩阵描述为一个二维数组

矩阵的常规存储的特点：可以对其元素进行随机存取；矩阵运算非常简单；存储的密度为 1。

不适宜常规存储的矩阵：值相同的元素很多且呈某种规律分布；零元素多

矩阵的压缩存储：为多个相同的非零元素只分配一个存储空间；对零元素不分配空间。

  1. 什么是压缩存储？

    若多个数据元素的值都相同，则只分配一个元素值的存储空间，且零元素不占存储空间。

  2. 什么样的矩阵能够压缩？

    一些特殊矩阵，如：对称矩阵，对角矩阵，三角矩阵，稀疏矩阵等

  3. 什么叫稀疏矩阵？

    矩阵中非零元素的个数较少 (一般小于5%)

先不边看网课边记笔记了，感觉这个对期末考试用处没直接看题目，然后针对性的学有用——2023.12.29

参考：

串的定长顺序存储结构（C语言实现） (biancheng.net)

数据结构：串(String)【详解】_数据结构sstring-CSDN博客

数据结构
#数据结构
数据结构 4 串、数组和线性表
http://viper2383.github.io/2023/12/24/数据结构 4 串、数组和线性表/
作者
w1per3
发布于
2023年12月24日
许可协议