内容纲要

串的概念及其特性:

  • 串是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为模式串长度)

模式匹配最好情况最坏情况平均情况空间复杂度
朴素算法O(1)O((n-m+1)*m)O(n*m)O(1)
KMP算法O(n+m)O(n)O(m)
最后修改日期:2020年7月12日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。