脚本宝典收集整理的这篇文章主要介绍了数据结构——串的定义及操作,脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。
(注:串与一般的线性表操作有很大区别,线性表主要针对表内的某个元素,而串操作主要针对子串)
在C语言中,一个串可以如下定义,但仅以''作为结束符时需要我们遍历整个数组,时间复杂度为O(n),这并不是我们想要的最优结果,
其他方法会在下文“串的结构体定义”部分有详细描述,这里仅举个例子
char str[] = "as123";
对C语言来讲,串主要由一个字符数组表示,上方字符串str中的字符有 'a' ,'s', '1','2','3',''
下对''单独介绍
''是转译字符,意思是告诉编译器,这不是字符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是为了存放''
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;
//此处取等号是为了把''放进去
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] = '';
substr.length = len;
return true;
}
}
bool clearStr(Str_p &str)
{
if(str.ch)
{
free(str.ch);
str.ch = nullptr;
}
str.length = 0;
return true;
}
以上是脚本宝典为你收集整理的数据结构——串的定义及操作全部内容,希望文章能够帮你解决数据结构——串的定义及操作所遇到的问题。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。