数据结构第4章串

《数据结构第4章串》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第四章串第四章串学习要点1了解串的基本操作，了解利用这些基本操作实现串的其它操作的方法；2掌握在串的堆分配存储结构下，串的基本操作算法；3掌握在串的模式匹配算法；串也叫字符串，它是由零个或多个字符组成的的字符序列。基本内容1串的有关概念串的基本操作2串的顺序存储结构，堆分配存储结构,链式存储结构；3串的基本操作算法；4串的模式匹配算法；第四章串第四章串4.1串的基本概念4.2串存储结构4.3串的基本运算实现4.3串的匹配算法1什么是串串是一种特殊的线性表，它是由零个或多个字符组成的有限序列，一般记作s=“a1,a2,

2、a3,...an”其中s----串名，a1,a2,a3,...an----串值串的应用非常广泛，许多高级语言中都把串的作为基本数据类型。在事务处理程序中，顾客的姓名、地址货物的名称、产地可作为字符串处理，文本文件中的每一行字符等也可作为字符串处理。4.1串的基本概念下面是一些串的例子：（1）a=“Thisisastring”（2）b=“string”（3）c=““（4）d=“”（5）e=“你好”说明：串中包含的字符个数，称为串的长度。长度为0的串称为空串，它不包括任何字符;串中所包含的字符可以是字母、数字或其他字符，这依赖

3、于具体计算机所允许的字符集。4.1串的基本概念2串的有关术语1）子串串中任意连续的字符组成的子序列称为该串的子串;例：c=“DATASTRUCTURE”，f=“DATA”f是c的子串2）子串的位置子串t在主串S中的位置是指主串s中第一个与T相同的子串的首字母在主串中的位置;例：s=“ababcabcac”,t=“abc”子串T在主串S中的位置为33）串相等两个串相等，当且仅当两个串长度相同，并且各个对应位置的字符都相同；4.1串的基本概念3串的基本操作串的逻辑结构与线性表一样，都是线性结构。但由于串的应用与线性表不同，串的

4、基本操作与线性表有很大差别。1）串赋值操作assign(s,t)功能：将串t的值赋给串变量s；2）串相等判断equal(s,t)函数串的联接操作concat(s,t)把串t接在串s后面求串长操作lenght(s)5)求子串操作sub(s,start,len,t)若0<=start

5、的子串的位置，若不存在返回04.1串的基本概念4.1串的基本概念7）替换操作replace(s,t,v)功能：由串v替换串s中出现的所有和t相同的不重叠子串；8）复制串操作strcopy(s,t)功能：由串变量s复制得到串变量t；9）判空操作empty(s)功能：若为空串，则返回1，否则返回010）串置空操作ClearString(s)功能：将s清为空串11)串插入操作StrInsert(s,start,t)功能：将串t插入到串s的第start字符之前12）串删除操作StrDelete(s,start,len)功能：从串s中

6、删除第start个字符起长度len为的子串4.2串存储和实现1顺序存储结构顺序存储结构类似于C语言的字符数组，以一组地址连续的存储单元存放串值字符序列，其类型说明如下：#defineMAX255charch[MAX]0123456789101114…MAX-1chdatastructure在数组ch中以字符‘’表示字符串的结束.特点是访问容易,但删除或插入麻烦4.2串存储和实现2链式存储结构链式存储结构类似线性链表，由于串结构的特殊性,要考虑每个结点是存放一个字符还是多个字符。一个字符的，插入、删除、求长度非常方便，但

7、存储效率低。多个字符的，改善了效率，在处理不定长的大字符串时很有效，但插入、删除不方便，可用特殊符号来填满未充分利用的结点。datastructure♀♀♀headdatehead4.2串存储和实现charstore[MAX];intfree;*/整型域：存放串长*/3、堆分配存储堆分配存储类似于线性表的顺序存储结构，以一组地址连续的存储单元存放串值字符序列，其存储空间是在程序执行过程中动态分配的。一个串值的确定是通过串在堆中的起始位置和串的长度实现的。为此，串名与串值之间要建立一个对照表。串名起址串长a04b49c134….

8、datastructurebookfree=1701234567894.3串的基本运算实现#defineMAX100Chart[MAX],s[MAX];（1）求长度length(s)intlength(chars[]){inti;for(i=0,s[i]!=‘’;i++)