菜缤的世界 CairBin's Blog - 字符串
type: channel
link: https://blog.cairbin.top/index.php/tag/字符串/
items: 串的定义及操作

串的定义及操作
type: item
date: 2021-11-04T15:45:00+00:00
description: 串串的定义概念串是由零个或多个字符数组组成的有限序列。串中字符的个数称为串的长度，含有零个元素的叫空串。串是限定了元素为字符的线性表（注：串与一般的线性表操作有很大区别，线性表主要针对表内的某个元素，而串操作主要针对子串）代码在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…