知识点-数据结构与算法

数据结构与算法相关知识点。

会一直持续更新。

1.时间复杂度中的O

O: 最坏情况下的时间复杂度

2.数据的逻辑结构

3.数据的存储结构

顺序存储：把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中，元素之间的关系由存储单元的邻接关系来体现。

优点：可以随机存取，快；存储密度大

缺点：删除，插入操作耗时在移动元素上，只能使用相邻的一整块存储单元，可能产生较多的外部碎片

链式存储：不要求逻辑上相邻的元素在物理位置上也相邻，借助指示元素存储地址的指针来表示元素之间的逻辑关系。

优点：删除，插入快，外部碎片少，能充分利用所有存储单元

缺点：不能随机存取

索引存储：在存储元素信息的同时，还建立附加的索引表。

散列存储：根据元素的关键字直接计算出该元素的存储地址，又称哈希(Hash) 存储。

4. 头指针与头结点

头指针：指向第一个节点存储位置的指针，具有标识作用，头指针是链表的必要元素，无论链表是否为空，头指针都存在。

头结点：放在第一个元素节点之前，便于在第一个元素节点之前进行插入和删除的操作。

头结点不是链表的必须元素，可有可无，头结点的数据域也可以不存储任何信息。

5.查找单链表中倒数第K个结点

1. 建立两个指针：fast、slow

2. 先让fast走k步

3. 再让fast和slow一起走，直到fast走到末尾后一位，slow指向的就是倒数第k个节点

listNode* get_kth_from_end(listNode *head, int k) {
listNode *fast = head; // 先走的指针
listNode *slow = head; // 后走的指针
while (k--) fast = fast->next; // 先让fast走k步
while (fast != NULL) { // 再让fast和slow一起走，直到fast走到末尾后一位
slow = slow->next;
fast = fast->next;
}
return slow;
}

6.单链表的头插法与尾插法

头插法：在插入时，新的结点插入到当前链表的表头。

s->next=L->next;		
L->next=s;				

尾插法：插入时，新的结点插入到当前链表的表尾，为此必须增加一个尾指针r，使其始终指向当前链表的尾结点。

r->next=s;			//r的指针域指向s
r=s;

7.单链表逆序

1. 建立两个指针：p、q

2. p 用于遍历链表中的每个节点

3. q 用于头插法创建新的逆序链表

void reverse(listNode* head) {
listNode *p, *q;
p = head->next;
head->next = NULL;
while (p) { // p用于遍历每个节点
q = p;
p = p->next; // 在该节点的next指针改变前更新p
q->next = head->next; // 类似头插法
head->next = q; // 类似头插法
}
}

8.判断链表有没有环

快慢指针法：从头开始设置两个指针，快指针每次走2 步，慢指针每次走1 步。

如果快指针先碰到尾，则无环。否则两个指针之后一定会重合，则有环。

9.栈与队列

栈：

定义：只允许在表尾（栈顶）进行插入和删除的线性表，“先进后出”

顺序栈：数组（存放栈中元素）、栈顶指针

链栈：栈顶指针

队列：

定义：只允许在表的一端（队尾）插入，在另一端（队首）删除的线性表，“先进先出”

顺序队列：数组（存放队列中元素）、头指针、尾指针

链式队列：队首指针、队尾指针

两个栈模拟一个队列：队列是先进先出，栈的是先进后出。同一组数据连续执行两次先进后出之后再出栈，就可以实现队列的先进先出。

10.区分循环队列是队空还是队满

如何区分循环队列是队空还是队满

一般情况，队空和队满的判断条件都是Q.front == Q.rear

front：指向第一个数

rear：指向最后一个数的下一个位置，即将要入队的位置

队空：Q.front == Q.rear

队满：(Q.rear+1) % MaxSize == Q.front

元素个数：(Q.rear-Q.front+MaxSize) % MaxSize

怎么区分？

方法一：牺牲一个单元（即最后一个单元不存数据）来区分队空和队满

方法二：队列结构体中增加一个Q.size表示元素个数

11.栈在括号匹配中的算法思想

设置一个空栈，顺序读入括号。

若是左括号，则进栈

若是右括号：

​ 若栈空，则匹配失败，右括号多余

​ 否则，弹出一个栈顶的左括号

读完所有括号后若栈空，则表达式中括号匹配正确否则，匹配失败，左括号多余