欢迎各位彦祖与热巴畅游本人专栏与博客
你的三连是我最大的动力
以下图片仅代表专栏特色 [点击箭头指向的专栏名即可闪现]
专栏跑道一
➡️网络空间安全——全栈前沿技术持续深入学习
专栏跑道二
➡️ 24 Network Security -LJS
专栏跑道三
➡️ MYSQL REDIS Advance operation
专栏跑道四
➡️HCIP;H3C-SE;CCIP——LJS[华为、华三、思科高级网络]
专栏跑道五
➡️RHCE-LJS[Linux高端骚操作实战篇]
专栏跑道六
➡️数据结构与算法[考研+实际工作应用+C程序设计]
专栏跑道七
➡️RHCSA-LJS[Linux初级及进阶骚技能]
上节回顾
王道第2.3章节之线性表精题汇总四
(6)题目:试编写算法将带头节点的单链表Q就地逆置,所谓“就地”是指辅助空间复杂度为0(1)。
解题思路:
链表节点结构体 (LNode): data 用于存储节点的数据。 next 是一个指针,用于指向下一个节点。 头插法 (HeadInsert): 通过不断读取输入,将新节点插入到链表的头部。 使用 L->next 来维护链表的结构。 尾插法 (TailInsert): 持续读取输入,将新节点追加到链表末尾。 r 用于跟踪当前尾部节点,更新尾部指针。 打印函数 (Print): 遍历链表,从头节点开始输出每个节点的数据。 反转链表 (fn): 将链表中的节点顺序反转。 使用三个指针:p 用于当前节点,r 用于暂存下一个节点,L->next 用于构建反转后的链表。 主函数 (main): 创建链表头节点,调用 TailInsert 进行数据插入,然后调用 fn 反转链表,最后输出反转后的链表。
实现代码:
using namespace std; // 定义链表节点结构体 typedef struct LNode { int data; // 节点数据 struct LNode *next; // 指向下一个节点的指针 } LNode, *LinkList; // 头插法 void HeadInsert(LinkList &L) { int val = 0; // 存储输入的值 while (cin >> val) // 持续接受输入 { LNode *s = new LNode; // 创建新的节点 s->data = val; // 将输入值赋给节点数据 s->next = L->next; // 新节点指向当前链表的第一个节点 L->next = s; // 更新头指针,指向新节点 // 判断是否为输入结束 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) { cout << p->data << '\t'; // 输出节点数据 p = p->next; // 移动到下一个节点 } cout << endl; // 输出换行 } // 反转链表 void fn(LinkList &L) { LNode *p, *r; p = L->next; // 从链表的第一个节点开始 L->next = NULL; // 清空链表 // 反转链表 while (p) { r = p->next; // 暂存当前节点的下一个节点 p->next = L->next; // 当前节点的next指向新的头节点 L->next = p; // 更新链表头,指向当前节点 p = r; // 移动到下一个节点 } } int main() { LinkList L = new LNode; // 创建链表头节点 TailInsert(L); // 调用尾插法插入数据 fn(L); // 反转链表 Print(L); // 打印链表 }
(7)题目:设在一个带表头节点的 单链表Q中所有元素节点的数据值无序,试编写一个函数,删除表中所有介于给定的两个值(作为函数参数给出)之间的元素的元素(若存在) 。
解题思路:
>定义工作指针p、前驱指针q >遍历链表删除节点 链表节点结构体 (LNode): data:用于存储节点的数据。 next:指向下一个节点的指针。 头插法 (HeadInsert): 通过不断读取输入,将新节点插入到链表的头部。 使用 L->next 来维护链表的结构。 尾插法 (TailInsert): 持续读取输入,将新节点追加到链表末尾。 r 用于跟踪当前尾部节点,更新尾部指针。 打印函数 (Print): 遍历链表,从头节点开始输出每个节点的数据。 删除指定范围内的节点 (DelValue): 该函数用于删除链表中数据值在 left 和 right 之间的所有节点。 使用两个指针 p 和 pre 来维护当前节点和前驱节点,判断并删除符合条件的节点。 主函数 (main):
实现代码:
using namespace std; // 定义链表节点结构体 typedef struct LNode { int data; // 节点数据 struct LNode *next; // 指向下一个节点的指针 } LNode, *LinkList; // 头插法函数 void HeadInsert(LinkList &L) { int val = 0; // 存储输入的值 while (cin >> val) // 持续接受输入 { LNode *s = new LNode; // 创建新的节点 s->data = val; // 将输入值赋给节点数据 s->next = L->next; // 新节点指向当前链表的第一个节点 L->next = s; // 更新头指针,指向新节点 // 判断是否为输入结束 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) { cout << p->data << '\t'; // 输出节点数据 p = p->next; // 移动到下一个节点 } cout << endl; // 输出换行 } // 删除指定范围内的节点 void DelValue(LinkList &L, int left, int right) { LNode *p, *pre; // p用于当前节点,pre用于前驱节点 p = L->next; // 从链表的第一个节点开始 pre = L; // pre初始化为头节点 while (p) // 当当前节点不为空时循环 { // 检查节点数据是否在指定范围内 if (p->data > left && p->data < right) { LNode *q = p; // 暂存待删除节点 p = p->next; // 移动到下一个节点 pre->next = p; // 前驱节点的next指向当前节点的下一个节点 delete q; // 删除旧节点,释放内存 } else // 若不在指定范围内 { pre = p; // 更新前驱节点 p = p->next; // 移动到下一个节点 } } } int main() { LinkList L = new LNode; // 创建链表头节点 TailInsert(L); // 调用尾插法插入数据 DelValue(L, 3, 5); // 删除数据在3和5之间的节点 Print(L); // 打印链表 }
(8)题目:给定两个单链表Q,编写算法找出两个链表的公共结点。
解题思路:
>公共结点之后的所有结点地址均一致 >所以只需要比较结点即可 >但是需要二者从同一倒数长度开始 >所以长的链表需要先向后偏移链表长度之差 链表结构: 使用 LNode 结构体定义链表节点,包括数据和指向下一个节点的指针。 链表操作: HeadInsert: 使用头插法插入数据。 TailInsert: 使用尾插法插入数据。 Print: 输出链表中所有节点的数据。 PublicNode: 查找两个链表的公共节点,并输出该节点的数据。 主函数: 创建两个链表,构建公共节点,并调用 PublicNode 函数查找和打印公共节点的数据。
实现代码:
using namespace std; // 定义链表节点结构体 typedef struct LNode { int data; // 节点数据 struct LNode *next; // 指向下一个节点的指针 } LNode, *LinkList; // 头插法创建链表 void HeadInsert(LinkList &L) { int val = 0; // 从输入中读取值,直到遇到换行符 while (cin >> val) { LNode *s = new LNode; // 创建新节点 s->data = val; // 设置节点数据 s->next = L->next; // 新节点指向当前链表的第一个节点 L->next = s; // 更新头节点的指针指向新节点 // 检测是否为换行符 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; // p指向链表的第一个节点 while (p) { cout << p->data << '\t'; // 输出节点数据 p = p->next; // 移动到下一个节点 } cout << endl; } // 查找两个链表的公共节点 void PublicNode(LinkList &LA, LinkList &LB) { int lena = 0, lenb = 0; LNode *p = LA->next; // 计算链表A的长度 while (p) { lena++; p = p->next; } p = LB->next; // 计算链表B的长度 while (p) { lenb++; p = p->next; } LNode *longList, *shortList; int dist = 0; // 确定较长和较短的链表 if (lena > lenb) { longList = LA->next; // 链表A较长 shortList = LB->next; // 链表B较短 dist = lena - lenb; // 计算长度差 } else { longList = LB->next; // 链表B较长 shortList = LA->next; // 链表A较短 dist = lenb - lena; // 计算长度差 } // 移动较长链表的指针,使其与较短链表对齐 while (dist--) { longList = longList->next; } // 同时遍历两个链表,寻找公共节点 while (longList != NULL) { if (longList == shortList) // 找到公共节点 { cout << longList->data; // 输出公共节点数据 return; } else { longList = longList->next; // 移动到下一个节点 shortList = shortList->next; } } } int main() { LNode *p1 = new LNode; // 创建链表A的头结点 LNode *q1 = new LNode; // 创建链表B的头结点 LNode *q2 = new LNode; // 链表B的节点 LNode *q3 = new LNode; // 链表B的节点 // 公共结点 LNode *m1 = new LNode; m1->data = 99999; // 公共节点的数据 LNode *m2 = new LNode; // 公共节点的下一个节点 m1->next = m2; // 设置公共节点的下一个节点 m2->next = NULL; // 公共节点的下一节点指向NULL p1->next = m1; // 链表A连接公共节点 // 构建链表B q1->next = q2; // q1指向q2 q2->next = q3; // q2指向q3 q3->next = m1; // q3指向公共节点m1 // 查找并输出公共节点 PublicNode(p1, q1); }
(9)题目:给定一个带表头结点的单链表,设head为头指针,结点结构为(data,next),data为整型元素,next为指针,试写出算法:按递增次序输出单链表中各节点的数据元素,并释放结点所占的存储空间(要求:不允许使用数组作为辅助空间)。
解题思路:
>遍历链表找到最小值将其输入 >然后将其删除,重复该过程 >直到表为空 链表结构: 使用 LNode 结构体定义链表节点,包括数据和指向下一个节点的指针。 链表操作: HeadInsert: 头插法创建链表(未在 main 中调用)。 TailInsert: 尾插法创建链表,从标准输入读取整数,直到遇到换行符。 Print: 遍历链表,输出所有节点的数据(未在 main 中调用)。 PrintValue: 遍历链表,找到并输出每次遍历中的最小值,并删除该节点。 主函数: 创建一个链表,调用 TailInsert 函数添加数据,然后调用 PrintValue 函数输出并删除链表中的最小值。
实现代码:
using namespace std; // 定义链表节点结构体 typedef struct LNode { int data; // 节点数据 struct LNode *next; // 指向下一个节点的指针 } LNode, *LinkList; // 头插法创建链表 void HeadInsert(LinkList &L) { int val = 0; // 从输入中读取值,直到遇到换行符 while (cin >> val) { LNode *s = new LNode; // 创建新节点 s->data = val; // 设置节点数据 s->next = L->next; // 新节点指向当前链表的第一个节点 L->next = s; // 更新头节点的指针指向新节点 // 检测是否为换行符 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; // p指向链表的第一个节点 while (p) { cout << p->data << '\t'; // 输出节点数据 p = p->next; // 移动到下一个节点 } cout << endl; } // 输出链表中的最小值并删除 void PrintValue(LinkList &L) { LNode *p, *pre; LNode *minP, *minPre; // 当链表还有节点时循环 while (L->next) { p = L->next; // 从第一个节点开始 pre = L; // pre指向当前节点的前驱 minP = L->next; // 初始最小节点为第一个节点 minPre = L; // 最小节点的前驱为头节点 // 遍历链表查找最小值节点 while (p) { if (p->data < minP->data) // 找到更小的值 { minP = p; // 更新最小节点 minPre = pre; // 更新最小节点前驱 } pre = p; // 移动前驱指针 p = p->next; // 移动当前指针 } // 输出最小值 cout << minP->data << '\t'; // 删除最小值节点 LNode *q = minP; // 临时保存最小节点 minPre->next = minP->next; // 更新前驱节点的next指针 delete q; // 删除最小节点 } } int main() { LinkList L = new LNode; // 创建链表的头结点 TailInsert(L); // 调用尾插法插入数据 PrintValue(L); // 打印链表中的最小值并删除 }
(10)题目:将一个带头节点的单链表QA分解为两个带头节点的单链表A和B,使得A表中含有原表中序号为奇数的元素,而B表中含有原表中序号为偶数的元素,且保持其相对顺序不变。
解题思路:
>定义位置变量,用于指示节点序号 >然后定义两个尾指针,分别判断节点序号奇偶 >使用尾插法进行插入 链表结构: 使用 LNode 结构体定义链表节点,包括数据和指向下一个节点的指针。 链表操作: HeadInsert: 头插法创建链表(未在 main 中调用)。 TailInsert: 尾插法创建链表,从标准输入读取整数,直到遇到换行符。 Print: 遍历链表,输出所有节点的数据。 BreakList: 将原链表中的节点分成两个链表,奇数位置的节点放入链表 LA,偶数位置的节点放入链表 LB。 主函数: 创建两个链表 LA 和 LB 的头节点。 调用 TailInsert 函数添加数据到链表 LA。 调用 BreakList 函数将链表 LA 分割成两个链表 LA 和 LB。 打印两个链表的内容。
实现代码:
using namespace std; // 定义链表节点结构体 typedef struct LNode { int data; // 节点数据 struct LNode *next; // 指向下一个节点的指针 } LNode, *LinkList; // 头插法创建链表 void HeadInsert(LinkList &L) { int val = 0; while (cin >> val) // 从标准输入读取值 { LNode *s = new LNode; // 创建新节点 s->data = val; // 设置节点数据 s->next = L->next; // 新节点指向当前链表的第一个节点 L->next = s; // 更新头节点的指针指向新节点 // 检测是否为换行符 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; // p指向链表的第一个节点 while (p) // 当p不为空时 { cout << p->data << '\t'; // 输出节点数据 p = p->next; // 移动到下一个节点 } cout << endl; // 输出换行 } // 将链表分成两个链表,奇数节点进入LA,偶数节点进入LB void BreakList(LinkList &LA, LinkList &LB) { int i = 1; // 节点计数器 LNode *p, *ra, *rb; p = LA->next; // 从LA的第一个节点开始 ra = LA; // ra指向LA链表的当前末尾 rb = LB; // rb指向LB链表的当前末尾 ra->next = NULL; // 初始化LA的next为空 rb->next = NULL; // 初始化LB的next为空 // 遍历原链表 while (p) { if (i % 2 == 1) // 如果是奇数位置的节点 { ra->next = p; // 将当前节点链接到LA ra = p; // 更新ra指向当前节点 } else // 如果是偶数位置的节点 { rb->next = p; // 将当前节点链接到LB rb = p; // 更新rb指向当前节点 } p = p->next; // 移动到下一个节点 i++; // 计数器加一 } ra->next = NULL; // 结束LA链表 rb->next = NULL; // 结束LB链表 } int main() { LinkList LA = new LNode; // 创建链表LA的头节点 LinkList LB = new LNode; // 创建链表LB的头节点 TailInsert(LA); // 使用尾插法创建链表LA BreakList(LA, LB); // 将链表LA分成两个链表LA和LB Print(LA); // 打印链表LA Print(LB); // 打印链表LB }