在双向链表中给定节点之前插入一个节点
问题描述:
我试图在给定节点之前插入一个节点。但我无法获得所需的输出。在双向链表中给定节点之前插入一个节点
#include<stdio.h>
#include<stdlib.h>
struct node{
int data;
struct node* prev;
struct node* next;
};
void insert_beg(struct node** head, int new_data){
struct node* temp = (struct node*)malloc(sizeof(struct node));
temp->data = new_data;
if(*head == NULL){
temp->next = *head;
temp->prev = NULL;
*head = temp;
}
else{
temp->next = *head;
(*head)->prev = temp;
*head = temp;
}
}
void insert_before(struct node* next_node,int new_data){
struct node* temp = (struct node*)malloc(sizeof(struct node));
temp->data = new_data;
if(next_node == NULL)
printf("Invalid!!!!");
temp->prev = next_node->prev;
temp->next = next_node;
next_node->prev = temp;
if(temp->prev!=NULL)
temp->prev->next = temp;
}
void printList(struct node* head){
if(head == NULL)
printf("The list is empty\n");
else
{
while(head!=NULL){
printf("%d\n",head->data);
head = head->next;
}
}
}
int main(){
struct node* head = NULL;
printList(head);
insert_beg(&head,10);
insert_beg(&head,20);
insert_before(head,70);
insert_beg(&head,30);
printList(head);
}
在这里,我试图插入的节点(与数据= 70)前20
输出:30,20,10
预期输出:30,70,20, 10
答
当您拨打insert_before
时,如果给定节点是头部,则新节点将成为新头部。所以你需要通过head
的地址来修改它。
你现在看起来是这样的:
head
|
v
------ ------ ------
- 30 - ---> - 20 - ---> - 10 -
------ <--- ------ <--- ------
^
------ |
- 70 - ---------|
------
为了解决这个问题,包括head
在参数insert_before
地址。
void insert_before(struct node **head, struct node *next_node, int new_data){
struct node* temp = malloc(sizeof(struct node)); // don't cast the return value of malloc
temp->data = new_data;
if(next_node == NULL)
printf("Invalid!!!!");
temp->prev = next_node->prev;
temp->next = next_node;
next_node->prev = temp;
if(temp->prev!=NULL) {
temp->prev->next = temp;
} else {
*head = temp;
}
}
然后调用它像这样:
insert_before(&head,head,70);
答
你正在做right.But你缺少一个东西在insert_before
如果传递的参数next_node
是头,那么你将被插入头节点之前的一切。因此,您必须将此新添加的节点设为head
。
+0
但是,如果传递的参数不是头呢? – oldDoctor
只读'main',但我没有看到如何在列表中的第一项之前插入而不通过地址('&head'),因为'head'变量需要更新。 – user3386109