【数据结构】串？在计算机中还有这样一种数据结构

串的基本概念与基本操作

• 导言
• 一、串的定义及其重要术语
• • 1.1 串的定义
  • 1.2 串的重要术语
  • 1.3 ASCII码值
  • 1.4 转义字符
  • 二、串的三要素
  • • 2.1 串的逻辑结构
    • 2.2 串的存储结构
    • 2.3 串的运算
    • 结语

      导言

      大家好，很高兴又和大家见面啦！！！

      看到今天的标题，有部分朋友可能会有这样的疑惑——这个串是指的什么？总不可能是羊肉串、牛肉串之类的吧！明人不说暗话，今天咱们要介绍的串这种数据结构说白了就是指的字符串。

      今天我们进入了数据结构的一个新的章节，在这个章节中，我们将学习字符串的模式匹配算法。

      为了更好的了解字符串及其模式匹配算法的内容，我们将会花两个篇章的内容来详细介绍字符串这种数据结构的三要素。

      下面我们就开始今天的内容吧！

      一、串的定义及其重要术语

      字符串简称串，计算机上非数据处理的对象基本都是字符串数据。

      1.1 串的定义

      串（string）是由零个或多个字符组成的有限序列。一般记为：

      S = " a 1 a 2 a 3 … … a n " ( n > = 0 ) S="a_1a_2a_3……a_n"(n>=0) S="a1​a2​a3​……an​"(n>=0)

      其中，S为串名，在C语言中我们学习的字符串是由双引号串起来的字符序列，这个序列就是S对应的值； a i a_i ai​可以是字母、数字或是其他字符；串中字符的个数n称为串的长度。当 n = 0 n=0 n=0时，对应的字符串称为空串，用∅表示。

      1.2 串的重要术语

      在串中我们需要了解以下术语：

      • 子串：由任意个连续的字符组成的子序列称为该串的子串；
      • 主串：包含子串的串称为主串；
      • 字符在串中的位置：字符串中的某个字符在串中的序号称为字符串在串中的位置；
      • 子串在主串中的位置：子串的第一个字符在主串中的位置；
      • 空串与空格串：由一个或多个空格组成的字符串如S = " "称为空格串，字符串长度为0的字符串称为空串；

        单看这些概念可能不太好理解，下面我们以串S = “Hello world!!!” 为例来说明以上的这些概念。

        对于字符串∅、“H”、“He”、“Hello”……这些由任意个连续的字符组成的子序列称为该串的子串；

        包含这些子串的串也就是S称为主串；

        字符’H’在串中的序号是1，字符’w’在串中的序号是7，也就是字符’H’在串中的位置为1，字符’w’在串中的位置为7；

        字符串"ell"在主串中第一次出现时第一个字符’e’的位置为2，因此子串"ell"在主串中的位置为2；

        对于子字符串" "它是由一个空格组成的字符串，它的长度为1，因此它被称为空格串；

        对于空串∅它的字符串长度为0

        提到字符串和字符串中的字符，那必然少不了ASCII码值的相关知识点。

        1.3 ASCII码值

        ASCII (American Standard Code for Information Interchange)：美国信息交换标准代码是基于拉丁字母的一套电脑编码系统，主要用于显示现代英语和其他西欧语言。它是最通用的信息交换标准，并等同于国际标准 ISO/IEC 646。ASCII第一次以规范标准的类型发表是在1967年，最后一次更新则是在1986年，到目前为止共定义了128个字符 ¹。

        在计算机中，所有的数据在存储和运算时都要使用二进制数表示（因为计算机用高电平和低电平分别表示1和0），例如，像a、b、c、d这样的52个字母（包括大写）以及0、1等数字还有一些常用的符号（例如*、#、@等）在计算机中存储时也要使用二进制数来表示，而具体用哪些二进制数字表示哪个符号，当然每个人都可以约定自己的一套（这就叫编码），而大家如果要想互相通信而不造成混乱，那么大家就必须使用相同的编码规则，于是美国有关的标准化组织就出台了ASCII编码，统一规定了上述常用符号用哪些二进制数来表示 ¹ 。

        美国信息交换标准代码是由美国国家标准学会(American National Standard Institute , ANSI )制定的，是一种标准的单字节字符编码方案，用于基于文本的数据。它最初是美国国家标准，供不同计算机在相互通信时用作共同遵守的西文字符编码标准，后来它被国际标准化组织（International Organization for Standardization, ISO）定为国际标准，称为ISO 646标准。适用于所有拉丁文字字母 ¹。

        ASCII 码使用指定的7 位或8 位二进制数组合来表示128 或256 种可能的字符。标准ASCII 码也叫基础ASCII码，使用7 位二进制数（剩下的1位二进制为0）来表示所有的大写和小写字母，数字0 到9、标点符号，以及在美式英语中使用的特殊控制字符 ¹。

        从上图中不难看出，在ASCII码表中0～31为控制字符，每一种字符都有特定的功能，如换行、回车、换页等；32～127为打印字符，能够在文本中正常打印；而上图中未展示的后128个称为扩展ASCII码。许多基于x86的系统都支持使用扩展（或“高”）ASCII。扩展ASCII 码允许将每个字符的第8 位用于确定附加的128 个特殊符号字符、外来语字母和图形符号。

        细心的朋友会在控制字符看到有一些控制字符存在对应的转义字符，下面我们就来继续复习一下转义字符的相关知识点。

        1.4 转义字符

        在C语言中反斜杠——''这个字符我们将其称为转义序列符，它的作用就是在跟特定的字符组合在一起时将其转换成其它字符，如下表所示：

        转义字符	释义
        \ ?	在书写连续多个问号时使用，防止它们被解析成三字符词
        \’	用于表示一个单引号 ’
        \"	用于表示一个字符串内部的双引号 "
        \\	用于表示一个反斜杠，防止它被解释成一个转义序列符
        \a	警告字符，部分计算机在输出时会有蜂鸣提示音
        \b	退格符
        \f	进纸符
        \n	换行
        \r	回车
        \t	水平制表符
        \v	垂直制表符
        \ddd	ddd代表1～3个八进制的数字。 如：\130 这里的130为八进制数字，对应的字符为X
        \xdd	x表示的是十六进制数字，dd表示2个十六进制的数字，如：\x30 这里的30为十六进制数字，对应字符为0

        转义字符的存在主要是为了能够在文本中展示一些无法正常打印的字符，比如我想在字符串中表示

        一个水平制表符，我们在文本中可以通过TAB键来进行操作，但是它也是和空格一样不会被显示出来，这时我们就可以通过它对应的转义字符\t来表示。比如"\thello"在这个字符串中，就是由一个水平制表符和五个小写字母组成，字符串的长度为6，该字符串在屏幕中输出的内容如下所示：

        大家看到这里应该对转义字符的相关知识点有了一个初步的了解，在转义字符中有几点我们需要注意一下：

        1. 并不是所有字符都有转义字符
        2. 所有的转义字符都是一个字符，其字符长度为1
        3. 由转义序列符和1～3个八进制数字组成的是一个八进制数
        4. 由转义序列符和字符x域两个十六进制数字组成的是一个十六进制数
        5. 转义序列符的作用是将原先字符转换成另一种字符，因此我们可以通过转义序列符将转移序列符转义成一个普通的字符'\'

        介绍完了串的基础知识点，下面我们就来依次探讨串这种数据结构的三要素——数据的逻辑结构、数据的存储结构和数据的运算。

        二、串的三要素

        2.1 串的逻辑结构

        串是由零个或多个字符组成的有限序列，一般记为 S = " a 1 a 2 a 3 … … a n " ( n > = 0 ) S="a_1a_2a_3……a_n"(n>=0) S="a1​a2​a3​……an​"(n>=0)。

        从这个定义中，我们不难得到以下信息：

        1. 串中的元素具有相同的数据类型——字符类型
        2. 串是一个有限序列 ( 0 ～ n ) (0～n) (0～n)
        3. 串中的元素之间只存在一对一的关系

        因此串也是一种线性表，串中的元素在逻辑上呈现的是线性结构。

        2.2 串的存储结构

        作为一种线性表，串中的元素在物理上的存储方式同样也是有两种——顺序存储和链式存储。

        在之前的学习中我们接触到的字符串实际上就是通过顺序存储实现的串，如下所示：

        可以看到此时串中的元素不仅在逻辑上相邻在物理位置上也是相邻的。

        通过链式存储实现的串实际上就是数据域为字符类型的链表，如下所示：

        //串的存储结构——链式存储
        typedef struct LinkString {char data;
        	struct LinkString* next;
        }LString;
        

        对于链表的基本操作，大家都已经很熟悉了，这里我就不再多加赘述了。

        2.3 串的运算

        串与我们之前学习的线性表在基础操作上还是有很大的区别的，串的基本操作有：赋值、复制、判空、比较、求串长、求子串，串联接、定位、清空、销毁等操作。这些操作对应的函数定义与含义如下所示：

        StrAssign(&T, chars);//赋值操作。把串T赋值为chars。
        StrCopy(&T, S);//复制操作。由串S复制得到串T。
        StrEmpty(S);//判空操作。判断串S是否为空。
        StrCompare(S, T);//比较操作。若S>T,则返回值>0；若S=T，则返回值=0；若S 
        不同的高级语言对串的基本操作集可以有不同的定义方法。在上述定义的操作中，串赋值StrAssign、串比较StrCompare、求串长StrLength、串联接Concat、以及求子串SubString五种操作构成串类型的最小操作子集，即这些操作不可能利用其他串操作来实现；反之，其他串操作（除串清除ClearString和串销毁DestroyString外）均可在该最小操作子集上实现。
         
        结语
         
        在今天的内容中，我们重新学习了串——串是由零个或多个字符组成的有限序列。并介绍了串中的相关术语：主串、子串、字符在串中的位置、子串在主串中的位置、空串和空格串。
         
        之后我们介绍了与字符串相关的知识点——ASCII码值与转义字符。这两个内容都是来帮助我们更好的学习字符串的相关内容。
         
        紧接着我们就从数据结构的三要素介绍了串这种数据结构的逻辑结构、存储结构以及相关运算。经过介绍，我们知道了串也是一种线性结构，并且在内存中和线性表一样既可以通过顺序存储来实现也可以通过链式存储来实现。最后我们简单介绍了串的10种基本操作——赋值、复制、判空、比较、求串长、求子串，串联接、定位、清空、销毁。
         
        通过今天的内容，希望大家能够重新认识串，并且对串的基本操作有一个初步的了解。在下一篇内容中，我们将重点介绍串的基本操作以及如何通过C语言来实现这些基本操作，大家记得关注哦！
         
        如果大家喜欢这篇内容，可以点赞、收藏加评论来支持一下博主哦！当然也可以转发给身边需要的朋友。最后感谢各位的支持，咱们下一篇再见！！！
         
         
         
        ASCII ↩︎ ↩︎ ↩︎ ↩︎