数据结构总结.ppt

,一个数据结构有两个要素：数据元素的集合；关系的集合。,Data_Structure=(D，R)其中D是数据元素的有限集，R是D上的关系的有限集。,数据的逻辑结构,数据的逻辑结构指数据结构中元素之间的逻辑关系。它是从具体问题中抽象出来的数学模型。是独立于计算机存储器（与具体的计算机无关）。可分为如下几种基本类型：集合结构：线性结构：树型结构：图形结构：,数据的存储结构,数据的存储结构数据的逻辑结构在计算机存储器中的存储方式，又称物理结构。可分为如下两种类型。顺序存储结构：链式存储结构：,1.3算法分析和评价,对算法的分析和评价，一般应考虑正确性、可维护性、可读性、运算量、占用存储空间等诸多因素。其中评价算法的3条主要标准是：（1）算法实现所耗费的时间（时间复杂度）。（2）算法实现所耗费的存储空间，其中主要考虑辅助存储空间（空间复杂度）。（3）算法应易于理解、易于编码、易于调试等。,常见的渐进时间复杂度有：O(1)：常量时间阶O(n)：线性时间阶O(n)：对数时间阶O(nn)：线性对数时间阶O(1)O(log2n)O(n)O(nlog2n)O(n2)rear？,操作集合（1）入队add(obj)：把数据元素obj插入队列。（2）出队remove()：出队,删除的数据元素由函数返回。（3）取队头数据元素element()：取队列当前队头的数据元素并由函数返回。（4）空否empty()：若堆栈不为空则函数返回true，否则函数返回false。,顺序循环队列类Queue,intfront;intrear;Objectdata;intlength;intmaxSize;,构造函数,publicQueue()maxSize=20;data=newObjectmaxSize;rear=front=0;length=0;,构造函数,publicQueue(intsize)maxSize=size;data=newObjectmaxSize;rear=front=0;length=0;,入队add,publicbooleanadd(Objectobj)if(rear=front,出队remove,publicObjectremove()if(length=0)System.out.println(队列为空，不能出队！);returnnull;Objecttemp=datafront;front=(front+1)%maxSize;length-;returntemp;,取队头元素peek,publicObjectpeek()returndatafront;,判断空否empty(),publicbooleanempty()returnlength=0;,5.2.1数组的定义,数组是一组偶对(下标值，数据元素值)的集合。在数组中，对于一组有意义的下标，都存在一个与其对应的值。一维数组对应着一个下标值，二维数组对应着两个下标值，如此类推。数组是由n(n1)个具有相同数据类型的数据元素a1，a2，an组成的有序序列，且该序列必须存储在一块地址连续的存储单元中。,数组的定义,数组中的数据元素具有相同数据类型。数组是一种随机存取结构，给定一组下标，就可以访问与其对应的数据元素。数组中的数据元素个数是固定的。,通常有两种顺序存储方式行优先顺序(RowMajorOrder)：列优先顺序(ColumnMajorOrder)：,对一个有n个数据元素的一维数组，设a0是下标为0的数组元素，LOC(a0)表示元素a0的内存单元地址，即数组的首地址，k是每个数据元素所需的字节个数，则有,Loc(ai)=Loc(a0)+i*k(i=0,1n-1),对一个m行n列的二维数组A=(aij)mn，若每个元素占用的存储单元数为k，LOCa00表示元素a00的首地址，即数组的首地址，则有：,Loc(aij)=Loc(a00)+(i*n+j)*k(i=0,1m-1,j=0,1n-1),Loc(aij)=Loc(a00)+(j*m+i)*k(i=0,1m-1,j=0,1n-1),5.2.2矩阵的压缩存储,在科学与工程计算问题中，矩阵是一种常用的数学对象，在高级语言编程时，通常将一个矩阵描述为一个二维数组。这样，可以对其元素进行随机存取，各种矩阵运算也非常简单。对于高阶矩阵，若其中非零元素呈某种规律分布或者矩阵中有大量的零元素，若仍然用常规方法存储，可能存储重复的非零元素或零元素，将造成存储空间的大量浪费。对这类矩阵进行压缩存储：多个相同的非零元素只分配一个存储空间；零元素不分配空间。,特殊矩阵,特殊矩阵：是指非零元素或零元素的分布有一定规律的矩阵。对称矩阵三角矩阵稀疏矩阵,1.对称矩阵,若一个n阶方阵A=(aij)nn中的元素满足性质：aij=aji1i,jn且ij则称A为对称矩阵，如图5-3所示。,对称矩阵中的元素关于主对角线对称，因此，让每一对对称元素aij和aji(ij)分配一个存储空间，则n2个元素压缩存储到n(n+1)/2个存储空间，能节约近一半的存储空间。,以主对角线划分，三角矩阵有上三角和下三角两种。上三角矩阵的下三角（不包括主对角线）中的元素均为常数c(一般为0)。下三角矩阵正好相反，它的主对角线上方均为常数，如图5-5所示。,2.三角矩阵,三角矩阵中的重复元素c可共享一个存储空间，其余的元素正好有n(n+1)/2个，因此，三角矩阵可压缩存储到向量sa0n(n+1)/2中，其中c存放在向量的1个分量中。,3.稀疏矩阵,稀疏矩阵(SparseMatrix)：其非零元素的个数远小于零元素个数。对于稀疏矩阵，目前还没有一个确切的定义。设矩阵A是一个nm的矩阵中有s个非零元素，设=s/(nm)，称为稀疏因子，如果某一矩阵的稀疏因子满足0.05时称为稀疏矩阵，如图5-8所示。,稀疏矩阵的压缩存储,对于稀疏矩阵，采用压缩存储方法时，只存储非0元素。必须存储非0元素的行下标值、列下标值、元素值。因此，一个三元组(i,j,aij)唯一确定稀疏矩阵的一个非零元素。如图5-8的稀疏矩阵A的三元组线性表为：(1,2,12),(1,3,9),(3,1,-3),(3,8,4),(4,3,24),(4,6,2),(5,2,18),(6,7,-7),(7,4,-6),稀疏矩阵的压缩存储,稀疏矩阵的压缩存储结构主要有三元组的数组结构存储和三元组的链表结构存储两大类型。,图稀疏矩阵示例,用三元组表示为：(1,2,3),(2,3,7),(3,1,2),(4,4,5),5.2.3广义表,广义表(Lists，又称为列表)：是由n(n0)个元素组成的有穷序列：LS=(a1，a2，an)其中ai或者是原子项，或者是一个广义表。LS是广义表的名字，n为它的长度。若ai是单个元素，则ai是广义表的原子，若ai是广义表，则称为LS的子表。,习惯上：原子用小写字母，子表用大写字母。若广义表LS非空时：a1(表中第一个元素)称为表头；其余元素组成的子表称为表尾；(a2，a3，an)广义表中所包含的元素(包括原子和子表)的个数称为表的长度。广义表中括号的最大层数称为表深度。,A=(a,b)/线性表，长度为2，深度为1B=(c,A)=(c,(a,b)/A为B的子表，B的长度位2，深度为2C=(d,A,B)=(d,(a,b),(c,(a,b)/A、B为C的子表，C的长度为3，深度为3D=()/空表，长度为0，深度为1D1=(D)=()/非空表，元素是一个空表，长度为1，深度为2E=(f,E)=(f,(f,(f,()/递归表，E的长度为2，深度是无穷值,汉诺塔问题,在这个汉诺塔问题中，假设有三个分别命名为X,Y和Z，在塔座X上插有n个直径大小各不同的圆盘。要求将X轴上的n个圆盘移至塔座Z上并任按同样顺序叠排，圆盘移动时必须遵循以下规则：1.每次只能移动一个圆盘；2.圆盘可以在X,Y和Z中的任意塔座上；3.任何时候都不能将一只较大圆盘压在较小的圆盘之上。最后输出移动的步骤以及移动的起始位置。,5.汉诺塔问题,1.树的定义,树（Tree）是零个或多个结点的有限集合。结点数为0的树称为空树，结点数大于0的树称为非空树。在一棵非空树中：（1）有且仅有一个特定的称为根（root）的结点；（2）当结点数大于1时，除根结点外，其它结点被分成n（n0）个互不相交的子集：T1，T2，Tn，其中每个子集本身又是一棵树（称之为子树），每一棵子树的根xi（1in）都是根结点root的后继，树T1，T2，Tn称为根的子树。,1.树的定义,例如图7-1就是一个典型的树形结构：,2.树的逻辑表示方法,树形图法嵌套集合法广义表形式凹入表示法,树形图法,图7-2给出了图形表示树的直观表示法，用圆圈表示结点，连线表示结点间的关系，并把树根画在上面。树形图法主要用于直观描述树的逻辑结构。,嵌套集合法,嵌套集合法采用集合的包含关系表示树，如图7-3所示。,广义表形式,广义表表示法以广义表的形式表示树，利用广义表的嵌套区间表示树的结构，如：(A(B，C(E，F)，D(G),凹入表示法,凹入表示法采用逐层缩进的方法表示树，有横向凹入表示和竖向凹入表示。图7-4所示的为横向凹入表示。,3.树的基本术语,结点的度（Degree）：是指结点拥有的子树的数目。树的度：是指树内各结点的度的最大值。叶子或终端结点：是指度为0的结点。非终端结点或分支结点：是指度不为0的结点。,3.树的基本术语,孩子（Child）和双亲（Parent）：某个结点的子树的根称为该结点的孩子，相应的，该结点称为其孩子的双亲。兄弟：同一个双亲的孩子结点互为兄弟。,3.树的基本术语,结点的层次：规定根所在的层次为第1层，根的孩子在第二层，依次类推。树的深度或高度：树中结点最大的层数。,3.树的基本术语,有序树：是指树中结点的各子树从左至右是有次序的，否则称为无序树。无序树：树中任意一个结点的各孩子结点的排列没有严格次序的树称为无序树。森林：是指n（n0）棵互不相交的树的集合。,4.树的性质,树中任一个结点都可以有零个或多个后继结点（孩子），但最多只能有一个前趋结点（双亲）。根结点无双亲，叶子结点无孩子。祖先与子孙的关系是父子关系的拓展。有序树中兄弟结点之间从左至右有次序之分。,树的基本运算,树的运算包括计算结点的度、树深度等。例【7-1】出如图7-6所示的树的叶子结点、非终端结点、每个结点的度及树深度。解：1.叶子结点有：B、D、F、G、H、I、J。2.非终端结点有：A、C、E。3.每个结点的度分别是：A的度为4，C的度为2，E的度为3，其余结点的度为0。4.树的深度为3。,7.2.2二叉树的概念和性质,二叉树的概念二叉树的性质二叉树与树、森林之间的转换,1.二叉树的概念,二叉树（BinaryTree）是结点的有限集合，这个集合或者为空，或者是由一个根结点和两棵互不相交的分别称为左子树和右子树的二叉树组成。二叉树中的每个结点至多有两棵子树，且子树有左右之分，次序不能颠倒。当二叉树中某个结点存在两个子树时，这两个子树分别称为左（二叉）子树和右（二叉）子树，该结点称为这两个子树的根结点。,1.二叉树的概念,二叉树与树的区别：二叉树中每个结点的孩子至多不超过两个，而树对结点的孩子数无限制；二叉树中结点的子树有左右之分，而树的子树没有次序。,2.二叉树的性质,性质1：二叉树第i层上的结点数目最多为2i-1(i=1）,满二叉树：在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子结点都在同一层上。完全二叉树：如果一棵具有n个结点的二叉树的逻辑结构与满二叉树的前n个结点的逻辑结构相同。（除最后一层外，每一层上的结点数均达到最大值，在最后一层上只缺少右边的若干结点。满二叉树也是完全二叉树。）满二叉树一定是完全二叉树。,满二叉树和完全二叉树,2.二叉树的性质,性质4：具有n个结点的完全二叉树的深度为log2n+1。,2.二叉树的性质,性质5：如果对一棵有n个结点的完全二叉树的结点按层次编号(即自上而下，自左至右)，则对任一结点i(11，则其双亲是编号为i/2的结点。(2)如果2*in，则结点i无左孩子；否则其左孩子是编号为2*i的结点。(3)如果2*i+1n，则结点i无右孩子；否则其右孩子是编号为2*i+1的结点。,2.二叉树的性质,(4)若i为奇数且不为1，则结点i的左兄弟的编号是i-1；否则，结点i无左兄弟。(5)若i为偶数且小于n，则结点i的右兄弟的编号是i+1；否则，结点i无右兄弟。,3.二叉树与树、森林之间的转换,将树转换为二叉树树中每个结点最多只有一个最左边的孩子(长子)和一个右邻的兄弟。按照这种关系很自然地就能将树转换成相应的二叉树：在所有兄弟结点之间加一连线;对每个结点，除了保留与其长子的连线外，去掉该结点与其它孩子的连线。,3.二叉树与树、森林之间的转换,例7-4将图7-13(a)所示的树转换为二叉树,7.3.3二叉树与树、森林之间的转换,将树转换为二叉树第一步：加线；第二步：抹线；第三步：旋转。,7.3.3二叉树与树、森林之间的转换,将一个森林转换为二叉树具体方法是：将森林中的每棵树变为二叉树因为转换所得的二叉树的根结点的右子树均为空，故可将各二叉树的根结点视为兄弟从左至右连在一起，就形成了一棵二叉树。,7.3.3二叉树与树、森林之间的转换,二叉树到树、森林的转换把二叉树转换到树和森林自然的方式是：若结点x是双亲y的左孩子，则把x的右孩子，右孩子的右孩子，都与y用连线连起来，最后去掉所有双亲到右孩子的连线。,7.2.3二叉树存储结构,二叉树的顺序存储结构二叉树的链式存储结构,1.二叉树的顺序存储结构,对于完全二叉树可以采用顺序存储结构(即一维数组)进行存储，按照性质5对结点进行编号，编号为i的结点存放在数组第i个元素所分配的存储单元中，完全二叉树结点之间的逻辑关系通过数组元素的下标体现。对于非完全二叉树，通过补设一些“虚结点”，使得二叉树的结点的编号与完全二叉树相同，再进行顺序存储。,1.二叉树的顺序存储结构,每个“虚结点”都将占据一个数组元素存储单元，非完全二叉树采用顺序存储结构将会造成存储空间的浪费。,2.二叉树的链式存储结构,二叉树除了可以采用顺序存储结构实现存储外，还可以采用链式存储结构进行存储，与采用顺序存储结构相比，采用链式存储结构实现二叉树的存储显得更自然。二叉树最常用的链式存储结构是二叉链，每个结点包含三个域，分别是数据元素域data、左孩子链域lChild和右孩子链rChild，结点结构为：,7.2.4二叉树的遍历,二叉树的遍历二叉树遍历递归算法,1.二叉树的遍历,二叉树的遍历指的是沿某条搜索路径访问二叉树，对二叉树中的每个结点访问一次且仅一次。这里的“访问”实际上指的是对结点进行某种操作。,1.二叉树的遍历,前序遍历二叉树（DLR）中序遍历二叉树（LDR）后序遍历二叉树（LRD）层序遍历二叉树,由于二叉树是非线性结构，每个结点会有零个、一个或两个孩子结点，所以一个二叉树的遍历序列不能决定一棵二叉树。如前序遍历序列A,B,D,G,C,E,F可以表示两棵不同的二叉树。,但某些不同的遍历序列组合可以唯一的确定一棵二叉树。可以证明，给定一棵二叉树的前序遍历序列和中序遍历序列，可以唯一确定一棵二叉树的结构。,例如，若给出一个二叉树的前序遍历序列是ABDGCEF，中序遍历序列是DGBAECF，则可以唯一的确定该二叉树的结构如下图所示：,publicclassVisitpublicvoidprint(Objectitem)System.out.print(item+);,例：访问结点的操作都是输出结点的数据元素值。,BiTreeNode,publicObjectdata;privateBiTreeNodeleftChild;privateBiTreeNoderightChild;,三个成员变量：,构造函数,publicBiTreeNode()leftChild=null;rightChild=null;publicBiTreeNode(Objectitem,BiTreeNodeleft,BiTreeNoderight)data=item;leftChild=left;rightChild=right;,先序遍历,publicvoidpreOrder(BiTreeNodet,Visitvs)if(t!=null)vs.print(t.getData();preOrder(t.getLeftChild(),vs);preOrder(t.getRightChild(),vs);,中序遍历,publicvoidinOrder(BiTreeNodet,Visitvs)if(t!=null)inOrder(t.getLeftChild(),vs);vs.print(t.getData();inOrder(t.getRightChild(),vs);,后序遍历,publicvoidpostOrder(BiTreeNodet,Visitvs)if(t!=null)postOrder(t.getLeftChild(),vs);postOrder(t.getRightChild(),vs);vs.print(t.getData();,7.最优二叉树-哈夫曼树,路径：若在树中存在一个结点序列k1,k2,.,kj，使得ki是ki+1(1ij)的双亲，则此结点序列称为从k1到kj的路径。路径长度：从k1到kj所经过的分支数称为这两点之间的路径长度，它等于路径上的结点数减1.,结点的权：常常为树中的某个结点赋上一个具有某种意义的数值，这个和某个结点相关的数值称为该结点的权或权值。结点的带权路径长度：是指从树根到该结点之间的路径长度与结点的权值的乘积。树的带权路径长度：是指树中所有叶子结点的带权路径长度之和。,树的带权路径长度：通常记为：WPL=W1L1+W2L2+.+WnLn。其中n表示叶子结点的个数，Wi表示叶子结点Ki的权值，Li表示根结点到Ki的路径长度。,哈夫曼树（HuffmanTree）：又称为最优二叉树，它是n个带权的叶子结点构成的所有二叉树中带权路径长度WPL最小的二叉树。,具有相同叶结点和不同带权路径长度的二叉树,（a）WPL=12+32+52+72=32（b）WPL=12+33+53+71=33（c）WPL=73+53+32+11=43（d）WPL=13+33+52+71=29,根据哈夫曼树的定义，要使一棵二叉树的带权路径长度WPL值最小，必须使权值越大的叶结点越靠近根结点。哈夫曼提出的构造哈夫曼树构造算法为：,（1）由给定的n个权值w1,w2,wn构造n棵只有根结点的二叉树，从而得到一个二叉树森林F=T1,T2,Tn。,（2）在二叉树森林F中选取根结点的权值最小和次小的两棵二叉树作为新的二叉树的左右子树构造新的二叉树，新的二叉树的根结点权值为左右子树根结点权值之和。,（3）在二叉树森林F中删除作为新二叉树左右子树的两棵二叉树，将新二叉树加入到二叉树森林F中。,（4）重复步骤（2）和（3），当二叉树森林F中只剩下一棵二叉树时，这棵二叉树就是所构造的哈夫曼树。,对于一组给定的叶结点，设它们的权值集合为7,5,3,1，按哈夫曼树构造算法对此集合构造哈夫曼树的过程如图所示。,哈夫曼树的构造算法,【例7-7】假定用于通信的电文由8个字符A、B、C、D、E、F、G、H组成，各字母在电文中出现的概率为5、25、4、7、9、12、30、8，试为这8个字母设计哈夫曼编码。,哈夫曼树可用于构造代码总长度最短的编码方案。具体构造方法如下：设需要编码的字符集合为d1,d2,dn，各个字符在电文中出现的次数集合为w1,w2,wn，以d1,d2,dn作为叶结点，以w1,w2,wn作为各叶结点的权值构造一棵二叉树，规定哈夫曼树中的左分支为0，右分支为1，则从根结点到每个叶结点所经过的分支对应的0和1组成的序列便为该结点对应字符的编码。这样的代码总长度最短的不等长编码称之为哈夫曼编码。,【例7-8】设计哈夫曼编码，利用第八步得到的哈夫曼树，规定左分支用0表示，右分支用1表示，则字母A、B、C、D、E、F、G、H的哈夫曼编码如下表示：A：0011B：01C：0010D：1010E：000F：100G：11H：1011,8.2.1图基本术语,图是由顶点集合(vertex)及顶点间的关系集合组成的一种数据结构：Graph(V,E)其中：V=x|x某个数据对象，是顶点的有穷非空集合；E=(x,y)|x,yV或E=|x,yV有向图的邻接矩阵可能是不对称的。,0,1,2,3,0,1,2,网络（有权图）的邻接矩阵,8,6,3,1,2,9,5,4,2,0,3,1,8.2.3图的遍历,从给定图中任意指定的顶点（称为初始点）出发，按照某种搜索方法沿着图的边访问图中所有顶点，使每个顶点仅被访问一次，这个过程称为图的遍历。深度优先搜索法DFS广度优先搜索法BFS,1.深度优先搜索法,DFS在访问图中某一起始顶点v后,由v出发,访问它的任一邻接顶点w1;再从w1出发,访问与w1邻接但还没有访问过的顶点w2;然后再从w2出发,进行类似的访问,如此进行下去,直至到达所有的邻接顶点都被访问过的顶点u为止。接着,退回一步,退到前一次刚访问过的顶点,看是否还有其它没有被访问的邻接顶点。如果有,则访问此顶点,之后再从此顶点出发,进行与前述类似的访问;如果没有,就再退回一步进行搜索。重复上述过程,直到连通图中所有顶点都被访问过为止。,深度优先搜索DFS(DepthFirstSearch),A,C,D,E,G,B,F,I,H,1,2,3,4,5,6,7,8,9,前进,回退,A,C,D,E,G,B,F,I,H,2.广度优先搜索法BFS,BFS在访问了起始顶点v之后,由v出发,依次访问v的各个未被访问过的邻接顶点w1,w2,wt,然后再顺序访问w1,w2,wt的所有还未被访问过的邻接顶点。再从这些访问过的顶点出发，再访问它们的所有还未被访问过的邻接顶点，如此做下去，直到图中所有顶点都被访问到为止。广度优先搜索是一种分层的搜索过程,每向前走一步可能访问一批顶点,不像深度优先搜索那样有往回退的情况。因此,广度优先搜索不是一个递归的过程。,广度优先搜索BFS(BreadthFirstSearch),A,C,D,E,G,B,F,I,H,1,2,3,4,5,6,7,8,9,A,C,D,E,G,B,F,I,H,8.2.4最小生成树,生成树最小生成树,1.生成树,无回路的图称为树、自由树或无根树；若连通图G有n个顶点，取连接n个顶点的n-1条边且无回路的子图称为G的生成树；使用不同的遍历图的方法，可以得到不同的生成树；从不同的顶点出发，也可能得到不同的生成树。,2.最小生成树,对于带边权的图来说，可以有许多生成树，把树中边权之和定义为树的权；在所有生成树中树权最小的那棵生成树称为最小生成树。,构成最小生成树的准则,必须使用且仅使用该网络中的n-1条边来联结网络中的n个顶点；不能使用产生回路的边；各边上的权值的总和达到最小。,求最小生成树的算法,普里姆(Prim)算法克鲁斯卡尔(Kruskal)算法,普里姆(Prim)算法,从N=V,E中的某一顶点u0出发,选择与它关联的具有最小权值的边(u0,v),将其顶点加入到生成树顶点集合U中。以后每一步从一个顶点在U中,而另一个顶点不在U中的各条边中选择权值最小的边(u,v),把它的顶点加入到集合U中。如此继续下去,直到网络中的所有顶点都加入到生成树顶点集合U中为止。,25,25,10,5,0,4,6,1,3,2,28,10,25,14,24,22,16,18,5,0,5,0,4,10,原图(a)(b),5,0,4,3,10,(c)(d)(e)(f),5,0,4,3,2,10,22,12,5,0,4,6,1,2,10,25,14,22,16,12,3,25,22,12,克鲁斯卡尔(Kruskal)算法,设有一个有n个顶点的连通网络N=V,E,最初先构造一个只有n个顶点,没有边的非连通图T=V,在网络N中选择一条具有最小权值的边,将其加入T中不产生回路，则将此边加入到T中;否则将此边舍去，将这条被选择的边从网络N的边集E中删除，如此重复下去,直到T中正好含有n-1条边为止。,5,0,4,6,1,3,2,28,10,25,14,24,22,16,18,12,9.2.1顺序查找,从表的一端开始，顺序扫描线性表，依次将扫描到的关键字和给定值k相比较，若当前扫描到的关键字与k相等，则查找成功；若扫描结束后，仍未找到关键字等于k的记录，则查找失败。,设要查找的数据元素在数据元素集合中出现的概率均相等，则该算法查找成功时的平均查找长度ASL成功为