選擇排序與鏈表的

Question

我有以下數據結構：

struct scoreentry_node { 
    struct scoreentry_node *next; 
    int score; 
    char name[1];  
}; 
typedef struct scoreentry_node *score_entry; 

我想創建消耗，爲了我的結構，安排他們根據名稱升序排列的功能。我想修改的輸入沒有分配任何存儲或釋放任何東西：

我試過你的建議：

void selectionsort(score_entry *a) { 
    for (; *a != NULL; *a = (*a)->next) { 
     score_entry *minafteri = a; 
     // find position of minimal element 
     for (score_entry j = (*a)->next; j != NULL; j = j->next) { 
      if (strcmp(j->name, (*minafteri)->name) == -1) { 
       *minafteri = j; 
      } 
     } 
     // swap minimal element to front 
     score_entry tmp = *a; 
     a = minafteri; 
     *minafteri = tmp; 
    } 
} 

我與測試上面的代碼如下：

score_entry x = add(8, "bob", (add(8 , "jill", (add (2, "alfred", NULL))))); 
iprint("",x); 
selectionsort(&x); 
iprint("", x); 
clear(x); //Frees the whole list 

iprint()在結構中打印分數和名稱字段。我的添加功能如下：

score_entry add(int in, char *n, score_entry en) {  
    score_entry r = malloc(sizeof(struct scoreentry_node) + strlen(n)); 
    r->score = in; 
    strcpy(r->name, n); 
    r->next = en; 
    return r; 
} 

我得到堆錯誤，我的第二個打印不打印排序列表，它不打印任何東西。我做錯了什麼，我能做些什麼來解決它？

Answer 1

你必須參考傳遞參數selectionsort：

void selectionsort(score_entry *a) { 
    for (; *a != NULL; *a = (*a)->next) 
    { 
     score_entry *minafteri = a; 
     // find position of minimal element 
     for (score_entry j = (*a)->next; j != NULL; j = j->next) { 
     if (strcmp(j->name, (*minafteri)->name) == -1) { 
     *minafteri = j; 
     } 
    } 
    // swap minimal element to front 
     score_entry tmp = *a; 
     a = minafteri; 
     *minafteri = tmp; 
    } 
} 

Answer 2

除了通過地址傳遞指針（請參見下面的註釋），您還需要修復您交換元素的方式太

void selectionsort(score_entry *a) { 
    for (; *a != NULL; *a = (*a)->next) 
    { 
    score_entry *minafteri = a; 
    // find position of minimal element 
    for (score_entry j = (*a)->next; j != NULL; j = j->next) { 
     if (strcmp(j->name, (*minafteri)->name) == -1) { 
     *minafteri = j; 
     } 
     } 
    // swap minimal element to front 
    score_entry tmp = *a; 
    a = minafteri; // put the minimal node to current position 
    tmp->next = (*a)->next ; //fix the links 
    (*minafteri)->next=tmp; //fix the links 
    } 
} 

Answer 3

這段代碼很可怕！您不僅沒有向我們提供重現您的問題的所有必需品（我們無法編譯這個！），但您已經隱藏了指針抽象背後的typedef（對我們來說也是一場噩夢）。一般來說，一個甚至不應該在C使用鏈表了別說排序他們...

但是，這裏有兩個答案。

---

*minafteri = j;發現在您找到循環實際修改您的列表！爲什麼你的找到循環正在修改你的列表？

答案：它不應該！通過而不是分配minafteri = &j->next，你將不會被修改清單，你發現環......

---

或者，您可以執行環路內的交換。

*minafteri = j;將需要交換以下，順序如下：

• (*minafteri)->next和j->next
• *minafteri和j

你認爲一行代碼能夠執行那些兩次掉期？好吧，它通過其中一箇中途...並在過程中從您的列表中刪除一堆元素！

---

下似乎是一個錯誤的嘗試交換元素：

score_entry *minafteri = a; // half of assigning `a` to `a` 
/* SNIP! 
* Nothing assigns to `minafteri` in this snippet. 
* To assign to `minafteri` write something like `minafteri = fubar;` */ 
score_entry tmp = *a;  // half of assigning `*a` to `*a` 
a = minafteri;    // rest of assigning `a` to `a` 
*minafteri = tmp;   // rest of assigning `*a` to `*a` 

它真的只是分配*a到*a和a到a ...你認爲你需要做的是什麼？

我以爲你會注意到那當你創建你的MCVE ......哦，等一下！真丟臉！

---

專注於交換列表中的兩個節點作爲較小的任務。一旦你做完了，考慮完成這個任務。

Answer 4

有你的代碼中的多個問題：

• if (strcmp(j->name, (*minafteri)->name) == -1) {是不正確的：strcmp()不一定返回-1，當第一個字符串小於第二，它可以返回任何負值。
• 您調整鏈接以移動較低條目的方式不正確：您無法更新從前一個節點到您移動到起始節點的鏈接。該列表已損壞。

這裏是一個改進版本：

void selectionsort(score_entry *a) { 
    for (; *a != NULL; a = &(*a)->next) { 
     // find position of minimal element 
     score_entry *least = a; 
     for (score_entry *b = &(*a)->next; *b != NULL; b = &(*b)->next) { 
      if (strcmp((*b)->name, (*least)->name) < 0) { 
       least = b; 
      } 
     } 
     if (least != a) { 
      // swap minimal element to front 
      score_entry n = *least; 
      *least = n->next; /* unlink node */ 
      n->next = *a;  /* insert node at start */ 
      *a = n; 
     } 
    } 
}