数据结构与算法——串
今天将讲解一下数据结构中的串
说实话我觉得推送应该做得实用
所以应该，加点题目提高实用性
有同学想看Python，下期安排
串的定义：
串 ( string ) 是由零个或任意多个字符组成的有限序列。一般记为：
S="a1a2a3.......an"(n>=0)
其中， S 为串名， 在本书中用双引号作为串的定界符 ， 引号括起来的字符序列为串值，ai(1<=i<=n)可以是字母、数字或其他字符,n 为串的长度.
串的相关术语：
(1) 空串。不含任何字符的串称为空串， 即串的长度n=O 时的串为空串。
(2) 空格串。由一个或多个称为空格的特殊字符组成的串称为空格串， 它的长度是串中空格字符的个数。
(3) 子串。串中任意个连续的字符组成的子序列称为 该串的子串。另外， 空串是任意串的子串， 任意串是自身的子串。
(4) 主串。包含子串的串称为该子串的主串。
(5) 模式匹配。子串的定位运算又称为串的模式匹配， 是一种求子串在主串中第一次出现的第一个字符的位置。
(6) 两个串相等。两个串的长度相等且各个位置上对应的字符也都相同。
例题：
有以下 4 个串 ：
S1= "Welcome to Beijing!"
S2= "Welcome to"
S3= "Welcometo "
S4="Beijing"
则各串长度及其之间的关系如何？
解：
(1)S1的长度为 19 , S2 的长度为 10 , S3 的长度为 10 , S4 的长度为 7。
(2)S2 和 S4 为 S1 的子串， S1 相对于 S2 和 S4 为其主串， S2 在 S1 的位置为 1, S4 在 S1 的位置为 12。
(3)S3 不是 S1 的子串， 因为它不是S1串中的连续字符组成的子序列（在e 与 t 字母之间缺少一个空格）。
(4)S2 与 S3 串不相等， 因为虽然两串的长度相等， 但各个对应的字符不相同。
顺序串的类型定义与顺序表的定义相似， 可以用一个字符型数组和一个整型变量表示， 其中字符数组存储串， 整型变量表示串的长度。
就好比我们输入“Beijing”，字符串从 S.ch[O]单元开始存放， 用'\O' 来表示串的结束， 则串S的存储示意图如图所示。
储存方式：
由于在内存中的存放方式不同，于是有了紧凑模式和非紧凑模式两种存储方式：
对于长度不确定的字符串的输入 ， 若采用定长字符串存储就会产生这样的问题 ： 存储空间定的大， 而实际输入字符串长度小， 则造成内存空间的浪费； 反之， 存储空间定的小， 而实际输入字符串长度大， 则不够存储。此时可采用链接存储的方法。
总结：
链式存储结构的使用大多数是数据输入个数不确定的情况
用链表存储字符串，每个结点有两个域：一个数据域 ( data ) 和一个指针域 (next)，和单链表一样。在串的链式存储结构中，有如下结构：
数据域 ( data )：存放串中的字符。
仍然以存储 S="Hello boy"为例， 链接存储结构如图所示。
链接存储的优点—— 插入、删除运算方便。
链接存储的缺点—— 存储、检索效率较低。
在各种串的处理系统中 ， 所处理的串往往很长或很多。例如 一本书的几百万个字符 ， 情报资料的几千万个条目，这就必须考虑字符串的存储密度。
存储密度 ＝ 串值所占的存储位／ 实际分配的存储位
串链接存储的存储密度小， 存储量比较浪费， 但运算处理， 特别是对串的连接等操作的实现比较方便。
由于字符串的特殊性，用链表作为字符串的存储方式也不太实用，因此使用较少。
当时看到这个名词，堆分配，我也蒙了。
在实际应用中，往往要定义很多字符串，并且各字符串长度在定义之前又无法确定。在这种情况下，可以采用堆分配存储（也称为索引存储），这是一种动态存储结构。
方法：
上例子：
设字符串：
S1 = "boy"
S2="girl"
S3="man"
S4="woman"
索引表如图所示：
所以我们的这个结构的定义是这样的：
下面我们用代码来实现这些内容：
定义字符串顺序存储的结构
length表示的是表长，和顺序表没有区别。
顺序串的插入和删除等操作与顺序表相同。因此，我们主要学习串的插入、删除、 查找、比较、取子串、连接等基本操作。（蛇皮操作！）
求串的长度：
由于我们以"\0"为字符串的结束符号，所以我们遍历整个字符串，遇到'\0'为止。
最后返回长度。
建立字符串：
用gets函数来读取字符串并放入储存空间中
调用函数StrLength（s），赋值字符串的长度给length。
求子串操作：
求串 S 从第 pos 位置开始， 长度为 len 的子串，并将其存入到串 Sub中。操作成功返回 1, 不成功返回 0。
如果，我们选择的位置<1，或者我们的位置大于主串的长度，（即选择的位置不在主串的范围内），报错，返回子串长度为0。
如果我们的子串是空串（len<1），或者这个子串的长度已经超过了pos位置的后续字符串长度，报错，返回子串长度为0。
之后我们读取后续子串的每一个字符存放在sub中，将最后一个字符赋值为"\0";
最后返回长度。
删除子串的操作：
将删除串 S 从指定位置 i 开始的连续 l 个字符。算法思路如下。
首先判断删除位置和删除串长度是否出错， 出错给出错误信息后返回 0。
不出错则继续下面操作：将第 i+l- 1 位的字符向前移到第i 位上， 以此类推， 直到最后一个字符移动完毕。最后修改串 S 的长度， 将新串 S 的尾部加上字符串结束标志‘\0' ( 不加该语句多次运行程序会出错）， 操作成功， 返回 1。
插入子串操作:
在串 S 中的第 i 位置开始插入子串 S1。算法思路如下。首先判断
插入子串的位置是否出错 ， 然后再判断两串长度是否超过存储空间长度 ， 都不出错则进行插入。
首先从最后一个字符开始向后移动子串 S1 长度， 直到第 i
个字符结束。移动完毕将子串 S1 的每个字符复制到串S 的第 i 位开始的各位置上， 完成插入子串过程。最后修改串
S 的长度， 将新串 S 的尾部加上字符串结束标志'\0' ( 不加该语句多次运行程序会出错）， 操作成功， 返回 1 。
串的定位操作：
若串s 中存在与串t 相同的子串， 则返回串 t 在串 s 中第一次出现的位置， 否则返回- 1。
算法思路如下。首先将i,j分别指向串 s 和串 t, 当 i,j 没有指向两串尾时进行循环：对应位置字符相同则继续比较下一个字符， 如果不相同则令i等于i-j+1且j等于 0 进行下一次的字符串首字符比较。循环完毕后若j大于等于串 t 的长度， 说明串 S 中有子串 t, 返回其首次出现的起始位置， 否则说明串s 中没有子串 t, 返回- 1。
#include<stdio.h>#include<stdio.h>#define MAXSIZE 100typedef struct{char ch[MAXSIZE];int length;}String;int StrLength(String *s){int i=0;while(s->ch[i]!='\0')i++;s->length=i;return (s->length);}void CreatStr(String *s){gets(s->ch);s->length=StrLength(s);}int SubSring(String *s,String *sub,int pos,int len){int j;if(pos<1||pos>s->length||len<1||len>s->length-pos+1){sub->length=0;printf("参数错误");return 0;}else{for(j=0;j<len;j++)sub->ch[j]=s->ch[pos+j-1];sub->ch[j]='\0';sub->length=len;return 1;}}int StrDelete(String *s,int i,int l){int k;if(i+l-1>s->length){printf("要求删除的子串越界！");return 0;}else{for(k=i+l-1;k<s->length;k++,i++){s->ch[i-l]=s->ch[k];}s->length=s->length-l;s->ch[s->length]='\0';return 1;}}int StrInsert(String *s,String *s1,int i){int k;if(i>s->length+1){printf("插入位置错误！");return 0;}else if(s->length+s1->length>MAXSIZE){printf("两串长度超过储存空间长度");return 0;}else{for(k=s->length-1;k>=i-1;k--)s->ch[s1->length+k]=s->ch[k];for(k=0;k<s1->length;k++)s->ch[i+k-1]=s1->ch[k];s->length=s->length+s1->length;s->ch[s->length]='\0';return 1;}}int StrIndex(String *s,String *t){int i=0,j=0,k;while(i<s->length && j<t->length){if(s->ch[i]==t->ch[j]){i++;j++;}else{i=i-j+1;j=0;}}if (j>t->length)k=i-t->length+1;elsek=-1;return k;}
冲冲冲！！