最新四章节串幻灯片.ppt

进入夏天，少不了一个热字当头，电扇空调陆续登场，每逢此时，总会进入夏天，少不了一个热字当头，电扇空调陆续登场，每逢此时，总会想起那一把蒲扇。蒲扇，是记忆中的农村，夏季经常用的一件物品。记想起那一把蒲扇。蒲扇，是记忆中的农村，夏季经常用的一件物品。记忆中的故乡，每逢进入夏天，集市上最常见的便是蒲扇、凉席，不论男女老忆中的故乡，每逢进入夏天，集市上最常见的便是蒲扇、凉席，不论男女老少，个个手持一把，忽闪忽闪个不停，嘴里叨叨着少，个个手持一把，忽闪忽闪个不停，嘴里叨叨着“怎么这么热怎么这么热”，于是三，于是三五成群，聚在大树下，或站着，或随即坐在石头上，手持那把扇子，边唠嗑五成群，聚在大树下，或站着，或随即坐在石头上，手持那把扇子，边唠嗑边乘凉。孩子们却在周围跑跑跳跳，热得满头大汗，不时听到边乘凉。孩子们却在周围跑跑跳跳，热得满头大汗，不时听到“强子，别跑强子，别跑了，快来我给你扇扇了，快来我给你扇扇”。孩子们才不听这一套，跑个没完，直到累气喘吁吁，。孩子们才不听这一套，跑个没完，直到累气喘吁吁，这才一跑一踮地围过了，这时母亲总是，好似生气的样子，边扇边训，这才一跑一踮地围过了，这时母亲总是，好似生气的样子，边扇边训，“你你看热的，跑什么？看热的，跑什么？”此时这把蒲扇，是那么凉快，那么的温馨幸福，有母亲此时这把蒲扇，是那么凉快，那么的温馨幸福，有母亲的味道！蒲扇是中国传统工艺品，在我国已有三千年多年的历史。取材的味道！蒲扇是中国传统工艺品，在我国已有三千年多年的历史。取材于棕榈树，制作简单，方便携带，且蒲扇的表面光滑，因而，古人常会在上于棕榈树，制作简单，方便携带，且蒲扇的表面光滑，因而，古人常会在上面作画。古有棕扇、葵扇、蒲扇、蕉扇诸名，实即今日的蒲扇，江浙称之为面作画。古有棕扇、葵扇、蒲扇、蕉扇诸名，实即今日的蒲扇，江浙称之为芭蕉扇。六七十年代，人们最常用的就是这种，似圆非圆，轻巧又便宜的蒲芭蕉扇。六七十年代，人们最常用的就是这种，似圆非圆，轻巧又便宜的蒲扇。蒲扇流传至今，我的记忆中，它跨越了半个世纪，也走过了我们的扇。蒲扇流传至今，我的记忆中，它跨越了半个世纪，也走过了我们的半个人生的轨迹，携带着特有的念想，一年年，一天天，流向长长的时间隧半个人生的轨迹，携带着特有的念想，一年年，一天天，流向长长的时间隧道，袅道，袅4.1 串类型的定义 一、串的定义串(String)是零个或多个字符组成的有限序列。一般记作：S=a1a2a3an，串名串名: S串值串值 a1a2a3anai(1in)可以是字母、数字或其它字符； 串的长度串的长度：串中所包含的字符个数； 长度为零的串称为空串空串(Empty String)，它不包含任何字符。 空白串空白串: :通常将仅由一个或多个空格组成的串称为空白串(Blank String)。 注意：空串空串和空白串空白串的不同。4.2 串的表示和实现三、串的链式存储S结点大小为1的单链表A B C M 存储密度：存储密度： 串值所占的存储空间串值所占的存储空间 实际分配的存储空间实际分配的存储空间S结点大小为4的单链表 DCBA HGFE#M4.2 串的表示和实现/= = = = = =串的块链存储表示串的块链存储表示= = = = = = #define CHUNKSIZE 80 /可由用户定义的块大小可由用户定义的块大小typedef struct Chunk char chCUNKSIZE; struct Chunk *next; Chunk;typedef struct Chunk *head, *tail; /串的头和尾指针串的头和尾指针 int curlen; /串的当前长度串的当前长度Lstring49串是任意有限个_。A符号构成的集合B符号构成的序列C字符构成的集合D字符构成的序列50串是一种特殊的线性表，其特殊性体现在_。A可以顺序存储B数据元素是一个字符C可以链接存储D数据元素可以是多个字符51以下_是”abcd321ABCD ”串的子串。Aabcd B321AB C ” abcABC” D ” 21AB”52两个串相等必有串长度相等且_。A串的各位置字符任意B串中各位置字符均对应相等C两个串含有相同的字符D两个所含字符任意53若串s=“software”，其子串的个数是_。A8 B37 C36 D954设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.15.1 数组的定义数组的定义5.35.3 矩阵的压缩存储矩阵的压缩存储 5.25.2 数组的顺序表示和实现数组的顺序表示和实现5.45.4 广义表的定义广义表的定义5.55.5 广义表的存储结构广义表的存储结构 数组是数组是有限有限个数据元素的集合个数据元素的集合; ; 数组的所有数组元素具有数组的所有数组元素具有相同特性相同特性; ; 每个数组元素名由每个数组元素名由数组名数组名和和下标下标组成组成; ; 每组每组下标值下标值都有一个与该组下标相都有一个与该组下标相对应对应的的数组元数组元素值素值. .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维的长度，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 数组一旦被定义，其维数和维界就不再改变，数组一旦被定义，其维数和维界就不再改变，因此，除了初始化和销毁之外，数组只有两种运算：因此，除了初始化和销毁之外，数组只有两种运算： 给定一组下标，读取相应的数据元素；给定一组下标，读取相应的数据元素； 给定一组下标，修改相应数据元素的值。给定一组下标，修改相应数据元素的值。 数组不能进行元素的插入和删除运算。数组不能进行元素的插入和删除运算。基本操作基本操作：InitArray(&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 数组的顺序表示和实现数组的顺序表示和实现类型特点类型特点: 数组是多维的结构，而存储空间是一数组是多维的结构，而存储空间是一 个一维的结构。个一维的结构。 有两种顺序映象的方式有两种顺序映象的方式:1) 以行序为主序以行序为主序(低下标优先低下标优先)；2) 以列序为主序以列序为主序(高下标优先高下标优先)。例如：例如： 称为基地址基地址以以“行序为主序行序为主序”的存储映象的存储映象二维数组A中任一元素ai,j 的存储位置 LOC(i,j) = LOC(0,0) + (b2ij)a0,1a0,0a0,2a1,0a1,1a1,2a0,1a0,0a0,2a1,0a1,1a1,2L L 例如：例如： 称为基地址基地址以以“列序为主序列序为主序”的存储映象的存储映象二维数组二维数组A中任一元素中任一元素ai,j 的存储位置的存储位置 LOC(i,j) = LOC(0,0) + (b1ji)a0,1a0,0a0,2a1,0a1,1a1,2a1,0a0,0a0,1a1,1a0,2a1,2L 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, int dim,); /若维数dim和随后的各维长度合法，则构造相应的数组A，并返回OKStatus DestroyArray(Array &A); /销毁数组AStatus Value(Array A, ElemType &e, ); /A是n维数组，e为元素变量，随后是n个下标值 /若各下标不超界，则e赋值为指定的A的元素值，并返回OK Status Assign(Array &A, ElemType e, ); /A是n维数组，e为元素变量，随后是n个下标值 /若各下标不超界，则将e的值赋给指定的A的元素，并返回OK/- - - - -基本操作的算法描述- - - - - Status InitArray(Array &A, int dim,);1.获得dim2.申请空间存放bi的值4.计算数组元素个数elemtotal3.获得bi的值5.申请空间存放A中所有元素的值6.申请空间存放Ci的值存放bi ci的值给A分配存储空间一维数组Array A;A.baseA.boundsA.constants 7A3=Loc0+3*（ ）1*1Aj1=Loc0+j1*c1;二维数组Array A;A.baseA.boundsA.constantsA3,2=Loc0,0+3*（ ）+2*( )4Aj1,j2=Loc0,0+j1*c1+j2*c2; 6 4 1*三维数组Array A;A.baseA.boundsA.constants323A2,1,2=Loc0,0,0+2* ( )+1*( )+2*( )631*631Aj1,j2,j3=Loc0,0,0+j1*c1+j2*c2+j3*c3; 压缩的含义压缩的含义 为多个值相同的元素只分配一个存贮空间；为多个值相同的元素只分配一个存贮空间； 零元素不分配或少分配存贮空间。零元素不分配或少分配存贮空间。 特殊矩阵：元素值相同或零元素分布有特殊矩阵：元素值相同或零元素分布有一定规律的矩阵。一定规律的矩阵。 稀疏矩阵：零元素较多但分布没有规律稀疏矩阵：零元素较多但分布没有规律的矩阵。的矩阵。 特殊矩阵的压缩存贮实际是将二维数组特殊矩阵的压缩存贮实际是将二维数组的数据元素压缩到一维数组上。的数据元素压缩到一维数组上。5.3 矩阵的压缩存储矩阵的压缩存储特殊矩阵的压缩存储特殊矩阵的压缩存储1 1、对称矩阵、对称矩阵 若若n n阶矩阵阶矩阵A A满足满足 aij= aji 0i,jn-1 则称为则称为n n阶对称矩阵。阶对称矩阵。 特殊矩阵特殊矩阵: 非零元在矩阵中的分布有一定规则非零元在矩阵中的分布有一定规则 例如例如: 三角矩阵三角矩阵 对角矩阵对角矩阵a00a11an-1n-1a00 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* *(n+1)/2(n+1)/2个元的空间中。不失一般性，我们可以个元的空间中。不失一般性，我们可以以行序为主序存储其下三角（包括对角线）中的元。以行序为主序存储其下三角（包括对角线）中的元。2 2、三角矩阵、三角矩阵 所谓下（上）三角矩阵是指矩阵的上（下）三角所谓下（上）三角矩阵是指矩阵的上（下）三角（不包括对角线）中的元均为（不包括对角线）中的元均为常数常数c c或或零零的的n n阶矩阵。阶矩阵。 对于三角矩阵，则除了和对称矩阵一样，只存对于三角矩阵，则除了和对称矩阵一样，只存储其下（上）三角中的元之外，再加一个存储常数储其下（上）三角中的元之外，再加一个存储常数c c的存储空间即可。的存储空间即可。cc下三角矩阵下三角矩阵上三角矩阵上三角矩阵3 3、对角矩阵、对角矩阵 所有的非零元都集中在以主对角线为中心的带状所有的非零元都集中在以主对角线为中心的带状区域中。即除了主对角线上和直接在对角线上、下区域中。即除了主对角线上和直接在对角线上、下方若干条对角线上的元之外，所有其它的元皆为零。方若干条对角线上的元之外，所有其它的元皆为零。 对于对角矩阵，也可按某个原则（或以行为主，对于对角矩阵，也可按某个原则（或以行为主，或以对角线的顺序）将其压缩存储到一维数组上。或以对角线的顺序）将其压缩存储到一维数组上。n*n稀疏矩阵的压缩存储稀疏矩阵的压缩存储 假设假设 m 行行 n 列列的矩阵含的矩阵含 t 个非零元素个非零元素，则称则称为稀疏因子稀疏因子。 通常认为通常认为 0.05 的矩阵为稀疏矩阵。的矩阵为稀疏矩阵。何谓稀疏矩阵？何谓稀疏矩阵？nmt 如果一个矩阵中非零元素的个数远远小于矩阵如果一个矩阵中非零元素的个数远远小于矩阵元素的总数，且非零元素的分布无一定规律，元素的总数，且非零元素的分布无一定规律，则称之为稀疏矩阵。则称之为稀疏矩阵。 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)对应对应的元素；的元素； 能尽可能快地找到同一行或同一列的能尽可能快地找到同一行或同一列的非零元。非零元。三元组表示法三元组表示法 用一个线性表来表示稀疏矩阵，线性表的每个用一个线性表来表示稀疏矩阵，线性表的每个结点对应稀疏矩阵的一个非零元素。其中包括三个结点对应稀疏矩阵的一个非零元素。其中包括三个域，分别为该元素的域，分别为该元素的行下标行下标、列下标列下标和和值值。结点间。结点间的先后顺序按矩阵的的先后顺序按矩阵的行优先行优先顺序排列（跳过零元顺序排列（跳过零元素），将线性表用顺序的方法存储在连续的存储区素），将线性表用顺序的方法存储在连续的存储区里。里。顺序存储顺序存储5.4 广义表的类型定义广义表的类型定义一、广义表的定义一、广义表的定义广义表：是线性表的推广，也称为列表，是广义表：是线性表的推广，也称为列表，是n个单元素或子表所个单元素或子表所组成的有限序列。记作组成的有限序列。记作 LS=( 1, 2, n) 其中：其中：LS是广义表的是广义表的名称名称，n是其是其长度长度； i 可以是单个元素，也可以是广义表，分别称为广义表可以是单个元素，也可以是广义表，分别称为广义表LS的的原子原子和和子表子表。 用大写字母表示广义表的名称，小写字母表示原子；用大写字母表示广义表的名称，小写字母表示原子； 当广义表当广义表LS非空时，称第一个元素非空时，称第一个元素 1为为LS的的表头表头，称其，称其余元素组成的表（余元素组成的表（ 2, 3，, n) 是是LS的的表尾表尾。A=( ) -A是一个空表，它的长度为零是一个空表，它的长度为零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)DEFa( ) d( )bec/- - - - -广义表的头尾链表存储表示- - - - -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)原子和子表所在层次清晰最高层的表结点个数为广义表长度非空广义表的头指针均指向一个表结点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，）的存储地址是_。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*k58若将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