四章节串.ppt

《四章节串.ppt》由会员分享，可在线阅读，更多相关《四章节串.ppt（46页珍藏版）》请在三一文库上搜索。

1、第四章 串,4.1 串类型的定义 4.2 串的表示和实现,4.1 串类型的定义,一、串的定义 串(String)是零个或多个字符组成的有限序列。 一般记作：S=a1a2a3an， 串名: S 串值 a1a2a3an ai(1in)可以是字母、数字或其它字符； 串的长度：串中所包含的字符个数； 长度为零的串称为空串(Empty String)，它不包含任何字符。 空白串:通常将仅由一个或多个空格组成的串称为空白串(Blank String)。 注意：空串和空白串的不同。,4.1 串类型的定义,串的子串：串中任意个连续字符组成的子序列称为该串的子串(SubString)，包含子串的串相应地称为主串

2、。 通常将子串在主串中首次出现时子串第一个字符在主串的位置,定义为子串在主串中的位置。 例如：A=“This is a string” B=“is” 则B是A的子串，A为主串。 B在A中出现了两次，其中首次出现所对应的主串位置是3。因此，称B在A中的位置为3。 特别地，空串是任意串的子串，任意串是其自身的子串。,二、串的抽象数据类型的定义 ADT String 数据对象：D=ai| aiCharacterSet； i=1,2,n,；n0 数据关系：R1=| ai-1, aiD； i= 2,n 基本操作： StrAssign (&T , chars) 初始条件：chars是字符串常量。 操作结果

3、：生成一个其值等于chars的串T。 StrCopy (&T , S) 初始条件：串S存在。 操作结果：由串S得串T。 StrEmpty (S) 初始条件：串S存在。 操作结果：若S为空串，则返回TRUE，否则返回FALSE。,StrLength (S) 初始条件：串S存在。 操作结果：则返S的元素个数，称为串的长度。 StrCompare (S, T) 初始条件：串S和T存在。 操作结果:若ST，则返回值0；若S = T，则返回值=0；若ST，则返回值0. ClearString (&S) 初始条件：串S存在。 操作结果：将S清为空串。 Concat (&T , S1, S2) 初始条件：串

4、S1和S2存在。 操作结果：用T返回由S1和S2联接而成的新串。 Substring (&Sub, S, pos, len) 初始条件：串S存在，1posStrLength (S)且0lenStrLength (S)- pos+1。 操作结果：用sub返回串S的第pos个字符起长度为len的字符。,StrInsert (&S, pos, T ) 初始条件：串S和T存在，1=pos=StrLength (S)+1。 操作结果：在串S的第pos个字符之前插入串T。 StrDelete (&S, pos, len) 初始条件：串S存在，0posStrLength (S)-len+1。 操作结果：从串

5、S中删除第pos个字符起长度为len的子串。 Index (S, T, pos) 初始条件：串S和T存在，T为非空串，1posStrLength (S)。 操作结果：若主串S中存在和串T值相同的子串，则返回它在主串S中 第pos 个字符之后第一次出现的位置；否则函数值为0。 Replace (&S, T, V) 初始条件：串S、T和V存在，T为非空串。 操作结果：用V替换主串S中出现的所有与T相等的不重叠的子串。 DestroyString (&S) 初始条件：串S存在。 操作结果：串S被销毁。 ADT String,4.2 串的表示和实现,一、串的定长顺序存储,使用数组存储串 #define

6、 maxstrlen 255 typedef unsigned char SStringmaxstrlen+1;,PASCAL方式,C方式,串的长度 串的实际长度可在这预定义长度范围内随意，超过预定义长度的串值则被舍去，称之为“截断”。,4.2 串的表示和实现,二、串的堆分配存储 在程序执行过程中从内存空闲区中动态申请满足串长的存储空间，串在其中仍是顺序存储的，称为堆结构。也称为动态存储分配的顺序表。 串的堆分配存储定义 typedef struct char *ch; /若是非空串，则按串长分配存储区,否则ch为NULL int length; HString;,4.2 串的表示和实现,三、

7、串的链式存储,存储密度： 串值所占的存储空间 实际分配的存储空间,4.2 串的表示和实现,/= = = = = =串的块链存储表示= = = = = = #define CHUNKSIZE 80 /可由用户定义的块大小 typedef struct Chunk char chCUNKSIZE; struct Chunk *next; Chunk; typedef struct Chunk *head, *tail; /串的头和尾指针 int curlen; /串的当前长度 Lstring,49串是任意有限个_。 A符号构成的集合 B符号构成的序列 C字符构成的集合 D字符构成的序列 50串是一

8、种特殊的线性表，其特殊性体现在_。 A可以顺序存储 B数据元素是一个字符 C可以链接存储 D数据元素可以是多个字符 51以下_是”abcd321ABCD ”串的子串。 Aabcd B321AB C ” abcABC” D ” 21AB”,52两个串相等必有串长度相等且_。 A串的各位置字符任意 B串中各位置字符均对应相等 C两个串含有相同的字符 D两个所含字符任意 53若串s=“software”，其子串的个数是_。 A8 B37 C36 D9,54设s=“abcd”,s1=“123”,则执行语句s2=InsStr（s，2，s1）后，s2=_。 A”123abcd” B”a123bcd” C”

9、ab123cd” D”abc123d” 55设s=“abcd”,则执行语句s2=DelStr（s，2，2）后，s2=_。 A”abcd” B”abc” C”ad” D”a”,第五章 数组和广义表,5.1 数组的定义,5.3 矩阵的压缩存储,5.2 数组的顺序表示和实现,5.4 广义表的定义,5.5 广义表的存储结构,数组是有限个数据元素的集合; 数组的所有数组元素具有相同特性; 每个数组元素名由数组名和下标组成; 每组下标值都有一个与该组下标相对应的数组元素值.,5.1 数组的类型定义,一、数组的定义,一维数组An： 简单的线性表(a1, a2, an)； 二维数组Am,n： a00 a01

10、a02 a0,n-1 a10 a11 a12 a1,n-1 am-1,0 am-1,1 am-1,2 am-1,n-1 看成由m个行向量组成的线性表，或由n个列向量组成的线性表； N维数组:看成其数据元素为n-1维数组类型的线性表。,ADT Array 数据对象： ji=0,bi-1,i=1,2,n Daj1j2jn | aj1j2jn ElemSet, n是数组的维数，bi是数组第i维的长度，ji是数组元素在第i维的下标 数据关系： RR1, R2, ., Rn Ri | 0 jk bk -1, 1 k n 且k i, 0 ji bi -2, i=2,.,n ADT Array,基本操作:,

11、二、抽象数据类型数组的定义,二维数组的定义:,数据对象: D = aij | 0ib1-1, 0 jb2-1 数据关系: R = ROW, COL ROW = | 0ib1-2, 0jb2-1 COL = | 0ib1-1, 0 jb2-2,数组一旦被定义，其维数和维界就不再改变，因此，除了初始化和销毁之外，数组只有两种运算： 给定一组下标，读取相应的数据元素； 给定一组下标，修改相应数据元素的值。 数组不能进行元素的插入和删除运算。,基本操作：,InitArray(&A, n, bound1, ., boundn) 操作结果：若维数 n 和各维长度合法，则构造相应的数组A，并返回OK。,De

12、stroyArray(&A) 操作结果：销毁数组A。,Value(A, &e, index1, ., indexn) 初始条件：A是n维数组，e为元素变量，随后是n 个下标值。 操作结果：若各下标不超界，则e赋值为所指定的A 的元素值，并返回OK。,Assign(&A, e, index1, ., indexn) 初始条件：A是n维数组，e为元素变量，随后是n 个下标值。 操作结果：若下标不超界，则将e的值赋 给所指定的A的元素，并返回OK。,5.2 数组的顺序表示和实现,类型特点: 数组是多维的结构，而存储空间是一 个一维的结构。,有两种顺序映象的方式: 1) 以行序为主序(低下标优先)；

13、2) 以列序为主序(高下标优先)。,例如：,称为基地址,以“行序为主序”的存储映象,二维数组A中任一元素ai,j 的存储位置 LOC(i,j) = LOC(0,0) + (b2ij),a0,1,a0,0,a0,2,a1,0,a1,1,a1,2,a0,1,a0,0,a0,2,a1,0,a1,1,a1,2,L,L,例如：,称为基地址,以“列序为主序”的存储映象,二维数组A中任一元素ai,j 的存储位置 LOC(i,j) = LOC(0,0) + (b1ji),a0,1,a0,0,a0,2,a1,0,a1,1,a1,2,a1,0,a0,0,a0,1,a1,1,a0,2,a1,2,L,L,/- - -

14、 - -数组的顺序存储表示- - - - - #include #define MAX_ARRAY_DIM 8 /假设数组维数的最大值为8 typedef struct ElemType *base; /数组元素基址,由InitArray分配 int dim； /数组维数 int *bounds; /数组维界基址, 由InitArray分配 int *constants /数组映象函数常量基址，由InitArray分配 Array;,/- - - - -基本操作函数原型说明- - - - - Status InitArray(Array /A是n维数组，e为元素变量，随后是n个下标值 /若各下

15、标不超界，则将e的值赋给指定的A的元素，并返回OK,/- - - - -基本操作的算法描述- - - - - Status InitArray(Array ,1.获得dim,2.申请空间存放bi的值,4.计算数组元素个数elemtotal,3.获得bi的值,5.申请空间存放A中所有元素的值,6.申请空间存放Ci的值,存放bi ci的值 给A分配存储空间,一维数组 Array A;,A.base A.bounds A.constants,A3,=Loc0+3*（ ）,1,*,1,Aj1=Loc0+j1*c1;,二维数组 Array A;,A.base A.bounds A.constants,A

16、3,2,=Loc0,0+3*（ ）+2*( ),4,Aj1,j2=Loc0,0+j1*c1+j2*c2;,1,*,三维数组 Array A;,A.base A.bounds A.constants,A2,1,2,=Loc0,0,0+2* ( )+1*( )+2*( ),*,6,3,1,Aj1,j2,j3=Loc0,0,0+j1*c1+j2*c2+j3*c3;,压缩的含义 为多个值相同的元素只分配一个存贮空间； 零元素不分配或少分配存贮空间。 特殊矩阵：元素值相同或零元素分布有一定规律的矩阵。 稀疏矩阵：零元素较多但分布没有规律的矩阵。 特殊矩阵的压缩存贮实际是将二维数组的数据元素压缩到一维数组

17、上。,5.3 矩阵的压缩存储,特殊矩阵的压缩存储,1、对称矩阵 若n阶矩阵A满足 aij= aji 0i,jn-1 则称为n阶对称矩阵。,特殊矩阵: 非零元在矩阵中的分布有一定规则 例如: 三角矩阵 对角矩阵,a00,a11,an-1n-1,a00 a10 a11 a20 an-1,0 an-1,n-1,对称矩阵的压缩存储：,a11 a21 a22 a31 an,1 an,n,存贮地址计算公式： Loc(aij)= Loc(a11)+ i*(i-1)/2+(j-1)*L,对于对称矩阵，我们可以为每一对对称元分配一个存储空间，则可将n2个元压缩存储到n*(n+1)/2个元的空间中。不失一般性，我

18、们可以以行序为主序存储其下三角（包括对角线）中的元。,2、三角矩阵 所谓下（上）三角矩阵是指矩阵的上（下）三角（不包括对角线）中的元均为常数c或零的n阶矩阵。 对于三角矩阵，则除了和对称矩阵一样，只存储其下（上）三角中的元之外，再加一个存储常数c的存储空间即可。,c,c,下三角矩阵,上三角矩阵,3、对角矩阵 所有的非零元都集中在以主对角线为中心的带状区域中。即除了主对角线上和直接在对角线上、下方若干条对角线上的元之外，所有其它的元皆为零。 对于对角矩阵，也可按某个原则（或以行为主，或以对角线的顺序）将其压缩存储到一维数组上。,n*n,稀疏矩阵的压缩存储,假设 m 行 n 列的矩阵含 t 个非零

19、元素，则称 为稀疏因子。 通常认为 0.05 的矩阵为稀疏矩阵。,何谓稀疏矩阵？,如果一个矩阵中非零元素的个数远远小于矩阵元素的总数，且非零元素的分布无一定规律，则称之为稀疏矩阵。,0 0 0 -3 0 0 0 8 0 0 0 0 M= 0 0 0 0 24 0 0 0 -7 0 0 9 18 0 0 0 0 0,例：,以常规方法，即以二维数组表示 高阶的稀疏矩阵时产生的问题:,1) 零值元素占了很大空间;,2) 计算中进行了很多和零值的运算， 遇除法，还需判别除数是否为零。,1) 尽可能少存或不存零值元素；,解决问题的原则:,2) 尽可能减少没有实际意义的运算；,3) 操作方便。 即： 能尽

20、可能快地找到与下标值(i，j)对应的元素； 能尽可能快地找到同一行或同一列的 非零元。,三元组表示法 用一个线性表来表示稀疏矩阵，线性表的每个结点对应稀疏矩阵的一个非零元素。其中包括三个域，分别为该元素的行下标、列下标和值。结点间的先后顺序按矩阵的行优先顺序排列（跳过零元素），将线性表用顺序的方法存储在连续的存储区里。,顺序存储,5.4 广义表的类型定义,一、广义表的定义,广义表：是线性表的推广，也称为列表，是n个单元素或子表所组成的有限序列。记作 LS=(1,2,n) 其中：LS是广义表的名称，n是其长度； i 可以是单个元素，也可以是广义表，分别称为广义表LS的原子和子表。 用大写字母表示

21、广义表的名称，小写字母表示原子； 当广义表LS非空时，称第一个元素1为LS的表头，称其余元素组成的表（2, 3，,n) 是LS的表尾。,A=( ) -A是一个空表，它的长度为零 B=(e) -列表B只有一个原子e，B的长度为1 C=(a,(b,c,d) - 列表C的长度为2，两个元素分别为原子a和子表（b,c,d） D=(A,B,C) - 列表D的长度为3，三个元素都是列表代入子表值，D=( ),(e),(a,(b,c,d) E=(a,E) -递归表，长度为2。E相当于一个无限的列表E=(a,(a,(a,),例如:,广义表是递归定义的线性结构，,LS = ( 1, 2, , n ) 其中：i

22、或为原子 或为广义表,广义表是一个多层次的线性结构,例如：,D=(E, F),其中: E=(a, (b, c) F=(d, (e),D,E,F,a,( ),d,( ),b,e,c,5.5广义表的存储结构,/- - - - -广义表的头尾链表存储表示- - - - - typedef enum ATOM, LIST ElemTag; /ATOM= =0：原子 LIST= =1：子表 typedef struct GLNode ElemTag tag; /公共部分，用于区分原子结点和表结点 union /原子结点和表结点的联合部分 AtomType atom； /atom是原子结点的值域, Ato

23、mType由用户定义 struct struct GLNode *hp, *tp;ptr; / ptr是表结点的指针域,ptr.hp和ptr.tp分别指向表头和表尾 ; *GList; /广义表类型,A=( ) B=(e) C=(a ,(b ,c ,d) D=(A , B , C) E=(a , E),原子和子表所在层次清晰,最高层的表结点个数为广义表长度,非空广义表的头指针均指向一个表结点,56设二维数组Amn,每个数组元素占用k个存储单元，第一个数组元素的存储地址是Loc（a00）,求按行优先顺序存放的数组元素aij（0im-1，0jn-1，）的存储地址是_。 ALoc(a00)+(i-1

24、)*n+j-1*k BLoc(a00)+i*n+j*k CLoc(a00)+j*m+i*k DLoc(a00)+(j-1)*m+i-1*k 57.设二维数组Amn,每个数组元素占用k个存储单元，第一个数组元素的存储地址是Loc（a00）,求按列优先顺序存放的数组元素aij（0im-1，0jn-1，）的存储地址是_。 ALoc(a00)+(i-1)*n+j-1*k BLoc(a00)+i*n+j*k CLoc(a00)+j*m+i*k DLoc(a00)+(j-1)*m+i-1*k,58若将n阶上三角矩阵A按列优先顺序压缩存放在一维数组B1n(n+1)/2中，第一个非零元素a1，1存于B0中，则应存放到Bk中的非零元素ai,j(1in,ijn)的下标i、j与k的对应关系是_。 Ai(i+1)/2+j Bi(i-1)/2+j-1 Cj(j+1)/2+I Dj(j-1)/2+i-1 59若将n阶下三角矩阵A按列优先顺序压缩存放在一维数组B1n(n+1)/2中，第一个非零元素a1，1存于B0中，则应存放到Bk中的非零元素ai,j(1in,1ji)的下标i、j与k的对应关系是_。 Aj(2n-j+1)/2+i-j B(j-1)(2n-j+2)/2+i-j Ci(2n-i+1)/2+j-i Di(2n-i+2)/2+j-i,