数据结构实用教程（C语言版） 董凤服及算法 第4章 串和数组

《数据结构实用教程（C语言版） 董凤服及算法 第4章 串和数组》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构实用教程（C语言版）中国水利水电出版社第4章串和数组本章主要介绍下列内容串的定义、存储结构和基本运算数组的定义、基本运算和存储结构稀疏矩阵的压缩存储与转置本章目录4.1串14.2数组24.3本章小结3结束4.1串4.1.1串的基本概念4.1.2串的基本操作4.1.3串的存储结构返回到总目录4.1.1串的基本概念字符串简称为串，是一种特殊的线性表，它的数据元素仅由字符组成。计算机上的非数值运算处理的对象基本上是字符串数据，如在汇编和高级语言的编译程序中，源程序和目标程序都是字符串数据；在事务处理程序中，顾客的姓名、地址等一般也是作为字符串处理的。1．串的概念串(String)是零

2、个或多个字符组成的有限序列。一般记为：S="a1a2...an"(n≥0)其中，S为串名，在本书中用双引号作为串的定界符，引号括起来的字符序列为串值，ai（1≤i≤n）可以是字母、数字或其他字符，n为串的长度。返回到本节目录4.1.1串的基本概念2．串的相关术语（1）空串不含任何字符的串称为空串，即串的长度n=0时的串为空串。（2）空格串由一个或多个称为空格的特殊字符组成的串称为空格串，它的长度是串中空格字符的个数（注：本书用符号“”代表空格符号）。【例4.1】有两个串，串S1=""，S2=""，S1与S2串是否相同。解：不相同，其中S1中没有字符，是一个空串；而S2中有两个空格

3、字符，它的长度等于2，它是由空格字符组成的串，是空格串。返回到本节目录4.1.1串的基本概念2．串的相关术语（3）子串串中任意个连续的字符组成的子序列称为该串的子串。另外，空串是任意串的子串，任意串是自身的子串。（4）主串包含子串的串称为该子串的主串。（5）子串的位置子串在主串中第一次出现的第一个字符的位置。（6）两个串相等两个串的长度相等且各个位置上对应的字符也都相同。返回到本节目录4.1.1串的基本概念2．串的相关术语【例4.2】有四个串，S1="WelcometoBeijing!"，S2="Welcometo"，S3="Welcometo"，S4="Beijing"，则各串长度

4、及其之间的关系如何？解：（1）S1的长度为19，S2的长度为10，S3的长度为10，S4的长度为7。（2）S2和S4为S1的子串，S1相对于S2和S4为其主串，S2在S1的位置为1，S4在S1的位置为12。（3）S3不是S1的子串，因为它不是S1串中的连续字符组成的子序列（在e与t字母之间缺少一个空格）。（4）S2与S3串不相等，因为虽然两串的长度相等，但各个对应的字符不相同。返回到本节目录4.1.2串的基本操作串的基本操作有：（1）串的赋值StrAsign(S,chars)初始条件：chars是字符串常量。操作结果：生成一个值等于chars的串S。（2）串的复制StrCopy(S,T

5、)初始条件：串S存在。操作结果：由串T复制得串S。（3）求串长度StrLength(S)初始条件：串S存在。操作结果：返回串S的长度，即串S中的元素个数。返回到本节目录4.1.2串的基本操作串的基本操作有：（4）串的连接StrCat(S,T)初始条件：串S和T存在。操作结果：将串T的值连接在串S的后面。（5）求子串SubString(Sub,S,pos,len)初始条件：串S存在，1≤pos≤StrLength(S)且1≤len≤StrLength(S)-pos+1。操作结果：用Sub返回串S的第pos个字符起长度为len的子串（6）串的定位（也称模式匹配）StrIndex(S,T)初

6、始条件：串S和T存在，T是非空串。操作结果：若串S中存在与串T相同的子串，则返回它在串S中第一次出现的位置；否则返回-1或代表错误的值。返回到本节目录4.1.2串的基本操作串的基本操作有：（7）串的插入StrInsert(S,pos,T)初始条件：串S和T存在,1≤pos≤StrLength(S)+1。操作结果：在串S的第pos个字符插入串T。（8）串的删除StrDelete(S,pos,len)初始条件：串S存在，1≤pos≤StrLength(S)且1≤len≤StrLength(S)-pos+1。操作结果：从串S中删除第pos个字符起长度为len的子串。（9）串的替换StrRep

7、lace(S,T,V)初始条件：串S，T和V存在，且T是非空串。操作结果：用V替换串S中出现的所有与T相等的不重叠子串.返回到本节目录4.1.2串的基本操作串的基本操作有：（10）判断串空StrEmpty(S)初始条件：串S存在。操作结果：若串S为空串，则返回TRUE，否则返回FALSE（11）串的比较StrCompare(S,T)初始条件：串S和T存在。操作结果：若S>T，则返回值>0；若S=T，则返回值=0；若S