在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); 
     } 
    } 
+}