第十一讲:高阶应用
主讲人:刘财政
B站:@计算机考研刘财政考点框架CON T EN T S
目录
考点一 线性表的高阶应用
考点二 二叉树的应用
考点三 图的高阶应用
考点四 其他高阶应用高阶应用
算法解法:
➢ 暴力解:枚举方法
➢ 可行解:
➢ 最优解:缘分方法高阶应用
算法解题套路:
➢ 方法体,非完整程序,核心代码
➢ 结构体定义
➢ 算法思想和算法步骤
➢ 算法实现
➢ 算法复杂度分析:时间复杂度和空间复杂度高阶应用
得分神助攻:
➢ 图文结合
➢ 代码注释
➢ 命名规范
➢ 格式严谨高阶应用
在算法中一般可直接使用的库函数
1.max:求最大值,时间复杂度为 O(n)
2.min:求最小值,时间复杂度为 O(n)
3.length:求长度,时间复杂度为 O(n)
4.pop():出栈
5.push():入栈CON T EN T S
目录
考点一 线性表的高阶应用
考点二 二叉树的应用
考点三 图的高阶应用
考点四 其他高阶应用考点框架
哈希策略
单链表或者数组逆序
单链表或者数组旋转
双指针策略【哈希策略】考点一:线性表的高阶应用
将记录的存储位置与它的关键字之间建立一个对应关系
常用的方法有:
直接定址法:hash(key)=keyhash(key) = a * key + b
取余法:hash(key)=key % p
空间换时间的一种思路考点一:线性表的高阶应用
1、使用算法复杂度为O(N)实现排序,其中N是元素个数,且元素大小不超过n。
例如:给定1,4,5,6,4,3,4,2,1,5,6。
0 1 2 3 4 5 6
0 0 0
1
01 0
3
20 20
2考点一:线性表的高阶应用
#define MAXNUM 200 // 待排序数组中元素的最大值,值域为[0, MAXNUM)
void BucketSort(int a[], int n) {
if (a == NULL || n <= 0) {
return;
}
int slots[MAXNUM] = {0}; // 用于记录每个元素出现的次数,初始化为0
for (int i = 0; i < n; ++i) {
++slots[a[i]]; // 记录每个元素出现的次数
}
int j = 0;
for (int i = 0; i < MAXNUM; ++i) { // 遍历每个元素出现的次数
while (slots[i]--) { // 如果该元素出现了,则将其重新放入数组a中
a[j++] = i;
}
}
}考点一:线性表的高阶应用
2、用单链表保存 m 个整数,结点的结构为:[data][link],且|data|≤n(n 为正
整数)。现要求设计一个时间复杂度尽可能高效的算法,对于链表中 data 的绝
对值相等的结点,仅保留第一次出现的结点而删除其余绝对值相等的结点。例如
,若给定的单链表 head 如下:Head
21 -15 15 7 ⋀
则删除结点后的 head 为:Head
21 -15 7 ⋀
要求:
1)给出算法的基本设计思想。
2)使用 C 或 C++语言,给出单链表结点的数据类型定义。
3)根据设计思想,采用 C 或 C++语言描述算法,关键之处给出注释。
4)说明你所设计算法的时间复杂度和空间复杂度。考点一:线性表的高阶应用
p
head
a a a a a a a
1 2 3 i-1 i i+1 n ∧
q ptr考点一:线性表的高阶应用
p
head
a a a a a a a
1 2 3 i-1 i i+1 n ∧
q ptr考点一:线性表的高阶应用
p
head
a a a a a a a
1 2 3 i-1 i i+1 n ∧
q ptr考点一:线性表的高阶应用
// 删除单链表中所有值重复的结点,使得所有结点的值都不相同。
void Delete_Node_Value(LNode *L) {
// 删除以L为结点的单链表中所有值相同的结点
LNode *p = L->link, *q, *ptr;
while (p != NULL) { // 检查链表中的所有结点
q = p; ptr = p-> link;
//检查结点p的所有后继结点ptr
while (ptr != NULL) {
if (|ptr->data| == |p->data|)
{q-> link = ptr-> link; free(ptr); ptr = q-> link;}
else {q = ptr ; ptr = ptr-> link;}
}
p = p-> link;
}
}考点一:线性表的高阶应用
(1)算法的基本设计思想 算法的核心思想是用空间换时间。使用辅助数组记
录链表中已出现的数值,从而只需对链表进行 一趟扫描。 因为|data|≤n,故
辅助数组 q 的大小为 n+1,各元素的初值均为 0。依次扫描链表中的各结点,
同 时检查 q[|data|]的值,如果为 0,则保留该结点,并令 q[|data|]=1;否则,
将该结点从链表中删除。
(2)使用 C 语言描述的单链表结点的数据类型定义
typedef struct node {
int data;
struct node *link;
}NODE;
typedef NODE *PNODE;考点一:线性表的高阶应用
#define N 100 // data域绝对值的最大值,data域绝对值的范围为[0, N]
void DeleteDuplicate(LinkList head, int n) {
if (!head) { return; } // head为空,链表不存在
bool* slots = new bool[n + 1]; // 用于记录每个结点data域绝对值是否出现过
for (int i = 0; i <= n; ++i) { // 初始化slots数组
slots[i] = false;
}
for (LinkList p = head; p->link;) {
int key = abs(p->link->data); // 计算p的后继结点data域绝对值
if (slots[key]) { // 如果p的后继结点data域绝对值出现过,删除p的后继结点
LinkList node = p->link;
p->link = node->link;
delete node;
} else { // 否则,将p的后继结点data域绝对值标记为出现过
slots[key] = true;
p = p->link;
}
}
delete[] slots;
}考点一:线性表的高阶应用
3、已知一个整数序列A=(a , a , …, a ),其中0<=a <=n(0<=i<n)。
0 1 n-1 i
若存在a =a =…=a =x且m>n/2(0<=p <n, 1<=k<=m),则称 x
p1 p2 pm k
为 A 的主元素。例如 A=( 0,5,5,3,5,7,5,5 ),则 5 为主元素;
又如 A= ( 0,5,5,3,5,1,5,7 ),则A 中没有主元素。假设 A 中
的 n 个元素保存在一个一维数组中,请设计一个尽可能高效的算法,找
出 A 的主元素。若存在主元素,则输出该元素;否则输出-1。要求:
(1)给出算法的基本设计思想。
(2)根据设计思想,采用 C 或 C++语言描述算法,关键之处给出注释。
(3)说明你所设计算法的时间复杂度和空间复杂度。考点一:线性表的高阶应用
(1)算法思想:算法的基本设计思想 算法的核心思想是用空间换时间。使用辅
助数组记录数组中已出现的数值,从而只需对数组进行 一趟扫描。 因为|data|≤n,
故辅助数组 q 的大小为 n+1,各元素的初值均为 0。依次扫描数组中的各结点,
同时检查 q[|data|]的值,如果为 0,并令 q[|data|]=1;否则,q[|data|] + 1。考点一:线性表的高阶应用
例: A=( 0,5,5,3,5,7,5,5 ),则 5 为主元素;又如 A= ( 0,5,5,3,
5,1,5,7 ),则A 中没有主元素。
0 1 2 3 4 5 6 7
0 0 0 01 0 05 0
1 1
0 1 2 3 4 5 6 7
0 0 0 0 0 0 0
1
1 1 4 1考点一:线性表的高阶应用
int FindMajorData(int a[], int n) {
int* slots = new int[n + 1]; // 用于记录每个元素出现的次数
for (int i = 0; i <= n; ++i) { // 初始化slots数组
slots[i] = 0;
}
for (int i = 0; i < n; ++i) {
++slots[a[i]]; // 统计每个元素出现的次数
}
int major = -1;
for (int i = 0; i <= n; ++i) {
if (slots[i] > n / 2) { // 如果某个元素出现的次数大于n/2,即为major
major = i;
break;
}
}
delete[] slots; // 释放slots数组
return major;
}考点一:线性表的高阶应用
4、给定一个含n(n>=1)个整数的数组,请设计一个在时间上尽可能高效的算
法,找出数组中未出现的最小正整数。例如,数组{-5,3,2,3}中未出现的最小正整
数是1,数组{1,2,3}中未出现的最小正整数是4.要求:
(1)给出算法的基本设计思想
(2)根据设计思想,采用C或C++语言描述算法,关键之处给出注释。
(3)说明你所设计的算法的时间复杂度和空间复杂度考点一:线性表的高阶应用
(1)给出算法的基本设计思想:设要查找的数组中未出现的最小正整数为K。K
取值范围只能是[1,n+1]。采用类似基数排序的思想,分配一个数组B[n],用来
标记A中是否出现了1~n之间的正整数。从左至右依次扫描数组元素A[i]并标记数
组B。若A[i]是负数、零或是大于n,则忽略该值;否则,根据计数排序的思想将
B[A[i]-1]置为1.标记完毕,遍历数组B,查找第一个值为0的元素,其下标+1即
为目标元素K;找不到0时,K = n+1。考点一:线性表的高阶应用
int FindMissMin(int a[], int n) {
bool* b = new bool[n]; // 标记数组,用于标记1到n中的每个数字是否出现过
for (int i = 0; i < n; ++i) {
b[i] = false;
}
for (int i = 0; i < n; ++i) {
if (a[i] > 0 && a[i] <= n) { // a[i]在[1, n]范围内,标记为出现过
b[a[i] - 1] = true;
}
}
int i = 0;
while (i < n && b[i]) { // 遍历标记数组,找到第一个未出现的数字
++i;
}
delete[] b;
return i + 1;
}考点一:线性表的高阶应用
哈希策略解题总结:
(1)找题眼 : 0<=a <=n
i
(2)开数组,并置0
(3)定下标:计数或者判有无
(4)后处理【单链表或者数组逆序】考点一:线性表的高阶应用
1、给定一个单链表,求出一个快速算法,实现单链表逆序
void ReverseList(LinkList head) {
if (!head || !head->next) {
return; // head为空或者只有一个结点,无须反转
}
LinkList p = head->next;
head->next = NULL;
while (p) {
LinkList node = p; // 记录当前结点
p = p->next; // 将p指向下一个结点
node->next = head->next;
head->next = node; // 头插法,将node结点插入到head结点之后
}
}考点一:线性表的高阶应用
2、给定一个数组,求出一个算法,实现数组逆置。
对位交换法
0 1 2 3 4 5 6 7 8 9
3 8 2 7 1 5 3 4 6 0
下标是1和8
8
6
0 1 2 3 4 5 6 7 8 9考点一:线性表的高阶应用
2、给定一个数组,求出一个算法,实现数组逆置。
对位交换法
0 1 2 3 4 5 6 7 8 9
3 8 2 7 1 5 3 4 6 0
下标是2和7
4
2
0 1 2 3 4 5 6 7 8 9考点一:线性表的高阶应用
2、给定一个数组,求出一个算法,实现数组逆置。
对位交换法
0 1 2 3 4 5 6 7 8 9
3 8 2 7 1 5 3 4 6 0
下标是3和6
3 7
0 1 2 3 4 5 6 7 8 9考点一:线性表的高阶应用
2、给定一个数组,求出一个算法,实现数组逆置。
对位交换法
0 1 2 3 4 5 6 7 8 9
3 8 2 7 1 5 3 4 6 0
下标是4和5
5 1
0 1 2 3 4 5 6 7 8 9考点一:线性表的高阶应用
2、给定一个数组,求出一个算法,实现数组逆置。
对位交换法
0 1 2 3 4 5 6 7 8 9
3 8 2 7 1 5 3 4 6 0
下标是0和9
下标是1和8
下标是2和7
下标是3和6
下标是4和5
下标和是9(length-1)
0 6 4 3 5 1 7 2 8 3
0 1 2 3 4 5 6 7 8 9考点一:线性表的高阶应用
2、给定一个数组,求出一个算法,实现数组逆置。
对位交换法
0 1 2 3 4 5 6 7 8 9
对位交换:
3 8 2 7 1 5 3 4 6 0
下标是0和9
下标是1和8
下标是2和7
下标是3和6
下标是4和5
时间复杂度是O(n)
0 6 4 3 5 1 7 2 8 3
空间复杂度是O(1)
0 1 2 3 4 5 6 7 8 9考点一:线性表的高阶应用
2、给定一个数组,求出一个算法,实现数组逆置。
void ReverseList(SqList& l) {
for (int i = 0, j = l.length - 1; i < j; ++i, --j) {
swap(l.data[i], l.data[j]);
}
}考点一:线性表的高阶应用
【改进,部分逆置】试写一算法,实现顺序表的就地逆置,但是要逆置
这个数组那一段的开始下标from,要逆置那一段的结束下标to 。
0 1 2 3 4 5 6 7 8 9
3 8 2 7 1 5 3 4 6 0
from To考点一:线性表的高阶应用
0 1 2 3 4 5 6 7 8 9
3 8 2 7 1 5 3 4 6 0
from To
需要交换值的元素下表是:
from + i VS to – i
i = (to – from + 1)/2考点一:线性表的高阶应用
/* 这个函数传入的参数为要逆置的数组 要逆置这个数组那一段的
开始下标from 要逆置那一段的结束下标to */
void Reverse(int R[], int from, int to){
int i, temp;//temp为临时变量
for(i=0; i < (to - from + 1)/2; i++){
temp = R[from + i];
R[from + i] = R[to - i];
R[to - i] = temp;
}
}考点一:线性表的高阶应用
3、设线性表 L=(a ,a ,a ,…,a ,a ,a )采用带头结点的单链表保存,
1 2 3 n-2 n-1 n
链表中结点定义如下:
typedef struct node{
int data;
struct node * next:
} NODE;
请设计一个空间复杂度为O(1)且时间上尽可能高效的算法,重新排列L 中的各
结点, 得到线性表 L‘=(a ,a ,a ,a , a a ,…)。
1 n 2 n-1 3, n-2
要求:
(1)给出算法的基本设计思想。
(2)根据设计思想,采用 c 或 c++语言描述算法,关键之处给出注释。
(3)说明你所设计的算法的时间复杂度。考点一:线性表的高阶应用
(1)算法的基本设计思想:算法分 3 步完成。
第 1步,采用两个指针交替前行,找到单链表的中间结点;
第 2 步.将 单链表的后半段结点原地逆置;
第 3 步,从单链表前后两段中依次各取一个结点,按要求重排。考点一:线性表的高阶应用
void ReverseList(NODE* head) {
if (!head || !head->next) {
return; // head为空或者只有一个结点,无须反转
}
LinkList p = head->next;
head->next = NULL;
while (p) {
LinkList node = p; // 记录当前结点
p = p->next; // 将p指向下一个结点
node->next = head->next;
head->next = node; // 头插法,将node结点插入到head结点之后
}
}考点一:线性表的高阶应用
void Rearrange(NODE* head) {
// 快慢指针找链表中点
NODE* slow = head;
for (NODE* fast = head; fast && fast->next; fast = fast->next->next) {
slow = slow->next; // 快指针走两步,慢指针走一步
}
// 采用头插法将链表的后半部分转置
ReverseList(slow); // 转置slow->next到链表尾结点之间的链表
NODE* bottom = slow->next; // bottom指向链表后半部分
slow->next = NULL; // 断开链表前半部分和后半部分的连接
// 将链表的后半部分交叉插入前半部分中
for (NODE *p = head->next, *q = bottom; q;) {
NODE* node = q; // 记录当前结点
q = q->next; // 将q指向下一个结点
node->next = p->next;
p->next = node; // 交叉插入,将node结点插入p结点之后
p = node->next; // p指向下一个结点
}
}考点一:线性表的高阶应用
单链表或者数组逆置解题总结:
(1)数组逆置:对位交换法
(2)单链表逆置:头逆尾顺【单链表或者数组旋转】考点一:线性表的高阶应用
【回顾】设有一个线性表存放在一维数组a[0,…,n-1]中,编程将数组
中每个元素循环右移k位,要求只用一个辅助单元,时间复杂度为O(n)。考点一:线性表的高阶应用
给定A(a ,a ,…,a ,b ,b ,…,b )
1 2 m 1 2 n
给定A(a,b)
逆置reverse(0,n+m-1)
给定A(b-1,a-1)
逆置reverse(0,n-1)
给定A(b,a-1)
逆置reverse(n,m+n-1)
给定A(b,a)=A( b, a)考点一:线性表的高阶应用
给定A(1,2,3,4,a,b,c,d, e)
给定A(a,b)
给定A(e,d,c,b,a,4,3,2, 1)
逆置reverse(0,8)
给定A(b-1,a-1)
逆置reverse(0,n-1) 给定A(a,b,c,d,e,4,3,2, 1)
给定A(b,a-1)
逆置reverse(n,m+n-1)
给定A(b,a)=A( b, a)
给定A(a,b,c,d, e , 1,2,3,4)考点一:线性表的高阶应用
void Reverse(int* array, int p, int q) { // 这一步是实现数组逆置
for (; p < q; p ++, q -- ){
int temp = array[p];
array[p] = array[q];
array[q] = temp;
}
}
void RightShift(int* array, int n, int k) {
k %= n;
Reverse(array, 0, n - 1);
Reverse(array, 0, k - 1);
Reverse(array, k, n - 1);
}考点一:线性表的高阶应用
1、设将 n(n>1)个整数存放到一维数组 R 中。试设计一个在时间和空间两方
面都尽可能高效的算法。将 R 中保存的序列循环左移 p(0<p<n)个位置,即
将 R 中的数据由(X , X …X )变换为(X , X …X , X , X …X )。要求:
0 1 n-1 p p+1 n-1 0 1 p-1
(1) 给出算法的基本设计思想。
(2) 根据设计思想,采用 C 或 C++语言描述算法,关键之处给出注释。
(3) 说明你所设计算法的时间复杂度和空间复杂度。考点一:线性表的高阶应用
(1)算法的基本设计思想: 可以将这个问题看做是把数组 ab 转换成数组 ba
(a 代表数组的前 p 个元素,b 代表数组中余下的 n-p 个元 素),先将 a 逆置
得到 a-1 b,再将 b 逆置得到 a-1 b-1 ,最后将整个 a-1 b-1 逆置得到(a-1 b-1)-
1 =ba。设 Reverse 函数执 行将数组元素逆置的操作,对 abcdefgh 向左循环移
动 3(p=3)个位置的过程如下:
Reverse(0,p-1)得到cbadefgh;
Reverse(p,n-1)得到 cbahgfed;
Reverse(0,n-1)得到 defghabc;考点一:线性表的高阶应用
void Reverse(int R[],int from,int to) {
int i,temp;
for(i = 0; i < (to-from+1)/2; i++){
temp = R[from+i];
R[from+i] = R[to-i];
R[to-i] = temp;
}
} // Reverse
void Converse(int R[],int n,int p){
Reverse(R,0,p-1);
Reverse(R,p,n-1);
Reverse(R,0,n-1);
}考点一:线性表的高阶应用
2、给定一个链表和一个特定值 x,对链表进行分隔,使得所有小于 x 的节点都在
大于或等于 x 的节点之前。应当保留两个分区中每个节点的初始相对位置。示例:
输入: head = 1->4->3->2->5->2, x = 3
输出: 1->2->2->4->3->5考点一:线性表的高阶应用
用快慢指针来解,快指针先走k步,然后两个指针一起走,当快指针走到末尾时,
慢指针的下一个位置是新的顺序的头结点,这样就可以旋转链表了,首先一个
就是当原链表为空时,直接返回NULL,还有就是当k大于链表长度和k远远大于
链表长度时该如何处理,我们需要首先遍历一遍原链表得到链表长度n,然后k
对n取余,这样k肯定小于n,就可以用上面的算法了,代码如下:考点一:线性表的高阶应用
int GetLength(LinkList head) {
int len = 0;
for (LinkList p = head->next; p; p = p->next) {
len++;
}
return len;
}考点一:线性表的高阶应用
void RightRotate(LinkList head, int k) {
if (!head) {
return; // head为空,链表不存在
}
int len = GetLength(head); // 获取链表长度
k = k % len; // 计算实际需要旋转的位置
if (k == 0) {
return; // k为0,无须旋转
}
// 使用快慢指针法找到倒数第k个结点
LinkList fast = head; // fast指向最后一个结点的前驱
for (int i = 0; i < k; ++i) {
fast = fast->next;
}
LinkList slow = head; // slow指向倒数第k个结点的前驱
while (fast->next) {
fast = fast->next;
slow = slow->next;
}
fast->next = head->next; // 将链表首尾相连
head->next = slow->next; // 将倒数第k个结点作为新的链表的首结点
slow->next = NULL; // 将倒数第k个结点的前驱与新的链表断开
}考点一:线性表的高阶应用
一个指针就够了,原理是先遍历整个链表获得链表长度n,然后此时把链表头
和尾链接起来,在往后走(n - k) % n个节点就到达新链表的头结点前一个
点,这时断开链表即可,代码如下:考点一:线性表的高阶应用
void RightRotate(LinkList head, int k) {
if (!head) {
return; // head为空,链表不存在
}
int len = 0;
LinkList tail = head;
while (tail->next) { // 计算链表长度,并找到最后一个结点的前驱
++len;
tail = tail->next;
}
k = k % len; // 计算实际需要旋转的位置
if (k == 0) {
return; // k为0,无须旋转
}
tail->next = head->next; // 将链表首尾相连
for (int i = 0; i < len - k; ++i) { // 找到原链表倒数第k个结点的前驱
tail = tail->next;
}
head->next = tail->next; // 将原链表倒数第k个结点作为新链表的首结点
tail->next = NULL; // 将倒数第k个结点的前驱与新的链表断开
}考点一:线性表的高阶应用
单链表或者数组旋转解题总结:
(1)数组旋转:分段逆置
(2)单链表旋转:改为循环单链表,再断链【双指针策略】考点一:线性表的高阶应用
◆ 双指针策略:
• 一快,一慢
• 一早,一晚
• 一左,一右
当遇到两个单链表或者数组,实现两个单链表或者数组的比较;
当遇到一个单链表,要对单链表的不同位置进行操作或者比较;考点一:线性表的高阶应用
1、对于一个数组,将数组中负数的放左边,正数放右边。
int arra[] = { -1, 3, 9, 0, -5, -20, -3, 4, 0, 8, -12, 7 };
x 无序整数序列
负数 x 整数考点一:线性表的高阶应用
◼ base=正负(基准)
◼ j从后向前找偶数元素:前移
◼ i从前向后找奇数元素:后移
base(基准)
0 1 2 3 4 5 6 7 8 9
3 -8 2 7 -1 5 3 4 -6 -1
i j考点一:线性表的高阶应用
void Rearrange(int a[], int n) {
int low = 0, high = n - 1;
while (low < high) {
while (low < high && a[high] >= 0) { // 从右向左找第一个负数
--high;
}
while (low < high && a[low] < 0) { // 从左向右找第一个非负数
++low;
}
swap(a[low], a[high]); // 交换负数和非负数
}
}考点一:线性表的高阶应用
2、已知由n(n>=2)个正整数构成的集合A={ak|0<=k<n}, 将其划分为两个不相
交的子集A1和A2, 元素个数分别是n1和n2, A1和A2中元素之和分别为S1和S2,
设计一个尽可能高效的划分算法, 满足| n1- n2|最小且| S1- S2|最大。考点一:线性表的高阶应用
第一种解法 (暴力法): 排序考点一:线性表的高阶应用
(1)算法的基本设计思想
由题意知,将最小的(n/2) 元素放在A1中,其余的元素放在A2中,分组结
向下取整个
果即可满足题目要求。仿照快速排序的思想,基于枢轴将n个整数划分为两个子
集。根据划分后枢轴所处的位置i分别处理
①若i=(n/2) ,则分组完成,算法结束;
向下取整
②若i<(n/2) ,则枢轴及之前的所有元素均属于A1,继续对i之后的元素进
向下取整
行划分;
③若i>(n/2) ,则枢轴及之后的所有元素均属于A2,继续对i之前的元素进
向下取整
行划分;
基于该设计思想实现的算法,无须对全部元素进行全排序,其平均时间复杂度是
O(n),空间复杂度是O(1)。考点一:线性表的高阶应用
仿照快速排序的思想,基于枢轴将n个整数划分为两个子集。根据划分后枢轴
所处的位置i分别处理
i = n/2 结束
A1 i < n/2
i > n/2 A2考点一:线性表的高阶应用
// 将数组a[low...high]划分为两个子数组a[low...pos-1]和a[pos+1...high]
// 其中a[pos]是枢轴元素,a[low...pos-1]中的元素都小于等于a[pos],a[pos+1...high]
中的元素都大于等于a[pos]
// 返回枢轴元素的下标
int Partition(int a[], int low, int high) {
int pivot = a[low]; // 选取a[low]作为枢轴元素
while (low < high) {
// 从high开始向前搜索,找到第一个小于pivot的元素
while (low < high && a[high] >= pivot) {
--high;
}
a[low] = a[high];
// 从low开始向后搜索,找到第一个大于pivot的元素
while (low < high && a[low] <= pivot) {
++low;
}
a[high] = a[low];
}
a[low] = pivot;
return low;
}考点一:线性表的高阶应用
void SetPartition(Set& a, Set& a1, Set& a2) {
int low = 0, high = a.size - 1;
int pos = Partition(a.data, low, high); // pos表示一趟Partition后的枢轴位置
// 当pos等于a.size / 2时,说明已经找到了枢轴元素的位置
while (pos != a.size / 2) {
if (pos < a.size / 2) {
low = pos + 1; // 如果pos小于a.size / 2,则枢轴位置在pos的右边
} else {
high = pos - 1; // 如果pos大于a.size / 2,则枢轴位置在pos的左边
}
pos = Partition(a.data, low, high);
}
for (int i = 0; i < pos; ++i) {
a1.data[a1.size++] = a.data[i];
}
for (int i = pos; i < a.size; ++i) {
a2.data[a2.size++] = a.data[i];
}
}考点一:线性表的高阶应用
3、一个长度为 L(L ≥ 1)的升序序列S,处在第(L/2)向上取整个位置的数称为
S的中位数。例如,若序列 S1=(11,13,15,17,19),则 S1 的中位数是15,两
个序列的中位数是含它们所有元素的升序序列的中位数。例如,若 S2=
(2,4,6,8,20),则 S1 和 S2 的中位数 是 11。现在有两个等长升序序列 A 和
B,试设计一个在时间和空间两方面都尽可能高效的算法,找出两个序列 A 和 B
的中位数。要求:
(1)给出算法的基本设计思想。
(2)根据设计思想,采用 C 或 C++语言描述算法,关键之处给出注释。考点一:线性表的高阶应用
(1)算法思想:分别求出序列 A 和 B 的中位数,设为 a 和 b,求序列 A 和 B
的中位数过程如下:
①若 a=b,则 a 或 b 即为所求中位数,算法结束。(由于此线性表采用顺序存
储,因此当a=b时,a左边的元素个数都小于右边,a右边的元素必然均大于a,
b也同理。且a和b左边元素个数之和等于右边,因此a 或 b 即为所求中位数)
②若 a<b,则舍弃序列 A 中较小的一半,同时舍弃序列 B 中较大的一半,要求
舍弃的长度相等;(当a<b时,那么b的左边元素就可能>a及a右边的元素因此
中位数位于a右边范围及b左边范围之中,注意下取整,a>b同理)
③若 a>b,则舍弃序列 A 中较大的一半,同时舍弃序列 B 中较小的一半,要求
舍弃的长度相等; 在保留的两个升序序列中,重复上述过程,直到两个序列中
只含一个元素时为止,较小者即为所求的中位数。考点一:线性表的高阶应用
int median(int A[], int B[], int n) {
// 分别表示序列 A 和 B 的首位数、末位数和中位数
int s1 = 0, d1 = n - 1, m1, s2 = 1, d2 = n - 1, m2;
while (s1 != d1 || s2 != d2) {
// 当序列A或B首位数不等于末位数时即序列中不只有一个元素
m1 = (s1 + d1) / 2;
m2 = (s2 + d2) / 2; // 令m1和m2分别等于序列A、B中间位置对应的数值
if (A[m1] == B[m2])
return A[m1]; // 满足条件1A的中位数与B的中位数相等,返回此值
if (A[m1] < B[m2]) { // 满足条件 2,即A的中位数小于B的中位数
if ((s1 + d1) % 2 == 0) { // 若元素个数为奇数
s1 = m1; // 舍弃 A 中间点以前的部分且保留中间点
d2 = m2; // 舍弃 B 中间点以后的部分且保留中间点
}考点一:线性表的高阶应用
int median(int A[], int B[], int n) {
// 分别表示序列 A 和 B 的首位数、末位数和中位数
int s1 = 0, d1 = n - 1, m1, s2 = 1, d2 = n - 1, m2;
while (s1 != d1 || s2 != d2) {
else { // 元素个数为偶数
s1 = m1 + 1; // 舍弃 A 中间点及中间点以前部分
d2 = m2; // 舍弃 B 中间点以后部分且保留中间点
}
}考点一:线性表的高阶应用
int median(int A[], int B[], int n) {
else { // 满足条件 3
if ((s1 + d1) % 2 == 0) { // 若元素个数为奇数
d1 = m1; // 舍弃 A 中间点以后的部分且保留中间点
s2 = m2; // 舍弃 B 中间点以前的部分且保留中间点
} else { // 元素个数为偶数
d1 = m1 + 1; // 舍弃 A 中间点以后部分且保留中间点
s2 = m2; // 舍弃 B 中间点及中间点以前部分
}
}
}
// 两个序列中只含一个元素时,较小者即为所求的中位数
return A[s1] < B[s2] ? A[s1] : B[s2];
}考点一:线性表的高阶应用
1、已知一个带有表头结点的单链表,结点结构为:
data link
假设该链表只给出了头指针 list。在不改变链表的前提下,请设计一个尽可能
高效的算法,查找链表中 倒数第 k 个位置上的结点( k 为正整数)。若查找成功,
算法输出该结点的 data 域的值,并返回 1;否则,只 返回 0。要求:
⑴ 描述算法的基本设计思想;
⑵ 描述算法的详细实现步骤;
⑶ 根据设计思想和实现步骤,采用程序设计语言描述算法(使用 C、C++语言
实现),关键之处请给出简要注释。考点一:线性表的高阶应用
第一种解法:大力出奇迹考点一:线性表的高阶应用
(1)算法的基本设计思想
问题的关键是设计一个尽可能高效的算法, 通过链表的一趟遍历,找到倒数第
k 个结点的位置。算法的基 本设计思想是:
➢ 定义两个指针变量 p 和 q,初始时均指向头结点的下一个结点(链表的第一
个结点)。p 指针沿 链表移动;
➢ 当 p 指针移动到第 k 个结点时,q 指针开始与 p 指针同步移动;
➢ 当 p 指针移动到最后一个结点时,q 指针所指示结点为倒数第 k 个结点。
➢ 以上过程对链表仅进行一遍扫描。考点一:线性表的高阶应用
(2)算法的详细实现步骤:
① count=0,p 和 q 指向链表表头结点的下一个结点;
② 若 p 为空,转⑤;
③ 若 count 等于 k,则 q 指向下一个结点;否则,count=count+1;
④ p 指向下一个结点, 转②;
⑤ 若 count 等于 k,则查找成功,输出该结点的 data 域的值,返回1;
否则,说明 k 值超过了线性表的长度,查找失败,返回 0;
⑥ 算法结束。考点一:线性表的高阶应用
(3)算法实现:
typedef int ElemType; // 链表数据的类型定义
typedef struct LNode{ // 链表结点的结构定义
ElemType data; //结点数据
struct Lnode *link; //结点链接指针
} *LinkList;考点一:线性表的高阶应用
int PrintLastKth(LinkList h, int k) {
if (!h || k <= 0) {
return 0; // 链表为空或k不合法,返回0
}
LinkList last = h;
for (int i = 0; i < k && last; ++i) {
last = last->next;
}
if (!last) {
return 0; // 链表长度不足k,返回0
}
LinkList lastKth = h;
while (last) {
last = last->next;
lastKth = lastKth->next; // 同时移动两个指针
}
printf("%d\n", lastKth->data);
return 1;
}考点一:线性表的高阶应用
2、假定采用带头结点的单链表保存单词,当两个单词有相同的后缀时,则可共享
相同的后缀存储空间, 例如,“loading”和“being”的存储映像如下图所示。
设 str1 和 str2 分别指向两个单词所在单链表的头结点,链表结点结构[data,next],
请设计一个时间上尽 可能高效的算法,找出由 str1 和 str2 所指向两个链表共同
后缀的起始位置(如图中字符 i 所在结点的位置 p)。要求:
(1)给出算法的基本设计思想。
(2)根据设计思想,采用 C 或 C++语言描述算法,关键之处给出注释。
(3)说明你所设计算法的时间复杂度。考点一:线性表的高阶应用
(1)算法思想:顺序遍历两个链表到尾结点时,并不能保证两个链表同时到达
尾结点。这是因为两个链表的 长度不同。假设一个链表比另一个链表长 k 个结
点,我们先在长链表上遍历 k 个结点,之后同步遍历两个链表。这 样我们就能
够保证它们同时到达最后一个结点了。由于两个链表从第一个公共结点到链表
的尾结点都是重合的。所 以它们肯定同时到达第一个公共结点。于是得到算法
思路:
① 遍历两个链表求的它们的长度 L1,L2;
② 比较 L1,L2,找出较长的链表,并求 L=|L1-L2|;
③ 先遍历长链表的 L 各结点;考点一:线性表的高阶应用
公共后缀,存在后端对齐的情况:(不是一般性)
两个单链表的长度有如下关系:
Len1:
Len1 = Len2
Len2:
谁长谁先走
Len1: 谁长谁削头
Len1 < Len2
Len2:
相等一起走
Len1:
Len1 > Len2
Len2:考点一:线性表的高阶应用
//本算法实现线性时间内找到两个单链表的第一个公共结点
LinkList Search_First_Common(LinkList L1,LinkList L2){
int len1=Length(L1),len2=Length(L2);
LinkList longList,shortlist;//分别指向较长和较短的链表
if(len1>len2){
longList=L1->next;
shortlist=L2->next;
L=len1-len2;//表长之差
} else{
longList=L2->next;
shortlist=L1->next;
L=len2-len1;//表长之差
}考点一:线性表的高阶应用
//本算法实现线性时间内找到两个单链表的第一个公共结点
LinkList Search_First_Common(LinkList L1,LinkList L2){
while(L--)
longList=longList->next;
while(longList!=NULL){
if(longList==shortList)//同步寻找共同结点
return longList;
else{
longList=longList->next;
shortlist=shortlist->next;
}
}//while
return NULL;
}考点一:线性表的高阶应用
6、给定一个单链表,判断其中是否有环?
设置两个指针(fast, slow),初始值都指向头,slow每次前进一步,fast每次前
进二步,如果链表存在环,则fast必定先进入环,而slow后进入环,两个指针
必定相遇。考点一:线性表的高阶应用
bool HasCycle(LinkList h) {
for (LinkList slow = h, fast = h; fast && fast->next;) {
slow = slow->next;
fast = fast->next->next;
if (fast == slow) {
return true;
}
}
return false;
}考点一:线性表的高阶应用
题目:
①计数
① 哈希 : 0<=a <=n =>
i
②判有无
①数组逆置:对位交换法
②逆置:
②单链表逆置:头逆尾顺
①数组旋转:分段逆置
③旋转:
②单链表旋转:改为循环单链表,再断链考点一:线性表的高阶应用
①均分: 二分法(有序)
①左右指针: 数组分割 =>
③双指针: ②基准: 快速排序(无序)
①找中间位置
②快慢指针:
②判断是否有环
①单链表合并
②数组合并
③早晚指针
③后缀
④倒数第k个THANKS