在双向链表中插入一个节点,需要遵循以下步骤:
找到插入位置:
确定新节点`s`应该插入到哪个节点`p`之前。
更新前驱节点的指针:
将新节点`s`的前驱指针`s->prior`指向节点`p`的前驱节点`p->prior`。
更新前驱节点的后继指针:
将节点`p`的前驱节点的后继指针`p->prior->next`指向新节点`s`。
更新后继节点的指针:
将新节点`s`的后继指针`s->next`指向节点`p`。
更新前驱节点的指针:
将节点`p`的前驱指针`p->prior`指向新节点`s`。
```c
include
include
// 定义双向链表节点结构体
typedef struct DuLNode {
int data; // 数据域
struct DuLNode *next; // 指向下一个节点的指针
struct DuLNode *prior; // 指向前一个节点的指针
} DuLNode;
// 在双向链表中插入节点
Status ListInsert_DuL(DuLinkList &L, int i, int e) {
if (!(p = GetElemP_DuL(L, i))) return ERROR; // 获取插入位置的节点
if (!(s = (DuLNode *)malloc(sizeof(DuLNode)))) return ERROR; // 分配新节点空间
s->data = e; // 设置新节点的数据
s->prior = p->prior; // 新节点的前驱指向原节点的前驱
p->prior->next = s; // 原节点的前驱指向新节点
s->next = p; // 新节点的后继指向原节点
p->prior = s; // 原节点的前驱指向新节点
return OK; // 插入成功
}
// 获取双向链表中第i个节点的指针
DuLNode* GetElemP_DuL(DuLinkList &L, int i) {
DuLNode *p = L.head;
for (int j = 0; j < i - 1 && p != NULL; j++) {
p = p->next;
}
return p;
}
// 初始化双向链表
void init_f(DuLinkList &L) {
L.head = L.tail = NULL;
L.len = 0;
}
// 打印双向链表
void print_list(DuLinkList &L) {
DuLNode *p = L.head;
while (p != NULL) {
printf("%d ", p->data);
p = p->next;
}
printf("\n");
}
int main() {
DuLinkList L;
init_f(L);
ListInsert_DuL(L, 1, 10);
ListInsert_DuL(L, 2, 20);
ListInsert_DuL(L, 3, 30);
print_list(L); // 输出: 10 20 30
return 0;
}
```
在这个示例中,我们定义了一个双向链表节点结构体`DuLNode`,并实现了在双向链表中插入节点的函数`ListInsert_DuL`。通过调用`ListInsert_DuL`函数,我们可以在双向链表的指定位置插入一个新节点。