数据结构与算法分析新视角（第2版） 课件 第4-6章 数组和串、树、图

内容特殊的线性表多维数组与字符串Chapter

4DataStructuresandAlgorithmAnalysis主要内容字符串的定义及存储方法模式匹配方法字符串使用二维数组表示矩阵及运算三角矩阵、对称矩阵、稀疏矩阵等各种压缩存储方法实现矩阵运算二维数组学习目标掌握多维数组的存储结构，熟悉特殊矩阵的压缩存储方法；熟悉稀疏矩阵三元组从顺序表、行的单链表到十字链表等到多种存储结构的演变过程；了解串操作的应用方法和特点，理解串匹配算法。数组与字符串4字符串字符串是基于数组的一种重要数据结构数组数组是一组相关的同类型数据的集合，它们与实际应用中数据的自然组织方法直接吻合，有着广泛的用途。多维数组的概念在数值计算和图形应用方面非常有用数组在计算机中的连续存储方式反映了内存中数据组织的底层机制。数组与线性表的关系5线性关系运算受限元素扩展元素受限栈队列串多维数组线性表、栈和队列等，均是线性结构，其中的数据元素是非结构的原子类型。数组可以看成是线性表的扩展，即表中的元素本身也是一种数据结构。数组与线性表的关系6线性关系运算受限元素扩展元素受限栈队列串多维数组线性表、栈和队列等，均是线性结构，其中的数据元素是非结构的原子类型。数组可以看成是线性表的扩展，即表中的元素本身也是一种数据结构。4.1CONTENTS多维数组矩阵的压缩存储4.24.3字符串4.3本章小结4.1CONTENTS多维数组矩阵的压缩存储4.24.3字符串4.3本章小结关于数组的种种9数组简单数组应该是我们最熟悉的数据组织形式之一。由于数组中各元素具有统一的类型，并且数组元素的下标一般具有固定的上界和下界，因此，数组的处理比其他复杂的结构更为简单。数组与数据结构各种数据结构的顺序存储分配，也都是借用一维数组来描述它们的存储结构。数组的维多维数组是一维数组的推广。

数组常见

几乎所有的高级程序设计语言都包含数组这种数据的结构形式。本节将从数据结构的角度，简单讨论数组的逻辑结构及其存储方式。4.1多维数组4.1.14.1.2数组的概念数组的存储结构4.1多维数组4.1.14.1.2数组的概念数组的存储结构数组的概念12a11a12…a1n

a21a22…a2n

…………

am1am2…amn

Amxn=a11a12a1n

a21a22…a2n

………

am1am2amn

Amxn=（a）（b）Amxn=[[a11a12…a1n],[a21a22…a2n],…,[am1am2…amn]]（c）是由类型相同的数据元素构成的集合，每个数据元素称为一个数组元素（简称元素）。数组（Array）一个行向量形式的线性表一个列向量形式的线性表数组的特点13元素推广性元素本身可以具有某种结构，而不限定是单个的数据元素。元素同一性元素具有相同的数据类型。关系确定性每个元素均受n（n≥1）个线性关系的约束，元素个数和元素之间的关系一般不发生变动。如二维数组的元素有2个下标4.1多维数组4.1.14.1.2数组的概念数组的存储结构数组的存储结构1515二维数组顺序存储方式以行序为主序(低下标优先)以列序为主序(高下标优先)存得进取得出A计算机的存储结构是一维的，而数组一般是多维的，怎样存放？思考与讨论数组结构特点16数目固定（1）数据元素数目固定，一旦定义了一个数组结构，就不再有元素个数的增减变化。类型相同（2）数据元素具有相同的类型。关系固定（3）数据元素的下标关系具有上下界的约束且下标有序。数组基本运算17（1）给定一组下标，存取相应的数据元素。（2）给定一组下标，修改相应的数据元素中某个数据项的值。数组运算数组的顺序存储1819aij之前共有((i-1)*n+j-1)个元素基地址aij的存储地址=Loc(aij

)=Loc(a11

)+((i-1)*n+j-1)*L数组的顺序存储2021aij

之前共有((j-1)*m+i-1)个元素基地址aij

的存储地址=Loc(aij

)=

Loc(a11

)+((j-1)*m+i-1)*L数组的顺序存储和访问22设数组a[1…60,1…70]的基地址为2048，每个元素占2个存储单元，若以列序为主序顺序存储，求元素a[32,58]的存储地址。注：a[1…60,1…70]是数组的一种表示方法，表示行优先的二维数组，行下标范围为1到60，列下标范围为1到70。解：数组行数m=60-1+1=60；

列数n=70-1+1=70；行下标i=32;列下标j=58;元素长度L=2；列优先元素求址公式Loc(aij)=Loc(a11)+[(j-1)*m+(i-1)]*L得：LOC(a32,58)=2048+[(58-1)*60+(32-1)]*2＝8950i、j均从0开始，求址公式为Loc(aij)=Loc(a00)+[j*m+i)]*LLOC(a32,58)=2048+[58*60+32]*2＝9072例思考与讨论若数组是a[0…59,0…69]，结果是否仍为8950？数组的顺序存储和访问23Loc(aij)=Loc(a00)+[j*m+i)]*L4.1CONTENTS多维数组矩阵的压缩存储4.24.3字符串4.3本章小结特殊矩阵的存储问题25数值分析计算中常常有高阶矩阵 值相同元素或者零元素分布有一定规律的矩阵对称矩阵上三角矩阵特殊矩阵如何高效存储上述矩阵思考与讨论节省存储空间，节约传输时间例特殊矩阵的存储问题26我们可以设想把相同的数据只存储一次，来实现数据的压缩存储。节省存储空间，节约传输时间。 值相同元素或者零元素分布有一定规律的矩阵特殊矩阵这在矩阵规模很大时（即高阶矩阵），可获得很高的效率。27【知识ABC】数据压缩

数据压缩是指在不丢失信息的前提下，缩减数据量以减少存储空间，提高其传输、存储和处理效率的一种技术方法。数据压缩方法——去除掉确定的或可推知的信息，而保留不确定的信息。矩阵压缩存储时会有什么问题？可以采用的方法是什么？思考与讨论A数据存储数据恢复（1）相同的数据只存储一次；（2）零元素不占存储空间，数据存放到一维数组中找到同一元素在一维数组与矩阵中的对应关系即可恢复原有的矩阵形式B矩阵压缩存储方法28确定存放压缩后数据的向量的空间大小；确定二维数组下标i,j与向量下标k的关系。步骤1步骤2矩阵的压缩存储2929特殊矩阵的压缩存储稀疏矩阵的压缩存储三元组表的存储结构十字链表的存储结构4.2矩阵的压缩存储4.2.14.2.24.2.34.2.4对称矩阵的压缩存储三角矩阵的压缩存储对角矩阵的压缩存储稀疏矩阵的压缩存储4.2矩阵的压缩存储4.2.14.2.24.2.34.2.4对称矩阵的压缩存储三角矩阵的压缩存储对角矩阵的压缩存储稀疏矩阵的压缩存储32特殊矩阵压缩存储——对称矩阵

在一个n阶方阵A中，若元素满足下述性质，则称A为对称矩阵。

aij=aji(0≦i,j≦n-1)对称矩阵用向量存储，对称矩阵元素可以只存储下或上三角部分对称矩阵压缩存储方法3334k等于aij前的元素个数（此处k的值从0开始）：k=1+2+3+...+i+j=i(1+i)/2+j（i≥j）4.2矩阵的压缩存储4.2.14.2.24.2.34.2.4对称矩阵的压缩存储三角矩阵的压缩存储对角矩阵的压缩存储稀疏矩阵的压缩存储三角矩阵的压缩存储36上三角矩阵下三角矩阵除了存储主对角线及上（下）三角中的元素外，再加一个存储常数c的空间。三角矩阵压缩存储方法设n阶方阵A，若其下三角的元素除对角线外均为常数c，即aij=c，0≤j<i<n，则称该方阵为上三角矩阵。三角矩阵三角矩阵的压缩存储37三角矩阵中的重复元素c可只用一个存储空间，其余的元素正好有n(n+1)/2个，因此，三角矩阵可压缩存储到长度为n(n+1)/2]+1的向量中，其中c存放在向量的最后一个位置下三角矩阵K值i、j关系a[i,j]=sa[k]i(i+1)/2+j当aij在下三角区域，i>=jcn(n+1)/2当aij在上三角区域，i<j下三角矩阵压缩

4.2矩阵的压缩存储4.2.14.2.24.2.34.2.4对称矩阵的压缩存储三角矩阵的压缩存储对角矩阵的压缩存储稀疏矩阵的压缩存储对角矩阵压缩存储39存储所有非零元素对角矩阵压缩存储方法所有非零元素都集中在以主对角线为中心的带状区域中的方阵，也称为带型矩阵。对角矩阵三对角矩阵压缩方法一40设有n阶三对角矩阵A[n][n],将三条对角线上的元素逐行存放于数组B[M]中，使得B[k]=A[i][j],给出i、j与k的对应关系。三对角矩阵压缩方法一41三对角矩阵压缩方法二42只存储带内的元素4.2矩阵的压缩存储4.2.14.2.24.2.34.2.4对称矩阵的压缩存储三角矩阵的压缩存储对角矩阵的压缩存储稀疏矩阵的压缩存储稀疏矩阵的压缩存储44设矩阵Amn中有s个非零元素，若s远远小于矩阵元素的总数（即s<<m×n），则称A为稀疏矩阵（sparsematrix）。如何进行稀疏矩阵的压缩存储？讨论一下稀疏矩阵令e=s/(m*n)，称e为矩阵的稀疏因子。通常认为e≦0.05时称之为稀疏矩阵矩阵的稀疏因子稀疏矩阵及其应用45PageRank算法是用于标识网页的等级/重要性的一种方法，是Google用来衡量一个网站好坏的唯一标准。PageRank算法首先要把各个网页及网页间的联系存储到计算机中，存储可以用矩阵来实现（相关内容见第6章）。由于互联网上网页的数量是巨大的，则这样的矩阵元素是网页数目的平方。如果我们假定有10亿个网页，那么这个矩阵就有100亿亿个元素。PageRank算法中要用到矩阵相乘，对应这样大的矩阵相乘，计算量是非常大的。PageRank算法的发明者LarryPage和SergeyBrin两人利用稀疏矩阵计算的技巧，大大的简化了计算量。签名扫描图，白色像素远远多于黑色像素PageRank算法稀疏矩阵的实例46电信总局到其各支局间的通信问题例双面镶边的块对角矩阵——稀疏矩阵用连线表示各局间有通信关系电信总局支局稀疏矩阵的压缩存储4747存储所有非零元素稀疏矩阵压缩存储原则前面讲述的各种特殊矩阵，其非零元素的分布都是有规律的，因此总能找到一种方法将它们压缩存储到一个向量中，并且一般都能找到矩阵中的元素与该向量的对应关系，通过这个关系，仍能对矩阵的元素进行随机存取。稀疏矩阵非零元素分布无规律，如何进行压缩存储？记位置，记值稀疏矩阵的压缩存储4848稀疏矩阵常用压缩存储形式位置下标、元素值带行指针向量的单链表表示法十字链表法三元组表1链表存储2稀疏矩阵存储——三元组表49三元组表存稀疏矩阵中各非零元的值、行列位置和矩阵的行列数三元组表存储原则稀疏矩阵的压缩存储——三元组顺序表【例4-3】用三元组表的形式存储稀疏矩阵。解：设稀疏矩阵为M[6,7]，为方便管理，可以把矩阵的行、列、非零元素个数信息，专门用三元组的第0行来记录。50稀疏矩阵的压缩存储——三元组顺序表51matrix[MAX]0矩阵行数矩阵列数非零元个数1行下标列下标非零元素值2行下标列下标非零元素值…MAX-1行下标列下标非零元素值matrix[0]用于存储矩阵行数、列数、非零元个数structnode{introw,col;//非零元素的行下标和列下标

intvalue;//非零元素值};typedefstructnodeNODE;NODEmatrix[MAX]；数据结构设计稀疏矩阵的压缩存储——链式存储结构52valuenextcol结点结构设计

typedefstructnode{intcol,value;structnode*next;}linklist;linklist*TAB[ROW];#defineROW4稀疏矩阵的压缩存储——链式存储结构53十字链表的存储结构54

structnode{introw,col,value;structnode*down,*right;};typedefstructnodeNODE;三元组rowcolvaluedownright向下域：链接同一列下一个非0元素向右域：链接同一行下一个非0元素十字链表的存储结构数据结构设计矩阵的压缩存储小结55矩阵压缩存储：值相同的元素分配一个存储空间，零元素不分配存储空间；稀疏矩阵的压缩存储保存非零元素的值及其在矩阵中的位置；特殊矩阵的压缩存储：确定元素的存储位置与元素在矩阵中的位置的对应关系；4.1CONTENTS多维数组矩阵的压缩存储4.24.3字符串4.3本章小结字符编译字符串处理文献查询机器翻译源码翻译为机器码利用计算机把一种自然源语言转变为另一种自然目标语言的过程，一般指自然语言之间句子和全文的翻译。计算机将检索者输入检索系统的检索提问(即检索标识)按检索者预先制定的检索策略与系统文档（机读数据库）中的存贮标识进行类比、匹配运算,通过“人机对话”而检索出所需要的文献内容特殊的线性表——字符串搜索引擎高级语言提供串处理功能搜索引擎是指根据一定的策略、运用特定的计算机程序从互联网上搜集信息，在对信息进行组织和处理后，为用户提供检索服务，将用户检索相关的信息展示给用户的系统。非数值数据4.3字符串4.3.14.3.24.3.3字符串的定义字符串的存储结构字符串的查找方法4.3字符串4.3.14.3.24.3.3字符串的定义字符串的存储结构字符串的查找方法字符串定义60串是一种特殊的线性表，它是由n(≥0)个字符组成的有限序列

定义

记作s=“a1,a2,a3,...an”s-串名，a1,a2,a3,...an串值ai是串中字符，n是串的长度高级语言提供串处理功能a1a2...ai...ai是字符an串的例子61串的实例串长度注“Thisisastring”16空格也算一个字符“string”6“”1空格串:仅由一个或多个空格组成的串“”0空串:长度为0的串称为空串，它不包括任何字符“你好”4串中所包含的字符可以是字母、数字或其他字符，这依赖于具体计算机所允许的字符集指的是串中所包含的字符个数。串长度62两个串相等，当且仅当两个串长度相同，并且各个对应位置的字符都相同。串的有关术语串中任意连续的字符组成的子序列称为该串的子串;子串t在主串S中的位置是指主串s中第一个与t相同的子串的首字母在主串中的位置;子串子串的位置串相等例：c=“DATASTRUCTURE”，f=“DATA”f是c的子串例：s=“ababcabcac”,t=“abc”子串t在主串s中的位置为3串的基本操作63（1）字符串的长度计算（2）字符串的复制（3）字符串的连接（4）字符串的替换（5）字符串的插入（6）字符串的删除（7）字符串的比较（8）抽取字符串（9）字符串的分割（10）字符串的查找由于串的匹配（字符串查找）算法的重要性与应用的广泛性，因此对它做一专门的介绍。由于在许多高级语言中都提供相应的串操作处理功能，故对串的操作不再赘述。4.3字符串4.3.14.3.24.3.3字符串的定义字符串的存储结构字符串的查找算法字符串的存储结构65

由于串是一种特殊的线性表，它的每个结点仅由一个字符组成，因此存储串的方法也同样可以采用顺序存储或链式存储。顺序串66串的字符顺序地存储在内存一片相邻的空间顺序串串的顺序存储——方案1012345…abcdef…空闲curlen用一个指针来向指最后一个字符typedefstruct{charch[MAXSIZE];intcurlen;}SeqString;数据结构设计串的顺序存储——方案2串长chars[MAXSIZE+1];0123456…6abcdef空闲用数组的0号单元存放串的长度串值从1号单元开始存放直接记录串长数据结构设计69串的顺序存储——方案3串终结符chars[MAXSIZE+1];0123456…abcdef\0空闲在串尾存储一个不会在串中出现的特殊字符作为串的终结符数据结构设计串的顺序存储特点70预定义串的最大长度

使得串的某些操作受限（截尾），如串的连接、插入、置换等运算；插入和删除操作不方便需要移动大量的字符串的块链存储结构71abcdefg结点大小为1的链串可用单链表方式来存储串值。串的链式存储结构简称为链串。链串与单链表的差异只是它的结点数据域为字符。链式串串的块链存储结构72abcdefg结点大小为1的链串typedefstructlinknode{chardata;structlinknode*next;}linkstring;数据结构设计单字符链串存储结构设计的优缺点是什么？思考&讨论讨论：每个链结点中只放一个字符，插入、删除、求长度等运算非常方便，但存储效率低。改进的方法，可以在一个链结点中存储多个字符，这样就可以改善存储效率，在处理不定长的大字符串时很有效，这是顺序串和链串的综合折中，称为块链结构。串的块链存储结构73abcdefg结点大小为1的链串typedefstructlinknode{chardata[4];structlinknode*next;}linkstring;abcdefg\0结点大小为4的链串typedefstructlinknode{chardata;structlinknode*next;}linkstring;数据结构设计串的块链存储结构74【例4-4】结点大小为4的链串“abcdefg”，在第n个字符后插入“xyz”。如n=3，对应链串中的字符c。设计插入方案。串的索引存储方法75s16s24...........pleaseek..带长度的串索引表namelengthstadrtypedefstruct{charname[maxsize];//串名intlength;//串长度char*stadr;//串起始地址}lnode设：S1=“please”，S2=

“seek”.用串变量的名字作为关键字组织起来的索引表，表中串名与串值之间一一对应。1串的索引存储结构76s1s2...........abcdefgbcd..带头尾指针的串索引表nameenadrstadrtypedefstruct{charname[maxsize];//串名char*stadr,//串头地址char*enadr;//串尾地址}enode;2串的索引存储方法设：S1=“abcdefg”，S2=“bcd”一个串设置两个指针，一个指向串开头，一个指向串末尾77s10s21bcd\0........abcdefg\0typedefstruct{charname[maxsize];inttag；//特征位

union{char*stadr;//特征位为0，放串首地址charvalue[4];//特征位为1，放串值}uval;}tagnode

nametagstadr/value..带特征位的串索引表3串的索引存储方法设：S1=“abcdefg”S2=“bcd”在索引表中设置一标志量tag来标示存储的是串地址还是串内容，这样设计可以让较短的串存取便捷一些。78设：s1=“GOOD”

s2=

“DAY”name……namelinkstruaStr[N]linknextdatanextdatalinkN-10串链结构数组串链结点s1s2...GN-10OOD∧DAY∧链式串索引表4串的索引存储方法79name……namedatanextnamelink串链结构linkstru串链结点linknodelinkstruaStr[N]linknextdatanextdatalinkN-10串链结构数组串链结点

//

串链数组定义typedefstruct{charname[maxsize];//串名linkstring*link;}linkstru;linkstruaStr[N];

//串链结点定义typedefstructlinknode{chardata;structlinknode*next;}linkstring;串的索引存储方法4.3字符串4.3.14.3.24.3.3字符串的定义字符串的存储结构字符串的查找算法

字符串的查找——模式匹配81搜索引擎——做字符串査找匹配的工作。模式匹配算法是搜索引擎的关键，它直接影响系统的实时性能。

字符串的查找——模式匹配82模式匹配（PatternMatching）模式匹配(PatternMatching)也称为串匹配(StringMatching)子串（模式串）在主串（目标串）中的定位运算即在主串中找出子串出现的位置匹配结果成功失败返回t子串在s中的起始位置返回约定标记模式匹配算法83BF算法KMP算法BM算法84串的模式匹配——Brute-Force算法85功能描述输入输出BF模式匹配主串s的内容int不匹配：-1index子串t的内容匹配：子串在主串中的位置函数名形参函数类型#defineMaxSize100typedefstruct{charch[MaxSize];intlen;}SqString;函数框架设计数据结构设计串的模式匹配——Brute-Force算法86第一步细化第二步细化初始化设主串S的下标i=0；子串T的下标j=0从主串S的第1个字符起和模式T的第一个字符比较之当i、j分别小于S、T的串长若相同，则继续比较后续字符；

若：Si与Tj匹配，则i++，j++；否则从主串S的下一个字符起再重新和模式T的字符比较之；

否则：将i、j设置为下次将开始匹配的位置:

主串：i=i-j+1;

子串：j=0;直到整个T串扫描完毕若已经扫描完T串则返回“匹配”给出结果否则返回“不匹配”串的模式匹配——Brute-Force算法/*==============================================函数功能：BF算法­——求模式t在目标串s是否匹配函数输入：目标串s、模式串t函数输出：匹配成功：返回模式串t首次在s中出现的位置

匹配不成功：返回-1================================================*/87串的模式匹配——Brute-Force算法【例4-5】分析给定字符串S和T时，BF算法的执行次数两个字符串S和T分别为S=“abcdgggkh”（N=9）T=“gggk”（M=4）88匹配成功平均比较次数算法分析最好情形串的模式匹配——Brute-Force算法89【例4-6】分析给定字符串S和T时，BF算法的执行次数两个字符串S和T分别为：S=“ggggggggk”（N=9）T=“gggk” （M=4）算法分析最坏情形注意书中改错：S串中最后应该为k串的模式匹配——Brute-Force算法90算法分析最坏情形匹配成功平均比较次数串的模式匹配——Brute-Force算法91匹配算法是检测引擎的关键，它直接影响系统的实时性能。最坏情况下的时间复杂度O(m×n)（∵n>>m）最好情况下的时间复杂度O(m+n)串的模式匹配——在链串上的算法实现【例4-7】BF算法在链串上的实现用结点大小为1的单链表做串的存储结构，实现朴素的匹配算法。若匹配成功，则返回有效位移所指的结点地址，否则返回空指针。92分析：用结点大小为1的单链表做串的存储结构时，实现朴素的匹配算法很简单。只是现在的位移是结点地址而非整数，且单链表中没有存储长度信息。若匹配成功，则返回有效位移所指的结点地址，否则返回空指针。串的模式匹配——在链串上的算法实现93功能描述输入输出IndexLBF模式匹配主串s的地址子串在主串中的位置子串t的地址函数名形参函数类型typedefstructnode{charch;structnode*next;}LinkString;函数框架设计数据结构设计串的模式匹配——在链串上的算法实现94伪代码细化描述设sptr指向主串s开始比较地址sptr，tptr指向子串起始地址；当(两串均未处理到末尾)若(sptr结点值=tptr结点值)

sptr与tptr移动指向下一个结点否则first移动指向下一个开始比较的结点sptr指向主串s开始比较地址sptr，tptr指向子串起始地址；若tptr已指向链尾，即查找完毕，“匹配”返回first否则“不匹配”返回NULL串的模式匹配——在链串上的算法实现/*==============================================函数功能：BF算法在链串上的实现函数输入：目标串链表起始地址，模式串链表起始地址函数输出：匹配点地址=================================================*/95模式匹配算法96BF算法KMP算法BM算法串的模式匹配——KMP算法97BF算法KMP算法无回溯改进了回溯问题有回溯效率低D.E.Knuth与V.R.Prett和J.H.Morris共同提出，因此称为克努特-莫里斯-普拉特操作（简称KMP算法）。KMP算法思路：不回溯主串s的位置指针i，以提高搜索效率。算法关键点：模式串t位置指针j不能每次都从头开始，而是根据“失配”时的位置，决定下一次的开始位置。KMP算法测试1【例4-8】用KMP算法思路做串的匹配测试1设：T=“abcabcacab”S=“babcbabcabcaabcabcabcacabc”观察结果每次比较结束时，已比较子串中，前缀与后缀相同的部分，在下一次就可以跳过不再比较。99100每次比较结束时，已经比较子串中，前缀与后缀相同的部分——下一次就可以“跳过”不用再比较j=0，表示当前比较，第一个字符就不相等，下一次从主串结束位的下一个字符开始比较KMP算法测试1101j0

1

2

3

4

5

6

7

8

9T[j]abcabcacabnext[j]-1000123401结束位j=比较结束时，已经比较的子串长度【知识ABC】字符串的前缀与字符串的后缀字符串的前缀是指字符串的任意首部（最后一个字符除外）。如字符串“abbc”的前缀有“a”，“ab”，“abb”，字符串的任意尾部是字符串的后缀（第一个字符除外），“abbc”的后缀有“c”，“bc”，“bbc”。“前缀”指除了最后一个字符以外，一个字符串的全部头部组合；“后缀”指除了第一个字符以外，一个字符串的全部尾部组合。102串的模式匹配——模式串的next值103next函数定义j表示子串t比较结束位，i表示主串s结束位t0t1t2…tk

1表示模式串t的k位前缀，用STR1表示tj

ktj

k+1…tj

1表示结束位j前的k位子串，用STR2表示情形j值next[j]取值含义STR1=STR2非0k下一次比较从si和tk开始STR1和STR2不存在非00下一次比较从si和t0开始s与t当前比较第一个字符即不等0-1下一次比较从si+1和t0开始串的模式匹配——模式串的next值【例4-9】给出模式串T=“abcac”的next数组值。104串的模式匹配——模式串的next值105第一步细化从主串S的第1个字符起和模式T的第一个字符比较之若相同，则继续比较后续字符；否则，从主串S的当前字符起，和模式T的next字符比较之；给出结果第二步细化设主串S的下标i=0；子串T的下标j=0当i、j分别小于S、T的串长若：Si与Tj匹配，则i++，j++；否则：将i、j设置为下次将开始匹配的位置:主串：i不变;子串：j=next[j];若已经扫描完T串

则返回“匹配”否则返回“不匹配”串的模式匹配——模式串的next值106如j=4时，k的变化从1~3，t0依次要和t1、t2、t3比较：若t0=t3，则k=1若t0t1=t2t3，则k=2若t0t1t2=t1t2t3，则k=3实际的情形是：当t0=t1

时，才有可能k=3当t0=t2

时，才有可能k=2当t0=t3

时，才有可能k=1故求next[j]的过程，就是一个在T串中匹配T前缀的过程107串的模式匹配——模式串的next值108求next算法描述初始化起始位k=-1，j=0；（k=-1，标志下一次开始位：T串从0开始，S串从j++开始）在s串的有效范围内

S[j]与T[k]相等或k=-1j、k后移一位

下一次子串开始比较位next[j]=k；

否则，设置重新比较位置：j串不变，k串从next表中取得下一次开始的位置串的模式匹配109#defineMaxSize30//串结构typedefstruct{charch[MaxSize];//用数组存储串值

intlen;//串长度}SqString;数据结构设计串的模式匹配110功能描述输入输出求next值GetNext模式串结构SqString（next数组地址）（next数组地址）函数名形参函数类型/*=======================================函数功能：由模式串t求出next的值函数输入：模式串t，（next数组）函数输出：无=========================================*/函数框架设计串的模式匹配111功能描述输入输出KMP匹配算法KMPIndex目标串结构SqString模式串结构SqStringint-1：不匹配int值：匹配位置函数名形参函数类型/*==============================================函数功能：KMP算法­——求模式t在目标串s是否匹配函数输入：目标串s、模式串t函数输出：匹配成功：返回模式串t首次在s中出现的位置

匹配不成功：返回-1================================================*/书中改错=1，改为-1函数框架设计串的模式匹配112step1后不需要再和S[3]进行比较，可以将模式串一次向右滑动4个字符的位置，直接进行i=4，j=0时的字符比较。【例4-10】用KMP算法思路做串的匹配测试2串的模式匹配【例4-10】用KMP算法思路做串的匹配测试2113tj=tk时next[j]置-1next[j]取值为-1的含义：下一次比较从si+1和t0开始KMP算法中，如何改进重复的比较步骤？模式匹配算法效率分析114设主串s的长度为n,子串t长度为m算法程序段时间复杂度说明BFO(m*n)一般情形接近O(m+n)KMP求next数组O(m)仅当模式串与主串之间存在许多“部分匹配”的情况下，KMP算法才明显比BF算法快得多KMP匹配O(n)KMP算法最大特点：不需要回溯，在匹配过程中，对主串仅需从头至尾扫描一遍，对处理从外部设备输入的庞大文件很有效，可以边读入边匹配，而无须回头重读。模式匹配算法115BF算法KMP算法BM算法BM算法简介116算法模式串移动方向比较方向说明BF从左到右从左到右KMP从左到右从左到右实际应用并不多BM从左到右从右到左文本编辑器常采用算法效率：BM算法>KMP算法>BF算法4.1CONTENTS多维数组矩阵的压缩存储4.24.3字符串4.3本章小结多维数组各概念间的联系118多维数组存储结构逻辑结构以行为主优先存储以列为主优先存储特殊矩阵定义：值相同元素或者零元素分布有一定规律的矩阵压缩方法：将矩阵元素存储于向量中，并找出二者的下标映射关系稀疏矩阵定义：非零元素个数远少于零元素个数的矩阵压缩方法：三元组表，十字链表，带行向量的链表n维数组是线性表，它的每个元素是n-1维数组运算矩阵压缩字符串各概念间的联系119字符串存储结构概念运算顺序存储块链存储索引存储复制、连接、替换求长度、插入、删除比较、抽取、分割子串、主串模式匹配模式匹配算法：BF算法、KMP算法基本操作经典算法逻辑结构字符间呈线性关系矩阵压缩要点120压缩对象高阶矩阵压缩条件矩阵中非零元素呈某种规律分布；或：矩阵中出现大量的零元素压缩目的使用高效的存储方法，减少数据的存储量压缩方法

对原矩阵的二维数组存储，根据数据分布特征进行压缩，存储至向量等结构

稀疏矩阵的压缩存储除了要保存非零元素的值外，还要保存其在矩阵中的位置本章小结一维数组是线性表结点一对一相连，M*N二维数组有M行或N列线性表组合阵列。随机存取说的是每个结点存取时间都一样长短，特殊矩阵有对称、对角、三角种种有规律包含。压缩存是把二维的矩阵映射到一维的空间，行列二下标对一维下标的变换。稀疏矩阵很特别，是大矩阵非零的元素稀少分布星星点点，三元组表、行链表、十字链表压缩存储方法有三，设计思路都是存非零的元素值与位置在哪边。121本章小结多个字符连在一起是字符的串，串结构依然是线性表无二般。数组或链串存字符各种方案，求串长、比大小、做连接运算都简单，唯模式匹配有点难。匹配是主串里面把子串查看，BF蛮力法要一个字符一个字符挨个验，复杂度大欧mn速度有点慢。KMP不愧是三个臭皮匠凑成诸葛亮，细观察巧安排主串无回溯，子串定位继续的点在next表中寻探，大欧n加m提速果然赞。

（注：二维数组：M行N列

模式匹配：主串长度为n,子串长度为m）122

结点逻辑关系分层次的非线性结构树Chapter

5DataStructuresandAlgorithmAnalysis主要内容广义表的概念、存储结构、基本运算广义表树的定义和基本术语二叉树的概念、存储结构遍历二叉树哈夫曼树及其应用树学习目标了解数据的逻辑结构从线性结构到非线性结构的过渡了解包含子结构的线性结构理解链式存储结构在表达非线性数据结构中的作用掌握树的概念、存储方法、基本运算了解广义表的概念、结构特点及其存储表示方法实际问题中的树及抽象树的逻辑结构树的存储结构二叉树的逻辑结构二叉树的存储结构及实现树的遍历树的应用广义表*CONTENTS5.15.25.35.45.55.65.75.8实际问题中的树及抽象树的逻辑结构树的存储结构二叉树的逻辑结构二叉树的存储结构及实现树的遍历树的应用广义表*CONTENTS5.15.25.35.45.55.65.75.85.1实际问题中的树及抽象树引例1——日常生活中的树形结构129树引例2——计算机的目录结构130树引例3——树形结构的网站131表达式树132实际问题本质的抽象133一切具有层次关系的问题都可用树来描述实际问题中的树及抽象树的逻辑结构树的存储结构二叉树的逻辑结构二叉树的存储结构及实现树的遍历树的应用广义表*CONTENTS5.15.25.35.45.55.65.75.8树的逻辑结构135abdcefhgijlmnk层次结构一多对应非线性线性结构便不足以方便地描述这样的复杂情形树5.2树的逻辑结构5.2.15.2.2树的定义和基本术语树的操作定义5.2树的逻辑结构5.2.15.2.2树的定义和基本术语树的操作定义树138定义AGDCBFE树形结构是一种重要的非线性结构，讨论的是层次和分支关系树是递归结构——在树的定义中又用到了树的概念树（tree）是包含n个结点的有限集合，其中：（1）有一个根结点，它只有直接后继，但没有直接前趋。（2）除根结点之外的其余数据元素被分为m个根的子树。当树的集合为空时，n=0，此时称为空树，空树中没有结点。树的示意图139树的图形表示方法140树的相关术语141AGDCBFE包含一个数据元素及若干指向子树的分支结点的子树的根称为该结点的孩子一个结点的直接上层结点称为该结点的双亲同一双亲的孩子结点B、C、D是A的孩子，E、F是B的孩子A是B、C、D的双亲，B是E、F的双亲B、C、D是兄弟关系树的结点孩子结点双亲结点兄弟结点树的相关术语142AGDCBFE结点层树的深度结点的度树的度叶子结点分枝结点有序树无序树森林Level1Level2Level3根结点的层定义为1；根的孩子为第二层结点，依此类推；树中最大的结点层度不为0的结点也叫终端结点，是度为0的结点树中最大的结点度结点子树的个数不考虑子树的顺序子树有序的树互不相交的树集合树的基本术语——示例143E,K,L,GH,I,M树的概念144我们熟悉的树形结构中，无序树、有序树有哪些？思考&讨论讨论：有序树无序树的区别在于子树是否有顺序要求，有顺序要求的如家谱、书的目录等；无序的可以是计算机中的文件夹目录等。5.2树的逻辑结构5.2.15.2.2树的定义和基本术语树的操作定义构造建立一棵树，初始化。树的基本操作查找可以是查找根结点、双亲结点、孩子结点、叶子结点、指定值的结点等。插入删除在指定位置插入/删除结点遍历沿着某条搜索路线，依次对树中每个结点均做一次且仅做一次访问。访问结点所做的操作依赖于具体的应用问题求深度计算树的高度。实际问题中的树及抽象树的逻辑结构树的存储结构二叉树的逻辑结构二叉树的存储结构及实现树的遍历树的应用广义表*CONTENTS5.15.25.35.45.55.65.75.8树的存储结构148存得进取得出A存数值存联系B树形结构的存储原则。非线性结构比线性关系复杂，存储树形结构问题的关键与重点。树的存储结构149149树形结构存储结点间联系的原则是什么？一个双亲n个孩子对于设计好的存储结构，检验的标准则是只要在存储结构中能找到一个结点的这两种关系，那么这样的存储结构设计就是可行的。我们可以称之为“双亲孩子检验原则”。双亲孩子检验法思考&讨论5.3树的存储结构5.3.15.3.2树的连续存储方式树的链式存储方式5.3树的存储结构5.3.15.3.2树的连续存储方式树的链式存储方式树连续存储1——双亲孩子表示法152树连续存储2——双亲表示法153树连续存储3——孩子表示法1545.3树的存储结构5.3.15.3.2树的连续存储方式树的链式存储方式树的链式存储方式156树的链式存储方式1571.同构型结构的特点有哪些？关于树的结构讨论158思考&讨论2．什么样的树在用同构型结构时，空的指针域最少？讨论：同构型结构消除了异构型的缺陷，结构的统一化使管理变得容易，但若多数结点的度小于树的度，则部分指针域为空，造成存储空间的浪费。159什么样的树在用同构型结构时，空链域最少？设有n个结点，度为d的树，用同构型结点存储整个链表共有指针域数有用的指针域数n*d个n-1个空的指针域数n(d-1)+1个R=空的指针域数整个链表共有指针域数=n(d-1)+1ndR=n→∞Limn→∞Limn(d-1)+1nd=1d1-K越小越好结论：d=2时，空链域最少二叉树关于树的结构讨论根结点的地址不占指针域degree——度想去掉结点个数的因素思考&讨论树链式存储——孩子兄弟表示法160树链式存储——孩子链表表示法161树链式存储——孩子链表表示法162实际问题中的树及抽象树的逻辑结构树的存储结构二叉树的逻辑结构二叉树的存储结构及实现树的遍历树的应用广义表*CONTENTS5.15.25.35.45.55.65.75.8164若我们能找到普通树转换为二叉树、二叉树又能还原成原来的普通树的方法，就完美地解决了这个问题。把二叉树作为典型的结构加以研究讨论，相应的结果能用到普通的树上面吗？二叉树普通树思考&讨论树转换为二叉树165树转换为二叉树的过程中各结点的联系有怎样的变化？树转换为二叉树166思考&讨论讨论：加线的过程，是增加了结点和兄弟的直接关联；去线的操作，是去掉了除长子之外的联系，但是可以通过长子的兄弟关系，间接得到所有孩子的信息，这个和前面介绍的“树链式存储-孩子兄弟表示法”是一样的原理。森林转换为二叉树167二叉树还原为树168树还原为二叉树的过程中各结点的联系有怎样的变化？思考&讨论一个结点x的左孩子其子孙，从来历上看，都是这个左孩子的兄弟，如图5.24中的FG点，都是E的子孙，EFG都是B的孩子，故加线是恢复结点与孩子的关系；去线是去掉兄弟间的连线，这样就可以恢复成原来的树结构了。树与二叉树的存储关系169树链式存储——孩子兄弟表示法1705.4二叉树的逻辑结构5.4.15.4.2二叉树的概念二叉树的基本性质5.4.3二叉树的操作定义5.4二叉树的逻辑结构5.4.15.4.2二叉树的概念二叉树的基本性质5.4.3二叉树的操作定义173说明：二叉树是每个结点最多有两个子树的有序树。二叉树的子树通常称为“左子树”（leftsubtree）和“右子树”（rightsubtree）。左、右子树的顺序不能互换。二叉树的概念AFGEDCB二叉树是递归结构，在二叉树的定义中又用到了二叉树的概念

二叉树是n(n≥0)个结点的有限集，它或为空树(n=0)，或由一个根结点和两棵分别称为左子树和右子树的互不相交的二叉树构成。二叉树二叉树的概念174二叉树与树的区别是什么？思考&讨论讨论：尽管二叉树与树有许多相似之处，树和二叉树的两个主要差别：（1）树中结点的最大度数没有限制，而二叉树结点的最大度数为2；（2）树的结点无左、右之分，而二叉树的结点有左、右之分，二叉树的基本形态175二叉树的特殊形态——满二叉树176如果深度为k的二叉树，有2k-1个结点则称为满二叉树二叉树的特殊形态——完全二叉树177可以说满二叉树是完全二叉树的特例情形、(b)完全二叉树(c)不是完全二叉树二叉树的特殊形态——完全二叉树178完全二叉树5.4二叉树的逻辑结构5.4.15.4.2二叉树的概念二叉树的基本性质5.4.3二叉树的操作定义二叉树的基本性质180深度为h的二叉树至多有2h–1个结点（h

≥1）对任何一棵二叉树，若它含有n0个叶子结点、n2个度为2的结点，则必存在关系式：n0=n2+1FGCBADE在二叉树的第i层上至多有2i-1个结点（i≥1）性质1性质2性质3完全二叉树的性质181具有n个结点的完全二叉树的深度为：[log2n]+1若对含n个结点的完全二叉树从上到下且从左至右进行1至n的编号，则对完全二叉树中任意一个编号为i的结点：若i=1，则该结点是二叉树的根，无双亲，否则，编号为

i/2

的结点为其双亲结点；若2i>n，则该结点无左孩子，否则，编号为2i的结点为其左孩子结点；若2i+1>n，则该结点无右孩子结点，否则，编号为2i+1的结点为其右孩子结点。123456FCBADE方括号表示取整性质4性质5完全二叉树的性质【例5-1】二叉树各种结点数目的计算若一个完全二叉树有n=1450个结点，则度为1的结点、度为2的结点、叶子结点个数分别是多少？有多少左孩子，多少右孩子？该树的高度是多少？解：树的高度：∵是完全二叉树

∴1～10层全满，k=10最下层叶子结点的个数=n-（2k

-1）=1450-1023=427k-1层带叶子的结点数=[427+1/2]=214k-1层结点数=2k-1=512k-1层叶子数=512-214=298∴总叶子数n0=427+298=725度为2的结点n2=n0-1=724度为1的结点n1=n-1-2n2=1450-1-2*724=1有左孩子结点数=度为2的结点数+度为1的结点数=725有右孩子结点数=度为2的结点数=724182二叉树的特殊形态——完全二叉树183完全二叉树k层最下层k-1层k-1层带叶子的结点k-1层带的叶子数5.4二叉树的逻辑结构5.4.15.4.2二叉树的概念二叉树的基本性质5.4.3二叉树的操作定义二叉树的操作定义构造建立一棵树，初始化查找查找指定条件的结点插入

删除在指定位置插入/删除结点遍历

对树中每个结点均做一次且仅做一次访问求深度计算树的高度实际问题中的树及抽象树的逻辑结构树的存储结构二叉树的逻辑结构二叉树的存储结构及实现树的遍历树的应用广义表*CONTENTS5.15.25.35.45.55.65.75.8普通树二叉树二叉树的存储结构及实现已讨论过一般形式树的存储方案简化对照树的一般形式来讨论二叉树的存储方案5.5二叉树的存储结构及实现5.5.15.5.2二叉树的顺序存储结构二叉树的链式存储结构5.5.3建立动态二叉链表二叉树顺序存储——结点间关系分析189二叉树顺序存储——结点间关系分析190二叉树顺序存储——结点位置分析191二叉树顺序存储——结点位置分析192完全二叉树存储方案是否适用一般的二叉树存储？将二叉树的所有结点，按照完全二叉树的编号方法进行编号，按序存储到一片连续的存储单元中。结点的顺序将反映出结点之间逻辑关系。二叉树的顺序存储思考&讨论二叉树顺序存储——结点位置分析193退化的二叉树的存储5.5二叉树的存储结构及实现5.5.15.5.2二叉树的顺序存储结构二叉树的链式存储结构5.5.3建立动态二叉链表二叉树的链式存储结构195

二叉树的每个结点含有两个指针域来分别指向相应的分支，称其为二叉链表二叉链表二叉树的链式存储结构196二叉树的每个结点含有两个指针域来分别指向相应的分支。二叉树的链式存储二叉树的三叉链存储结构197树的三重链表表示198静态二叉链表199ADBCFE021435孩子结点在数组中的位置。用-1表示无左孩子或右孩子采用数组存储的静态二叉链表5.5二叉树的存储结构及实现5.5.15.5.2二叉树的顺序存储结构二叉树的链式存储结构5.5.3建立动态二叉链表层次输入法创建二叉链表方法一201层次输入法创建二叉链表方法一202

Q队列元素A出列，A的下标i=1

将A的左孩子结点地址（在下标为2*i处）填入A结点的左指针域

将A的右孩子结点地址（在下标为2*i+1处）填入A结点的右指针域层次输入法创建二叉链表方法一203

Q队列元素A出列，A的下标i=1

将A的左孩子结点地址（在下标为2*i处）填入A结点的左指针域

将A的右孩子结点地址（在下标为2*i+1处）填入A结点的右指针域204层次输入法创建二叉链表方法一伪代码描述设二叉树的深度为k，则队列Q的长度至少为2k-1+1(队列的0下标位不用)生成树的所有结点，结点地址按结点编号顺序填入队列数组Q[]中队头元素下标i=1当Q队列i<k-1层元素个数(2k-1)

Q队列元素i出列将i的左孩子结点地址(下标2*i）填入i的左指针域将i的右孩子结点地址(下标2*i+1的结点）填入i的右指针域返回根结点地址层次输入法创建二叉链表方法二205

输入结点信息，若输入的结点不是虚结点，则建立一个新结点。若新结点是第1个结点，则令其为根结点，否则将新结点作为孩子链接到它的双亲结点上。如此反复进行，直到输入结束标志“＃”为止层次输入法创建二叉链表方法二206

输入结点信息，若输入的结点不是虚结点，则建立一个新结点。若新结点是第1个结点，则令其为根结点，否则将新结点作为孩子链接到它的双亲结点上。如此反复进行，直到输入结束标志“＃”为止207层次输入法创建二叉链表方法二伪代码细化描述设二叉树的深度为k，则队列Q的长度设置按完全二叉树编号至树的最后一个结点当输入结点信息不是结束标志‘#’若输入的结点不是虚结点，则建立一个新结点并入队若新结点是第1个结点，则令其为根结点，否则将新结点作为孩子链接到它的双亲结点上。若新结点是双亲结点的右孩子，则双亲结点出队。返回根结点地址208层次输入法创建二叉链表方法二功能描述输入输出CreaTree无根地址函数名形参函数类型

typedefstructnode{datatypedata;structnode*lchild,*rchild;}bitree;数据结构设计函数框架设计层次输入法创建二叉链表方法二/*===============================================函数功能：层次输入法创建二叉链表函数输入：无函数输出：二叉链表根结点键盘输入：按完全二叉树结点编号规则顺序输入结点值，空结点为@====================================================*/2095.6树的遍历5.6.15.6.2树的广度优先遍历树的深度优先遍历5.6.3树的遍历的应用引例1——机电设备通电自检模型211设备通电自检步骤应该如何进行检测步骤：左子树：网卡等正常→PCI正常→显卡等正常→非PCI正常→板卡正常右子树：硬盘等正常→外存正常→键盘等正常→其他正常→非板卡正常整棵树：板卡正常→非板卡正常→计算机正常在上述的检测过程中，“后序遍历”的意思是指树的根结点是最后被访问到的，无论是整棵树还是左右子树。“后序遍历”引例2——网购商品的管理212FoodMeatPorkBeefFruitYellowBananMangoRedCherry如何打印商品清单“先序遍历”根结点：Food左子树：Meat→Pork/Beef右子树：Fruit→（左子树）Yellow→Banan/MangoFruit→（右子树）Red→Cherry引例3——树中结点的快速查找策略213“中序遍历”如何得到有序序列？二分查找递归过程根为1的树：左子树（空）→根1→右子树（2）→结果为1、2根为3的树：左子树（1,2）→根3→右子树（4,5）→结果为1、2、3、4、5根为9的树：左子树（7,8）→根9→右子树（10,11）→结果为7、8、9、10、11214遍历的基本概念对结点的处理。如修改结点数据、输出结点数据。

按某种顺序访问数据结构中的结点，要求每个结点访问一次且仅访问一次。遍历对线性结构是容易解决的，而二叉树是非线性的，因而需要寻找一种规律，以便使二叉树上的结点能排列在一个线性队列上，从而便于遍历。如何访问二叉树的每个结点，而且每个结点仅被访问一次？CBADFE遍历访问215遍历的基本概念——基本遍历策略广度遍历(Breadth-FirstSearch)深度遍历(Depth_FirstSearch)5.6树的遍历5.6.15.6.2树的广度优先遍历树的深度优先遍历5.6.3树的遍历的应用基于顺序存储结构的树的广度优先遍历217广度遍历（层次遍历）方法：从上到下、从左到右访问各结点适用于顺序存储结构

基于链式存储结构的二叉树广度优先遍历218基于链式存储结构的二叉树广度优先遍历219(1)初始化一个队列，并把根结点入列队；

(2)队列元素出队，取得一个结点，访问该结点；

(3)若该结点的左孩子非空，则将该结点的左子树入队列；

(4)若该结点的右孩子非空，则将该结点的右子树入队列；(5)循环执行步骤2到4，直至队列为空。算法描述基于链式存储结构的二叉树广度优先遍历220二叉树结点结构描述typedefstructnode{datatypedata;structnode*lchild,*rchild;}bitree;bitree*Q[MAXSIZE];//设数组Q做队列，队列元素类型为二叉链表结点类型功能输入输出层次遍历二叉树leverOrder二叉链表根结点地址无函数名形参函数类型函数框架设计数据结构设计基于链式存储结构的二叉树广度优先遍历/*=====================================函数功能：层次遍历二叉树，打印遍历序列函数输入：二叉链表根结点地址bitree*Ptr函数输出：无=======================================*/2215.6树的遍历5.6.15.6.2树的广度优先遍历树的深度优先遍历5.6.3树的遍历的应用树的深度优先遍历223深度优先遍历方法深度优先遍历递归算法深度优先遍历非递归算法树的深度优先遍历224深度优先遍历方法深度优先遍历递归算法深度优先遍历非递归算法深度优先遍历方法225先左后右：DLR，LDR，LRD先右后左：DRL，RDL，RLD226深度优先遍历方法先序遍历（DLR）中序遍历（LDR）后序遍历（LRD）深度遍历策略——先序遍历227若二叉树非空，则依次进行以下操作（1）访问根结点；（2）先序遍历左子树；（3）先序遍历右子树；深度遍历策略——中序遍历228若二叉树非空，则依次进行以下操作（1）中序遍历左子树；（2）访问根结点；（3）中序遍历右子树；深度遍历策略——后序遍历229若二叉树非空，则依次进行以下操作（1）后序遍历左子树；（2）后序遍历右子树；（3）访问根结点；用投影法理解树的遍历230用投影法理解树的遍历231用投影法理解树的遍历232先序遍历的例子233先序遍历的例子234情形圈中表示DLR序列情形圈中表示DLR序列1树的根A6A的右子树继续细化2A的左子树继续细化7A右子树的根E3A左子树的根B8E的右子树继