四章节串.ppt

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

1、第四章 串,4.1 串类型的定义4.2 串的表示和实现,4.1 串类型的定义,一、串的定义串(String)是零个或多个字符组成的有限序列。一般记作：S=a1a2a3an，串名:S串值 a1a2a3anai(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是字符串常量。操作结果：生成一个其值等于chars的串T。StrCopy(&T,S

3、)初始条件：串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)初始条件：串S1和S2存在。操作结果：用T返回由S1和S2联接而成的新串。Substring(&Sub,S,pos,len)初始条件

4、：串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。操作结果：从串S中删除第pos个字符起长度为len的子串。Index(S,T,pos)初始条件：串S和T存在，T为非空串，1posStrLength(S)。操作结果：若主串S中存在和串

5、T值相同的子串，则返回它在主串S中 第pos 个字符之后第一次出现的位置；否则函数值为0。Replace(&S,T,V)初始条件：串S、T和V存在，T为非空串。操作结果：用V替换主串S中出现的所有与T相等的不重叠的子串。DestroyString(&S)初始条件：串S存在。操作结果：串S被销毁。ADT String,4.2 串的表示和实现,一、串的定长顺序存储,使用数组存储串#define maxstrlen 255typedef unsigned char SStringmaxstrlen+1;,PASCAL方式,C方式,串的长度串的实际长度可在这预定义长度范围内随意，超过预定义长度的串值则

6、被舍去，称之为“截断”。,4.2 串的表示和实现,二、串的堆分配存储在程序执行过程中从内存空闲区中动态申请满足串长的存储空间，串在其中仍是顺序存储的，称为堆结构。也称为动态存储分配的顺序表。串的堆分配存储定义 typedef struct char*ch;/若是非空串，则按串长分配存储区,否则ch为NULL int length;HString;,4.2 串的表示和实现,三、串的链式存储,存储密度：串值所占的存储空间 实际分配的存储空间,4.2 串的表示和实现,/=串的块链存储表示=#define CHUNKSIZE 80/可由用户定义的块大小typedef struct Chunk char

7、 chCUNKSIZE;struct Chunk*next;Chunk;typedef struct Chunk*head,*tail;/串的头和尾指针 int curlen;/串的当前长度Lstring,49串是任意有限个_。A符号构成的集合B符号构成的序列C字符构成的集合D字符构成的序列50串是一种特殊的线性表，其特殊性体现在_。A可以顺序存储B数据元素是一个字符C可以链接存储D数据元素可以是多个字符51以下_是”abcd321ABCD”串的子串。Aabcd B321AB C”abcABC”D”21AB”,52两个串相等必有串长度相等且_。A串的各位置字符任意B串中各位置字符均对应相等C两

8、个串含有相同的字符D两个所含字符任意53若串s=“software”，其子串的个数是_。A8 B37 C36 D9,54设s=“abcd”,s1=“123”,则执行语句s2=InsStr（s，2，s1）后，s2=_。A”123abcd”B”a123bcd”C”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广义表的存储结构,数组是有限个数据元素的集合;数组的所有数组元

9、素具有相同特性;每个数组元素名由数组名和下标组成;每组下标值都有一个与该组下标相对应的数组元素值.,5.1 数组的类型定义,一、数组的定义,一维数组An：简单的线性表(a1,a2,an)；二维数组Am,n：a00 a01 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维

10、的长度，ji是数组元素在第i维的下标 数据关系：RR1,R2,.,Rn Ri|0 jk bk-1,1 k n 且k i,0 ji bi-2,i=2,.,n ADT Array,基本操作:,二、抽象数据类型数组的定义,二维数组的定义:,数据对象:D=aij|0ib1-1,0 jb2-1数据关系:R=ROW,COL ROW=|0ib1-2,0jb2-1 COL=|0ib1-1,0 jb2-2,数组一旦被定义，其维数和维界就不再改变，因此，除了初始化和销毁之外，数组只有两种运算：给定一组下标，读取相应的数据元素；给定一组下标，修改相应数据元素的值。数组不能进行元素的插入和删除运算。,基本操作：,In

11、itArray(&A,n,bound1,.,boundn)操作结果：若维数 n 和各维长度合法，则构造相应的数组A，并返回OK。,DestroyArray(&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 数组的顺序表示和实现,类型特点:数组

12、是多维的结构，而存储空间是一 个一维的结构。,有两种顺序映象的方式:1)以行序为主序(低下标优先)；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

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

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

15、c0,0+j1*c1+j2*c2;,1,*,三维数组Array A;,A.baseA.boundsA.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;,压缩的含义为多个值相同的元素只分配一个存贮空间；零元素不分配或少分配存贮空间。特殊矩阵：元素值相同或零元素分布有一定规律的矩阵。稀疏矩阵：零元素较多但分布没有规律的矩阵。特殊矩阵的压缩存贮实际是将二维数组的数据元素压缩到一维数组上。,5.3 矩阵的压缩存储,特殊矩阵的压缩存储,1、对称矩阵 若n阶矩阵A满足 aij=aj

16、i 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个元的空间中。不失一般性，我们可以以行序为主序存储其下三角（包括对角线）中的元。,2、三角矩阵 所谓下（上）三角矩阵是指矩阵的上（下）

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

18、小于矩阵元素的总数，且非零元素的分布无一定规律，则称之为稀疏矩阵。,0 0 0-3 0 0 0 8 0 0 0 0M=0 0 0 0 24 0 0 0-7 0 0 9 18 0 0 0 0 0,例：,以常规方法，即以二维数组表示高阶的稀疏矩阵时产生的问题:,1)零值元素占了很大空间;,2)计算中进行了很多和零值的运算，遇除法，还需判别除数是否为零。,1)尽可能少存或不存零值元素；,解决问题的原则:,2)尽可能减少没有实际意义的运算；,3)操作方便。即：能尽可能快地找到与下标值(i，j)对应的元素；能尽可能快地找到同一行或同一列的非零元。,三元组表示法 用一个线性表来表示稀疏矩阵，线性表的每个结

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

20、表，它的长度为零B=(e)-列表B只有一个原子e，B的长度为1C=(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 或为原子 或为广义表,广义表是一个多层次的线性结构,例如：,D=(E,F),其中:E=(a,(b,c)F=(d,(e),D,E,F,a,(),d,(),b,e,c,5.5广义表的存储结构,/-广义表的

21、头尾链表存储表示-typedef enum ATOM,LIST ElemTag;/ATOM=0：原子 LIST=1：子表typedef struct GLNode ElemTag tag;/公共部分，用于区分原子结点和表结点 union/原子结点和表结点的联合部分 AtomType atom；/atom是原子结点的值域,AtomType由用户定义 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),原子和子表

22、所在层次清晰,最高层的表结点个数为广义表长度,非空广义表的头指针均指向一个表结点,56设二维数组Amn,每个数组元素占用k个存储单元，第一个数组元素的存储地址是Loc（a00）,求按行优先顺序存放的数组元素aij（0im-1，0jn-1，）的存储地址是_。ALoc(a00)+(i-1)*n+j-1*k BLoc(a00)+i*n+j*kCLoc(a00)+j*m+i*kDLoc(a00)+(j-1)*m+i-1*k57.设二维数组Amn,每个数组元素占用k个存储单元，第一个数组元素的存储地址是Loc（a00）,求按列优先顺序存放的数组元素aij（0im-1，0jn-1，）的存储地址是_。ALo

23、c(a00)+(i-1)*n+j-1*k BLoc(a00)+i*n+j*kCLoc(a00)+j*m+i*kDLoc(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-1Cj(j+1)/2+IDj(j-1)/2+i-159若将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-jCi(2n-i+1)/2+j-i Di(2n-i+2)/2+j-i,