![数据结构讲义清华严版第4章串修改_第1页](http://file4.renrendoc.com/view/d6aa8014d27831295d4afb4abeaa79e8/d6aa8014d27831295d4afb4abeaa79e81.gif)
![数据结构讲义清华严版第4章串修改_第2页](http://file4.renrendoc.com/view/d6aa8014d27831295d4afb4abeaa79e8/d6aa8014d27831295d4afb4abeaa79e82.gif)
![数据结构讲义清华严版第4章串修改_第3页](http://file4.renrendoc.com/view/d6aa8014d27831295d4afb4abeaa79e8/d6aa8014d27831295d4afb4abeaa79e83.gif)
![数据结构讲义清华严版第4章串修改_第4页](http://file4.renrendoc.com/view/d6aa8014d27831295d4afb4abeaa79e8/d6aa8014d27831295d4afb4abeaa79e84.gif)
![数据结构讲义清华严版第4章串修改_第5页](http://file4.renrendoc.com/view/d6aa8014d27831295d4afb4abeaa79e8/d6aa8014d27831295d4afb4abeaa79e85.gif)
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、DATA1065865ABCDEFG数据结构第4章 串 1. 熟悉串的七种基本操作的定义,并能利用这些基本操作来实现串的其它各种操作的方法。 2. 熟练掌握在串的定长顺序存储结构上实现串的各种操作的方法。 3. 掌握串的堆存储结构以及在其上实现串操作的基本方法。 4. 了解串操作的应用方法和特点。学习提要 4.1 串的定义和基本运算 串是字符串的简称。它是一种在数据元素的组成上具有一定约束条件的线性表,即要求组成线性表的所有数据元素都是字符。串:由零个或多个字符组成的有限序列。人们经常又这样定义串:串:是一个有穷字符序列。 串一般记作: s= a1a2.an (n0) 其中,s是串的名称,用单
2、引号()括起的字符序列是串的值;ai可以是字母、数字或其他字符;串中字符的数目n被称作串的长度。当n=0时,串中没有任何字符,其串的长度为0,通常被称为空串。 s1= “” s2= “ ” s1中没有字符,是一个空串;而s2中有两个空格字符,它的长度等于2,它是由空格字符组成的串,一般称此为空格串。 概念: 子串、主串:串中任意连续的字符组成的子序列被称为该串的子串。包含子串的串又被称为该子串的主串。 例如,有下列四个串a,b,c,d: a= “ e to Beijing” b= “ e” c= “Bei” d= “ e to” 子串的位置:子串在主串中第一次出现的第一个字符的位置。 两个串相
3、等:两个串的长度相等,并且各个对应的字符也都相同。 例如,有下列四个串a,b,c,d: a= “program” b= “Program” c= “pro” d= “program ” 串的基本操作:(1) 创建串 StringAssign (s,string_constant)(2)判断串是否为空 StringEmpty(s) (3)计算串长度 Length(s) (4)串连接 Concat(s1,s2) (5)求子串 SubStr(s1,s2start,len)(6)串的定位 Index(s1,s2)4.2 串的存储结构 1. 顺序存储结构 串的顺序存储结构与线性表的顺序存储类似,用一组连
4、续的存储单元依次存储串中的字符序列。在C语言中,有两种实现方式: 第一种是事先定义字符串的最大长度,字符串存储在一个定长的存储区中。类型定义如下所示: #define MAX_STRING 255 /0号单元存放串的长度,字符从1号单元开始存放 type unsigned char StringMAX_STRING; 第二种是在程序执行过程中,利用标准函数malloc和free动态地分配或释放存储字符串的存储单元,并以一个特殊的字符作为字符串的结束标志,它的好处在于:可以根据具体情况,灵活地申请适当数目的存储空间,从而提高存储资源的利用率。类型定义如下所示:typedef structchar
5、 *str; int length;STRING; 不同的定义形式,算法中的处理也略有不同。下面我们将给出在第二种顺序存储方式下串的几个基本操作的算法。(1) 串的赋值 int StringAssign(STRING*s, char *string_constant) if (s-str) free(s-str); /若s已经存在,将它占据的空间释放掉 for (len=0,ch=string_constant;ch;len+,ch+); /求string_constant串的长度 if (!len) s-str=(char*)malloc(sizeof(char); s-str0=0; s-
6、length=0; /空串 else s-str=(char*)malloc(len+1)*sizeof(char); /分配空间 if (!s-str) return ERROR; s-str0.len=string_constant0.len; /对应的字符赋值 s-length=len; /赋予字符串长度 return OK;(2)判断串是否为空 int StringEmpty(STRING s) if (!s.length) return TRUE; else return FALSE;(3)求串的长度 int Length(STRING s) return s.length;(4)串
7、连接 int Concat(STRING *s1,STRING s2) STRING s; StringAssign(&s, s1-str); /将s1原来的内容保留在s中 len=Length(s1)+Length(s2); /计算s1和s2的长度之和 free(s1-str); /释放s1原来占据的空间 s1-str=(char*)malloc(len+1)*sizeof(char); /重新为s1分配空间 if (!s1) return ERROR; else /连接两个串的内容 s1-str0.Length(s)-1=s.str0.Length(s)-1); s1-strLength(
8、s).len+1=s2.str0.Length(s2); s1-length=len; free(s-str); /释放为临时串s分配的空间 return OK; (5)求子串 int SubStr(STRING *s1, STRING s2,int start,int len) len2=Length(s2); /计算s2的长度 if (startlen2|len2len2-start+1) /判断start和len的合理性 s1-str=(char*)malloc(sizoef(char); s1-str0=0; s1-length=0;return ERROR; s1-str=(char
9、*)malloc(len+1)*sizeof(char); if (!s1.str) return ERROR; s1-str0.len-1=s2.strstart-1.start+len -2; s1-strlen=0; s1-length=len; return OK;(6)串的定位int Index(STRING s1,STRING s2) len1=Length(s1); len2=Length(s2); /计算s1和s2的长度 i=0; j=0; /设置两个扫描指针 while (ilen1&jlen2) if (s1.stri=s2.strj) i+; j+; else i=i-j
10、+1; j=0; /对应字符不相等时,重新比较 if (j= =len2) return i-len2+1; else return 0;与教材P79有何不同?实质上是不是一样?教材上是i=i-j+2;j=1;a b a b c a b c a c b a ba b c a ci=j=i=0; j=0; /设置两个扫描指针 while (ilen1&jlen2) if (s1.stri=s2.strj) i+; j+; else i=i-j+1; j=0; /对应字符不相等时,重新比较 if (j= =len2) return i-len2+1; else return 0;a b a b c
11、 a b c a c b a ba b c a ci=0j=0i=0; j=0; /设置两个扫描指针 while (ilen1&jlen2) if (s1.stri=s2.strj) i+; j+; else i=i-j+1; j=0; /对应字符不相等时,重新比较 if (j= =len2) return i-len2+1; else return 0;a b a b c a b c a c b a ba b c a ci=1j=1i=0; j=0; /设置两个扫描指针 while (ilen1&jlen2) if (s1.stri=s2.strj) i+; j+; else i=i-j+1
12、; j=0; /对应字符不相等时,重新比较 if (j= =len2) return i-len2+1; else return 0;a b a b c a b c a c b a ba b c a ci=2j=2i=0; j=0; /设置两个扫描指针 while (ilen1&jlen2) if (s1.stri=s2.strj) i+; j+; else i=i-j+1; j=0; /对应字符不相等时,重新比较 if (j= =len2) return i-len2+1; else return 0;a b a b c a b c a c b a ba b c a ci=1j=0i=0;
13、j=0; /设置两个扫描指针 while (ilen1&jlen2) if (s1.stri=s2.strj) i+; j+; else i=i-j+1; j=0; /对应字符不相等时,重新比较 if (j= =len2) return i-len2+1; else return 0;a b a b c a b c a c b a ba b c a ci=2j=0i=0; j=0; /设置两个扫描指针 while (ilen1&jlen2) if (s1.stri=s2.strj) i+; j+; else i=i-j+1; j=0; /对应字符不相等时,重新比较 if (j= =len2)
14、return i-len2+1; else return 0;a b a b c a b c a c b a ba b c a ci=3j=1i=0; j=0; /设置两个扫描指针 while (ilen1&jlen2) if (s1.stri=s2.strj) i+; j+; else i=i-j+1; j=0; /对应字符不相等时,重新比较 if (j= =len2) return i-len2+1; else return 0;a b a b c a b c a c b a ba b c a ci=4j=2i=0; j=0; /设置两个扫描指针 while (ilen1&jlen2) i
15、f (s1.stri=s2.strj) i+; j+; else i=i-j+1; j=0; /对应字符不相等时,重新比较 if (j= =len2) return i-len2+1; else return 0;a b a b c a b c a c b a ba b c a ci=5j=3i=0; j=0; /设置两个扫描指针 while (ilen1&jlen2) if (s1.stri=s2.strj) i+; j+; else i=i-j+1; j=0; /对应字符不相等时,重新比较 if (j= =len2) return i-len2+1; else return 0;a b a
16、 b c a b c a c b a ba b c a ci=6j=4i=0; j=0; /设置两个扫描指针 while (ilen1&jlen2) if (s1.stri=s2.strj) i+; j+; else i=i-j+1; j=0; /对应字符不相等时,重新比较 if (j= =len2) return i-len2+1; else return 0;a b a b c a b c a c b a ba b c a ci=3j=0i=0; j=0; /设置两个扫描指针 while (ilen1&jlen2) if (s1.stri=s2.strj) i+; j+; else i=i
17、-j+1; j=0; /对应字符不相等时,重新比较 if (j= =len2) return i-len2+1; else return 0;a b a b c a b c a c b a ba b c a ci=4j=0i=0; j=0; /设置两个扫描指针 while (ilen1&jlen2) if (s1.stri=s2.strj) i+; j+; else i=i-j+1; j=0; /对应字符不相等时,重新比较 if (j= =len2) return i-len2+1; else return 0;a b a b c a b c a c b a ba b c a ci=5j=0i
18、=0; j=0; /设置两个扫描指针 while (ilen1&jlen2) if (s1.stri=s2.strj) i+; j+; else i=i-j+1; j=0; /对应字符不相等时,重新比较 if (j= =len2) return i-len2+1; else return 0;a b a b c a b c a c b a ba b c a ci=6j=1i=0; j=0; /设置两个扫描指针 while (ilen1&jlen2) if (s1.stri=s2.strj) i+; j+; else i=i-j+1; j=0; /对应字符不相等时,重新比较 if (j= =le
19、n2) return i-len2+1; else return 0;a b a b c a b c a c b a ba b c a ci=7j=2i=0; j=0; /设置两个扫描指针 while (ilen1&jlen2) if (s1.stri=s2.strj) i+; j+; else i=i-j+1; j=0; /对应字符不相等时,重新比较 if (j= =len2) return i-len2+1; else return 0;a b a b c a b c a c b a ba b c a ci=8j=3i=0; j=0; /设置两个扫描指针 while (ilen1&jlen2) if (s1.stri=s2.strj) i+; j+; else i=i-j+1; j=0; /对应字符不相等时,重新比较 if (j= =len2) return i-len2+1; else return 0;a b a b c a b c a c b a ba b c a ci=9j=4i=0; j=0; /设置两个扫描指针 while (ilen1&jlen2) if (s1.stri=s2.strj) i+; j+; else i=i-j+1; j=0; /对应字符不相等时,重新比较 if (j= =len2) return i-len2+1; else ret
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2024年《建筑施工技术》7月期末试题及答案
- 2024-2025学年高中化学下学期《乙烯》教学设计
- 4 地球-我们的家园(教学设计)2023-2024学年统编版道德与法治六年级下册
- Unit4 Adversity and Courage Reading and Thinking A Successful Failure教学设计-2023-2024学年高中英语人教版(2019)选择性必修第三册
- 2023年广西投资集团有限公司校园招聘考试题库及答案解析
- 隧洞施工中不稳定围岩的分析及处理措施
- 专题1 两直线的位置关系(知识梳理与考点分类讲解)-2023-2024学年七年级数学下册专项突破讲与练(北师大版)
- 2023年合心人才发展集团幼儿园教师招聘考试真题
- 珠海市委政法委选调公务员笔试真题2023
- 第八章施工质量管理体系及措施
- 材料设备采购供应方案
- 北京版小学数学二年级上册全册教案
- PISA-阅读样题及点评
- 凝聚最大价值戴比尔斯——变卖钻石为卖爱情
- 昆明市小江寻甸县功山镇段治理工程环境影响报告书
- 你有多少种画平行线的方法---课件
- 人教版英语九年级Unit-1-全单元ppt课件(126页)
- 招聘求职简历制作表格模板可编辑下载 精品简历模板 空白标准表格03
- (精心整理)深圳小学英语语法汇总
- 部编二年级语文上册单元教材分析
- 部编版道德与法治四年级下册---全册教案(表格版)
评论
0/150
提交评论