安徽科技学院数据结构课件第四章 串.ppt

01/06/2002 数据结构讲义 第四章 串 ⒈教学内容：4.1 串及其基本运算 4.2 串的定长顺序存储及基本运算 4.3 串的堆存储结构 ⒉教学目的：⑴了解串的定义； ⑵理解和领会串的存储方式； ⑶掌握常用的串运算。 ⒊教学重点：⑴串的基本概念、基本运算； ⑵串的两种存储方式。 ⑶串的模式匹配算法。 ⒋教学难点：⑴串的模式匹配算法； ⑵串的基本运算的综合应用 ⒌学时安排： 4学时 4.1 串及其基本运算 串的基本概念 串的基本运算 4.1.1 串的基本概念 串是由零个或多个任意字符组成的字符序列。一般记作：s=”s1 s2 … sn”。 其中s 是串名；在本书中，用双引号作为串的定界符，引号引起来的字符序列为串值，引号本身不属于串的内容； ai(1=i=n)是一个任意字符，它称为串的元素，是构成串的基本单位，i是它在整个串中的序号; n为串的长度，表示串中所包含的字符个数，当n=0时，称为空串，通常记为Ф。 4.1.2 串的基本运算 ⒈求串长 StrLength(s) 操作结果是求出串s的长度。 ⒉串赋值 StrAssign(s1,s2) s1是一个串变量，s2或者是一个串常量，或者是一个串变量（通常s2 是一个串常量时称为串赋值，是一个串变量称为串拷贝），操作结果是将s2的串值赋值给s1， s1原来的值被覆盖掉。 ⒊连接操作 StrConcat (s1,s2,s) 或 StrConcat (s1,s2) 两个串的连接就是将一个串的串值紧接着放在另一个串的后面，连接成一个串。前者是产生新串s，s1和s2不改变; 后者是在s1的后面联接s2的串值，s1改变， s2不改变。 ⒋求子串 SubStr (s,i,len) 串s存在并且1≤i≤StrLength(s)，0≤len≤StrLength(s)-i+1。操作结果是求得从串s的第i个字符开始的长度为 len 的子串。len=0得到的是空串。 ⒌串比较 StrCmp(s1,s2) 操作结果是若s1==s2，操作返回值为0；若s1s2，返回值0；若s1s2，返回值0。 4.2 串的定长顺序存储及基本运算 串的定长顺序存储 定长顺序串的基本运算 模式匹配 4.2.1 串的定长顺序存储 用一组地址连续的存储单元存储串值中的字符序列，所谓定长是指按预定义的大小，为每一个串变量分配一个固定长度的存储区，如： #define MAXSIZE 256 char s[MAXSIZE]; 则串的最大长度不能超过256。 4.2.2 定长顺序串的基本运算 主要讨论定长串联接、求子串、串比较算法，顺序串的插入和删除等运算基本与顺序表相同，在此不在赘述。设串结束用＇\0＇来标识。 4.2.3 模式匹配 串的模式匹配即子串定位是一种重要的串运算。设s和t是给定的两个串，在主串s中查找子串t的过程称为模式匹配，如果在s中找到等于t的子串，则称匹配成功，函数返回t在s中的首次出现的存储位置(或序号)，否则匹配失败，返回0。t也称为模式。 为了运算方便，设字符串采用定长存储，且用第三种方式表示串长，即串的长度存放在0号单元，串值从1号单元存放，这样字符序号与存储位置一致。 4.3 串的堆存储结构 串名的存储映象 堆存储结构 基于堆结构的基本运算 4.3.1 串名的存储映象 串名的存储映象是串名－串值内存分配对照表，也称为索引表。表的形式有多种表示，常见的串名－串值存储映象索引表有如下几种： 带串长度的索引表 末尾指针的索引表 带特征位的索引表 4.3.2 堆存储结构 在应用程序中，参与运算的串变量之间的长度相差较大，并且操作中串值的长度变化也较大，因此为串变量预分配固定大小的空间不尽合理。堆存储结构的基本思想是：在内存中开辟能存储足够多的串、地址连续的存储空间作为应用程序中所有串的可利用存储空间，称为堆空间，如设store[SMAX+1]; 根据每个串的长度，动态的为每个串在堆空间里申请相应大小的存储区域，这个串顺序存储在所申请的存储区域中，当操作过程中若原空间不够了，可以根据串的实际长度重新申请，拷贝原串值后再释放原空间。 4.3.3 基于堆结构的基本运算 堆结构上的串运算仍然基于字符序列的复制进行，基本思想是