数据结构与算法(c语言版)串讲

《数据结构与算法(c语言版)串讲》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构与算法（C++语言版）第4章串现实世界中的实体有多种形式，如数值、文字符号序列、图形、图像、声音等，其中文字（符号）序列称为字符串，简称串。串是一种常用的数据结构，用于描述非数值的简单信息，它在现实世界中屡见不鲜，如人名、产品名、事物名称、车牌号、文献、源程序等。从数据元素间的逻辑关系看，串是线性表，但从操作方式与种类看，它与线性表有许多不同。在计算机中，串被认为是一种特殊的线性表——元素为文字符号的线性表。由于现实问题中经常使用串，所以对串应选择合适的存储结构，并提供灵活多样的基本操作。串的逻辑结构基本概念串（string）是由零个

2、或多个字符构成的有限序列，一般记为s=‘s1s2…sn’（n≥0）。其中，s是串名，用单引号括起来的字符序列是串的值，但单引号本身并不属于串，si（1≤i≤n）为一个字符，字符是计算机可识别的任意符号（字母、数字或其他符号）。串的长度：串中字符的数目n。空串：零个字符的串，其长度为零。空白串：由一个或多个空格组成的串，其长度为串中空格字符的个数。子串：串中任意个连续的字符组成的子序列。主串：包含子串的串相应地称为主串。串的逻辑结构字符在串中的位置：字符在序列中的序号。串相等：当且仅当这两个串的值相等，即两个串的长度相等，并且各个对应位置的字符

3、都相等。通常，在程序中使用的串可分为两类：串变量和串常量。串变量和其他类型的变量一样，其取值是可改变的。串常量和常数一样，在程序中只能被引用但不能改变其值，即只能读不能写。例4-1假设a、b、c、d为如下的4个串：a=‘Guang’，b=‘Zhou’，c=‘GuangZhou’，d=‘GuangZhou’。它们的长度分别为5、4、9、10；并且a和b都是c和d的子串，a在c和d中的位置都是1，而b在c中的位置是6，在d中的位置是7；a、b、c、d彼此都不相等。显然，若某串的长度为n，则在该串中，长度为1的子串的个数为n，长度为2的子串的个数为

4、n1，……，长度为i的子串的个数为n(i1)，所以长度为n的串中子串总数（包括空串与自身）为1+=1+。串的抽象数据类型定义见以下ADT。例4-1例4-1例4-1串的逻辑结构串的大小比较字符的大小在计算机中，每个字符都有一个唯一的数值表示——字符编码（字符内码），字符间的大小关系就定义为它们的代码之间的大小关系。字符编码可有多种，对英文字母和符号，ASCII码是最常见的一种。本书用字符的ASCII码之间的大小关系代表相应字符的大小关系。ASCII码即美国信息交换标准编码，是长度为8位二进制符号，所以最多能编28=256个不同的字符。但A

5、SCII码中规定，最高位为1的码代表一些特殊的字符（或命令），所以ASCII码有效的字符编码为128个，其包括英文大、小写字母，数字0～9及一些常用符号（计算机键盘上的字符键）。在字符和数字中，空格编码最小，其次是数字（按0～9的次序）、大写字母（按A～Z的次序）、小写字母（按a～z的次序）等。串的逻辑结构对于汉字，它们的大小关系也按编码大小确定。汉字的编码也有几种，如我国内地用的国标码（GB2312），我国台湾地区用的Big5等。GB2312（国标码）是针对汉字的16位二进制编码，所以最多能编216=65536个不同的码，足以代表新华字典中

6、所有的汉字。GB2312将汉字分为两级编码，分别称一级字库和二级字库。一级字库包括了日常用的大多数汉字，其汉字的国标码之间的大小关系，与对应的汉语拼音构成的串的大小关系一致（在新华字典中，排在较前面的字，它的国标码也较小）。而二级字库中的汉字码之间的大小关系，与对应汉字的笔画数目的大小关系一致。要在一个系统中混合使用多种文字，需要一种统一的编码系统，它可以将各种文字的基本字符在同一空间内编码，UniCode就是这样一种编码。串的逻辑结构字符串间的大小关系有了字符大小的定义，就可考虑串的大小关系了。设X与Y是两个串，X=‘x1x2…xm’，Y=

7、‘y1y2…yn’，则它们之间的大小关系定义如下。①当m=n且x1=y1,…,xm=yn时，称X=Y。②当下列条件之一成立时，称X＜Y：i．m

8、串也有两种基本的存储结构：顺序结构与链式结构。考虑到存储效率与算法实现的方便性，串多采用顺序存储结构。顺序存储串的顺序存储结构简称为顺序串。与顺序表类似，顺序串用一