为什么选择排序时一个元素保留在原始列表中？

Question

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

struct node { 
    int val; 
    struct node* next; 
    } ; 

struct node* largest(struct node** first) 
{ 
    struct node* largest = *first; 
    struct node* prev = NULL; 
    struct node* temp_prev = NULL; 

    for(;first != NULL; first = first -> next) 
     { 
      if (first -> val > largest -> val) 
       { 
        largest = first; 
        prev = temp_prev; 
       }   
      temp_prev = first; 
     } 
     if(prev != NULL) 
     prev -> next = largest -> next; 
     largest -> next = NULL; 
     return largest;    
} 


struct node* sel_sort(struct node** list) 
{ 
    struct node* head = NULL; 
    struct node* temp_largest = NULL; 
    while (*list) 
    { 
     head = largest(list); 
     head->next=temp_largest; 
     temp_largest = head; 

    } 
    *list = head; // note sets the input pointer to the new list. 
    return head; 
} 

void print_list(struct node* first) 
{ 
    struct node* temp; 
    for (temp = first; temp != NULL; temp = temp->next) 
    { 
     printf("%d\n", temp->val); 
    } 
} 

void main() { 
    struct node* r = malloc(sizeof(struct node)); 
    struct node* s = malloc(sizeof(struct node)); 
    struct node* t = malloc(sizeof(struct node)); 
    struct node* w = malloc(sizeof(struct node)); 
    struct node* q = malloc(sizeof(struct node)); 
    r->val = 2; 
    r->next = s; 
    s->val = 10; 
    s->next = t; 
    t->next = w; 
    t->val = 3; 
    w->val = 1; 
    w->next = q; 
    q->val = 6; 
    q->next = NULL; 
    printf("\nBefore Sort:\n"); 
    print_list(r); 
    printf("\nSorted:\n"); 
    struct node* sorted = sel_sort(&r); 
    print_list(sorted); 
    } 

简而言之，以上是对单向链表的选择排序。我遇到了sel_sort方法中出现无限循环的问题，因为无论我称多少次最大的方法，都会将一个节点留在原始列表中。除此之外，我的代码似乎工作，但我怎么解决这个小问题？

Answer 1

那么，你能指望什么会永远修改变量list在这个while循环：

struct node* temp = *list; 
struct node* head; 
struct node* temp_largest = NULL; 
while (list != NULL) // <<=== infinite loop 
{ 
    head = largest(temp); 
    head->next=temp_largest; 
    temp_largest = head; 

} 
return head; 

我怀疑你的temp使用。从技术上讲，你的largest()函数应该采用逐个地址的列表（指向指针的指针），提取最大节点，从列表中移除后返回该节点，并且更新传入的列表头以使其不可能是第一个列表中的节点（因此头部有被移动）：

struct node* head = NULL; 
struct node* temp_largest = NULL; 
while (*list) 
{ 
    head = largest(list); 
    head->next=temp_largest; 
    temp_largest = head; 

} 
*list = head; // note sets the input pointer to the new list. 
return head; 

而且具有largest()采取按地址列表指针（双指针）

struct node* largest(struct node** first) 
{ 
    struct node *prev = NULL; 
    struct node *lprev = NULL; 
    struct node *cur = NULL; 
    struct node *largest = NULL; 

    if (!(first && *first)) 
     return NULL; 

    // assume the first node is the largest node 
    largest = lprev = prev = *first; 
    cur = largest->next; 
    for(; cur; prev = cur, cur = cur->next) 
    { 
     if (cur->val > largest->val) 
     { 
      largest = cur; 
      lprev = prev; 
     } 
    } 

    // go with the simple stuff first. was `largest` 
    // the first item in the list? 
    if (largest == *first) 
    { 
     // yes it was, so move the list head. 
     *first = largest->next; 
    } 
    else 
    { // no it was not, so link `lprev` to be 
     // the node following `largest` 
     lprev->next = largest->next; 
    } 

    // regardless. always unlink the largest node. 
    largest->next = NULL; 
    return largest; 
} 

使用这种结合更新排序，我得到这个输出：

输出

Before Sort: 
2 
10 
3 
1 
6 

Sorted: 
1 
2 
3 
6 
10