0 
 #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 方法中发生了无限循环，因为无论我调用多少次最大的方法，一个节点都会留在原始列表中。除此之外，我的代码似乎可以工作，但我该如何解决这个小问题？

4

1 回答 1

1

所以，你期望在这个whilelist循环中修改变量：

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
于 2013-02-28T04:12:36.187 回答