songzi 2008-5-2 23:48
串的学习与应用（数据结构）
[color=Red][size=6]串的介绍：[/size][/color]
一、串定义
[indent][color=#ff0066]串[/color]（或字符串），是由零个或多个字符组成的有限序列。一般记为：
s='[size=+2]a[/size]1[size=+2]a[/size]2...[size=+2]a[/size]n'(n>=0)
其中s是串的名，用单引号括起来的字符序列是串的值；串中字符的数目n称为串的[color=#ff0033]长度[/color]。零个字符的串称为[color=#ff0000]空串[/color]，它的长度为零。
串中任意个连续的字符组成的子序列称为该串的[color=#ff0033]子串[/color]。包含子串的串相应地称为[color=#ff0033]主串[/color]。通常称字符在序列中的称为该字符在串中的[color=#ff0000]位置[/color]。子串在主串中的位置则以子串的第一个字符在主串中的位置来表示。
例：a='BEI',b='JING',c='BEIJING',d='BEI JING'
串长分别为3,4,7,8,且a,b都是c,d的子串。
称两个串是相等的，当且仅当这两个串的值相等。
[/indent]二、串的抽象数据类型的定义：
[indent]ADT String{
数据对象：D={[size=+2]a[/size]i|[size=+2]a[/size]i(-CharacterSet,i=1,2,...,n,n>=0}
数据关系：R1={<[size=+2]a[/size]i-1,[size=+2]a[/size]i>|[size=+2]a[/size]i-1,[size=+2]a[/size]i(-D,i=2,...,n}
基本操作：
StrAssign(&T,chars)
[indent]chars是字符常量。生成一个其值等于chars的串T。
[/indent]StrCopy(&T,S)
[indent]串S存在则由串S复制得串T
[/indent]StrEmpty(S)
[indent]串S存在则若S为空串,返回真否则返回假
[/indent]StrCompare(S,T)
[indent]串S和T存在,若S>T,则返回值大于0,若S=T,则返回值=0,若S<T,则返回值<0
[/indent]StrLength(S)
[indent]串S存在返回S的元素个数称为串的长度.
[/indent]ClearString(&S)
[indent]串S存在将S清为空串
[/indent]Concat(&T,S1,S2)
[indent]串S1和S2存在用T返回由S1和S2联接而成的新串
[/indent]SubString(&Sub,S,pos,len)
[indent]串S存在,1<=pos<=StrLength(S)且0<=len<=StrLength(S)-pos+1
[/indent]Index(S,T,pos)
[indent]串S和T存在,T是非空,1<=pos<=StrLength(S),若主串S中存在和串T值相同的子串,则返回它在主串S中第pos个字符之后第一次出现的位置,否则函数值为0
[/indent]Replace(&S,T,V)
[indent]串S,T和V存在,T是非空串,用V替换主串S中出现的所有与T相等的不重叠的子串
[/indent]StrInsert(&S,pos,T)
[indent]串S和T存在,1<=pos<=StrLength(S)+1,在串S的第pos个字符之前插入串T
[/indent]StrDelete(&S,pos,len)
[indent]串S存在,1<=pos<=StrLength(S)-len+1从串中删除第pos个字符起长度为len的子串
[/indent]DestroyString(&S)
[indent]串S存在,则串S被销毁
[/indent]}ADT String
[/indent]三、串操作应用举例:
[indent]1文字处理中常用的:串的查找(比较,定位)与替换
在TC集成环境中可用^QF快速查找变量 在WORD中可用搜索与替换批量改变文本
2串的截断与连接
可用求子串及串连接的方法进行文字处理
[/indent]四、总结
[indent]找出几个自己亲自做过的串操作例子。
[size=6][color=Red]串的应用：[/color][/size]
一、复习串的定义
[indent][url=http://www.bccn.net/Article/rjgc/sjjg/200411/242.html]串的定义[/url]
[/indent]二、定长顺序存储表示
[indent]类似于线性表的顺序存储结构,用一组地址连续的存储单元存储串值的字符序列.
#define MAXSTRLEN 255
typedef unsigned char SString[MAXSTRLEN+1] //0号单元存放串长
串的实际长度可在这予定义长度的范围内随意,超过予定义长度的串值则被舍去
串长可用下标为0的数组元素存储,也可在串值后设特殊标记
[table=75%][tr][td][align=center]a[0][/align][/td][td][align=center]a[1][/align][/td][td][align=center]a[2][/align][/td][td][align=center]a[3][/align][/td][td][align=center]a[4][/align][/td][td][align=center]a[5][/align][/td][td][align=center]...[/align][/td][td][align=center]a[n][/align][/td][/tr][/table][table=75%][tr][td=1,1,13%][align=center]3[/align][/td][td][align=center]a[/align][/td][td=1,1,13%][align=center]b[/align][/td][td][align=center]c[/align][/td][td=1,1,13%]
[/td][td]
[/td][td=1,1,10%]
[/td][td=1,1,13%][align=center][color=#ff0000]pascal[/color][/align][/td][/tr][/table][table=75%][tr][td][align=center]a[/align][/td][td=1,1,13%][align=center]b[/align][/td][td][align=center]c[/align][/td][td=1,1,13%][align=center]\0[/align][/td][td]
[/td][td=1,1,12%]
[/td][td]
[/td][td=1,1,13%][align=center][color=#ff0033]c[/color][/align][/td][/tr][/table]1串联接的实现Concat(&T,S1,S2)
假设S1,S2和T都是SString型的串变量,且串T是由串S1联结串S2得到的,即串T的值的前一段和串S1的值相等,串T的值的后一段和串S2的值相等,则只要进行相应的"串值复制"操作即可,对超长部分实施"截断"操作
以下是串联接可能出现的三种情况:
[table=98%][tr][td][table=85%][tr=#ffcccc][td=1,1,32%]S1[/td][td]S2[/td][td=1,1,35%]T[/td][/tr][tr][td]4[/td][td=1,1,33%]2[/td][td]6[/td][/tr][tr][td=1,1,32%]a[/td][td]d[/td][td=1,1,35%]a[/td][/tr][tr][td]b[/td][td=1,1,33%]e[/td][td]b[/td][/tr][tr][td=1,1,32%]c[/td][td] [/td][td=1,1,35%]c[/td][/tr][tr][td]d[/td][td=1,1,33%] [/td][td]d[/td][/tr][tr][td=1,1,32%] [/td][td] [/td][td=1,1,35%]e[/td][/tr][tr][td] [/td][td=1,1,33%] [/td][td]f[/td][/tr][tr][td=1,1,32%] [/td][td] [/td][td=1,1,35%] [/td][/tr][tr][td] [/td][td=1,1,33%] [/td][td] [/td][/tr][/table]S1,S2串长和小于最大值
[/td][td=1,1,37%][table=89%][tr=#ffcccc][td]S1[/td][td=1,1,33%]S2[/td][td]T[/td][/tr][tr][td=1,1,32%]6[/td][td]6[/td][td=1,1,35%]8[/td][/tr][tr][td]a[/td][td=1,1,33%]g[/td][td]a[/td][/tr][tr][td=1,1,32%]b[/td][td]h[/td][td=1,1,35%]b[/td][/tr][tr][td]c[/td][td=1,1,33%]i[/td][td]c[/td][/tr][tr][td=1,1,32%]d[/td][td]j[/td][td=1,1,35%]d[/td][/tr][tr][td]e[/td][td=1,1,33%]k[/td][td]e[/td][/tr][tr][td=1,1,32%]f[/td][td]l[/td][td=1,1,35%]f[/td][/tr][tr][td] [/td][td=1,1,33%] [/td][td]g[/td][/tr][tr][td=1,1,32%] [/td][td] [/td][td=1,1,35%]h[/td][/tr][/table]S1,S2串长和超过最大串长
[/td][td][table=89%][tr=#ffcccc][td=1,1,32%]S1[/td][td]S2[/td][td=1,1,35%]T[/td][/tr][tr][td]8[/td][td=1,1,33%]2[/td][td]8[/td][/tr][tr][td=1,1,32%]a[/td][td]i[/td][td=1,1,35%]a[/td][/tr][tr][td]b[/td][td=1,1,33%]j[/td][td]b[/td][/tr][tr][td=1,1,32%]c[/td][td] [/td][td=1,1,35%]c[/td][/tr][tr][td]d[/td][td=1,1,33%] [/td][td]d[/td][/tr][tr][td=1,1,32%]e[/td][td] [/td][td=1,1,35%]e[/td][/tr][tr][td]f[/td][td=1,1,33%] [/td][td]f[/td][/tr][tr][td=1,1,32%]g[/td][td] [/td][td=1,1,35%]g[/td][/tr][tr][td]h[/td][td=1,1,33%] [/td][td]h[/td][/tr][/table]S1串长已等于最大串长
[/td][/tr][/table]算法描述如下:
Status Concat(SString &T,SString S1,SString S2){
if(S1[0]+S2[0]<=MAXSTRLEN){
[indent]T[1..S1[0]]=S1[1..S1[0]];
T[S1[0]+1..S1[0]+S2[0]]=S2[1..S2[0]];
T[0]=S1[0]+S2[0]uncut=TRUE;
[/indent]}
else if(S1[0]<MAXSTRSIZE){
[indent]T[1..S1[0]]=S1[1..S1[0]];
T[S1[0]+1..MAXSTRLEN]=S2[1..MAXSTRLEN-S1[0]];
T[0]=MAXSTRLEN;uncut=FALSE;
}
else{
[indent]T[0..MAXSTRLEN]=S1[0..MAXSTRLEN];
uncut=FALSE;
[/indent]}
[/indent]return uncut;
}
[/indent]三、堆分配存储表示
[indent]这种存储表示的特点是,仍以一组地址连续的存储单元存放串值字符序列,但它们的存储空间是在程序执行过程中动态分配而得
在C语言中,存在一个称之为堆的自由存储区,并由C语言的动态分配函数malloc()和free()来管理.利用函数malloc()为每个新产生的串分配一块实际串长所需存储空间,为处理方便,约定串长也作为存储结构的一部分
typedef struct{
char *ch;//若是非空串,则按串长分配存储区,否则ch为NULL
int length; //串长度
}HString
Status StrInsert(HString &S,int pos,HString T){
if(pox<1||pos>S.length+1) return ERROR;
if(T.length){
[indent]if(!(S.ch=(char *)realloc(S.ch,(S.length+T.length)*sizeof(char))))
[indent]exit(OVERFLOW);
[/indent]for(i=S.length-1;i>=pos-1;--i)
[indent]S.ch[i+T.length]=S.ch[i];
[/indent]S.ch[pos-1..pos+T.lenght-2]=T.ch[0..T.length-1];
S.length+=T.length;
[/indent]}
return OK;
}
[/indent]四、总结
[indent]思考两种存储表示方法的优缺点
[/indent][size=6]
[/size]
[/indent]