在C排序问题双向链表

Question

我想写一个方法，在双向链表中排序元素。该列表由具有向前和向后指针（闪烁，闪烁）到下一个元素的结构组成。 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); 
     } 
    } 

Answer 1

看起来listNode2可以NULL是for循环之后。在尝试访问listNode2->flink之前，您应该检查一下。

Answer 2

for(;listNode2 != NULL; listNode2 = listNode2->flink) 

这个循环只有当listNode2是NULL退出。所以我们已经确定在这一点上listNode2 == NULL。

不可跟随NULL指针 为混乱和疯狂等待 你在它的末端。

这里是你在做什么，突破了第二诫

listNode2->flink = temp; 

Answer 3

我可以看到在代码中的几个问题：

1. 你保持插入相同的内存块，temp当你移动节点。
2. 当您移动listnode时，listnode->flink->blink（移动前）仍指向listnode。
3. 同＃2，但listnode->blink->flink
4. 当您移动listnode，你可能跳过旧的位置和listnode2之间的所有节点，如linstnode->flink现在listnode2->flink，这并不一定是旧值。这不会导致崩溃，但它会留下一些未排序的节点。
5. 当移动节点时，我没有看到head和tail的任何特殊处理，所以当你完成后它们可能会指向奇怪的节点。处理这种无缝操作的一个诀窍是使它们成为具体的_DblLinkList结构，以便代码不会与if陈述混杂在一起。

可能还有其他问题。

Answer 4

FTFY: still pretty ugly hack but should work 

--- 2.c 2011-06-07 13:03:48.000000000 -0700 
+++ 1.c 2011-06-07 13:49:18.000000000 -0700 
@@ -7,7 +7,8 @@ 
    int num; 
} DblLinkList; 

-struct _DblLinkList *head, *tail; 
+struct _DblLinkList *head = NULL; 
+struct _DblLinkList *tail = NULL; 

struct _DblLinkList *init(int nElements); 
void sort(struct _DblLinkList *listNode); 
@@ -35,16 +36,16 @@ 
    for(i = 0; i < nElements; i++) { 
     listNode = (struct _DblLinkList *)malloc(sizeof(struct _DblLinkList)); 
     listNode->num = random(); 
+    listNode->flink = NULL; 
+    listNode->blink = NULL; 

     if(head == NULL) { 
      head = listNode; 
-   listNode->blink = NULL; 
     } else { 
      tail->flink = listNode; 
      listNode->blink = tail; 
     } 
     tail = listNode; 
-  listNode->flink = NULL; 
    } 
    return listNode; 
} 
@@ -55,29 +56,33 @@ 
    } 
} 

-void sort(struct _DblLinkList *listNode) { 
+void sort(struct _DblLinkList *_listNode) { 
    //Not working properly 
- struct _DblLinkList *listNode2; 
- struct _DblLinkList *minNode; 
- struct _DblLinkList *temp = (struct _DblLinkList *)malloc(sizeof(struct _DblLinkList)); 
+  struct _DblLinkList* listNode = head; 
+ struct _DblLinkList *listNode2 = NULL; 
+ struct _DblLinkList *minNode = head; 
+ struct _DblLinkList *temp = NULL; 

    //start from the head and traverse the list 
- for(listNode = head; listNode != NULL; listNode = listNode->flink) { 
-  minNode = listNode; 
+ for(; listNode != NULL; listNode = listNode->flink) { 
     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; 
+      if (listNode->num > listNode2->num) { 
+        temp = listNode; 
+        listNode = listNode2; 
+        temp->flink = listNode2->flink; 
+        listNode->flink = temp; 
+        listNode->blink = temp->blink; 
+        listNode2 = temp; 
+        listNode2->blink = listNode; 
+        if (head == listNode2) 
+          head = listNode; 
+      } 
     printf("min: %d\n", minNode->num); 
     } 
    } 
+}