数据结构线性表、栈、队列、二叉树、图

1、常见数据结构线性表、栈、队列、二叉树、图（一）、线性表 线性表线性表是n个类型相同的数据元素的有限序列，数据元素之间是一对一的关系，即每个数据元素最多有一个直接前驱和一个直接后继，如图2.1所示。例如：英文字母表(a,b,z)就是一个简单的线性表，表中的每一个英文字母是一个数据元素，每个元素之间存在唯一的顺序关系，如在英文字母表字母b的前面是字母a，而字母b后面是字母c。（二）、栈 栈是允许在一端进行插入和删除操作的特殊线性表。 允许进行插入和删除操作的一端称为栈顶(top)，另一端为栈底(bottom)；栈底固定，而栈顶浮动；栈中元素个数为零时称为空栈。栈结构也称为后进先出表（lifo）。

2、a1 a2 an栈底栈底栈顶栈顶maxsizetop 队列(queue)的定义 队列是限定仅在表的一端进行插入，在另一端进行删除操作的线性表。 允许插入的一端称为队尾(rear)，允许删除的一端称为队首(front)。 队列的插入操作，称为入队；队列的删除操作，称为出队。当队列中没有元素时称为空队列。 设队列q=(a0，a1，a2，an-1)，则a0称为队头元素，an-1称为队尾元素。元素按a0，a1，a2， ，an-1的次序入队，出队也只能按照这个次序。 队列和栈相反，队列的操作是按先进先出（first in first out）的原则进行的，又称为先进先出的线性表（简称fifo表）。三、队

3、列（四）、二叉树（四）、二叉树 类型与定义类型与定义 二叉树或为空树空树；或是由一个根结根结点点加上两棵两棵分别称为左子树左子树和右子树的、互不交的互不交的二叉树二叉树组成。abcdefghk根结点左子树右子树ef二叉树的五种基本形态：二叉树的五种基本形态：n空树空树只含根结点只含根结点nnnlrr右子树为空树右子树为空树l左子树为空树左子树为空树左右子左右子树均不树均不为空树为空树介绍基本术语 叶子结点 结点 结点总数 深度 层abcdefghij 结点的层次从根开始定义起，根结点的层次从根开始定义起，根为第一层，根的孩子为第二层，依次为第一层，根的孩子为第二层，依次累计。累计。 树中结点的

4、最大层次称为树的深树中结点的最大层次称为树的深度或高度。度或高度。 性质性质 1 ： 在二叉树的第 i 层上至多有2i-1 个结点。 (i1)用归纳法用归纳法证明证明： 归纳基归纳基： 归纳假设：归纳假设： 归纳证明：归纳证明：i = 1 层时，只有一个根结点， 2i-1 = 20 = 1；假设对所有的 j，1 j i，命题成立;二叉树上每个结点至多有两棵子树，则第 i 层的结点数 = 2i-2 2 = 2i-1 。 性质性质 2 ： 深度为 k 的二叉树上至多含 2k-1 个结点（k1）证明：证明： 基于上一条性质，深度为 k 的二叉树上的结点数至多为 20+21+ +2k-1 = 2k-1

5、 性质性质 3 ： 对任何一棵二叉树，若它含有n0 个叶子结点、n2 个度为 2 的结点，则必存在关系式：n0 = n2+1证明：证明：设设 二叉树上结点总数 n = n0 + n1 + n2又又 二叉树上分支总数 b = n1 + 2n2而 b = n-1 = n0 + n1 + n2 - 1由此，由此， n0 = n2 + 1两类两类特殊特殊的二叉树：的二叉树：满二叉树满二叉树：指的是深度为k且含有2k-1个结点的二叉树。完全二叉树完全二叉树：树中所含的 n 个结点和满二叉树中编号编号为为 1 至至 n 的结点的结点一一对应。123456789 10 11 12 13 14 15abcde

6、fghij 性质性质 4 ： 具有 n 个结点的完全二叉树的深度深度为 log2n +1证明：证明：设设 完全二叉树的深度为 k 则根据第二条性质得 2k-1 n 2k 即 k-1 log2 n k 因为因为 k 只能是整数，因此，只能是整数，因此， k = log2n + 1满二叉树的叶节点为n，则它的节点总数（ ） a、n b、2n c、2n-1 d、2n+1 e、2n-1 高度为n的均衡的二叉树是指：如果去掉叶结点及相应的树枝，它应该是高度为n-1的满二叉树。在这里，树高等于叶结点的最大深度，根结点的深度为0，如果某个均衡的二叉树共有2381个结点，则该树的树高为（ ）。 a. 10 b

7、. 11 c. 12 d. 13 二叉树的遍历二叉树的遍历 顺着某一条搜索路径巡访巡访二叉树中的结点，使得每个结点均被访问一均被访问一次次，而且仅被访问一次仅被访问一次。一、问题的提出一、问题的提出“访问访问”的含义可以很广，如：输出结点的信息等。 对对“二叉树二叉树”而言，可以而言，可以有三条搜索路径：有三条搜索路径： 1先上后下先上后下的按层次遍历； 2先左先左（子树）后右后右（子树）的遍历； 3先右先右（子树）后左后左（子树）的遍历。二、先左后右的遍历算法二、先左后右的遍历算法先先（根）序的遍历算法中中（根）序的遍历算法后后（根）序的遍历算法根根左子树右子树根根根根根根根根根根 若二叉树

8、为空树，则空操作；否则，（1）访问根结点；（2）先序遍历左子树；（3）先序遍历右子树。先（根）序的遍历算法：先（根）序的遍历算法： 若二叉树为空树，则空操作；否则，（1）中序遍历左子树；（2）访问根结点；（3）中序遍历右子树。中（根）序的遍历算法：中（根）序的遍历算法： 若二叉树为空树，则空操作；否则，（1）后序遍历左子树；（2）后序遍历右子树；（3）访问根结点。后（根）序的遍历算法：后（根）序的遍历算法：abcdefghk例如：例如：先序序列：先序序列：中序序列：中序序列：后序序列：后序序列：a b c d e f g h kb d c a e h g k fd c b h k g f e

9、a前缀、后缀表达式 二叉树的应用。二叉树的应用。 中缀表达式转换后缀表达式中缀表达式转换后缀表达式 从左向右扫描表达式、运算数送到输出队列、运从左向右扫描表达式、运算数送到输出队列、运算符进栈、如果运算优先级大于栈顶元素直接进算符进栈、如果运算优先级大于栈顶元素直接进栈，如果运算优先级小于或等于栈顶元素，则先栈，如果运算优先级小于或等于栈顶元素，则先弹出栈顶元素，再进栈、左括号直接进栈、右括弹出栈顶元素，再进栈、左括号直接进栈、右括号则依次弹出栈中的元素，直到遇到第一个左括号则依次弹出栈中的元素，直到遇到第一个左括号为止。号为止。 有些题目要求写出前缀、中缀和后缀表达式，做有些题目要求写出前缀

10、、中缀和后缀表达式，做这类题目时，可以先通过优先级画出一棵二叉树这类题目时，可以先通过优先级画出一棵二叉树再分别利用先根、中根和后根遍历写出对应的序再分别利用先根、中根和后根遍历写出对应的序列，就是它们的前缀、中缀和后缀表达式。列，就是它们的前缀、中缀和后缀表达式。 表达式a*(b+c)-d的后缀表达式是： a)abcd*+- b) abc+*d- c) abc*+d- d) -+*abcd 假设一棵二叉树的后序遍历序列为dgjhebifca，中序遍历序列为dbgehjacif，则其前序遍历序列为 。 一棵二叉树的中序遍历序列为：dgbaechf，后序遍历序列为：gdbehfca，则前序列遍历

11、序列是 _。数据结构之图 什么是图什么是图 什么是计算机中所说的图?请先看下面的“柯尼斯堡桥问题”。传说在东普鲁士境内，有一座柯尼斯堡城，希雷格尔河流经这个城市的克奈霍福岛后，就将这个城市一分为二，形成如图11（左）的a、b、c、d 4个地区。人们建造了7座桥将这4个地区连起来。在游览中有人提出，是否可以从a地出发，各座桥恰好通过一次，最后又回到原来出发地呢? 这个问题在18世纪被数学家欧拉解决了。他把这个问题转化为图11右边所示的图。图上用a、b、c、d4个顶点分别表示4个地区，用两点间的线段表示连接各地的桥。这样原来的问题就转化为：从a顶点出发经过其中每一条线段一次，而且仅一次，再回到a点

12、的“一笔画”问题。 欧拉对柯尼斯堡问题作出了否定的结论。因为对于每一个顶点，不论如何经过，必须有一条进路和一条出路，所以对每一个顶点(除起点和终点)来说与它有关的线段(称为边)必须是偶数条。而图1-1(右)的顶点有关的线段都是奇数条，因此不可能一笔画出。 欧拉通过对柯尼斯堡桥问题的研究，于1736年发表了著名的关于图论的论文，从而创立了图论的学说。图12一类的问题就是图论中所指的图。 又如，有6个足球队之间进行循环赛，他们比赛的场次可以用图1-3(1)来表示。有3个人相互写信，可以用图13(2)来表示。 从上面两个例子可看出，我们这里所说的图(graph)，与人们通常所熟悉的图，如圆、四边形、

13、函数图象等是很不相同的。是指某些具体事物和这些事物之间的联系。如果我们用点来表示事物(如地点、队)，用线段来表示两事物之间的联系，那么一个图就是表示事物的点集和表示事物之间联系的线段集合所构成。其中线段仅表示两点的关系，它的长短与曲直是无关紧要的。例如图1-4中3个图，被认为是同一个图。图的基本概念图的基本概念 定义定义：图g定义为一个偶对(v，e)，记作g：(v，e)。其中 1)v是一个非空有限集合，它的元素称为顶点； 2)e也是一个集合，它的元素称为边 例如图1-4中的图有4个顶点，4条边。 或者定义或者定义：图g（graph）是由顶点的集合v和边的集合e所组成的二元组，记作：g =（v，

14、e） 其中v是顶点的集合，e是边的集合。无向图无向图与有向图有向图：边的表示方式是用该边的两个顶点来表示的，如果边的表示无方向，那么，对应的图就是无向图，否则称为有向图，如下图所示： 在无向图中，边的两个顶点在边的表示中可以互换，如边（在无向图中，边的两个顶点在边的表示中可以互换，如边（v1,v4）与边（与边（v4,v1）是等价的，表示的是同一条边。）是等价的，表示的是同一条边。（无向图中边的表（无向图中边的表示用圆括号）示用圆括号） 在有向图中，边的走向不同就认为是不同的边。如在边的集合在有向图中，边的走向不同就认为是不同的边。如在边的集合e=,(见右见右上图上图)中，其中中，其中表示该边是

15、由顶点表示该边是由顶点1出发，到顶点出发，到顶点4结束，即结束，即边边表明了该边的方向性，且两个顶点的顺序不能颠倒。表明了该边的方向性，且两个顶点的顺序不能颠倒。（有（有向图中边的表示用尖括号）向图中边的表示用尖括号） 顶点的度顶点的度：与顶点关联的边的数目，有向图顶点的度等于该顶点的入度与出度之和。 入度入度以该顶点为终点的边的数目和 出度出度以该顶点为起点的边的数目和 图的阶图的阶：图中顶点的个数。例如图13中分别是6和3。 度数为奇数的顶点叫做奇点，度数为偶数的点叫度数为奇数的顶点叫做奇点，度数为偶数的点叫做偶点。做偶点。 定理定理1 图g中所有顶点的度数之和等于边数的2倍。因为计算顶点

16、的度数时。每条边均用到2次。定理定理2 任意一个图一定有偶数个奇点。连通连通：如果图中结点：如果图中结点u，v之间存在一条从之间存在一条从u通过若干条边、点到达通过若干条边、点到达v的通路，称的通路，称u、v是连通的。是连通的。连通图连通图：如果一个无向图中：如果一个无向图中,任一对任一对不同顶点不同顶点u、v，都有一条（，都有一条（u，v）通路通路，则，则称图称图g是连通的。是连通的。强连通图强连通图：在有向图：在有向图g中，每一对结点之间都有中，每一对结点之间都有路径路径的图。的图。网络网络：带权的连通图。：带权的连通图。bacdfe 连通连通：如果顶点：如果顶点u，v属于属于g，u，v之

17、间有一条从之间有一条从u通过若干条边到达通过若干条边到达v的通路，则认为顶点的通路，则认为顶点u和和v是是连通的。连通的。 连通图连通图：如果对于图：如果对于图g中每一对不同顶点中每一对不同顶点u，v都都有一条有一条(u，v)通路，则称通路，则称g是连通图。是连通图。 通路指通路指u-边边1-顶点顶点1-边边2-顶点顶点2-v，点和边交替相接，且互不相同。，点和边交替相接，且互不相同。 图的遍历 1、概念：从图中某一结点出发系统地访问图中所有结点，使每个结点恰好被访问一次，这种运算 称图的遍历。为了避免重复访问某个结点，可以设一个标志数组visitedi，未访问时值为false，访问一次后就改为true。 2、分类：深度优先遍历和广度优先遍历。 深度优先遍历深度优先遍历：类似于树的先序遍历，从图中某个结点v0出发，访问此结点，然后依次访问从v0的未被访问的邻接点出发进行深度优先遍历，直到图中所有和v0有路径相通的结点均被访问到。若此时图中尚有结点未被访问，则另选图中一个未被访问的结点v1作为起点，重复上述过程，直至图中所有结点都被访问到为止。广度优先遍历广度优先遍历： 从图中某个结点从图中某个结点v0出发，访问此结点，然后依次访问与出发，访问此结点，然后依次访问与v0邻