数据结构（12.1）串结构的定义
数据结构（12.1）串结构的定义
前⾔
串是⼀种⽐较特殊的数据结构，它是计算机上⾮数值处理的主要对象。
事实上在C语⾔中，是没有“字符串”这个变量类型的，虽然可以通过字符指针 char *p 这样来记录⼀个字符串，p本质上仍是⼀个字符指针，保存的是⼀个字符的地址。因此，C语⾔中的保存⼀个字符串，只是保存它⾸个字符的地址。但是到了诸如Java这样的语⾔⾥，提供了⼀种String类，可以直接⽤String s 来记录字符串，String和int、char⼀样是⼀种数据类型（只不过不是基本的数据类型，⽽是属于引⽤类型）。并且Java提供了很多操作函数，可以直接实现对字符串的相关操作。当然，C语⾔中虽然没有明确的字符串类型，但是同样存在字符串操作函数。
串的定义
定义：串（或字符串）是由零个或多个字符组成的有限序列，⼀般记为：s = ‘a1a2…an’（n>=0)
串的名称：s
画公主
串的值：⽤单引号（有些书中也⽤双引号）括起来的字符序列，可以是数字、字母或者其他字符。但是单引号本⾝不属于串，它的作⽤是避免与变量名或数的常量混淆。
串的长度：n
有关概念
空串：零个字符的串称为空串，其长度为零。例如 s = ‘’。
⼦串：串中任意个连续的字符组成的⼦序列称为该串的⼦串，例如 s = ‘abcde’，t = ‘abc’，则 t 是 s 的⼦串
主串：包含⼦串的串相应地称为主串，例如 s = ‘abcde’，t = ‘abc’，那么 s 就是 t 的主串
串的位置：字符在序列中的序号称为该字符在串中的位置，例如s = ‘abcde’，字符’ b '在 s 中的位置就是2（在实际应⽤中为了⽅便数组操作，也可以从零开始数，则此处就为1）。
⽽⼦串在主串中的位置，则⽤⼦串的第⼀个字符在主串中的位置来表⽰。例如 s = ‘abcde’，t = ‘cd’，⼦串 t 在 s 中的位置为3。
串相等：只有两个串的长度相等，并且各个对应位置的字符都相等时才称为串相等。例如 s = ‘abc’，t = ‘ab c’，此时 s 和 t 并不相等（空格也属于字符集合中的⼀个元素）。
空格串：由⼀个或者多个空格组成的串，称为空格串。例如 s = ’ '，此时 s 串是空格串，但不是空串，其长度为空格的数量。
南张北周串的存储结构
回顾线性表的概念：由n(n>=0)个数据特性相同的元素构成的有限序列。
可以发现，同样是有限序列，串的逻辑结构和线性表是很相似的，区别仅在于串的约束对象是字符集。也就是说，假如字符串中存储的
是’123456’这么⼀串，实际上它保存的类型是char，⽽不是int。
布丁仓鼠
那么，把线性表的存储类型改为char不也能表⽰串吗？按理来说是这样，但是串与线性表的主要区别是在操作上。在线性表的基本操作中，多以”单个元素“作为操作的对象，例如插⼊、删除等，多是对某个元素进⾏操作；⽽在线性表中，多以“串的整体”作为操作的对象，⽐如插⼊，多是插⼊另⼀个串，⽽不是单个字符。因此，串的操作和线性表有很⼤不同，需要把串当成与线性表不同的逻辑结构来看待。
从存储结构上来说，串也有两种基本的存储结构：顺序存储和链式存储。
顺序存储
有些资料中说，串有三种机内表⽰⽅法，分别是定长顺序表⽰、堆分配存储表⽰和块链存储表⽰。实际上，定长顺序表⽰和堆分配表⽰都属于顺序存储。
顺序存储的特点是，使⽤⼀组地址连续的存储单元来进⾏存储。我们使⽤顺序存储结构时，往往需要在⼀开始去申请⼀整块的内存空间，然后在我们所申请好的这块内存空间内来插⼊、删除元素；这样就会出现⼀个问题：如果这块空间满了，⼜有新元素需要存⼊，应该怎么办呢？
在我们以往的实现中，有两种做法：第⼀种是逻辑上我的这个存储空间已经满了，就不允许再存⼊了，它的内存是静态的，能存多少元素已经在⼀开始确定了。⽽第⼆种则会在空间满的时候去重新申请⼀块更⼤的空间，只有当物理内存真正满了，空间申请失败的时候，才不允许再存⼊，它的内存是动态分配的。
我们把采⽤第⼀种处理⽅法称为定长顺序表⽰，定长即串空间的⼤⼩在编译的时候就确定了，不允许再更改，顺序则意味着它的地址空间是连续的。⽽第⼆种处理⽅法称为堆分配表⽰，因为C语⾔的内存分为五⼤分区，其中⼀个区叫做堆（heap）区，这个区的空间可以让程序员来进⾏分配释放，我们
调⽤malloc和free函数，就是在对堆区的内存进⾏操作。在堆分配表⽰中，串的空间可以动态分配，意味着串长可以任意（只要不超过实际的内存），但是它的地址空间仍然是连续的。
定长顺序表⽰
在定长顺序表⽰⾥，需要规定⼀个最⼤串长，在串创建时就按照预定义的⼤⼩为每个串分配固定的存储区，串的实际长度可以在预定义的范围之内，超过预定义长度的部分将会被舍去，称为”截断“。
堆分配表⽰
在堆分配表⽰中，存储空间是在程序执⾏过程中动态分配⽽来的，所占的空间由串的实际长度决定。需要注意的是，即使是动态分配，它的空间也是连续的⼀整块，可以去查⼀下malloc、relloc和calloc函数的细节。
顺序存储中串结构的设计
雨后小故事图
⽆论是顺序存储还是链式存储，都⾸先需要考虑⼀个问题：怎样确定串已经结束了？实际上它也可以转换成另⼀个问题：怎样确定串的实际长度？针对这两个问题的不同回答，决定了对串结构的不同设计。在这⾥先说顺序存储中的情况。
假设我们从串长的⾓度来考虑，只需要额外使⽤⼀个变量来保存串的长度，并且实时更新就可以了。这样，我们可以设计出来⼀个结构体，它包括⼀个存储串的空间，和⼀个保存串当前长度的整型变量
定长顺序表⽰：
#define MAXSTRLEN 255 //最⼤串长
typedef struct SString{
char ch[MAXSTRLEN];//存储串的⼀维数组
int length;//串的当前长度
}SString;
堆分配表⽰：
typedef struct HString{
char*ch;//串的存储空间
int length;//串的当前长度
}HString;
在定长顺序串中，还可以直接把当前长度存到数组中的0号单元⾥，让串从1下标开始，这样⼀开始要开辟的就是最⼤串长+1的空间，并且也不需要结构体了。
#define MAXSTRLEN 255 //最⼤串长
typedef unsigned char SString[MAXSTRLEN+1];//0号单元存放串的当前长度
需要注意，这个时候使⽤ unsigned char 型来保存数值，最⼤串长只能到255。
假如从串结束的问题来考虑，可以和C语⾔的做法⼀样，在串的最后加上⼀个不计⼊串长的字符来标记，⽐如’\0’，这样要开辟的也是最⼤串长+1的空间。由于这个时候的串长是⽆法直接得到的，在有些操作上可能不太⽅便。
定长顺序表⽰：
#define MAXSTRLEN 255 //最⼤串长
通讯录同步助手typedef unsigned char SString[MAXSTRLEN+1];//多出来⼀位⽤于在串满时在末尾加上'\0'
堆分配表⽰：
（初始化时需要记得多申请⼀个位置⽤于存放’\0’，并且在每次串变动后都需要注意’\0’的设置。）
typedef unsigned char* HString;
链式存储
⼀般⽽⾔，链式存储的设计包括两个部分：第⼀是结点的设计，包括结点要保存的内容和后续结点的
指针。第⼆则是针对整个链式结构的设计，⽐如设置头指针尾指针、结点数量等，⽤于对整个结构进⾏管理，并且⽅便⼀些操作。
额外提⼀下，这个“结点要保存的内容”可以很简单，我们平时学习的时候为了简便常常只是设置⼀个int型，得到的只是⼀些数值，感觉似乎没什么⽤；但是它也可以⽐较复杂，例如⼀个学⽣的信息，那么就需要char来记录名字，int来记录年龄、编号等等等等，需要根据实际情况来设置这个结构体，它的应⽤其实是很⼴泛的。
⾔归正传，对结点的设计很重要。按照往常的思路，我们⼀个结点⽤于保存⼀个字符，那么就是这样的：
//结点
typedef struct Node{
char c;//保存字符
struct Node * next;//下⼀个结点
}Node;
这虽然可⾏，但是我们⼀个结点只保存⼀个字符的话，每保存⼀个字符，就要花⼀个额外的空间来保存下⼀个结点的指针，造成⽐较⼤的浪费，由于串的特性，我们也可以考虑⼀个结点保存多个字符。
⼀个结点保存多个字符，⾸先需要设置结点可保存的最⼤字符量，假如我们⽤数组来存储，这实际上就是定长顺序串和链式存储的结合。
#define CHUNCKSIZE 3 //⼀个结点保存三个字符
//结点
typedef struct Chunk{
char ch[CHUNKSIZE];//存储串的⼀维数组
struct Chunk *next;//下⼀个结点
}Chunk;
这⾥可以通过判断next结点是否为空来确定串是否结束，所以不像顺序存储中那么⿇烦。
如图所⽰，假如我们使⽤数组来存储的话，最后⼀个结点它不⼀定会被占满，此时常补上“#”或者其他的⾮串值字符（通常不把“#”包括在串的字符集中，⽽是当做⼀个特殊符号。）
如果不想造成这样的浪费的话，也可以考虑不⽤数组来存储，⽽是动态开辟空间，假如要存储的字符串长度⼤于等于设定的结点长度，就按照设定长度来开辟；假如⼩于，则按照字符串实际的长度来开辟（怎样确定要存储的字符串长度，⼜是⼀个问题）。
#define CHUNCKSIZE 3 //⼀个结点保存三个字符
//结点
扣子手工制作
typedef struct Chunk{
char*ch;//实际空间->按照情况来分配
电脑如何设置自动关机struct Chunk *next;//下⼀个结点
}Chunk;
为了⽅便串的操作，除了头指针外还可以附设⼀个尾指针，并且给出当前串的长度，称这样定义的串存储结构为块链结构，因为单个结点它不是只保存⼀个数据，⽽是⼀“块”数据。
//整个串
typedef struct LString{
Chunk *first;//头指针
Chunk *last;//尾指针
述职报告格式int length;//串长
}LString;
串的链式存储结构在除了某些操作，⽐如连接两个串时，有⼀定的⽅便之处，但是总体⽽⾔没有顺序存储结构灵活，性能也不⾼，因此⽐较少⽤。
