数据结构知识点

一、顺序表

1、属于线性表。

2、顺序表插入删除需要移动元素。

3、动态顺序表中，插入需要检查是否需要扩容

4、数据在内存中是连续的，可以支持随机访问

1、顺序表插入删除：

a、顺序表插入元素，需要移动元素，这里需要把[i, n - 1]区间的元素全部向后移动一次，故移动的次数为n - 1 - i + 1

b、顺序表删除元素，需要移动元素，这里需要把[i + 1, n - 1]区间的元素全部向前移动一次，故移动的次数为 n - i - 1

二、链表

1、属于线性表。

2、链表插入删除元素只需要修改指针指向，不需要移动元素。

3、每次插入元素，都是先出开一个节点的空间，不需要事先估计存储空间。

4、链表是用指针链接前后节点，数据在内存中不一定连续，链表没有索引，不能随机访问。

5、链表是由节点构成，自然链表长度越大空间开销越大。 因此会为节点间的逻辑关系而增加额外的存储开销

1、单链表

1.1、插入

链表插入：

a、空链表插入时，首指针需要改变。

b、非空链表插入时，尾指针需要改变。

//在单链表指针为p的结点之后插入指针为s的结点
s->next=p->next; 
p->next=s;

具体操作

1.2、删除

//在一个单链表中，q 的前一个节点为 p，删除 q 所指向节点时
p->next=q->next; //链接起来
delete q;

注意：

在长度为n(n>1)的单链表上，设有头和尾两个指针，执行.（删除单链表中的最后一个元素操作）与链表的长度有关。

因为其需要遍历单链表，找到尾节点的前一个节点。所以与长度有关。

其他的头删、头插、尾插都不需要遍历链表

2、循环链表

循环链表是另一种形式的链式存贮结构。它的特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环。

（1）单循环链表——在单链表中，将终端结点的指针域NULL改为指向表头结点或开始结点即可。

（2）多重链的循环链表——将表中结点链在多个环上。

指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。

2.1、双向循环链表判空

//双向带头循环链表中，head不是存放有效数据的节点，如果只有一个head节点，说明链表为空。
head->next==head;

2.2、双向循环插入

//在一个循环双向链表中，要在p所指的节点之前插入s所指节点
s->next=p;
s->prev=p->prev;
p->prev->next=s;
p->prev=s;// 最后对p的前继节点做出修改

链表和顺序表的区别：

1、链表和顺序表都属于线性表。

a、顺序存储结构---顺序表

b、链式存储结构---链表

2、链表不能随机访问其中的某个元素，顺序表可以

3、链表能做的事，顺序表都可以完成，只是操作方法不同，效率不同

4、链表插入和删除元素因为不需要移动节点，所以相比较于数组而言，链表的时间复杂度为O(1)，数组的时间复杂度O(n)。

注意：链表的插入和删除不是所有情况下都比顺序表快，比如尾插尾删，顺序表的时间复杂度为O（1），并且如果是单链表，如果要在中间某个节点的前面插入/删除一个节点，则需要遍历。所以时间的快慢要分情况看待。

5、链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。

6、顺序表物理相邻逻辑相邻，链表逻辑相邻物理不一定相邻

三、栈

1、栈是一种后进先出的数据结构

2、顺序表和链表都可以用来实现栈，不过一般都使用顺序表，因为栈想当于是阉割版的顺序表，只用到了顺序表的尾插和尾删操作，顺序表的尾插和尾删不需要搬移元素效率非常高，故一般都是使用顺序表实现。

3、栈只能在栈顶进行输入的插入和删除操作。

4、队列只能从队头删除元素。

5、栈是有入栈和出栈操作，出栈就是从栈中删除一个元素。

3.1、链栈与顺序栈区别

1、如果是链栈，一般需要进行头插或者头删操作，而顺序栈一般进行尾插和尾删操作，链表的操作比顺序表复杂，因此使用顺序结构实现栈更简单。

2、链式结构实现栈时，每次入栈相当于链表中头插一个节点，没有扩容一说。

3.2、用栈模拟队列注意事项：

1、用栈模拟实现队列可以使用两个栈，一个栈模拟入队列，一个栈模拟出队列。

2、出队列时直接弹出模拟出队列栈的栈顶元素，当该栈为空时，将模拟入队列栈中所有元素导入即可，不是每次都需要导入元素。

3、一个栈模拟入队列，一个栈模拟出队列，入队列时，将元素直接往模拟入队列的栈中存放

4、入队列操作时间复杂度为O(1)

四、队列

1、队列是先进先出的

2、顺序表和链表都可以用来实现队列。

3、出队操作，一定会影响头指针，如果出队之后，队列为空，会影响尾指针。

4、数据入队列时一定从尾部插入、

5、队列只能从队头删除元素。

1、出队列注意事项：

用无头单链表存储队列，其头指针指向队头结点，尾指针指向队尾结点，则在进行出队操作时。

一定会修改头指针，如果出队之后，队列为空，需要修改尾指针。

2、顺序结构实现循环队列：

为什么用循环队列：

队列适合使用链表实现，使用顺序结构(即固定的连续空间)实现时会出现假溢出的问题，因此大佬们设计出了循环队列，循环队列就是为了解决顺序结构实现队列假溢出问题的。

1、循环队列的长度都是固定的

2、队头和队尾在同一个位置时队列可能是空的，也可能是满的，因此无法判断。

3、设置计数即添加一个字段来记录队列中有效元素的个数，如果队列中有效元素个数等于空间总大小时队列满，如果队列中有效元素个数为0时队列空。

4、循环队列也是队列的一种，是一种特殊的线性数据结构

循环队列判空：

(rear - front) % (N + 1)

解释：有效长度一般是rear-front, 但是循环队列中rear有可能小于front，减完之后可能是负数，所以需要+N，此时结果刚好是队列中有效元素个数，但如果rear大于front，减完之后就是有效元素个数了，再加N后有效长度会超过N，故需要%N。

五、堆

1、堆的性质

1、堆是在完全二叉树的基础上进行了条件的限制，即：每个节点都比其孩子节点大，则为大堆；每个节点都比其孩子节点小则为小堆。

2、大根堆：根结点 > 子结点，总是最大的，并且在堆的每一个局部都是如此。例如{3,1,2}可以看作为大根堆，而{3,2,1}亦可以看作为大根堆。大根堆的根结点在整个堆中是最大的元素

3、小根堆：小根堆的性质与大根堆类似。

4、删除操作需要执行向下调整算法

5、插入操作需要执行向上调整算法

向下调整的基本操作：

1、建堆时，从每一个非叶子节点开始，倒着一直到根节点，都要执行一次向下调整算法。

2、删除元素时，首先交换堆顶元素与堆中最后一个元素，对中有效元素个数减1，即删除了堆中最后一个元素，最后将堆顶元素向下调整。

时间复杂度：O(n)

堆的常用场景

1、堆排序。
2、建立优先级队列，若利用堆来建立优先级队列，可以快速的获取到队列中优先级最高/低的任务。
3、n个元素中排列出前k大的元素问题，对于此类问题，可以建立一个小根堆，依次读入n个元素并调整，并在堆的规模达到k+1时，剔除掉第1个元素，剩下k个较大元素，保持堆的规模不超过k，一直循环即可得到最终的结果。

六、二叉树

1、二叉树的基本性质

1、高度h = log(n)向上取整注意：底数是2。即log (n) + 1。

2、完全二叉树中如果一个节点没有左孩子，则一定没有右孩子，必定为一个叶子节点，最后一层一定为叶子节点，但是倒数第二层也可能存在叶子节点。

3、在任意二叉树中，度为0的节点都比度为2的节点多1个。

4、在完全二叉树中，如果节点总个数为奇数，则没有度为1的节点，如果节点总个数为偶数，只有一个度为1的节点。

5、对于任意的树都满足：边的条数比节点个数少1，因为每个节点都有双亲，但是根节点没有

6、一颗深度为 h 的满二叉树拥有 2^h-1 个结点（根结点深度为1）

7、一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足只有一个叶子结点。

2、哈夫曼树的基本性质

哈夫曼树(Huffman)树又称最优二叉树。它是n个带权叶子结点构成的二叉树中，带权路径长度WPL最小的二叉树。因为构造这种树的算法是最早由哈夫曼于1952年提出的，所以被称之为哈夫曼树。

1、路径
树中从“一个结点”到“另一个结点”之间的分支。
2、路径长度
一个路径上的分支数量。
3、树的路径长度
从树的根节点到每个节点的路径长度之和。
4、节点的带权路径路径长度
其实也就是该节点到根结点的路径长度乘以该节点的权。
5、树的带权路径长度
树中各个叶节点的路径长度*该叶节点的权的和，常用WPL(Weight Path Length)表示。

6、哈夫曼树的总结点数是2n-1（n是叶子节点数），并且非叶子节点数目总是比叶子节点数目小1。哈夫曼树没有度为1的节点