本课主题: 串
表示和实现教学目
: 掌握串几种实现思路方法教学重点: 定长顺序存储表示法 堆分配存储表示法
教学难点: 堆分配存储表示法
授课内容:
、复习串定义串
定义 2、定长顺序存储表示
类似于线性表
顺序存储结构,用组地址连续存储单元存储串值
序列.#
MAXSTRLEN 255typedef unsigned char SString[MAXSTRLEN+1] //0号单元存放串长
串
实际长度可在这予定义长度范围内随意,超过予定义长度串值则被舍去串长可用下标为0
元素存储,也可在串值后设特殊标记a[0]
a[1]
a[2]
a[3]
a[4]
a[5]
...
a[n]
3
a
b
c
pascal
a
b
c
\\0
c
1串联接
实现Concat(&T,S1,S2)假设S1,S2和T都是SString型
串变量,且串T是由串S1联结串S2得到,即串T值前段和串S1值相等,串T值后段和串S2值相等,则只要进行相应"串值复制"操作即可,对超长部分实施"截断"操作以下是串联接可能出现
3种情况:S1
S2
T
4
2
6
a
d
a
b
e
b
c
c
d
d
e
f
S1,S2串长和小于最大值
S1
S2
T
6
6
8
a
g
a
b
h
b
c
i
c
d
j
d
e
k
e
f
l
f
g
h
S1,S2串长和超过最大串长
S1
S2
T
8
2
8
a
i
a
b
j
b
c
c
d
d
e
e
f
f
g
g
h
h
S1串长已等于最大串长
算法描述如下:
Status Concat(SString &T,SString S1,SString S2){
(S1[0]+S2[0]<=MAXSTRLEN){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;
}
(S1[0]<MAXSTRSIZE){T[1..S1[0]]=S1[1..S1[0]];
T[S1[0]+1..MAXSTRLEN]=S2[1..MAXSTRLEN-S1[0]];
T[0]=MAXSTRLEN;uncut=FALSE;
}
{T[0..MAXSTRLEN]=S1[0..MAXSTRLEN];
uncut=FALSE;
}
uncut;}
3、堆分配存储表示
这种存储表示
特点是,仍以组地址连续存储单元存放串值序列,但它们存储空间是在
执行过程中动态分配而得在C语言中,存在
个称的为堆自由存储区,并由C语言动态分配
malloc
和free来管理.利用malloc为每个新产生串分配块实际串长所需存储空间,为处理方便,约定串长也作为存储结构部分typedef struct{
char *ch;//若是非空串,则按串长分配存储区,否则ch为NULL
length; //串长度}HString
Status StrInsert(HString &S,
pos,HString T){(pox<1||pos>S.length+1) ERROR;(T.length){(!(S.ch=(char *)realloc(S.ch,(S.length+T.length)*
(char))))exit(OVERFLOW);
for(i=S.length-1;i>=pos-1;--i)
S.ch[i+T.length]=S.ch[i];
S.ch[pos-1..pos+T.lenght-2]=T.ch[0..T.length-1];
S.length
T.length;}
OK;}
4、整理总结
研究两种存储表示思路方法
优缺点
最新评论