我正在尝试编写一种对双向链表中的元素进行排序的方法。该列表由具有指向下一个元素的前向和后向指针(flink、blink)的结构组成。 head->blink 应该为 null,tail->flink 应该为 null(也不是循环)。我尝试了一种选择排序方法,但我一直遇到段错误。我已将问题隔离到注释行中。但是我包含了我的所有代码,排序方法在底部。
//header (dblLinkList.h)
#include <stdio.h>
#include <stdlib.h>
typedef struct _DblLinkList {
struct _DblLinkList *flink;
struct _DblLinkList *blink;
int num;
} DblLinkList;
struct _DblLinkList *head, *tail;
struct _DblLinkList *init(int nElements);
void sort(struct _DblLinkList *listNode);
void print(struct _DblLinkList *listNode);
//implementation
#include <stdio.h>
#include <stdlib.h>
#include "dblLinkList.h"
int main() {
struct _DblLinkList *list1 = init(2);
printf("-----Head to Tail------\n");
print(list1);
printf("Sorting...\n");
sort(list1);
printf("-----Head to Tail------\n");
print(list1);
}
struct _DblLinkList *init(int nElements) {
struct _DblLinkList *listNode;
int i = 0;
for(i = 0; i < nElements; i++) {
listNode = (struct _DblLinkList *)malloc(sizeof(struct _DblLinkList));
listNode->num = random();
if(head == NULL) {
head = listNode;
listNode->blink = NULL;
} else {
tail->flink = listNode;
listNode->blink = tail;
}
tail = listNode;
listNode->flink = NULL;
}
return listNode;
}
void print(struct _DblLinkList *listNode) {
for(listNode = head; listNode != NULL; listNode = listNode->flink) {
printf("%d\n", listNode->num);
}
}
void sort(struct _DblLinkList *listNode) {
//Not working properly
struct _DblLinkList *listNode2;
struct _DblLinkList *minNode;
struct _DblLinkList *temp = (struct _DblLinkList *)malloc(sizeof(struct _DblLinkList));
//start from the head and traverse the list
for(listNode = head; listNode != NULL; listNode = listNode->flink) {
minNode = listNode;
listNode2 = listNode->flink;
for(;listNode2 != NULL; listNode2 = listNode2->flink) {
if (listNode2->num < minNode->num) {
minNode = listNode2;
}
}
//Problem Lies here vvvvvvvvvvvv
temp->flink = listNode->flink;
temp->blink = listNode->blink;
listNode->blink = listNode2;
listNode->flink = listNode2->flink;
listNode2->flink = temp;
listNode2->blink = temp->blink;
printf("min: %d\n", minNode->num);
}
}
最佳答案
for(;listNode2 != NULL; listNode2 = listNode2->flink)
此循环仅在 listNode2 为 NULL
时退出。所以我们在这一点上确定了 listNode2 == NULL
。
Thou shalt not follow the NULL pointer, for chaos and madness await thee at its end.
这就是你所做的,违反了第二条诫命
listNode2->flink = temp;
关于c - C排序问题中的双向链表,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/6270827/