时间戳

首页 > 解决方案 > C、如何从队列中删除元素？

c - C、如何从队列中删除元素？

问题描述

更新：我们相信在这两种解决方案中都发现了一些错误，也邀请您分享您的想法:)

我试图实现我自己的数据结构，它将列表与 C 中的队列相结合。

我的数据结构有 2 个指针，前面指向队列中最旧的成员，后面指向新添加的成员，每个成员都指向在它之后插入的成员。

例如，如果我插入 1 然后 2 然后 3，我将有：

NULL <-3 <- 2 <- 1 // 1 is front and 3 is rear.

现在我想支持从这个 DS 中删除元素，所以我开始 imeplemnting 它并发现了数十种边缘情况，例如：

  1. 如果该成员是前面，则更改 DS 的前面并释放该成员，但是如果现在前面为 null，则将后面也更改为 null，否则其他代码将无法按预期工作。

  2. 如果成员处于中间版本，则返回上一个成员并更新其下一个但这似乎真的很难

  3. 后部成员几乎相同，除了我们现在需要更新后部并且只将指向元素的指针更改为右侧（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
}

标签： clistalgorithmdata-structuresqueue

解决方案

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
------------

程序演示

推荐阅读