数据结构04串与数组ppt课件

1、数据结构数据结构 第四章 串和数组数组 第四章 串和数组数组主要内容主要内容串的相关知识串的相关知识1数组的定义数组的定义2特殊矩阵的数组存储特殊矩阵的数组存储3数组和串的运用数组和串的运用4教学要求教学要求教学重点教学难点目的要求1了解串的根本操作的定义；2. 熟练掌握在串的顺序存储构造上实现串的各种操作的方法3.掌握朴素的方式匹配算法。4.了解数组的两种存储表示方法，并掌握数组的地址计算方法；5.了解稀疏矩阵的特点和紧缩存储方法1.朴素的方式匹配运算2.掌握数组的存储方式，顺序存储的地址计算公式1.串的匹配运算算法2.稀疏矩阵紧缩存储表示下实现的算法4.1串串4.1.1 4.1.1 串的定

2、义串的定义串的值串的值 串的长度串的长度 串的名串的名 字母、数字或其他字符字母、数字或其他字符 必需有！必需有！ 但不属于串！但不属于串！ 作用：防止字符串与变量名或数的常量混淆。作用：防止字符串与变量名或数的常量混淆。 例：例：x = 123 x = 123 test =test 4.1.2 串间关系串间关系2. 子串关系子串关系1. 相等关系相等关系准确相等关系 左对齐相等关系 两串有一样的长度，且自左至右逐对对应字符相等时两串才为相等 不要求两串有一样的长度自最左的第1个字符开场逐个对应字符比较当不等时，如何判别大小关系包含关系例：例：S=NanJing S1=Nan Jing S3=

3、“NanJing S S1 S S2 例：例：S7 =“I am a student now.，S8 =“student，S9 =“student.S7主串主串S8S7子串子串S9非非S7子串子串空串是恣意串的子串，恣意串是其本身的子串空串是恣意串的子串，恣意串是其本身的子串在在S S中的位置：中的位置：8 8 非串非串 S 中的延续字符所组成中的延续字符所组成4.1.3串的根本操作串的根本操作1u 串赋值串赋值2u 串准确相等串准确相等3u 串左对齐相等串左对齐相等4u 求串长度求串长度5u 取子串取子串6u 串匹配7u 并串8u 串置换9u 串插入10u 串删除4.1.4串的存储构造串的存

4、储构造串的存储构造与线性表的存储构造非常类似。串的存储构造与线性表的存储构造非常类似。 区别是：串的数据元素在任何情况下仅是一个单个字符区别是：串的数据元素在任何情况下仅是一个单个字符 顺序存储构造顺序存储构造静态顺序存储构造顺序串静态顺序存储构造顺序串动态顺序存储构造动态顺序存储构造一次性为串分配好足够的存储单元一次性为串分配好足够的存储单元块链式存储构造块链式存储构造堆存储构造堆串堆存储构造堆串随时扩展和释放空间随时扩展和释放空间 顺序串顺序串#define M 100typedef structchar chM ； int n ；SSTR ；堆串堆串typedef structchar

5、*ch ； int len ； HSTR ；串的实践长度可在这个预定义长度范围内随意设定，超出那么被截断以一个特殊的字符作为字符串的终了标志，串长是一个隐含值3.1.5关于串的几个算法关于串的几个算法串的根本操作和线性表有很大差别串的根本操作和线性表有很大差别线性表：大多以线性表：大多以“单个元素作为操作对象单个元素作为操作对象串：通常以串：通常以“串的整体作为操作对象串的整体作为操作对象如：在线性表中查找某个元素、求取某个元素、在某个位置上插入一个元素和删除一个元素等；如：在串中查找某个子串、求取一个子串、在串的某个位置上插入一个子串以及删除一个子串等。3.1.5关于串的几个算法关于串的几个

6、算法1.判串准确相等判串准确相等 EQUALS，Q串串S：串串Q：s t u d e n t . s t u d u n t , S.nQ.nint EQUAL(SSTR S,SSTR Q) int i; if(S.n!=Q.n) return 0; elsefor(i=0;S.chi=Q.chi;i+); if(i=S.n-1) return(1); else return(0); i=0i=0 i=1i=1i=2i=2i=3i=3i=4i=4字符字符不等不等返返回回i与与S.n比较比较3.1.5关于串的几个算法关于串的几个算法2.取子串取子串 SUBSTRS,pos,len求子串的过程：为

7、复制字符序列的过程将串 S中的第 pos 个字符开场的长度为 len 的字符串复制到串 Sub 中。 d a t a s t r u c t u r e主串主串S：子串子串Q：posalenkkksktkrkukci=0i=70能够出现“参数非法的情况，应前往 ERROR3.1.5关于串的几个算法关于串的几个算法3. 串匹配串匹配 MATCH(S,T)就是在主串中找出子串出现的位置就是在主串中找出子串出现的位置假设在主串 S 中可以找到子串 T， 那么称匹配胜利，前往第一个和子串 T 中第一个字符相等的字符在主串S 中的序号；否那么，称匹配失败，前往 0。简单匹配算法或朴素匹配算法简单匹配算法

8、或朴素匹配算法匹配过程是一个字符比较的过程 cdcbabbaacdbai 匹配j不匹配jcdbai 匹配j不匹配jicdba不匹配jicdba不匹配jicdba 匹配j 匹配j 匹配j 匹配jcdbai=i-j+2 前往此元素序号前往此元素序号3.1.5关于串的几个算法关于串的几个算法4. 并串并串串串S S值值 Q.len+T.len Q.len+T.len MAXSTRLEN MAXSTRLEN Q.len MAXSTRLEN Q.len MAXSTRLEN Q.len+T.len MAXSTRLEN Q.len = MAXSTRLEN Q.len = MAXSTRLEN 在串的静态顺序存

9、储构造上实现在串的静态顺序存储构造上实现CONCAT(S,Q,T)CONCAT(S,Q,T)，需思索能够出现的三种情况：，需思索能够出现的三种情况：采用串的堆存储构造上实现采用串的堆存储构造上实现CONCAT(S,Q,T)CONCAT(S,Q,T)，不存在串衔接时被截断的问题，不存在串衔接时被截断的问题4.2 数组数组数组是同类数据元素的有序陈列。数组是同类数据元素的有序陈列。4.2.1 数组的定义数组的定义一样数据类型、一样的存储空间大小 数组元素：组成数组的数据元素数组元素：组成数组的数据元素指数据元素的存储和陈列有固定的规那么 一维数组一维数组二维数组二维数组三维数组三维数组.多维数组多

10、维数组 int szM= 0，1，2，3，4; M为最多数组元素个数 sz为数组名数组类型为整数留意：留意：C C言语规定数组元素号从言语规定数组元素号从0 0起始，到起始，到M-M-1 1为止为止( (普通从普通从1 1数数到数数到M) M) 数组元素4.2.2一维数组一维数组又称向量，是一个顺序表构造又称向量，是一个顺序表构造 数组元素即是顺序表的数据元素或结点数组元素即是顺序表的数据元素或结点 声明格式：声明格式： 数据类型数据类型 变量称号变量称号长度长度；例如：例如： int szM =0，1，2，3，4; 存储位置地址存储位置地址( 表示为表示为的方式的方式 )计算公式为计算公式为

11、 = A + ib 数组存储空间起始地址 第i号数组元素元素存储为b个字节假设一维数组中的数据元素又是一维数组构造假设一维数组中的数据元素又是一维数组构造二维数组二维数组三要素便可随时求出任一元素的地址：三要素便可随时求出任一元素的地址：开场结点的存放地址即基地址开场结点的存放地址即基地址维数和每维的上、下界；维数和每维的上、下界；每个数组元素所占用的单元数每个数组元素所占用的单元数4.2.3二维数组二维数组又称矩阵，是在横竖两个方向上陈列数组元素构成的数组又称矩阵，是在横竖两个方向上陈列数组元素构成的数组声明格式：声明格式： 数据类型数据类型 变量称号变量称号长度长度长度长度；例如：例如：

12、int ewszNM N为行数，为行数，M为列数为列数行行列列二维数组看成一个一维数组二维数组看成一个一维数组例如：例如：sz4=sz0，sz1，sz2，sz3; wsz45e191817161514131211109876543210sz0sz1sz2sz3szi =(a0j,a1j,am-1,j) 0jN-1 二维数组顺序存储位置地址二维数组顺序存储位置地址( 表示为表示为的方式的方式 )计算公式为计算公式为数组存储空间起始地址 第i号数组元素每行M个元素元素存储为b个字节根据一维数组地址公式根据一维数组地址公式 = A + iMb =(A + iMb) + jb = A + iMb +

13、jb = A + iM + jb 某个元素的地址就是它前面一切行所占的单元加上它所在行某个元素的地址就是它前面一切行所占的单元加上它所在行前面一切列元素所占的单元数之和前面一切列元素所占的单元数之和 . a1, n-1 . a11 a10 a0, n-1 . a01 a0001n -1m*n -1na00 a01 . a0, n-1a10 a11 . a1, n-1 .例如：例如： 设数组设数组 A059, 069 的基地址为的基地址为 2048，每个元，每个元 素素占占 2 个存储单元，顺序存储，那么元素个存储单元，顺序存储，那么元素A31, 57 的存储的存储地址为地址为 。 解：解：=

14、= =A =A i iM + jM + jb b = 2048 + (31 = 2048 + (31707057 )57 )2 2 = 6502 = 6502 a00 a01 a0, 69 a10 a11 a1, 69 a59, 0 a59, 1 a59, 69 a31, 57 4.3特殊矩阵的数组存储特殊矩阵的数组存储矩阵的常规存储的特点：矩阵的常规存储的特点： 可以对其元素进展随机存取；可以对其元素进展随机存取； 矩阵运算非常简单；存储的密度为矩阵运算非常简单；存储的密度为 1 1。 不适宜常规存储的矩阵：值一样的元素很多且呈某种不适宜常规存储的矩阵：值一样的元素很多且呈某种 规律分布；零

15、元素多。规律分布；零元素多。 矩阵的紧缩存储：为多个一样的非零元素只分配一个存储空间；对零元素不矩阵的紧缩存储：为多个一样的非零元素只分配一个存储空间；对零元素不分配空间。分配空间。 特殊矩阵特殊矩阵稀疏矩阵稀疏矩阵三角形矩阵三角形矩阵对角线矩阵对角线矩阵对称矩阵对称矩阵4.3.1对角线矩阵的数组表示对角线矩阵的数组表示对角线矩阵是除矩阵主对角线上的元素外，其他一切元素的值都是对角线矩阵是除矩阵主对角线上的元素外，其他一切元素的值都是0 0的矩阵。的矩阵。 nn2211a0a0a将其紧缩存储到一维数组中，且能找到将其紧缩存储到一维数组中，且能找到每个非零元素和向量下标的对应关系每个非零元素和向

16、量下标的对应关系定义为定义为int djxszn 当当i = j时，时，djx(i,j)=djxszi 当当ij时，时，djx(i,j)= 0。第第i i个元素的存储地址的计算公式是：个元素的存储地址的计算公式是：djx = A + i= A + ib b 各参数含义同前面4.3.2三角形矩阵的数组表示三角形矩阵的数组表示以主对角线划分，三角矩阵有上下三角两种。以主对角线划分，三角矩阵有上下三角两种。上下三角矩阵的下上三角不含主对角线中的元素均为常数上下三角矩阵的下上三角不含主对角线中的元素均为常数( (通通常为常为0)0)。nnn222n11211a00aa0aaann2n1n222111a

17、aa0aa00a上三角矩阵上三角矩阵下三角矩阵下三角矩阵三角矩阵的存储：存储主对角线和上下三三角矩阵的存储：存储主对角线和上下三 角中的元角中的元素。素。用一维数组用一维数组sjxszMsjxszM存储存储 ，其中，其中 M= n(1+n)/2 M= n(1+n)/2 对称矩阵上下三角中的元素数均为：对称矩阵上下三角中的元素数均为： 1 + 2 + + n = n(1+n)/2 =n(n + 1)/2 1 + 2 + + n = n(1+n)/2 =n(n + 1)/2 k = 0 1 2 3 n(n-1)/2 n(n+1)/21 a11a21a22a31a32 an1ann如：一维数组如：一

18、维数组 sjxszM存储下三角矩阵存储下三角矩阵存储地址计算公式存储地址计算公式 = = = = = A + (i(i-1)/2+j-1)b = A + (i(i-1)/2+j-1)b 各参数含义同前面k = 1 + 2 + + (i - 1) = (1+(i-1)(i-1)/2 = i(i-1)/24.3.3对称矩阵的数组表示对称矩阵的数组表示数据元素值以主对角线为对称轴对应相等数据元素值以主对角线为对称轴对应相等 nnnnnnaaaaaaaaa212222111211存储对称矩阵存储对称矩阵忽略主对角线上方的一切数据元素忽略主对角线上方的一切数据元素或忽略主对角线下方的一切数据元素或忽略主

19、对角线下方的一切数据元素 下三角形矩阵下三角形矩阵 上三角形矩阵上三角形矩阵 满足满足aij=aji aij=aji 对称矩阵上下三角中的元素数均为：对称矩阵上下三角中的元素数均为：n(n + 1)/2 n(n + 1)/2 4.3.4稀疏矩阵的数组表示稀疏矩阵的数组表示稀疏矩阵是稀疏矩阵是0 0元素较多，且出现位置无固定规律的矩阵元素较多，且出现位置无固定规律的矩阵 060000900000004007200010003005M紧缩存储原那么：存各非零元的值、行列位置和矩阵的行列数紧缩存储原那么：存各非零元的值、行列位置和矩阵的行列数 例如：例如：5 56 6的稀疏矩阵，只需的稀疏矩阵，只需8 8个非个非0 0元素元素用形如行号用形如行号, ,列号列号, ,元素值的三元组表示之元素值的三元组表示之, ,普通表示为普通表示为i,j,vi,j,v ijv该非零元素的值该非零元素的列号该非零元素的行号三元组表结点：三元组表结点：用三元组线性表表示：用三元组线性表表示： 1,1,5,1,4,3,2,2,1,3,1,7,