选择排序与链表的

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; 
     } 
    } 
}