《数据结构第四章 串part2.》由会员分享,可在线阅读,更多相关《数据结构第四章 串part2.(26页珍藏版)》请在金锄头文库上搜索。
1、 在程序设计语言中,串只是作 为输入或输出的常量出现,则只需 存储此串的串值,即字符序列即可 。但在多数非数值处理的程序中, 串也以变量的形式出现。 4.2 串的表示和实现 一、串的定长顺序存储表示 二、串的堆分配存储表示 三、串的块链存储表示 串有三种机内表示方法: 将串中的字符顺序地存 放在内存一片连续的存储单 元中。 设串S=a1 a2 . an,则顺序存贮结构在内 存贮器中的存贮示意图如图 所示: a1 a2 a3 a n 一、串的定长顺序存储表示 串的顺序存贮结构的两种方式 非紧缩存贮格式 即一个字的存贮单元存放一个字符. 紧缩存贮格式 即一个字的存贮单元中放满多个字符, 然后在往下
2、一个字存贮单元存放 与非紧缩存贮格式相比,紧缩存贮格式 节省了存贮空间 非紧缩存贮结构 存储单元 紧缩存贮结构 存储单元 #define MAXSTRLEN 255 / 用户可在255以内定义最大串长 typedef unsigned char Sstring MAXSTRLEN + 1; / 0号单元存放串的长度 按这种串的表示方法实现的串的运算 时,其基本操作为 “字符序列的复制”。 串的实际长度可在这个予定义长度的 范围内随意设定,超过予定义长度的串 值则被舍去,称之为“截断” 。 特点: 下面以串联接和求子串为例讨论之。 1.串联接 Concat( / Concat T1.S10 =
3、S11.S10; TS10+1.S10+S20 = S21.S20; T0 = S10+S20; uncut = TRUE; if (S10+S20 = MAXSTRLEN) / 未截断 else if (S10 =pos-1;i-) /为插入T而腾出位置 S.chi+T.length=S.chi; S.chpos-1.pos+T.length-2=T.ch0.T.length-1; /插入T S.length+=T.length; return OK; / SubInsert 以上两种存储表示通常为高级程序设计语 言所采用。由于堆分配存储结构的串既有顺序 存储结构的特点,处理方便,操作中对串
4、长又 没有任何限制,更显灵活,因此,在串处理的 应用程序中也常被选用。 以下所示为只含最小操作子集的Hstring串 类型的模块说明: typedef struct char *ch; / 若是非空串,则按串长分配存储区, / 否则ch为NULL int length; / 串长度 HString; 串的堆分配存储表示: 基本操作的函数原型说明: Satus StrAssign( Hstring /生成一个其值等于串常量chars的串T int StrLength(Hstring S); /返回S的元素个数,称为串的长度 int Strcompare(Hstring S, Hstring T); /若ST,则返回值0; /若S=T,则返回值=0; /若S0; /若S=T,则返回值=0; /若ST,则返回值0; for (i=0;iS.length +i) if (S.chi!=T.chi) return S.chi-T.chi; return S.length-T.length; / Strcompare Satus ClearString( Hstring /将S清为空串 if (S.ch) free(S.ch); S.ch=NULL; S.length =0; return OK; / ClearString