数据结构（自考） 课件 第四章数组广义表和串

全国高等教育自学考试指定教材

计算机及应用专业（专科段）数据结构第四章数组、广义表和串学习目标掌握数组、广义表和串的基本概念掌握数组按行主序及按列主序的存储方式及二维数组地址计算方法掌握特殊矩阵的存储方式及相应的地址计算方法理解广义表的概念，掌握广义表的表示及基本运算了解模式匹配概念，掌握串的模式匹配算法本章主要内容数组及广义表12串第一节

数组及广义表数组是程序设计语言中的重要语法成分，很多语言都定义了数组类型以C语言为例，它定义了一维数组，数组元素还可以是数组，由此得到数组的数组，即多维数组一般地将n（n≥2）维数组看作是n-1维数组的数组从数据结构的角度来理解，一维数组可以作为线性表的存储结构，数组中保存的各元素可以组成一个线性表多维数组在系统内部都对应一个隐含的一维数组，所以多维数组也是一种线性表例如二维数组就是以一维数组为元素的线性表数组的每个元素都是形如(index,value)的二元对，index是数组下标，也称为索引，value是对应于该下标的数值任何两个元素的index值都不相同数组的基本操作Create(); //创建一个空的数组Store(index,value);//添加数据(index,value)//同时删除有相同index值的数据对（若存在）Retrieve(index);//返回下标为index的value值示例用数组表示一个星期每天的最高温度hightem={(星期日,30),(星期一,28),(星期二,29),(星期三,32),(星期四,28),(星期五,30),(星期六,31)}数组上的操作Store(星期一,29);Retrieve(星期五);也可以约定使用0到6来分别表示星期日到星期六，此时，数组hightem可表示为hightem={(0,30),(1,28),(2,29),(3,32),(4,28),(5,30),(6,31)}数组的顺序存储方式数组的顺序存储有两种形式。以二维数组为例，它的元素可以按行排列，也可以按列排列所谓按行排列，就是先排数组的第一行，紧随其后排第二行，依此类推所谓按列排列，就是先排数组的第一列，紧随其后排第二列，依此类推最终都是将数组中的全部元素排列成一个序列C语言中多维数组下标的形式：[i1][i2][i3]…[ik]ij（1≤j≤k）为非负整数声明值为整型类型的k维数组DkArrayintDkArray[u1][u2][u3]…[uk];每一维的下标取值范围是：0≤ij<uj（1≤j≤k）数组最多可容纳n=u1

u2

u3

…

uk个整数所需要的内存空间sizeof(DkArray)=n

sizeof(int)个字节若开始地址为start，则占用的空间将延伸至start+sizeof(DkArray)-1。intD2Array[3][6];对应一个3行6列的矩阵通常int占4个字节数组D2Array中含有18个元素共占用18

4=76个字节编号对上述的下标表格按行自上而下、同一行中自左至右进行连续编号，从0开始按行优先把二维数组中的下标映射到0到n-1之间的某个整数的方式称为行主序，也称为行主映射按列优先，对下标表格从第一列开始，从上到下进行连续编号，直到最后一列映射函数行主序所对应的映射函数为 map(i1,i2)=i1

u2+i2

其中u2是数组的列数列主序所对应的映射函数为 map(i1,i2)=i2

u1+i1

其中u1是数组的行数示例例4.2二维数组A[10][5]采用行主序方式存储，每个数据元素占4个存储单元，若A[0][4]的存储地址是1000，则A[8][4]的存储地址是多少？解：给定的数组A是10行5列，需要从A[0][4]的存储地址反推出数组A的首地址，然后再计算A[8][4]的存储地址行主序所对应的映射函数为map(i1,i2)=i1

u2+i2本题中：u2=5，map(0,4)=4每个元素占4个存储单元 A[0][0]的存储地址=1000-4

4=984根据计算公式，A[8][4]的映射编号是 map(8,4)=8

5+4=44存储地址为984+44

4=1160换一种计算方法A[0][4]和A[8][4]之间的元素个数是 8

5=40A[0][4]与A[8][4]之间的偏移量 =40

4A[8][4]的存储地址 =A[0][4]的存储地址+ A[0][4]与A[8][4]之间的偏移量 =1000+160=1160示例三维数组D3Array[3][2][4]按行主序下标排列的形式对于三维数组ThrDimenArray[u1][u2][u3]，其行主序的映射函数应为 map(i1,i2,i3)=i1

u2

u3+i2

u3+i3排列规律所有第一维值为i1的元素都排在第一维值大于i1的元素之前。第一维值相同的元素数目为u2

u3。因此第一维值小于i1的元素数目为i1

u2

u3，第一维值等于i1且第二维值小于i2的元素数目为i2

u3，第一维值等于i1第二维值等于i2且第三维值小于i3的元素数目为i3矩阵的压缩存储对称矩阵和三角矩阵从节省存储空间的角度考虑，对称矩阵和上（下）三角矩阵，都可以只保存矩阵中约一半的元素，从而可以节省差不多一半的存储空间这样的存储形式称为压缩存储

压缩存储对于对称矩阵，因为对角线以上及以下的元素对称相等，所以只需要保存其中的一半及对角线上的元素即可对于上三角矩阵或下三角矩阵，仅保存上三角部分或下三角部分的元素，另外一半的零元素不再保存若矩阵有n行n列，则这三种形式下需要保存的元素个数为n

(n+1)/2三角部分

稀疏矩阵稀疏矩阵该矩阵只有10个非零元素，每个非零元素用一个三元组表示

三元组表三元组表应是一个有序序列，通常按行主序次序排列，即先按行的大小排列，同一行的三元组再按列的大小排列对应前例的三元组表i0012234455j1200521405v891-3121624615-7稀疏矩阵的存储结构typedefstruct{ inti,j; //存储非零元素的下标 ELEMTypev; //存储非零元素的值}triTerm;typedefstruct{ introws,cols; //矩阵的行数、列数 intterms; //非零元素个数 triTermtri[maxSize]; //三元组表}SparseMatrix;输入三元组生成三元组表的程序矩阵转置矩阵转置即是行、列互换，i行的元素放置到i列，这也意味着，j列的元素放置在j行。如果矩阵是n

m的，则转置后得到的矩阵是m

n的很容易想到，将三元组表中的每个三元组项的i与j互换，即可得到转置后矩阵的三元组表但是这样转换后得到的三元组表不再按行主序排列，不便于后续操作的实现所以要实现的矩阵转置程序，必须得到一个按行主序排列的三元组表思路可以像readSparseMatrix函数那样处理，读入原矩阵的一个三元组，插入到目标矩阵的三元组表中可以使用一个临时计数数组，记录原矩阵的每个三元组在目标矩阵的三元组表中的插入位置，以辅助完成转置操作，由此避免了三元组的移动，高效率地实现转置操作不失一般性，设原矩阵A的行数是rows，列数是cols。则转置后矩阵B的行数是cols，列数是rows。三元组的个数没有改变A中处于0列的元素，将是B中处于0行的元素。所以B的三元组表中的最前面的元素，是A中列值为0的元素。接下来是A中列值为1的元素，依此类推，最后是A中列值为cols-1的元素。使用临时数组ColSize来保存统计结果前例中的矩阵，临时数组ColSize内容在B的三元组表中，为各行元素预留位置01234532201201234567890行元素1行元素2行元素4行元素5行元素对于A的三元组(0,1,8)和(4,1,24)，转置后分别为(1,0,8)和(1,4,24)，它们应该保存在上述第二部分，即位置3和位置4中故由ColSize数组中的元素值，从前向后依次相加，得到RowNext的值012345603577810转置算法数组的应用走迷宫是实验心理学中的一个经典问题不失一般性，使用一个m行n列的矩阵maze表示迷宫，让机器人R寻找从maze[0][0]（左上角，入口）到maze[m-1][n-1]（右下角，迷宫的唯一出口）间的可行路径任一时刻，R在迷宫中的位置用行、列号[i][j]来表示，这时它有4个方向可以进行试探，即从图上看是上、下、左、右设下一位置是[g][h]，显然[g][h]的值与走的方向有关若从[i][j]向右走一步，则g=i;h=j+1若向上走一步，则g=i-1;h=j当R走到迷宫边缘时，可以试探的方向不足4个，需要进行边界的判断为了避免过多的边界条件判断，可以把原来表示迷宫的矩阵maze扩大一圈，变成m+2行n+2列，并且令表示边缘的这些矩阵元素全为1编写计算机程序求解迷宫问题，一般采用一步一探查并加回溯的方法。称R所在的位置为当前位置，当R走到一个位置时，除了进入当前位置的方向外，可以在其他3个方向进行探查，选择可行并尚未走过的方向走一步，所处的新位置变为当前位置，并再次探查下一个可行位置；当3个方向都走不通时，只能沿来路退到前一个位置再选择其他方向，这一步骤称为回溯。回溯后的位置又变为当前位置在探查的过程中，因为有回溯，所以可能会走到原来已走过的位置，为避免重复并找出确定的可行路径，需要一个栈记录已走过的每一步的位置及方向，另外还需要设置一个与原来迷宫矩阵同样大小的标志矩阵mark，以对走过的位置进行标记mark矩阵的初值全为0，当R走到maze[i][j]位置时，则置mark[i][j]为1R走迷宫的步骤令R处在迷宫入口，此为当前位置在当前位置上，依右、下、左、上的顺序探查前进方向向可以进入的方向前进，即目标位置的maze和mark值全为0。前进一步后，目标位置为当前位置，将mark矩阵的当前位置标记为1，并且将前一位置的位置值及进入当前位置的方向入栈重复步骤②和③若找不到前进通路，则从原路后退一步（退栈），改变探测方向，再重复步骤②、③，以寻找另一条新的通路重复步骤②~⑤，直到走出迷宫或宣布迷宫无通路为止走步时相邻两个位置之间行、列值的关系若向右走，则行值不变，列值加1若向下走，则行值加1，列值不变若向左走，则行值不变，列值减1若向上走，则行值减1，列值不变将这4组值定义在move矩阵中列号0、1、2、3分别对应着方向右,下,左,上行号0和1分别对应着位置坐标i和j

走迷宫算法走迷宫算法广义表广义表是线性表的推广，也称为列表是由n(n≥0)个表元素组成的有限序列 LS=(a0,a1,…,an-1)LS是广义表的名称n是表的长度当n=0时称为空表ai(0≤i≤n-1)的类型可以不完全一致，既可以是单个元素（称为原子），也可以是广义表（称为子表）原子不可再分第一个元素a0称为LS的表头（Head），其余元素组成的表(a1,a2,…,an-1)称为LS的表尾（Tail）广义表中括号的最大嵌套层数定义为表的深度空表的深度为1，原子的深度为0其他情况，可以递归求解广义表的深度=max{各子表的深度}+1示例A=()A是空表，长度为0，深度为1B=(())B的长度为1，深度为2C=(6,2)C的长度为2，深度为1，两个元素都是原子D=('a',(5,3,'x’))D的长度为2，深度为2，含一个原子及一个子表示例E=(C,D,A)E的长度为3，深度为3，含3个子表F=(C)F的长度为1，深度为2，含1个子表G=(4,G)G的长度为2，深度为∞，递归表各表的表头和表尾示例Head(B)=()，Tail(B)=()Head(C)=6，Tail(C)=(2)Head(D)='a'，Tail(D)=((5,3,'x'))Head(E)=C，Tail(E)=(D,A)Head(F)=C，Tail(F)=()Head(G)=4，Tail(G)=(G)空表没有定义表头和表尾，所以不能求表A的表头和表尾表E的表头是表C第二节

串串（String）也称为字符串，是由零个或多个字符组成的有限序列记为：s="a0a1…an-1"，(n≥0)，其中，s是串名，使用双引号括起来的字符序列是串的值串中的每个符号ai(0≤i≤n-1)可以是字母、数字或其他字符，其在串中的次序定义为该符号的位置位置从0开始串中字符个数n称为串的长度n=0时称为空串串s中任意个连续字符组成的子序列称为串s的子串，相应地s称为主串子串在主串中首次出现时子串首字符对应于主串的符号位置，定义为子串在主串中的位置设有串s1="Thisisastring"，s2="is"s1为主串，s2是s1的子串s2在s1中的位置为2空串是任意串的子串任意串是其自身的子串串的模式匹配在主串中寻找子串（第一个字符）在主串中的位置，称为串的模式匹配子串又称为模式，主串称为目标朴素的模式匹配算法（B-F算法）设主串T="aaaaab"，模式串P="aab"，采用B-F算法的匹配过程在每趟匹配中，主串与模式串的字符之间的比较次数有3次，共4趟，所以共进行了12次比较主串aaaaab

模式串aab

第1趟

aab

第2趟

aab

第3趟

aab第4趟朴素的模式匹配算法简单，但时间效率不高设主串长度为n，模式串长度为m。如果每次都是比较到模式串最后一个字符时才出现失配，且主串的最后m个字符与模式串匹配成功，这就出现了最坏情况此时，每一趟都进行了m次比较，共比较了n-m+1趟，故总比较次数将达到(n-m+1)

m算法的最坏情况时间复杂度为O(n

m)改进的模式匹配算法（KMP算法）设主串T="b0b1b2…bm-1…bn-1"，模式串P="p0p1p2…pm-1"，进行第一趟匹配时，T与P的对应字符进行比较主串Tb0b1b2…bm-1…bn-1模式串Pp0p1p2…pm-1匹配过程中，若某一趟比较时出现失配，模式串P需要整体右移，那么P右移的位数应该是多少呢模式串P的首字符p0对应于主串的字符bs，且前j(j≥0)对字符都匹配成功，第j+1对字符匹配不成功则有bsbs+1bs+2…bs+j-1=p0p1p2…pj-1如果下一趟比较时模式串P与主串T匹配，也就是P与主串中从bs+1开始的子串匹配，则必须满足p0p1p2…pj-1…pm-1=bs+1bs+2bs+3…bs+j…bs+m若知道p0p1…pj-2

p1p2…pj-1，则立刻可以断定p0p1…pj-2

bs+1bs+2…bs+j-1，即下一趟必不匹配同样地，若p0p1…pj-3

p2p3…pj-1，则再下一趟也不匹配，因为p0p1…pj-3

bs+2bs+3…bs+j-1如果找到一个k值，满足p0p1…pk+1

pj-k-2pj-k-1…pj-1但p0p1…pk=pj-k-1pj-k…pj-1则有p0p1…pk=bs+j-k-1bs+j-k…bs+j-1那么，下一趟可以直接用pk+1与bs+j进行比较如何确定k值呢对于不同的失配位置j，k的取值是不同的，它仅依赖于模式串P本身前j个字符的构成，而与主串无关设模式串P=p0p1…pm-2pm-1，定义特征向量next

从特征向量next的定义可知，next(0)=-1，next(1)=0。对于j≥2，要去查看模式串前j个字符组成的子串p0p1…pj-2pj-1的前缀和后缀，找到相等的两个，next值是相等的前缀后缀的长度模式串Pp0p1…pkpk+1…pj-k-1pj-k…pj-1

…==

=模式串P

p0p1…pkp0p1...pj-2pj-1的前缀和后缀也可能有重叠示例设模式串p="abaabcac"，求它的特征向量。next(0)=-1，next(1)=0j=2时，p0p1="ab"，next(2)=0j=3时，p0p1p2="aba"，p0=p2，k=0，next(3)=1j=4时，p0p1p2p3="abaa"，p0=p3，k=0，next(4)=1j=5时，p0p1p2p3p4="abaab"，p0p1=p3p4，k=1，next(5)=2j=6时，p0p1p2p3p4p5="abaabc"，没有相等的子串，next(6)=0j=7时，p0