c - 在C中对链表中的队列元素进行排序

Question

我上周参加了数据结构期末考试。我正在尝试解决考试中的一道题。我想出了一个解决方案，但我编写的代码在我的计算机上不起作用。我可能做错了什么。

问题是这样的:给定了 2 个队列，我们​​应该从这些队列中取出元素并在链接列表中对它们进行排序。

我想到了一个主意。将会有一个函数，它接受 2 个队列和一个链表的根作为参数，并且它将使每个队列出队，直到没有剩余的东西开始使另一个队列出队。链表有一个添加函数，可以按排序添加。

这是出队并添加到链表的函数 `

void sortedlist(queue *q1, queue *q2, node *root) {
    while (q1->counter != 0) {
        sortedInsert(root, dequeue(q1));
    }
    while (q2->counter != 0) {
        sortedInsert(root, dequeue(q2));
    }
}

`

这是将元素按排序添加到链表的函数。

  node* sortedInsert(node *root, int x) {
    if (root == NULL) {
        root = (node *)malloc(sizeof(node*));
        root->x = x;
        root->next = NULL;
        return root;
    }
    if (x< root->x) {
        node *temp = (node *)malloc(sizeof(node));
        temp->next = root;
        temp->x = x;
        return temp;
    }
    node *iter = root;
    while (iter->next != NULL && iter->next->x < x) {
        iter = iter->next;
    }
    node *temp = (node *)malloc(sizeof(node));
    temp->x = x;
    temp->next = iter->next;
    iter->next = temp;
    return root;
}

我将在这里编写所有代码。也许有人可以告诉我我哪里做错了。预先感谢您的考虑。

#include <stdio.h>
#include <stdlib.h>
#define MAX 100
//there are 2 queues, and one empty linked list
//take elements from queues and sort it on linked list

struct q {
    int queue[MAX];
    int front;
    int rear;
    int counter;
};

struct node {
    int x;
    struct node *next;
};

typedef struct node node;
typedef struct q queue;


void enqueue(queue *queue, int x) {

    if (!(queue->counter == MAX)) {
        queue->rear++;
        queue->counter++;
        if (queue->rear == MAX)
            queue->rear = 0;
        queue->queue[queue->rear] = x;
    }

}

int dequeue(queue *queue) {

    if (!(queue->counter == 0)) {
        int x = queue->queue[queue->front];
        queue->counter--;
        queue->front++;
        if (queue->front == MAX)
            queue->front = 0;
        return x;
    }
    else 
        return - 1;
}

node* sortedInsert(node *root, int x) {
    if (root == NULL) {
        root = (node *)malloc(sizeof(node*));
        root->x = x;
        root->next = NULL;
        return root;
    }
    if (x< root->x) {
        node *temp = (node *)malloc(sizeof(node));
        temp->next = root;
        temp->x = x;
        return temp;
    }
    node *iter = root;
    while (iter->next != NULL && iter->next->x < x) {
        iter = iter->next;
    }
    node *temp = (node *)malloc(sizeof(node));
    temp->x = x;
    temp->next = iter->next;
    iter->next = temp;
    return root;
}

void printlist(node *root) {

    while (root != NULL) {
        printf("%d \n", root->x);
        root = root->next;
    }
}

void initialize(queue *queue) {
    queue->counter = 0;
    queue->front = 0;
    queue->rear = -1;
}

void sortedlist(queue *q1, queue *q2, node *root) {
    while (q1->counter != 0) {
        sortedInsert(root, dequeue(q1));
    }
    while (q2->counter != 0) {
        sortedInsert(root, dequeue(q2));
    }
}

int main(void) {

    queue *q1 = NULL, *q2 = NULL;
    node *root = NULL;
    initialize(q1);
    initialize(q2);

    enqueue(q1, 10);
    enqueue(q1, 20);
    enqueue(q1, 30);
    enqueue(q1, 40);
    enqueue(q1, 50);
    enqueue(q1, 60);
    enqueue(q1, 70);
    enqueue(q2, 15);
    enqueue(q2, 25);
    enqueue(q2, 35);
    enqueue(q2, 45);
    enqueue(q2, 55);
    enqueue(q2, 65);
    enqueue(q2, 75);
    enqueue(q2, 85);
    enqueue(q2, 95);
    enqueue(q2, 105);
    enqueue(q2, 115);

    sortedlist(q1, q2, root);
    printlist(root);
}

Answer 1

实际上，只需进行很少的更改即可使该程序正常运行。

首先，让我们看看如何初始化队列:

queue *q1 = NULL, *q2 = NULL;
node *root = NULL;
initialize(q1);
initialize(q2);

您正在创建两个队列指针并将其初始化为 NULL。然后像这样初始化它们:

void initialize(queue *queue) {
    queue->counter = 0;
    queue->front = 0;
    queue->rear = -1;
}

这不起作用(并且立即对我来说出现段错误)，因为您将 NULL 指针传递到该函数中，然后尝试在其上设置值(NULL->counter = 0，...) .

有很多方法可以做到这一点，但其中一种可能是这样的:

/* Allocate a queue and initialize it */
queue *createQueue(void) {
    queue *q = malloc(sizeof(*q));
    q->counter = 0;
    q->front = 0;
    q->rear = -1;
    return q;
}

/* In your main() */
queue *q1 = createQueue();
queue *q2 = createQueue();
node *root = NULL;

接下来让我们看看 sortedInsert 函数的开头以及如何调用它:

node* sortedInsert(node *root, int x) {
    if (root == NULL) {
        root = (node *)malloc(sizeof(node*));
        root->x = x;
        root->next = NULL;
        return root;
    }
    /* ... */
    return root;
}

void sortedlist(queue *q1, queue *q2, node *root) {
    while (q1->counter != 0) {
        sortedInsert(root, dequeue(q1));
    }
    while (q2->counter != 0) {
        sortedInsert(root, dequeue(q2));
    }
}

这里有两个问题。首先，在 sortedInsert 中，您正在为 node*(指向结构的指针)malloc内存，但您希望为 malloc节点(结构本身)。

此外，您永远不会使用返回的 node*，因此它每次都将为 NULL。我会更多地重新调整它，但为了进行最小的改变，这将起作用:

/* The proper allocation in sortedInsert */
node* sortedInsert(node *root, int x) {
    if (root == NULL) {
        root = (node *)malloc(sizeof(node));
    /* ... */

    /* Store the return value each time, *and* return root from here */
    node *sortedlist(queue *q1, queue *q2) {
        node *root = NULL;

        while (q1->counter != 0) {
            root = sortedInsert(root, dequeue(q1));
        }
        while (q2->counter != 0) {
            root = sortedInsert(root, dequeue(q2));
        }

        return root;
    }

最后，清理分配始终是一个好习惯，因此请在打印列表后执行此操作:

/* New function to free your list elements */
void freelist(node *root) {
    node *tmp;

    while (root) {
        tmp = root->next;
        free(root);
        root = tmp;
    }
}

/* The end of your main() */
root = sortedlist(q1, q2);
printlist(root);
freelist(root);
free(q1);
free(q2);

如果您打算用 C 语言完成更多工作，那么使用调试器(gdb、VisualStudio 等)和 valgrind 等工具将非常有用。

如果上面的内容难以理解，这里是修改后的工作程序的链接:gist