前言

废话不多，数据结构必须学！ 每天更新一章，一篇写不完的话会分成两篇来写~

资料获取

5.4串的存储结构

5.4.1串的顺序存储结构

对于不同的高级语言，其实对串的基本操作会有不同的定义方法

在C#中，字符串操作有ToLower转小写、ToUpper转大写、IndexOf从左查找子串位置

/*T为非空串。若主串S中第pos个字符之后存在与T相等的子串，*/
 /*则返回第一个这样的子串在S中的位置，否则返回0 */
 int a Index (String S, String T, int pos )
 {
     int n,m,i;
     String sub;
     if (pos > 0)
     {
             n=StrLength (s) ;   /*得到主串S的长度*/
             m = StrLength (T) ; /*得到子串T的长度*/
             i = pos;
             while (i <= n-m+1 )
             {
                 SubString (sub,S,i,m) ;/*取主串第i个位置*/
                                         /*长度与T相等子串给sub */
                 if (StrCompare (sub,T)!= 0) /*如果两串不相等*/
                     ++i;
                 else        /*如果两串相等*/
                     return i;       /*则返回i值*/
             }
     }
     return 0;   /*若无子串与T相等，返回0 */ 
 }

我们要理解其中的原理串的顺序存储结构是用一组地址连续的存储单元来存储串中的字符序列的。按照预定义的大小，为每个定义的串变量分配一个固定长度的存储区。一般是用定长数组来定义。

既然是定长数组，就存在一个预定义的最大串长度，一般可以将实际的串长度值保存在数组的0下标位置，有的书中也会定义存储在数组的最后一个下标位置。但也有些编程语言不想这么干，觉得存个数字占个空间麻烦。它规定在串值后面加一个不计入串长度的结束标记字符，比如“\0” 来表示串值的终结，这个时候，你要想知道此时的串长度，就需要遍历计算一下才 知道了，其实这还是需要占用一个空间，何必呢。

于是对于串的顺序存储，有一些变化， 串值的存储空间可在程序执行过程中动态分配而得。比如在计算机中存在-一个自由存储区，叫做“堆”。 这个堆可由C语言的动态分配函数malloc ()和free ()来管理。

5.4.2串的链式存储结构

对于串的链式存储结构，与线性表是相似的，但由于串结构的特殊性，结构中的每个元素数据是一个字符，如果也简单的应用链表存储串值，一个结点对应一个字符，就会存在很大的空间浪费。因此，一个结点可以存放一个字符， 也可以考虑存放多个字符，最后一个结点若是未被占满时，可以用“#”或其他非串值字符补全

当然，这里一个结点存多少个字符才合适就变得很重要，这会直接影响着串处理的效率，需要根据实际情况做出选择。串的链式存储结构除了在连接串与串操作时有一定方便之外，总的来说不如顺序存储灵活，性能也不如顺序存储结构好。