数据结构c语言版第二版(严蔚敏)第四章笔记

目录

串的定义

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

串的抽象类型定义

串的存储结构

串的顺序存储

串的链式存储

串的模式匹配算法

BF算法(Brute-Force)

KMP算法 

数组广义表

总结

---

计算机上的非数值处理对象大部分是字符串数据，字符串一般称为串。串是一种特殊的线性表，其特殊性体现在数据元素是一个字符，也就是说，串是一种内容受限的线性表。由于现今使用的计算机硬件结构是面向数值计算的需要而设计的，在处理字符数据时比处理整数和浮点数要复杂得多。而且在不同类型的应用中，所处理的字符串具有不同的特点，要有效地实现字符串的处理，就必须根据具体形况使用合适的存储结构

串的定义

串或字符串是由零个或多个字符组成的有限序列，一般记为

其中s是串的名，用双引号表示的字符串序列是串的值。(1<=i<=n)可以是字母、数字或其他的字符，串中字符的数目n称为串的长度。零个字符的串称为空串，其长度为0

串任意个连续的字符组成的子序列称为该串的子串，包含字串的串相应的称为主串，通常称字符在序列中的需要为该字符在串中的位置，子串在主串中的位置则以子串中第一个字符在主串中的位置来表示

当且仅当两个串的值相等，称这两个串是相等的。也就是说，只有当两个串长度相等，并且各个对应位置的字符都相等时两个串才相等

在各种应用中，空格常常是串的字符集合中的一个元素，因而可以出现在其他字符中间。由一个或多个空格组成的串称为空格串(空格串不是空串)，其长度为串中空格字符的个数，为清楚起见，以后我们用符号来表示空串

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

串的抽象类型定义

串的逻辑结构和线性表极为相似，区别仅在于串的数据对象约束为字符集。然而串的基本操作和线性表有很大的差别。在线性表的基本操作中，大多以“单个元素”作为操作对象。但是在串的基本操作当中，常常以“串整体”作为操作对象

串的存储结构

与线性表类似，串也有两种基本存储结构：顺序存储和链式存储。但考虑到存储效率和算法的方便性，串多采用顺序存储结构

串的顺序存储

串的定长顺序存储

typedef struct
{
	char ch[MAXSIZE];
	int length;
}SString;

其中，MAXISIZE表示串的最大长度，ch是存储字符串的一维数组，每个分量存储一个字符，length表示字符串的当前长度，这种定义方式是静态的，在编译时刻就确定好了串空间的大小，而多数情况下，串的操作是以串的整体形式参与的，串变量之间的长度相差较大，在操作中串值长度的变化也较大，这样为串变量设定固定大小的空间不尽合理。因此最好是根据实际需要，在程序的执行过程中动态地分配和释放字符数组空间。在c语言当中，存在一个称为堆的自由存储区，可以为每个新产生的串动态分配到一块实际串长所需要的存储空间，若分配成功，则返回一个指向起始地址的指针，作为串的基址，同时以后为了方便处理，约定串长也作为存储结构的一部分。这种字符串的存储方式也称为串的堆式存储结构 

typedef struct
{
	char *ch;
	int length;
}HString;

串的链式存储

顺序串的插入和删除操作不方便，需要移动大量的字符。因此可以采用单链表的形式存储串，由于串结构的特殊性---结构中每个数据元素是一个字符，则在用链表存储串值的时候，存在一个“节点大小”的问题，即每个节点可以存储一个字符，也可以存放多个字符。为了便于进行串的操作，当以链表存储串值时，除头指针外，还可附设一个尾指针指示链表中的最后一个节点，并给出当前串的长度，称如此定义串的存储结构为块链结构

typedef struct Chunk
{
	char ch[MAXSIZE];
	struct Chunk *next;
}Chunk;
typedef struct
{
	Chunk *head,*tail;
	int length;
}LString;

在链式存储中，节点的大小选择直接影响着串处理的效率。在各种串的处理系统中，所处理的串往往很长或者很多，显然，存储密度小，运算处理方便，然而，存储占用量大，如果在串处理过程中需进行内、外存交换的话，则会因为内、外存交换操作过多而影响处理的总效率。应该看到，串的字符集的大小也是一个重要的因素，一般说来，字符集校，则字符的机内编码就短，这也影响串值存储方式的选取

串值的链式存储结构对某些串操作如链接操作等有一些方便之处，但总的来说，不如顺序存储结构灵活，它占用存储量大且操作复杂。此外在串的链式存储结构中，串操作的实现和线性表在链式存储结构中的操作类似

串的模式匹配算法

子串的定位运算通常称为串的模式匹配或串匹配。设有两个字符串S和T，设S为主串，也称正文串；设T为子串，也称为模式。在主串S中查找与模式T相匹配的子串，如果匹配成功，确定相匹配的子串的第一个字符在主串S中出现的位置

著名的模式匹配算法有BF算法和KMP算法

BF算法(Brute-Force)

最简单直观的模式匹配算法是BF算法

模式匹配不一定是从主串的第一个位置开始，可以指定主串中查找的起始位置pos，如果采用字符串顺序存储结构。可以写出不依赖于其他串的匹配算法

算法步骤：

1.分别利用计数指针i和j指示主串S和模式T中当前正待比较的字符位置，i的初值为pos，j的初值为1

2.如果两个串均未比较到串尾即i和j均小于等于S和T的长度时则循环执行以下操作：

S.ch[i]和T.ch[j]进行比较，若相等则i，j分别指向串中的下个位置，继续比较后续字符

若不相等，指针后退开始重新匹配，从朱传的下一个字符(i = i - j + 2)起再重新和模式的第一个字符(j = 1)比较

3.如果j > T.length，说明模式T中的每个字符依次和主串S中的一个连续的字符序列相等，则匹配成功，返回和模式T中第一个字符相等的字符在主串S中的序号(i - T.length)，否则匹配不成功，返回0

BF的算法时间最优复杂度为O(n + m)，最劣时间复杂度为O(n * m)

int BF(SString S,SString T,int pos)//BF算法,最优时间复杂度为O(n + m),最坏时间复杂度为O(n * m)
{
	int i = pos;
	int j = 1;
	while(i <= S.length && j <= T.length)
	{
		if(S.ch[i] == T.ch[j])
		{
			i ++ ;
			j ++ ;
		}
		else
		{
			i = i - j + 2;
			j = 1;
		}
	}
	if(j > T.length)return i - T.length;
	else return 0;
} 

KMP算法 

KMP算法可以在时间复杂度为O(n + m)的时间数量级上完成串的模式匹配操作，其改进于：每一趟匹配过程中出现字符不等时，无需回溯主串的指针，而是利用已经得到的“部分匹配”的结果将模式向右“滑动”尽可能元的一段距离后，继续进行比较，在求得next数组之后，KMP算法的步骤如下：

若在匹配过程中si = tj，则i与j分别增1，否则i不变；而j退到next[j]的位置再比较，若相等则个指针自增一，否则j再退到下一个next的位置，以此类推，直至以下两种可能：

一种是退到某个next值时字符相等，则各指针自增1，继续匹配，另一种是j退到0，则此时需要将模式继续向右滑动一个位置，即从主串的下一个字符si + 1起和模式串重新开始匹配

与BF算法类似，不同之处在于在匹配中产生失配的时候，指针i不变，指针j退回至next[j]所指的位置重新开始比较，并且当指针j退回至0时，指针i和j同时自增1，即若主串的第i个字符和模式的第一个字符不等，应从主串的第i + 1个字符起重新开始比较

求取模板串next数组

void get_next(SString S,int next[])//求取next数组 
{
	int i = 1,j = 0;
	next[1] = 0;
	while(i < S.length)
	{
		if(j == 0 || S.ch[i] == S.ch[j])
		{
			i ++ ;
			j ++ ;
			next[i] = j;
		}
		else j = next[j];
	}
}

 开始KMP字符串匹配

int KMP(SString S,SString T,int pos)
{
	int i = pos;
	int j = 1;
	while(i <= S.length && j <= T.length)
	{
		if(j == 0 || S.ch[i] == T.ch[j])
		{
			i ++ ;
			j ++ ;
		}
		else j = next[j];
	}
	if(j > T.length)return i - T.length;
	else return 0;
}

当然，虽然BF的算法时间复杂度为O(n * m)，但是在情况下，其实际的执行时间近似于O(n + m)，因此至今仍然被采用，KMP算法仅当模式与主串之间存在许多"部分匹配"的情况下，才会显得比BF算法快得多。KMP算法的最大特点时指针i不需要回溯，整个匹配过程中，对主串仅需从头至尾遍历一遍，这对处理从外设输入的庞大文件很有效，可以边读入边匹配，而无需从头回读

前面定义的构造next数组仍然有缺陷，在处理有着多个连续重复的字符时，产生的next数组往往会在使用的时候多出一些无用的操作导致时间变慢，因此给出修正后的nextval数组

void get_nextval(SString S,int nextval[])
{
	int i = 1,j = 0;
	nextval[1] = 0;
	while(i < S.length)
	{
		if(j == 0 || S.ch[i] == S.ch[j])
		{
			i ++ ;
			j ++ ;
			if(S.ch[i] != S.ch[j])nextval[i] = j;
			else nextval[i] = nextval[j];
		}
		else j = nextval[j];
	}
} 

数组广义表

tag = 1时表示为表，tag = 2时表示为元素

表长度的得到，顺着表头指针不断的沿tp遍历，遍历了几个节点长度就是几

表深度的得到，沿每个表节点的hp往下遍历得到的最大节点数值 

总结

本章介绍了三种数据结构，分别是：串、数组、广义表

1.串是内容受限的线性表，它限定了表中的字符，串有两种基本存储结构，即顺序存储结构和链式存储结构，但多采用顺序存储结构。串的常用算法是模式匹配算法，主要有BF算法和KMP算法。BF算法实现简单，但存在回溯，效率低，时间复杂度为O(m * n)；KMP算法对BF算法进行了改进，消除了回溯，提高了效率，时间复杂度为O(m + n)

2.多为数组可以看成线性表的推广，其特点是结构中的元素本身可以是具有某种结构的数据，但属于同一数据类型。一个n维数组实质上是n个线性表的组合，其每一维都是一个线性表。数组一般采用顺序存储结构，故存储多维数组时，应先将其转换为一维结构，转换方式有按“行”转换和按“列”转换两种。科学与工程计算中的矩阵通常用二维数组来表示，为了节省存储空间，对于几种常见形式的特殊矩阵登，比如对称矩阵、三角矩阵和对角矩阵，在存储时可以进行压缩存储，即多个值相同的元只分配一个存储空间，对零元不分配存储空间

3.广义表是另外的一种线性表的推广形式，表中的元素可以是称为原子的单个元素，也可以是子表，所以线性表可以看成广义表的特例。广义表的结构相当灵活，在某种前提下，它可以兼容线性表、数组、树、有向图等各种常用的数据结构，广义表的常用操作有取表头和取表尾，广义表通常采用链式存储结构存储，包括头尾链表的存储结构和扩展线性链表的存储结构