所以现在我正在尝试实现一个deltaclock，我正在尝试的第一步是首先创建一个使用双链表的优先级队列（稍后我将做其他的deltaclock工作）。从优先级队列弹出的第一个元素是位于链接列表（或deltaclock结构）根目录的元素。
在我的测试中，我将一些元素推到队列中，在一些弹出操作之后，有一种情况是，当它从一个几乎为空的列表中弹出时，它会分段。
当我注释掉pop方法中我说“clock->root->previous=0；”的行时，当我弹出元素时，main方法中的程序不会分段。但是，前一个节点的指针需要去掉，因为以前的节点将不再存在。
在执行pop操作时，如何使新根的前一个指针为空？
#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");
}
最佳答案
值得一提的是，这段代码运行得相当正常：
#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。次要更改是在print语句的末尾添加新行，并从开头删除它们。列表是水平打印的，每行有多个数字，而不是每行一个数字。
所示代码使用以下方法进行干净编译：
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)-做得很好，这非常好。