Teenits 2008-5-15 23:36
数据结构教程 第十五课 串的表示和实现
教学目的： 掌握串的几种实现方法
教学重点： 定长顺序存储表示法 堆分配存储表示法
教学难点： 堆分配存储表示法
授课内容：
一、复习串的定义
串的定义
二、定长顺序存储表示
类似于线性表的顺序存储结构,用一组地址连续的存储单元存储串值的字符序列.
#define MAXSTRLEN 255
typedef unsigned char SString[MAXSTRLEN+1] //0号单元存放串长
串的实际长度可在这予定义长度的范围内随意,超过予定义长度的串值则被舍去
串长可用下标为0的数组元素存储,也可在串值后设特殊标记
[table=75%] [tr] [td]a[0][/td] [td]a[1][/td] [td]a[2][/td] [td]a[3][/td] [td]a[4][/td] [td]a[5][/td] [td]...[/td] [td]a[n][/td] [/tr] [/table][table=75%] [tr] [td=1,1,13%]3[/td] [td]a[/td] [td=1,1,13%]b[/td] [td]c[/td] [td=1,1,13%] [/td] [td] [/td] [td=1,1,10%] [/td] [td=1,1,13%]pascal[/td] [/tr] [/table][table=75%] [tr] [td]a[/td] [td=1,1,13%]b[/td] [td]c[/td] [td=1,1,13%]\0[/td] [td] [/td] [td=1,1,12%] [/td] [td] [/td] [td=1,1,13%]c[/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]这种存储表示的特点是,仍以一组地址连续的存储单元存放串值字符序列,但它们的存储空间是在程序执行过程中动态分配而得
在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]