计算机上的非数值处理的对象基本上是字符串数据。
串类型的定义
串(string)是由零个或多个字符组成的有限序列，一般记为：
其中s是串的名，用单引号括起来的字符序列是串的值；串中字符数目n称为串的长度，零个字符的串称为空串，它的长度为零。
串中任意个连续的字符组成的子序列称为该串的子串，包含子串的串相应地称为主串。通常称字符在序列中的序号为该字符在串中的位置。
称两个串是相等，当且仅当这两个串的值相等，只有当两个串的长度相等，并且各个对应位置的字符都相等时才相等。
在各种应用中，空格常常是串的字符集合中的一个元素，因而可以出现在其他字符中间。由一个或多个空格组成的串‘ ’称为空格串，此处不是空串。
串的定长顺序存储表示
用一组地址连续的存储单元存储串值得字符序列:
#define MAXSTRLEN 255 //用户可在255以内定义最大串长
typedef unsigned char SString[MAXSTRLEN+1]; //0号单元存放串的长度
串的堆分配存储表示
以一组地址连续的存储单元存放串值字符序列，但它们的存储空间是在程序执行过程中动态分配而得。在C语言中存在一个称之为”堆”的自由存储区，并有C语言的动态分配函数malloc()和free()来管理。利用函数malloc()为每个新的串分配一块实际串长所需的存储空间。
完整代码：
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
//函数结果状态代码
#define OK 1
#define ERROR 0
typedef int Status;
//串的堆分配存储表示
typedef struct{
char *ch; //若是非空串 则按串长分配存储区 否则ch为NULL
int length; //串长度
}HString;
//赋值操作
Status StrAssign(HString &T,char *chars){
if(!T.ch) free(T.ch); //释放T原有空间
int i=0;
char *c;
for(i=0,c=chars;*c;i++,c++); //求chars的长度
if(!i){
T.ch=NULL;
T.length=0;
}else{
if(!(T.ch=(char*)malloc((i+1)*sizeof(char))))
exit(OVERFLOW);
for(int j=0;j<i;j++)
T.ch[j]=chars[j];
T.ch[i]='\0';
T.length=i;
}
return OK;
}
//比较
int StrCompare(HString S,HString T){
for(int i=0;i<S.length&&i<T.length;i++){
if(S.ch[i]!=T.ch[i])
return S.ch[i]-T.ch[i];
}
return S.length-T.length;
}
//字符串合并
Status Concat(HString &T,HString s1,HString s2){
if(!T.ch) free(T.ch);
if(!(T.ch=(char*)malloc((s1.length+s2.length+1)*sizeof(char))))
exit(OVERFLOW);
for(int i=0;i<s1.length;i++)
T.ch[i]=s1.ch[i];
for(int i=0;i<s2.length;i++)
T.ch[i+s1.length]=s2.ch[i];
T.length=s1.length+s2.length;
T.ch[T.length]='\0';
return OK;
}
//求子串
Status SubString(HString &Sub,HString s,int pos,int len){
if(pos<1||pos>s.length||len<0||len>s.length-pos+1)
return ERROR;
if(!Sub.ch) free(Sub.ch);
if(!len){ //空子串
Sub.ch=NULL;
Sub.length=0;
}else{
Sub.ch=(char*)malloc((len+1)*sizeof(char));
for(int i=0;i<len;i++)
Sub.ch[i]=s.ch[pos-1+i];
Sub.ch[len]='\0';
Sub.length=len;
}
return OK;
}
//串的模式匹配算法
int Index(HString s,HString T,int pos){
int i=pos-1;
int j=0;
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)
return i-T.length+1;
else
return 0;
}
int main(){
HString T1,T2,T3;
char *chars1="dagfd";
StrAssign(T1,chars1);
char *chars2="TTTdddTT";
StrAssign(T2,chars2);
Concat(T3,T1,T2);
printf("%s %d\n",T3.ch,T3.length);
HString T4;
SubString(T4,T3,1,4);
printf("%s\n",T4.ch);
HString T5;
StrAssign(T5,"dT");
printf("%s\n",T5.ch);
printf("%d\n",Index(T3,T5,6));
system("pause");
}
串的块链存储表示
可采用链表方式存储串值，链表结构中每个结点可以存放一个字符，也可以存放多个字符。
称如此定义的串存储结构为块链结构。
#define CHUNKSIZE 80 //块的大小
typedef struct Chunk{
char ch[CHUNKSIZE];
struct Chunk *next;
}Chunk;
typedef struct{
Chunk *head,*tail; //串的头和尾指针
int curlen; //串的当前长度
}LString;