4

所以现在我正在尝试实现一个 deltaclock，我尝试的第一步是首先创建一个使用双链表的优先级队列（我稍后会做其他 deltaclock 的事情）。从优先级队列中弹出的第一个元素是位于链表（或 deltaClock 结构）根部的元素。

我在测试中将一些元素推送到队列中，经过几次弹出操作后，有一种情况是当它从一个几乎为空的列表中弹出时会出现段错误。

当我在 pop 方法中注释掉我说“clock->root->previous = 0;”的行时，当我弹出元素时，main 方法中的程序不会出现段错误。但是，需要删除指向前一个节点的指针，因为前一个节点将不再存在。

当我执行弹出操作时，如何使新根的前一个指针为空？

#include <stdio.h>
#include <stdlib.h>

struct deltaNode{
    int tics;                  // source
    struct deltaNode* next;
    struct deltaNode* previous;
};

struct deltaClock{
    struct deltaNode* root;
    struct deltaNode* tail;
    int size;
};

void initDeltaClock(struct deltaClock **clock){
    (*clock) = malloc(sizeof(struct deltaClock));
    (*clock)->size = 0;
}

void push(struct deltaClock* clock, int numberOfTics){
if(clock->root == 0){
    // root is empty, initialize it.
    clock->root = malloc(sizeof(struct deltaNode));
    clock->root->tics = numberOfTics;
    clock->tail = clock->root;
} 
else {
    struct deltaNode* newNode = malloc(sizeof(struct deltaNode));
    newNode->tics = numberOfTics;
    struct deltaNode* temp = clock->root;

    if(newNode->tics < temp->tics){
        clock->root->previous = newNode;
        newNode->next = clock->root;
        clock->root = newNode;
    } else {
        while(newNode->tics > temp->tics){
            if(temp->next == 0){
                break;
            }
            temp = temp->next;
        }

        if(temp->next == 0 && newNode->tics > temp->tics){
            clock->tail->next = newNode;
            newNode->previous = clock->tail;
            clock->tail = newNode;
        }
        else{
            temp->previous->next = newNode;
            newNode->previous = temp->previous;
            newNode->next = temp;
            temp->previous = newNode;
        }

    }

}
clock->size++;
}

int pop(struct deltaClock* clock){
    struct deltaNode* temp = clock->root;
       if(temp == 0){
        return -1;
    }
    int result = temp->tics;
    clock->root = clock->root->next;
    clock->root->previous = 0;
    free(temp);
    clock->size--;
    return result;
}

void printClock(struct deltaClock* clock){
    struct deltaNode* iterator;
    iterator = clock->root;
    while(iterator != 0){
            printf("\n%d",iterator->tics);
            iterator = iterator->next;
    }
}


int main(int argc, char* argv[]){
    printf("\nHello world.");
    struct deltaClock* clock;
    initDeltaClock(&clock);
    push(clock, 3);
    push(clock, 2);
    push(clock, 7);
    push(clock, 33);
    push(clock, 221);
    push(clock, 5);
    printClock(clock);
    printf("\npopping %d",pop(clock));
    printf("\npopping %d",pop(clock));
    printf("\npopping %d",pop(clock));
    printf("\npopping %d",pop(clock));
    printf("\npopping %d",pop(clock));
    printf("\npopping %d",pop(clock));
    printf("\npopping %d",pop(clock));
    printf("\npopping %d",pop(clock));
    printf("\npopping %d",pop(clock));
    printf("\npopping %d",pop(clock));
    printf("\npopping %d",pop(clock));
    printf("\npopping %d",pop(clock));
    push(clock, 25);
    printf("\npopping %d",pop(clock));
    printf("\n");
}
4

2 回答 2

2

除了给出的其他建议之外，在处理指针时，最好始终将它们初始化为 NULL 或它们的最终值，不要让它们悬空。

例如， ininitDeltaClock和(*clock)->root未(*clock)->tail初始化。这意味着在第一次push调用中，即使检查if (clock->root == 0)也将无效，因为clock->root尚未初始化为 0。

这是一个建议的改进：

void initDeltaClock(struct deltaClock **clock){
    (*clock) = calloc(sizeof(struct deltaClock));  /* <-- zero out entire contents after alloc */
}

这同样适用于malloc'ed in 的结构push，您可以使用calloc而不是malloc确保返回的块被清除为零，或者您应该明确地将结构的指针设置为零。

此外，如果这不仅仅是一个玩具项目，请始终检查分配函数的返回值以检查内存不足错误。

于 2013-10-20T02:41:46.963 回答
2

对于它的价值，这段代码运行得相当稳健：

#include <stdio.h>
#include <stdlib.h>

struct deltaNode
{
    int tics;                  // source
    struct deltaNode *next;
    struct deltaNode *previous;
};

struct deltaClock
{
    struct deltaNode *root;
    struct deltaNode *tail;
    int size;
};

void initDeltaClock(struct deltaClock * *clock);

void initDeltaClock(struct deltaClock * *clock)
{
    (*clock) = malloc(sizeof(struct deltaClock));
    (*clock)->size = 0;
}

void push(struct deltaClock *clock, int numberOfTics);

void push(struct deltaClock *clock, int numberOfTics)
{
    if (clock->root == 0)
    {
        // root is empty, initialize it.
        clock->root = malloc(sizeof(struct deltaNode));
        clock->root->tics = numberOfTics;
        clock->tail = clock->root;
    }
    else
    {
        struct deltaNode *newNode = malloc(sizeof(struct deltaNode));
        newNode->tics = numberOfTics;
        struct deltaNode *temp = clock->root;

        if (newNode->tics < temp->tics)
        {
            clock->root->previous = newNode;
            newNode->next = clock->root;
            clock->root = newNode;
        }
        else
        {
            while (newNode->tics > temp->tics)
            {
                if (temp->next == 0)
                    break;
                temp = temp->next;
            }

            if (temp->next == 0 && newNode->tics > temp->tics)
            {
                clock->tail->next = newNode;
                newNode->previous = clock->tail;
                clock->tail = newNode;
            }
            else
            {
                temp->previous->next = newNode;
                newNode->previous = temp->previous;
                newNode->next = temp;
                temp->previous = newNode;
            }
        }
    }
    clock->size++;
}

int pop(struct deltaClock *clock);

int pop(struct deltaClock *clock)
{
    struct deltaNode *temp = clock->root;
    if (temp == 0)
        return -1;
    int result = temp->tics;
    clock->root = clock->root->next;
    if (clock->root != 0)
        clock->root->previous = 0;
    free(temp);
    clock->size--;
    return result;
}

void printClock(struct deltaClock *clock);

void printClock(struct deltaClock *clock)
{
    struct deltaNode *iterator;
    iterator = clock->root;
    while (iterator != 0)
    {
        printf(" %d", iterator->tics);
        iterator = iterator->next;
    }
    putchar('\n');
}

int main(void)
{
    printf("Hello world.\n");
    struct deltaClock *clock;
    initDeltaClock(&clock);
    push(clock, 3);
    push(clock, 2);
    push(clock, 7);
    push(clock, 33);
    push(clock, 221);
    push(clock, 5);
    printClock(clock);
    printf("popping %d\n", pop(clock));
    printf("popping %d\n", pop(clock));
    printf("popping %d\n", pop(clock));
    printf("popping %d\n", pop(clock));
    printf("popping %d\n", pop(clock));
    printf("popping %d\n", pop(clock));
    printf("popping %d\n", pop(clock));
    printf("popping %d\n", pop(clock));
    printf("popping %d\n", pop(clock));
    printf("popping %d\n", pop(clock));
    printf("popping %d\n", pop(clock));
    printf("popping %d\n", pop(clock));
    push(clock, 25);
    printf("popping %d\n", pop(clock));
    printf("\n");
}

它产生：

Hello world.
 2 3 5 7 33 221
popping 2
popping 3
popping 5
popping 7
popping 33
popping 221
popping -1
popping -1
popping -1
popping -1
popping -1
popping -1
popping 25

clock->root->previous = 0;除非clock->root不为空，否则未设置主要更改。

次要更改是在打印语句的末尾添加换行符，并从开头删除它们。并且列表水平打印，每行多个数字，而不是每行一个数字。

显示的代码使用以下代码干净地编译：

gcc -O3 -g -std=c11 -Wall -Wextra -Wmissing-prototypes -Wstrict-prototypes \
    -Wold-style-definition pl.c -o pl

需要函数声明才能使用这些选项进行干净编译；总的来说，它们是个好主意。另一种方法是将函数全部设为静态，这也适用于单文件程序。使代码编译干净所需的唯一更改是添加函数原型并替换main(int argc, char **argv)为main(void)- 做得好，这非常好。

于 2013-10-20T02:04:35.510 回答