数据结构 第六讲 串
51页1、数据结构数据结构 第六讲第六讲 串串 清华大学清华大学 自动化系自动化系 黄双喜黄双喜 博士博士 提纲提纲 1.1. 串的定义串的定义 2.2. 串的表示和实现串的表示和实现 3.3. 串的模式匹配算法串的模式匹配算法 1 1、串的定义、串的定义 串串(String)(String)是由零个或多个字符组成的有限序列。是由零个或多个字符组成的有限序列。 记为:记为:s=s=a a1 1a a2 2a an n (n0)(n0) 其中,其中,s s是串的名,用单引号括起来的字符序列是串的值。是串的名,用单引号括起来的字符序列是串的值。 a ai i(1in)(1in)可以是字母、数字或其它字符。可以是字母、数字或其它字符。 注:注:串值必须用一对单引号括起来,区别于变量名或数的常量。例串值必须用一对单引号括起来,区别于变量名或数的常量。例 如:如:1 1与与1 1 串(即字符串)是一种特殊的线性表,它的数据元素仅串(即字符串)是一种特殊的线性表,它的数据元素仅 由一个字符组成。由一个字符组成。 基本概念基本概念 串的长度串的长度串中字符的数目串中字符的数目n n。 空串空串(Null(N
2、ull string)string)长度为零的串长度为零的串。用用“”表示表示。 子串子串串中任意个串中任意个连续连续的字符组成的子序列的字符组成的子序列。 主串主串包含子串的串相应地称为主串包含子串的串相应地称为主串。 位置位置称字符在序列中的序号为该字符在串中的位称字符在序列中的序号为该字符在串中的位 置置。 子串在主串中的位置子串在主串中的位置则以子串的第一个字符在主串则以子串的第一个字符在主串 在的位置来表示在的位置来表示。 例如例如:a,b,c,d :a,b,c,d 四个字符串为四个字符串为 a=a=BEIBEI , b=, b=JINGJING c=c=BEIJINGBEIJING , d=, d=BEI JINGBEI JING 它们的长度分别为它们的长度分别为 :3,4,7,83,4,7,8 a a和和b b都是都是c c和和d d的的子串子串 a a在在c c和和d d中的位置是中的位置是1 1 b b在在c c中的位置是中的位置是4 4, ,而而b b在在d d中的位置是中的位置是5 5 注意注意: :单引号是为字符串区别于变量名而设单引号是为字符串区别于变量名而设
3、, ,它不是字它不是字 符串的内容符串的内容 如何表示单引号?如何表示单引号? 空格串和空格串和“空串空串”区别区别: : 空格串的长度是空格的个数空格串的长度是空格的个数。 “空串空串”长度为零长度为零。 串与线性表的区别:串与线性表的区别: 逻辑结构相似:区别仅在于串的数据对象约束为字符集。逻辑结构相似:区别仅在于串的数据对象约束为字符集。 表示与实现差别很大:线性表以表示与实现差别很大:线性表以“单个元素单个元素”作为操作对作为操作对 象;串以象;串以“串的整体串的整体”作为操作对象作为操作对象; ; 串相等串相等只有当两个串的长度相等,并且各个对应位只有当两个串的长度相等,并且各个对应位 置的字符都相等,称两串相等。置的字符都相等,称两串相等。 空格串空格串(blank string)(blank string)由一个或多个由一个或多个空格空格组成的串。组成的串。 串比较大小:串比较大小:比较第一个不相同字符的比较第一个不相同字符的ASCIIASCII码码 串的抽象数据类型定义串的抽象数据类型定义 ADT String ADT String 数据对象数据对象:D=aD=ai i
4、|a|ai iCharacterSetCharacterSet,i=1,2i=1,2n n,n0n0 数据关系数据关系:R= |a |ai i- -1 1,a ai iDD,i=i=2 2,3,3,n,n 基本操作基本操作:ADT StringADT String StrAssignStrAssign( m=Strlength(T); i=pos; While(i 复习:复习:C语言中常用的串运算语言中常用的串运算 Replace( (1)在执行下列语句后,s3的值是什么? strcpy(s3,s1); strcat(s3,“,“); strcat(s3,s2); (2)调用函数strcmp(s1,s2)的返回值是什么? (3)调用函数strcmp( 后,s3的值是“Stocktom,CA“ 在执行strcat(s3,“,“); 后,s3的值变成“Stocktom,Ca,“ 在执行完strcat(s3,s2);后,s3的值就成了“Stocktom,Ca,March 5,1999“ (2)函数strcmp(串1,串2)的功能是串比较,按串的大小进行比较, 返回大于0,等于0或小于0的值以
《数据结构 第六讲 串》由会员suns****4568分享,可在线阅读,更多相关《数据结构 第六讲 串》请在金锄头文库上搜索。
土地管理与地籍测量---第八章界址点测量
人机工程学案例分析(2)
工程安全培训_201303
第9章房地产投资决策分析
第2章房地产经纪制度
ACM程序设计-东北林业大学acm05
《亲爱的汉修先生》读书交流会
中原_深圳新世界尖岗山项目市场汇报_40P_2012年_别墅_项目分析_量价走势
五年级数学质量分析演示文稿
人工智能小镇-智慧小镇建设20180525
景观基本知识及发展历程
建设工程信息管理(2)
机电驱动技术第二章步进驱动技术
工程力学-第9章圆轴扭转时的应力变形分析与强度刚度设计
第一章第二节幼儿园文化环境建设的原则
第一章检测技术的基础知识
第一章__现代表面工程技术
第六章钢结构工程
第9节项目试运行管理
班主任工作经验交流课件(4)
2022-08-01 4页
2023-04-17 14页
2023-08-26 2页
2023-07-18 11页
2023-11-22 4页
2023-11-05 9页
2023-01-04 4页
2023-06-20 3页
2023-06-25 5页
2022-11-03 2页