串数组广义表

Nuyoah2021-05-052022-11-21

串

串：内容受限制的线性表（里面内容只能是字符串）

			S = "a1a2a3·····an"(n≥0)

串名：S；

串值：“a1a2a3·····an”;

串长：n;

空串：n = 0；空集

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

例如，“abcde”的字串有：
```
  		“”， “a”,"ab", "abc","abcd","abcde"
```
真子串是指不包含自身的所有子串
主串：包含子串的串相应的称为主串
字符位置：字符在序列中的序号为该字符在串中的位置
字串位置：子串第一个字符再主串中的位置

空格串：有一个或多个空格组成的串，与空串不同

例：字符串a,b,c,d

a = "BEI";

b = "JING";

c = "BEIJING";

d = "BEI JING"

它们的长度是：3，4，7，8

c的子串：a b

d的子串：a b

a在c中的位置是：1 ； a在d中的位置是：1

b在c中的位置是：4； b在d中的位置是：5

串相等：当且仅当两个串的长度相等并且对应位置上字符都相同时，这两个串才是相同的
- 如“abcd” ≠ “abc”,
- “abcd e” ≠ “abcde”,

案例引入（病毒感染检测）

研究者将人的DNA和病毒DNA均表示由一些字母组成的字符串序列，然后检测某种病毒DNA序列是否在患者的DNA序列中出现过，如果出现过，则此人感染了病毒，否则没有感染
- 例如：加入病毒的DNA序列为baa，患者1的DNA序列为aaabbba，则感染，患者2的DNA序列为babbba，则为感染
- 注意：人的DNA序列是线性的，而病毒的DNA序列是环状的
  - 病毒baa 还有可能是 aab aba

串的类型定义，存储结构及其运算

ADT String
{
    数据对象:D = {ai | ai ∈ CharacterSet, i = 1,2,···n, n ≥ 0}
    数据关系:R1 = {<a(i-1), ai> | a(i-1), ai ∈ D, i = 1,2,···，n}
    基本操作:
    StrAssign(&T, chars); // 串赋值
    StrCompare(S,T); // 串比较
    StrLength(S);    // 求串长
    Concat(&T, S1, S2); // 串连结
    SubString(&Sub, S, pos, len); // 求子串
    StrCopy(&T,S);  // 串拷贝
    StrEmpty(S);     // 串判空
	ClearString(&S); // 清空串
    Index(S,T, pos); // 子串的位置
    Replace(&S,T,V); // 串替代
    StrInsert(&S,pos,T);// 子串的插入
    StrDelete(&S,pos,len); // 子串的插入
      
}

串的存储：串中元素逻辑关系与线性表相同，串可以采用与线性表相同的存储结构
- 顺序结构：顺序串
- 链式结构：链串

串的顺序存储结构

#define MAXLEN 255
typedef struct
{
    char ch[MAXLEN + 1]; // 存储串的一维数组
    int length; // 串当前长度
}SString

串的链式存储结构

和链表的使用方法一样，只不过里面存着数据只能是字符串
优点：操作方便
缺点，存储密度低
可以将多个字符存放在一个结点中**（称为块）**，这样可以克服其存储密度低的缺点
串的链式存储结构-----块链结构

#define CHUNKSIZE 80  //块的大小可以由用户定义
typedef struct Chunk
{
    char ch[CHUNKSIZE];
    struct Chunk* next;
}Chunk;
typedef struct
{
    Chunk *head, *tail; // 串的头指针和尾指针
    int curlen; // 串的当前长度
}LString;  //字符串的块链结构

串的模式比配算法

算法目的：
- 确定主串中所含子串（模式串）第一次出现的位置（定位）
算法应用
- 搜索引擎，拼写检查，语言翻译，数据压缩
算法种类：
- BF算法（Brute - Force，暴力破解法，古典，经典，朴素，穷举）
- KMP算法（特点：速度快）

BF算法

S: a a a a b c d  						主串：正文串

T: a b c										子串：模式串

算法思路是从S的每一个字符开始依次与T的字符串比较
例如，设目标串S = “aaaaab”,模式串T = “aaab”。S的长度为n(n = 6)，T的长度为m(m = 4)

BF算法的匹配过程中是设置两个变量i, j，依次存储S，T的第一个位置，然后依次比较各个字符的值，如果相等则各加一，如果不相同，则让(i - j + 2), j = 1从新开始比较
- 为什么是（i-j+2）：因为从开始到结束一共走了j-1步因为 j 初始值为1 所以是走了j-1步
- （i-j+2） = （i - (j-1) + 1 ）为什么要加一，是因为要从下一个位置开始
- 匹配成功后返回：i-t.length这是模式串在主串的位置

Index（S,T,pos）

将主串的第pos给字符和模式串的第一个字符比较，
- 若相等，继续逐个比较后序字符；
- 若不等，从主串的下一个字符起，从新与模式串的第一个字符比较
  - 直到主串的一个连续子串字符序列与模式串相同。返回值为S中与T匹配的子序列第一个字符的序号，即匹配成功
  - 否则，匹配失败，返回值0

int Index_BF(String *S1, String *S2)
{
    int i = 1, j = 1;
    //  这里默认主串是从1开始， 也可以自定义位置， 只需要在函数调用的时候传递一个位置参数即可
    while(i<=S1->length && j<=S2->length)
	{
		if(S1->ch[i-1] == S2->ch[j-1])
		{
			i++;
			j++;
		}
		else
		{
			i = (i-j+2);
			j = 1;
		}
	}
	if(j> S2->length)
	{
		return i-S2->length;
	}
	else
	{
		return 0;
	}
}

时间复杂度分析

若n为主串的长度，m为子串的长度，最坏的情况是
- 主串前面n-m个位置都部分匹配到字串的最后一位，即这个n-m位各比较了m次
- 最后m位也比较了1次
- 总次数为：（n-m)*m + m = （n-m+1） *m
- 若m<<n则算法复杂度为O(n*m)

KMP算法

优点：时间效率高，每次比较的时候，主串不必再回溯，子串依据next数组来进行变动

使用KMP算法主要由三部分

第一部分：主串（正文串）
第二部分：子串（模式串）
第三部分：next数组

主串和子串就是定义上的主串和子串，主要是next数组，以下就来解释什么是next数组的求法

在解释next数据的求法之前，先了解什么是前缀和后缀

例如字符串 abcde

其中

前缀有 a	ab	abc	abcd 其中前缀不包括字符串的本身

后缀有e 	de	cde	bcde 其中后缀不包括字符串的本身

next数组就是列出来子串（模式串）的所有前缀，外加一个它的本身

然后再去寻找每一个前缀中自己的**最大（前缀==后缀）**的字符数量，这就是next数组的元素

例如：a b a b c的next数组，

			max[K, 1 < k < j, 且p1 ··· pk-1  ==  pj-k+1 ·····  pj-1]

next[j] 0 当j=1时

			1   其他情况

	看正在查找的原素的前面的元素， 前缀 == 后缀 的字符有几个

J	1	2	3	4	5
P	a	b	a	b	c
N	0	1	1	2	3
	j = 1	其他情况前面的元素前缀！= 后缀	其他情况前面的元素前缀！= 后缀	前面的元素有一个相等的 k - 1 = 1 k = 2	前面的元素有两个相等的 k - 1 = 2 k = 3

这样a b a b c 的next数组就表达出来了

数组元素分别是 0 0 1 2 0；

利用这个数组来进行KMP算法：

T数组的下标i	1	2	3	4	5	6	7	8	9	10	11	12
T	a	b	a	a	c	a	b	a	b	c	a	c
P数组的下标j	1	2	3	4	5
P	a	b	a	b	c
N	0	1	1	2	3

上面依次比较直到 i = j = 4 的时候出现偏差不相同了，这时候应该让 j = next[j] , i 不动来继续进行比较

	1	2	3	4	5	6	7	8	9	10	11	12
T	a	b	a	a	c	a	b	a	b	c	a	c
P数组的下标j			1	2	3	4	5
P			a	b	a	b	c
N			0	1	1	2	3

这时候还是在P数组的b这里卡住了继续上一步的算法让P数组的j位置对应的的P数组的元素移动到i位置

T数组的下标i	1	2	3	4	5	6	7	8	9	10	11	12
T	a	b	a	a	c	a	b	a	b	c	a	c
P数组的下标j				1	2	3	4	5
P				a	b	a	b	c
N				0	1	1	2	3

这里还不相同,继续移动

T数组的下标i	1	2	3	4	5	6	7	8	9	10	11	12
T	a	b	a	a	c	a	b	a	b	c	a	c
P数组的下标j					1	2	3	4	5
P					a	b	a	b	c
N					0	1	1	2	3

这时候也不相同，继续移动，但这时候 j == 0，这时候就让 j = 1, 然后 i++即可

T数组的下标i	1	2	3	4	5	6	7	8	9	10	11	12
T	a	b	a	a	c	a	b	a	b	c	a	c
P数组的下标j						1	2	3	4	5
P						a	b	a	b	c
N						0	1	1	2	3

这时候还不相同，但是P数组已经到了头部，无法继续进行上一步操作否则会一直循环下去，这时候就要 j++ 和 i++ 来跳过这个元素，从新进行操作

T数组的下标i	1	2	3	4	5	6	7	8	9	10	11	12
T	a	b	a	a	c	a	b	a	b	c	a	c
P数组的下标j						1	2	3	4	5
P						a	b	a	b	c
N						0	1	1	2	3

这是候已经完全对应上这时候让 i - j 就是该模式串在正文串中的位置

这时候还可以继续上面的操作让模式串继续移动看是否有第二个位置

以上就是KMP算法的基本操作，

然而上面的数据还可以简化， 需要从next这方面入手， 求出nextval 来代替next；

根据next求nextval的方法

P数组的下标j	1	2	3	4	5
P	a	b	a	b	c
N	0	1	1	2	3
Nextval	0	1	0	0	3

这里的求法就是根据 next中的值来判断

第一个元素不变依旧是零

如果p[next[j]] = p[j]	的话就让 Nextval[j] = 0; 否则的话 就让Nextval[j] = Next[ j ];

以下是next的求法
next求法分为 1. 顺序 2. 回溯，其中回溯最为重要

// p = { a  b a b c  a c b a c b}
// 要有两个变量来记录这个next数组， 一个是前缀变量 j， 一个是后缀变量 i ;
j = 0;
i = 1;
next[i] = 0;
while( i <= strlen(p))
{
    if(j == 0 || p[j] == p[i])// 顺序
    {
        j++;
        i++;
        next[i] = j;
    }
    else  // 回溯
    {
        j = next[j];
    }
}

a	b	a	b	a	c	b	a	c	b	a	b	c	a	b	c
						b	a	c	b	a
						0	1	1	1	2

KMP实现如下

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

char* Next(char *S, int *next);

int* KMP(char *T, char *P, int *n);

int main()
{
	char T[255] = " ababacbacbabcabc";
	char P[255] = " bacba";

	int n[3];

	KMP(T, P, n);

	printf("%d %d", n[0], n[1]);
    return 0;
}

char* Next(char *S, int *next)
{
	int i, j;
	i = 1;
	j = 0;
	next[1] = 0;
	while(i < strlen(S))
	{
		if(j == 0 || S[i] == S[j] )
		{
			j++;
			i++;
			next[i] = j;
		}
		else
		{
			j = next[j];
		}

	}
	return next;

}

int* KMP(char *T, char *P, int *n)
{
	int next[255] = {0};
	Next(P, next);
	int i, j, k=0;
	i =1;
	j = 1;
	while( i <= strlen(T))
	{

		if( strlen(P) - 1  == j)
		{
			n[k++] = i - j;
			j = next[j];

		}
		else if(T[i] == P[j] || j == 0)
		{
			i++;
			j++;
		}
		else
		{
			j = next[j];

		}
	}

}

数组

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

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

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

二维数组：一维数组的每一个元素都是一个一维数组

三维数组：二维数组的每一个元素都是一个一维数组

定义二维数组的新方法

typedef elemtype array1[n];

typedef array1 array2[m];

数组的特点：结构固定-----定义后，维数和维界不在改变

数组的基本操作：处理结构的初始化和销毁外，只有取元素和修改元素的操作

n维数组的抽象数据类型

n为数组的维数

bi维数组第i维的长度

ADT Array

{

数据对象： ji = 0, ·····bi-1,   i = 1,2,·······n；

					D = {}

}

是第几维的数组，就有几个前趋和后继；

存储位置的求法

一维数组：

第n个位置 ====  a[0] + n * L（L为一个数据类型所占的空间）

二维数组

a[ n ] [m] ==== a[0] [0] + n* i * L+m * L;

先求几行，再加上第个；

三维数组

a[m] [n] [p] ===== a[0] [0] [0] + m* i * j  * L + n * i *L + p * L;

先求第几面，再求第几行， 再加上第一个

特殊矩阵的压缩存储

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

矩阵的常规存储：

将矩阵描述为一个二维数组

矩阵的常规存储特点：

可以对其元素进行随机存取

矩阵运算非常简单，存储密度为1

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

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

什么是压缩存储：

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

什么样的矩阵能够压缩？

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

什么加稀疏矩阵？

矩阵中非零元素个数较少（一般先小于5%）

对称矩阵的压缩：

将下三角的元素存储在一个一维数组中需要n(n+1)/2 个空间

他们在一维数组的存储位置是：例如a[m] [n] 在一维数组的下标是： n(n-1)/2
三角矩阵的压缩
- 三角矩阵：对角线以下（或者以上）的数据元素（不包括对角线）全部为常数c
- 存储方法: 重复的元素c共享一个元素存储空间，共占用n（n+1）/2 +1个元素空间，这里的 +1是表示哪一个常数c的空间
- 下三角矩阵：
  - k = i(i-1)/2+j;
- 上三角矩阵
  - k = (i-1) * (2n-i+2)/2 + j - i + 1
对角矩阵的压缩存储

这个是三对角矩阵（有三条对角线），还有四对角矩阵，五对角矩阵等等

存储方式是：

	1	2	3	4	5
-1		a01	a12	a23	a24
0	a00	a11	a22	a33	a44
1		a10	a21	a32	a43

系数矩阵压缩方法

使用三元组（就是每一行三个数据的二维数组）

第一个数是这个数据的行

第二个数是这个数据的列

第三个数是这个数据的数值

注意为更可靠描述，一般还再加一行，里面存储的是总行数，总列数，非零元素的总个数

三元组顺序表又称为有序的双下标法

三元组的优点：非零元素在表中按行序存储，因此便于进行依行顺序处理的矩阵运算

三元组缺点：不能随机存取，若要按行号寻找元素，则需要从头开始查找

广义表

是n≥0个元素组成的有限序列，其中每一个ai或者是一个原子，或者是一个广义表

广义表通常记作 LS = (a1 a2 a3 ·····an);

其中LS为表名， n为表的长度，每一个ai为表的元素

习惯上一般用大写字母表示广义表，小写字母表示原子

表头：若LS非空，则其第一个元素a1就是表头，记作head(LS) = a1

	 **注**：表头可是原子，也可使广义表

表尾：除表头外，其他元素组成的表

	**注**：表尾不是最后一个元素，而是一个子表

A = ( ) 空表长度为零

B = (()) 长度为1，表头，表尾均为（）；

C = (a, (b, c)) 长度为2：由原子a和子表（b, c）构成

			表头为a, 表尾为（(b,c)）

D = (a , b , c) 长度为3；每一项都是原子，

			表头为a， 表尾为（b, c）

性质：

广义表中数据元素有相对次序：一个直接前趋和一个直接后继
广义表的长度定义为最外层包含元素的个数
广义表的深度定义为该广义表展开后所含括号的层数

A = (b, c) 深度为1； B = (A, d) 深度为2； C = (f, B)深度为3，
广义表可以共享，例如上面B = (A, d), 这时候B中就包含A中的元素了
广义表可以是一个递归的表如：F = (a, F)

注意：递归表的深度是无穷值，长度是一个有限值
广义表是多层次结构的，广义表的元素可以是单元素，也可以是子表，而子表的元素还可是子表····

J	1	2	3	4	5
P	a	b	a	b	c
N	0	1	1	2	3
	j = 1	其他情况前面的元素前缀！= 后缀	其他情况前面的元素前缀！= 后缀	前面的元素有一个相等的 k - 1 = 1 k = 2	前面的元素有两个相等的 k - 1 = 2 k = 3