数据结构课件第4章串.ppt
《数据结构课件第4章串.ppt》由会员分享,可在线阅读,更多相关《数据结构课件第4章串.ppt(40页珍藏版)》请在三一文库上搜索。
1、计算机上的非数值处理的对象基本上都是字符串数据。字符串 (string) 一般简称为串。,1,第,4,章,串,4.1 串的逻辑结构,4.2 串的存储结构,例4-1 x = computer ,以下是串的 3 个例子:,2,例4-2 y = student-1 ,例4-2 z = data structure ,串的定义,串的基本操作,3,其中:,串是由零个或多个字符组成的有限序列。记为: s = a1 a2 an ( n 0 ),s 是串的名,用单引号括起来的字符序列是串的值;,ai(1in)可以是字母、数字或其他字符;,n 是串中字符的数目,称为字符串的长度。,4.1.1 串的定义,零个字符
2、的串称为空串 (null string),它的长度为零。用 “” 来表示空串。,4,当且仅当两个字符串的值相等时,也就是说,只有当两个字符串的长度相等,并且各个对应位置上的字符都相等时,则称这两个字符串是相等的。,串中的任意连续的字符组成的子序列称为该串的子串;包含子串的串相应地称为主串。,通常称字符在序列中的序号为该字符在串中的位置。子串在主串中的位置则以子串的第一个字符在主串中的位置来表示。,例4-4 假设 a 、b 、c 、d 为如下 4 个字符串: a = beijing,b = bei,c = jing,d = beijing 则:,a 的长度为 7,b 的长度为 3,c 的长度为
3、4,d 的长度为 8; b 和 c 都是 a 和 d 的子串,且 b 在 a 和 d 中的位置都是 1,而 c 在 a 中的位置是 4 ,在 d 中的位置是 5 。,串 a ,b ,c ,d 彼此都不相等。,5,6,7,4.1.2 串的基本操作,串的逻辑结构和线性表极为相似,区别仅在于串的数据对象约束为字符集 (character set)。,但是,串的基本操作和线性表有很大的差别。在线性表的基本操作中,大多是以 “单个元素” 作为操作对象,比如:在线性表中查找某个元素、在线性表中求取某个元素、在线性表某个位置上插入一个元素以及删除一个元素等;而在串的基本操作中,通常以 “串的整体” 作为操作
4、对象,比如:在串中查找某个子串、在串中求取某个子串、在串的某个位置上插入一个子串以及删除一个子串等。,8,在串的 13 种基本操作操作中,以下 5 种操作构成串类型的最小操作子集,即:这些操作不可能利用其他操作来实现:, 串赋值 StrAsign 串比较 StrCompare 求串长 StrLength 串连接 StrCat 求子串 SubString,而其他串操作(除了串清除操作 StrClear 和串销毁操作 StrDestroy外)均可以在这个最小操作子集上实现。,9,如果在程序设计语言中,串只是作为输入或者输出的常量出现,则只需要存储此串的串值,即字符序列即可。但是在多数非数值处理的程
5、序中,串也以变量的形式出现。串有 3 种机内表示方法。,定长顺序存储结构,10,堆分配存储结构,块链存储结构,串的定长顺序存储表示类似于线性表的顺序存储结构,用一组地址连续的存储单元存储串值的字符序列。在串的定长顺序存储结构中,按照予定义的大小,为每个定长的串变量分配一个固定长度的存储区,则可以用定长数组描述。,予定义大小 MAXSTRLEN 为串变量分配一个固定长度的存储区,11,4.2.1 定长顺序存储结构,1. 定长顺序存储表示,# define MAXLEN 40 /* 用户可在 40以内定义最大串长*/ typedef struct char chMAXLEN; int len; S
6、String ; /*为定长顺序存储结构类型名*/,12,(1) 串联接 StrCat(SString *s,SString t), 算法思想 假设 SString *s,SString t 。将串t连接在串s的后面,需要进行相应的 “串值复制” 操作即可,对超长部分实施 “截断” 操作。 基于串 s和串 t 长度的不同情况,新串(存于s中) 值的产生可能有如下 3 种情况:,13,2. 基本操作在定长顺序存储上的实现,s-len+t.lenMAXLEN 得到的 串是正确的结果。,s-lenlen+t.lenMAXLEN 将 t一部分截断,得到的 新串只包含 t 一个子串。,s-len=MAX
7、LEN 得到的 新串并非联接结果,而和 s相等。,14,s串长s-len,t串长t.len,新串s的串长s-len+t.len,MAXLEN,s,剩 余 空 间,15,s-len+t.lenMAXLEN,剩 余 空 间,s串长s-len,t串长t.len,s,新串s长,MAXLEN,t中被截去的字符序列,16,S-lenlen+t.lenMAXLEN,s串长s-len,t串长t.len,s,MAXLEN,新串s的长度,t串被全部截去,17,s-len=MAXLEN,Int strCat( SString *s, SString t) /* 用 s返回由 s和 t联接而成的新串。*/ / *如果
8、没有截断,则返回flag=1,否则返回 flag=0。*/,if (s-len+t.lenlen;ilen+t.len;+) s-chi= t.chi-s-len; s-len+=t.len; flag=1; if 结束, 算法编写,18,else if (s-lenlen; ichi= t.ch i-s-len; s-len=MAXLEN; flag=0; ,else flag=0; /* s-len= MAXLEN t被完全截断(仅取 S)*/ return(flag); ,19,(2) 求子串 SubString ( SString *Sub, SString S, pos, len )
9、, 算法思想 求子串的过程即为复制字符序列的过程,将串 S 中下标是pos 的字符开始、长度为 len 的字符序列复制到串 Sub 中。,求子串的操作不会出现截断的情况,但有可能产生用户给出的参数不符合操作的初始条件的情况,当参数非法时,返回 0。,20,SubString ( SString *Sub, SString S, int pos, int len) /* 用 Sub 返回串 S 的下标 pos 起长度为 len 的子串。*/,if ( pos s.len| len s.len-pos ) sub-len=0; return(0); , 算法编写,else for (i=0;ich
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 课件 章串
链接地址:https://www.31doc.com/p-2904182.html