串

串的定义

概念

• 串是由零个或多个字符数组组成的有限序列。
• 串中字符的个数称为串的长度，含有零个元素的叫空串。
• 串是限定了元素为字符的线性表

（注：串与一般的线性表操作有很大区别，线性表主要针对表内的某个元素，而串操作主要针对子串）

代码

在C语言中，一个串可以如下定义，但仅以'0'作为结束符时需要我们遍历整个数组，时间复杂度为O(n)，这并不是我们想要的最优结果，

其他方法会在下文“串的结构体定义”部分有详细描述，这里仅举个例子

char str[] = "as123";

对C语言来讲，串主要由一个字符数组表示，上方字符串str中的字符有 'a' ,'s', '1','2','3','0'

下对'0'单独介绍

‘0’

'0'是转译字符，意思是告诉编译器，这不是字符0，而是空字符，是字符串的结束标志。

故字符数组str的长度为7，而串str的长度为6

串相关的术语

• 串中任意连续的字符组成的子序列称为该串的子串
• 包含子串的串称为主串
• 某个字符在串中的序号称为这个字符的位置
• 有一个或多个空格组成的串称为空格串

串的结构体定义

串的储存结构主要分为定长顺序储存与变长分配储存两种

定长顺序储存

用额外一个变量来存放串的长度，这样求串长时间复杂度就降为了O(1)

#define MAXSIZE 1024

//串的定长顺序储存结构
typedef struct _str
{
    char str[MAXSIZE+1];
    int length;
}Str;

变长分配储存

//串的变长储存结构
typedef struct _str_p
{
    char *ch;
    int length;
}Str_p;

串的操作

此处以变长储存为例（定长顺序储存没什么太值得好说的）

//先定义一个串的结构体
typedef struct _str_p
{
    char *ch;
    int length;
}Str_p;

//定义一个串
Str_p str;

串的初始化

bool initStr(Str_p &str)
{
    str.length = 0;
    str.ch = nullptr;
    return true;
}

串的赋值

ISO C++11 does not allow conversion from string literal to 'char *'
注意:在C++11里，指针指向的内容如果不可修改，就建议把该指针确认为const指针类型,否则会有个warning
也就是说我们这里要用 const char* ch 而非 char* ch

//参数：串， 串的内容
bool inputString(Str_p &str, const char* ch)
{
    if(str.ch) free(str.ch);

    int len = 0;
    const char *c = ch;
    while(*c)
    {
        ++len;
        //因为内存连续，所以可以对c进行自增
        ++c;
    }
  
    //若赋值为空，即该串为空串
    if(!len)
    {
        str.ch = nullptr;
        str.length = 0;
        return true;
    }
    else
    {
        //len+1是为了存放'\0'
        str.ch = (char*)malloc(sizeof(char)*(len+1));
      
        if(!str.ch) return false;
        else
        {
            c = ch;
            for(int i=0; i<len; i++,c++)
                str.ch[i] = *c;
            str.length = len;
            return true;
        }
      
    }
  
}

获取串的长度

int getStrLen(Str_p str)
{
    return str.length;
}

串的比较

//串的比较
int strCompare(Str_p s1, Str_p s2)
{
    for(int i=0; i<s1.length && i<s2.length; i++)
        if(s1.ch[i]!=s2.ch[i])
            return s1.ch[i] - s2.ch[i];
    return s1.length - s2.length;
}

合并串

//参数： 合并后的字符串， 子串1， 子串2
bool conStr(Str_p &str, Str_p s1, Str_p s2)
{
    initStr(str);
    if(str.ch)
    {
        free(str.ch);
        str.ch = nullptr;
    }
  
    str.ch =
    (char*)malloc(sizeof(char*)*(s1.length+s2.length+1));
  
    if(!str.ch) return false;
  
    //将s1的字符保存到str
    int i;
    for(i=0; i<s1.length;i++)
        str.ch[i] = s1.ch[i];
  
    //同理
    int j;
    //此处取等号是为了把'\0'放进去
    for(j=0; j<=s2.length; j++)
        str.ch[i+j] = s2.ch[j];
  
    str.length = s1.length + s2.length;
  
    return true;
}

求子串

//参数： 子串， 父串， 起始位置， 切片长度
bool subStr(Str_p &substr,Str_p str, int pos, int len)
{
    initStr(substr);
    if(pos<0||
       pos>str.length||
       len<0||
       len>str.length-pos)
        return false;
    if(substr.ch)
    {
        free(substr.ch);
        substr.ch = nullptr;
    }
  
    //所求子串为空串
    if(!len)
    {
        substr.ch = nullptr;
        substr.length = 0;
        return true;
    }
    else{
        substr.ch =
        (char*)malloc(sizeof(char)*(len+1));
        int i = pos, j = 0;
        while(i<pos+len)
        {
            substr.ch[j] = str.ch[i];
            i++;
            j++;
        }
      
        substr.ch[j] = '\0';
        substr.length = len;
      
        return true;
    }
  
}

清空串

bool clearStr(Str_p &str)
{
    if(str.ch)
    {
        free(str.ch);
        str.ch = nullptr;
    }
    str.length = 0;
    return true;
}