串和数组课件

《串和数组课件》由会员分享，可在线阅读，更多相关《串和数组课件（34页珍藏版）》请在金锄头文库上搜索。

1、2020/9/1,1,第7章 串和数组,2020/9/1,2,第7章 串和数组,7.1 串及其运算 7.2 串的存储结构 7.3 串运算的实现 7.4 数组的定义和运算 7.5 数组的顺序存储结构 7.6 矩阵的压缩存储 习题,2020/9/1,3,7.1 串及其运算,串：由多个或零个字符组成的有限序列 ，记作 S =“c1c2c3cn” (n=0) 其中，S是串名，c1c2c3cn是串值，ci是串中字符，n是串的长度，表示串中字符的数目。 空串：零个字符的串称为空串 记作 “” 子串：串中任意个连续的字符组成的子序列 主串：包含子串的串 字符在串中的位置：字符在序列中的序号 子串在串中的位置

2、：子串的第一个字符在主串中的位置 空格串：由一个或多个空格组成的串 串的表示：用一对双引号括起来，这里约定为双引号 串的操作：以“串的整体”作为操作对象,2020/9/1,4,串的基本运算 串赋值 strcopy(String struct linklist*next; linkstring;,每个结点存放4个字符： typedef struct linknode char data4; struct linklist*next; linkstring;,2020/9/1,6,索引存储 建立串名与串值之间对应关系的索引表。串值采用顺序存储结构，索引表存放串名、串起始地址、串长度或串尾地址。 例

3、如，有2个串：s1=“work” ，s2=“day”,2020/9/1,7,7.3 串运算的实现,7.3.1 基本运算的实现（串的顺序存储） 顺序串的类型定义： #define maxsize 100 typedef struct char chmaxsize; int len; seqstring; seqstring*S; 说明：串中字符的序号从1开始，在向量中从下标0开始存放。,2020/9/1,8,串连接 将两个串首尾相接，连成一个新串。 void StrCat(seqstring* /串长度是两串长度之和 ,2020/9/1,9,求子串 从主串的第i个字符起，取j个字符构成子串。 v

4、oid SubString(seqstring* /在T末尾赋0 ,2020/9/1,10,子串定位（模式匹配） 模式匹配是串处理中最重要的运算之一。 定义 在串中寻找子串（第一个字符）在串中的位置 词汇 在模式匹配中，子串称为模式，串称为目标。 示例 目标 S : “Beijing” 模式 P : “jin” 匹配结果 = 4,2020/9/1,11,朴素的模式匹配算法（穷举的模式匹配算法）： 设S=s1,s2,sn(主串)T=t1,t2,tm(模式串) 其中0mn i为指向S中字符的指针，j为指向T中字符的指针 若sipj，匹配失败；若 (si-j+1 si-1)=(t1 tj-1)，匹配

5、成功 算法简单，但效率不高，重复回溯太多，时间复杂度为O(m*n),2020/9/1,12,朴素的模式 第1趟 S a b b a b a 匹配过程 | | T a b a 第2趟 S a b b a b a T a b a 第3趟 S a b b a b a T a b a 第4趟 S a b b a b a | | | T a b a ,2020/9/1,13,int Index(seqstring*S, seqstring*T) /顺序串的朴素模式匹配 i=1; j=1; /位序从1开始 while(ilen /匹配不成功 ,2020/9/1,14,7.4 数组的定义和运算,数组的定义

6、数组是由值与下标构成的有序对，结构中的每一个数据元素都与其下标有关。 数组结构的性质： (1)数据元素数目固定：一旦说明了一个数组结构，其元素数目不再有增减变化； (2)数据元素具有相同的类型； (3)数据元素的下标关系具有上下界的约束并且下标有序。 数组有两种运算： 给定一组下标，存取相应的数据元素； 给定一组下标，修改相应数据元素中的某个数据项的值。,2020/9/1,15,Amn=,2020/9/1,16,次序约定问题： 存储单元是一维的结构，而数组是个多维的结构，那么用一组连续存储单元如何存放数组的数据元素？ 二维数组的顺序存储分为： 以行为主序的优先存储；将数组元素按行优先关系排列，

7、第i+1行中的数据元素紧跟在第i行中数据元素的后面。同一行中元素以列下标次序排列。 以列为主序的优先存储：列为主序的优先存储是将数组元素按列优先关系排列，第j+1列中的数据元素紧跟在第j列中数据元素的后面，同一列中元素以行下标次序排列。,(a) 以行为主序 (b) 以列为主序,7.5 数组的顺序存储结构,2020/9/1,17,二维数组A1.m,1.n 以行优先存储的地址计算公式：Loc(aij)=Loc(a11)+(i1)n+(j1)d其中：d 是每个数据元素占用的存储单元数 以列优先存储的地址计算公式：Loc(aij)=Loc(a11)+(j1)m+(i1)d 二维数组A0.m,0.n 数

8、组下标的下界是0，每行具有n+1个元素。二维数组以行优先存储的地址计算公式为：Loc(aij)=Loc(a00)+i(n+1)+jd 二维数组Ac1.d1,c2.d2 数组下标的下界任意，每行具有d2-c2+1个元素。二维数组以行优先存储的地址计算公式为：Loc(aij)=Loc(ac1c2)+(i-c1)(d2-c2+1)+(j-c2)d,2020/9/1,18,7.6.1 特殊矩阵 对于值相同的元素或者零元素在矩阵中的分布具有一定规律的矩阵，称之为特殊矩阵。 对角矩阵：所有的非零元素都集中在以主对角线为中心的带状区域中。,7.6 矩阵的压缩存储,2020/9/1,19,采用一维数组压缩存储

9、最简单的对角矩阵，只存放主对角线上的元素。 显然，当|i-j|0时，aij=0 Ak=aij k=i=j (0k,i,jn-1) 采用一维数组压缩存储三对角矩阵。 显然，当|i-j|1时，aij=0 A2i+j=aij 0in-1，i-1ji+1（下标从0开始） A2(i-1)+j= aij 1in，i-1ji+1（下标从1开始） 例： A:(3,2,4,3,5,7,6,0,8,9),2020/9/1,20,三角矩阵：三角矩阵有上三角和下三角两种。上三角矩阵是指矩阵的下三角（不包含对角线）中的元素均为常数（或零）的n阶矩阵，下三角矩阵与之相反。,(a)下三角矩阵 (b)上三角矩阵,2020/9

10、/1,21,元素：相同元素占用一个单元，若为0则不存储。 存储：用一维数组A0.n(n+1)/21 存储矩阵中的n(n+1)/2个非零元素。下三角矩阵以行为主序存储，上三角矩阵以列为主序存储。 数组元素Ak与aij的关系：,2020/9/1,22,例： (a) A: (1,2,3,4,5,6) (b) A: (1,2,4,3,5,6),(a)下三角矩阵 (b)上三角矩阵,2020/9/1,23,对称矩阵：在n阶方阵中，若中的元素满足aij=aji(0i,jn1)，则称是对称矩阵。 对称的元素aij和aji共享一个存储空间，要存储的元素总数为1+2+n=n(n+1)/2。即用一维数组存放矩阵的下

11、三角（以行为主序）或上三角（以列为主序）。 Ak与aij对应关系： k=i(i+1)/2+j (ij) k=j(j+1)/2+i (ij) Ak中相当于存放了aij和aji，若ij，则认为是aij；若ij，则认为是aji 。,0k n(n+1)/2-1 0 i,jn-1,2020/9/1,24,7.6.2 稀疏矩阵 含有非零元素及较多的零元素，但非零元素的分布没有任何规律，这样的矩阵称为稀疏矩阵。即稀疏矩阵Amn中有t个非零元素，若t/m*n0.05，则称A为稀疏矩阵。 稀疏矩阵压缩存储方法： 三元组表 十字链表,2020/9/1,25,稀疏矩阵的三元组表 将稀疏矩阵的非零元素用三元组按行优先

12、（或列优先）的顺序排列（跳过零元素），则得到一个其结点均是三元组的线性表。 三元组三元组=（行i，列j，非零元素值）行优先三元组=（列j，行i，非零元素值）列优先,2020/9/1,26,数据结构描述：#define smax 16 /最大非零元素个数的常数 typedef int datatype;typedef struct int i,j; /行，列号 datatype v; /元素值 node; /三元组结构类型typedef struct int m,n,t; /行数,列数,非零元素个数 node datasmax; /存放三元组表的向量 spmatrix; /稀疏矩阵的三元组表结构

13、类型,2020/9/1,27,稀疏矩阵的三元组表示实例：,2020/9/1,28,稀疏矩阵三元组表示的转置运算,2020/9/1,29,方法：按照a-data的列序，依次在a-data中寻找相应的三元组填入b中，所得到的b-data是按行优先存放的，因此进行了转置。 步骤：从ano=0开始扫描，遇到列号为col的项，将其行号变列号、列号变行号，顺次存于转置矩阵三元组表b。 矩阵A具有n行，对a-data扫描n趟，a-data的长度为t，所以算法的时间复杂度为 O(n*t),2020/9/1,30,算法描述如下：spmatrix TRANSMAT(spmatrix a)/ 返回稀疏矩阵A的转置，

14、ano和bno分别指示adata和bdata中结点序号 /col指示*a的列号(即*b的行号) int ano,bno,col; spmatrix *b; /存放转置后的矩阵 b=(spmatrix*)malloc(sizeof(spmatrix); /产生存放转置矩阵的空间 b-m=a-n; b-n=a-m; /行列数交换 b-t=a-t; /非零元素个数不变 if (b-t0) / 有非零元素，则转置 bno=0； for(col=0;coln;col+) / 按*a的列序转置 for(ano=0;anot; ano+) /扫描整个三元组表 if(a-dataano.j=col) / 列号

15、为col则进行置换 b-databno.i=a-dataano.j; /a的列号变为b的行号 b-databno.j=a-dataano.i; /a的行号变为b的列号 b-databno.v=a-dataano.v; bno+; / b-data结点序号加1 return b; /返回转置结果指针 / TRANSMAT,2020/9/1,31,用十字链表示稀疏矩阵 当矩阵中非零元素的个数和位置经过运算后变化较大时，就不宜采用顺序存储结构，而应采用链式存储结构来表示稀疏矩阵。 稀疏矩阵的链接表示采用十字链表：行链表与列链表十字交叉。 行链表与列链表都是带表头结点的循环链表。用表头结点表征是第几行，第几列。,2020/9/1,32,元素结点 right指向同一行中下一个非零元素的指针（向右域） down指向同一列中下一个非零元素的指针（向下域） 表头结点 行、列表头结点 next用于表示头结点的链接 总表头结点,元素结点,表头结点,总表头结点,2020/9/1,33,2020/9/1,34,习题,1、2、3、4、5、6、12、13、14、18、19,