数据结构，数据结构与算法
串的基本概念
字符串：应用在非数值处理、事务处理等领域。
计算机的硬件：主要是反映数值计算的要求。
字符串的处理比具体数值处理复杂。
串(字符串)：是零个或多个字符组成的有限序列。记作： S=“a1a2a3…”，其中S是串名，ai(1≦i≦n)是 单个字符，可以是字母、数字或其它字符。
串值：双引号括起来的字符序列，引号不属于串的内容。
串长：串中所包含的字符个数。
空串(空的字符串)：长度为零的串，它不包含任何字符。
空格串(空白串)：构成串的所有字符都是空格。
注意：空串和空白串的不同，空格串是有内容有长度的，而且可以不止一个空格；例如“ ”和“”分别表示长度为3的空白串和长度为0的空串。
子串(substring)：串中任意个连续字符组成的子序列称为该串的子串，包含子串的串相应地称为主串。
子串的序号：子串在主串中首次出现时,该子串的首字符对应在主串中的序号，称为子串在主串中的序号（或位置）。
例如，A=“This is a string”，B=“is”，
B是A的子串，A为主串。
B在A中的序号为3 。
特别地，空串是任意串的子串，任意串是其自身的子串。
串的基本操作
对于串的基本操作，许多高级语言均提供了相应的运算或标准库函数来实现。下面先介绍几种在C语言中常用的串运算。
定义下列几个变量：
char s1[20]=“dirtreeformat”;
char s2[20]=“file.mem”;
char s3[30], *p;
int result;（1）求串长(length)
int strlen(char *s); //求串的长度
例如：printf(“%d”,strlen(s1)); 输出13
（2）串复制(copy)
char *strcpy(char *to,char *from);
该函数将串from复制到串to中，并且返回一个指向串to的开始处的指针。
例如：strcpy(s3,s1); //s3=“dirtreeformat”
(3)联接(concatenation)
char * strcat(char *to,char *from)
该函数将串from复制到串to的末尾，并且返回一个指向串to的开始处的指针。
例如：strcat(s3,”/”);
strcat(s3,s2); //s3=“dirtreeformat/file.mem”
(4)串比较（compare)
int strcmp(char *s1,char *s2);
该函数比较串s1和串s2的大小，当返回值<0，=0或>0时分别表示s1<s2、s1=s2或s1>s2
例如：result=strcmp(“baker”,”Baker”) result>0
result=strcmp(“12”,”12”); result=0
result=strcmp(“Joe”,”Joseph”); result<0
（5）字符定位(index)
int strchr(char *s, char c);
该函数是找c在字符串中第一次出现的位置，若找到则返回该位置，否则返回NULL。
串的存储表示和实现
串是一种特殊的线性表，其存储表示和线性表类似，但又不完全相同。串在计算机中有3种表示方式：
◆ 定长(静态)顺序存储表示：将串定义成字符数组，利用串名可以直接访问串值。用这种表示方式，串的存储空间在编译时确定，其大小不能改变。
◆ 堆分配(动态顺序)存储方式：仍然用一组地址连续的存储单元来依次存储串中的字符序列，但串的存储空间是在程序运行时根据串的实际长度动态分配的。
◆ 块链存储方式：是一种链式存储结构表示。
串的定长顺序存储表示
这种存储结构又称为串的顺序存储结构。所谓定长顺序存储结构，是直接使用定长的字符数组来定义，数组的上界预先确定。
定长顺序存储结构定义为：
＃define MAX_STRLEN 256
typedef struct
{ char str[MAX_STRLEN] ;
int length;
} StringType ; 1 串的联结操作
Status StrConcat ( StringType *s, StringType t)
/* 将串t联结到串s之后，结果仍然保存在s中 */
{ int i, j ;
if ((s->length +t->length)>MAX_STRLEN)
return ERROR ; /* 联结后长度超出范围 */
for (i=0 ; i<t->length ; i++)
s-> str[s->length+i]=t->str[i] ; /* 串t联结到串s之后 */
s->length= s->length+ t->length ; /* 修改联结后的串长度 */
return OK ;
}
1 串的联结操作
Status StrConcat(HString *T, HString s1, HString s2)
/* 用T返回由s1和s2联结而成的串 */
{ int k, j , t_len ;
if (T.ch) free(T); /* 释放旧空间 */
T-> length =s1.length+s2.length ;
if (( T->ch=(char *)malloc(sizeof((char)*t_len))==NULL)
{ printf(“系统空间不够，申请空间失败 ！\n”) ;
return ERROR ; }
for ( j=0 ; j<s1.length; j++ )
T->ch[j]=s1.ch[j] ; /* 将串s1复制到串T中 */
for ( j=s1.length, k=0 ; k<s2.length; k++, j++)
T->ch[j]=s2.ch[k] ; /* 将串s2复制到串T中 */
return OK ;
}
串的模式匹配算法
模式匹配(模范匹配)：子串在主串中的定位称为模式匹配或串匹配(字符串匹配) 。模式匹配成功是指在主串S中能够找到模式串T，否则，称模式串T在主串S中不存在。
模式匹配的应用在非常广泛。例如，在搜索引擎和文本编辑程序中，我们经常要查找某一特定单词在文本中出现的位置。显然，解此问题的有效算法能极大地提高文本编辑程序的响应性能。
模式匹配是一个较为复杂的串操作过程。迄今为止，人们对串的模式匹配提出了许多思想和效率各不相同的计算机算法。