使用链表的循环队列

Question

我想使用链表创建一个循环队列，我还想创建该数据结构（队列）的实例，而不仅仅是一个队列，很多队列而不重复代码。这就是我想出的...

#include <stdio.h>
#include <stdlib.h>
struct queue
{
    int info;
    struct queue *next;
    struct queue *front;
    struct queue *rear;
};
void create(struct queue **q)
{
    (*q)->next = 0;
    (*q)->front = 0;
    (*q)->rear = 0;
}
struct queue* makenode(int item){
    struct queue* p = (struct queue*)malloc(sizeof (struct queue));
    if (p) p->info = item;
    return p;
}
void addLast(struct queue **q, int item){
    struct queue* p = makenode(item);
    if ((*q)->front == NULL){

        (*q)->front = (*q)->rear = p;
        (*q)->front->next = (*q)->front;
        (*q)->rear->next = (*q)->rear;
    }
    else
    {
        (*q)->rear->next = p;
        p->next = (*q)->front;
        (*q)->rear = p;
    }
}
int delFirst(struct queue **q){

    struct queue *p = (*q)->front;

    if ((*q)->front == 0)
        printf("\nEmpty Queue\n");
    else
    {

        int temp = (*q)->front->info;
        if (((*q)->front->next) != ((*q)->front))
        {
            (*q)->front = (*q)->front->next;
            (*q)->rear->next = (*q)->front;
        }
        else
        {
            (*q)->front = 0;
        }
        return temp;
    }
    free(p);
}
void main()
{
    struct queue *premium, *normal;
    create(&premium);
    create(&normal);
    addLast(&premium, 5);
    addLast(&premium, 10);
    addLast(&normal, 20);
    addLast(&normal, 30);
    printf("%i\n", delFirst(&premium));
    printf("%i\n", delFirst(&premium));
    delFirst(&premium);
    printf("%i\n", delFirst(&normal));
    printf("%i\n", delFirst(&normal));
    delFirst(&normal);
    getch();
}

请问有什么好的方法吗？我有点觉得我的代码很复杂。我是 C 编程的新手，我只学习了有关队列和链接的基础知识 list.so 我什至不知道我的代码是 100% 正确的还是优雅的代码。我使用 DevC++ 编译这段代码工作正常，但是当我使用 MS Visual Studio 2013 编译它时，它给了我一个异常“访问冲突写入位置......”。所以我很确定我的代码不是那么好. 请帮帮我。谢谢

Answer 1

问题一：数据结构

您有一个结构，其中包含 linked 列表项（信息和下一个元素）和队列结构（前面和后面，所有元素都应该相同。

我建议使用：

struct queue_item
{
    int info;
    struct queue_item *next;
};
struct queue
{
    struct queue_item *front;
    struct queue_item *rear;
};

问题 2：队列创建

当您调用create()时，您传递的地址指针（例如premium）尚未初始化。它可以指向任何地方！最肯定的是到一个无效的位置。它还没有指向队列。因此，当您执行 (*q)->next = 0; 之类的操作时，您会尝试覆盖非法位置。

根据上面提出的数据结构，我提出以下建议：

struct queue* create (struct queue *q)  /* q points to a queue already allocated, or it is NULL */ 
{
    if (q==NULL) 
       q = malloc(sizeof (struct queue)); 
    if (q) {
        q->front = 0;
        q->rear = 0;
    }
    return q; 
}

在 main() 中，您可以选择：

struct queue *premium, normal;
premium = create(NULL);  /* allocate the queue structure */
create(&normal);         /* use an allocated structure */

问题 3：节点指针在节点创建时未初始化

malloc() 没有初始化它的内存returns。如果您不初始化 link 指针，这些指针实际上可能包含 NULL 以外的内容。

struct queue_item* makenode(int item){
    struct queue* p = (struct queue_item*)malloc(sizeof (struct queue_item));
    if (p) {
        p->info = item;
        p->next = NULL;   /* There is no link yet, so make it clear to avoid any surprises later. */
    }
    return p;
}

问题4：当adding/deleting项

时不一致

使用新的数据结构，您必须调整 addLast() 和 delFirst()。但是会更清楚，因为front和rear是队列级别的，而next只是项目级别的。

从签名来看，可以避免双重间接寻址，因为指向队列的指针永远不会被这些操作改变：

void addLast(struct queue *q, int item);      
int delFirst(struct queue *q);

Answer 2

您的第一个问题是您在未初始化的指针上调用 create()：

void create(struct queue **q)
{
    (*q)->next = 0;
    …
}

int main()
{
    struct queue *premium, *normal;
    create(&premium);
    create(&normal);

要么你需要在create()函数内部或main()中调用makenode()，要么你需要为premium和normal提供结构来指向.

选项A：

void create(struct queue **q)
{
    *q = makenode(0);
    if (*q != 0)
    {
        (*q)->next = 0;
        …
    }
}

选项 B：

int main()
{
    struct queue q_premium, q_normal;
    struct queue *premium = &q_premium;
    struct queue *normal  = &q_normal;
    create(&premium);
    create(&normal);

这两种技术都可以工作，但选项 B 需要小心，因为结构 q_premium 和 q_normal 未分配（尽管如果有必要，它们可能会分配）。但是，create() 的签名表明选项 A 是预期的，因为选项 B 实际上不需要 create().

中的双指针

我不清楚混合使用三个指针（front、rear、next）对您的结构有什么好处（如果有的话）。为了自己的利益，我实现了一个循环 DLL，只是为了看看可能涉及到什么，我只需要一个数据指针和 next 和 previous 指针。从列表中的任何元素，您都可以到达列表中的所有其他元素。您可以在给定节点之前或之后插入，删除给定节点，将函数应用于所有节点，或者找到与函数提供的谓词匹配的第一个节点（并获取下一个节点、上一个节点或数据），或者销毁整个列表。

我的印象是，如果没有其中一个指针，您的代码会更简单。

随着选项 A 的改变，代码编译并似乎工作，产生：

5
10

Empty Queue
20
30

Empty Queue

使用链表的循环队列

Circular Queue using Linked List

c

queue

linked-list

circular-list

circular-queue