C、如何从队列中移除元素？
C, How to Remove Element From Queue?
更新： 我们相信会在这两个解决方案中发现一些错误，也邀请您分享您的想法:)
我试图实现我自己的数据结构，它在 C 中结合了列表和队列。
我的数据结构有 2 个指针，front 指向队列中最旧的成员，rear 指向新添加的成员，每个成员指向在它之后插入的 .
例如，如果我插入 1 然后 2 然后 3，我将有：
NULL <-3 <- 2 <- 1 // 1 is front and 3 is rear.
现在我想支持从此 DS 中删除元素，所以我开始实施它并发现了数十种边缘情况，例如：
如果成员是前面，则更改 DS 的前面并释放成员，但如果现在前面为空，则也将后面更改为空，否则其他代码将无法按预期工作.
如果该成员处于中间版本，则返回上一个成员并更新其下一个但这似乎真的很难
rear 成员几乎相同，除了我们现在需要更新 rear 并且只更改指向其右侧元素的指针（NULL 在其左侧）
我该如何做这样的事情？
几天来我已经有了几十个想法和实现，但都失败了，或者我做了一些非常糟糕的事情，使 运行 时间复杂度更高，或者我写了 170 行有矛盾并留下未完成的条件（通过使用 2 个指针）。
请帮忙实施这个？
struct queue_node
{
int key;
struct queue_node *next;
};
struct queue
{
int queue_size;
struct queue_node *front, *rear;
};
int requeue(struct queue *q, int val)
{
struct queue_node *tmp = q->front;
while (tmp!=NULL)
{
if (tmp->key==val)
{
if (tmp==q->front)
{
q->front=tmp->next;
if (q->front == NULL)
{
q->rear = NULL;
}
free(tmp);
}else if (tmp == q->rear)
{
}
return 0; // found
}
tmp=tmp->next;
}
return -1; // not found
}
函数可以这样定义
int requeue( struct queue *q, int val )
{
struct queue_node **current = &q->front;
struct queue_node *prev = NULL;
while ( *current && ( *current )->key != val )
{
prev = *current;
current = &( *current )->next;
}
int success = *current == NULL ? -1 : 0;
if ( success == 0 )
{
struct queue_node *tmp = *current;
*current = ( *current )->next;
free( tmp );
--q->queue_size;
if ( *current == NULL ) q->rear = prev;
}
return success;
}
这是一个演示程序。
#include <stdio.h>
#include <stdlib.h>
struct queue_node
{
int key;
struct queue_node *next;
};
struct queue
{
int queue_size;
struct queue_node *front, *rear;
};
int requeue( struct queue *q, int val )
{
struct queue_node **current = &q->front;
struct queue_node *prev = NULL;
while ( *current && ( *current )->key != val )
{
prev = *current;
current = &( *current )->next;
}
int success = *current == NULL ? -1 : 0;
if ( success == 0 )
{
struct queue_node *tmp = *current;
*current = ( *current )->next;
free( tmp );
--q->queue_size;
if ( *current == NULL ) q->rear = prev;
}
return success;
}
int push( struct queue *q, int key )
{
struct queue_node *node = malloc( sizeof( struct queue_node ) );
int success = node != NULL;
if ( success )
{
node->key = key;
node->next = NULL;
if ( q->rear == NULL )
{
q->front = q->rear = node;
}
else
{
q->rear = q->rear->next = node;
}
++q->queue_size;
}
return success;
}
void display( const struct queue *q )
{
for ( struct queue_node *current = q->front; current; current = current->next )
{
printf( "%d -> ", current->key );
}
puts( "null" );
}
int main(void)
{
struct queue q = { .front = NULL, .rear = NULL };
push( &q, 1 );
push( &q, 2 );
push( &q, 3 );
push( &q, 4 );
display( &q );
requeue( &q, 4 );
display( &q );
push( &q, 4 );
display( &q );
requeue( &q, 1 );
display( &q );
requeue( &q, 3 );
display( &q );
requeue( &q, 4 );
display( &q );
requeue( &q, 2 );
display( &q );
push( &q, 1 );
push( &q, 2 );
push( &q, 3 );
push( &q, 4 );
display( &q );
return 0;
}
程序输出为
1 -> 2 -> 3 -> 4 -> null
1 -> 2 -> 3 -> null
1 -> 2 -> 3 -> 4 -> null
2 -> 3 -> 4 -> null
2 -> 4 -> null
2 -> null
null
1 -> 2 -> 3 -> 4 -> null
如果为了测试将函数 printf 的调用添加到函数 requeue
中的此代码片段
if ( success == 0 )
{
struct queue_node *tmp = *current;
*current = ( *current )->next;
printf( "tmp->key == %d, tmp == %p\n", tmp->key, ( void * )tmp );
free( tmp );
--q->queue_size;
if ( *current == NULL ) q->rear = prev;
}
然后演示程序的输出可以看起来像
1 -> 2 -> 3 -> 4 -> null
tmp->key == 4, tmp == 0x55b55f9e02c0
1 -> 2 -> 3 -> null
1 -> 2 -> 3 -> 4 -> null
tmp->key == 1, tmp == 0x55b55f9e0260
2 -> 3 -> 4 -> null
tmp->key == 3, tmp == 0x55b55f9e02a0
2 -> 4 -> null
tmp->key == 4, tmp == 0x55b55f9e02c0
2 -> null
tmp->key == 2, tmp == 0x55b55f9e0280
null
1 -> 2 -> 3 -> 4 -> null
typedef struct queue_node
{
int key;
struct queue_node *next;
}node;
typedef struct
{
size_t size;
node *head;
node *tail;
}queue;
node *append(queue *q, int key)
{
node *n = malloc(sizeof(*n));
node *c = q -> head;
if(n)
{
if(!q -> head) q -> head = n;
else
{
while(c -> next) c = c -> next;
c -> next = n;
}
n -> key = key;
n -> next = NULL;
q -> size++;
q -> tail = n;
}
return n;
}
int removenode(queue *q, int key)
{
node *n = q -> head, *p = q -> head;
int result = 0;
while(n)
{
if(n -> key == key)
{
if(n == p)
{
q -> head = n -> next;
if(!n -> next) q -> tail = n;
}
else
{
p -> next = n -> next;
if(!p -> next) q -> tail = p;
}
free(n);
q -> size--;
result = 1;
break;
}
if(p != n) p = p -> next;
n = n -> next;
}
return result;
}
void printqueue(queue *q)
{
node *n = q -> head;
printf("The queue:\n");
while(n)
{
printf("Node key = %d\n", n -> key);
n = n -> next;
}
printf("--------------\n");
if(q -> head) printf("Head key: %d, Tail key: %d, Queue size: %zu\n -------------\n\n", q -> head -> key, q -> tail -> key, q -> size);
else printf("Queue empty\n------------\n\n");
}
int main(void)
{
queue q = {0,};
append(&q,1);
append(&q,2);
append(&q,3);
append(&q,4);
printqueue(&q);
removenode(&q,3);
printqueue(&q);
removenode(&q,1);
printqueue(&q);
removenode(&q,4);
printqueue(&q);
removenode(&q,2);
printqueue(&q);
}
结果：
The queue:
Node key = 1
Node key = 2
Node key = 3
Node key = 4
--------------
Head key: 1, Tail key: 4, Queue size: 4
-------------
The queue:
Node key = 1
Node key = 2
Node key = 4
--------------
Head key: 1, Tail key: 4, Queue size: 3
-------------
The queue:
Node key = 2
Node key = 4
--------------
Head key: 2, Tail key: 4, Queue size: 2
-------------
The queue:
Node key = 2
--------------
Head key: 2, Tail key: 2, Queue size: 1
-------------
The queue:
--------------
Queue empty
------------
更新： 我们相信会在这两个解决方案中发现一些错误，也邀请您分享您的想法:)
我试图实现我自己的数据结构，它在 C 中结合了列表和队列。
我的数据结构有 2 个指针，front 指向队列中最旧的成员，rear 指向新添加的成员，每个成员指向在它之后插入的 .
例如，如果我插入 1 然后 2 然后 3，我将有：
NULL <-3 <- 2 <- 1 // 1 is front and 3 is rear.
现在我想支持从此 DS 中删除元素，所以我开始实施它并发现了数十种边缘情况，例如：
如果成员是前面，则更改 DS 的前面并释放成员，但如果现在前面为空，则也将后面更改为空，否则其他代码将无法按预期工作.
如果该成员处于中间版本，则返回上一个成员并更新其下一个但这似乎真的很难
rear 成员几乎相同，除了我们现在需要更新 rear 并且只更改指向其右侧元素的指针（NULL 在其左侧）
我该如何做这样的事情？
几天来我已经有了几十个想法和实现，但都失败了，或者我做了一些非常糟糕的事情，使 运行 时间复杂度更高，或者我写了 170 行有矛盾并留下未完成的条件（通过使用 2 个指针）。
请帮忙实施这个？
struct queue_node
{
int key;
struct queue_node *next;
};
struct queue
{
int queue_size;
struct queue_node *front, *rear;
};
int requeue(struct queue *q, int val)
{
struct queue_node *tmp = q->front;
while (tmp!=NULL)
{
if (tmp->key==val)
{
if (tmp==q->front)
{
q->front=tmp->next;
if (q->front == NULL)
{
q->rear = NULL;
}
free(tmp);
}else if (tmp == q->rear)
{
}
return 0; // found
}
tmp=tmp->next;
}
return -1; // not found
}
函数可以这样定义
int requeue( struct queue *q, int val )
{
struct queue_node **current = &q->front;
struct queue_node *prev = NULL;
while ( *current && ( *current )->key != val )
{
prev = *current;
current = &( *current )->next;
}
int success = *current == NULL ? -1 : 0;
if ( success == 0 )
{
struct queue_node *tmp = *current;
*current = ( *current )->next;
free( tmp );
--q->queue_size;
if ( *current == NULL ) q->rear = prev;
}
return success;
}
这是一个演示程序。
#include <stdio.h>
#include <stdlib.h>
struct queue_node
{
int key;
struct queue_node *next;
};
struct queue
{
int queue_size;
struct queue_node *front, *rear;
};
int requeue( struct queue *q, int val )
{
struct queue_node **current = &q->front;
struct queue_node *prev = NULL;
while ( *current && ( *current )->key != val )
{
prev = *current;
current = &( *current )->next;
}
int success = *current == NULL ? -1 : 0;
if ( success == 0 )
{
struct queue_node *tmp = *current;
*current = ( *current )->next;
free( tmp );
--q->queue_size;
if ( *current == NULL ) q->rear = prev;
}
return success;
}
int push( struct queue *q, int key )
{
struct queue_node *node = malloc( sizeof( struct queue_node ) );
int success = node != NULL;
if ( success )
{
node->key = key;
node->next = NULL;
if ( q->rear == NULL )
{
q->front = q->rear = node;
}
else
{
q->rear = q->rear->next = node;
}
++q->queue_size;
}
return success;
}
void display( const struct queue *q )
{
for ( struct queue_node *current = q->front; current; current = current->next )
{
printf( "%d -> ", current->key );
}
puts( "null" );
}
int main(void)
{
struct queue q = { .front = NULL, .rear = NULL };
push( &q, 1 );
push( &q, 2 );
push( &q, 3 );
push( &q, 4 );
display( &q );
requeue( &q, 4 );
display( &q );
push( &q, 4 );
display( &q );
requeue( &q, 1 );
display( &q );
requeue( &q, 3 );
display( &q );
requeue( &q, 4 );
display( &q );
requeue( &q, 2 );
display( &q );
push( &q, 1 );
push( &q, 2 );
push( &q, 3 );
push( &q, 4 );
display( &q );
return 0;
}
程序输出为
1 -> 2 -> 3 -> 4 -> null
1 -> 2 -> 3 -> null
1 -> 2 -> 3 -> 4 -> null
2 -> 3 -> 4 -> null
2 -> 4 -> null
2 -> null
null
1 -> 2 -> 3 -> 4 -> null
如果为了测试将函数 printf 的调用添加到函数 requeue
if ( success == 0 )
{
struct queue_node *tmp = *current;
*current = ( *current )->next;
printf( "tmp->key == %d, tmp == %p\n", tmp->key, ( void * )tmp );
free( tmp );
--q->queue_size;
if ( *current == NULL ) q->rear = prev;
}
然后演示程序的输出可以看起来像
1 -> 2 -> 3 -> 4 -> null
tmp->key == 4, tmp == 0x55b55f9e02c0
1 -> 2 -> 3 -> null
1 -> 2 -> 3 -> 4 -> null
tmp->key == 1, tmp == 0x55b55f9e0260
2 -> 3 -> 4 -> null
tmp->key == 3, tmp == 0x55b55f9e02a0
2 -> 4 -> null
tmp->key == 4, tmp == 0x55b55f9e02c0
2 -> null
tmp->key == 2, tmp == 0x55b55f9e0280
null
1 -> 2 -> 3 -> 4 -> null
typedef struct queue_node
{
int key;
struct queue_node *next;
}node;
typedef struct
{
size_t size;
node *head;
node *tail;
}queue;
node *append(queue *q, int key)
{
node *n = malloc(sizeof(*n));
node *c = q -> head;
if(n)
{
if(!q -> head) q -> head = n;
else
{
while(c -> next) c = c -> next;
c -> next = n;
}
n -> key = key;
n -> next = NULL;
q -> size++;
q -> tail = n;
}
return n;
}
int removenode(queue *q, int key)
{
node *n = q -> head, *p = q -> head;
int result = 0;
while(n)
{
if(n -> key == key)
{
if(n == p)
{
q -> head = n -> next;
if(!n -> next) q -> tail = n;
}
else
{
p -> next = n -> next;
if(!p -> next) q -> tail = p;
}
free(n);
q -> size--;
result = 1;
break;
}
if(p != n) p = p -> next;
n = n -> next;
}
return result;
}
void printqueue(queue *q)
{
node *n = q -> head;
printf("The queue:\n");
while(n)
{
printf("Node key = %d\n", n -> key);
n = n -> next;
}
printf("--------------\n");
if(q -> head) printf("Head key: %d, Tail key: %d, Queue size: %zu\n -------------\n\n", q -> head -> key, q -> tail -> key, q -> size);
else printf("Queue empty\n------------\n\n");
}
int main(void)
{
queue q = {0,};
append(&q,1);
append(&q,2);
append(&q,3);
append(&q,4);
printqueue(&q);
removenode(&q,3);
printqueue(&q);
removenode(&q,1);
printqueue(&q);
removenode(&q,4);
printqueue(&q);
removenode(&q,2);
printqueue(&q);
}
结果：
The queue:
Node key = 1
Node key = 2
Node key = 3
Node key = 4
--------------
Head key: 1, Tail key: 4, Queue size: 4
-------------
The queue:
Node key = 1
Node key = 2
Node key = 4
--------------
Head key: 1, Tail key: 4, Queue size: 3
-------------
The queue:
Node key = 2
Node key = 4
--------------
Head key: 2, Tail key: 4, Queue size: 2
-------------
The queue:
Node key = 2
--------------
Head key: 2, Tail key: 2, Queue size: 1
-------------
The queue:
--------------
Queue empty
------------