我有以下数据结构：
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;
}
我收到了堆错误，我的第二次打印没有打印排序列表，它什么也不打印。我做错了什么？我能做些什么来纠正它？
除了按地址传递指针（请参阅下面的注释）之外，您还需要修复交换元素的方式
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
}
}
您必须通过引用将参数传递给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;
}
}
这段代码太可怕了！你不仅没有为我们提供重现你的问题的所有必要条件（我们无法编译它！），而且你在typedef后面隐藏了指针抽象（对我们来说也是一场噩梦）。一般来说，一个人甚至不应该在C中使用链表，更不用说排序了。。。
尽管如此，这里有两个答案。
在find循环中找到的*minafteri = j;实际上修改了您的列表！为什么您的find循环要修改您的列表？
答案：不应该！通过分配minafteri = &j->next，您将不会使用find循环修改列表。。。
或者，您可以在该循环内部执行交换。
*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时会注意到。。。哦，等一下！你真可耻！
将重点放在将列表中的两个节点作为一个较小的任务进行交换上。一旦你完成了，就考虑承担这项任务。
您的代码中存在多个问题：
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;
}
}
}
以下是链表上选择排序的Java实现：
- 时间复杂度：O（n^2）
- 空间复杂性：O（1）-选择排序是就地排序算法
class Solution
{
public ListNode selectionSortList(ListNode head)
{
if(head != null)
{
swap(head, findMinimumNode(head));
selectionSortList(head.next);
}
return head;
}
private void swap(ListNode x, ListNode y)
{
if(x != y)
{
int temp = x.val;
x.val = y.val;
y.val = temp;
}
}
private ListNode findMinimumNode(ListNode head)
{
if(head.next == null)
return head;
ListNode minimumNode = head;
for(ListNode current = head.next; current != null; current = current.next)
{
if(minimumNode.val > current.val)
minimumNode = current;
}
return minimumNode;
}
}