串

串

串的概念及其特性：

• 串是n(>= 0)个字符的有限序列，记作：S = c1c2c3…cn。S是串名字， c1c2c3…cn 是串值，ci是串中字符，n是串的长度，n=0是空串。其中的空串与空白串不同，" "长度为3的空白串，""长度为0的空串。
• 串中任意个连续字符组成的子序列称为该串的子串，包含子串的串相应地称为主串。
• 通常将子串在主串中首次出现时，该子串首字符对应的主串中的序号，定义为子串在主串中的位置。
• 空串是任意串的子串，任意串是其自身的子串。
• 通常在程序中使用的串可分为两种：串变量和串常量。

C语言中字符串操作：

• 字符串初始化char strn
• 单个字符串的输入函数gets(str)
• 字符串输出函数puts(str)
• 字符串求长度函数strlen(str)(不包括\0与分界符)
• 字符串连接函数strcat (str1, str2)
• 字符串比较函数strcmp (str1, str2)从头开始逐个比较其ASCII码

自定义字符串数据类型：定长顺序存储表示，堆分配存储表示，块链存储表示。

顺序串：使用静态分配的字符数组存储字符串中的字符序列。字符数组的长度预先用MAXSTRLEN 指定，一旦空间存满不能扩充。

堆式串：字符数组的存储空间是通过malloc( )函数动态分配的。串的最大空间数MAXSTRLEN 和串中实际字符个数length保存在串的定义中。可以根据需要，随时改变字符数组的大小。

堆式串的运算

• 初始化空串算法initString (Hstring &S)
• 提取子串算法subString ( HString& s, int pos, int len )
• 串的连接算法concat ( HString &s, HString &t )

代码实现：

#include <cstdio>
#include <cstdlib>
#include <cstring>

#define MAXSTRLEN 256
typedef struct {
    char* ch; //串的存储数组
    int maxSize; //串数组的最大长度
    int length; //串的当前长度
} HString;

void initString(HString& s)
{
    s.ch = (char*)malloc(MAXSTRLEN * sizeof(char));
    if (s.ch == NULL) exit(1); //判断分配成功与否
    s.ch[0] = '\0'; //置空串
    s.maxSize = MAXSTRLEN; //置串的最大字符数
    s.length = 0; //实际字符数置0
}

HString subString(HString& s, int pos, int len)
{
    HString t;//创建子串
    t.ch = (char*)malloc(MAXSTRLEN * sizeof(char));
    t.maxSize = MAXSTRLEN;
    if (pos < 0 || len < 0 || pos + len - 1 >= s.maxSize){//参数错误返回空串
        t.length = 0;
        t.ch[0] = '\0';
    }else{
        if (pos + len - 1 >= s.length)
            len = s.length - pos;
        for (int i = 0, j = pos; i < len; i++, j++)
            t.ch[i] = s.ch[j]; //复制子串的字符
        t.length = len; t.ch[len] = '\0';
    }
    return t; //返回复制的子串
}

void concat(HString& s, HString& t)
{
    int i;
    if (s.length + t.length <= s.maxSize) {//s可以容纳
        for (i = 0; i < t.length; i++){
            s.ch[s.length++] = t.ch[i];
        }
        s.length += t.length;
        s.ch[s.length] = '\0';
    }
    else {//存储空间不足
        char* str = s.ch;
        s.maxSize = s.length + t.length;
        s.ch = (char*)malloc(sizeof(char) * s.maxSize);
        strcpy(s.ch, str);//复制原来串的数据
        concat(s, t);//递归
        free(str);
    }
}

块链串：使用单链表作为字符串的存储表示。链表的每个结点可以存储1 个字符，称其“块的大小”为1，也可以存储n 个字符，称其“块的大小”为n。存储密度=串值所占的存储位/实际分配的存储位;显然，存储密度越高，存储利用率越高。块链存储表示一般带头结点，设置头、尾指针。

串的模式匹配：

• 简单算法（朴素算法、BF算法）O(n*m)
• 首尾匹配算法O(n*m)
• KMP算法O(n)

时间复杂度分析：(n为主串长度，m为模式串长度)