2022年数据结构知识 2.pdf

坦洲中学电脑班教程指导：钟志鹏1 数据结构1.1 基本概念和术语数据 ：是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并做计算机程序处理的符号的总称。是计算机程序加工的原料。数据含义极为广泛，如图像、声音等都可以通过编码而归之于数据的范畴。数据元素 ：是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。数据对象： 是性质相同的数据元素的集合，是数据的一个子集。例如：整数数据对象是集合N=0, 1, 2, ,，字母字符数据对象是集合C= A , B , Z 数据结构 ：是相互之间存在一种或多种特定关系的数据元素的集合。通常在任何问题中，数据元素都不是孤立的，而是它们之间存在着某种关系，这种数据元素相互之间的关系称为 结构 。有四类基本结构1.2 线性表1、线性结构的特点：在数据元素的非空有限集中，（1）存在唯一的一个被称做“第一个 ”的元素。（2）存在唯一的一个被称为“最后一个 ”的数据元素； （3）除第一个之外，集合中的每个数据元素均只有一个前驱； （4）除最后一个之外，集合中的每个数据元素均只有一个后继。2、线性表 是几个数据元素的有限序列。至于每个数据元素的含义，在不同的情况下各不相同，它可以是一个数，或一个符号，也可以是一页书，甚至其它更复杂的信息。如： 26 个英文字母的字母表：（A,B,C, ,Z）是一个线性表，表中的数据元素是单个字母字符。3、线性表中元素的个数n （n0）定义为线性表的长度 ，可以根据需要增长而缩短，n=0 时称为 空表 。4、在非空表中的每个数据元素都有一个确定的位置，如a 是第一个数据元素，an是最后一个数据元素， ai是第 i 个元素，称之为数据元素ai在线性表中的 位序 。1.2.1 线性表的顺序表示和实现集合 ：数据元素间除了“同属一个集合”的关系外，别无其它关系。线性结构 ：结构中的数据元素之间存在一个对一个的关系。树形结构 ：结构中的数据元素之间存在一个对多个的关系。图状或网状结构：结构中的数据之间存在多个对多个的关系。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 13 页 - - - - - - - - - 坦洲中学电脑班教程指导：钟志鹏2 线性表的顺序表示指用一组地址连续的存储单元，依次存储线性表的数据元素。假设线性表的每个元素需占用 L 个存储单元， 并以所占的第一个单元的存储地址作为数据元素的存储位置，则线性表中第i+1 个数据元素的存储位置Loc(ai+1)和第 i 个数据元素的存储位置Loc(ai)之间满足下列关系：Loc(ai+1)= Loc(ai)+L 一般来说，线性表的第i 个元素 ai的存储位置为Loc(ai)=Loc(a1)+(i-1)*L 式中 Loc(a1)是线性表的第一个数据元素a1的存储位置，通常称做线性表的起始位置或基地址。具有此种存储结构的线性表称为顺序表。存储地址内存状态数据元素在线性表中的位序b a1 1 b+l a2 2 b+(i-1)*L ai i . b+(n-1)*L an n b+nL b+(maxlen-1)*L 1.2.2 线性表的链式表示和实现链式存储结构的特点：用一组任意的存储单元存储线性表的数据元素（这些存储单元可以是连续的，也可以是不连续的） 。因此，为了表示每个数据元素ai与其直接后继元素ai+1之间的逻辑关系，对数据元素 ai来说，除了存储其本身的信息之外，还需存储一个指示其直接后继 的信息（即直接后继的存储位置）。这两部分信息组成数据元素ai的存储映象，称为结点（Node） ，它包括两个 域：其中存储数据元素信息的域称为数据域 ，存储直接后继存储位置的域称为指针域 。指针域中存储的信息称做指针或链。几个结点（ ai(1in)）的存储映象链结成一个链表，即线性表：（a1,a2,an）的链式存储结构。又：每个结点中只包含一个指针域，故又称线性链表 或单链表 。例：线性表（ZHAO,QIAN,SCN,LI,ZHOU,WU,ZHENG,WANG ）的线性链表存储结构，整个链表的存取必须从头指针开始。弱点：在播入或删除操作时，需移动大量元素。只要确定了存储线性表的起始位置，线性表中任一数据元素都可随机存取，所以线性的顺序存储结构是一种随机存储结构。总之，线性表的顺序存储结构的特点是逻辑关系上相邻的两个元素在物理位置上也相邻。因此，可以随机存取表中任一元素，它的存储位置可以用一个简单直观的公式来表示。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 13 页 - - - - - - - - - 坦洲中学电脑班教程指导：钟志鹏3 存储地址数据域指针域1 LI 43 7 QIAN 13 13 SUN 1 19 WANG NULL 25 WU 37 31 ZHAO 7 37 ZHENG 19 43 ZHOU 25 注：链式结构是非随机存储的结构。逻辑状态：H 1.2.3 循环链表循环链表 ：是另一种形式的链式存储结构。它的特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环。因此，从表中任何一结点出发均可找到表中其它结点。头指针 H ZHAO QIAN SUN LI ZHOU WU ZHENG WANG 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 13 页 - - - - - - - - - 坦洲中学电脑班教程指导：钟志鹏4 H (A) 非空循环链表H （B）空循环链表2.1 栈栈和队列是两种重要的线性结构。从数据结构角度看，栈和队列也是线性表，其特殊性在于栈和队列的基本操作是线性表操作的子集。栈是限定仅在表尾进行插入或删除操作的线性表。对栈来说， 表尾端有其特殊的含义，称为 栈顶 ，相应地表头端称为栈底 。不含元素的空表称为空栈 。栈又称为 后进先出 （ Last In First out ）的线性表（简称LIFO 结构 ） 。出进栈顶（ top）出进栈底（ bottom）（a）栈的示意图（b）用铁路调度站表示栈2.2 队列队列是一种先进先出（First In First out ，缩写为FIFO ）的线性表 。它只允许在表的一端进行插入，而在另一端删除元素。这和我们日常生活中的排队是一致的，最早进入队列的元素最早离开。队列中，允许插入的一端叫队尾 （rear） ，允许删除的一端叫队头 （front） 。设队列为q=(a1,a2, , an) 那么， a1就是队头元素，an就是队尾元素。a1 a2 an 进栈出栈名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 13 页 - - - - - - - - - 坦洲中学电脑班教程指导：钟志鹏5 出队列入队列a1 a2 a3 an-1 an 队头队尾队列示意2.2.1 队列的链式表示和实现用链表表示的队列称链队列 。一个队列显然需要两个分别指向队头和队尾的指针（分别称为 头指针 和尾指针 ）才能唯一确定。为操作方便，也给链队列添加一个头结点 ，并令头指针指向头结点。由此，空的链队列的判决条件为头指针和尾指针都指向头结点链队列示意图2.2.2 队列的顺序表示和实现循环队列：初始化时，front= rear=o 当插入新队列尾元素，尾指针增1 当删除队列头元素时“头指针增1”因此， 在非空队列中，头指针始终指向队列头元素，而尾指针始终指向队列尾元素的下一个位置3.1 树的定义树的 度为树中各结点度的最大值祖先 指从根到该结点所经历分支上的所有结点以某结点为根的子树中的任一结点都称为该结点的子孙 ，如 B的子孙为 E、F、K、L 其双亲在同一层次上的结点称为堂兄弟 ，树中结点的最大层次称为树的深度 。图中为 4 Data next Q.front 队头队尾Q.rear 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 13 页 - - - - - - - - - 坦洲中学电脑班教程指导：钟志鹏6 只有根结点的树二叉树的定义 ：是一种树型结构，它的特点是每个结点至多只有二棵子树（即二叉树中不存在度大于2 的结点）并且，二叉树的子树有左右之分，其次序不能任意颠倒。递归定义：二叉树或为空，或是由一个根结点加上两棵分别称为左子树和右子树，互不相交的二叉树组成。二叉树五种基本形态： , , , , (1) (2) (3) (4) (5) 二叉树五种基本形态遍历二叉树 ：如何按某条搜索路径巡访树中的每个结点，使得每个结点均被访问一次，而且仅被访问一次。 （注：“访问”的含义很广，可以是对结点作各种处理，如输出结点信息）二叉树表示下述表达式： a+b*(c-d)-e/f 先根（ 先序 ）遍历结果：-+a*b-cd/ef( 前缀表达式 （波兰式）) 中根 （中序 ）遍历结果：a+b*c-d-e/f（中缀表达式）后根（后序 ）遍历结果：abcd-*+ef/-（后缀表达式 （逆波兰式）三种遍历结果比对A B C D E F GH I J K L M 一般的树：B 结点称 E，F 结点的双亲结点A 为根结点A 结点的度为3 E，F 结点称 B 结点的孩子E，F 互称为兄弟1 层叶子结点结点2 层4 层3 层A + / a * b c d e f 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 13 页 - - - - - - - - - 坦洲中学电脑班教程指导：钟志鹏7 满二叉树 ：一棵深度为k 且有 (2k-1)个结点的二叉树，若对满二叉树的结点进行编号，约定编号从根结点开始，自上而下，自左而右，由此引出： 3层的满二叉树及其编号它有： （23-1 ）=7个结点完全二叉树的定义：深度为 R的，有 n 个结点的二叉树，当且仅当其每一个结点都与深度为R的满二叉树中编号从1 至 n 的结点一一对应，称之为完全二叉树。一棵完全二叉树及其编号3.2 赫夫曼树（最优二叉树）路径长度： 从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径，路径上的分支数目称为路径长度 。树的路径长度 ，是从树根到每一结点的路径长度之和。完全二叉树就是这种路径长度最短的二叉树。结点的带权路径长度为从该结点到树根之间的路径长度与结点上权的乘积。树的带权路径长度为树中所有叶子结点的带权路径长度之和，通常记作：WPL= 赫夫曼树： 假设有几个权值 W1，W2，, ，Wn 试构造一棵有n 个叶子结点的二叉树，每个叶子结点带权为Wi，则其中带权路径长度WPL 最小的二叉树称为最优二叉树或赫夫曼树。n R=1 WRLRn 个叶子结点1 2 4 5 3 6 7 1 2 5 3 4 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 13 页 - - - - - - - - - 坦洲中学电脑班教程指导：钟志鹏8 例：有 4 个叶子结点a.b.c.d.分别带权 7,5,2,4 2 7 5 4 7 5 2 4 2 4 7 5 (a) (b) (c) (a)WPL= 7 2+52+2 2+42=36 (b)WPL=73+53+21+42=46 (c)WPL=71+52+23+43=35 以(c) 最小，可以验证，它恰为赫夫曼树构造赫夫曼树的算法：（1）根据给定的几个权值 W1， W2，, , Wn 构成 n 棵二叉树的集合F= T1,T2.，Tn , 其中每棵二叉树Ti 中只有一个带权为W3的根结点，其左右子树均为空。（2）在 F 中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左，右子树上根结点的权值之和。（3）在 F 中删除这两棵树，同时将新得到的二叉树加入F 中（4）重复（ 2） ， （3） ，直到 F只含一棵树为止。这棵树便是赫夫曼树。注：这样生成的赫夫曼树不一定是唯一的，但是这些二叉树的带权路径长度一定相等。题：设权（ 5，29，7，8，14，23，3，11）试构造一棵赫夫曼树。3.3 二叉树补充1、已知结点的前序序列和中序序列，求整棵二叉树。根据前序遍历定义，二叉树前序遍历是先访问根结点D，其次遍历左子树L，最后遍历右子树R。即在结点的前序序列中，第一个结点必是根D ；而另一方面，由于中序遍历是先遍历左子树，然后访问根 D， 最后遍历右子树R， 由结点 D将中序序列分割成两部分，在 D之前是左子树结点的中序序列，在D 之后是右子树结点的中序序列。反过来，根据左子树的中序序列中结点个数，又可将前序序列除根a b d c a d b c d c b a 根结点根结点根结点名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 13 页 - - - - - - - - - 坦洲中学电脑班教程指导：钟志鹏9 以外分成左子树的前序序列和右子树的前序序列两部分。依次类推，便可递归得到整棵二叉树。例：已知前序序列：ABCDEFG 中序序列： CBEDAFG 可通知如下图方式求得整棵二叉树上图由前序和中序序列构造一棵二叉树的过程2、二叉排序树二叉排序树或者是一棵空树，或者是具有这样性质的二叉树；（1）若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；（2）若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；（3）它的左、右子树也分别为二叉排序树。 (a) (b) 二叉排序树又称二叉查找树 ，查找过程：二叉排序树不空时，先将给定值和根结点的关键字比较，若相等，则查找成功，否则，将依据给定值和根结点的关键字之间的大小关系，分别在左子树或右子树上继续进行查找。如何从已知关键字序列, 生成一颗二权排序树? A F G B C D E A B C D E F G A B C D E F G A B C D E F G 45 12 3 37 53 24 78 90 100 61 CAO ZHAO DING CHEN WANG CAO DU LI MA 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 13 页 - - - - - - - - - 坦洲中学电脑班教程指导：钟志鹏10 例: 已知序列为 45,24,53,45,12,24,90则生成二叉排序树的过程如图所示: ， (a) 空树(b) 插入 45(c) 插入 24 (d) 插入 53 (e)插入 12 （f ）插入 90 二叉排序树的构造过程说明 :(a) 空树 (b)插入 45 (c)插入 24 (d)插入 53 (e) 插入 12 (f)插入 90 构造方法 : 每进一个新数均需与最顶根结点比较大小, 然后根据比较的结果, 再依次与左 / 右子树根结点比较。 容易看出， 中序遍历二叉排序树可得到一个关键字的有序序列。一个无序序列可以通过构造一颗二叉排序树而变成一个有序序列，构造树的过程即为对无序序列进行排序的过程。又：每次插入的新结点都是二叉排序树上新的叶子结点，则进行插入操作时，不必移动其它结点，仅需改动整某个结点的指针，由空变为非空即可。表明在一个有序序列上插入一个记录存储结构，因此是动态查找表的一种适宜表示。3、平衡二叉树又称 AVL树。递归定义：它或者是一棵空树，或者是具有下列性质的二叉树，它的左子树和右子树都是平衡二叉树，且左子树和右子树深度之差的绝对值不超过1。若将二叉树上结点的平衡因子BF（Balance Facdor） 定义为该结点的左子树的深度去它右子树的深度，则平衡二叉树上所有结点的平衡因子只可能是-1 ，0 和 1。只要二叉树上有一个结点的平衡因子的绝对值大于1，则该二叉树就是不平衡的。（a）平衡二叉树 (b)不平衡二叉树45 45 24 45 45 24 53 24 53 12 45 24 12 53 90 1 1 0 0 0 1 -1 1 0 0 1 0 1 0 0 1 0 -1 2 0 0 -2 0 1 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 13 页 - - - - - - - - - 坦洲中学电脑班教程指导：钟志鹏11 3.4 哈希表在前面讨论的各种结构（线性表、树等）中，查找记录时需进行一系列的关键字的比较。这类查找的方法建立在“比较”的基础上。但是，我们希望不经过任何比较，一次存取便能得到记录，那就必须在记录的存储位置和它的关键字之间建立一个确定的对应关系f ，使每个关键字和结构中一个唯一的存储位置相对应。我们称这个对应关系f 为哈希（ Hash）函数，按这个思想建立的表称为哈希表。哈希函数的构造方法a.直接定址法H(key)=Key 或 H(key)=a.Rey+b 其中 a 和 b 为常数（这种哈希函数称为自身函数）b.除留余数法取关键字被某个不大于哈希表表长m的数 p 除后所得余数为哈希地址。即 H(Rey)=ReyMODP PM 通常： p 为质数或不包含小于20 的质因素的合数处理冲突的方法a.开放地址法Hi=(H(Rey)+di)MODm i=1,2,R(R m-1) 其中， H(Rey) 为哈希函数，m为哈希表长， di 为增量序列，可有下列三种取法：（1）di=1 ，2，3, ,m-1，称线性探测再散列， （2）di=12,-12,22,-22, , R2(Rm/2) 称二次探测再散列； （3）di= 伪随机数列，称伪随机探测再散列。（4）再哈希法：Hi=RHi(Rey) i=1,2, ， R RHi 均是不同的哈希函数，即在同义词产生地址冲突时计算另一个哈希函数地址，直到冲突不再发生。（5） 链地址法（6）建立一个公式溢出区名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 13 页 - - - - - - - - - 坦洲中学电脑班教程指导：钟志鹏12 4.1 图一、图的表示：G1= （Vi ，Ai ）其中： V1=V1，V2，, ，Vi A1=(Vi,Vi),(,), , 注: 有向图称为孤，无向图称为边二、连通图 ：对于图中任意两个顶点Vi,Vj,GV,Vi和 Vj 都是连通的，则称G是连通图。连通分量指无向图中的极大连通子图。 n(n-1)边三、完全图 n(n-1)孤有向图强连通图 ：有向图中，若从Vi 到 Vj 和从 Vj 到 Vi 都存在路径，则为强连通图一棵有 N个顶点的生成树有目仅有n-1 条边。若边数小于n-1 ，则是非连通图，若边数大于n-1 ，则树中必定存在着环，但有n-1 条边的图，不一定是生成树。有向树 ：有向图中恰有一个顶点的入度为O,其余顶点的入度均为1. 注：只有在有向图中，才有顶点的入度与出度之分。深度优先遍历：类似于是树的先根遍历，是先根遍历的推广。四、广度优先遍历：类似于树的按层次遍历的过程，原则使先被访问的顶点的邻接点先于后被访问的顶点的邻接点被访问。其中一个深度优先遍历序列为：V1 V2 V4 V8 V5 V3V6 V7 其中一个广度优先遍历序列：V1 V2 V3 V4 V5 V6 V7 V8 有向无环图及其应用存顶点信息1 2 存弧或边的信息名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 13 页 - - - - - - - - - 坦洲中学电脑班教程指导：钟志鹏13 AOV网：用孤表示活动间的优先关系的有向图称为顶点表示活动的网拓扑排序：在有向图中选一个没有前驱的顶点且输出之从图中删除该顶点和所有以它为尾的孤。重复上述两步，直至全部顶点均已输出，或当前图中不存在无前驱的顶点为止，后一种情况说明有向图中存在环。最小生成树问题假设要在 n 个城市间建立通信联络网，则连通n 个城市只要n-1 条线路。当然，n 个城市间，最多可以设置 n(n-1)/2条线路，而建每一个线路的费用是不同的，问题是：如何在这n(n-1)/2条线中，作出恰当的选择，使得选出的n-1 条线路花费最小，最小生成树的MST性质，在所有的最性成树中，必须存一颗包含权值最小的边的生成树！普里姆算法：假设 N= （V，E ）是连通图，TE是 N上最小生成树中边的集合。算法从V=Uo(Vo V ，TE=) 开始，重复执行这样的动作：在所有U E ，V V-U的边（ V，U） E 中找一条代价最小的边（VO ，VO ）并入集合 TE，同时 Vo 并入 U，直至 U=U为止。此时， TE中必有 n-1 条边，则 T=(U,TE)为 n 的最小生成树。克鲁斯卡尔算法：先挑图中最小权值的边，再挑次小的边，并且看该边两端的顶点，是否落在不同的连通分量上，若是则留下，若不是，则继续选择下一条代价最小的边。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页，共 13 页 - - - - - - - - -