ch4串

新的一篇总结，较为简陋，主要是因为核心内容KMP算法之前就写过了

上一单元总结传送门：ch3栈和队列

串的基本概念：

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

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

☺主串：包含子串的串称为主串。

☺空串： n=0时的串为空串**(Null String)**。

☺空格串：’ ’

☺例如，‘abcde’的子串有：

♫‘’、‘a’、‘ab’、‘abc’、‘abcd’和‘abcde’等

注意空串和空格串别搞混了就行

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

串的不同储存实现方法：

无非就是静态（顺序串）卡死长度与内存，或者换用动态（堆串、块链串）调用堆栈一类来分配内存。

定长型代码：

#define MAXLEN 40
typedef struct {   /*串结构定义*/
    char ch[MAXLEN];
    int len;
} SString; 
//仍然是设计成结构类型，但是长度早在编译时就确定了

堆串代码：

typedef struct{
    char *ch;	//若是非空串，按串长分配空间，否则ch为NULL
    int length;	//串长
} string;
/*这种存储方法以一组地址连续的存储单元存放串的字符序列，但它们的存储空间是在程序执行过程中动态分配的。
系统将一个地址连续、容量很大的存储空间作为字符串的可用空间，每当建立一个新串时，系统就从这个空间中分配一个大小和字符串长度相同的空间存储新串的串值。 
在C语言中，存在一个称为“堆”的自由空间，由动态分配函数malloc( )分配一块实际串长所需的存储空间，如果分配成功，则返回这段空间的起始地址，作为串的基址。由free( )释放串不再需要的空间。*/

块链串代码：

#define  BLOCK_SIZE  4  /*每结点存放字符个数*/
typedef struct Block{
    char ch[BLOCK_SIZE];	 /*BLOCK_SIZE为1，就是单链表结构*/
    struct Block   *next;
} Block;

typedef struct {
    Block   *head;
    Block   *tail; 	/* tail联接2个串使用*/
    int     length;
} BLString; 

存储密度：

☺ “存储密度”= 结点数据本身占用的空间 / 结点占用的空间总量

☺ 存储密度小（如节点大小为1时，每个结点存放一个字符），运算处理方便，但存储占用量大。

☺ 存储密度大，当一个块内存放多个字符时，往往使操作过程变的较为复杂，如在串中插入一个字符或删除一个字符，通常需要将字符在块间移动。

之前的定长串显然是储存密度最大的，但是相对的，对它的操作往往比另外两种存储方式繁琐的多。

串的匹配模式：

这点请移步至我之前写的 数据结构KMP算法 这篇博客进行详细了解