欢迎各位彦祖与热巴畅游本人专栏与博客
你的三连是我最大的动力
以下图片仅代表专栏特色 [点击箭头指向的专栏名即可闪现]
专栏跑道一
➡️网络空间安全——全栈前沿技术持续深入学习
专栏跑道二
➡️ 24 Network Security -LJS
专栏跑道三
➡️ MYSQL REDIS Advance operation
专栏跑道四
➡️HCIP;H3C-SE;CCIP——LJS[华为、华三、思科高级网络]
专栏跑道五
➡️RHCE-LJS[Linux高端骚操作实战篇]
专栏跑道六
➡️数据结构与算法[考研+实际工作应用+C程序设计]
专栏跑道七
➡️RHCSA-LJS[Linux初级及进阶骚技能]
上节回顾
(1)题目:设计一个递归算法,删除不带头结点的单链表L中所有值为x的结点。
解题思路:
>利用递归,不断将节点的下个节点传入函数 >每个函数执行对应删除操作
实现代码:
using namespace std; // 定义链表节点结构体 typedef struct LNode { int data; // 节点数据 struct LNode *next; // 指向下一个节点的指针 } LNode, *LinkList; // LinkList 是 LNode 指针类型的别名 // 头插法构建链表 void HeadInsert(LinkList &L) { int val = 0; while (cin >> val) // 从标准输入读取数据 { LNode *s = new LNode; // 创建新节点 s->data = val; // 设置节点数据 s->next = L->next; // 新节点的next指向当前头节点的下一个节点 L->next = s; // 头指针的next指向新节点 // 如果读取到换行符,结束输入 if (cin.get() == '\n') { break; } } } // 尾插法构建链表 void TailInsert(LinkList &L) { int val = 0; LNode *r = L; // r为指向链表最后一个节点的指针 while (cin >> val) // 从标准输入读取数据 { LNode *s = new LNode; // 创建新节点 s->data = val; // 设置节点数据 r->next = s; // 尾节点的next指向新节点 r = s; // r更新为新节点 r->next = NULL; // 新节点的next设为nullptr // 如果读取到换行符,结束输入 if (cin.get() == '\n') { break; } } } // 遍历输出链表元素 void Print(LinkList L) { LNode *p = L->next; // 从头节点的下一个节点开始遍历 while (p) // 当p不为空时 { cout << p->data << '\t'; // 输出节点数据 p = p->next; // 移动到下一个节点 } cout << endl; // 输出换行 } // 删除链表中所有值为x的节点 void DelValue(LinkList &L, int x) { if (L == NULL) // 如果链表为空,直接返回 { return; } LNode *p; // 如果当前节点的值等于x if (L->data == x) { p = L; // 将当前节点赋值给p L = L->next; // 将链表的头指针指向下一个节点 delete p; // 删除当前节点 DelValue(L, x); // 递归调用,继续删除后面的节点 } else { DelValue(L->next, x); // 否则,递归到下一个节点 } } int main() { LinkList L = new LNode; // 创建链表头节点 L->next = NULL; // 初始化头节点的next指针为NULL TailInsert(L); // 调用尾插法插入数据 DelValue(L, 2); // 删除值为2的节点 Print(L); // 打印链表 }
编辑
(2)题目:在带头结点的单链表L中,删除所有值为x的结点,并释放其空间,假设值为x的结点不唯一,试编写算法以实现上述操作。
解题思路:
>定义工作指针p、前驱指针pre >遍历链表,删除元素
实现代码:
using namespace std; // 定义链表节点结构体 typedef struct LNode { int data; // 节点数据 struct LNode *next; // 指向下一个节点的指针 } LNode, *LinkList; // LinkList 是 LNode 指针类型的别名 // 头插法构建链表 void HeadInsert(LinkList &L) { int val = 0; // 用于存储输入值 while (cin >> val) // 从标准输入读取数据 { LNode *s = new LNode; // 创建新节点 s->data = val; // 设置节点数据 s->next = L->next; // 新节点的next指向当前头节点的下一个节点 L->next = s; // 头指针的next指向新节点 // 如果读取到换行符,结束输入 if (cin.get() == '\n') { break; } } } // 尾插法构建链表 void TailInsert(LinkList &L) { int val = 0; // 用于存储输入值 LNode *r = L; // r指向链表的尾节点 while (cin >> val) // 从标准输入读取数据 { LNode *s = new LNode; // 创建新节点 s->data = val; // 设置节点数据 r->next = s; // 尾节点的next指向新节点 r = s; // r更新为新节点 r->next = NULL; // 新节点的next设为NULL // 如果读取到换行符,结束输入 if (cin.get() == '\n') { break; } } } // 遍历输出链表元素 void Print(LinkList L) { LNode *p = L->next; // 从头节点的下一个节点开始遍历 while (p) // 当p不为空时 { cout << p->data << '\t'; // 输出节点数据 p = p->next; // 移动到下一个节点 } cout << endl; // 输出换行 } // 删除链表中所有值为x的节点 void DelValue(LinkList &L, int x) { LNode *p, *pre; // p指向当前节点,pre指向前一个节点 p = L->next; // 从头节点的下一个节点开始 pre = L; // pre初始化为头节点 while (p) // 当p不为空时 { if (p->data == x) // 如果当前节点的值等于x { LNode *q = p; // 将当前节点赋值给q pre->next = p->next; // 前一个节点的next指向当前节点的下一个节点 p = p->next; // p移动到下一个节点 delete q; // 删除当前节点 } else // 当前节点的值不等于x { pre = p; // 更新前一个节点为当前节点 p = p->next; // p移动到下一个节点 } } } int main() { LinkList L = new LNode; // 创建链表头节点 L->next = NULL; // 初始化头节点的next指针为NULL TailInsert(L); // 调用尾插法插入数据 DelValue(L, 2); // 删除值为2的节点 Print(L); // 打印链表 }
(3)题目:设L 为带头结点的单链表,编写算法实现从尾到头反向输出每个结点的值。
解题思路:
>利用递归栈进行实现 >栈的特性是后进先出 >所以可以采用递归实现
实现代码:
using namespace std; // 定义链表节点结构体 typedef struct LNode { int data; // 节点数据 struct LNode *next; // 指向下一个节点的指针 } LNode, *LinkList; // LinkList 是 LNode 指针类型的别名 // 头插法构建链表 void HeadInsert(LinkList &L) { int val = 0; // 用于存储输入值 while (cin >> val) // 从标准输入读取数据 { LNode *s = new LNode; // 创建新节点 s->data = val; // 设置节点数据 s->next = L->next; // 新节点的next指向当前头节点的下一个节点 L->next = s; // 头指针的next指向新节点 // 如果读取到换行符,结束输入 if (cin.get() == '\n') { break; } } } // 尾插法构建链表 void TailInsert(LinkList &L) { int val = 0; // 用于存储输入值 LNode *r = L; // r指向链表的尾节点 while (cin >> val) // 从标准输入读取数据 { LNode *s = new LNode; // 创建新节点 s->data = val; // 设置节点数据 r->next = s; // 尾节点的next指向新节点 r = s; // r更新为新节点 r->next = NULL; // 新节点的next设为NULL // 如果读取到换行符,结束输入 if (cin.get() == '\n') { break; } } } // 遍历输出链表元素 void Print(LinkList L) { LNode *p = L->next; // 从头节点的下一个节点开始遍历 while (p) // 当p不为空时 { cout << p->data << '\t'; // 输出节点数据 p = p->next; // 移动到下一个节点 } cout << endl; // 输出换行 } // 递归逆序打印链表 void ReversePrint(LinkList &L) { if (L == NULL) // 如果链表为空,直接返回 { return; } ReversePrint(L->next); // 递归调用,先打印后面的节点 cout << L->data << '\t'; // 打印当前节点的数据 } int main() { LinkList L = new LNode; // 创建链表头节点 L->next = NULL; // 初始化头节点的next指针为NULL TailInsert(L); // 调用尾插法插入数据 // 逆序打印链表的元素 ReversePrint(L->next); }
(4)题目:试编写在带头结点的单链表L 中删除一个最小值结点的高效算法(假设最小值结点是唯一的)。
解题思路:
>定义工作指针p、pre >定义用于保存最小值的指针minP、minPre >遍历链表找到最小值,用指针标记 >最后修改指针将其删除释放空间
实现代码:
using namespace std; // 定义链表节点结构体 typedef struct LNode { int data; // 节点数据 struct LNode *next; // 指向下一个节点的指针 } LNode, *LinkList; // LinkList 是 LNode 指针类型的别名 // 头插法构建链表 void HeadInsert(LinkList &L) { int val = 0; // 用于存储输入值 while (cin >> val) // 从标准输入读取数据 { LNode *s = new LNode; // 创建新节点 s->data = val; // 设置节点数据 s->next = L->next; // 新节点的next指向当前头节点的下一个节点 L->next = s; // 头指针的next指向新节点 // 如果读取到换行符,结束输入 if (cin.get() == '\n') { break; } } } // 尾插法构建链表 void TailInsert(LinkList &L) { int val = 0; // 用于存储输入值 LNode *r = L; // r指向链表的尾节点 while (cin >> val) // 从标准输入读取数据 { LNode *s = new LNode; // 创建新节点 s->data = val; // 设置节点数据 r->next = s; // 尾节点的next指向新节点 r = s; // r更新为新节点 r->next = NULL; // 新节点的next设为NULL // 如果读取到换行符,结束输入 if (cin.get() == '\n') { break; } } } // 遍历输出链表元素 void Print(LinkList L) { LNode *p = L->next; // 从头节点的下一个节点开始遍历 while (p) // 当p不为空时 { cout << p->data << '\t'; // 输出节点数据 p = p->next; // 移动到下一个节点 } cout << endl; // 输出换行 } // 删除链表中的最小值节点 void DelMinValue(LinkList &L) { // 工作节点 LNode *p, *pre; // p是当前节点,pre是前驱节点 p = L->next; // 从链表的第一个节点开始 pre = L; // 前驱节点初始化为头节点 // 用于保存最值的节点 LNode *minP, *minPre; // minP是当前最小值节点,minPre是其前驱节点 minP = p; // 初始化为第一个节点 minPre = pre; // 初始化为头节点 // 遍历链表查找最小值节点 while (p) { if (p->data < minP->data) // 找到更小的值 { minPre = pre; // 更新前驱节点 minP = p; // 更新最小值节点 } pre = p; // 前驱节点向后移动 p = p->next; // 当前节点向后移动 } // 删除最小值节点 minPre->next = minP->next; // 将前驱节点的next指向最小值节点的下一个节点 delete minP; // 释放内存 } int main() { LinkList L = new LNode; // 创建链表头节点 L->next = NULL; // 初始化头节点的next指针为NULL TailInsert(L); // 调用尾插法插入数据 DelMinValue(L); // 删除链表中的最小值节点 Print(L); // 打印修改后的链表 }
(5)题目:试编写算法将带头结点的单链表就地逆置,所谓“就地”是指辅助空间复杂度为 O(1)。
解题思路:
>头插法
实现代码:
using namespace std; // 定义链表节点结构体 typedef struct LNode { int data; // 节点数据 struct LNode *next; // 指向下一个节点的指针 } LNode, *LinkList; // LinkList 是 LNode 指针类型的别名 // 头插法构建链表 void HeadInsert(LinkList &L) { int val = 0; // 用于存储输入值 while (cin >> val) // 从标准输入读取数据 { LNode *s = new LNode; // 创建新节点 s->data = val; // 设置节点数据 s->next = L->next; // 新节点的next指向当前头节点的下一个节点 L->next = s; // 头指针的next指向新节点 // 如果读取到换行符,结束输入 if (cin.get() == '\n') { break; } } } // 尾插法构建链表 void TailInsert(LinkList &L) { int val = 0; // 用于存储输入值 LNode *r = L; // r指向链表的尾节点 while (cin >> val) // 从标准输入读取数据 { LNode *s = new LNode; // 创建新节点 s->data = val; // 设置节点数据 r->next = s; // 尾节点的next指向新节点 r = s; // r更新为新节点 r->next = NULL; // 新节点的next设为NULL // 如果读取到换行符,结束输入 if (cin.get() == '\n') { break; } } } // 遍历输出链表元素 void Print(LinkList L) { LNode *p = L->next; // 从头节点的下一个节点开始遍历 while (p) // 当p不为空时 { cout << p->data << '\t'; // 输出节点数据 p = p->next; // 移动到下一个节点 } cout << endl; // 输出换行 } // 反转链表 void fn(LinkList &L) { LNode *p, *r; // p用于遍历链表,r用于保存当前节点的下一个节点 p = L->next; // 从头节点的下一个节点开始 L->next = NULL; // 初始化头节点的next为NULL,准备反转 // 反转链表 while (p) { r = p->next; // 保存当前节点的下一个节点 p->next = L->next; // 将当前节点的next指向当前头节点的next L->next = p; // 更新头节点的next为当前节点 p = r; // 移动到下一个节点 } } int main() { LinkList L = new LNode; // 创建链表头节点 TailInsert(L); // 调用尾插法插入数据 fn(L); // 反转链表 Print(L); // 打印反转后的链表 }