C语言设计一个算法,在双链表中值为y的结点前面插入一个值为x的新结点。即使值为x的新结点成为值为y的结点的前驱结点。
时间: 2024-03-27 19:36:16 浏览: 105
C语言算法设计
可以按照以下步骤设计算法:
1. 新建一个双链表节点,将节点的值设置为x。
2. 遍历双链表,找到值为y的节点。
3. 如果找到了值为y的节点,将新建的节点插入到该节点的前面即可。
4. 如果没有找到值为y的节点,则将新建的节点插入到双链表的末尾。
以下是C语言的代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct node {
int data;
struct node *prev;
struct node *next;
} Node;
// 创建新节点
Node *create_node(int data) {
Node *new_node = (Node *)malloc(sizeof(Node));
new_node->data = data;
new_node->prev = NULL;
new_node->next = NULL;
return new_node;
}
// 在双链表中插入新节点
void insert_node(Node *head, int x, int y) {
Node *new_node = create_node(x);
Node *cur = head;
while (cur != NULL) {
if (cur->data == y) {
new_node->prev = cur->prev;
new_node->next = cur;
cur->prev = new_node;
if (new_node->prev != NULL) {
new_node->prev->next = new_node;
}
break;
}
cur = cur->next;
}
if (cur == NULL) {
// 没有找到值为y的节点,将新节点插入到双链表末尾
cur = head;
while (cur->next != NULL) {
cur = cur->next;
}
new_node->prev = cur;
cur->next = new_node;
}
}
// 打印双链表
void print_list(Node *head) {
Node *cur = head;
while (cur != NULL) {
printf("%d ", cur->data);
cur = cur->next;
}
printf("\n");
}
int main() {
Node *head = create_node(1);
Node *node2 = create_node(2);
Node *node3 = create_node(3);
head->next = node2;
node2->prev = head;
node2->next = node3;
node3->prev = node2;
print_list(head);
insert_node(head, 4, 3);
print_list(head);
insert_node(head, 5, 6);
print_list(head);
return 0;
}
```
在上面的代码中,我们首先定义了一个 `Node` 结构体表示双链表的节点,然后实现了 `create_node` 函数用于创建新的节点,实现了 `insert_node` 函数用于在双链表中插入新节点,实现了 `print_list` 函数用于打印双链表的值。
在 `insert_node` 函数中,我们首先创建一个新的节点,然后遍历双链表找到值为y的节点。如果找到了值为y的节点,则将新节点插入到该节点的前面;否则将新节点插入到双链表的末尾。在插入新节点时,我们需要注意调整前驱和后继节点的指针。
最后,在 `main` 函数中我们创建了一个含有三个节点的双链表,并测试了 `insert_node` 函数的功能。
阅读全文