数据结构初赛复习

1、初赛数据结构大约初赛数据结构大约题题l约分数据结构数据结构l线性表l队l栈l树l图线性表线性表l定义：一个线性表是n个数据元素的有限序列l线性表的特点：l存在唯一一个被称做“第一个”的数据元素l存在唯一一个被称做“最后一个”的元素l除第一个之中，集合中的每个数据元素均只有一个前驱l除最后一个之外，集合中每个数据元素均只有一个后继线性表的顺序存储结构线性表的顺序存储结构 l线性表的顺序存储即用一组地址连续的存储单元依次存储线性表中的元素 l设线性表中每个元素需占用r个存储单元则lloc（ai+1 ）=loc（ai）+rl loc（ai）=loc（a1）+（i-1）*r线性表的链式存储结构线性表的

2、链式存储结构 l定义：实现表的另一种方法是用指针将存储表元素的那些单元依次串联在一起。这种方法避免了在数组中用连续的单元存储元素的缺点，因而在执行插入或删除运算时，不再需要移动元素来腾出空间或填补空缺。然而我们为此付出的代价是，需要在每个单元中设置指针来表示表中元素之间的逻辑关系，因而增加了额外的存储空间的开销。 指针的定义及操作指针的定义及操作 l在pascal中,指针变量(也称动态变量)存放某个存储单元的地址；也就是说， 指针变量指示某个存储单元。指针类型的格式为:基类型ltype pointer=Integer;var p1,p2:pointer;l和其它类型变量一样，也可以在var区直

3、接定义指针型变量。例如：var a:real; b:boolean;l利用介绍的指针类型可以构造一个简单而实用的动态存储分配结构链表结构。下图是一个简单链表结构示意图：链表中的每个结点至少应该包含两个域；一是数据域，一是指针域。因此，每个结点都是一个记录类型，指针的基类型也正是这个记录类型。因此，head可以这样定义：type pointer= rec；rec=recorddata：integer;next:pointer;end;var head:pointer;l结点的插入结点的插入如下图所示,要在P结点和Q结点之间插入一个结点m,其操作如下:l只要作如下操作即可:New(m);read(

4、m.data);m.next:=q;p.next:=m; l结点的删除结点的删除如下图所示，要在删除结点P的操作如下:要删除结点P,则只要将其前趋结点的指针域指向P 的后继结点即可。q.next:=p.next;dispose(p);l双向链表结构双向链表结构单链表中，每个结点只有一个指向其后继结点的指针域。如果每个结点不仅有一个指向其后继结点的指针域，还有一个指向其前趋的指针域，则这种链表称为双向链表。如图所示。可用如下定义一个数据域为整型的双向链表:type pointer=node;node=recordprev:pointer;data:integer;next:pointer;end

5、;A队队l队列的定义：队列是一种特殊的线性表，对这种线性表，删除操作只在表头(称为队头)进行，插入操作只在表尾(称为队尾)进行。队列的修改是按先进先出的原则进行的，所以队列又称为先进先出(First In First Out)表，简称FIFO表。队列可以用数组Q1.m来存储，m表示队列所容许的最大容量，队列的运算需要设两个指针：front：对头指针，指向实际队头元素的前一个位置rear：队尾指针，指向实际队尾元素所在的位置元素个数：nrear-front进队：rear+1；出队：front+1空队：frontrear克服假溢出的方法有两种。一种是将队列中的所有元素均向低地址区移动，显然这种方法

6、是很浪费时间的；另一种方法是将数组存储区看成是一个首尾相接的环形区域。当存放到n地址后，下一个地址就翻转为。在结构上采用这种技巧来存储的队列称为循环队列23456781fr 循环队列中，由于入队时尾指针向前追赶头指针；出队时头指针向前追赶尾指针，造成队空和队满时头尾指针均相等。因此，无法通过条件front=rear来判别队列是“空”还是“满”。 解决这个问题的方法至少有三种： 另设一布尔变量以区别队列的空和满； 少用一个元素的空间。约定入队前，测试尾指针在循环意义下加1后是否等于头指针，若相等则认为队满（注意：rear所指的单元始终为空）；使用一个计数器记录队列中元素的总数（即队列长度）。队列

7、元素个数 ：n（rearforntm）mod ml1、已知队列(13，2，11，34，41，77，5，7，18，26，15)，第一个进入队列的元素是13，则第五个出队列的元素是( )。 lA)5 B)41 C)77 D)13 E)18 B2、若用一个大小为6的数组来实现循环队列，且当rear和front的值分别为0和3。当从队列中删除有一个元素，再加入两个元素后，rear何front的值分别为多少？（ ）A.1和5 B.2和4 C.4和2 D.5和13、如图所示的循环队列中元素数目是（ ）。其中tali=32 指向队尾元素，head=15 指向队头元素的前一个空位置，队列空间m=60.A.42

8、 B.16 C.17 D.412、B 3、C栈栈l栈的定义：栈是一种特殊的表这种表只在表头进行插入和删除操作。因此，表头对于栈来说具有特殊的意义，称为栈顶。相应地，表尾称为栈底。不含任何元素的栈称为空栈。l栈的修改是按后进先出的原则进行的，如图1所示。因此，栈又称为后进先出后进先出(Last In First Out)表表，简称为LIFO表表。所以，只要问题满足LIFO原则，就可以使用栈。l栈是只能在某一端插入和删除的特殊线性表。假设一个假设一个n个单元的栈定义为个单元的栈定义为ST，栈顶用，栈顶用top表示表示 入栈：入栈： top top1 出栈：出栈： top top-1； 当当top0

9、时空栈，当时空栈，当top=0个互不相交的集合T1、T2、.Tn，而且， 这些集合的每一个又都是树。树T1、T2、.Tn被称作根的子树(Subtree 树的一些重要概念树的一些重要概念l树的度也即是宽度，简单地说，就是结点的分支数。以组成该树各结点中最大的度作为该树的度，树中度为零的结点称为叶结点或终端结点。树中度不为零的结点称为分枝结点或非终端结点。除根结点外的分枝结点统称为内部结点。l树的深度组成该树各结点的最大层次 l树中每个分叉点称为结点，起始结点称为树根，任意两个结点间的连接关系称为树枝，结点下面不再有分枝称为树叶。结点的前趋结点称为该结点的双亲，结点的后趋结点称为该结点的子女或孩子

10、，同一结点的子女之间互称兄弟。 二叉树二叉树l一、 二叉树的定义l二叉树是一种重要的树型结构，它是n(n=0)个结点的有限集，其子树分为互不相交的两个集合，分别称为左子树和右子树，左子树和右子树也是如上定义的二叉树。二叉树不是树的特例。l二叉树五种基本形态： (1)空二叉树空二叉树(a)；(2)只有一个根结点的二叉树只有一个根结点的二叉树(b)；(3)右子树为空的二叉树右子树为空的二叉树(c)；(4)左子树为空的二叉树左子树为空的二叉树(d)；(5)有左、右子树的二叉树有左、右子树的二叉树(e)二、二叉树的相关概念 （1）结点的度。结点所拥有的子树的个数称为该结点的度。 （2）叶结点。度为0的

11、结点称为叶结点，或者称为终端结点。 （3）分枝结点。度不为0的结点称为分支结点，或者称为非终端结点。一棵树的结点除叶结点外，其余的都是分支结点。 （4）左孩子、右孩子、双亲。树中一个结点的子树的根结点称为这个结点的孩子。这个结点称为它孩子结点的双亲。具有同一个双亲的孩子结点互称为兄弟。（5）结点的层数。规定树的根结点的层数为1，其余结点的层数等于它的双亲结点的层数加1。完全二叉树完全二叉树只有最下面的两层结点度小于只有最下面的两层结点度小于2，并且，并且最下面一层的结点都集中在该层最左边的若干位置的二最下面一层的结点都集中在该层最左边的若干位置的二叉树；叉树；满二叉树满二叉树除了叶结点外每一个

12、结点都有左除了叶结点外每一个结点都有左右子女且叶结点都处在最底层的二叉树右子女且叶结点都处在最底层的二叉树,。 二叉树的性质二叉树的性质l1) 在二叉树中，第i层的结点总数不超过2(i-1)；l (2) 深度为h的二叉树最多有2h-1个结点(h=1)，最少有h个结点；l(3) 对于任意一棵二叉树，如果其叶结点数为N0，而度数为2的结点总数为N2，则N0=N2+1；l (4) 具有n个结点的完全二叉树的深度为trunc（log2n）+1 二叉树的遍历二叉树的遍历二叉树的遍历二叉树的遍历二叉树的遍历二叉树的遍历4、二叉树的遍历、二叉树的遍历4、二叉树的遍历、二叉树的遍历二叉树的遍历二叉树的遍历1)

13、定义：遍历二叉树，就是按一定的规则和顺序走遍二叉树的定义：遍历二叉树，就是按一定的规则和顺序走遍二叉树的所有结点，使每个结点都被访问到一次，且只被访问一次。所有结点，使每个结点都被访问到一次，且只被访问一次。2)遍历方式遍历方式(1)先根次序，简称先序或前序：先根次序，简称先序或前序：访问根结点；访问根结点；按照先跟次序遍历左子树；按照先跟次序遍历左子树；按照先根次序遍历右子树按照先根次序遍历右子树abdgcefhi先序遍历：先序遍历：abdgcefhiabdgcefhi(2)中根次序，简称中序：中根次序，简称中序：按照中根次序遍历左子树；按照中根次序遍历左子树；访问根结点；访问根结点；按照中

14、根次序遍历右子树按照中根次序遍历右子树中序：中序：dgbaechif(3)后根次序，简称后序：后根次序，简称后序：按照后根次序遍历左子树；按照后根次序遍历左子树；按照后根次序遍历右子树按照后根次序遍历右子树访问根结点；访问根结点；后序：后序：gdbeihfcaa+*/ef-cd练习练习（1）写出右图的前序、中序和后序遍历的）写出右图的前序、中序和后序遍历的次序次序若先序遍历此二叉树，可得：若先序遍历此二叉树，可得：-+a*-cd/ef若中序遍历此二叉树，可得：若中序遍历此二叉树，可得：A+*c-d-e/f若后序遍历此二叉树，可得：若后序遍历此二叉树，可得：Acd-*+ef/-（2）已知某二叉树

15、的中序为）已知某二叉树的中序为uwtvs,前序为前序为stuwv,则该二叉树的后序为：则该二叉树的后序为：wuvts(3)已知某二叉树的中序为已知某二叉树的中序为dbeafc,后序为后序为debfca,则该二叉树的前序为则该二叉树的前序为：abdecfl表达式a*(b+c)-d的后缀表达式是：( )lA)abcd*+- B) abc+*d- C) abc*+d- D) -+*abcdB55、二叉排序树、二叉排序树 所谓二叉排序树，是指一棵空的二叉树，或者是一棵具有如下所谓二叉排序树，是指一棵空的二叉树，或者是一棵具有如下特性的非空二叉树：特性的非空二叉树：若它的左子树非空，则左子树上所有的结点

16、的值均小于根结点的值；若它的左子树非空，则左子树上所有的结点的值均小于根结点的值；若它的右子树非空，则右子树上所有结点的值均大于根结点的值若它的右子树非空，则右子树上所有结点的值均大于根结点的值左、右子树本身又是一棵二叉排序树。左、右子树本身又是一棵二叉排序树。6、一般树转换为二叉树、一般树转换为二叉树abcdefghiabcdefghi 转换规则：转换规则：.原树的根仍为转换后二叉树的根；原树的根仍为转换后二叉树的根；.原树中每一个非终端结点的第一个孩子转换后成为原树中每一个非终端结点的第一个孩子转换后成为其双亲的左孩子；其双亲的左孩子；.原树中每一个结点的右边的第一个兄弟孩子转换后原树中每

17、一个结点的右边的第一个兄弟孩子转换后成为它的右孩子。成为它的右孩子。最优二叉树或哈夫曼树最优二叉树或哈夫曼树 在权为wl，w2，wn的n个叶子所构成的所有二叉树中，带权路径长度最小(即代价最小)的二叉树称为最优二叉树最优二叉树或哈夫曼树哈夫曼树。 【例】给定4个叶子结点a，b，c和d，分别带权7，5，2和4。构造如下图所示的三棵二叉树(还有许多棵)，它们的带权路径长度分别为： (a)WPL=7*2+5*2+2*2+4*2=36 (b)WPL=7*3+5*3+2*1+4*2=46 (c)WPL=7*1+5*2+2*3+4*3=35其中(c)树的WPL最小，可以验证，它就是哈夫曼树。 哈夫曼树哈夫

18、曼树最优二叉树，带权路径长度最优二叉树，带权路径长度(WPL)(WPL)最小。最小。1) 1) 哈夫曼树的构造哈夫曼树的构造: :前提条件:给出n个实数 w1，w2， ，wn。操作结果：以给出的n个实数作为叶子的权，构造出哈夫曼树。构造过程如下：需要进行n-1次合并；将开始给定的n个权值看作只有根结点的n棵二叉树，每次合并是将选出的两棵根结点的权值最小的树分别作为左子树和右子树合并成一棵新树；为了保证新树是二叉树，需要增加一个新结点作为新树的根结点，新树的权值为其左右子树根结点的权值之和；这样的合并进行n-1后，最后的二叉树就是所得的哈夫曼树。有关哈夫曼树的结论：有关哈夫曼树的结论：哈夫曼树是

19、严格二叉树。对于有n个叶子结点的哈夫曼树共有2*n-1个结点。哈夫曼树的形状不是唯一的，但带权路径长度是最小的。F : 7 5 2 4F : 7 5 67524初始初始合并合并2 4F : 7 11 752475246611合并合并5 6F : 18 5合并合并7 1127461118101100哈夫曼哈夫曼编码编码主要用途是实现数据压缩。主要用途是实现数据压缩。设给出一段报文：设给出一段报文：CAST CAST SAT AT A TASA 若给每个字符以等长编码若给每个字符以等长编码A : 00 T : 10 C : 01 S : 11则总编码长度为则总编码长度为 ( 2+7+4+5 ) *

20、 2 = 36若按各个字符出现的概率不同而给予不等长编码，若按各个字符出现的概率不同而给予不等长编码，可望减少总编码长度。可望减少总编码长度。以它们为各叶结点上的权值以它们为各叶结点上的权值, , 建立霍夫曼树。建立霍夫曼树。左分左分支支赋赋右分支右分支赋赋得得哈夫曼哈夫曼编码编码( (变长编码变长编码) )。 A : 0 T : 10 C : 110 S : 111它的总它的总编码长度：编码长度：比等长编比等长编码的情形要短。码的情形要短。 总编码长度正好等于总编码长度正好等于哈夫曼哈夫曼树的带权路径长度树的带权路径长度WPLWPL。哈夫曼哈夫曼编码是一种编码是一种无前缀无前缀编码编码。解码

21、时不会混淆。解码时不会混淆。哈夫曼哈夫曼编码树编码树2450001117概述：图是一种非线性的数据结构，在图形结构中，接点之间概述：图是一种非线性的数据结构，在图形结构中，接点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关。的关系可以是任意的，图中任意两个数据元素之间都可能相关。一、图的定义及其相关术语一、图的定义及其相关术语1、定义：图、定义：图G是有两个集合是有两个集合V(顶点集合顶点集合)和和E(边集合边集合)组成的。组成的。V是一个是一个有限的非空的顶点集合，有限的非空的顶点集合，E是边的集合。是边的集合。2、术语：、术语：（1）顶点：图中每一个数据元素都称之为顶点；）顶点

22、：图中每一个数据元素都称之为顶点；（2）有向图：对于一个图）有向图：对于一个图G，若边集合，若边集合E（G）为有向边的集合，则称）为有向边的集合，则称该图为有向图；该图为有向图；（3）无向图：对于一个图）无向图：对于一个图G，若边集合，若边集合E（G）为无向边的集合，则称）为无向边的集合，则称该图为无向图；该图为无向图；（4）端点和邻接点：在一个无向图中，若存在一条边（）端点和邻接点：在一个无向图中，若存在一条边（vi，vj），则称），则称vi，vj为该边的两个端点，并称它们互为邻接点；为该边的两个端点，并称它们互为邻接点；（5）起点和终点：在一个有向图中，若存在一条边（弧）起点和终点：在一个

23、有向图中，若存在一条边（弧），则称该边是顶点则称该边是顶点vi的一条出边，顶点的一条出边，顶点vj的一条入边；称的一条入边；称vi为起点（弧为起点（弧尾），尾），vj为终点（弧头）；为终点（弧头）；vi和和vj互为邻接点；互为邻接点；（6）度、入度、出度：）度、入度、出度： 度：该顶点为边的个数，记为度：该顶点为边的个数，记为D（v）；）； 入度：对于有向图，顶点入度：对于有向图，顶点v的入度是以该顶点为终点的入边数目；的入度是以该顶点为终点的入边数目； 出度：对于有向图，顶点出度：对于有向图，顶点v的出度是以该顶点为起点的出边数目；的出度是以该顶点为起点的出边数目； 有向图顶点的度是该顶点的

24、出度与入度之和；有向图顶点的度是该顶点的出度与入度之和；（7）子图：设有两个集合）子图：设有两个集合G=（V，E）和）和G =（V ，E ），若），若V 是是V的子集，且的子集，且E 是是E的子集，则称的子集，则称G 是是G的子图；的子图；（8）无向完全图：具有）无向完全图：具有n(n-1)/2条边的无向图称为无向完全图；条边的无向图称为无向完全图；（9）有向完全图：具有）有向完全图：具有n(n-1)条边的无向图称为有向完全图；条边的无向图称为有向完全图；(10)路径和路径长度：路径是指图中顶点路径和路径长度：路径是指图中顶点vi1到顶点到顶点vim的一条通路；的一条通路；对于无向图，则顶点序

25、列满足对于无向图，则顶点序列满足( vi1 ， vi1+1 ), ( vim-1 ， vim ) E(G)，对于有向图，则顶点序列满足对于有向图，则顶点序列满足, E(G);路径长度是指一条路径上经过的边的数目；路径长度是指一条路径上经过的边的数目；v1v3v4v2 ( v1, v2), ( v2 , v4), ( v4 , v3)构成从顶点构成从顶点 v1 到到 v3的路径可写成顶点序列的路径可写成顶点序列( v1 , v2，v4 ，v3)，长度为，长度为3v3v2v1(11)简单路径：如果一条路径上的顶点除了起点和终点可以相同简单路径：如果一条路径上的顶点除了起点和终点可以相同外，其它顶点

26、均不相同，则称此路径为一条简单路径。外，其它顶点均不相同，则称此路径为一条简单路径。(12)回路和环：如果一条路径上的开始顶点和结束顶点为同一回路和环：如果一条路径上的开始顶点和结束顶点为同一顶点，则称该路径为回路或环；顶点，则称该路径为回路或环；v1v3v4v2( v1 , v2，v4 ，v3)是一条简单路径；是一条简单路径；( v1 , v2，v4 ，v2)不是一条简单路径。不是一条简单路径。（13）权和网：在一个图中，每条边可以标上具有某种含义的数值，该数）权和网：在一个图中，每条边可以标上具有某种含义的数值，该数值称为该边的权。边上带权的图称为带权图，也称为网。如：下图值称为该边的权。

27、边上带权的图称为带权图，也称为网。如：下图10v589111573024v1v2v3v4图的表示：邻接矩阵表示法和邻接表表示法l假设假设 V = 1, 2, , nl邻接矩阵（邻接矩阵（adjacency matrix） 将图表示成一个将图表示成一个 n x n 矩阵矩阵 A:lAi, j = 1 若边若边 (i, j) E = 0 若边若边 (i, j) El或或 Ai, j = wij 若边若边 (i, j) E （带权图）（带权图） = 0 若边若边 (i, j) E图图: 邻接矩阵邻接矩阵lExample:1243A123410110200103000040010有向图有向图 非对称矩

28、阵非对称矩阵图图: 邻接矩阵邻接矩阵lExample:1243adbcA1234123?4图图: 邻接矩阵邻接矩阵lExample:1243adbcA123410ad0200b030000400c0图图: 邻接矩阵邻接矩阵lExample:12435143A123410350200103000040040图图: 邻接矩阵邻接矩阵lExample:1243adbcA123410ad02a0b03db0c400c0无向图 对称矩阵图: 邻接矩阵l邻接矩阵的实现邻接矩阵的实现 const maxlength=100 最大顶点数最大顶点数type graph=array1.maxlength,1.ma

29、xlength of integer; 二维数组二维数组l输入和查看一遍邻接矩阵需要多少时间？输入和查看一遍邻接矩阵需要多少时间？l答答: O(|V|2)l存储一个邻接矩阵需要多少存储空间？存储一个邻接矩阵需要多少存储空间？l答答: O(|V|2)l稀疏图稀疏图（|E|E| |V|V|或或|E|V|),|E|V|),邻接矩阵是稀疏邻接矩阵是稀疏矩阵，浪费空间，因此采用矩阵，浪费空间，因此采用邻接表邻接表更有效。更有效。图: 邻接矩阵图:邻接表l邻接表邻接表: : 对每个顶点对每个顶点 v V, 将将v的所有邻接点的所有邻接点存放在一个列表中。存放在一个列表中。lExample:lAdj1 =

30、2,3lAdj2 = 3lAdj3 = lAdj4 = 312431243图:邻接表1 12 23 3nilnil2 23 3nilnil3 3nilnil4 43 3nilnill邻接表的实现邻接表的实现Type pointer=adjnode adjnode=record adjvex:integer; 该点在图中的位置该点在图中的位置 next:pointer; 指向下一个顶点的指针指向下一个顶点的指针 infor: ; 与边有关的信息，如权值与边有关的信息，如权值w Adjlist=array1.maxlength of pointer;图:邻接表 无环有向图的拓扑排序无环有向图的拓扑

31、排序 Directed acyclic graphs( DAG) topological sort DAG:不含回路的有向图称为无环有向图。不含回路的有向图称为无环有向图。 检查有向图中是否存在回路的方法之一，检查有向图中是否存在回路的方法之一，是对有向图进行是对有向图进行拓扑排序拓扑排序。 如果有向图如果有向图G有一个有一个拓扑排序拓扑排序,则则G是一个是一个有向无环图有向无环图.反之反之, 任一有向无环图必可进行任一有向无环图必可进行拓拓扑排序扑排序。何谓何谓“拓扑排序拓扑排序”？ 按照有向图给出的次序关系，将图按照有向图给出的次序关系，将图中顶点排成一个线性序列，对于有向图中顶点排成一个线性序列，对于有向图中没有限定次序关系的顶点，则可以人中没有限定次序关系的顶点，则可以人为加上任意的次序关系。为加上任意的次序关系。 由此所得顶点的线性序列称之为由此所得顶点的线性序列称之为拓拓扑有序序列扑有序序列例如：对于下列有向图例如：对于下列有向图BDAC可求得可求得拓扑有序序列拓扑有序序列： A B C D 或或 A C B DBDAC反之，对于下列有向图反之，对于下列有向图不能求得它的拓扑有序序列。不能求得它的拓扑有序序列。因为图中存在一个回路因为图中存在一个回路 B, C, D如何进行拓扑排序？如何进行拓扑排序？一、从有向图中选取一个没有前驱一、从有向图中选取一