从 C 语言中的链表中删除元素

Question

我正在尝试编写一个函数，该函数正在从链表中删除特定元素，但是当我到达该元素时，它因分割错误而崩溃。 这是我代码的一部分

typedef struct dlist_t {
int data;
struct dlist_t *prev, *next;
} dlist_t;
typedef struct list_t {
dlist_t *head, *tail;
} list_t;
int delElement(list_t *list, int elem) {
while (list) {
if ((list->head)->data == elem) {
list->head->next = list->head->prev;
list->head->prev = list->head->next;
free(list);
return 1;
}
list = list->head->next;
}
return 0;
}

Answer 1

您的函数定义没有意义。例如在此赋值语句中

list = list->head->next;

在赋值的左侧(类型为list_t(和赋值的右侧(类型为dlist_t(中存在不同类型的使用对象。

或者这个电话

free(list);

尝试释放列表，而不仅仅是其一个节点。等等。

该函数可以如下所示，如下面的演示程序所示。

#include <stdio.h>
#include <stdlib.h>
typedef struct dlist_t 
{
int data;
struct dlist_t *prev, *next;
} dlist_t;
typedef struct list_t 
{
dlist_t *head, *tail;
} list_t;
int delElement( list_t* list, int elem )
{
dlist_t **current = &list->head;
while ( *current != NULL && ( *current )->data != elem )
{
current = &( *current )->next;
}
int success = *current != NULL;
if ( success )
{
dlist_t *tmp = *current;
if ( ( *current )->next != NULL )
{
( *current )->next->prev  = ( *current )->prev;
}
else
{
list->tail = ( *current )->prev;
}
*current = ( *current )->next; 
free( tmp );
}
return success;
}
int pushFront( list_t *list, int elem )
{
dlist_t *new_node = malloc( sizeof( dlist_t ) );
int success = new_node != NULL;
if ( success )
{
new_node->next = list->head;
new_node->prev = NULL;
new_node->data = elem;
if ( list->head != NULL )
{
list->head->prev = new_node;
}
else
{
list->tail = new_node;
}
list->head = new_node;
}
return success;
}
int pushBack( list_t *list, int elem )
{
dlist_t *new_node = malloc( sizeof( dlist_t ) );
int success = new_node != NULL;
if ( success )
{
new_node->prev = list->tail;
new_node->next = NULL;
new_node->data = elem;
if ( list->tail != NULL )
{
list->tail->next = new_node;
}
else
{
list->head = new_node;
}
list->tail = new_node;
}
return success;
}
void printList( list_t *list )
{
for ( dlist_t *current = list->head; current != NULL; current = current->next )
{
printf( "%d -> ", current->data );
}
puts( "null" );
}

void printReverseList( list_t *list )
{
for ( dlist_t *current = list->tail; current != NULL; current = current->prev )
{
printf( "%d -> ", current->data );
}
puts( "null" );
}
int main(void) 
{
list_t list = { .head = NULL, .tail = NULL };
const int N = 10;
for ( int i = 0; i < N; i++ )
{
if ( i % 2 == 0 ) pushFront( &list, N / 2 - i / 2 - 1 );
else pushBack( &list, N / 2 + i / 2 );
}
printList( &list );
printReverseList( &list );
putchar( 'n' );
for ( size_t i = 0; i < N; i++ )
{
if ( i % 2 == 0 ) delElement( &list, i / 2 );
else delElement( &list, N - i / 2 - 1 );
printList( &list );
printReverseList( &list );
putchar( 'n' );
}       
return 0;
}

程序输出为

0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> null
9 -> 8 -> 7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1 -> 0 -> null
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> null
9 -> 8 -> 7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1 -> null
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> null
8 -> 7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1 -> null
2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> null
8 -> 7 -> 6 -> 5 -> 4 -> 3 -> 2 -> null
2 -> 3 -> 4 -> 5 -> 6 -> 7 -> null
7 -> 6 -> 5 -> 4 -> 3 -> 2 -> null
3 -> 4 -> 5 -> 6 -> 7 -> null
7 -> 6 -> 5 -> 4 -> 3 -> null
3 -> 4 -> 5 -> 6 -> null
6 -> 5 -> 4 -> 3 -> null
4 -> 5 -> 6 -> null
6 -> 5 -> 4 -> null
4 -> 5 -> null
5 -> 4 -> null
5 -> null
5 -> null
null
null

玩程序并播放调查它。

不要忘记为自己编写释放列表中所有已分配节点的函数。

Answer 2

我还不太确定是什么导致了你的崩溃，但在这里我有一个应该可以工作的代码示例。 结构定义：

typedef int item_type;
typedef struct _list* list;
struct node {
item_type data;
struct node *next,*prev;
};
struct _list {
struct node* head;
struct node* tail;
int size;
};

"元素"删除功能

void list_del(list l,item_type data) {
if (list->size ==0) {
abort();
}
int i=0;
struct node* head = l->head;
while(i<list->size){
if(head->data==data){
head->prev = head->next;
l->size -= 1;
free(head);
return;
}else{
head=head->next;
}
}
}

"item_type"它是一个 typedef，如果你有很多函数并且你不应该太关心类型。在我们的示例中，如您所愿，键入 int

Answer 3

不用担心，只需尝试一下这段代码。这是最简单的实现和删除链表中的节点，如果您遇到任何问题，请随时询问.

#include <stdio.h>
#include <stdlib.h>
struct Node
{
int data;
struct Node *next;
}*first=NULL;
void create(int A[],int n)
{
int i;
struct Node *t,*last;
first=(struct Node *)malloc(sizeof(struct Node));
first->data=A[0];
first->next=NULL;
last=first;
for(i=1;i<n;i++)
{
t=(struct Node*)malloc(sizeof(struct Node));
t->data=A[i];
t->next=NULL;
last->next=t;
last=t;
}
}
void Display(struct Node *p)
{
while(p!=NULL)
{
printf("%d ",p->data);
p=p->next;
}
}
void RDisplay(struct Node *p)
{
if(p!=NULL)
{
RDisplay(p->next);
printf("%d ",p->data);
}
}
int Delete(struct Node *p,int index)
{
struct Node *q=NULL;
int x=-1,i;
if(index < 1 || index > count(p))
return -1;
if(index==1)
{
q=first;
x=first->data;
first=first->next;
free(q);
return x;
}
else
{
for(i=0;i<index-1;i++)
{
q=p;
p=p->next;
}
q->next=p->next;
x=p->data;
free(p);
return x;
}

}
int main()
{
int A[]={10,20,30,40,50};
create(A,5);
printf(“%dn",Delete(first),2);
Display(first);
return 0;
}

所以首先我们使用malloc函数创建了链表。我们创建了一个带有变量的结构，它将构建链表，即"数据">，并创建了结构类型的指针。

然后我们创建了一个函数名称"create"来创建我们的第一个节点。并根据它插入值.

然后，如您所见，我们g=已使用for循环来加快创建链接列表的过程，直到n的值。

然后为了显示链表，我们创建了函数名称"Display">，如果p！=NULL即包含地址的节点最后一列，我们使用 for 循环打印该节点的值/数据。

然后对于删除，我们使用函数名称"删除">：

第一步：我们需要一个指向第一个节点的指针"p"吗？

第二步：现在首先移动到下一个节点。

第三步：现在将已删除节点的值存储在新变量"x"中。

第四步：删除p

其余代码用于使用两个指针从特定位置删除节点，一个指针用于上一个节点，下一个指针用于当前节点。

只需尝试一下或与您的代码交叉检查您出错的地方。