数据结构-4.3.串的存储结构

一.串的顺序存储：

1.静态数组会由系统自动回收；动态数组需要手动回收；

2.优点：随机存取，可以立即找到所需的字符；缺点：插入和删除较麻烦；

3.串的顺序存储方案：

对于方案二：如果ch[0]存储字符串长度，会导致字符串长度限制在0到255，因为ch[0]位置是一个字符型，占1B即8bit；

对于方案三：额外设置一个变量记录长度，从头开始遍历，每找到一个字符，长度加一，当到\0时，停止遍历，得出字

符串长度(如果经常要用到字符串长度的话，方案三的效率会低很多)；

对于方案四：ch[0]不存任何内容，从ch[1]开始存，使得字符的位序和数组下标相同，在最后一个位置记录字符串长度

Length;

二.串的链式存储：

1.存字符的每个结点如果只存1个字符(1个字符占1B即有效内容占1B)，会导致存储密度低，因为指向下一个结点的指针

占了4B，该指针在实际开发中没什么用，因此导致存储密度低->为了解决这一问题，可以在结点中定义字符数组，字

符数组长度定义的大一些，就会使得一个结点存的字符变多，有效内容也就相对指针而言变多了，最终存储密度提高；

2.如果在最后一个结点中存不满，可以用特殊的字符如#或者\0填充进去；

3.串的链式存储的优点：增和删较方便；缺点：不具备随机存取的特性。

三.基本操作的实现：

注：用方案四来顺序存储串，字符下标从1开始，与位序一致

1.求字串：

pos+len-1代表从第pos个字符起长度为len的子串，因为长度为len的子串实际用一个len就可以表示，但这时需要一个pos来表示它的位置，为了结果仍为len，就需要减1(相当于减去pos占的那一个)即pos+len-1，子串的长度最大为主串的长度，因此pos+len-1必须不大于串的长度；

从第pos个字符起长度为len的子串中第一个字符的索引为pos，最后一个字符的索引为pos+len-1，因为从第pos个字符起，需要长度为len的子串就pos+len，但实际pos也占了一个位置，此时长度就是len+1，为了使得结果是长度为len，就需要减一即pos+len-1;

2.比较两个串的大小：

3.定位要找的子串在主串中的位置：

如果在主串中无法找到要找的子串，则返回0，因为定位操作的函数的返回值代表要找的子串的第一个字符在主串中的位

置，主串中0不存任何数据，返回0相当于返回一个不存在的位置

定位操作的思路：可以从主串中依次取出与要找的子串长度相同的子串，再与要找的子串比较，此时取主串的子串是这样

的：第一次从主串的第一个位置开始取，第二次从主串的第二个位置开始取，以此类推；

注：1.StrLength是求主串长度的函数。

2.以上述图片为例，n是主串S的长度，m是要找的子串T的长度，主串S的长度为7，要找的子串T的长度为3，按照上

述方法依次找到主串S中第5个位置的字符即可，因为此时再往后子串T的长度即3就已经到了S的最后一个位置，就无

需再往后找了，因此循环到n-m+1就行了，思路：可以逆向来推导，由于下标从1开始，因此S中最后一个字符在第n

个位置上，n-m似乎是可以停止循环的位置(主串S的长度减去要找的子串T的长度)，但实际上这只是个差，做差后实

际是停止循环的前一个位置上，因此要加一，所以停止循环的位置为n-m+1，以上述图为例:n=7,m=3,在主串S中的第

5个位置就可以停止循环即7-3+1也就是n-m+1。

四.总结：