26考研 | 王道 | 数据结构 | 408数据结构算法题笔记

408数据结构算法题笔记

1.顺序表

1.快排部分

1.快排代码

2.快排的划分思想

空间：O（1）

时间：O（n）

划分实战

其实就是把数组分成两半，那就直接找第n/2小的元素就好了

3.快排实战

2.归并排序

归并排序的合并两个数组

2.链表

1.按位序查找

//这样找中间结点更好记一点 如果是1 2 3 4 5，那么l就是3，如果是1 2 3 4 5 6，那l就是4
l = head;
r = head;
//1.找中间节点
while (r->next && r->next->next)
{
	l = l->next;
	r = r->next->next;
}

也可以用两个指针，让第一个指针先移动K步

先获得长度，然后长的减去短的，让长的先移动这个长度，然后一起往后移动

2.双指针 按关键字插入和删除

pre始终是p的前驱，p用来判断找没找到关键字

常用思想：如果只说了时间复杂度，那说明大概就是时间换空间了，再加上所有数据都小于n，所以要一个辅助数组，如果出现了这个数，把这个数作为下标的数组元素标记为1

然后删除的时候使用前后指针

3.头插-原地逆置

//头插法原地逆置
p=head;//原来链表的第一个结点
head2->next = NULL;//虚拟头结点
while (p != NULL)
{
	NODE* q = p;
	p = p->next;
	q->next = head2->next;
	head2->next = q;
}

4.尾插-保持原来顺序

找到中间结点然后分成两部分，把第二部分逆置，然后分别插入新的链表就行

5.2018综合实战

void change(NODE* head)
{
	NODE head2,* l, *r, *p,*q1,*q2;
	head1->next = head;
	l = head;
	r = head;
	//1.找中间节点
	while (r->next && r->next->next)
	{
		l = l->next;
		r = r->next->next;
	}
	//2.和原来链表断开 l是前半段的最后一个结点
	p = l->next;
	l->next = NULL;
	//3.头插法原地逆置后半部分
	head2->next = NULL;
	while (p != NULL)
	{
		NODE* q = p;
		p = p->next;
		q->next = head2->next;
		head2->next = q;
	}
	//4.一个接着一个重排 注意下面的交替顺序
	q1 = head;
	q2 = head2->next;
	while (q1 && q2)
	{
		NODE* s1 = q1;
		q1 = q1->next;
		NODE* s2 = q2;
		q2 = q2->next;
		s1->next = s2;
		s2->next = q1;
	}
}

3.二叉树

1.遍历

2.高度

3.宽度

4.WPL

5.二叉排序树

98. 验证二叉搜索树 - 力扣（LeetCode）

这样也行

6.平衡二叉树

7.完全二叉树

4.图

1.图的顺序遍历-邻接矩阵邻接表存储

1.邻接矩阵

名字随自己喜欢定义

#define MAXV 6
typedef struct{
   int numE,numV;//边数和顶点数
   char list[MAXV];//顶点表
   int edge[MAXV][MAXV];//邻接矩阵
}G;

2.邻接表

3.实战21年真题

其实就是统计一下度为奇数的个数，就是遍历个二维数组，可以说相当简单了

1.邻接矩阵

2.邻接表

4.实战23年真题

1.邻接矩阵

2.邻接表

时间：O(v+e)，空间：O(v)

2.拓扑排序

3.多重链表、十字链表数据结构的定义

复习对应的第六章的部分，要知道怎么写

4.图的遍历和最短路（有时间的话看看DFS，BFS，迪杰斯特拉，弗洛伊德什么的）