第5章 串与数组1.pptVIP

数据结构课程的内容 补充：C语言中常用的串运算 第5章 串和数组 练1：串是由 字符组成的序列，一般记为 。 5.2 串的表示和实现 定长顺序存储特点：用一组连续的存储单元来存放串，直接使用定长的字符数组来定义，数组的上界预先给出，故称为静态存储分配。 例：用顺序存储方式实现求子串函数SubString(Sub, S, pos, len) 堆分配存储特点：仍用一组连续的存储单元来存放串，但存储空间是在程序执行过程中动态分配而得。 例：用“堆”实现串插入操作(教材P94) 链式存储特点 ：用链表存储串值，易插入和删除。 5.3 正文模式匹配算法 算法种类： ② BF算法的实现—即Index（）操作的实现 （见教材P96） * 串比较，int strcmp(chars1,char s2); // StrCompare(S,T) 求串长， int strlen(char s); // StrLength(S) 串连接，char strcat(char to,char from) // Concat(T, S1, S2) 子串T定位，char strchr(char s,char c); // Index(S, T, pos) …… Concat ＝concatenation，在字符串处理中,把多个短字符串合成为长字符串的操作。 注：用C处理字符串时，要调用标准库函数 #includestring.h 5.2 串的表示和实现 5.3 串的模式匹配算法 1. 定义 2. 逻辑结构 3. 存储结构 4. 运算规则 5. 实现方式 5.1 串类型的定义 记为： s =“ a1 , a2 , …….. , an” (n≥0 ) 串名 串值（用”” 括起来） 串中字符个数（n≥0）. n=0 时称为空串 ? 。 由一个或多个空格符组成的串。 串s中任意个连续的字符序列叫s的子串; S叫主串。 子串的第一个字符的序号。 字符在串中的序号。 串长度相等，且对应位置上字符相等。 串即字符串，是由零个或多个字符组成的有限序列，是数据元素为单个字符的特殊线性表。 5.1 串类型的定义 若干术语： 串长： 空白串： 子串： 子串位置： 字符位置： 串相等： 隐含结束符‘/0’ ，即ASCII码NUL 练2：现有以下4个字符串： a =“BEI” b =“JING” c = “BEIJING” d = “BEI JING” 问：① 他们各自的长度？ ② a是哪个串的子串？在主串中的位置是多少？ a =3，b =4，c = 7，d=8 a是c和d的子串，在c和d中的位置都是1 练3：空串和空白串有无区别？ 答：有区别。空串(Null String)是指长度为零的串；而空白串(Blank String),是指包含一个或多个空白字符” “(空格键)的字符串. 0个或多个 S=“a1a2……an” 定长顺序存储表示 ——用一组地址连续的存储单元存储串值的字符序列 堆分配存储表示 ——用一组地址连续的存储单元存储串值的字符序列,但存储空间是在程序执行过程中动态分配而得。 串的块链存储表示 ——链式方式存储 首先强调：串与线性表的运算有所不同，是以“串的整体”作为操作对象，例如查找某子串，在主串某位置上插入一个子串等。 串有三种机内表示方法： 顺序存储 链式存储 例如： #define Maxstrlen 255 //用户可用的最大串长 typedef unsigned char SString[ Maxstrlen＋1 ]; SString s; //s是一个可容纳255个字符的顺序串。 注： 一般用SString[0]来存放串长信息； C语言约定在串尾加结束符 ‘ \0’，以利操作加速，但不计入串长； 若字符串超过Maxstrlen 则自动截断（因为静态数组存不 进去）。 讨论：想存放超长字符串怎么办？——静态数组有缺陷！ 实现方式：参见教材P73编程两例，两串连接和求子串 改用动态分配的一维数组—— “堆”！ Status SubString(char sub[ ], char S[ ], int pos, int len ) { slen=StrLength_Sq(S); // 求字符串S的长度 if(pos0 || posslen-1] || len0 || lenslen-pos) retur