串的定义

串（string）——零个或多个任意字符组成的有限序列串是内容受限的线性表

串的几个术语

子串：串中任意几个连续字符组成的子序列称为该串的子串（真子串是指不包含自身的所有子串）主串：包含子串的串相应地称为主串字符位置：字符在序列中的序号为该字符在串中的位置子串位置：子串第一个字符在主串中的位置空格串：由一个或多个空格组成的串  与空串不同

 串相等：当且仅当两个串的长度相等并且各个对应位置上的字符都相同时，这两个串才时相等的。

        串的应用非常广泛，计算机上的非数值处理的对象大部分是字符串数据，例如：文字编辑、符号处理、各种信息处理系统等等。

串的类型定义、存储结构

串的抽象类型定义

<code>串的抽象类型定义

ADT String{

数据对象：D={ ai | ai ∈ CharacterSet，i=1，2，…，n，n≥0}

数据关系：R1={ < a(i-1),ai > | a(i-1),ai ∈ D，i=2，…，n }

基本操作：

StrAssign（&T,chars）  

// 生成一个其值等于chars的串T(chars是字符串常量)

StrCopy（&T,S）  

// 由串S复制得T

StrEmpty（S）  

// 若S为空串，返回true，否则返回false

StrCompare（S,T）  

// 若S>T，则返回值>0；若S=T，则返回值=0；若S<T，则返回值＜0

StrLength（S）  

// 返回S的元素个数，称为串的长度

ClearString（&S）  

// 将S清为空串

Concat（&T,S1,S2）  

// 用T返回由S1和S2联接而成的新串

SubString（&Sub,S,pos,len）  

// 用Sub返回串S的第pos个字符起长度为len的子串

Index（S,T,pos）  

// 若主串S中存在和串T值相同的子串，则返回它在主串S中第pos个字符之后第一次出现的位置；否则函数值为0

Replace（&S,T,V）  

// 用V替换主串S中出现的所有与T相等的不重叠的子串

StrInsert（&S,pos,T）  

// 在串S的第pos个字符之前插入串T

StrDelete（&S,pos,len）  

// 从串S中删除第pos个字符起长度为len的子串

DestroyString（&S）  

// 销毁串S

}ADT String

串的存储结构

        串中元素逻辑关系与线性表的相同，串可以采用与线性表相同的存储结构。

串的顺序存储

        串的定长顺序存储结构，可以简单地理解为采用 “固定长度的顺序存储结构” 来存储字符串，因此限定了其底层实现只能使用静态数组。使用定长顺序存储结构存储字符串时，需结合目标字符串的长度，预先申请足够大的内存空间。

<code>//------串的定长顺序存储结构-------

#define MAXLEN 255 //串的最大长度

typedef struct{

char ch[MAXLEN+1]; //存储串的一维数组

int length; //串的当前长度

}SString;

串的链式存储 

 想要方便，又想要提高存储密度，可以在一个结点存储多个字符，以克服缺点

 这种存储结构称为块链存储结构

<code>//-------串的链式存储结构---------

#define CHUNKSIZE 80 //可由用户定义的块大小

typedef struct Chunk{

char ch[CHUNKSIZE];

struct Chunk*next;

}Chunk;

typedef struct{

Chunk *head,*tail; //串的头和尾指针

int length; //串的当前长度

}LString; //字符串的块链结构