科技数据结构及应用算法n ds5.pdfVIP

5.1串的定义和操作

•串定义

–字符串，由零个或多个字符组成的有限序列。S

＝“aaa”

01n-1

–串的长度：n

–空串：n=0，NullString

–子串与主串，子串的位置（从0开始）

–串的比较：最大相等前缀子序列

•串的基本操作

1)StrAssign(T,chars)strcpy

2)StrCopy(T,S)strcpy

3)StrEmpty(S)strlen(S)0

4)StrCompare(S,T)strcmp

5)StrLength(S)strlen

6)Concat(T,S1,S2)strcat

7)Substring(Sub,S,Pos,len)0=pos=Strlength(S)-1

0=len=Strlength(S)-posstrncpy

8)Index（S，T，pos）0=pos=Strlength(S)-1strstr

9)Replace(S,T,V)

10)StrInsert(S,pos,T)0=pos=Strlength(S)

11)StrDelete(S,pos,len)0=pos=StrLength(S)-len

12)DestroyString(S)

•最小操作子集

StrAssign、StrCompare、StrLength、Concat，Substring

5.2串的表示

1.定长顺序表示

•两种表示方法

–下标为0的数组存放长度(pascal)

typedefunsignedcharSString[MAXSTLEN+1];

–在串值后面加‘\0’结束(C语言)

charstr[10];

算法5.2voidConcat_Sq(charS1[],charS2[],charT[]

【注意】T[]必须足够长度，否则会溢出

算法5.3voidSubstring_Sq(charSub[],charS[],intpos,int

len)

5.2.2堆分配表示

•串变量的空间是在程序执行过程中动态分配

的，程序中出现的所有串变量可用的空间是

一个共享空间，称为“堆”。

算法5.4voidStrinsert_HSq(char*S,intpos,char*T)

【更正】：缺少delete[]S。S其实不可重新分配地址，

因其在函数内不可改变地址值(即S指针)。

算法5.5voidStrinsert(char*S,intpos,char*T)

利用C语言固有函数

【更正】：S1=strdup(S)改为S1=S，无需分配空间。S

同上

5.2.3块链表示

•用链表来串。存在节点大小问题

ConstCHUNKSIZE=80;

typedefstructChunk{

charch[CHUNKSIZE];

structChunk*next;

}Chunk;

typedefstruct{

Chunk*head,*tail;

intcurlen;

}Lstring;

Relplacestring实现

char*replacestring(char*s,char*oldstr,char*n