高级数据结构

高级数据结构第1页，共64页，2023年，2月20日，星期四主要内容12.1多维数组12.2广义表12.3Trie和Patricia结构12.4改进的二叉搜索树第2页，共64页，2023年，2月20日，星期四12.1多维数组数组（Array）是元素和元素类型固定的有序序列静态数组必须在定义时指定其大小和类型动态数组可以在程序运行才分配内存空间多维数组（Multi-array）是向量的扩充向量的向量就组成了多维数组可以表示为：

ELEMA[c1..d1][c2..d2]…[cn..dn]ci和di是各维下标的下界和上界。所以其元素个数为：

第3页，共64页，2023年，2月20日，星期四数组类型特点:数组一般不做插入、删除操作，一旦建立数组，结构中的数据元素个数和元素之间的关系不再发生变动。2)数组是多维的结构，而存储空间是一个一维的结构。

有两种顺序映象的方式（二维数组）:

1)以行序为主序(低下标优先);2)以列序为主序(高下标优先);数组的存储第4页，共64页，2023年，2月20日，星期四例如：

称为基地址或基址以“行序为主序”的存储映象二维m×n数组A中任一元素ai,j

的存储位置

LOC(i,j)=LOC(0,0)+(n×i＋j)×a0,1a0,0a0,2a1,0a1,1a1,2a0,1a0,0a0,2a1,0a1,1a1,2L

L

第5页，共64页，2023年，2月20日，星期四若矩阵元素有规律地排列，则称为特殊矩阵。例如：对称矩阵，三角矩阵...用数组表示特殊矩阵第6页，共64页，2023年，2月20日，星期四二维数组是表示矩阵的最简单方法三角矩阵可以被分为上三角矩阵和下三角矩阵，它是指n阶矩阵中的下(上)三角的元素都是0或者一个常数c。

在上三角矩阵中，当数组的下标i>j时，数组元素a[i][j]=c；而在下三角矩阵中，当下标i<j时，a[i][j]=c。第7页，共64页，2023年，2月20日，星期四200004700095700563601353724795756361353701234567891011121314压缩位置转换公式k=i(i-1)/2+j-1

i>=j-1i<j第8页，共64页，2023年，2月20日，星期四用数组表示特殊矩阵对称矩阵指的是一个n阶矩阵，它的元素满足性质ai,j=aj,i，0<=（i,j）<n。在用数组存储时，元素a[i][j]=a[j][i]。第9页，共64页，2023年，2月20日，星期四为了节省空间，存储其下三角的值，而对角线之上的值通过对称关系映射过去。以一维数组sa[0..n(n+1)/2-1]作为n阶对称矩阵A的存储结构，则sa[k]和矩阵元ai,j之间存在着一一对应的关系：第10页，共64页，2023年，2月20日，星期四稀疏矩阵稀疏矩阵中的非零元素非常少，分布也不规律稀疏因子用来描述稀疏矩阵的非零元素情况，定义为:在m×n的矩阵中，有t个非零元素，则稀疏因子为:通常当这个值小于0.05时，可以认为是稀疏矩阵通常用三元组(i,j,aij)表示稀疏矩阵，其中i是元素的行号，j是元素的列号，aij该元素的值第11页，共64页，2023年，2月20日，星期四121415-522-731363428ijaij第12页，共64页，2023年，2月20日，星期四30020-100200011314222-13

12^^^^^^^１

稀疏矩阵的十字链表两组链表组成：行和列的指针序列每个结点都包含两个指针，一个指向它的同一行的下一个元素，一个指向它的同一列的下一个元素第13页，共64页，2023年，2月20日，星期四12.2广义表线性表由n（n≥0）个数据元素组成的有限有序序列.线性表的每个元素都具有相同的数据类型。如果一个线性表中还包括一个或者多个子表，就称之为广义表，一般记作：L＝（x0，x1，…，xi，…，xn-1）第14页，共64页，2023年，2月20日，星期四

L＝（x0，x1，…，xi，…，xn-1）L是广义表的名称n为长度xi（0≤i≤n-1）是L的成员，它可以是单个元素（原子），也可以是一个广义表（子表）A=()B=(e)C=(a,(b,c,d))D=(A,B,C)E=(a,E)第15页，共64页，2023年，2月20日，星期四eabcdDABC广义表的图形表示表原子广义表是一个多层次的线性结构第16页，共64页，2023年，2月20日，星期四广义表的结构特点:1)广义表中的数据元素有相对次序;2)广义表的长度定义为最外层包含元素个数;A=()长度为0B=(e)长度为1C=(a,(b,c,d))长度为2D=(A,B,C)长度为3E=(a,E)长度为2第17页，共64页，2023年，2月20日，星期四3)广义表的深度定义为所含括弧的重数;

注意:“原子”的深度为0;“空表”的深度为1。4)广义表可以共享;5)广义表可以是一个递归的表;

递归表的深度是无穷值，长度是有限值。第18页，共64页，2023年，2月20日，星期四6)任何一个非空广义表

LS=(1,2,…,n)

均可分解为

表头

Head(LS)=1和

表尾

Tail(LS)=(2,…,n)两部分例如:B=(e)Head(B)=eTail(B)=()C=(a,(b,c,d))Head(C)=aTail(C)=((b,c,d))D=(A,B,C)Head(D)=ATail(D)=(B,C)E=(a,E)Head(E)=aTail(E)=(E)第19页，共64页，2023年，2月20日，星期四广义表的各种类型纯表（purelist）从根结点到任何叶结点只有一条路径也就是说任何一个元素（原子、子表）只能在广义表中出现一次可重入表(reentrantlist)图示对应于一个DAG其元素(包括原子和子表)可能会在表中多次出现，但不会出现回路循环表(cycliclist，递归表)有向图中可能包含回路循环表的深度为无穷大第20页，共64页，2023年，2月20日，星期四广义表的存储使用数组来存储可以使用链表结构存储第21页，共64页，2023年，2月20日，星期四广义表存储ADTtypedefenum{ATOM,LIST}TAG;typedefstructGLNode{TAGtype;//表示该结点是ATOM或者LISTunion{Elemtypedata;GLNode*sublist;//如果是LIST,则指向它的元素的首结点

};GLNode*next;//指向下一个结点

};第22页，共64页，2023年，2月20日，星期四表头、表尾分析法:构造存储结构的分析方法:若表头为原子，则为空表

ls=NIL非空表lstag=1指向表头的指针指向表尾的指针tag=0data否则，依次类推。第23页，共64页，2023年，2月20日，星期四L=(a,(x,y),((x)))a(x,y)(

)

1LL=()0a

1

1

1

10x()x

1

10y0x第24页，共64页，2023年，2月20日，星期四12.3Trie结构和Patricia树BST（二叉搜索树）不是一棵平衡树，其结构与输入数据的顺序有关由关键字序列3，1，2，5，4构造而得的BST，由关键字序列1，2，3，4，5构造而得的BST，2134535412ASL=（1+2+3+4+5）/5=3ASL=（1+2+3+2+3）/5=2.2第25页，共64页，2023年，2月20日，星期四对象空间分解BST是一种组织上基于对象空间分解的数据结构，空间分解由存储在树中的对象（关键码值）决定。最简单的方法是对对象（关键码）的范围进行划分，既可以平均划分，也可以按照某种方式不平均划分。第26页，共64页，2023年，2月20日，星期四关键码空间分解不依赖于关键码的插入顺序树的深度受到关键码精度的影响最坏的情况下，深度等于存储关键码所需要的位数

例如，如果关键码是0到255之间的整数，关键码的精度就是8个二进制位。如果有两个关键码：10000010和10000011，它们的前面7位都是相同的所以直到第8次划分才能将这两个关键码分开这样的搜索树深度也为8，但这是最坏的情况

第27页，共64页，2023年，2月20日，星期四Trie结构基于关键码分解的数据结构，叫作Trie结构主要应用信息检索（informationretrieval）用来存储英文字符串，尤其大规模的英文词典Trie结构主要基于两个原则有一个固定的关键码集合对于结点的分层标记

如果所有的元素都可以使用数字或者字母等来标记，就可以考虑使用Trie结构。例如，元素可以用0-9的数字来标记在根结点处，分出10个子结点，分别标记0-9然后每个子结点又可以分出10个结点如此下去直到所有的元素都能够被区分开第28页，共64页，2023年，2月20日，星期四Trie结构特点与B+树一样，基于关键码空间分解的树结构，其内部结点仅作为占位符引导检索过程，数据纪录只存储在叶结点中。Huffman编码树也是一种二叉Trie树。第29页，共64页，2023年，2月20日，星期四Trie结构应用：“字符树”

存储字典里面的单词英文的单词是由26个字母组成的（简单起见，忽略大小写），英文字符树每一个内部结点都有26个子结点树的高度为最长字符串长度第30页，共64页，2023年，2月20日，星期四英文字符树一棵子树代表具有相同前缀的关键码的集合。例如“an”子树代表具有相同前缀an-的关键码集合{and，ant}第31页，共64页，2023年，2月20日，星期四字符树的改进由于单词可能不等长，所以更好的存储是其内部结点不存储单词信息，只有叶结点才存储单词信息第32页，共64页，2023年，2月20日，星期四字符树中的检索首先用待查关键码的第一个字符与森林的各个根的字符相比较。然后下一步的检索在前次比较相等的那棵树上进行.其中，用待查关键码的第二个字符与选定的这棵树的根的各个子结点进行比较。接着再沿着前次比较相等的分支进行进一步的检索。...直到进行到某一层，该层所有结点的字符都与待查关键码相应位置的字符不同，这说明此关键码在树目录里没有出现。若检索一直进行到树叶，那么就在树目录里找到了给定的关键码。第33页，共64页，2023年，2月20日，星期四Trie字符树的缺陷Trie结构显然也不是平衡的在存取英文单词时，显然t子树下的分支比z子树下的分支多很多每次有26个分支因子使得树的结构过于庞大，给检索也带来了不便字母在计算机中是以二进制ASCII码的形式存储的使用每个字母的二进制编码来代表这个字母关键码就只有编码0和1二叉Trie树第34页，共64页，2023年，2月20日，星期四PATRICIA结构为了得到更加平衡的结构，提出了Trie结构的一种变体PATRICIA

“PracticalAlgorithmToRetrieveInformationCodedInAlphanumeric”它不是对整个关键码大小范围的划分根据关键码每一个二进制位的编码来划分因为每一位不是0，就是1，所以分支因子是2，生成的树是二叉树第35页，共64页，2023年，2月20日，星期四PATRICIA结构图第36页，共64页，2023年，2月20日，星期四PATRICIA结构图因为最大的数是63，用6位二进制表示即可每个结点都有一个标号，表示它是比较第几位，然后根据那一位是0还是1来划分左右两个子树在图中检索5的话，5的编码为000101首先我们比较第0位，从而进入左子树然后在第1位仍然是0，还是进入左子树在第2位还是0，仍进入左子树第3位变成了1，从而进入右子树，就找到了位于叶结点的数字5第37页，共64页，2023年，2月20日，星期四PATRICIA的特点每个内部结点都代表一个位的比较，必然产生两个子结点，所以它是一个满二叉树，进行一次检索，最多只需要关键码位数次的比较即可。第38页，共64页，2023年，2月20日，星期四12.4二叉树结构的改进平衡的二叉搜索树、伸展树和最佳二叉排序树，它们都是对二叉树的结构或者操作规则做部分的改进以使树保持在一种类似于平衡的状态，从而达到较好的效率。第39页，共64页，2023年，2月20日，星期四12.4.2平衡的二叉搜索树(AVL)BST受输入顺序影响最好情况O(logn)最坏情况O(n)

BST如何始终保持O(logn)级的平衡状态？Adelson-Velskii和Landis发明了AVL树一种平衡的二叉搜索树任何结点的左子树和右子树高度最多相差1第40页，共64页，2023年，2月20日，星期四AVL树的性质可以为空具有n个结点的AVL树，高度为O(logn)如果T是一棵AVL树它的左右子树TL、TR也是AVL树并且|hL-hR|≤1hL、hR是它的左右子树的高度第41页，共64页，2023年，2月20日，星期四第42页，共64页，2023年，2月20日，星期四平衡因子用bf(x)来表示结点x的平衡因子。它被定义为：

bf(x)=x的右子树的高度–x的左子树的高度对于一个AVL树中的结点平衡因子可能取值为:

0，1和-1

第43页，共64页，2023年，2月20日，星期四AVL树结点的插入插入17后导致不平衡重新调整为平衡结构12第44页，共64页，2023年，2月20日，星期四二叉搜索树的平衡旋转ABBLARBRhh-1h-112ABBLARBR00LL型第45页，共64页，2023年，2月20日，星期四RR型ABBRALBLhh-1h-1-1-2ABBRBLAL00二叉搜索树的平衡旋转第46页，共64页，2023年，2月20日，星期四LR型ABBLARCLh-1h-2h-1-12CRC1ACBLARCR-10B0CL二叉搜索树的平衡旋转第47页，共64页，2023年，2月20日，星期四RL型BCALBRCR-10A0CLABBRALCLh-1h-2h-11-2CRC1二叉搜索树的平衡旋转第48页，共64页，2023年，2月20日，星期四插入下列单词得到的AVL树：

cup，cop，copy，hit，hi，his,hia1第49页，共64页，2023年，2月20日，星期四插入下列单词后得到的AVL树：

cup，cop，copy，hit，hi，his,hia第50页，共64页，2023年，2月20日，星期四AVL树的效率AVL树的检索、插入和删除效率都是O(1ogn)，这是因为具有n个结点的AVL树的高度一定是O(logn)。AVL树适用于组织较小的、内存中的目录。而对于较大的、存放在外存储器上的文件，用二叉搜索树来组织索引就不合适了。在文件索引中大量使用每个结点包括多个关键码的B树，尤其是B+树。第51页，共64页，2023年，2月20日，星期四第4章字符串(了解）52基本概念存储结构（顺序、标准类）基本操作的含义第52页，共64页，2023年，2月20日，星期四字符串的模式匹配主串：s=“babcabcacbab”模式：t=“bcac”Index(s,t)=5第53页，共64页，2023年，2月20日，星期四intNaiveStrMatching(constString&T,constString&P){inti=0,j=0;intpLen=P.length();//模式长度inttLen=T.length();//主串长度if(tLen<pLen)return-1;while(i<pLen&&j<tLen){if(T[j]==P[i]){i++;j++;}else{j=j–i+1;i=0;}}if(i>=pLen)returnj–pLen+1;elsereturn-1;}012345678*********###第54页，共64页，2023年，2月20日，星期四时间复杂度设主串T长度为n，子串P长度为m最坏情况:每次比较到P串的第m个字符时不匹配，则时间复杂度为O(n*m)。第55页，共64页，2023年，2月20日，星期四改进办法1如果重新比较时，T中所剩的字符个数不足子串P时，立即让算法终止。

j第56页，共64页，2023年，2月20日，星期四改进办法2每次先用子串的第一个字符及最后一个字符与主串对应的字符进行比较，若均相等，再比较中间的字符。第57页，共64页，2023年，2月20日，星期四改进办法3ababcabcacbababcj=2i=2子串：abca