WEB开发网
开发学院软件开发数据结构 数据结构教程 第十五课 串的表示和实现 阅读

数据结构教程 第十五课 串的表示和实现

 2007-05-16 11:56:22 来源:WEB开发网   
核心提示:教学目的: 掌握串的几种实现方法教学重点: 定长顺序存储表示法 堆分配存储表示法教学难点: 堆分配存储表示法授课内容:一、复习串的定义串的定义 二、定长顺序存储表示类似于线性表的顺序存储结构,用一组地址连续的存储单元存储串值的字符序列.#define MAXSTRLEN 255typedef unsigned char

教学目的: 掌握串的几种实现方法

教学重点: 定长顺序存储表示法 堆分配存储表示法

教学难点: 堆分配存储表示法

授课内容:

一、复习串的定义

串的定义

二、定长顺序存储表示

类似于线性表的顺序存储结构,用一组地址连续的存储单元存储串值的字符序列.

#define MAXSTRLEN 255

typedef 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的值相等,则只要进行相应的"串值复制"操作即可,对超长部分实施"截断"操作

以下是串联接可能出现的三种情况:

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){

if(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;

}

else if(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;

}

else{

T[0..MAXSTRLEN]=S1[0..MAXSTRLEN];

uncut=FALSE;

}

return uncut;

}

三、堆分配存储表示

这种存储表示的特点是,仍以一组地址连续的存储单元存放串值字符序列,但它们的存储空间是在程序执行过程中动态分配而得

在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){

if(!(S.ch=(char *)realloc(S.ch,(S.length+T.length)*sizeof(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;

}

return OK;

}

四、总结

思考两种存储表示方法的优缺点

Tags:数据结构 教程 第十五

编辑录入:爽爽 [复制链接] [打 印]
赞助商链接