欢迎各位彦祖与热巴畅游本人专栏与博客
你的三连是我最大的动力
以下图片仅代表专栏特色 [点击箭头指向的专栏名即可闪现]
专栏跑道一
➡️网络空间安全——全栈前沿技术持续深入学习
专栏跑道二
➡️ 24 Network Security -LJS
专栏跑道三
➡️ MYSQL REDIS Advance operation
专栏跑道四
➡️HCIP；H3C-SE;CCIP——LJS[华为、华三、思科高级网络]
专栏跑道五
➡️RHCE-LJS[Linux高端骚操作实战篇]
专栏跑道六
➡️数据结构与算法[考研+实际工作应用+C程序设计]
专栏跑道七
➡️RHCSA-LJS[Linux初级及进阶骚技能]
上节回顾
目录
（16）题目：两个整数序列A= ay, a2, a3, , am和B= b, b2, b3, , b,已经存入两个单链表中,设计一个算法，判断序列 B 是否是序列 A 的连续子序列。编辑
（17）题目：设计一个算法用于判断带头结点的循环双 链表Q是否对称。编辑
（18）题目：有两个循环 单链表Q，链表头指针分别为h1和h2，编写一个函数将链表h2链接到链表h1之后，要求链接后的链表仍保持循环链表形式。
（19）题目：设有一个带头结点的循环单链表Q,其结点值均为正整数,设计一个算法,反复找出单链表中结点值最小的结点并输出,然后将该结点从中删除,直到单链表空为止，再删除表头结点。
（16）题目：两个整数序列A= ay, a2, a3, , am和B= b, b2, b3, , b,已经存入两个单链表中,设计一个算法，判断序列 B 是否是序列 A 的连续子序列。 
编辑
解题思路：
>KMP字符串比较算法
实现代码：
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; // 将新节点的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->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; // 输出换行 } // 判断链表B是否是链表A的子序列 void SubNode(LinkList &LA, LinkList &LB) { LNode *p, *q, *pre; // LA、LB的工作结点，和每次开始的比较结点 p = LA->next; // A链表的第一个节点 q = LB->next; // B链表的第一个节点 pre = p; // pre用于记录当前匹配的位置 while (p && q) // 当A和B都未遍历完时 { // 如果二者相等，指针后移继续匹配 if (p->data == q->data) { p = p->next; // A链表指针后移 q = q->next; // B链表指针后移 } // 不等，将pre开始指针向后偏移一位，q重新开始 else { pre = pre->next; // pre后移 p = pre; // p指向pre q = LB->next; // q重新指向B链表的头 } } // 检查B链表是否完全遍历 if (q) { cout << "B不是A的子序列" << endl; // 如果q没有遍历完，说明B不是A的子序列 return; } cout << "B是A的子序列" << endl; // 如果q遍历完了，说明B是A的子序列 } int main() { LinkList LA = new LNode; // 创建链表A的头节点 LinkList LB = new LNode; // 创建链表B的头节点 TailInsert(LA); // 插入链表A的元素 TailInsert(LB); // 插入链表B的元素 SubNode(LA, LB); // 判断链表B是否是链表A的子序列 }
（17）题目：设计一个算法用于判断带头结点的循环双 链表Q是否对称。 
编辑
解题思路：
>定义两个工作指针，一个从前向后扫描 >一个从后向前扫描
实现代码：
using namespace std; // 定义双向链表节点结构体 typedef struct LNode { int data; // 节点数据 struct LNode *prior; // 指向前一个节点的指针 struct LNode *next; // 指向下一个节点的指针 } LNode, *LinkList; // 尾插法 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指向新节点 s->prior = r; // 新节点的prior指向当前尾节点 r = s; // 更新r为新节点 if (cin.get() == '\n') // 如果输入回车，则结束输入 { break; } } // 建立循环关系 r->next = L; // 尾节点的next指向头节点 L->prior = r; // 头节点的prior指向尾节点 } // 遍历输出链表元素 void Print(LinkList L) { LNode *p = L->next; // 从链表第一个节点开始 while (p != L) // 当未到达头节点时 { cout << p->data << '\t'; // 输出节点数据 p = p->next; // 移动到下一个节点 } cout << endl; // 输出换行 } // 判断循环链表是否对称 void JudgeSymmetry(LinkList &L) { LNode *p, *q; // 定义工作结点，分别保存对应的前驱和后继 p = L->next; // p指向链表的第一个节点 q = L->prior; // q指向链表的最后一个节点 // 二者不重合继续判断 while (p != q) { // 偶数元素情况 if (p->next == q && p->data == q->data) { cout << "该循环链表对称" << endl; return; // 找到对称，返回 } // 奇数情况 if (p->data != q->data) { cout << "该循环链表不对称" << endl; return; // 找到不对称，返回 } else { p = p->next; // p指向下一个节点 q = q->prior; // q指向前一个节点 } } cout << "该循环链表对称" << endl; // 如果所有节点都匹配，说明对称 } int main() { LinkList L = new LNode; // 创建链表的头节点 TailInsert(L); // 尾插法插入节点 Print(L); // 打印链表 JudgeSymmetry(L); // 判断链表是否对称 }
（18）题目：有两个循环 单链表Q，链表头指针分别为h1和h2，编写一个函数将链表h2链接到链表h1之后，要求链接后的链表仍保持循环链表形式。
编辑
解题思路：
>问题关键就是找到两个链表的尾指针 >然后修改指针指向
实现代码：
using namespace std; // 定义单向链表节点结构体 typedef struct LNode { int data; // 节点数据 struct LNode *next; // 指向下一个节点的指针 } LNode, *LinkList; // 尾插法插入节点 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为新节点 if (cin.get() == '\n') // 如果输入回车，则结束输入 { break; } } r->next = L; // 尾节点的next指向头节点，形成循环链表 } // 遍历输出链表元素 void Print(LinkList L) { LNode *p = L->next; // 从链表第一个节点开始 while (p != L) // 当未到达头节点时 { cout << p->data << '\t'; // 输出节点数据 p = p->next; // 移动到下一个节点 } cout << endl; // 输出换行 } // 连接两个循环链表 LA 和 LB void ConnectList(LinkList &LA, LinkList &LB) { LNode *pa, *pb; // 定义两个工作指针 pa = LA->next; // pa 指向链表 LA 的第一个节点 pb = LB->next; // pb 指向链表 LB 的第一个节点 // 找到 LA 的尾指针 while (pa->next != LA) // 遍历直到找到尾节点 { pa = pa->next; // 移动到下一个节点 } // 找到 LB 的尾指针 while (pb->next != LB) // 遍历直到找到尾节点 { pb = pb->next; // 移动到下一个节点 } // 修改指针指向以连接两个链表 pa->next = LB->next; // 将 LA 的尾节点连接到 LB 的第一个节点 pb->next = LA; // 将 LB 的尾节点连接到 LA } int main() { LinkList LA = new LNode; // 创建链表 LA 的头节点 LinkList LB = new LNode; // 创建链表 LB 的头节点 TailInsert(LA); // 调用尾插法插入节点到 LA TailInsert(LB); // 调用尾插法插入节点到 LB ConnectList(LA, LB); // 连接两个链表 LA 和 LB Print(LA); // 打印连接后的链表 LA }
（19）题目：设有一个带头结点的循环单链表Q,其结点值均为正整数,设计一个算法,反复找出单链表中结点值最小的结点并输出,然后将该结点从中删除,直到单链表空为止，再删除表头结点。
编辑
解题思路：
>定义几个工作指针 >每次遍历找到最小值将其删除 >直到表为空
实现代码：
using namespace std; // 定义单向链表节点结构体 typedef struct LNode { int data; // 节点数据 struct LNode *next; // 指向下一个节点的指针 } LNode, *LinkList; // 尾插法插入节点 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 为新节点 // 如果输入回车，则结束输入 if (cin.get() == '\n') { break; } } r->next = L; // 尾节点的 next 指向头节点，形成循环链表 } // 遍历输出链表元素 void Print(LinkList L) { LNode *p = L->next; // 从链表第一个节点开始 while (p != L) // 当未到达头节点时 { cout << p->data << '\t'; // 输出节点数据 p = p->next; // 移动到下一个节点 } cout << endl; // 输出换行 } // 删除链表中最小值节点 void DelValue(LinkList &L) { LNode *p, *pre, *minP, *minPre; // 定义工作节点和保存最小值及其前驱的指针 // 只要链表不为空就搜索最小值 while (L->next != L) { // 重置指针 p = minP = L->next; // p 和 minP 指向链表的第一个节点 pre = minPre = L; // pre 和 minPre 初始化为头节点 // 遍历链表查找最小值 while (p != L) { if (p->data < minP->data) // 如果当前节点数据小于当前最小值 { minP = p; // 更新最小值节点 minPre = pre; // 更新最小值节点的前驱 } pre = p; // 移动前驱指针 p = p->next; // 移动到下一个节点 } cout << minP->data << '\t'; // 输出最小值 minPre->next = minP->next; // 删除最小值节点 delete minP; // 释放内存 } delete L; // 删除头节点 } int main() { LinkList L = new LNode; // 创建链表的头节点 TailInsert(L); // 调用尾插法插入节点 DelValue(L); // 删除链表中的所有最小值节点 }
（20）题目：设头指针为L的带有表头结点的非循环双向链表,其每个结点中除有pred(前驱指针)、data（数据）和 next（后继指针）城外，还有一个访问频度域 freq。在链表被启用前,其值均初始化为零。每当在链表中进行一次Locate (L,x)运算时,令元素值为x的结点中freq域的值增1,并使此链表中结点保持按访问频度非增（递减)的顺序排列,同时最近访问的结点排在频度相同的结点前面,以使使频繁访问的结点总是靠近表头。试编写符合上述要求的 Locate (L,x)运算的算法，该运算为函数过程，返回找到结点的地址,类型为指针型。
编辑
解题思路：
>双链表的插入、删除
实现代码：
using namespace std; // 定义链表节点结构 typedef struct LNode { int data; // 节点数据 int freq = 0; // 节点频率，默认值为0 struct LNode *pred; // 前驱指针 struct LNode *next; // 后继指针 } LNode, *LinkList; // 尾插法插入节点 void TailInsert(LinkList &L) { int val = 0; // 用于存储输入值 LNode *r = L; // r指向链表的最后节点 while (cin >> val) // 循环读取输入值 { LNode *s = new LNode; // 创建新节点 s->data = val; // 设置节点数据 r->next = s; // 将新节点链接到链表 r = s; // 更新r指向新节点 if (cin.get() == '\n') // 如果读取到换行符，结束输入 { break; } } r->next = L; // 形成循环链表 } // 遍历输出链表元素 void Print(LinkList L) { LNode *p = L->next; // 从第一个有效节点开始 while (p != L) // 当未回到头节点时 { cout << p->data << '\t'; // 输出节点数据 p = p->next; // 移动到下一个节点 } cout << endl; // 输出换行 } // 定位节点并更新频率 LNode *Locate(LinkList &L, int x) { LNode *p, *q; p = L->next; // 从第一个有效节点开始 while (p && p->data != x) // 查找数据为x的节点 { p = p->next; } if (!p) // 如果没有找到，返回NULL { return NULL; } else { p->freq++; // 找到节点，频率加1 // 如果该节点在链表头或前驱频率更大，直接返回 if (p->pred == L || p->pred->freq > p->freq) { return p; } // 断开p节点与其前驱的链接 if (p->next != NULL) { p->next->pred = p->pred; } p->pred->next = p->next; // 在前驱节点中寻找合适的位置插入p节点 q = p->pred; while (q != L && q->freq <= p->freq) { q = q->pred; } // 更新p的前驱和后继指针 p->next = q->next; if (q->next != NULL) { q->next->pred = p; } p->pred = q; q->next = p; } return p; // 返回更新后的节点 } int main() { LinkList L = new LNode; // 创建链表头节点 TailInsert(L); // 尾插法插入节点 LNode *p = Locate(L, 3); // 定位值为3的节点 }
