我编写了一个程序，可以在双链表的开头添加字符。现在，一旦我有了这个列表，我的程序的目的就是从列表中完全删除某些字符。例如(使用花括号仅用于代表性目的(：如果列表由{a，b，b，a，c}组成，那么我的程序可以删除所有的"b"；从列表中选择，使其｛a，a，c｝。此外，如果我的列表是{b，a，c，a}或｛a，c、a，b}a，c，a}。
但是有许多问题(对于所有情况，假设我想删除"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 frontn");
previous = head;
head = head->next;
head->prev = NULL;
//boolean = 1;
//free(previous);
}
if (cursor->next == NULL)
{
//printf("deleting from backn");
previous = last;
last = last->prev;
last->next = NULL;
//boolean = 1;
//free(previous);
}
else
{
// printf("deleting from middlen");
previous = cursor;
cursor = cursor->next;
cursor->prev = previous->prev;
store_el = previous->prev;
store_el->next = cursor;
cursor = head;
}
free(previous);
//printf("head data = %cn", 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;
}
}
尝试更新光标
cursor = head;
在你从前面删除之后。
Ellothere我认为您的程序中的问题是您在前一个程序中分配了节点的地址，但没有并排释放它。
if (cursor->prev == NULL)
{
// printf("deleting from frontn");
previous = head;
head = head->next;
head->prev = NULL;
//boolean = 1;
//free(previous);
}
if (cursor->next == NULL)
{
//printf("deleting from backn");
previous = last;
last = last->prev;
last->next = NULL;
//boolean = 1;
//free(previous);
}
这里存储节点，但在最后释放它，然后这里有2个if语句，那么发生的事情是｛a b b a c｝中的"b"都紧挨着，所以前一个变量存储第一个"b"的地址，然后存储下一个'b'的地址，它只是释放那个'b'和那个'b]。简而言之，您应该并排释放节点。我做了这个小改动，效果很好。
if (cursor->prev == NULL)
{
// printf("deleting from frontn");
previous = head;
head = head->next;
head->prev = NULL;
free(previous);
//boolean = 1;
//free(previous);
}
if (cursor->next == NULL)
{
//printf("deleting from backn");
previous = last;
last = last->prev;
last->next = NULL;
free(previous);
//boolean = 1;
//free(previous);
}
else
{
// printf("deleting from middlen");
previous = cursor;
cursor = cursor->next;
cursor->prev = previous->prev;
store_el = previous->prev;
store_el->next = cursor;
cursor = head;
}
我刚刚在两个if语句中添加了free函数。