串的类型定义
ADT String{
数据对象:D={ai|ai∈CharacterSet,i=1,2,......,n, n>=0}
数据关系:R={<ai-1,ai>|ai-1,ai∈D,i=1,2,......,n}
基本操作:
StrAssign(&T,chars) // 串赋值
StrCompare(S,T) // 串比较 (比较是通过ASCII码)
StrLength(S) // 求串长
Concat(&T,S1,S2) // 串连接
SubString(&Sub,S,pos,len) // 求子串
StrCopy(&T,S) // 串拷贝
StrEmpty(S) // 串判空
ClearString(&S) // 清空串
Index(S,T,pos) // 子串的位置
Replace(&S,T,V) // 串的替换
StrInsert(&S,pos,T) // 子串的插入
StrDelete(&S,pos,len) // 子串删除
DestroyString(&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 curlen; // 串的当前长度
}LString; // 字符串的块链结构