数据结构 - 字符串

[TOC]

简介

串（string）是由零个或多个字符组成的有限序列，又名字符串。

上述描述是对字符串的定义，将其使用数学方法进行描述，一般记为：s = "a_1,a_2 \cdots a_n" ( n \geq 0)，其中：

  • s 是字符串的名称，用双引号括起来的是字符串的内容（值），注意双引号本身不属于字符串内容。
  • a_i (1 \leq i \leq n) 表示字符串中第 i 个位置的字符。
  • n 表示字符串s的长度，当 n = 0 时，表示字符串内容为空，即 “空串”，可以直接使用两个双引号""表示。

从上述字符串的定义中，还可以看到以下几方面内容：

  • 零个或多个字符组成：说明字符串的内部元素类型为字符。
    注：关于字符的更加详细释义，请参考 附录。
  • 有限：说明字符串的内容长度是有一定限制的，小于一个最大范围，但是在该范围内，实际的长度是不确定的。
  • 序列：说明字符串中的相邻字符存在前驱和后继的关系。

一些名词释义

  • 空串：表示字符串没有内容，可用两个双引号""进行表示。

  • 空格串：表示只包含一个或多个空格的字符串。注意其与 空串 的区别，空格串 是有内容的，其内容为一个或多个空格。空串 没有内容，且其长度为0。

  • 主串：具备全部内容的字符串。

  • 子串：字符串中任意个数的连续字符组成的子串称为该串的子串。

  • 串的比较：两个串的大小比较方法是依次比较相同位置上的字符码值，首次不同时则比较完成。

字符串的存储结构

字符串的逻辑结构和线性表很相似，因此这里可以借助线性表的典型结构，即数组和链表来实现字符串结构：

  • 串的顺序存储结构：即基于数组实现字符串结构。首先分配一个足够大的数组作为字符串的底层数据结构，然后依次将字符存储到数组对应位置上，完成存储。

  • 串的链式存储结构：即基于链表实现字符串结构。由于字符串的数据元素为字符，如果采用链表作为字符串的底层数据结构，则需要为每一个字符创建一个链表结点，链表结点最少还应当具备一个后继指针域，如果要求具备往前回溯功能，则还应当创建一个前驱指针域，相对来说，基于链表的字符串在空间上存在资源使用过大问题。

当然，可以通过其他方式提高串的链式存储结构效率，但是总体来说，使用数组作为字符串的底层结构更加简单直接，性能上也更加优越。
因此，本文主要介绍基于数组的方式实现字符串数据结构。

字符串的基本操作

字符串的基本操作包含如下内容：

// 头文件
#ifndef __STRING_H__
#define __STRING_H__

#include <iostream>

#define DEFAULT_LENGTH 100                 // 底层数组默认长度

class String {
private:
    char* pstr = nullptr;                  // 字符串指针
    std::size_t capacity = DEFAULT_LENGTH; // 底层数组最大容量
    std::size_t length = 0;                // 字符串长度
private:
    void init();
    void checkIfNeedEnlarge();             // 长度超过默认长度，则动态扩展
public:
    String();                              // 空串
    String(char c);                        // 一个字符串
    String(const char* str);               // 字符串指针
    String(const String& str);             // 字符串引用
    ~String(); // 析构函数

    // 获取字符串长度
    size_t size() const;
    // 清空
    void clear();
    // 判空
    bool isEmpty() const;

    // 子串开头
    bool startsWith(const char* str) const;
    bool startsWith(const String& str) const;
    // 子串结尾
    bool endsWith(const char* str) const;
    bool endsWith(const String& str) const;

    // 删除字符串前后空白符
    String trim();

    // 获取索引 i 的字符
    char& operator[](std::size_t i);

    // 比较
    bool operator==(const char* str) const;
    bool operator==(const String& str) const;

    bool operator!=(const String& str) const;
    bool operator!=(const char* str) const;

    // 字符串拼接 concat
    String& operator+=(const String& str);
    String& operator+=(const char* str);
    String& operator+=(const char c);
    String operator+(const String& str) const;
    String operator+(const char* str) const;
    String operator+(const char c) const;

    // 支持输出操作
public:
    friend std::ostream& operator<<(std::ostream& os, const String& str);
};

#endif

各个操作对应的具体实现如下所示：

#include "String.h"

void String::init() {
    // 动态开辟一块内存，并初始化为 0
    this->pstr = new char[DEFAULT_LENGTH] {0};
    if (this->pstr == nullptr) {
        throw "No extra memory to create String object!";
    }
}

void String::checkIfNeedEnlarge() {
    if (this->length >= this->capacity) {
        // 开启一块更大的内存
        char* p = new char[this->capacity += DEFAULT_LENGTH];
        // 复制源字符串数组
        std::memcpy(p, this->pstr, this->length);
        // 释放源数组内存
        free(this->pstr);
        // 指向新字符串数组内存空间
        this->pstr = p;
    }
}
 
String::String() {
    init();
}

String::String(char c) {
    init();
    (*this) += c;
}

String::String(const char* str) {
    init();
    (*this) += str;
}

String::String(const String& str) {
    init();
    (*this) += str;
}

String::~String() {
    if (this->pstr) {
        delete[] this->pstr;
    }
}

size_t String::size() const {
    return this->length;
}

void String::clear() {
    std::memset(this->pstr, 0, this->length);
    this->length = 0;
}

bool String::isEmpty() const {
    return this->length == 0;
}

bool String::startsWith(const char* str) const {
    bool ret = (str != nullptr);
    do {
        // str 为空
        if (!ret) {
            ret = false;
            break;
        }
        // 子串长度大于主串，直接返回 false
        size_t len = strlen(str);
        if (len > this->length) {
            ret = false;
            break;
        }
        ret = true;
        for (size_t i = 0; i < len; ++i) {
            if (str[i] != this->pstr[i]) {
                ret = false;
                break;
            }
        }
    } while (false);
    return ret;
}

bool String::startsWith(const String& str) const {
    return this->startsWith(str.pstr);
}

bool String::endsWith(const char* str) const {
    bool ret = (str != nullptr);
    do {
        if (!ret) {
            ret = false;
            break;
        }
        size_t len = strlen(str);
        if (len > this->length) {
            ret = false;
            break;
        }
        ret = true;
        for (size_t i = 0; i < len; ++i) {
            if (str[len - 1 - i] != this->pstr[this->length - 1 - i]) {
                ret = false;
                break;
            }
        }
    } while (false);
    return ret;
}

bool String::endsWith(const String& str) const {
    return this->endsWith(str.pstr);
}

String String::trim() {
    size_t begin = 0;
    size_t end = this->length - 1;

    while (this->pstr[begin] == ' ') {
        ++begin;
    }
    while (this->pstr[end] == ' ') {
        --end;
    }

    String trimStr;
    while (begin <= end) {
        trimStr += this->pstr[begin++];
    }
    return trimStr;
}


char& String::operator[](std::size_t i) {
    return this->pstr[i];
}

bool String::operator==(const char* str) const {
    size_t len = strlen(str);
    if (this->length != len) {
        return false;
    }
    for (size_t i = 0; i < len; ++i) {
        if (str[i] != this->pstr[i]) {
            return false;
        }
    }
    return true;
}

bool String::operator==(const String& str) const {
    if (this->length != str.size()) {
        return false;
    }
    for (size_t i = 0; i < this->length; ++i) {
        if (str.pstr[i] != this->pstr[i]) {
            return false;
        }
    }
    return true;
}

bool String::operator!=(const String& str) const {
    return !(*this == str);
}
bool String::operator!=(const char* str) const {
    return !(*this == str);
}

String& String::operator+=(const String& str) {
    size_t len = str.size();
    // 先增加长度
    this->length += len;
    // 在检查
    this->checkIfNeedEnlarge();
    // 最后复制
    for (size_t i = 0; i < len; ++i) {
        this->pstr[this->length - len + i] = str.pstr[i];
    }
    return *this;
}
String& String::operator+=(const char* str) {
    size_t len = strlen(str);
    for (size_t i = 0, len = strlen(str); i < len; ++i) {
        (*this) += str[i];
    }
    return *this;
}

String& String::operator+=(const char c) {
    // 先检查边界
    this->checkIfNeedEnlarge();
    this->pstr[this->length++] = c;
    return *this;
}

String String::operator+(const String& str) const {
    String newStr(*this);
    return newStr += str;
}

String String::operator+(const char* str) const {
    String newStr(*this);
    return newStr += str;
}

String String::operator+(const char c) const {
    String newStr(*this);
    return newStr += c;
}

std::ostream& operator<<(std::ostream& os, const String& str) {
    os << str.pstr;
    return os;
}

注：以上实现更多的在于展现思路，具体代码未经严格测试，可能存在错误，请知悉。

附录

  • 字符：百度百科对字符的定义如下

    字符指类字形单位或符号，包括字母、数字、运算符号、标点符号和其他符号，以及一些功能性符号。字符是电子计算机或无线电通信中字母、数字、符号的统称，其是数据结构中最小的数据存取单位...

    可以简单将字符视作为一种符号，但是这里就存在一种问题，因为计算机只能处理0、1这样的数值类型数据，所以对于字符这种符号类型数据，计算机不能直接进行处理，因此，这里存在一个转换/映射过程。

    这个映射过程就叫 编码，比如，当计算机采用 ASCII 编码时，大写字符A就会被映射为数值65，而进行打印等操作的时候，计算机会通过查询 ASCII 编码表，就可以将65转换为A进行输出，这样就完成了字符类型的输入输出操作。

    但是，ASCII 码采用 7 位二进制数表示一个字符，因此它最多能表示 128 个字符，这样有一些特殊符号就无法进行表示，后来就采用 8 位二进制数表示一个字符，称为扩展 ASCII 码，它最多能够表示 256 个字符。扩展 ASCII 码对于以英语为母语的国家已经足够使用了，但是对于亚洲等国家，扩展 ASCII 码还远远无法满足这些国家的文字映射。

    最初的一段时间，各个国家为了能让计算机支持显示自己的文字符号，就自定义了一套满足自己国家需求的编码表，比如中国制定的GB2312编码，就可以编码简体中文字符，比如日本的日文编码表Shift_JIS，比如韩国的韩文编码表Euc-kr...

    这种每个国家都自定义一套编码表存在的问题就是编码冲突，比如当不同国家相互通信的时候，就会由于解码方式不同导致乱码产生。因此，国际间需要一套标准编码表，以支持所有国家的文字符号。而这套编码表就是 Unicode。

    Unicode 本身是一种规定，它规定了每个字符对应的数字编码（即码值），但是没有规定这个码值如何存储（简而言之，Unicode 是一种字符集）。比如，对于字符A，Unicode 只规定了它对应的数字编码为65，但是是使用 1 字节进行存储，还是使用 2 字节进行存储，由不同的编码形式决定。Unicode 的编码形式一般称为 UTF-* 编码，常见的有 UTF-8、UTF-16 和 UTF-32。这里需要注意一下，早期的 Unicode 采用两字节编码方案，该方案称为 "Unicode"，后来又改名为 UCS-2，但是后来发现 16 位编码无法囊括所有字符，然后引入了一种采用四字节编码的 UCS-4 方案，但是该编码方案太浪费空间了，最终为了平衡 UCS-2 和 UCS-4 两套编码之间的僵局，采用了新的编码方案 UTF-16。所以 UTF-16 其实是一种变长编码，每个字符编码为 16 位或者 32 位，对于码值在65535之内的字符，采用两字节编码，超出的字符则采用四字节编码。

    Unicode 虽然统一了编码字符集，解决了多语言乱码问题，但是它本身在空间利用率上（早期 Unicode 使用两字节方案），稍显不足，比如对于字符A，使用 ASCII 码编码的话，其二进制为01000001，而采用 Unicode 编码，则为00000000 01000001，可以看到，Unicode 对于字符A的编码，其实就是在 ASCII 编码的前面补0，数值完全一样，但是 Unicode 比 ASCII 编码多占用了一倍的存储空间，存在资源浪费问题，并且对于文本的存储与传输会带来较大的性能损耗。同时，除了在空间利用率效率低之外，Unicode 还存在无法识别问题，因为虽然大部分编码采用两个字节，但是有些偏僻字符会采用三字节或者四字节...计算机无法区分当前是两字节编码字符还是三字节编码字符...

    因此，为了解决以上问题，又出现了 UTF-8 编码，它是对 Unicode 的一种优化，将 Unicode 编码转化为可变长编码，即 UTF-8 编码对于一个 Unicode 字符，会根据其数字编码大小编码成 1~6 个字节，常用的英文字母被编码成 1 个字节，汉字通常使用 3 个字节，其他比较偏僻的字符才会被编码为 4~6 个字节，这样，就可以节省空间。同时，UTF-8 会给每个 Unicode 字符编码进行标记，使得计算机通过该标记就知道当前 Unicode 字符占据的字节数，增加容错性。

    综上所述，Unicode 是一种包含了全世界所有字符的编码集，而 UTF-* 是对 Unicode 的具体实现，其中，UTF-8 是当前使用最多的 Unicode 实现。
    在计算机内存中，统一使用 Unicode 编码，当需要保存到磁盘或者进行传输的时候，就转换为 UTF-8 编码。比如，对于以 UTF-8 保存的文本文件，程序进行读取时，指定编码格式为 UTF-8，这样就能正确识别文本字符对应的字节数并将其转换为相应的 Unicode 码值，存储到内存中。当保存数据时，程序将内存中的字符码值转换为 UTF-8 的编码格式，即将一个数值以 UTF-8 的编码格式转换为另一个数值（二进制表示），存储到文本文件中即可。

参考

最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 194,524评论 5赞 460
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 81,869评论 2赞 371
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 141,813评论 0赞 320
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 52,210评论 1赞 263
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 61,085评论 4赞 355
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 46,117评论 1赞 272
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 36,533评论 3赞 381
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 35,219评论 0赞 253
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 39,487评论 1赞 290
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 34,582评论 2赞 309
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 36,362评论 1赞 326
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 32,218评论 3赞 312
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 37,589评论 3赞 299
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 28,899评论 0赞 17
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 30,176评论 1赞 250
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 41,503评论 2赞 341
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 40,707评论 2赞 335