数据结构（12.1）串结构的定义

柔情只为你懂 2023-06-24 12:29 10阅读 0赞

### 数据结构（12.1）串结构的定义 ###

*   *   *  前言
         *  串的定义
         *  有关概念
         *  串的存储结构
         *   *  顺序存储
             *   *  定长顺序表示
                 *  堆分配表示
                 *  顺序存储中串结构的设计
             *  链式存储

### 前言 ###

串是一种比较特殊的数据结构，它是计算机上非数值处理的主要对象。

事实上在C语言中，是没有“字符串”这个变量类型的，虽然可以通过字符指针 char \*p 这样来记录一个字符串，p本质上仍是一个字符指针，保存的是一个字符的地址。因此，C语言中的保存一个字符串，只是保存它首个字符的地址。但是到了诸如Java这样的语言里，提供了一种String类，可以直接用String s 来记录字符串，String和int、char一样是一种数据类型（只不过不是基本的数据类型，而是属于引用类型）。并且Java提供了很多操作函数，可以直接实现对字符串的相关操作。当然，C语言中虽然没有明确的字符串类型，但是同样存在字符串操作函数。

### 串的定义 ###

*  定义：串（或字符串）是由零个或多个字符组成的有限序列，一般记为：s = ‘a1a2…an’（n>=0)
 *  串的名称：s
 *  串的值：用单引号（有些书中也用双引号）括起来的字符序列，可以是数字、字母或者其他字符。但是单引号本身不属于串，它的作用是避免与变量名或数的常量混淆。
 *  串的长度：n

### 有关概念 ###

*  空串：零个字符的串称为空串，其长度为零。例如 s = ‘’。
 *  子串：串中任意个连续的字符组成的子序列称为该串的子串，例如 s = ‘abcde’，t = ‘abc’，则 t 是 s 的子串
 *  主串：包含子串的串相应地称为主串，例如 s = ‘abcde’，t = ‘abc’，那么 s 就是 t 的主串
 *  串的位置：字符在序列中的序号称为该字符在串中的位置，例如s = ‘abcde’，字符’ b '在 s 中的位置就是2（在实际应用中为了方便数组操作，也可以从零开始数，则此处就为1）。
    
    而子串在主串中的位置，则用子串的第一个字符在主串中的位置来表示。例如 s = ‘abcde’，t = ‘cd’，子串 t 在 s 中的位置为3。
 *  串相等：只有两个串的长度相等，并且各个对应位置的字符都相等时才称为串相等。例如 s = ‘abc’，t = ‘ab c’，此时 s 和 t 并不相等（空格也属于字符集合中的一个元素）。
 *  空格串：由一个或者多个空格组成的串，称为空格串。例如 s = ’ '，此时 s 串是空格串，但不是空串，其长度为空格的数量。

### 串的存储结构 ###

回顾线性表的概念：由n(n>=0)个数据特性相同的元素构成的有限序列。

可以发现，同样是有限序列，串的逻辑结构和线性表是很相似的，区别仅在于串的约束对象是字符集。也就是说，假如字符串中存储的是’123456’这么一串，实际上它保存的类型是char，而不是int。

那么，把线性表的存储类型改为char不也能表示串吗？按理来说是这样，但是串与线性表的主要区别是在操作上。在线性表的基本操作中，多以”单个元素“作为操作的对象，例如插入、删除等，多是对某个元素进行操作；而在线性表中，多以“串的整体”作为操作的对象，比如插入，多是插入另一个串，而不是单个字符。因此，串的操作和线性表有很大不同，需要把串当成与线性表不同的逻辑结构来看待。

从存储结构上来说，串也有两种基本的存储结构：顺序存储和链式存储。

#### 顺序存储 ####

有些资料中说，串有三种机内表示方法，分别是定长顺序表示、堆分配存储表示和块链存储表示。实际上，定长顺序表示和堆分配表示都属于顺序存储。

顺序存储的特点是，使用一组地址连续的存储单元来进行存储。我们使用顺序存储结构时，往往需要在一开始去申请一整块的内存空间，然后在我们所申请好的这块内存空间内来插入、删除元素；这样就会出现一个问题：如果这块空间满了，又有新元素需要存入，应该怎么办呢？

在我们以往的实现中，有两种做法：第一种是逻辑上我的这个存储空间已经满了，就不允许再存入了，它的内存是静态的，能存多少元素已经在一开始确定了。而第二种则会在空间满的时候去重新申请一块更大的空间，只有当物理内存真正满了，空间申请失败的时候，才不允许再存入，它的内存是动态分配的。

我们把采用第一种处理方法称为定长顺序表示，定长即串空间的大小在编译的时候就确定了，不允许再更改，顺序则意味着它的地址空间是连续的。而第二种处理方法称为堆分配表示，因为C语言的内存分为五大分区，其中一个区叫做堆（heap）区，这个区的空间可以让程序员来进行分配释放，我们调用malloc和free函数，就是在对堆区的内存进行操作。在堆分配表示中，串的空间可以动态分配，意味着串长可以任意（只要不超过实际的内存），但是它的地址空间仍然是连续的。

##### 定长顺序表示 #####

在定长顺序表示里，需要规定一个最大串长，在串创建时就按照预定义的大小为每个串分配固定的存储区，串的实际长度可以在预定义的范围之内，超过预定义长度的部分将会被舍去，称为”截断“。

##### 堆分配表示 #####

在堆分配表示中，存储空间是在程序执行过程中动态分配而来的，所占的空间由串的实际长度决定。需要注意的是，即使是动态分配，它的空间也是连续的一整块，可以去查一下malloc、relloc和calloc函数的细节。

##### 顺序存储中串结构的设计 #####

无论是顺序存储还是链式存储，都首先需要考虑一个问题：怎样确定串已经结束了？实际上它也可以转换成另一个问题：怎样确定串的实际长度？针对这两个问题的不同回答，决定了对串结构的不同设计。在这里先说顺序存储中的情况。

假设我们从串长的角度来考虑，只需要额外使用一个变量来保存串的长度，并且实时更新就可以了。这样，我们可以设计出来一个结构体，它包括一个存储串的空间，和一个保存串当前长度的整型变量

定长顺序表示：

#define MAXSTRLEN 255 //最大串长
    typedef struct SString{ 
      char ch[MAXSTRLEN]; //存储串的一维数组
      int length;      //串的当前长度
    }SString;

堆分配表示：

typedef struct HString{ 
        char *ch;  //串的存储空间
        int length;  //串的当前长度
    }HString;

在定长顺序串中，还可以直接把当前长度存到数组中的0号单元里，让串从1下标开始，这样一开始要开辟的就是最大串长+1的空间，并且也不需要结构体了。

#define MAXSTRLEN 255 //最大串长
    typedef unsigned char SString[MAXSTRLEN+1]; //0号单元存放串的当前长度

![img\_1][img_1]

需要注意，这个时候使用 unsigned char 型来保存数值，最大串长只能到255。

假如从串结束的问题来考虑，可以和C语言的做法一样，在串的最后加上一个不计入串长的字符来标记，比如’\\0’，这样要开辟的也是最大串长+1的空间。由于这个时候的串长是无法直接得到的，在有些操作上可能不太方便。

定长顺序表示：

#define MAXSTRLEN 255 //最大串长
    typedef unsigned char SString[MAXSTRLEN+1]; //多出来一位用于在串满时在末尾加上'\0'

![img\_2][img_2]

堆分配表示：  
（初始化时需要记得多申请一个位置用于存放’\\0’，并且在每次串变动后都需要注意’\\0’的设置。）

typedef unsigned char* HString;

#### 链式存储 ####

一般而言，链式存储的设计包括两个部分：第一是结点的设计，包括结点要保存的内容和后续结点的指针。第二则是针对整个链式结构的设计，比如设置头指针尾指针、结点数量等，用于对整个结构进行管理，并且方便一些操作。

额外提一下，这个“结点要保存的内容”可以很简单，我们平时学习的时候为了简便常常只是设置一个int型，得到的只是一些数值，感觉似乎没什么用；但是它也可以比较复杂，例如一个学生的信息，那么就需要char来记录名字，int来记录年龄、编号等等等等，需要根据实际情况来设置这个结构体，它的应用其实是很广泛的。

言归正传，对结点的设计很重要。按照往常的思路，我们一个结点用于保存一个字符，那么就是这样的：

![img\_3][img_3]

//结点
    typedef struct Node{ 
      char c; //保存字符
      struct Node * next; //下一个结点
    }Node;

这虽然可行，但是我们一个结点只保存一个字符的话，每保存一个字符，就要花一个额外的空间来保存下一个结点的指针，造成比较大的浪费，由于串的特性，我们也可以考虑一个结点保存多个字符。

![img\_4][img_4]

一个结点保存多个字符，首先需要设置结点可保存的最大字符量，假如我们用数组来存储，这实际上就是定长顺序串和链式存储的结合。

#define CHUNCKSIZE 3 //一个结点保存三个字符
    //结点
    typedef struct Chunk{ 
      char ch[CHUNKSIZE]; //存储串的一维数组
      struct Chunk *next; //下一个结点
    }Chunk;

这里可以通过判断next结点是否为空来确定串是否结束，所以不像顺序存储中那么麻烦。

![img\_5][img_5]  
如图所示，假如我们使用数组来存储的话，最后一个结点它不一定会被占满，此时常补上“\#”或者其他的非串值字符（通常不把“\#”包括在串的字符集中，而是当做一个特殊符号。）

如果不想造成这样的浪费的话，也可以考虑不用数组来存储，而是动态开辟空间，假如要存储的字符串长度大于等于设定的结点长度，就按照设定长度来开辟；假如小于，则按照字符串实际的长度来开辟（怎样确定要存储的字符串长度，又是一个问题）。

#define CHUNCKSIZE 3 //一个结点保存三个字符
    //结点
    typedef struct Chunk{ 
      char *ch; //实际空间->按照情况来分配
      struct Chunk *next; //下一个结点
    }Chunk;

![img\_6][img_6]

为了方便串的操作，除了头指针外还可以附设一个尾指针，并且给出当前串的长度，称这样定义的串存储结构为块链结构，因为单个结点它不是只保存一个数据，而是一“块”数据。

//整个串
    typedef struct LString{ 
      Chunk *first; //头指针
      Chunk *last; //尾指针
      int length;  //串长
    }LString;

串的链式存储结构在除了某些操作，比如连接两个串时，有一定的方便之处，但是总体而言没有顺序存储结构灵活，性能也不高，因此比较少用。

[img_1]: https://img-blog.csdnimg.cn/20191223141551349.png
[img_2]: https://img-blog.csdnimg.cn/20191223141621993.png
[img_3]: https://img-blog.csdnimg.cn/20191223141643674.png
[img_4]: https://img-blog.csdnimg.cn/20191223141700974.png
[img_5]: https://img-blog.csdnimg.cn/2019122314172019.png
[img_6]: https://img-blog.csdnimg.cn/20191223141732507.png