0

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

#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 编程的新手，我只学习了有关队列和链表的基础知识。所以我什至不知道我的代码是 100% 正确还是优雅的代码。我使用 DevC++ 编译此代码工作正常，但是当我使用 MS Visual Studio 2013 编译它时，它给了我一个异常“访问冲突写入位置......”。所以我很确定我的代码不是那么好。请帮助我出去谢谢

4

2 回答 2

3

问题一：数据结构

您有一个结构，其中包含链表项（信息和下一个元素）和队列结构（前和后，对于所有元素应该是相同的。

我建议使用： 

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()不初始化它返回的内存。如果您不初始化链接指针，它们实际上可能包含除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：添加/删除项目时的不一致

使用新的数据结构，您必须调整您的addLast()和delFirst(). 但它会更清楚，因为front和rear处于队列级别，并且next仅处于项目级别。

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

void addLast(struct queue *q, int item);      
int delFirst(struct queue *q);
于 2015-01-18T20:55:27.920 回答
1

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

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

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

您需要在函数makenode()内部或 in 中调用，或者您需要为和指向的结构提供结构。create()main()premiumnormal

选项 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，只是为了看看可能涉及什么，我只需要一个数据指针以及下一个和上一个指针。从列表中的任何元素，您可以访问列表中的所有其他元素。您可以在给定节点之前或之后插入，删除给定节点，将函数应用于所有节点，或查找与函数提供的谓词匹配的第一个节点（并获取下一个节点、前一个节点或数据），或销毁整个列表。

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

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

5
10

Empty Queue
20
30

Empty Queue
于 2015-01-18T20:57:05.320 回答