字符串.ppt
《字符串.ppt》由会员分享,可在线阅读,更多相关《字符串.ppt(31页珍藏版)》请在三一文库上搜索。
1、数据结构 第四章 字符串,本章内容 4.1 串的基本概念 4.2 串的存储结构 4.3 串的基本运算的实现,4-3,4.1 串的基本概念,串(String)的概念 串是由零个或多个字符组成的有限序列。记作: S=a1 a2 an(n0) 其中S是串名,用双引号括起来的字符序列为串值,引号是界限符,ai(1in)是一个任意字符(字母、数字或其他字符),它称为串的元素,是构成串的基本单位,串中所包含的字符个数n称为串的长度,当n=0时,称为空串。,4-4,4.1 串的基本概念,将串值括起来的双引号本身不属于串,它的作用是避免串与常数或与标识符混淆。例如,A=123是数字字符串,长度为3,它不同于整
2、常数123。 【空白串】:仅由一个或多个空格组成的串称为空白串。 【空串】:长度为零的串,除串结束符外,不包括任何其他字符 注意:空串和空白串的不同,例如 和 分别表示长度为1的空白串和长度为0的空串。,4-5,4.1 串的基本概念,子串的概念:串中任意连续的字符组成的子序列称为该串的子串。包含子串的串相应地称为主串。 通常称字符在序列中的序号为该字符在串中的位置。子串在主串中的位置则以子串的第一个字符首次出现在主串中的位置来表示。 例如,设有两个字符串C和D: C=This is a string. D=is 则它们的长度分别为17、2;D是C的子串,C为主串。D在C中出现了两次,其中首次出
3、现所对应的主串位置是3。因此,称D在C中的序号(或位置)为3。 若两个串的长度相等且对应字符都相等,则称两个串是相等的。当两个串不相等时,可按“字典顺序”区分大小。,4.1 串的基本概念,两个串相等,当且仅当这两个串的值相等。 例,串 bei jing 与串 beijing 不相等 。 例,串 eij 是串 beijing 的子串, beijing 称为主串。 例,字符 n 在串 beijing 中的位置为 6 。 例,子串 eij 在串 beijing 中的位置为2。,4-6,4-7,4.1 串的基本概念,串也是线性表的一种,因此串的逻辑结构和线性表极为相似,区别仅在于串的数据对象限定为字符
4、集。 串的运算: 串赋值 StrAssign(&T,chars) 初始条件:chars是字符串常量。 操作结果:生成一个其值等于chars的串T。 StrCopy(&T, S) 初始条件:串S存在。 操作结果:由串S复制得串T。,4-8,4.1 串的基本概念,StrEmpty(S) 初始条件:串S存在。 操作结果:若S为空串,则返回TRUE,否则返回FALSE。 StrCompare(S,T) 初始条件:串S和T存在。 操作结果:若ST,则返回值大于0;若S=T,则返回值等于0 若ST,则返回值小于0。 StrLength(S) 初始条件:串S存在。 操作结果:返回S的元素个数,称为串的长度。
5、,4-9,4.1 串的基本概念,ClearString(&S) 初始条件:串S存在。 操作结果:将S清空为空串。 Concat(&T,S1,S2) 初始条件:串S1和S2存在。 操作结果:用T返回由S1和S2联接而成的新串。 SubString(&Sub,S,pos,len) 初始条件:串S存在,1=pos=StrLength(S) 0=len=StrLength(S) - pos + 1 操作结果:用Sub返回串S的第pos个字符起长为len的子串。,4-10,4.1 串的基本概念,Index(S, T, pos) 初始条件:串S和T存在,T是非空串,1=pos=StrLength(S) 操
6、作结果:若主串S中存在和串T值相同的子串,则返回它在主串S中第pos个字符后第一次出现的位置;否则函数值为0。 Replace(&S, T, V) 初始条件:串S,T和V存在。 操作结果:用V替换主串S中出现的所有与T相等的不重叠的子串。 StrInsert(&S, pos,T) 初始条件:串S和T存在,1=pos=StrLength(S)+1 操作结果:在串S的第pos个字符之前插入串T。,4-11,4.1 串的基本概念,StrDelete(&S, pos, len) 初始条件:串S存在,0=len=StrLength(S) - pos + 1 操作结果:从串S中删除第pos个字符起长度为l
7、en的子串。 DestroyString(&S) 初始条件:串S存在。 操作结果:串S被销毁。,4-12,4.2 串的存储结构,顺序存储 块链存储,4-13,4.2 串的存储结构,4.2.1 串的顺序存储 顺序串:串的顺序存储结构简称为顺序串。 与顺序表类似,顺序串是用一组地址连续的存储单元来存储串中的字符序列的。因此可用高级语言的字符数组来实现,按其存储分配的不同可将顺序串分为静态存储分配的顺序串和动态存储分配的顺序串两类。,4-14,4.2 串的存储结构,1. 静态存储分配的顺序串(定长顺序存储) 所谓静态存储分配,是指按预定义的大小为每一个串变量分配一个固定长度的存储区,即串值空间的大小
8、在编译时刻就已确定,是静态的。所以串空间最大值为MAXSIZE时,最多只能放MAXSIZE-1个字符。其类型描述如下: #define MAXSIZE 256 /该值依赖于应用,由用户定义 typedef struct char chMAXSIZE; /256个字符依次存储在ch0chMAXSIZE1中 int len; SString; /SString是顺序串类型,则串的最大长度不能超过255 SString s; /定义串变量s,4-15,4.2 串的存储结构,在直接使用定长的字符数组存放串内容外,一般可使用一个不会出现在串中的特殊字符放在串值的末尾来表示串的结束。例如,C语言中以字符0
9、表示串值的终结。 C语言中串的静态存储结构如下图所示:,C语言中串的静态存储结构,4-16,4.2 串的存储结构,2. 动态存储分配的顺序串(堆分配存储) 堆分配存储仍以一组地址连续的存储单元存放串值字符序列,但它们的存储空间是在程序执行过程中动态分配而得的。 系统将一个地址连续、容量很大的存储空间作为字符串的可用空间,每当建立一个新串时,系统就从这个空间中分配一个大小和字符串长度相同的空间存储新串的串值。 假设以一维数组heapMAXSIZE表示可供字符串进行动态分配的存储空间,并设一整型变量free指向heap中未分配区域的开始地址。在程序执行过程中,当生成一个新串时,就从free指示的位
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 字符串
链接地址:https://www.31doc.com/p-2730523.html