专栏首页张俊红数据结构—字符串

数据结构—字符串

总第118篇

前言

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

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

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

概念

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

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

char str[] = "abcdef";

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

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

串的存储结构

1.定长顺序存储

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

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

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

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最后的"\0"一起赋值给新串作为结尾标记符
                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] = "\0"
        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中就比较简单了,很多方法都有现成的函数,可以供你直接使用。

你还可以看:

数据结构—线性表 数据结构-栈和队列

本文分享自微信公众号 - 张俊红(zhangjunhong0428)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2018-07-28

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【倒计时7天】2018教育部-腾讯公司产学合作协同育人项目申请即将截止!

    腾讯高校合作
  • 不只是软件,在线也可以免费下载百度文库了。

    不管是学生,还是职场员工,下载各种文档几乎是不可避免的,各种XXX.docx,XXX.pptx更是家常便饭,人们最常用的就是百度文库,豆丁文库,道客巴巴这些下载...

    课代表
  • SQL中GROUP BY用法示例

    GROUP BY我们可以先从字面上来理解,GROUP表示分组,BY后面写字段名,就表示根据哪个字段进行分组,如果有用Excel比较多的话,GROUP BY比较类...

    Awesome_Tang
  • ISUX Xcube智能一键生成H5

    腾讯ISUX
  • 理工男图解零维到十维空间,烧脑已过度,受不了啦!

    让我们从一个点开始,和我们几何意义上的点一样,它没有大小、没有维度。它只是被想象出来的、作为标志一个位置的点。它什么也没有,空间、时间通通不存在,这就是零维度。

    钱塘数据
  • 中国互联网协会发布:《2018中国互联网发展报告》

    在2018中国互联网大会闭幕论坛上,中国互联网协会正式发布《中国互联网发展报告2018》(以下简称《报告》)。《中国互联网发展报告》是由中国互联网协会与中国互联...

    钱塘数据
  • 知识体系解决迷茫的你

    最近在星球里群里都有小伙伴说道自己对未来的路比较迷茫,一旦闲下来就不知道自己改干啥,今天我这篇文章就是让你觉得一天给你 25 个小时你都不够用,觉得睡觉都是浪费...

    桃翁
  • 考研英语-1-导学

    英二图表作文要重视。总体而言,英语一会比英语二难点。不过就写作而言,英语二会比英语一有难度,毕竟图表作文并不好写。

    用户1335799
  • 【系统设置】CentOS 修改机器名

    ken.io
  • 复杂业务下向Mysql导入30万条数据代码优化的踩坑记录

    从毕业到现在第一次接触到超过30万条数据导入MySQL的场景(有点low),就是在顺丰公司接入我司EMM产品时需要将AD中的员工数据导入MySQL中,因此楼主负...

    haifeiWu

扫码关注云+社区

领取腾讯云代金券