1、串的定义
串是由零个或者多个字符组成的有限序列。串中字符的个数称为串的长度,含有零个元素的串叫空串。在C语言中,可以用以下语句定义一个名为str的串。
char str[]="abcdef";
说明:串通常用一个字符数组来表示。从这个角度来讲,数组str内存储的字符为’a’、‘b’、‘c’、‘d’、‘e’、‘f’、‘\0’,其中’\0’作为编译器识别串结束的标记。而串内字符为’a’、‘b’、‘c’、‘d’、‘e’、‘f’。所以数组str的长度为7,而串str的长度为6。
串中任意连续的字符组成的子序列称为该串的子串,包含子串的串称为主串,某个字符在串中的序号称为这个字符的位置。通常用子串第一个字符的位置作为子串在主串中的位置。
空格也是串字符集合的一个元素,由一个或者多个空格组成的串称为空格串(注意,空格串不是空串)。
串的逻辑结构和线性表类似,串是限定了元素为字符的线性表。从操作集上讲,串与线性表有很大的区别,线性表的操作主要针对表内的某一个元素,而串操作主要针对串内的一个子串。
2、串的存储结构
(1)串的定长顺序存储
一般不采取char str[]="abcdef";
的方式定义并初始化一个串,原因是在以’\0’作为串结束的标记的串,在求串长的时候需要扫描整个串,时间复杂度为O(n);额外定义一个变量专门来存储串的长度,求串长就变成了时间复杂度为O(1)。
定长顺序存储表示结构体定义如下:
typedef struct{
char str[maxSize+l];//maxSize 为已经定义的常量,表示串的最大长度;str 数组长度定义为maxSize+1,是因为多出一个'\0'作为结束标记
int length;//存储串的长度
}Str;
(2)串的变长分配存储
变长分配存储表示(又叫动态分配存储表示)方法的特点是,在程序执行过程中可以根据需要动态分配。
其结构体定义如下:
typedef struct {
char *ch;//指向动态分配存储区首地的字符指针
int length;//存储串的长度
}Str;
串的变长分配存储方式在使用时,需要用函数malloc( )来分配一个长度为length、类型为char型的连续存储空间,分配的空间可以用函数free( )释放掉。用函数malloc( )分配存储空间如果成功,则返回一个指向起始地址的指针,作为串的基地址,这个地址由ch指针来指向;如果分配失败,则返回NULL。
对比两种存储结构的分配方法可以看出,变长分配存储表示方法有顺序存储结构的特点,操作中串长可根据需要来设定,更加灵活,因此在串处理的应用程序中更为常用。
3、串的基本操作
(1)赋值操作
与普通变量赋值操作不同,串的赋值操作不能直接用“=”来实现。因为串是一个数组,如果将一个数组的值赋给另一个数组,则直接用“=”是不可行的,必须对数组中的每个元素进行逐一赋值操作。
串赋值操作函数strassign( )具体实现的代码如下所示,其功能是将一个常量字符串赋值给 str,赋值操作成功返回1,否则返回0。
int strassign(Str &str,char *ch){
if(str.ch){
free(str.ch);//释放原串空间
int len=0;
char *c=ch;
while(*c)//求ch串的长度
{
++len;
++C;
}
if(len==0)//如果ch为空串,则直接返回空串
{
str.ch=NUL;
str.length=0;
return 1;
}
else{
str.ch=(char*)malloc(sizeof(char)/'*'(len+1));//此处*两边的引号需要去掉理解,加引号是为了避免代码格式乱
//取1en+1是为了多分配一个空间存放`“\0”`字符
if(str.ch==NULL)
return 0;
else{
c=ch;
for(int i=0;i<=len;++i,++c)
str.ch[i]=*c;
/*注意:循环条件中之所以用“<=”,是为了将ch最后的’\0’复制到新串中作为结束标记*/
str.length=len;
return 1;
}
}
}
函数strassign)使用时格式如下:
strassign(str,"cur input");
此句执行后,str.ch的值为“cur input”,str.len的值为9。
(2)取串长度操作
在使用变长分配存储表示的情况下,取串长度的操作就变得极为简单,考试中直接使用str.length语句即可。统一成函数的形式,代码如下:
如果在没有给出串长度信息的情况下,求串长度的操作可以借鉴函数strassign( )中的求输入串长度部分的代码来实现。
(3)串比较操作
串的比较操作是串排序应用中的核心操作。例如,在单词的字典排序中,需要通过串比较操作来确定一个单词在字典中的位置,规则如下:设两串A和B中的待比较字符分别为a和b,如果a的ASCII码小于b的ASCII码,则返回A小于B标记;如果a的ASCII码大于b的ASCII码,则返回A大于B标记;如果a的ASCII码等于b的ASCII码,则按照之前的规则继续比较两串中的下一对字符。经过上述步骤,在没有比较出A和B大小的情况下,先结束的串为较小串,两串同时结束则返回两串相等标记。
串比较代码如下:
(4)串连接操作
将两个串首尾相接,合并成一个字符串的操作称为串连接操作。串连接操作的实现代码如下:
(5)求子串操作
求从给定串中某一位置开始到某一位置结束的串的操作称为求子串操作(规定开始位置总在结束位置前边),如下面的代码实现了求str串中从pos位置开始,长度为len的子串,子串由substr返回给用户。
(6)串清空操作
串清空操作的实现代码如下: