如何在 c 中删除链表中多个变量的多次出现

Question

我是 c 编程的初学者，几天来我一直在尝试解决以下问题：

如何删除在以下列表中至少出现 3 次的数字：

3→3→1→2→4→3→5→3→5→4

这使得结果：

1→2→4→5→5→4.

现在我知道如何删除链表中多次出现的">

一个"键，例如删除链表中所有出现的"1"，但似乎无法理解如何删除多个变量的多次出现。简直要了我的命。如果有人能帮忙，我将不胜感激。提前谢谢。

Answer 1

似乎没有人急着帮助你:)

如果通过引用将指针头传递给函数，则编写函数更简单。

下面是一个演示程序，展示了如何实现该功能。

#include <stdio.h>
#include <stdlib.h>
struct Node
{
int data;
struct Node *next;
};
int insert( struct Node **head, int data )
{
struct Node *node = malloc( sizeof( struct Node ) );
int success = node != NULL;
if ( success )
{
node->data = data;
node->next = *head;
*head = node;
}
return success;
}
void out( struct Node *head )
{
for ( ; head != NULL; head = head->next )
{
printf( "%d -> ", head->data );
}
puts( "null" );
}
void remove_repetitive( struct Node **head )
{
const size_t LIMIT = 3;
while ( *head != NULL )
{
size_t count = 1;
int data = ( *head )->data;
for ( struct Node *node = ( *head )->next; 
count < LIMIT && node != NULL; node = node->next )
{
if ( node->data == data ) ++count;
}
if ( count == LIMIT )
{
for ( struct Node **node = head; *node != NULL; )
{
if ( ( *node )->data == data )
{
struct Node *tmp = *node;
*node = ( *node )->next;
free( tmp );
}
else
{
node = &( *node )->next;
}
}
}
else
{
head = &( *head )->next;
}
}
}
int main(void) 
{
struct Node *head = NULL;
int a[] = { 4, 5, 3, 5, 3, 4, 2, 1, 3, 3 };
const size_t N = sizeof( a ) / sizeof( *a );
for ( size_t i = 0; i < N; i++ )
{
insert( &head, a[i] );
}
out( head );
remove_repetitive( &head );
out( head );
return 0;
}

程序输出为

3 -> 3 -> 1 -> 2 -> 4 -> 3 -> 5 -> 3 -> 5 -> 4 -> null
1 -> 2 -> 4 -> 5 -> 5 -> 4 -> null

函数remove_repetitive可以拆分为两个函数，如下所示。

#include <stdio.h>
#include <stdlib.h>
struct Node
{
int data;
struct Node *next;
};
int insert( struct Node **head, int data )
{
struct Node *node = malloc( sizeof( struct Node ) );
int success = node != NULL;
if ( success )
{
node->data = data;
node->next = *head;
*head = node;
}
return success;
}
void out( struct Node *head )
{
for ( ; head != NULL; head = head->next )
{
printf( "%d -> ", head->data );
}
puts( "null" );
}
void remove_all( struct Node **head, int data )
{
while ( *head != NULL )
{
if ( ( *head )->data == data )
{
struct Node *tmp = *head;
*head = ( *head )->next;
free( tmp );
}
else
{
head = &( *head )->next;
}
}
}
void remove_repetitive( struct Node **head )
{
const size_t LIMIT = 3;
while ( *head != NULL )
{
size_t count = 1;
int data = ( *head )->data;
for ( struct Node *node = ( *head )->next; 
count < LIMIT && node != NULL; node = node->next )
{
if ( node->data == data ) ++count;
}
if ( count == LIMIT )
{
remove_all( head, data );   
}
else
{
head = &( *head )->next;
}
}
}
int main(void) 
{
struct Node *head = NULL;
int a[] = { 4, 5, 3, 5, 3, 4, 2, 1, 3, 3 };
const size_t N = sizeof( a ) / sizeof( *a );
for ( size_t i = 0; i < N; i++ )
{
insert( &head, a[i] );
}
out( head );
remove_repetitive( &head );
out( head );
return 0;
}

程序输出与上图相同。