North China Electric Power University 数据结构 Data Structure 华北电力大喾计算机斛学与工程柰 Dept of Computer Science& Engineering of North China Electric Power University
数据结构 North China Electric Power University Data Structure 华北电力大学计算机科学与工程系 Dept. of Computer Science&Engineering of North China Electric Power University
North China Electric Power University 第五章辛 ★串的基本撬念 ★串的基本操作 ★辛的存储结构 ★关于串的几个算法
第五章 串 ★ 串的基本概念 ★ 串的基本操作 ★ 串的存储结构 North China Electric Power University ★ 关于串的几个算法
North China Electric Power University ★辛的基本念 .串的定义 串是由n0个字符组成的有限序列,通常记为 1a2a3 n-12n 其中S表示串名(也称串变量),一对引号括起来的字 符序列称为串值,a可以是字母、数字或其他允许的字 符。n为串的长度,长度为0的串称为空串。 例如: S1= abc S2=′ FORTRAN77 S3 ①(空串 S4= 由4个空格组成的空格串 华电计算机系
★串的基本概念 North China Electric Power University 华电计算机系 例如: S1= ´ abc ´ S2= ´ FORTRAN_77 ´ S3= ´´ = (空串) S4= ´ ´ 由4个空格组成的空格串 串是由n0个字符组成的有限序列, 通常记为 S = ´ a1 a2 a3 … an-1 an ´ 其中, S表示串名(也称串变量), 一对引号括起来的字 符序列称为串值, ai可以是字母、数字或其他允许的字 符。n 为串的长度, 长度为0的串称为空串。 一.串的定义
North China Electric Power University 说明 1.串值须用一对引号括起来,但引号不属于串值。 2要区分空串与由空格字符组成的串的不同。 String= String 华电计算机系
North China Electric Power University 华电计算机系 1. 串值须用一对引号括起来，但引号不属于串值。 说明 2. 要区分空串与由空格字符组成的串的不同。 String = ´ String ´
North China Electric Power University 几个名词概念 1.子串:串中若千个连续的字符组成的子序列 例如:S=' Beijing&Sha anghaI T=jing 2主串:包含子串的串 3.位置:(1).单个字符在主串中的位置被定义为主串 中首次出现的该子串的第一个字符在主 串中的位置。 (2)子串在主串中的位置被定义为该字符在 串中的序号。 例如:S=′ Beijing& Nanjing& Shanghai 位置为4 华电计算机系
North China Electric Power University 华电计算机系 1. 子串：串中若干个连续的字符组成的子序列。 例如: S= ´ Beijing&Shanghai ´ T= ´ jing ´ 2. 主串: 包含子串的串。 3. 位置： (2).子串在主串中的位置被定义为该 字符在 串中的序号。 例如: S= ´ Beijing&Nanjing&Shanghai ´ T= ´ jing ´ 位置为4 二. 几个名词概念 (1). 单个字符在主串中的位置被定义为主串 中首次出现的该子串的第一个字符在主 串中的位置
North China Electric Power University 4.两个字符分必要条件为两个字符串的长度相等, 并且对应位置上的字符相同。 abcd≠'bacd abed abcd 华电计算机系
North China Electric Power University 华电计算机系 的充分必要条件为两个字符串的长度相等， 并且对应位置上的字符相同。 4. 两个字符串相等 ´ abcd ´ ´ bacd ´ ´ abcd ´ = ´ abcd ´
North China Electric Power University 62串的基本操作 C函数 1给串变量赋值 ASSIGN(S1,S2) strcpy(S2, S1) 2判断两个串是否相等 EQUAL(S1,S2) strcmp(S1,S2) 3两个字符串连接 CONCAT(S1,S2) trcat(s,2) 4求字符串的长度LEN(S) strlen(s) 5求子串 SUBSTR(Sik) 6求子串在主串中的位置 INDEX(S1S2) strstr(S1,S2) 7串的替换 REPLACE(S,S1,S2) 8串的复制COPY(S12) strcpy(s2, s1) 9串的插入 INSERTS(Sl,i,S2) 华电计算机系
North China Electric Power University 华电计算机系 6.2 串的基本操作 1.给串变量赋值 ASSIGN(S1,S2) strcpy(S2,S1) 2.判断两个串是否相等 EQUAL(S1,S2) strcmp(S1,S2) 3.两个字符串连接 CONCAT(S1,S2) strcat(S1,S2) 4.求字符串的长度 LEN(S) strlen(S) 5.求子串 SUBSTR(S,i,k) 6.求子串在主串中的位置 INDEX(S1,S2) strstr(S1,S2) 7.串的替换 REPLACE(S,S1,S2) 8.串的复制 COPY(S1,S2) strcpy(S2,S1) 9.串的插入 INSERTS(S1,i,S2) C函数
North China Electric Power University 6.3串的存储结构 串的顺序存储结构 1.非紧缩格式(设每个字有4个字节) 例如:S=′ DATA STRUCTURE 2紧缩格式 3.单字节方式 华电计算机系
North China Electric Power University 华电计算机系 1. 非紧缩格式(设每个字有4个字节) 例如: S = ´ DATA STRUCTURE ´ D A S T R U C T A T U R E @ D A T A S T R U C T U R E@ 2. 紧缩格式 3. 单字节方式 6.3 串的存储结构 一.串的顺序存储结构 D A T A S T R U C T U R E @
North China Electric Power University 串的链式存储结构 【说明 所谓链结点大小是指每个链结点的数据域中存放 的字符的个数。 ATA■STRU→ RE 结点大小为4的链表 E 结点大小为1的链表
North China Electric Power University S D A T … … E ^ 说 明： 所谓链结点大小是指每个链结点的数据域中存放 的字符的个数。 DATA STRU … … RE@@ S ^ 二.串的链式存储结构 结点大小为4的链表 结点大小为1的链表
North China Electric Power University I 64串的几个算法 串的定义 Type string=record curlen: integer; ch: arrayll.maxlen of char; end: 二串的连接 假设rs,都是上面定义的 string型变量,且r是与连接后 得到的串,则连接运算 conca(;s,t)是将s与t的串值分别传送 到r相应的位置上
North China Electric Power University 6.4 串的几个算法 一.串的定义 Type string=record curlen:integer; ch:array[1..maxlen] of char; end; 二.串的连接 假设r,s,t都是上面定义的string型变量，且r是s与t连接后 得到的串，则连接运算concat(r,s,t)是将s与t的串值分别传送 到r相应的位置上