• / 21
  • 下载费用:10 金币  

第5章 串.ppt

关 键 词:
第5章 串.ppt
资源描述:
第5章 串,数据结构(C描述),目录,5.1串的定义及运算,5.2 串的存储结构,5.3 串的运算的实现,结束放演,,5.1串的定义及运算,5.1.1 基本概念,1.串的定义串( string) 是由零个或多个字符组成的有限序列,记作s=“a1a2…an”,其中s为串的名字,用成对的双引号括起来的字符序列为串的值,但两边的双引号不算串值,不包含在串中。ai(1≤i≤n)可以是字母、数字或其它字符。n为串中字符的个数,称为串的长度。,2.空串不含任何字符的串称为空串,它的长度n=0,记为s=“”。,,3.空格串含有一个或多个空格的串,称为空格串,它的长度是空格的个数。若串中含有空格,在计算串长时,空格应计入串的长度中,如:s=“I’m a student”的长度为13。,4.子串、主串子串是指串中任意个连续字符组成的子序列,而包含该子串的串称为主串。例如,串s1=“abcdefg”,s2=“fabcdefghxyz”,则s1为s2的子串,s2相对于s1为主串。,另外,空串是任意串的子串,任意串是自身的子串。除串本身以外的子串都称为真子串。,,5.1.2 串的运算,为描述方便,假定用大写字母表示串名,小写字母表示组成串的字符。,1. 联接 concat(&S,T) 表示将S串和T串联接起来,使T串接入S串的后面。,2. 求串长度 length (T)求T串的长度。 3. 串比较大小 strcmp(S,T) 比较S串和T串的大小,若ST,函数值为正。,,4.求子串 substr(S,i,j,&T) 表示截取S串中从第i个字符开始连续j个字符,作为S的一个子串,存入T串。,5. 串插入 insert (&S,i,T)在S串的第i个位置扦入T串。,6. 串删除 delete(&S,i,j)删除串S中从第i个字符开始连续j个字符。,,5.2 串的存储结构,5.2.1 顺序存储串的顺序存储结构,也称为顺序串,与第三章介绍的顺序表类似,用一组地址连续的存储单元存储串值。不同的计算机,存储器编址的方式不同,主要有字节编址和字编址。一个字符只占1个字节,一个字(即一个存储单元)占多个字节,因此结合具体计算机顺序存储结构有三种不同的实现方式:,1.串的紧缩存储 根据各机器字的长度,尽可能将多个字符存放在一个字中。假设一个字(即一个存储单元)可存储4个字符,则紧缩存储具体形式见下图。,2.串的非紧缩存储 一个存储单元中只存储一个字符,即使一个单元可以存放4个字符。具体形式见图4-1,设串S=“How do you do”。,可见,紧缩存储能够节省大量存储单元,但对串的单个字符操作(插入或删除)很不方便,要花费较多的处理时间。,,,,可见非紧缩存储与紧缩存储的特点刚好相反,操作方便,但将占用较多的内存单元。,3.串的字节存储(单字节存储方式) 前两种存储方法都是以字编址形式进行的,而有的计算机存取单位是字节。而一个字符恰占一个字节。具体形式见图4-3。,,,显然,第三种方式结合前两种的优点,比较适用。,5.2.2 链式存储结点有两个域:data域存放字符,next域存放指向下一个结点的指针。另外涉及到结点的大小( 即结点的data域可存放字符的个数),1.结点大小为1的链式存储 和前面介绍到的单链表一样,每个结点为一个字符,链表也可以带头结点。,S=“abcdef”的存储结构具体形式见图。,,2.结点大小为K的链式存储,和紧缩存储类似,假设一个字中可以存储K个字符,则一个结点有K个数据域和一个 指针域,若一个结点中数据域少于K个,用ø代替。例如串S=“abcdef”的存储结构具体形式见图5-5。通常K值取4的时候较为常见。,,可见,结点大小为1的链表形式简单,便于进行串的插入和删除操作。以上讨论的都是结点大小都是定长的链表,除了这种定长结点链表外,还可采用结点大小不固定的变长结点链表,实际上串的链式存储不如顺序存储结构使用得广泛。,,,5.3 串的基本运算 顺序串的数据类型描述如下: const int maxlen=100;typedef struct str{ char ch[maxlen]; int len; } string ;,(1)串的初始化 void clearstring(string *s) { for(int i=0;i=maxlen-1)cout“t串超长“endl;else{,while( (*s1).ch[j]!=‘\0’)(* t).ch[i++]=(*s1).ch[j++]; while((*s2).ch[k]!=‘\0’)(* t).ch[i++]=(*s2).ch[k++]; (*t).ch[i]=‘\0’; //给新生成的t串加结束标志
展开阅读全文
  微传网所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
0条评论

还可以输入200字符

暂无评论,赶快抢占沙发吧。

关于本文
本文标题:第5章 串.ppt
链接地址:https://www.weizhuannet.com/p-10036096.html
微传网是一个办公文档、学习资料下载的在线文档分享平台!

微传网博客

网站资源均来自网络,如有侵权,请联系客服删除!

 网站客服QQ:80879498  会员QQ群:727456886

copyright@ 2018-2028 微传网络工作室版权所有

     经营许可证编号:冀ICP备18006529号-1 ,公安局备案号:13028102000124

收起
展开