数据结构—字符串

总第118篇

前言

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

概念

串的存储结构

串的基本操作

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

概念

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

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

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

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

串的存储结构

1.定长顺序存储

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

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

2.变长分配存储

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

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

串的基本操作

1.赋值操作

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

2.取串长度操作

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

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

3.串比较操作

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

4.串连接操作

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

5.求子串操作

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

6.串清空操作

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

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