全都是自己错题的知识点，记录一下吧！
1.C++ STL 的实现：
(1)vector 底层数据结构为数组，支持快速随机访问，不在乎插入和删除的效率
(2)list 底层数据结构为双向链表，支持快速增删，而关心随机存取
(3)deque 是一个双端队列，是一种具有队列和栈的性质的数据结构。双端队列中的元素可以从两端弹出，其限定插入和删除操作在表的两端进行。相比list增加[]运算符重载。底层数据结构为一个中央控制器和多个缓冲区，支持首尾（中间不能）快速增删，也支持随机访问
(4)stack 底层一般用list和deque实现，封闭头部即可，不用vector的原因应该是容量大小有限制，扩容耗时
(5)queue 底层一般用list和deque实现，封闭头部即可，不用vector的原因应该是容量大小有限制，扩容耗时
(6)priority_queue 的底层数据结构一般为vector为底层容器，堆heap为处理规则来管理底层容器实现，优先队列具有队列的所有特性，包括队列的基本操作，只是在这基础上添加了内部的一个排序，在优先队列中，元素被赋予优先级。当访问元素时，具有最高优先级的元素最先删除。它本质是一个堆实现的。
(7)在C++中，标准库提供了三种顺序容器适配器：queue(FIFO队列)、priority_queue(优先级队列)、stack(栈) 。
(8)set 底层数据结构为红黑树，有序，不重复
红黑树是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构
红黑树和AVL树类似，都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡，从而获得较高的查找性能。它虽然是复杂的，但它的最坏情况运行时间也是非常良好的，并且在实践中是高效的： 它可以在O(log n)时间内做查找，插入和删除，这里的n是树中元素的数目。
红黑树是每个节点都带有颜色属性的二叉查找树，颜色或红色或黑色。在二叉查找树强制一般要求以外，对于任何有效的红黑树我们增加了如下的额外要求:
性质1. 节点是红色或黑色。
性质2. 根节点是黑色。
性质3 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
性质4. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
红黑树
(9)multiset 底层数据结构为红黑树，有序，可重复
(10)map 底层数据结构为红黑树，有序，不重复
(11)multimap 底层数据结构为红黑树，有序，可重复
(12)hash_set 底层数据结构为hash表，无序，不重复
(13)hash_multiset 底层数据结构为hash表，无序，可重复
(14)hash_map 底层数据结构为hash表，无序，不重复
(15)hash_multimap 底层数据结构为hash表，无序，可重复
2.三维数组
三维数组可以看成是一本书！int a[3][4][2]; 就是有3页每页4行2列
3.二维数组按行存储和按列存储
(1)为什么要引入以列序为主序和以行序为主序的存储方式？
因为一般情况下存储单元是单一的存储结构，而数组可能是多维的结构，则用一维数组存储数组的数据元素就存在着次序约定的问题，所以就有了以列序为主序和以行序为主序的存储方式。
(2)以列序为主序的存储方式的存储地址计算公式：
LOC(i,j) = LOC(0,0) + (m行数×(j-1)+(i-1))×L
LOC(i,j)是a(i,j)的存储位置； LOC(0,0)是a(0,0)的存储位置（即二维数组的起始存储位置，为称为基地址或基址）；m是数组的总行数，L是单个数据元素占据的存储单元。
(3)以行序为主序的存储方式的存储地址计算公式：
LOC(i,j) = LOC(0,0) + (n列数×(i-1)+(j-1))×L，下标从1开始
注意：下标从0开始a(i,j)处于第i+1行j+1列，其地址为LOC(0,0) +(i×n+j)×L
LOC(i,j)是a(i,j)的存储位置； LOC(0,0)是a(0,0)的存储位置（即二维数组的起始存储位置，为称为基地址或基址）；n是数组的总列数，L是单个数据元素占据的存储单元。
4.数据结构中常用的操作的效率表
通用数据结构
专用数据结构
5.数组指针和指针数组
(1)定义不同
数组指针是指向数组首元素的地址的指针，其本质为指针（这个指针存放的是数组首地址的地址，相当于2级指针，这个指针不可移动）；
指针数组是数组元素为指针的数组，其本质为数组。
(2)所占存储空间的区别
数组指针只是一个指针变量，是C语言里专门用来指向二维数组的，它占有内存中一个指针的存储空间。如int (*p)[10]，p即为指向数组的指针，又称数组指针。
指针数组是多个指针变量，以数组形式存在内存当中，占有多个指针的存储空间，如char *p[5] 系统至少会分配5个连续的空间用来存储5个元素，表示p是一个5个元素的数组，每个元素是一个指向字符型数据的一个指针。
(3)应用上的区别
指针数组一般用于处理二维数组。指向一维数组的指针变量用于处理二维数组也是非常方便的。
数组指针和指针数组在处理同一个二维数组时，数组指针的元素个数和指针数组的数组长度不相同，数组指针的元素个数和二维数组的列长度相同。 而指针数组的数组长度和二维数组的行长度相同。
在处理字符串的问题上，使用指针数组处理就比使用数组指针方便多了。因为多个字符串比用二维字符数组处理字符串更加方便，更加的节省内存空间。
数组指针和指针数组对比图
例如：
若有定义:
pc是一个数组指针（指向数组的指针），指向列数为5的二维数组，pc = c，表示pc指向二维数组的第一行，pc+1偏移一行，一行5个元素。*pc得到二维数组c的第一行数组的首地址，+2偏移到c[0][2]的地址，解引用就得到数据2。c[4][5]可以理解为4个长度为5的一位数组，这四个一维数组的地址要用数组指针存放。
6.广义表
如果广义表LS=（a1,a2...an）非空，则a1是LS的表头，其余元素组成的表（a2,a3,..an）是称为LS的表尾。
根据定义，非空广义表的表头是一个元素，它可以是原子也可以是一个子表，而表尾则必定是子表。例如:LS=(a,b),表头为a,表尾是（b）而不是b.另外：LS=（a)的表头为a，表尾为空表()。
广义表即我们通常所说的列表（lists)。它放松了对表元素的原子性限制，允许他们有自身结构。
广义表的特性：
广义表的元素可以是子表，而子表的元素还可以是子表。
广义表可为其他广义表所共享。
广义表可以是一个递归的表，即广义表也可以是其本身的一个子表
二维以上的数组其实是一种特殊的广义表
广义表的长度：最大括号中的逗号数+1，如 ( f , () , (e), (a,(b,c,d)) ) 长度是4
广义表的深度：每个元素的括号匹配数加1，如 ( f , () , (e), (a,(b,c,d)) )
f没有括号匹配，深度为0+1=1
()一个括号匹配，深度为1+1=2 (e)一个括号匹配，深度为1+1=2
(a,(b,c,d))一共有两个括号形成匹配，深度为2+1=3
深度取最大的为3
非空广义表，除表头外，其余元素构成的表称为表尾，所以非空广义表尾一定是个表。
7.排序
数据结构八大排序
插入排序（直接插入排序，希尔排序）
选择排序（简单选择排序，堆排序）
交换排序（冒泡排序，快速排序）
归并排序
基数排序
（1）插入排序之直接插入排序
方法：对于给定的一组记录，初始时假定第一个记录自成一个有序的序列，其余的记录为无序序列；接着从第二个记录开始，按照记录的大小依次将当前处理的记录插入到其之前的有序序列中，直至最后一个记录插入到有序序列为止。
将21,25,49,25,16,08由小到大排序
直接插入排序各趟排序后的结果
（2）插入排序之希尔排序
希尔排序是插入排序的一种又称“缩小增量排序”，是直接插入排序算法的一种更高效的改进版本。基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录依次进行直接插入排序。
希尔排序过程
（3）选择排序之简单选择排序
基本思想是在要排序的一组数中，选出最小（或者最大）的一个数与第1个位置的数交换；然后在剩下的数当中再找最小（或者最大）的与第2个位置的数交换，依次类推，直到第n-1个元素（倒数第二个数）和第n个元素（最后一个数）比较为止。
简单选择排序过程
操作方法：
第一趟，从n 个记录中找出关键码最小的记录与第一个记录交换；
第二趟，从第二个记录开始的n-1 个记录中再选出关键码最小的记录与第二个记录交换；
以此类推.....
第i趟，则从第i 个记录开始的n-i+1 个记录中选出关键码最小的记录与第i 个记录交换，直到整个序列按关键码有序。
（4）选择排序之堆排序
堆是具有以下性质的完全二叉树：
每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；
或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。
基本思路：
a.将待排序序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆，（一般升序采用大顶堆，降序采用小顶堆)；
b.此时，整个序列的最大值就是堆顶的根节点，将堆顶元素与末尾元素交换，将最大元素"沉"到数组末端;
c.重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序。
建立大顶堆过程
排序过程
图片来自博客园
（5）交换排序之冒泡排序
冒泡排序，类似于水中冒泡，较大的数沉下去，较小的数慢慢冒起来。
基本思想是，对相邻的元素进行两两比较，顺序相反则进行交换，这样，每一趟会将最小或最大的元素“浮”到顶端，最终达到完全有序。
第一轮完毕结果
图片来自博客园
冒泡排序过程
（6）交换排序之快速排序
快速排序是对冒泡排序的一种改进。
基本思想:
1.在待排序的元素任取一个元素作为基准(通常选第一个元素，但最的选择方法是从待排序元素中随机选取一个作为基准)，称为基准元素；
2.将待排序的元素进行分区，比基准元素大的元素放在它的右边，比其小的放在它的左边；
3.对左右两个分区重复以上步骤直到所有元素都是有序的。
快速排序过程
（7）归并排序
归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法的一个非常典型的应用。分治法将问题分成一些小的问题然后递归求解，而治的阶段则将分阶段得到的各答案"修补"在一起，即分而治之。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。归并排序是一种稳定的排序方法。
分而治之
治阶段，需要将两个已经有序的子序列合并成一个有序序列，比如上图中的最后一次合并，要将[4,5,7,8]和[1,2,3,6]两个已经有序的子序列，合并为最终序列[1,2,3,4,5,6,7,8]
实现步骤
（8）基数排序
基数排序基本原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。基数排序法会使用到桶，通过将要比较的位（个位、十位、百位…），将要排序的元素分配至 0~9 个桶中，达到排序的作用，在某些时候，基数排序法的效率高于其它的比较性排序法。
排序过程
各种排序算法的总结
8.数组常用方法
Array方法
9.线性表，顺序表，链表和数组的区别
一张图表示它们的关系
在C语言中，数组和线性表的区别：数组长度不可变，线性表长度是动态可变的。
逻辑结构：结构定义中是对操作对象的数学描述，描述的是数据元素之间的逻辑关系。例如，线性结构，树形结构，图状结构或网状结构。它们都属于逻辑结构。
物理结构：又称存储结构，是数据结构在计算机中的表示（又称映像）。例如，数组，指针。
线性表：属于逻辑结构中的线性结构，它包括顺序表和链表。
顺序表：线性表中的一种，它是用数组来实现的一种线性表，所以它的存储结构（物理结构）是连续的。
链表：线性表中的一种，它的存储结构是用任意一组存储单元来存储数据元素。所以它的存储结构可以是连续的，也可以不是连续的。一般我们说的链表都是不连续的。有一种用数组来表示的链表，叫做静态链表，它的存储结构就是连续的。
数组：一种物理结构，它的存储单元是连续的。
转载简书：https://www.jianshu.com/p/2008e29c39e2
数组和链表的区别与联系:
相同：两种结构均可实现数据的顺序存储，构造出来的模型呈线性结构
不同：数组是顺序的存储结构，把所有元素按次序依次存储。
数组从栈中分配空间，链表从堆中分配空间
链表是链式的存储结构，通过指针来连接元素与元素，
数组的特点:
在内存中，数组是一块连续的区域。
数组需要预留空间，在使用前要先申请占内存的大小，可能会浪费内存空间。
插入数据和删除数据效率低，插入数据时，这个位置后面的数据在内存中都要向后移。删除数据时，这个数据后面的数据都要往前移动。
随机读取效率很高。因为数组是连续的，知道每一个数据的内存地址，可以直接找到给地址的数据。
并且不利于扩展，数组定义的空间不够时要重新定义数组
链表的特点:
在内存中可以存在任何地方，不要求连续。
每一个数据都保存了下一个数据的内存地址，通过这个地址找到下一个数据。
查找数据时效率低，因为不具有随机访问性，所以访问某个位置的数据都要从第一个数据开始访问，然后根据第一个数据保存的下一个数据的地址找到第二个数据，以此类推。
插入删除速度快
不指定大小，扩展方便。链表大小不用定义，数据随意增删。
10.ArrayList和LinkedList的区别
1.ArrayList基于动态数组的数据结构，LinkedList基于链表的数据结构。
2.对于随机访问get和set，ArrayList优于LinkedList，因为LinkedList要移动指针。
3.对于新增和删除操作add和remove，LinkedList比较占优势，因为ArrayList要移动数据。
在一个长度为n的顺序表中删除第i个元素，要移动n-i个元素。如果要在第i个元素前插入一个元素，要后移n-i+1个元素。
向一个长度为n的向量的第i个元素(1≤i≤n+1)之前插入一个元素时，需向后移动n-i+1个元素。
从一个长度为n的顺序表中删除第i个元素(1≤i≤n)时,需向前移动n-i个元素
11.稀疏矩阵
原文链接：https://blog.csdn.net/qq_35733751/article/details/80843589
在矩阵中，若数值为0的元素数目远远多于非0元素的数目，并且非0元素分布没有规律时，则称该矩阵为稀疏矩阵
压缩存储方式：三元组
三元组方式存储数据的策略是只存储非零元素。但是稀疏矩阵中非零元素的分布是没有任何规律的，在这种情况下，存储方案是：
1.存储非零元素
2.同时存储该非零元素所对应的行下标和列下标
3.稀疏矩阵中的每一个非零元素需由一个三元组(i, j, aij)唯一确定,稀疏矩阵中的所有非零元素构成三元组线性表，三元组中的i就是行下标，j是列下标，aij是对应的元素值。
稀疏矩阵的压缩存储
当我们确定三元组的存储策略后，下一步我们要做的就是如何把这样的三元组存储下来。我们在进行保存时，需要把矩阵中的行数，列数，非零元素个数，矩阵中的数据都保存在data数据域（数组），在data数据域中的每个数据元素都是以三元组（行号，列号，元素值）形式存储，data域中表示的非零元素通常以行序为主序顺序排列，下标按行有序的存储结构。如图2所示：
定义存储结构
12.对称矩阵的压缩
在处理对称矩阵的存储的问题上，通常为多个值相同的元素分配一个存储空间，也就是将n^2个元素压缩存储到n*(n+1)/2个元素的存储空间中。一般情况下，以行序为主序存储其下三角中的元素。
假设以一维数组M[n(n+1)/2]作为n阶对称矩阵A的存储结构，则M[k]和矩阵中的元素aij之间存在着下述一一对应的关系：
网友评论