数据结构——串的定义及存储结构
串的定义
- 串（string）——零个或多个任意字符组成的有限序列
- 串是内容受限的线性表
串的几个术语
- 子串：串中任意几个连续字符组成的子序列称为该串的子串（真子串是指不包含自身的所有子串）
- 主串：包含子串的串相应地称为主串
- 字符位置：字符在序列中的序号为该字符在串中的位置
- 子串位置：子串第一个字符在主串中的位置
- 空格串：由一个或多个空格组成的串 与空串不同
- 串相等：当且仅当两个串的长度相等并且各个对应位置上的字符都相同时，这两个串才时相等的。
串的应用非常广泛，计算机上的非数值处理的对象大部分是字符串数据，例如：文字编辑、符号处理、各种信息处理系统等等。
串的类型定义、存储结构
串的抽象类型定义
串的抽象类型定义
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串的存储结构
串中元素逻辑关系与线性表的相同，串可以采用与线性表相同的存储结构。
串的顺序存储
串的定长顺序存储结构，可以简单地理解为采用 “固定长度的顺序存储结构” 来存储字符串，因此限定了其底层实现只能使用静态数组。使用定长顺序存储结构存储字符串时，需结合目标字符串的长度，预先申请足够大的内存空间。
//------串的定长顺序存储结构-------
#define MAXLEN 255 //串的最大长度
typedef struct{char ch[MAXLEN+1]; //存储串的一维数组int length; //串的当前长度
}SString;
串的链式存储
想要方便，又想要提高存储密度，可以在一个结点存储多个字符，以克服缺点
这种存储结构称为块链存储结构
//-------串的链式存储结构---------
#define CHUNKSIZE 80 //可由用户定义的块大小
typedef struct Chunk{char ch[CHUNKSIZE];struct Chunk*next;
}Chunk;
typedef struct{Chunk *head,*tail; //串的头和尾指针int length; //串的当前长度
}LString; //字符串的块链结构