第四章串
串的定义
串的操作
数据结构
之
串24.1 串的定义
¾串：由零个或多个字符组成的有限序列，记为S= “a
1
a
2
a
3
……a
n
”。
¾主串、子串、串名、串长；
S=“How are you,everybody!”
¾空串、空格串；
¾字符在串中的位置、子串在串中的位置；¾两个串相等，当且仅当两个串值相等，即长度，位置相等；
数据结构
之
串3
4.2 串的基本操作
¾StrAssign(&T,chars)
¾StrCompare(S,T): S、T相等返回true，否则返回faule；
¾StrLength(S) : 求串中字符的个数；
¾ConCat(S,T) : 将串T的值紧接着放在串S的末尾，组成一个新串；
字符串长度17模式串长度¾SubString(Sub,S,start,length): 求S从start位置开始，长度为length 的子串；
数
据结构
之
串4¾SetEmpty(&T) : 设置空串
¾StrCopy(S,T): 把T值赋给S；
¾Index(S,T,pos): 求子串在主串中位置的定位函数；¾Replace(S,T,v): 以v替换所有在S中出现的和T相
等的串；
¾StrInsert(S,Pos,T): 在串S的第Pos个字符之前插入串T；
¾StrDelete(S,Pos,len): 从串S中删除Pos个字符起长度为len的子串；
数据结构
之
串54.3 串的表示和实现
¾定长顺序存储表示
¾紧缩格式：在一个存储单元中存放多个字符
¾非紧缩格式：一个存储单元中只存放一个字符，所需存储单元个数即串的长度
例：如一个单元存放k个字符，长度为n，则此串值占[n/k]个存储单元。
D
T
A
:
S
A
A
D T A
S
W T R
C
U T U
E
F S
一个存储单元
数
据结构
之
串6¾动态分配串值的存储空间；
¾动态串的类型定义：typedef struct{
char *ch;
int length; //串的长度}HS;
数据结构
之
串7¾串的链式存储
#define CHUNKSIZE 80 /*由用户定义的块长度*/ typedef struct Chunk {
char ch[CHUNKSIZE]; /*字符串块*/
struct Chunk *next; /*指向下一个字符串块*/ }Chunk; /*结构名称*/
typedef struct {
Chunk *head, *tail; /*指向头尾的指针*/
int curlen; /*串的当前长度*/
} LString; /*串名称*/
F A B C1^
A B C D E F G H1###^
F
数据结构
之
串8¾串基本操作的实现
¾将串S1和串S2联接成新串
¾算法描述：
¾给T分配存储空间，存储空间大小为S1和S2长度
之和。
¾将S1中的每一个字符拷贝到T中。
¾修改T的长度。
¾将S2中的所有字符拷贝到T剩余的存储空间中。
¾返回。
¾程序如下：
数据结构
之
串9Status Concat(Hstring T,Hstring S1,Hstring S2){
int count;
if(T.ch) free(T.ch); /*如果T.ch非空，则释放其存储空间*/
if(!(T.ch=(char *)malloc(S1.length+S2.length+1)*sizeof(char)))) /*分配空间*/
return OVERFLOW; /*若分配失败，则返回溢出信息*/
for(count=0;count<S1.length;count++)
T.ch[count]=S1.ch[count]; /*将S1中字符拷贝到T中*/
T.length=S1.length+S2.length; /*修改长度*/
for(count=S1.length;count<T.length;count++)
T.ch[count]=S2.ch[count-S1.length]; /*将S2中所有字符拷贝到T中*/
T.ch[T.length] = ‘\0’;
return OK; /*返回*/ }
数据结构
之
串10¾求子串T在主串S中的位置
¾算法思想：从主串S的第一个字符
起和模式串（子串）的第一个字符
比较，相等则继续，否则从主串的
第二个字符起重新和模式比较，直
至比较完毕为止。
¾图示
S = “a b a b c a b c a c b a b”
T = “a b c a c”
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论