华中师范大学计算机科学系：《数据结构》第5章 串和数组

第5章串与数组

第5章 串与数组

【课就者】 串就是线性表"的结论是否正确? 从教据结袍的观点来说,串是一特殊的纜性 袁沮就数据类型而言,串不是錢性歌。 为什么顺序表以及其它线性结构的顺序存储结构都可 以用”一维数组来描述? 因为在高级编程语言中实现的一雄教组正是用的这种 顺序存储的映象方式

【课前思考】 为什么顺序表以及其它线性结构的顺序存储结构都可 以用"一维数组"来描述？ 因为在高级编程语言中实现的一维数组正是用的这种 顺序存储的映象方式。 从数据结构的观点来说，串是一种特殊的线性 表;但就数据类型而言，串不是线性表。 "串就是线性表"的结论是否正确？

5串美到的定 5.9串的表录和现 53串的式匹已算法 54串操作应举例 55组的定 56数组顺序存储的表录和魂 57矩除的压缩高储

5.1 串类型的定义 5.2 串的表示和实现 5.3 串的模式匹配算法 5.4 串操作应用举例 5.5 数组的定义 5.6 数组顺序存储的表示和实现 5.7 矩阵的压缩存储

【学习标 1.理解串类型定义中各基本操作的特点,并能正确利用 它们进行串的其它操作。 理解串类型的各种存储表示方法。 理解串匹配的各种算法。 2.理解数组类型的特点及其在高级编程语言中的存储表 示和实现方法,并掌握数组在以行为主的存储表示中 的地址计算方法; 3.掌握特殊矩阵的存储压缩表示方法; 4.理解稀疏矩阵的两类存储压缩方法的特点及其适用范 围,掌握以三元组表示稀疏矩阵时进行矩阵运算所采 用的处理方法

【学习目标】 1.理解串类型定义中各基本操作的特点，并能正确利用 它们进行串的其它操作。 理解串类型的各种存储表示方法。 理解串匹配的各种算法。 2.理解数组类型的特点及其在高级编程语言中的存储表 示和实现方法，并掌握数组在以行为主的存储表示中 的地址计算方法； 3.掌握特殊矩阵的存储压缩表示方法； 4.理解稀疏矩阵的两类存储压缩方法的特点及其适用范 围,掌握以三元组表示稀疏矩阵时进行矩阵运算所采 用的处理方法；

【量点和点】 1.重点 了解串类型定义以及串的实现方法一串的匹配, 学会利用这些基本操作来实现串的其它操作; 掌握随机稀疏矩阵的压缩存储表示方法和运算实现 【知识赢】 串、串的匹配、数组、特殊矩阵、稀疏矩阵、三元组、 十字链表。 课后练习题:51,52,53,54,56,511512

【重点和难点】 1.重点 了解串类型定义以及串的实现方法—串的匹配， 学会利用这些基本操作来实现串的其它操作； 掌握随机稀疏矩阵的压缩存储表示方法和运算实现 串、串的匹配、数组、特殊矩阵、稀疏矩阵、三元组、 十字链表。 【知识点】 课后练习题：5.1，5.2，5.3，5.4，5.6，5.11，5.12

5。串的发义和作 串( string):由0个或多个字符组成的有限序列 出称中他日·c=699 0 串相等的条件:当两个串的长度相等且各个对应位置的字符 都相等时才相等。 注意:(1)串值必须用一对单引号括起来 (2)串值大小是按词典次序进行比较的 StrCompare data’,’stru)0 StrCompare ' cat’,’case)>0 显然,只有在两个串的长度相等且每个字符一一对等的情况 下称两个串相等。 吧名识。 串相等:串长度相等,且对应位置上字符相等

记为： s = “a0 a1 ….. an-1” (n≥0 ) 串名 串值(用双引号括起来） 串中字符个数(n≥0),n=0时称为空串 。 由一个或多个空格符组成的串。 串s中任意个连续的字符序列叫s的子串; S叫主串。 子串的第一个字符的序号。 字符在串中的序号。 串长度相等，且对应位置上字符相等。 串即字符串，是由零个或多个字符组成的有限序列，是数据元素 为单个字符的特殊线性表。 若干术语： 串长： 空白串： 子串： 子串位置： 字符位置： 串相等： 隐含结束符‘/0’ ， 即ASCII码NUL 5.1 串的定义和操作 • 串（string）：由0个或多个字符组成的有限序列， 也称字符串。记为：s=“a0 a1 a2……an-1 ” (n≥0), 其 中 s 是 串 的 名 ， a0 a1 a2……an-1 是串的值 ， ai (0≤i≤n-1)可以是字母、数字或其它字符。 • 串长度：串中字符的数目n。 • 空串：不含任何字符的串，串长度=0 • 空格串：仅由一个或多个空格组成的串 • 子串：由串中任意个连续的字符组成的子序列 • 主串：包含子串的串。 • 串相等的条件：当两个串的长度相等且各个对应位置的字符 都相等时才相等。 • 注意：(1) 串值必须用一对单引号括起来 • (2) 串值大小是按词典次序进行比较的 • StrCompare(‘data’ , ’Stru’)0 显然，只有在两个串的长度相等且每个字符一一对等的情况 下称两个串相等

练1:串是由0个或多个字符组成的序列,一般记 为S=a12…an 练2:现有以下4个字符串: a=bEr b=JNG C=BEING d=BEIJNG 问:①他们各自的长度?a=3,b=4,c=7,d=8 ②a是哪个串的子串?在主串中的位置是多少? a是c和d的子串,在c和d中的位置都是1 练3:空串和空白串有无区别? 答:有区别。空串(Nu! String)是指长度为零的串;而空 白串 Blank String)是指包含一个或多个空白字符 ′(空格键)的字符串 串的逻辑结构和线性表的区别: 1.串的数据对象约束为字符集 2.线性表的基本操作大多以“单个元素”为操作对象,而串的 基本操作通常以“串的整体”作为操作对象

练1：串是由 字符组成的序列，一般记 为 。 练2：现有以下4个字符串： a =‘BEI’ b =‘JING’ c = ‘BEIJING’ d = ‘BEI JING’ 问：① 他们各自的长度？ ② a是哪个串的子串？在主串中的位置是多少？ a =3，b =4，c = 7，d=8 a是c和d的子串，在c和d中的位置都是1 练3：空串和空白串有无区别？ 答：有区别。空串(Null String)是指长度为零的串；而空 白串(Blank String),是指包含一个或多个空白字符 ‘ ’(空格键)的字符串。 0个或多个 S=’a1 a2……an ’ 1.串的数据对象约束为字符集。 2. 线性表的基本操作大多以“单个元素”为操作对象，而串的 基本操作通常以“串的整体”作为操作对象。 串的逻辑结构和线性表的区别:

补充:0语言中常用的串运算 注:用C处理字符串时,要调用标准库函数# nclude 串比较, int strcmp( charal, char s2);/ StrCompare((S,T 求串长, int strlen( char s /Str Length(S) 串连接, char strcat(char*to, char *from)/ Concat(&TS1,S2) 子串定位, char strchr(char*s,char* //Index(s, T, pos) gets(char*s)输入一个串; puts(char*s)输出一个串 stra(char*s,char*s2)串联接函数; strcpy(char*sl,char*2)串复制函数; strcmp(char*sl,char*s2)串比较函数; strlen(char*)求串长函数; ”表示空串,空串的长度为零

补充：C语言中常用的串运算 串比较， int strcmp(chars1,char s2); //StrCompare(S,T) 求串长， int strlen(char s); //StrLength(S) 串连接， char strcat(char *to,char *from) //Concat(&T,S1,S2) 子串定位，char strchr(char *s, char *c); //Index(S,T,pos) …… 注：用C处理字符串时，要调用标准库函数#include • gets( char *s ) 输入一个串； • puts( char *s ) 输出一个串； •strcat(char *s1, char *s2 ) 串联接函数； •strcpy( char *s1, char *s2 ) 串复制函数； •strcmp( char *s1, char *s2 ) 串比较函数； •strlen( char *s ) 求串长函数；  表示空串，空串的长度为零

串的喜事操作 StrEmpty s) 例如: StrCompare('data', state-0 初始条件:串S存在 StrCompare('cat, 'case PO 操作结果:着S为空串则返回ue否则返回ase StrCopy(&T, s) 初始条件:串S存在。 StrCompare s,T 操作结果:由串S复制得串T。 初始条件:串S和T有在 DestroyString(&s) 操作结果:若s>T,则返回值>0; 初始条件:串$存在。 若S=T,则返回值=0; 操作结果:串S被销毁。 若s<T,则返回值<0 StrAssign(&T, chars) StrEngth(s) 初始条件:cha是字符串常量。初始条件:串S存在 操作结果:把 chars为的值操作结果:返回S的元素个数称为串的长度 Concat(&T, S1, S2) 初始条件:串S1和S2存在。 例如: Concat(T"man","kind") 操作结果:用返回由1和联接而成的新串 求得T=" mankind SubString( &Sub, S, pos, len) 初始条件:串S存在,1 spossstrLength(S)且0 slensstrLength(S}po+1。 操作结果:用Sub返回串S的第pos个字符起长度为ln的子串

StrAssign (&T, chars) 初始条件：chars是字符串常量。 操作结果：把chars赋为T的值。 StrCopy (&T, S) 初始条件：串S 存在。 操作结果：由串S复制得串T。 DestroyString (&S) 初始条件：串S存在。 操作结果：串S被销毁。 StrEmpty (S) 初始条件：串S存在。 操作结果：若S为空串,则返回true,否则返回false. 串的基本操作 StrCompare (S, T) 初始条件：串S 和 T 存在。 操作结果：若S  T，则返回值 0; 若S = T，则返回值= 0; 若S  T，则返回值 0. StrLength (S) 初始条件：串S存在。 操作结果：返回S的元素个数,称为串的长度. Concat (&T, S1, S2) 初始条件：串S1和S2存在。 操作结果：用T返回由S1和S2联接而成的新串。 SubString (&Sub, S, pos, len) 初始条件： 操作结果：用Sub 返回串 S 的第 pos 个字符起长度为len 的子串。 串 S 存在，1≤pos≤StrLength(S) 且 0≤len≤StrLength(S)-pos+1。 例如：Concate( T, man , kind), 求得 T = mankind 例如: StrCompare(data , state)0

子串为“串”中的一个字符子序列 例如: Sub string(sub," commander",4,3)求得sub="man"; SubString( sub, "commander",1, 9) 34 sub="commander SubString(sub," commander",9,1)求得sub="r" SubString(sub, ' commander, 4, 7) SubString(sub, ' beijing, 7, 2)=? sub=? sub=? 起始位置和子串长度之间存在约束关系 Sub String(" student",50)=" 长度为0的子串为“合法”串 Index(s, T, pos) 初始条件:串S和T存在,T是非空串,1 spossStrLength(S) 操作结果:若主串S中存在和串T值相同的子串,则返回它在主串S中第pos个 字符之后第一次出现的位置;否则函数值为0。 “子串在主串中的位置”意指子串中的第一个字符在主串中的位序。 假设S=" abcaabcaaabc",T="bca" Index (s, T, 1)=2; Index(s, t,3)=6 Index(s, t,8)=0;

例如：SubString( sub, commander , 4, 3 ) 子串为“串”中的一个字符子序列 求得 sub = man  ; SubString( sub, commander  , 1, 9 ) SubString( sub, commander , 9, 1 ) 求得 sub = r  求得 sub = commander  SubString( sub, commander, 4, 7 ) sub = ? SubString( sub, beijing, 7, 2 ) = ? sub = ? 起始位置和子串长度之间存在约束关系 SubString( student, 5, 0 ) =  长度为 0 的子串为“合法”串 Index( S, T, pos ) 初始条件：串S和T存在，T是非空串，1≤pos≤StrLength(S)。 操作结果：若主串S 中存在和串T 值相同的子串, 则返回它在主串S 中第pos个 字符之后第一次出现的位置; 否则函数值为0。 假设 S = abcaabcaaabc , T = bca  Index(S, T, 1) = 2; Index(S, T, 3) = 6; Index(S, T, 8) = 0; “子串在主串中的位置”意指子串中的第一个字符在主串中的位序