当前位置: 首页> 房产> 家装 > 【数据结构与算法】双向链表中指定值前后插入新元素的算法 C++实现(双向链表+循环)

【数据结构与算法】双向链表中指定值前后插入新元素的算法 C++实现(双向链表+循环)

时间:2025/7/10 3:57:28来源:https://blog.csdn.net/qq_34988204/article/details/136976840 浏览次数:0次

分别在带头结点的双链表中的第一个值为x的结点之前、之后插入元素值为y的结点,分别编写各自的算法。


思路

insertBefore函数用于在双链表中指定值的结点之前插入新的元素值。它通过遍历双链表找到对应的结点,然后调用listInsert函数完成插入操作。首先获取双链表的第一个结点,然后使用循环遍历整个双链表,直到找到值为x的结点或遍历结束。如果找到了值为x的结点,就调用listInsert函数,在该位置插入新的元素值y。如果未找到值为x的结点,则返回错误。

insertAfter函数的操作类似,不同之处在于在指定值的结点之后插入新的元素值。它也是通过遍历双链表找到对应的结点,然后调用listInsert函数完成插入操作。与insertBefore函数类似,它首先获取双链表的第一个结点,然后使用循环遍历整个双链表,直到找到值为x的结点或遍历结束。如果找到了值为x的结点,就调用listInsert函数,在该位置的后面插入新的元素值y。如果未找到值为x的结点,则返回错误。

时间复杂度都为O(n),因为在最坏情况下,需要遍历整个双链表来找到指定的结点。空间复杂度取决于双链表的长度,为O(n)。


代码

#include <algorithm>
#include <iostream>
#define AUTHOR "HEX9CF"
using namespace std;
using Status = int;
using ElemType = int;const int N = 1e6 + 7;
const int TRUE = 1;
const int FALSE = 0;
const int OK = 1;
const int ERROR = 0;
const int INFEASIBLE = -1;
const int OVERFLOW = -2;int n;
ElemType a[N];struct ListNode {ElemType data;ListNode *prior, *next;
};
using LinkList = ListNode *;Status initList(LinkList &L) {L = (ListNode *)malloc(sizeof(ListNode));if (!L) {return ERROR;}L->prior = NULL;L->next = NULL;return OK;
}Status listInsert(LinkList &L, int pos, ElemType e) {ListNode *p = L;for (int i = 0; p && i < pos; i++) {p = p->next;}if (!p) {return ERROR;}ListNode *newNode = (ListNode *)malloc(sizeof(ListNode));if (!newNode) {return ERROR;}newNode->data = e;newNode->prior = p;newNode->next = p->next;p->next = newNode;if (newNode->next) {newNode->next->prior = newNode;}return OK;
}ElemType getElem(LinkList L, int pos) {ListNode *p = L->next;for (int i = 0; p && i < pos; i++) {p = p->next;}if (!p) {return NULL;}return p->data;
}Status insertBefore(LinkList &L, int x, int y) {ListNode *p = L->next;int i = 0;while (p && p->data != x) {p = p->next;i++;}if (!p) {return ERROR;}return listInsert(L, i, y);
}Status insertAfter(LinkList &L, int x, int y) {ListNode *p = L->next;int i = 0;while (p && p->data != x) {p = p->next;i++;}if (!p) {return ERROR;}return listInsert(L, i + 1, y);
}int main() {cin >> n;for (int i = 0; i < n; i++) {cin >> a[i];}LinkList L;initList(L);for (int i = 0; i < n; i++) {listInsert(L, i, a[i]);}for (int i = 0; i < n; i++) {cout << getElem(L, i) << " ";}cout << "\n";n += insertBefore(L, 1, 2);n += insertBefore(L, 3, 4);for (int i = 0; i < n; i++) {cout << getElem(L, i) << " ";}cout << "\n";n += insertAfter(L, 7, 6);n += insertAfter(L, 9, 8);for (int i = 0; i < n; i++) {cout << getElem(L, i) << " ";}cout << "\n";return 0;
}
关键字:【数据结构与算法】双向链表中指定值前后插入新元素的算法 C++实现(双向链表+循环)

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: