数据结构知识点整理

《数据结构知识点整理》由会员分享，可在线阅读，更多相关《数据结构知识点整理（6页珍藏版）》请在装配图网上搜索。

1、数据是信息的载体，是描述客观事物的数、字符、以及所有能输入到计算机中，被计算机程序识别和处理的符号（数 值、字符等）的集合。数据元素（数据成员）是数据的基本单位。在不同的条件下，数据元素又可称为元素、结点、顶点、记录等 数据对象具有相同性质的数据元素（数据成员）的集合数据结构由某一数据对象及该对象中所有数据成员之间的关系组成。记为Data_Structure = D, R其中，D是某一数据 对象，R是该对象中所有数据成员之间的关系的有限集合。数据类型是指一种类型，以及定义在这个值集合上的一组操作的总称。 判断一个算法的优劣主要标准：正确性、可使用性、可读性、效率、健壮性、简单性。算法效率的衡量

2、方法：后期测试，事前估计 算法分析是算法的渐进分析简称数据结构包括“逻辑结构” 和“物理结构”两个方面（层次）:逻辑结构是对数据成员之间的逻辑关系的描述，它可以用一个数据成员的集合和定义在此集合上的若干关系来表示物 理结构是逻辑结构在计算机中的表示和实现，故又称“存储结构”线性表的定义：n（ 0）个表项的有限序列L = （al, a2,，an）ai是表项，n是表长度。第一个表项是表头，最后 一个是表尾。线性表的特点：表中元素的数据类型相同；线性表中，结点和结点间的关系是一对一的，有序表和无序表线性表的存 储方式。一，顺序存储方式，二，链表存储方式。顺序表的存储表示有 2 种方式：静态方式和动态

3、方式。 顺序表的定义是：把线性表中的所有表项按照其逻辑顺序依次存储到从计算机存储中指定存储位置开始的一块连续的 存储空间中。顺序表的特点：用地址连续的一块存储空间顺序存放各表项，各表项的逻辑顺序与物理顺序一致，对各个表项可以顺 序访问，也可以随机访问 。单链表是一种最简单的链表表示，也叫线性链表，用她来表示线性表时，用指针表示结点间的逻辑关系。特点：是长 度可以很方便地进行扩充。连续存储方式（顺序表）特点：存储利用率高，存取速度快缺点：插入、删除等操作时需要移动大量数据： 链式存储方式（链表） 特点：适应表的动态增长和删除。缺点：需要额外的指针存储空间单链表的类定义：多个类表达一个概念（单链表

4、）。分为：链表结点（ListNode）类，链表（List）类。循环链表的概念：是另一种形式的表示线性表的链表，它的结点结构与单链表相同，与单链表不同的是链表中表尾结 点的LINK域中不是NULL，而是存放了一个指向链表开始结点的指针，这样，只要知道表中任何一个结点的地址， 就能遍历表中其他任何一结点。双向链表的概念：在双向链表的没饿结点中应有两个链接指针作为它的数据成员：1LINK指示它的前驱结点，RLINK 指示它的后继结点，因此，双向链表的每个结点至少有3个域：1LINK（前驱指针）DADA（数据）RLINK（后继指针）。 栈：定义为只允许在表的末端进行插入和删除的线性表。特点是：后进先出

5、。递归的定义 ：若一个对象部分地包含它自己，或用它自己给自己定义, 则称这个对象是递归的；若一个过程直接地或 间接地调用自己, 则称这个过程是递归的过程。以下三种情况常常用到递归方法一。 定义是递归的二。 数据结构是递 归的三问题的解法是递归的。队列：队列是只允许在一端删除，在另一端插入的顺序表允许删除的一端叫做队头，允许插入的一端叫做队尾。特性 先进先出。优先级队列：是不同于先进先出队列的另一种队列。每次从队列中取出的是具有最高优先权的元素。多维数组是一维 数组的推广。多维数组是一维数组的推广。多维数组的特点是每一个数据元素可以有多个直接前驱和多个直接后继。数组元素的下 标一般具有固定的下界

6、和上界，因此它比其他复杂的非线性结构简单。字符串是n （ 0 ）个字符的有限序列，记作S : “”其中，S是串名字”是串值ci是串中字符n是 串的长度， n = 0 称为空串。广义表是n （三0 ）个表元素组成的有限序列，记作LS （al, a2, a3,，an），LS是表名，ai是表元素，可以是表（称为 子表），可以是数据元素（称为原子）。n为表的长度。n = 0的广义表为空表。n 0时，表的第一个表元素称为广义表 的表头（head），除此之外，其它表元素组成的表称为广义表的表尾（tail有根树：一棵有根树T简称为树，它是n （n0）个结点的有限集合。当n = 0时，T称为空树；否则，T是非

7、空树， 记作 T= 空集 n=0r,T1,T2. .Tn,n0r是一个特定的称为根（root）的结点，它只有直接后继，但没有直接前驱；根以外的其他结点划分为m （m 0）个互不 相交的有限集合T1, T2,Tm,每个集合又是一棵树，并且称之为根的子树。每棵子树的根结点有且仅有一个直接前 驱，但可以有0个或多个直接后继 二叉树的定义:一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根结点加上两棵分别称为左子树和 右子树的、互不相交的二叉树组成。完全二叉树:-若设二叉树的深度为k,则共有k层。除第k层外，其它各层（1k-1）的结点数都达到最大个数， 第 k 层从右向左连续缺若干结点，这

8、就是完全二叉树二叉树的遍历就是按某种次序访问树中的结点，要求每个结点访问一次且仅访问一次。设访问根结点记作V遍历根的 左子树记作L遍历根的右子树记作R。则可能的遍历次序有:前序VLR镜像VRL；中序LVR镜像RVL；后序LRV 镜像 RLV前序遍历二叉树算法的框架是：若二叉树为空，则空操作；否则访问根结点（V）；前序遍历左子树（L）；前序遍历右子 树（R）。遍历结果-+ a * b - c d / e f树的后根次序遍历:当树非空时依次后根遍历根的各棵子树访问根结点：树后根遍历EFBCGDA；对应二叉树中序遍历 EFBCGDA；树的后根遍历结果与其对应二叉树。表示的中序遍历结果相同:树的后根遍

9、历可以借助对应二叉树的中序遍历算法实现最小堆和最大堆：如果有一个关键码集合K=K0,K1, K2, K3, .Kn-l，把它的所有元素按完全二叉树的顺序存储 方式存放在一个一维数组中。并满足KiWK2i+1且KiWK2i+2（或者Ki三K2i+1且KiK2i+2 ）i=0,1,. （n-2） /2,则称 这个集合为最小堆或最大堆。堆是最高效的一种数据结构，每次出队列的是优先权最高的元素。用堆实现其存储表示，能够高效运作。 堆的建立：有2种方式建立最小的堆，一种方式是通过第一个构造函数建立一个空堆，其大小通过动态存储分配得到， 另一中建立最小堆的方式是通过第二个构造函数复制一个记录数组并对其加以

10、调整形成一个堆。路径：从树中一个结点到达另一个结点之间的分支构成该两结点之间的路径。 路径长度：是指路径上的分支条数，树的路径长度是从树的根结点到每一个结点的路径长度之和。由树的定义，从根 结点到达书中每一结点有且仅有一条路径。Huffman 树：带权路径长度最小的二叉树应是权值大的外结点离根结点最近的扩充二叉树。 带路径长度最小的扩充二 叉树不一定是完全二叉树。集合是成员（元素）的一个群集。集合中的成员可以是原子（单元素），也可以是集合。字典是一些元素的集合，每个元素有一个称作关键码（key）的域，不同元素的关键码互不相同。 散列方法：理想的搜索方法是可以不经过比较，一次直接从字典中得到要搜

11、索的元素。如果在元素存储位置与其关键 码之间建立一个确定的对应函数关系Hash（）,使得每个关键码与结构中一个唯一的存储位置相对应：Address = Hash（key）。在插入时依此函数计算存储位置并按此位置存放。在搜索时对元素的关键码进行同样的计算，把求得的函 数值当做元素存储位置，在结构中按此位置搜索。这就是散列方法。在散列方法中所用转换函数叫做散列函数。按此 方法构造出来的表叫做散列表。使用散列方法进行搜索不必进行多次关键码的比较, 搜索速度比较快, 可以直接到达或 逼近具有此关键码的表项的实际存放地址。散列函数是一个压缩映象函数。关键码集合比散列表地址集合大得多。因此有可能经过散列函

12、数的计算，把不同的关 键码映射到同一个散列地址上，这就产生了冲突搜索就是在数据集合中寻找满足某种条件的数据对象。搜索的结果通常有两种可能：搜索成功，即找到满足条件的数 据对象。这时，作为结果，可报告该对象在结构中的位置, 还可给出该对象中的具体信息。搜索不成功，或搜索失败。作为结果，应报告一些信息, 如失败标志、位置等 搜索结构通常称用于搜索的数据集合为搜索结构，它是由同一数据类型的对象（或记录）组成。在每个对象中有若干属性， 其中有一个属性，其值可唯一地标识这个对象。称为关键码。使用基于关键码的搜索，搜索结果应是唯一的。但在实 际应用时，搜索条件是多方面的，可以使用基于属性的搜索方法，但搜索

13、结果可能不唯一。实施搜索时有两种不同的 环境。静态环境，搜索结构在插入和删除等操作的前后不发生改变。一静态搜索表动态环境，为保持较高的搜索效 率，搜索结构在执行插入和删除等操作的前后将自动进行调整，结构可能发生变化。一动态搜索表 顺序搜索主要用于在线性表中搜索。设若表中有 CurrentSize 个元素，则顺序搜索从表的先端开始，顺序用各元素的关 键码与给定值 x 进行比较若找到与其值相等的元素，则搜索成功，给出该元素在表中的位置。若整个表都已检测完仍 未找到关键码与 x 相等的元素，则搜索失败。给出失败信息二叉搜索树或者是一棵空树，或者是具有下列性质的二叉树：1每个结点都有一个作为搜索依据的

14、关键码（key）,所有 结点的关键码互不相同。 2左子树（如果非空）上所有结点的关键码都小于根结点的关键码。 3右子树（如果非空）上 所有结点的关键码都大于根结点的关键码。 4 左子树和右子树也是二叉搜索树。二叉搜索树为二叉排序树如果对一棵二叉搜索树进行中序遍历，可以按从小到大的顺序，将各结点关键码排列起来， 所以也称二叉搜索树为二叉排序树在二叉搜索树上进行搜索，是一个从根结点开始，沿某一个分支逐层向下进行比较判等的过程。它可以是一个递归的 过程。假设想要在二叉搜索树中搜索关键码为x的元素，搜索过程从根结点开始。如果根指针为NULL,则搜索不成 功；否则用给定值 x 与根结点的关键码进行比较：

15、若给定值等于根结点关键码，则搜索成功，返回搜索成功信息并报 告搜索到结点地址。若给定值小于根结点的关键码，则继续递归搜索根结点的左子树；否则。递归搜索根结点的右子 二叉搜索树的插入算法：为了向二叉搜索树中插入一个新元素，必须先检查这个元素是否在树中已经存在。在插入之 前，先使用搜索算法在树中检查要插入元素有还是没有。如果搜索成功，说明树中已经有这个元素，不再插入；如果 搜索不成功，说明树中原来没有关键码等于给定值的结点，把新元素加到搜索操作停止的地方。图定义：图是由顶点集合(vertex)及顶点间的关系集合组成的一种数据结构：Graph=( V, E )其中 V = x I x e某 个数据对

16、象 是顶点的有穷非空集合；E = (x, y) I x, y e V 或E = I x, y e V & Path (x, y),是顶点之间关 系的有穷集合，也叫做边(edge)集合。Path (x,y)表示从x到y的一条单向通路，它是有方向的。有向图与无向图：在有向图中，顶点对vx, y是有序的。在无向图中，顶点对(x, y)是无序的。完全图：若有 n 个顶点的无向图有 n(n-1)/2 条边, 则此图为完全无向图。有 n 个顶点的有向图有 n(n-1) 条边, 则此 图为完全有向图 在图的邻接矩阵表示中，有一个记录各个顶点信息的顶点表，还有一个表示各个顶点之间关系的邻接矩阵。邻接表是邻接矩

17、阵的改进形式。为此需要把邻接矩阵的各行分别组织为一个单链表。在邻接表中，同一个顶点发出的 边链接在同一个边链表中，每一个链结点代表一条边(边结点)，结点中有另一顶点的下标dest和指针link。对于带 权图，边结点中还要保存该边的权值cost。顶点表的第i个顶点中保存该顶点的数据，以及它对应边链表的头指针adj 最短路径问题：如果从图中某一顶点(称为源点)另一顶点(称为终点)的路径可能不止一条，如何找到一条路径使 得沿此路径上各边上的权值总和达到最小。排序：将一组杂乱无章的数据按一定的规律顺次排列起来。数据表(血個伽/):它是待排序数据元素的有限集合。排序码(key):通常数据元素有多个属性域

18、，即多个数据成员组成，其中有一个属性域可用来区分元素，作为排序依据。 该域即为排序码。每个数据表用哪个属性域作为排序码，要视具体的应用需要而定。插入排序基本方法是：每步将一个待排序的元素，按其排序码大小，插入到前面已经排好序的一组元素的适当位置上, 直 到元素全部插入为止。链表1、单链表中的插入与删除第一种情况：在第一个结点前插入 newnodelink = first;first = newnode；第二种情况：在链表中间插入 newnodelink = plink;plink = newnode；第三种情况：在链表末尾插入newnodelink = plink;pUnk = last =

19、newnode；2、链表插入算法实现int List:Insert (const int x, const int i) /在链表第i个结点处插入新元素xListNode *p = first; int k = 0;while (p != NULL & k i -1) p =plink; k+; /找第i-1个结点if (p = NULL & first != NULL) cout “无效的插入位置!n”；return 0;ListNode *newnode= new ListNode(x, NULL); 创建新结点，其数据为x,指针为0if (first = NULL | i = 0 ) /

20、插在表前newnodelink = first;if (first = NULL) last = newnode; first = newnode;else 插在表中或末尾newnodelink = plink;if (p link = NULL) last = newnode; plink = newnode;return 1;在带表头结点的单链表，第一个结点前插入新结点 newnodelink = plink;if (plink = NULL) last = newnode;plink = newnode;排序3、链表结点删除算法int List:Remove (int i) /在链表中删

21、除第i个结点Node *p = first, *q; int k = 0;while (p != NULL & k i-1 ) p =plink; k+; /找第i-1个结点if (p = NULL | plink = NULL) cout template vclass Tvoid InsertSort (dataListvT& L, int left, int right) void BinaryInsertSort (dataListvT& L,依次将兀素LVectori按其排序码插入到有序表const int left, const int right) /LVectorleft,LV

22、ector-1中，使得利用折半搜索，在 L.Vectorleft到 L.Vectori-1中/L.Vectorleft到 LVectori有序。查找LVectori应插入的位置，再进行插入。ElementvT temp; int i, j;ElementvT temp;for (i = left+1; i v= right; i+)int i, low, high, middle, k;if (Li = left & temp v Lj);if (temp v Lmiddle)插入值小于中点值Lj+1 = temp;high = middle-1;向左缩小区间else low = middle

23、+1;否贝山 向右缩小区间;for (k = i-1; k = low; k-) Lk+1 = Lk;成块移动,空出插入位置Llow = temp;插入;堆排序的算法直接选择排序的算法template vclass T#include dataList.hvoid HeapSort (dataListvT& L) template vclass T对表LVector0到LVectorn-1进行排序，使得表void SelectSort (dataListvT& L,中各个兀素按其排序码非递减有序const int left, const int right) int i, n = L.leng

24、th();for (int i = left; i v right; i+) for (i = (n-2)/2; i = 0; i-) 将表转换为堆int k = i;/在 Li到Ln-1找取小排序码兀素siftDown (L, i, n-1);for (int j = i+1; j v= right; j+)for (i = n-1; i = 0; i-) 对表排序if (Lj v Lk) k = j;L.Swap(0, i); siftDown (L, 0, i-1); ;if (k != i) Swap (Li, Lk); 交换 ;希尔排序的算法起泡排序的算法#include dataL

25、ist.htemplate vclass Ttemplate void BubbleSort (dataListvT & L, const int left,void Shellsort (dataListvT& L,const int right) const int left, const int right) int pass = left+1, exchange = 1;int i, j, gap = right-left+1;/增量的初始值while (pass v= right & exchange) ElementvT temp;exchange = 0;标志为0假定未交换do

26、for (int j = right; j = pass; j-)gap = gap/3+1;求下一增量值if (Lj-1 Lj) 逆序for (i = left+gap; i v= right; i+)Swap (Lj-1, Lj);交换if (Li v Li-gap) 逆序exchange = 1;标志置为1,有父换temp = Li; j = i-gap;do pass+;Lfj+gap = Lj; j = j-gap； while (j = left & temp v Lj); Lj+gap = temp; 将 vectori回送 while (gap 1);两路归并算法最大堆的向下调

27、整算法#include dataList.htemplate vclass Tvoid merge (dataListvT& L1, dataListvT& L2,const int left, const int mid, const int right) /L1.Vectorleft.mid与 L1.Vectormid+1right是两template vclass TsiftDown (dataListvT & L, const int start, const int m)私有函数：从结点start开始到m自上向下比较， 如果子女的值大于双亲的值，则相互交换，将一/# 人 启二 人 |

28、= 寺r/JJE、匚 曰.1 -4-Zr-/个集合局部调整为取人堆。个有序表，将这两个有序表归并成一个有序表 /L2.Vectorleftrightint k, i, j；i = left; j = mid+1; k = left;sl, s2是检测指针,t是存放指针while (i = mid & j = right)两两比较if (L1i = L1j)L2k+ = L1i+;elseL2k+ = L1j+;while (i = mid) L2k+ = L1i+;若第一个表未检测完，复制while (j temp = Li;暂存子树根结点while (j v= m) 逐层比较if (j = Lj) break; /temp 排序码大不调整 else 否则子女中的大者上移Li = Lj;i = j; j = 2*j+1;/i下降到子女位置Li = temp;/temp放到合适位置;