c - 从双向链表中删除节点会导致分段错误 - C
问题描述
我编写了一个程序,可以将 char 字符添加到双向链表的开头。现在,一旦我有了这个列表,我的程序的目的就是从列表中完全删除某些 char 字符。例如(仅出于代表性目的使用大括号):如果列表由{ a, b, b, a, c }组成,那么我的程序可以从列表中删除所有“b”以使其成为{ a, a, c} . 此外,如果我的列表是{b, a, c, a}或{a, c, a, b}并且如果我想删除“b”,那么程序在这两种情况下都可以正常工作并给我{a, c,一个}。
但是有很多问题(对于所有情况,假设我想删除“b”):
- 如果我的列表是{b,a,b,a,c}(“b”在前面和中间某处),我会遇到分段错误(我认为这与在 while 循环中使用光标有关,但我没有不知道为什么以及如何解决它)
- 如果我的列表是{a, b, b, a, c, b}(中间最后是“b”),那么输出会给我奇怪的符号(我假设它是内存错误,不知道为什么)
这是我正在使用的代码:
#include<stdio.h>
#include<stdlib.h>
struct list
{
int data;
struct list* next;
struct list* prev;
};
struct list* head; // global variable - pointer to head node of list.
struct list* last; // global variable - pointer to last node of list
//Creates a new list and returns pointer to it.
struct list* GetNewNode(char x)
{
struct list* newNode
= malloc(sizeof(struct list));
newNode->data = x;
newNode->prev = NULL;
newNode->next = NULL;
return newNode;
}
//Inserts a list at head of doubly linked list
void InsertAtHead(char x)
{
struct list* newNode = GetNewNode(x);
if(head == NULL)
{
head = newNode;
return;
}
head->prev = newNode;
newNode->next = head;
head = newNode;
struct list* temp = head;
while (temp->next != NULL) temp = temp->next;
last = temp;
}
void remove_element (char character)
{
struct list * cursor, *previous, *store_el;
//int boolean = 0;
if (head == NULL) return;
else
{
cursor = head;
while(cursor != NULL)
{
if (cursor->data == character)
{
if (cursor->prev == NULL)
{
// printf("deleting from front\n");
previous = head;
head = head->next;
head->prev = NULL;
//boolean = 1;
//free(previous);
}
if (cursor->next == NULL)
{
//printf("deleting from back\n");
previous = last;
last = last->prev;
last->next = NULL;
//boolean = 1;
//free(previous);
}
else
{
// printf("deleting from middle\n");
previous = cursor;
cursor = cursor->next;
cursor->prev = previous->prev;
store_el = previous->prev;
store_el->next = cursor;
cursor = head;
}
free(previous);
//printf("head data = %c\n", cursor->data);
}
cursor = cursor->next;
}
}
}
//Prints all the elements in linked list in forward traversal order
void Print()
{
struct list* temp = head;
printf("Forward: ");
while(temp != NULL)
{
printf("%c ",temp->data);
temp = temp->next;
}
printf("\n");
}
int main()
{
char character;
/*Driver code to test the implementation*/
head = NULL; // empty list. set head as NULL.
// Calling an Insert and printing list before and after deletion of character
InsertAtHead('c');
InsertAtHead('a');
InsertAtHead('b');
InsertAtHead('b');
InsertAtHead('a');
Print();
printf("After deletion:\n");
remove_element ('b');
Print();
}
解决方案
/*
*I changed the name of your variable 'last' to 'tail'
*I removed the code at the end of your InsertAtHead function
*I added "tail = newNode;"
*I changed the name of your variable 'previous' to 'garbage'
*I removed your variable 'store_el' completely.
*I could have changed the whole code in your remove element function because the 3 cases are unnecessary but anyway.
*/
//Inserts a list at head of doubly linked list
void InsertAtHead(char x){
struct list* newNode = GetNewNode(x);
if (head == NULL){
head = newNode;
tail = newNode;
return;
}
head->prev = newNode;
newNode->next = head;
head = newNode;
}
void remove_element (char character){
struct list * cursor, *garbage;
cursor = head;
while(cursor != NULL){
if (cursor->data == character){
garbage = cursor;
if (cursor->prev == NULL){
head = head->next;
If (head!=NULL) head->prev = NULL;
cursor=head;
}else if (cursor->next == NULL){
tail = tail->prev;
tail->next = NULL;
cursor=NULL;
}else{
garbage->prev->next = garbage->next;
garbage->next->prev = garbage->prev;
cursor=cursor->next;
}
free(garbage);
} else cursor=cursor->next;
}
}
现在就试试。
您的代码的问题是您正在使用您释放的内存。
/*
*cursor and previous point to the same memory address
*you free the memory that the variable previous points so the cursor points to that freed memory
*when you save the next address to the cursor using that freed memory you create an undefined behaviour (your code may work or may not)
*/
cursor = head;
while(cursor != NULL)
{
if (cursor->data == character)
{
if (cursor->prev == NULL)
{
previous = head;
head = head->next;
head->prev = NULL;
free(previous);
...
cursor=cursor->next;
改进的代码:
#include<stdio.h>
#include<stdlib.h>
//The type of your variable data was wrong. I changed it to char
struct list{
char data;
struct list *prev, *next
};
void remove_element (char character){
struct list * cursor, *garbage;
cursor = head;
while(cursor != NULL){
if (cursor->data == character){
garbage = cursor;
if (garbage->prev!=NULL ) garbage->prev->next = garbage->next;
if (garbage->next!=NULL ) garbage->next->prev = garbage->prev;
cursor=cursor->next;
if (head==garbage) head=cursor;
//Basically the tail variable has no use for your current program.
//if (tail==garbage) tail=garbage->prev;
free(garbage);
} else cursor=cursor->next;
}
}
推荐阅读
- java - 将 Json 转换为类型脚本类 [ts]
- android - Oreo DocumentsContract.getDocumentId(uri) 返回路径而不是 Long
- javascript - R - 对角网络中的 JS 数组
- reactjs - 如何从 React Typescript 中的通用数组中删除项目?
- cassandra - Cassandra Nodetool 状态显示找不到命令
- enterprise-architect - Enterprise Architect 的文档中未生成序列图
- r - R中的匹配值
- asp.net-mvc - 如何使用 ImageResizer 处理图像并将其上传到 Azure 存储?
- neural-network - H2O.ai mini_batch_size 真的用过吗?
- iframe - 如果 iframe [src] 使用角度 5 给出 404 错误,如何处理错误