字符串和字符串的常见存储结构

继续接去年的常见数据结构和算法总结 系列随笔记录

一、计算机里进行非数值处理的对象基本上是字符串数据，比处理浮点和整数都要复杂

string串定义：由 0 个或多个 字符 组成的 有限的 序列，通常记为：s =“a1 a2 a3 … ai …an”  ( n≥0 ，且n是有限的)。其中的引号不属于串，只是一个标记作用！

n就是串的长度，且字符串里的字符 ai 的值由 字母、数字或其他字符 组成的。

二、字符串为什么要用双引号标记

作用：避免字符串与变量名或数的常量混淆。  

    char *str = "*str";
    int x = 1111111;
    char *str1 = "1111111";

三、几个概念

空串：不含任何字符的串，长度 = 0，用符号 f  表示。也就是说空串也是字符串！

空格串：仅由一个或多个空格组成的串。 区分空串和空格串！

子串：由串中任意个连续的字符组成的子序列。空串是任意串的子串，任意串是其自身的子串。 

主串：包含子串的串。

字符的位置：字符在序列中的序号。

子串在主串中的位置：子串的首字符在主串中的位置。

    char *str = "";//空串
    char *str1 = "    ";//空格串
    char *strMain = "abcdefg";//主串
    char *strSub = "cde";//strMain的子串，子串在主串的位置是 3
    char *strSub1 = "";//空串同样是strMain的子串
    char *strSub2 = "abcdefg";//也可以看成是strMain的子串，字符串本身也是自己的子串，在主串的位置是 1

串相等：当两个串的长度相等且各个对应位置的字符都相等时才相等。

    char *s1 = "12345";
    char *s2 = "12345";
    //s1和s2相等
    char *s3 = "1 2345";
    //s1，s2和s3不等

四、串的逻辑存储结构

还是那句话，线性表是数据结构和算法的基础！很多地方都以线性表为基础去扩展！同样，串的逻辑结构和线性表很相似！

串和线性表的区别：串的数据对象，我们约定是字符集，也就是说，字符串是数据受限的！而线性表的数据对象，不一定是字符集！可以存储整数，浮点数等，都没问题。

五、串的基本操作

和线性表差别较大。 因为，线性表的基本操作大多以“单个元素”作为操作对象，比如删除一个元素，初始化一个结点，插入一个结点等，而串的基本操作通常以“串这个整体”作为操作对象。比如在串中查找某个子串、在串的某个位置上插入一个子串、删除一个子串，子串的模式匹配……

六、字符串的三种存储结构

串也是一类特殊的线性表，故其存储结构与线性表的存储结构类似，只不过组成串的结点是单个字符而已。

定长顺序存储

也称为静态存储分配的顺序串。即用一组地址连续的存储单元依次存放串中的字符序列。“定长”、“静态”的意思可简单地理解为一个确定的存储空间，它的长度是不变的。 

串长的表示方法：

1）在串的存贮区首地址显式地记录串的长度。 方便使用，一目了然，比如Pascal语言。

2）在串之后加结束标志，隐式记录串的长度，不直观，如C/C++ 使用 “