数据结构第四章 串part2.ppt

* 在程序设计语言中，串只是作为输入或输出的常量出现，则只需存储此串的串值，即字符序列即可。但在多数非数值处理的程序中，串也以变量的形式出现。 4.2 串的表示和实现 一、串的定长顺序存储表示 二、串的堆分配存储表示 三、串的块链存储表示 串有三种机内表示方法： 将串中的字符顺序地存放在内存一片连续的存储单元中。 设串S=‘a1 a2 ... an’,则顺序存贮结构在内存贮器中的存贮示意图如图所示: a1 a2 a3 a n 一、串的定长顺序存储表示 串的顺序存贮结构的两种方式 非紧缩存贮格式即一个字的存贮单元存放一个字符. 紧缩存贮格式即一个字的存贮单元中放满多个字符，然后在往下一个字存贮单元存放 与非紧缩存贮格式相比，紧缩存贮格式节省了存贮空间 非紧缩存贮结构 存储单元 紧缩存贮结构 存储单元 #define MAXSTRLEN 255 // 用户可在255以内定义最大串长 typedef unsigned char Sstring [MAXSTRLEN + 1]; // 0号单元存放串的长度 按这种串的表示方法实现的串的运算时，其基本操作为 “字符序列的复制”。 串的实际长度可在这个予定义长度的范围内随意设定，超过予定义长度的串值则被舍去，称之为“截断” 。 特点: 下面以串联接和求子串为例讨论之。 1.串联接 Concat(T,S1,S2) 假设S1、S2 和T都是Sstring型的串变量，且串T是由串S1联结串S2得到的，则只要进行相应的“串值复制”操作即可，只是需按前述约定，对超长部分实施“截断”操作。 基于串S1和S2长度的不同情况，串T值的产生可能有如下三种情况： (1) S1[0]+S2[0] ≤MAXSTRLEN，得到的串T是正确的结果。 (2) S1[0] MAXSTRSIZE，而S1[0]+S2[0] MAXSTRLEN，则将串S2的一部分截断，得到的串T只包含S2的一个子串。 (3) S1[0] =MAXSTRSIZE，则得到串T并非联接结果，而和串S1相等。 算法描述如下： Status Concat(SString S1, SString S2, SString T) { // 用T返回由S1和S2联接而成的新串。若未截断, 则返回TRUE，否则FALSE。 return uncut; } // Concat 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; } if (S1[0]+S2[0] = MAXSTRLEN) {// 未截断 else if (S1[0] MAXSTRSIZE) { // 截断 else { // 截断(仅取S1) 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]; // T[0] == S1[0] == MAXSTRLEN uncut = FALSE; } 2.求子串 SubString(Sub,S,pos,len) 求子串的过程即为复制字符序列的过程，将串S中从第pos个字符开始长度为len的字符序列复制到串Sub中。显然，本操作不会有需截断的情况，但有可能产生用户给出的参数不符合操作的初始条件，当参数非法时，返回ERROR。 Status SubString (SString Sub, SString S, int pos,int len) {