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

つまり、上記は単方向リストの選択ソートです。最大のメソッドを何度呼び出しても元のリストに 1 つのノードが残るため、sel_sort メソッドで無限ループが発生するという問題があります。それ以外の場合、私のコードは機能しているようですが、この小さな問題を回避するにはどうすればよいですか?

4

1 に答える 1

1

では、この while ループで変数が変更されると予想されることは次のとおりです。list

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 に答える