爲什麼選擇排序時一個元素保留在原始列表中？

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