2013-04-18 67 views
-1

需要幫助,請需要幫助請 我的代碼編譯得很好,但是當我運行它給出了一個seg故障,我不知道爲什麼。我已經翻遍了這麼多次,但仍然不知道問題出在哪裏。需要幫助。可以請你告訴我這是什麼問題

void insertionSort(listNode ** listPtr, listNodeCompareFcn compare) 
{ 

    listNode * sorted = *listPtr; 
    listNode * swapper; 
    listNode * prev; 
    int swapped; 

    while(sorted != NULL) 
    { 

    swapper = sorted -> next; 
    prev = findprev(*listPtr, swapper); 
    swapped = 0; 

    while(swapper != NULL && prev != NULL && swapper != *listPtr && compare(swapper,prev)) 

    { 
     swapNodes(*listPtr, prev, swapper); 
     prev = findprev(*listPtr, swapper); 
     swapped = 1; 
    } 

     if (!swapped) sorted = sorted -> next; 

    } 

} 


static listNode * findprev(listNode * head, listNode * ptr){ 

    listNode * current = head; 

    while (current -> next != NULL){ 
     if ((current -> next) == ptr) return current; 
     current = current -> next; 
    }  

    return NULL; 

} 

void swapNodes(listNode * head, listNode * l1, listNode * l2){ 

    listNode * prev = findprev(head, l1); 
    prev -> next = l2; 
    l1 -> next = l2 -> next; 
    l2 -> next = l1; 

} 
+0

歡迎堆棧溢出。請儘快閱讀[常見問題]。還請學習如何撰寫SSCCE([簡短,獨立,正確的例子](http://sscce.org/));它可以幫助人們幫助你。你上面的代碼不是SSCCE;我們沒有結構定義,也沒有主要的程序。你能打印你的未分類數據嗎?從美觀上講,當你編寫C時,''''和' - >'操作符絕不會在它們周圍寫入空格;它們緊密結合。 (爲了在SO上展示代碼,不要使用製表符;每個級別縮進4個空格;在複製代碼時,使用編輯框上方的**按鈕來縮進代碼。) –

+0

我已經做得夠多了在一個SSCCE上工作,以知道你的問題的一個主要部分是,你沒有足夠小心,你的名單的頭。如果交換頭節點和下一個節點,則需要更新頭節點指針,否則會丟失列表的前端。我可以肯定,這只是麻煩的一部分。給定一個有效的列表,findprev()函數可以正常工作。我認爲'swapNodes()'和'insertionSort()'都不能給出一個乾淨的健康法案。例如,如果'findprev()'返回NULL,'swapNodes()'會高興地解引用NULL指針;崩潰! –

回答

2

我說:

我已經做了一個SSCCE足夠的工作,要知道,你的問題的一個重要組成部分是,你是不是與您的清單頭不夠仔細。如果交換頭節點和下一個節點,則需要更新頭節點指針,否則會丟失列表的前端。我可以肯定的是,這只是麻煩的一個組成部分[它實際上是整個麻煩]。給定一個有效的列表,findprev()函數可以正常工作。我想,swapNodes()insertionSort()都不能給出乾淨的健康法案(呢!)。例如,如果findprev()返回NULL,則swapNodes()高興地解引用NULL指針;崩潰!

這裏是您的代碼的SSCCE版本,使用上述註釋中確定的關於修復的反向通道信息更新爲swapNodes()compare()函數原來是C++風格的比較器,而不是C風格的比較器;也就是說,如果節點1位於節點2之前,則返回true,否則返回false(而C樣式比較器返回-1,0,+ 1 - 或者嚴格地說是負的零爲正值 - 小於,等於,大於)。只要修復了swapNodes() - 界面和代碼更改 - 以及正確的比較語義,列表就會正確排序。幾乎沒有詳盡的測試,但一個好的開始。

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

typedef struct listNode listNode; 
struct listNode 
{ 
    int datum; 
    listNode *next; 
}; 

typedef int (*listNodeCompareFcn)(const listNode *n1, const listNode *n2); 
//static void swapNodes(listNode *head, listNode *l1, listNode *l2); 
static void swapNodes(listNode **head, listNode *l1, listNode *l2); 
static listNode *findprev(listNode *head, listNode *ptr); 

static int node_compare(const listNode *n1, const listNode *n2)  // SSCCE 
{ 
    assert(n1 != 0 && n2 != 0); 
    printf("Compare: %2d and %2d\n", n1->datum, n2->datum); 
    if (n1->datum < n2->datum) 
     return 1; 
// if (n1->datum < n2->datum) 
//  return -1; 
// else if (n1->datum > n2->datum) 
//  return +1; 
    else 
     return 0; 
} 

static void insertionSort(listNode **listPtr, listNodeCompareFcn compare) 
{ 
    listNode *sorted = *listPtr; 

    while (sorted != NULL) 
    { 
     listNode *swapper = sorted->next; 
     listNode *prev = findprev(*listPtr, swapper); 
     int swapped = 0; 

     while (swapper != NULL && prev != NULL && swapper != *listPtr && compare(swapper, prev)) 
     { 
      //swapNodes(*listPtr, prev, swapper); 
      swapNodes(listPtr, prev, swapper); 
      prev = findprev(*listPtr, swapper); 
      swapped = 1; 
     } 

     if (!swapped) 
      sorted = sorted->next; 
    } 
} 

static listNode *findprev(listNode *head, listNode *ptr) 
{ 
    listNode *current = head; 
    assert(current != 0); 

    while (current->next != NULL) 
    { 
     if (current->next == ptr) 
      return current; 
     current = current->next; 
    } 

    return NULL; 
} 

// Update via email 
void swapNodes(listNode **listPtr, listNode *l1, listNode *l2) 
{ 
    listNode *prev = findprev(*listPtr, l1); 
    if (prev == NULL) 
    { 
     l1->next = l2->next; 
     *listPtr = l2; 
     l2->next = l1; 
    } 
    else 
    { 
     prev->next = l2; 
     l1->next = l2->next; 
     l2->next = l1; 
    } 
} 

/* 
static void swapNodes(listNode *head, listNode *l1, listNode *l2) 
{ 
    listNode *prev = findprev(head, l1); 
    prev->next = l2; 
    l1->next = l2->next; 
    l2->next = l1; 
} 
*/ 

static listNode *node_insert(listNode *head, int datum)  // SSCCE 
{ 
    listNode *node = malloc(sizeof(*node)); 
    node->datum = datum; 
    node->next = head; 
    return node; 
} 

static void print_list(const char *tag, const listNode *list)  // SSCCE 
{ 
    printf("%-8s", tag); 
    while (list != 0) 
    { 
     printf(" -> %2d", list->datum); 
     list = list->next; 
    } 
    putchar('\n'); 
} 

int main(void)  // SSCCE 
{ 
    static const int unsorted[] = { 29, 3, 14, 2, 91, 87, 13, 29, 1 }; 
    enum { NUM_VALUES = sizeof(unsorted)/sizeof(unsorted[0]) }; 
    listNode *head = 0; 

    print_list("Empty:", head); 
    for (int i = 0; i < NUM_VALUES; i++) 
    { 
     head = node_insert(head, unsorted[i]); 
     print_list("Added:", head); 
    } 

    for (listNode *curr = head; curr != 0; curr = curr->next) 
    { 
     listNode *prev = findprev(head, curr); 
     if (prev == 0) 
      printf("%2d - no prior node\n", curr->datum); 
     else 
      printf("%2d - prior node %2d\n", curr->datum, prev->datum); 
    } 

    print_list("Before:", head); 
    insertionSort(&head, node_compare); 
    print_list("After:", head); 

    return 0; 
} 

輸出從SSCCE(包括診斷):

Empty: 
Added: -> 29 
Added: -> 3 -> 29 
Added: -> 14 -> 3 -> 29 
Added: -> 2 -> 14 -> 3 -> 29 
Added: -> 91 -> 2 -> 14 -> 3 -> 29 
Added: -> 87 -> 91 -> 2 -> 14 -> 3 -> 29 
Added: -> 13 -> 87 -> 91 -> 2 -> 14 -> 3 -> 29 
Added: -> 29 -> 13 -> 87 -> 91 -> 2 -> 14 -> 3 -> 29 
Added: -> 1 -> 29 -> 13 -> 87 -> 91 -> 2 -> 14 -> 3 -> 29 
1 - no prior node 
29 - prior node 1 
13 - prior node 29 
87 - prior node 13 
91 - prior node 87 
2 - prior node 91 
14 - prior node 2 
3 - prior node 14 
29 - prior node 3 
Before: -> 1 -> 29 -> 13 -> 87 -> 91 -> 2 -> 14 -> 3 -> 29 
Compare: 29 and 1 
Compare: 13 and 29 
Compare: 13 and 1 
Compare: 87 and 29 
Compare: 91 and 87 
Compare: 2 and 91 
Compare: 2 and 87 
Compare: 2 and 29 
Compare: 2 and 13 
Compare: 2 and 1 
Compare: 14 and 91 
Compare: 14 and 87 
Compare: 14 and 29 
Compare: 14 and 13 
Compare: 3 and 91 
Compare: 3 and 87 
Compare: 3 and 29 
Compare: 3 and 14 
Compare: 3 and 13 
Compare: 3 and 2 
Compare: 29 and 91 
Compare: 29 and 87 
Compare: 29 and 29 
After: -> 1 -> 2 -> 3 -> 13 -> 14 -> 29 -> 29 -> 87 -> 91 
相關問題