数据结构——字符串

前言

本篇开始写数据结构的第三部分——字符串，主要内容如下：

• 概念
• 串的存储结构
• 串的基本操作

关于字符串还有一个重要的知识点是KMP模式匹配算法，关于这个算法会单独拿一篇来写。

概念

串是由零个或多个字符组成的有限序列，又叫字符串。串中字符的个数称为串的长度，含有零个元素的串叫空串，空格也属于一个元素，只有空格的串称为空格串，空格串不等于空串。

在C语言中，可以用如下语句来定义一个名为str的字符串。

char str[] = "abcdef";

串通常用一个字符数组表示，数组str内存储的字符为"a","b","c","d","e","f","",其中""作为编译器识别串结束标记，不算实际字符，因此数组str的长度为7，串str的长度为6。

串中任意连续字符组成的子序列称为该串的子串，包含子串的串称为主串，某个字符在串中的序号称为这个字符的位置。

串的存储结构

1.定长顺序存储

定长顺序存储就是事先指定串的长度并分配存储空间，定义如下：

typedef struct{    char str[maxsize+1];    int length;    //字符串长度}Str;

maxsize表示串的最大长度，maxsize+1表示字符数组的长度，多出来的一个长度是用来存储标识符的。

2.变长分配存储

变长分配存储是在程序执行过程中根据需要动态分配串的长度以及空间，定义如下：

typedef struct{    char *ch;        //指向动态分配存储区首地址的字符指针    int length;     //串长度}Str;

这种存储方式在使用时需要用函数malloc()来分配一个长度为length、类型为char型的连续存储空间。用函数malloc()分配存储空间，如果成功，则返回一个指向起始地址的指针，作为串的基地址，这个地址由ch指针指向。

串的基本操作

1.赋值操作

因为串是一个数组，不可以直接进行赋值，需要对数组中的每个元素进行逐一赋值操作。

int strassign(Str& str,char* ch){    if(str.ch)        free(str.ch);    //释放    int len = 0;    char *c = ch;    while(*c)            //求串ch的长度    {        ++len;          //字符串长度+1        ++c;             //指针向后移动1    }    if(len == 0)      //如果ch串长度为0，即为空串，直接返回空串    {        str.ch = NULL;        str.length = 0;        return 1;    }    else    {        str.ch = (char*)malloc(sizeof(char)*(len+1));    //动态分配存储，如果分配成功则返回具体指针，负责返回0        if(str.ch == NULL)               //分配失败            return 0;        else        {            c = ch            for (int i = 0;i <= len;++i,++c)    //将ch最后的""一起赋值给新串作为结尾标记符                str.ch[i] = *c;                str.length = len;                return 1;        }    }}

2.取串长度操作

如果字符串数组给出了串的长度，取字符串的长度就比较简单，直接调用str.length即可，具体代码如下：

int strlength(Str str){    return str.length}

如果字符串数组没有给出串的长度，那么直接去遍历字符串中每个元素，依次将length加1，最后就是字符串长度，具体代码如下：

 int len = 0;    char *c = ch;    while(*c)            //求串ch的长度    {        ++len;          //字符串长度+1        ++c;             //指针向后移动1    }

3.串比较操作

两个字符串比较，对于等长的两个字符串依次将两个字符串中的每一个对应的数据元素去做对比，比较数据元素的ASCII码值。对于不等长的字符串，字符串较短的串比较小。

int strcompare(Str s1,Str s2){    for(int i = 0;i < s1.length && i < s2.length)        if(s1.ch[i] != s2.ch[i])            return s1.ch[i] - s2.ch[2];    return s1.length - s2.length}

4.串连接操作

串链接就是将两个字符串首尾进行链接，合并成一个新的字符串，其实具体的赋值原理就是分别将俩个串以先后顺序赋值给同一个新串。具体实现代码如下：

int concat(Str& str,Str str1,Str str2){    if(str.ch)    {        free(str.ch);    //释放原串空间        str.ch = NULL;    }    str.ch = (char*) malloc (sizeof(char)*(str1.length + str2.length + 1));    if(str.ch == NULL)        return 0;    int i = 0;    while(i < str1.length)    {        str.ch[i] = str1.ch[i];        ++i;    }    int j = 0;    while(j <= str2.length)    {        str.ch[i + j] = str2.ch[j];        ++j;    }    str.length = str1.length + str2.length;    return 1;}

5.求子串操作

求从某一位置开始，另一位置结束的串的操作称为求子串操作。现在要从字符串str中的pos位置开始，获取长度为len的子串，子串由substr返回。具体代码如下：

int substring(Str& substr,Str str,int pos,int len){    if(pos) < 0 || pos >= str.length || len < 0 || len > str.length - pos  //如果开始位置小于0或开始位置大于字符串长度或子串                                                                                                            //长度小于0或子串长度大于总字符串长度-开始位置        return 0;    if(substr.ch)    {        free(substr.ch);        substr.ch = NULL;    }    if(len) = 0    {        substr.ch = NULL;        substr.length = 0;        return 1;    }    else    {        substr.ch = (char*)malloc(sizeof(char)*len+1);        int i = pos;        int j =0;        while(i < pos + len)        {            substr.ch[j] = str.ch[]i];            ++i;            ++j;        }        substr.ch[j] = ""        substr.length = len;        return 1;    }

6.串清空操作

串清空就是将字符串中的元素全部删除，具体代码如下：

int clearstring(Str& str){    if(str.ch)    {        free(str.ch);        str.ch = NULL;    }    str.length = 0;    return 1;}

关于字符串的操作，在Python中就比较简单了，很多方法都有现成的函数，可以供你直接使用。

End.爱数据网专栏作者：张俊红作者介绍：一个数据科学路上的学习者、实践者、传播者个人公众号：俊红的数据分析之路