《数据结构第四章 串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
