当前位置：首页 > article >正文

数据结构（11）串的基本概念

article 2024/11/27 12:55:07

一、串的定义

1.串是由一个或者多个字符组成的有限序列，一般记为：s=a1a2…an（n≥0）。其中，s是串的名称，用单括号括起来的字符序列是串的值；ai（1≤i≤n）可以是字母、数字或其他字符。

2.串中的字符数目n称为串的长度。零个字符的串称为空串，它的长度为0。

3.串中任意个连续的字符组成的子序列称为该串的子串。包含子串的串相应的称为主串。

二、串的相关术语

1.空串：长度为0的串称为空串。注意，空串和空格串（只包含空格的串）是有区别的。

2.空格串：由一个或多个空格组成的串。空格串有内容有长度，而空串没有。

3.子串与主串：串中任意个连续的字符组成的子序列称为该串的子串。包含子串的串相应地称为主串。

三、串的表示与存储

1.串的表示方法多种多样，常见的包括定长顺序存储表示、堆串（动态分配存储空间的串表示）和块链串（类似于链表结构，但每个节点可以存放多个字符）等。

2.在计算机内存中，串的存储结构主要分为顺序存储结构和链式存储结构。顺序存储结构是将串中的字符顺序地存放在一段连续的存储空间中，通常是字符数组。链式存储结构则是通过链表来存储串的字符，每个节点存储一个字符，并且通过指针将各个节点连接起来。

四、串的基本操作

串的基本操作通常包括查找、插入、删除、替换、连接和比较等。这些操作在文本处理、字符串匹配和数据库索引等方面具有重要应用。

查找：在串中查找特定子串或字符的位置。
插入：在串的指定位置插入新的字符或子串。
删除：从串中删除指定位置的字符或子串。
替换：将串中的指定字符或子串替换为新的字符或子串。
连接：将两个或多个串连接成一个新的串。
比较：比较两个串是否相等，或者按照字典顺序比较它们的大小。