数据结构csdn总结

数据结构csdn总结第1篇数据结构csdn总结第1篇1.顺序查找

2.顺序查找的性能分析

3.顺序查找算法的特点

分块查找性能评价

易错点：1.注意mod的是m（表长），而不是求哈希值mod的那个东西了2.公式是基于hash（key）进行变化的，不是对原数进行变化

再哈希法：就是对出现的重复的哈希值再进行一次运算

链地址法：类似邻接表的形式，把所有映射值相同的元素都放到内部一个链表中

公共溢出区法：把出现冲突的数据直接放在另一个空间中存储起来

AVL树：自平衡二叉查找树，一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树节点的平衡因子：节点的左子树的高度减去它的右子树的高度

装填因子：α=填入表中记录个数/哈希表长度，α越大，产生冲突的可能性越大，平均查找长度也就越大

二叉排序树：若左子树不为空，则左子树上节点的值均小于根节点，若右子树不为空，则右子树上节点的值均大于根节点，左右子树均为二叉排序树(这是一个递归的定义)

数据结构csdn总结第2篇线性表的定义：具有相同数据类型的n(N>=0)个数据元素的有限序列。

线性表的特点：

1.除第一个元素外，每个元素有且仅有一个直接前驱，除最后一个元素外，每个元素有且仅有一个直接后继

2.表中元素个数有限

3.表中元素具有逻辑上的顺序关系

4.表中每个元素都是数据元素，每个元素都是单个元素

5.表中元素的数据类型都相同，即每个元素占有相同大小的存储空间

6.表中元素具有抽象性，即只关注与逻辑结构，不关注于元素表示的内容

7.线性表示一种逻辑结构，表示元素之间一对一的相邻关系；顺序表和链表是存储结构，表示物理结构

线性表的基本操作：

InitList(&L):初始化表

Length(L):求表长

LocateElem(L,e)：按值查找操作

GetElem(L,i):按位查找操作

ListInsert(&L,e):插入操作

ListDelete(&L,i,&e):删除操作

PrintList(L)：输出操作

Empty(L):判空操作

DestroyList(&L):销毁操作

顺序表的定义：用一组连续的存储单元，一次存储线性表中的数据元素，使得逻辑上相邻的数据元素在物理位置上也相邻。

顺序表的特点：随机访问，并且存储密度高，但是增删操作需要移动大量元素

结构体描述：

基本操作相关代码：

1.插入操作

2.删除操作

3.按值查找

单链表的定义：

通过一组任意的存储单元来存储线性表中的数据元素，每个链表节点除了放自身的信息外，还要存放一个指向后继的指针，其中data为数据域。next为指针域。

节点类型定义

1.单链表中的元素是离散的分布在存储空间中的。所以是非随机存储结构，想找到某个元素必须从头遍历。

2.通常用头指针标识一个单链表，此外，在单链表的第一个结点之前附加一个节点，称之为头节点。头结点中可以不加任何信息，也可以记录表长等。

引入头结点的优点：

开始节点放在头结点的指针域中，所以链表的第一个节点位置上的操作与其他位置上的操作一致，不需要特殊处理。

若链表为空，头指针是指向头结点的非空指针（头结点的指针域为空），所以空表与非空表的处理统一。

单链表解决了顺序表需要大量连续存储空间的缺点，但是单链表附加了指针域，也存在浪费存储空间的缺点。

基本操作相关代码

1.建立单链表

2.按序号查找节点值

3.按值查找

4.插入节点主要代码片段

5.删除节点操作

双向链表是单链表中有一个指向后继节点的指针next的基础上，增加了一个指向前驱节点的指针prior

循环链表

循环单链表：在单链表的基础上，表中最后一个节点的指针不是NULL,而是改为指向头结点，整个链表形成一个环。

因为没有指针域为NULL的节点，所以，循环单链表的判空条件不是头结点的指针是否为空，而是它是否等于头指针。

插入，删除操作算法与单链表一致，只是在尾部操作不同，

循环双向链表：在双向链表的基础上，表中最后一个节点的指针不是NULL，而是改为指向头结点，整个链表形成一个环。

判空条件为头结点的prior域和next域都等于头结点。

静态链表

静态链表是借助数组来描述线性表的链式存储结构，节点也有数据域data和指针域next，不过这里的指针域指的数组下标（游标）

结点类型定义

顺序表和单链表的比较

1.存取方式

顺序表可以顺序存取，也可以随机存取；链表只能顺序存取

2.逻辑结构和物理结构

顺序表，逻辑上相邻的元素，物理位置上也相邻；链表，逻辑上相邻，物理位置上不一定相邻

3.查找,插入和删除操作时间复杂度

按值查找：顺序表无序时，两者时间复杂度都为O(n)；当顺序表有序时，可以采用折半查找，时间复杂度O(log2n)

按位查找：顺序表随机访问，时间复杂度为链表平均时间复杂度为O(n)

数据结构csdn总结第3篇栈

栈的基本概念

栈的定义：只允许一端进行插入和删除操作的线性表

栈顶：栈允许进行插入和删除的那一端

栈底：固定的，不允许进行插入和删除的一端。

栈是一个先进后出的线性表

栈的基本操作

顺序栈：

顺序在的基本操作：

利用栈底位置不变的特性，让两个栈共享一个一维数组空间，将两个栈的栈底分别设置在共享空间的两端，两个栈顶向共享空间的中间延伸

链栈

采用链式存储的栈，通常采用单链表实现，并规定所有操作在单链表的表头进行，且链栈没有头结点，Lhead指向栈顶元素

队列的定义：只允许在表的一段进行插入，表的另一端进行删除

队列的基本操作

队列的顺序存储

分配一块连续的存储单元存放队列中的元素，并设置两个指针front和rear分别指示队头元素和队尾元素的位置。

结构体描述

循环队列

将顺序队列想象成一个环状空间，也就是逻辑上将存储队列元素的表看成一个环，即循环队列

队列的链式存储结构

队列的链式表示即链队列

双端队列

双端队列是指允许两端都可以进行入队和出队操作的

栈和队列的应用

矩阵

压缩矩阵：指多个值相同的元素只分配一个存储空间，对零元素不分配存储空间。其目的是为了节省存储空间特殊矩阵：指具有许多相同矩阵元素或零元素，并且这些相同矩阵元素或零元素的分布有一定规律性的矩阵。常见特殊矩阵有对称矩阵、上（下）三角矩阵、对角矩阵等特殊矩阵的压缩存储方法：找出特殊矩阵中值相同的矩阵元素的分布规律，把那些呈现规律性分布的值的多个矩阵元素压缩存储到一个存储空间中

稀疏矩阵

矩阵元素个数远大于非零元素个数的矩阵

1．掌握树型结构的定义。

2．掌握二叉树的定义、性质及各种存贮结构。

3．掌握遍历二叉树、线索二叉树及其他基本操作。

4．掌握树、森林与二叉树的相互转换；理解树的遍历；掌握哈夫曼树及其应用。

1．掌握图的定义和术语。

2．掌握图的存贮结构；理解图的基本操作。

3．掌握图的遍历算法；了解利用图的遍历解决图的应用问题。

4．理解图的有关应用：求最小生成树、求最短路径、拓扑排序及关键路径等算法的基本思想。

1．掌握静态查找表。

2．掌握二叉排序树和平衡二叉树。

3．理解B－树；了解B＋树。

4．掌握哈希表。

5．掌握各种查找方法的时间性能分析。

掌握直接插入排序、希尔排序、冒泡排序、快速排序、简单选择排序、堆排序、归并排序；理解基数排序。

插入排序是一种简单直观的排序方法，其基本思想是每次将一个待排序的记录按其关键字大小插入前面已排好序的子序列，直到全部记录插入完成，由插入排序的思想可以引申三个重要的排序算法：直接插入排序，折半插入排序和希尔排序。

根据上面的插入排序思想，不难得出一种最简单也最直观的直接插入排序算法，假设在排序过程中，待排序表L[1...n]在某次排序过程重的某一个时刻状态如下:

要将元素L(i)插入已有序的子序列L[1...i-1],需要执行以下操作（为避免混淆，下面用L[]表示一个表，而用L()表示一个元素）：

1.查找出L(i)在L(1...i-1)中的插入位置k。

2.将L[k...i-1]中的所有元素依次后移一个位置。

3.将L(i)复制到L(k)。

为了实现对L[1...n]的排序，可以将L(2)~L(n)依次插入前面已经排好的子序列，初始L[1]可以视为是一个已排好序的子序列。上述操作执行n-1次就能得到一个有序的表，插入排序在现实上通常采用就地排序（空间复杂度O(1)）因而在从后向前的比较过程中，需要反复把已排序元素逐步向后挪位，为新元素提供插入空间。

下面是直接插入排序的代码：

直接插入排序算法的性能分析如下：

空间效率：仅使用了常数个辅助单元，因而空间复杂度为O(1)。

时间效率：在排序过程中，向有序子表中逐个地插入元素的操作进行n-1趟，每趟操作都分为比较关键字和移动元素，而比较次数和移动次数取决于待排序表的初始状态。

在最好情况下，表中元素已经有序，此时每插入一个元素，都只需比较一次而不用移动元素，因而时间复杂度为O(n)。

在最坏情况下，表中元素顺序刚好与顺序结果中的元素顺序相反（逆序），总的比较次数达到最大，为(i+1)。

平均情况下，考虑待排序表中元素是随机的，此时可以取上述最好与最坏情况的平均值作为平均情况下的时间复杂度，总的比较次数与总的移动次数约为。

因此，直接插入排序算法的时间复杂度为O().

稳定性：由于每次插入元素时总是从后向前先比较再移动，所以不会出现相同元素对位置发生变化的情况，即直接插入排序是一个稳定的排序算法。

适用性：直接插入排序算法适用于顺存储和链式存储的线性表。为链式存储时，可以从前往后查找指定元素的位置。

从直接插入排序算法中，不难看出每趟插入的过程中都进行了两项工作：

1.从嵌满的有序子表中查找出待插入元素应该_入的位置；

2.给插入位置腾出空间，将待插入元素复制到表中插入位置。注意到在该算法中，总是边比较边移动元素。下面将比较和移动操作分离，即先折半查找出元素的待插入位置，然后统一地移动待插入位置之后的所有元素。当排序表为顺序表时，可以对直接插入排序算法做如下改进：由于是顺序存储的线性表，所以查找有序子表时可以用折半查找来实现。确定待插入位置后，就可统一地向后移动元素。算法代码如下：

从上述算法中，不难看出折半插入排序不仅减少了比较元素的次数，约为O(nlog2n),该比较次数与待排序表的初始状态无关，仅取决于表中的元素个数n;而元素的移动次数并未改变，它依赖于待排序表的初始状态，因此，折半插入排序的时间复杂度仍为O(),但对于数据量不很大的排序表，折半插入排序往往能表现出很好的性能。折半插入排序是一种稳定的排序方法。

从前面的分析可知，直接插入排序算法的时间复杂度为O(),但若待排序列为“正序”时，其时间复杂度可提高至O(n)，由此可见它更适用于基本有序的排序表和数据量不大的排序表。希尔排序正是基于这两点分析对直接插入排序进行改进而得来的，又称缩小增量排序。

希尔排序的基本思想是：先将待排序表分割成若干形如若L[i,i+d,i+2d,...,i+kd]的“特殊”子表，即把相隔某个“增量”的记录组成一个子表，对各个子表分别进行直接插入排序，当整个表中的元素已呈“基本有序”时，再对全体记录进行一次直接插入排序。

希尔排序的过程如下:先取一个小于n的步长d1,把表中的全部记录分成d1组，所有距离为d1的倍数的记录放在同一组，在各组内进行直接插入排序；然后取第二个步长d2=1，即所有记录已放在同一组中，在进行直接插入排序，由于此时已经具有加号的局部有序性，故可以很快得到最终结果，到目前为止，尚未求得一个最好的增量序列。示例：第一趟取增量=5，将该序列分成5个子序列，即图中第2行至第6行，分别对各子序列进行直接插入排序，结果如第7行所示；第二趟取增量=3，分别对3个子序列进行直接插入排序，结果如第11行所示；最后对整个序列进行一趟直接插入排序，整个排序过程如图所示：

希尔排序算法的代码如下：

希尔排序算法的性能分析如下：

空间效率：仅使用了常数个辅助单元，因而空间复杂度为O(1).

时间效率：由于希尔排序的时间复杂度依赖于增量序列的函数，这涉及数学上尚未解决的难题，所以其时间复杂度分析比较困难。当n在某个特定范围时，希尔排序的时间复杂度约为O()。在最坏情况下希尔排序的时间复杂度为O()。

稳定性:当相同关键字的记录被划分到不同的子表时，可能会改变它们之间的相对次序，因此希尔排序是一种不稳定的排序方法。

适用性：希尔排序算法仅适用于线性表为顺序存储的情况。

所谓交换，是指根据序列中两个元素关键字的比较结果来对换这两个记录在序列中的位置。

冒泡排序的基本思想是：从后往前（或从前往后）两两比较相邻元素的值，若为逆序（即A[i-1]>A[i]）,则交换它们，直到序列比较完。我们称它为第一趟冒泡，结果是将最小的元素交换到待排序的第一个位置（或将最大的元素交换到待排序列的最后一个位置），关键字最小的元素如气泡一般逐渐往上“漂浮”直至“水面”（或关键字最大的元素如石头一般下沉至水底）。下一趟冒泡时，前一趟确定的最小元素不再参与比较，每趟冒泡的结果是把序列中的最小元素（或最大元素）放到了序列的最终位置......这样最多做n-1趟冒泡就能把所有元素排好序。

如图所示冒泡排序的过程，第一趟冒泡时：27<,不交换；13<27,不交换；76>13,交换；97>13,交换；65>13,交换；38>13，交换；49>13,交换。通过第一趟冒泡后，最小元素已交换到第一个位置，也是它的最终位置。第二趟冒泡时对剩余子序列采用同样方法进行排序，依次类推，到第5趟结束后没有发生交换，说明表已有序，冒泡排序结束。

冒泡排序算法的代码如下：

冒泡排序的性能分析如下：

空间效率：仅使用了常数个辅助单元，因而空间复杂度为O(1);

时间效率：当初始序列有序时，显然第一趟冒泡后flag依然为false(本趟冒泡没有元素交换)，从而直接跳出循环，比较次数为n-1，移动次数为0，从而最好情况下的时间复杂度为O(n);当初始序列为逆序时，需要进行n-1趟排序，第i趟排序要进行n-i次关键字的比较，而且每次比较后都必须移动元素3次交换元素位置。这种情况下，

比较次数=,移动次数=

从而，最坏情况下的时间复杂度为O(),其平均时间复杂度也为O()。

稳定性:由于i>j且A[i]=A[j]时，不会发生交换，因此冒泡排序是一种稳定的排序方法。

注意：冒泡排序中产生的有序子序列一定是全局有序的（不同于直接插入排序），也就是说，有序子序列中所有元素的关键字一定小于或大于无序子序列中所有元素的关键字，这样每趟排序都会将一个元素放置到其最终的位置上。

快速排序的基本思想是基于分治的：：在待排序表L[1...n]中任取一个元素pivot作为枢轴（或基准，通常取首元素），通过一趟排序将待排序表划分为独立的两部分L[1..k-1]和L[k+1...n],使得L[1...K-1]中的所有元素小于pivot

,L[k+1...n]中的所有元素大于等于pivot,则pivot放在了其最终L(K)上，这个过程称为一趟快速排序（或一次划分）。然后分别递归地随两个子表重复上述过程，直至每部分内只有一个元素或空为止，即所有元素放在了其最终位置上。

一趟快速排序的过程是一个交替搜索和交换的过程，下面通过实例来介绍，附设两个指针i和j,初值分别为low和high,取第一个元素49为枢轴复制到变量pivot。

指针j从high往前搜索找到第一个小于枢轴的元素27，将27交换到i所指位置。

对算法的最好理解方式是搜总模拟一遍这些算法。

假设划分算法已知，记为Partition(),返回的是上述的k，注意到L(K)已经在最终的位置，因此可以先对表进行划分，而后对两个表调用同样的排序操作。因此可以递归地条用快速排序算法进行排序，具体的程序结构如下：

从上面的代码不难看出快速排序算法的关键在于划分操作，同时快速排序算法的性能也主要取决于划分操作的好坏。从快速排序算法提出至今，已有许多不同的划分操作版本，但考研所考察的快速排序的划分操作基本以严蔚敏的教材《数据结构》为主，假设每次总以当前表中第一个元素作为枢轴来对表进行划分，则将表中比枢轴大的元素向右移动，将比枢轴小的元素向左移动，使得一趟Partition()操作后，表中的元素被枢轴值一分为二。代码如下：

快速排序算法的性能分析如下：

空间效率：由于快速排序是递归的，需要借助一个递归工作栈来保存每层递归调用的必要信息，其容量应与递归调用的最大深度一致。最好情况下为O();最坏情况下，因为要进行n-1次递归调用，所以栈的深度为O(n);平均情况下，栈的深度为O(log)。

时间效率：快速排序的运行时间于划分是否对称有关，快速排序的最坏情况发生在两个区域分别包含n-1个元素和0个元素时，这种最大限度的不对称性若发生在每层递归上，即对应于初始排序表基本有序或记恨逆序时，就得到最坏情况下的时间复杂度为O()。

有很多方法可以提高算法的效率:一种方法是尽量选取一个可以将数据中分的枢轴元素，若从序列的头尾及中间选取三个元素，再取这三个元素的中间值作为最终的枢轴元素；或者随机地从当前表中选取枢轴元素，这样做可是得最坏情况在实际排序中几乎不会发生。

在最理想的状态下，即Partition()可能做到最平衡的划分，得到的两个子问题的大小都不可能大于n/2,在这种情况下的，快速排序的运行速度将大大提升，此时，时间复杂度为O(nlog)。好在快速排序平均情况下运行时间与其最佳情况下的运行时间很接近，而不是接近最坏情况下的运行时间。快速排序是所有的内部排序算法中平均性能最优的排序算法。

稳定性：在划分算法中，若右端区间有两个关键字相同，且均下雨基准的记录，则在交换到左端区间后，它们的相对位置就会发生变化，即快速排序是一种不稳地的排序方法。例如表L={3,2,2}经过一趟排序后L={2,2,3},最终排序序列也是L={2,2,3},显然，2与2的相对次序发生了变化。

注意：在快速排序算法中，并不产生有序子序列，但没每趟排序后会将枢轴（基准）元素方法其最终的位置上。

选择排序的基本思想是：每一趟（如第i趟）在后面n-i+1(i=1,2,...,n-1)个待排序元素中选取关键字最小的元素，作为有序子序列的第i个元素，直到第n-1趟做完，待排序元素只剩下1个，就不用再选了。

根据上面选择排序的思想，可以很直观地得出简单选择排序算法的思想：假设排序表为L[1...n],第i趟排序即从L[i...n]中选择关键字最小的元素与L(i)交换，每一趟排序可以确定一个元素的最终位置，这样经过n-1趟排序就可以使得真个排序表有序。

简单选择排序算法的代码如下：

简单选择排序算法的性能分析如下：

空间效率：仅使用常数个辅助单元，故空间效率为O(1);

时间效率:从上述伪代码中不难看出，在简单选择排序的过程中，元素移动的操作次数很少，不会超过3（n-1）次，最好的情况下是移动0次，此时对应的表已经有序；但元素比较的次数与序列的初始状态无关，始终是n(n-1)/2次，因此时间复杂度始终是O()。

稳定性：在第i趟找到最小元素后，和第i个元素交换，可能会导致第i个元素与其含有相同关键字元素的相对位置发生改变，例如，表L={2,2,1},经过一趟排序后L={1,2,2},最终排序序列也是L={1,2,2},显示，2与2的相对次序已发生变化。因此，简单选择排序是一种不稳定的排序方法。

堆的定义如下，n个关键字序列L[1...n]成为堆，当且仅当该序列满足：

1.L(i)>=L(2i)且L(i)>(2i+1)或

2.L(i)<=L(2i)且L(i)<=L(2i+1)(1<=i<=)

可以将该一维数组视为一颗完全二叉树，满足条件1的成为大根堆（大顶堆），大根堆的最大元素存放在根节点，且其任一非根节点的值小于等于其双亲结点值。满足条件2的推成为小根堆（小顶堆），小根堆的定义刚好相反，根节点是最小元素。该图所示就是一个大根堆：

堆排序的思路很简单：首先将存放在L[1...n]中的n个元素建成初始堆，由于堆本身的特点（以大根堆为例），堆顶元素就是最大值。输出堆顶元素后，通常将堆低元素送入堆顶。此时根节点已不满足大顶堆的性质，堆被破坏，将堆顶元素向下调整使其继续保持大顶堆的性质，再输出堆顶元素。如此重复，直到堆中仅剩一个元素为止。可见堆排序需要解决两个问题：

1，如何将无序序列构造成初始堆？

2.输出堆顶元素后，如何将剩余元素调整成新的堆？

堆排序的关键是构造初始堆。n个节点的完全二叉树，最后一个节点是第个节点的孩子。对第个节点为根的子树筛选（对于大根堆，若根节点的关键字小于左右孩子中关键字较大者，则交换），使该子树成为堆。之后向前依次对各个节点（-1~1）为根的子树进行筛选，看该节点值是否大于其左右子节点的值，若不大于，则将左右子结点中的较大值与之交换，交换后可能会破坏下一级的堆，于是继续采用上述方法构造下一级的堆，直到以该结点为根的子树构成堆为止。反复利用上述调整对的方法建堆，直到根结点。

如图所示，初始时调整L(4)子树，09<32,交换，交换，交换后满足堆的定义；向前继续调整L(3)子树，78<左右孩子的较大者87，交换，交换后满足堆的定义；向前调整L(2)子树，17<左右孩子的较大者45，交换后满足堆的定义；向前调整至根结点L(1),53<左右孩子的较大者87，交换，交换后破坏了L(3)子树的推，采用上述方法对L(3)进行调整，53<左右孩子的较大者78，交换，至此该完全二叉树满足堆的定义。

输出堆顶元素后，将堆的最后一个元素与堆顶元素交换，此时堆的性质被破坏，需要向下进行筛选。将09和左右孩子的较大者78交换，交换后破坏了L(3)子树的堆，继续堆L(3)子树向下筛选，将09和左右孩子大的较大者65交换，交换后得到了新堆，调整过程如图所示。

下面是建立大根堆的算法：

调整的时间与树高有关，为O(h)。在建含n个元素的堆时，关键字的比较总次数不超过4n,时间复杂度为O(n),这说明在线性时间内将一个无序数组建成一个堆。

下面是堆排序算法：

同时，堆也支持插入操作。对堆进行插入操作时，先将新结点放在堆的末端，再对这个新结点向上执行调整操作。大根堆的插入操作如图所示：

堆排序适合关键字较多的情况，例如，在1亿个数中选出前100个最大值？首先使用一个大小为100的数组，读入前100个数，建立小顶堆，而后依次读入余下的数，若小于堆顶则舍弃，否则用该数取代堆顶并重新调整堆，待数据读取完毕，堆中100个数即为所求。

堆排序算法的性能分析如下：

空间效率：仅使用了常数个辅助单元，所以空间复杂度为O(1);

时间效率：建堆时间为O(n),之后有n-1次向下调整操作，每次调整的时间复杂度为O(h),故在最好，最坏和平均情况下，堆排序的时间复杂度为O(n)。

稳定性：进行筛选时，有可能把后面相同关键字的元素调整到前面，所以堆排序算法是一种不稳定的排序算法。例如，表L={1,2,2},构造初始堆时可能将2交换到堆顶，此时L={2,1,2},最总排序序列为L={1,2,2},显然，2与2的相对次序已发生变化。

数据结构csdn总结第4篇在计算机中用一组任意的存储单元存储线性表的数据元素(这组存储单元可以是连续的,也可以是不连续的)。它不要求逻辑上相邻的元素在物理位置上也相邻.因此它没有顺序存储结构所具有的弱点,但也同时失去了顺序表可随机存取的优点。

特点：

1、比顺序存储结构的存储密度小(每个节点都由数据域和指针域组成，所以相同空间内假设全存满的话顺序比链式存储更多)。

2、逻辑上相邻的节点物理上不必相邻。

3、插入、删除灵活(不必移动节点，只要改变节点中的指针)。

4、查找结点时链式存储要比顺序存储慢。

5、每个结点是由数据域和指针域组成。

数据结构csdn总结第5篇B树的定义如下：1、每个结点最多有m-1个关键字。2、根结点最少可以只有1个关键字。3、非根结点至少有(m/2)-1个关键字。()为向上取整。4、每个结点中的关键字都按照从小到大的顺序排列，每个关键字的左子树中的所有关键字都小于它，而右子树中的所有关键字都大于它。5、所有叶子结点都位于同一层，或者说根结点到每个叶子结点的长度都相同。

上图是一颗阶数为3的B树。在实际应用中的B树的阶数m都非常大（通常大于100），所以即使存储大量的数据，B树的高度仍然比较小。每个结点中存储了关键字（key）和关键字对应的数据（data），以及孩子结点的指针。我们将一个key和其对应的data称为一个记录。但为了方便描述，除非特别说明，后续文中就用key来代替（key,value）键值对这个整体。在数据库中我们将B树（和B+树）作为索引结构，可以加快查询速速，此时B树中的key就表示键，而data表示了这个键对应的条目在硬盘上的逻辑地址。

数据结构csdn总结第6篇下图中这棵树，就是一颗典型的红黑树：红黑树通过将结点进行红黑着色，使得原本高度平衡的树结构被稍微打乱，平衡程度降低。红黑树不追求完全平衡，只要求达到部分平衡。这是一种折中的方案，大大提高了结点删除和插入的效率。C++中的STL就常用到红黑树作为底层的数据结构。使用场景：HashMap底层结构是数组+链表，中底层结构加入了红黑树，数组+链表+红黑树。

数据结构csdn总结第7篇平衡二叉树的产生是为了解决二叉排序树在插入时发生线性排列的现象。由于二叉排序树本身为有序，当插入一个有序程度十分高的序列时，生成的二叉排序树会持续在某个方向的字数上插入数据，导致最终的二叉排序树会退化为链表，从而使得二叉树的查询和插入效率恶化平衡二叉树的出现能够解决上述问题，但是在构造平衡二叉树时，却需要采用不同的调整方式，使得二叉树在插入数据后保持平衡。主要的四种调整方式有LL（左旋）、RR（右旋）、LR（先左旋再右旋）、RL（先右旋再左旋）。这里先给大家介绍下简单的单旋转操作，左旋和右旋。LR和RL本质上只是LL和RR的组合。在插入一个结点后应该沿搜索路径将路径上的结点平衡因子进行修改，当平衡因子大于1时，就需要进行平衡化处理。从发生不平衡的结点起，沿刚才回溯的路径取直接下两层的结点，如果这三个结点在一条直线上，则采用单旋转进行平衡化，如果这三个结点位于一条折线上，则采用双旋转进行平衡化。

数据结构csdn总结第8篇

在网站的搜索框中输入搜索文字时，会罗列出以搜索词开头的相关搜索信息。这里就运用到了前缀树，在后端进行快速的检索。如下：

还有我们经常使用的汉语拼音输入法，它的联想输入功能也用到了前缀树。

数据结构csdn总结第9篇内容提要：

◆线性表的逻辑结构定义，对线性表定义的操作。

线性表的定义：用数据元素的有限序列表示

◆线性表的存储结构：顺序存储结构和链式存储结构。

顺序存储定义：把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构。

链式存储结构:其结点在存储器中的位置是随意的，即逻辑上相邻的数据元素在物理上不一

定相邻。通过指针来实现！

1)修改——通过数组的下标便可访问某个特定元素并修改之。

核心语句:V[i]=x;

顺序表修改操作的时间效率是O(1)

2)插入——在线性表的第i个位置前插入一个元素

实现步骤：

①将第n至第i位的元素向后移动一个位置；

②将要插入的元素写到第i个位置；

③表长加1。

注意：事先应判断:插入位置i是否合法?表是否已满?

应当符合条件：1≤i≤n+1或i=[1,n+1]

核心语句：

for(j=n;j>=i;j--)

a[j+1]=a[j];

a[i]=x;

n++;

插入时的平均移动次数为：n(n+1)/2÷（n+1）＝n/2≈O(n)

3)删除——删除线性表的第i个位置上的元素

实现步骤：

①将第i+1至第n位的元素向前移动一个位置；

②表长减1。

注意：事先需要判断，删除位置i是否合法?

应当符合条件：1≤i≤n或i=[1,n]

核心语句：

for(j=i+1;j<=n;j++)

a[j-1]=a[j];

n--;

顺序表删除一元素的时间效率为:T（n)=(n-1)/2≈O(n)

顺序表插入、删除算法的平均空间复杂度为O(1)

单链表：

（1）用单链表结构来存放26个英文字母组成的线性表（a，b，c，…，z）,请写出C语言程序。

（2）单链表的修改(或读取）

思路：要修改第i个数据元素，必须从头指针起一直找到该结点的指针p，

然后才能：p>data=new_value

读取第i个数据元素的核心语句是：

（3）.单链表的插入

链表插入的核心语句：

Step1：s->next=p->next;

Step2：p->next=s；

（4）.单链表的删除

删除动作的核心语句（要借助辅助指针变量q）：

q=p->next;//首先保存b的指针，靠它才能找到c；

p->next=q->next;//将a、c两结点相连，淘汰b结点；

free(q)；//彻底释放b结点空间

(5).双向链表的插入操作：

设p已指向第i元素，请在第i元素前插入元素x：

①ai-1的后继从ai(指针是p)变为x（指针是s):

s->next=p;p->prior->next=s;

②ai的前驱从ai-1(指针是p->prior)变为x(指针是s);

s->prior=p->prior;p->prior=s;

(6).双向链表的删除操作：

设p指向第i个元素，删除第i个元素

后继方向：ai-1的后继由ai(指针p)变为ai+1(指针p->next);

p->prior->next=p->next;

前驱方向：ai+1的前驱由ai(指针p)变为ai-1(指针p->prior);

p->next->prior=p->prior;

◆数组的逻辑结构定义及存储

数组：由一组名字相同、下标不同的变量构成

N维数组的特点：n个下标，每个元素受到n个关系约束

一个n维数组可以看成是由若干个n－1维数组组成的线性表。

存储：事先约定按某种次序将数组元素排成一列序列，然后将这个线性序列存入存储器中。

在二维数组中，我们既可以规定按行存储，也可以规定按列存储。

设一般的二维数组是A[c1..d1,c2..d2]，

则行优先存储时的地址公式为：

二维数组列优先存储的通式为：

◆稀疏矩阵（含特殊矩阵）的存储及运算。

稀疏矩阵：矩阵中非零元素的个数较少（一般小于5%）

学习重点：

◆线性表的逻辑结构，指线性表的数据元素间存在着线性关系。在顺序存储结构中，元素

存储的先后位置反映出这种线性关系，而在链式存储结构中，是靠指针来反映这种关系的。

◆顺序存储结构用一维数组表示，给定下标，可以存取相应元素，属于随机存取的存储结构。

◆链表操作中应注意不要使链意外“断开”。因此，若在某结点前插入一个元素，或删除

某元素，必须知道该元素的前驱结点的指针。

◆掌握通过画出结点图来进行链表（单链表、循环链表等）的生成、插入、删除、遍历等操作。

◆数组（主要是二维）在以行序/列序为主的存储中的地址计算方法。

◆稀疏矩阵的三元组表存储结构。

◆稀疏矩阵的十字链表存储方法。

补充重点：

1.每个存储结点都包含两部分：数据域和指针域(链域)

2.在单链表中，除了首元结点外，任一结点的存储位置由其直接前驱结点的链域的值指示。

3.在链表中设置头结点有什么好处？

头结点即在链表的首元结点之前附设的一个结点，该结点的数据域可以为空，也可存放

表长度等附加信息，其作用是为了对链表进行操作时，可以对空表、非空表的情况以及对首

元结点进行统一处理，编程更方便。

4.如何表示空表？

（1）无头结点时，当头指针的值为空时表示空表；

（2）有头结点时，当头结点的指针域为空时表示空表。

5.链表的数据元素有两个域，不再是简单数据类型，编程时该如何表示？

因每个结点至少有两个分量，且数据类型通常不一致，所以要采用结构数据类型。

(x)——计算变量x的长度（字节数）；

malloc(m)—开辟m字节长度的地址空间，并返回这段空间的首地址；

free(p)——释放指针p所指变量的存储空间，即彻底删除一个变量。

7.链表的运算效率分析：

（1）查找

因线性链表只能顺序存取，即在查找时要从头指针找起，查找的时间复杂度为O(n)。

数据结构csdn总结第10篇循环链表又分为单循环链表和双循环链表，也就是将单向链表或双向链表的首尾节点进行连接，这样就实现了单循环链表或双循环链表了，如下图所示：使用场景：链表作为一种基本的物理结构，常被用来构建许多其它的逻辑结构，如堆栈、队列都可以基于链表实现。

散列表，也叫哈希表，是根据关键码和值(key和value)直接进行访问的数据结构，通过key和value来映射到集合中的一个位置，这样就可以很快找到集合中的对应元素。它利用数组支持按照下标访问的特性，所以散列表其实是数组的一种扩展，由数组演化而来。查找效率是O(1)

给定表M，存在函数f(key)，对任意给定的关键字值key，代入函数后若能得到包含该关键字的记录在表中的地址，则称表M为哈希(Hash）表，函数f(key)为哈希(Hash)函数。

散列表首先需要根据key来计算数据存储的位置，也就是数组索引的下标；HashValue=hash(key)

在上图散列表中，最下面连续的是个数组，数组的每个成员包括一个指针，指向一个链表的头，当然这个链表可能为空，也可能元素很多。我们根据元素的一些特征把元素分配到不同的链表中去，也是根据这些特征，找到正确的链表，再从链表中找出这个元素。再上图散列表张，竖着的是链表，可以看出由一根指针连接着。每次存放元素前都会通过hash函数计算然后存放在计算后的位置，当出现hash碰撞时会直接挂在链表的下面。上图采用的求模取余方法存放元素。

场景：MySQL底层的索引结构，使用较少。缺点：适用等值查询不支持范围查找、无法orderby排序。

树作为一种树状的数据结构，其数据节点之间的关系也如大树一样，将有限个节点根据不同层次关系进行排列，从而形成数据与数据之间的父子关系。常见的数的表示形式更接近“倒挂的树”，因为它将根朝上，叶朝下。树的数据存储在结点中，每个结点有零个或者多个子结点。没有父结点的结点在最顶端，成为根节点；没有非根结点有且只有一个父节点；每个非根节点又可以分为多个不相交的子树。当链表的元素增加到很多时其查询效率明显下降，所以树这种结构可以很好的弥补这点。树可以理解成链表的plus版本，其本身其实就是链表的一个变种。可以很好的弥补链表的查询料率的同时也不会使其增删效率太差。树的种类虽然很多，但都是由二叉树（二分查找思想）衍生而来，做了某些优化加上了一些特性而产生的有其特点的树。

数据结构csdn总结第11篇遍历获取元素的时候可以按照_左中右_的顺序进行遍历；

注意：二叉查找树存在的问题：会出现_瘸子_的现象，影响查询效率。

（基于查找二叉树，但是让树不要太高，尽量让树的元素均衡分布。这样综合性能就高了）

为了避免出现_瘸子_的现象，减少树的高度，提高我们的搜素效率，又存在一种树的结构：“平衡二叉树”

规则：它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树

如下图所示：如上图所示，左图是一棵平衡二叉树，根节点10，左右两子树的高度差是1，而右图，虽然根节点左右两子树高度差是0，但是右子树15的左右子树高度差为2，不符合定义，

所以右图不是一棵平衡二叉树。

在构建一棵平衡二叉树的过程中，当有新的节点要插入时，检查是否因插入后而破坏了树的平衡，如果是，则需要做旋转去改变树的结构。

左旋：

右旋：

红黑树是一种自平衡的二叉查找树，是计算机科学中用到的一种数据结构，它是在1972年由RudolfBayer发明的，当时被称之为平衡二叉B树，后来，在1978年被和RobertSedgewick修改为如今的_红黑树_。它是一种特殊的二叉查找树，红黑树的每一个节点上都有存储位表示节点的颜色，可以是红或者黑；

红黑树的特性：

数据结构csdn总结第12篇1.链表头节点的作用：如果没有头节点，那么在头部插入一个节点和在中间插入一个节点的操作是不一样的，如果加上头节点就可以去除这样的判断，代码更加简化了。

2.线性表最开始的节点没有前驱，最后一个节点没有后继。

3.循环链表的优点：从任一节点出发都可以访问到链表中的每一个元素。

4.循环链表不同于循环队列，循环队列如果头指针和尾指针在最后重叠到了一起，无法判断队列已满，所以决定牺牲一个位置，让尾指针实际上为尾后指针。

5.顺序表和链表的比较：

1.栈的定义：限定仅在表尾进行插入和删除操作的线性表。允许插入和删除的一端称为栈顶，另一端称为栈底。空栈：不含任何数据元素的栈。栈的操作特性：后进先出。

2.队列的定义：只允许在一端进行插入操作，而在另一端进行删除操作的线性表。允许插入的一端称为队尾，允许删除的一端称为队头。空队列：不含任何数据元素的队列。

3.链栈的表示：运算是受限的单链表，只能在链表头部进行操作，故没有必要附加头结点。栈顶指针就是链表的头指针。

4.涉及到表达式的题目，关键就在于考虑运算符的优先级，当前符号会把符号栈中优先级更高的元素全部执行完，然后自己进栈，这是不难理解的。

5.队列删除元素是在队首，添加元素是在队尾。

6.尾递归和单向递归可以使用循环来消除递归。尾递归就是递归语句在最后，当前环境的情况不需要保留。即使保留了也没什么用，所以不需要单独开辟堆栈来进行下一次递归，下一次的递归直接在本次递归的空间进行即可。注意这里说的是能够用循环消除递归的条件。不是说消除递归的条件，事实上任何递归都可以转化为非递归。

7.假溢出：头指针没有指向最开始的位置，尾指针指向最后位置，呈现出队满的假象，所以引入循环队列。

8.循环队列应该是用顺序存储机构，所以头尾指针的变化都是通过数的运算得来的，没有什么next指针。

9.循环队列中:

1.串的定义：即字符串，由零个或多个字符组成的有限序列，是数据元素为单个字符的特殊线性表。串长:串中字符个数（n≥0）。n=0时称为空串,。空白串:由一个或多个空格符组成的串。

2.串的术语：子串:串中任意个连续的字符组成的子序列。主串:包含子串的串。字符位置:字符在串中的序号。子串的位置:子串的第一个字符在主串中的序号。串相等:串长度相等，且对应位置上字符相等。

3.广义表常用术语：长度:广义表中元素的个数n。n=0时称为空表。深度:定义为括号嵌套的最深层次。(a,(b，c，d))。表头:对于任意一个非空广义表LS=(a1,a2,…,an)