5

最大値を見つけてその位置から削除し、リストの先頭に挿入して、リンクされたリストを並べ替えようとしています。

私が遭遇している困難は、実際の削除と上部への挿入です。問題は、sortList 関数内に含まれる while ループの if 条件にあるようですが、修正方法がわかりません。

どんな助けでも大歓迎です。

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

typedef struct node{
    int num;
    struct node *next;
} Node, *NodePtr;

void printList(NodePtr np);
NodePtr makeList(void);
NodePtr makeNode(int n);
NodePtr sortList(NodePtr list);

int main(void) {
    NodePtr list;
    printf("Enter numbers for the list (0 to end)\n");
    list = makeList();
    printList(list);
    list = sortList(list);
    printList(list);
    return 0;
}

NodePtr makeList(void) {
    NodePtr makeNode(int), np, top, last;
    int n;
    top = NULL;
    if(scanf("%d", &n) != 1)n = 0;
    while(n != 0) {
        np = makeNode(n);
        if(top == NULL)top = np;
        else last->next = np;
        last = np;
        if(scanf("%d", &n)!=1)n=0;
    }
    return top;
}


void printList(NodePtr np) {
    while(np != NULL) {
        printf("%d\n", np->num);
        np = np->next;
    }
}

NodePtr makeNode(int n) {
    NodePtr np = (NodePtr)malloc(sizeof(Node));
    np->num = n;
    np->next = NULL;
    return np;
}

NodePtr sortList(NodePtr list) {
    NodePtr top = list;
    NodePtr curr = NULL;
    NodePtr largest;
    NodePtr prev;
    prev = NULL;
    curr = top;
    largest = top;

    while(curr != NULL) {
        prev = curr;
        if(curr->num > largest->num) {
            largest = curr;
            prev->next = curr->next;
            largest->next = top;
        }
        curr = curr->next;
    }
    if(prev == NULL) {
        largest->next = top;
        return largest;
    }
    return largest;
}
4

5 に答える 5

1

これは、QuickSortアルゴリズムを使用して単一リンクリストを並べ替える私の試みです。nがわかっている場合、実行時間はO（n log n）になります。これが役立つかどうかを確認してください。

#include "malloc.h"

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

bool insert_node(struct node **head, int val)
{
    struct node *elem;
    elem = (struct node *)malloc(sizeof(struct node));
    if (!elem)
        return false;
    elem->val = val;
    elem->next = *head;
    *head = elem;
    return true;
}

int get_lval(struct node *head, int l)
{
    while(head && l) {
        head = head->next;
        l--;
    }
    if (head != NULL)
        return head->val;
    else
        return -1;
}

void swap(struct node *head, int i, int j)
{
    struct node *tmp = head;
    int tmpival;
    int tmpjval;
    int ti = i;
    while(tmp && i) {
        i--;
        tmp = tmp->next;
    }
    tmpival = tmp->val;
    tmp = head;
    while(tmp && j) {
        j--;
        tmp = tmp->next;
    }
    tmpjval = tmp->val;
    tmp->val = tmpival;
    tmp = head;
    i = ti;
    while(tmp && i) {
        i--;
        tmp = tmp->next;
    }
    tmp->val = tmpjval;
}


struct node *Quick_Sort_List(struct node *head, int l, int r)
{
    int i, j;
    int jval;
    int pivot;
    i = l + 1;
    if (l + 1 < r) {
        pivot = get_lval(head, l);
        printf("Pivot = %d\n", pivot);
        for (j = l + 1; j <= r; j++) {
            jval = get_lval(head, j);
            if (jval < pivot && jval != -1) {
                swap(head, i, j);
                i++;
            }
        }
        swap(head, i - 1, l);
        Quick_Sort_List(head, l, i);
        Quick_Sort_List(head, i, r);
    }
    return head;
}

struct node *Sort_linkedlist(struct node *head)
{
    struct node *tmp = head;
    // Using Quick sort.
    int n = 0;

    while (tmp) {
        n++;
        tmp = tmp->next;
    }
    printf("n = %d\n", n);
    head = Quick_Sort_List(head, 0, n);
    return head;
}

void print_list(struct node *head)
{
    while(head) {
        printf("%d->", head->val);
        head = head->next;
    }
    printf("\n");
}

int _tmain(int argc, _TCHAR* argv[])
{
    struct node *head = NULL;
    struct node *shead = NULL;

    insert_node(&head, 10);
    insert_node(&head, 12);
    insert_node(&head, 9);
    insert_node(&head, 11);
    insert_node(&head, 7);
    insert_node(&head, 1);
    insert_node(&head, 3);
    insert_node(&head, 8);
    insert_node(&head, 5);
    insert_node(&head, 2);
    insert_node(&head, 4);
    insert_node(&head, 6);
    print_list(head);

    shead = Sort_linkedlist(head);
    print_list(shead);

    return 0;
}
于 2013-03-17T03:41:57.970 に答える
1

機能に問題がありsortListます。

この関数は、いくつかの大きなノードをリストの先頭に配置するだけです。すべてのリストをソートしているわけではありません。ファイルをソートするソートアルゴリズムを使用できます：クイックソート/バブルソート/ ...この回答の最後にソートを行うコードを配置します。

リストの並べ替えを行うコードは次のとおりです。

// 最大のノードを最初のノードに置き換えてから、サブリスト (リストの最初の要素) で同じ操作を行います

NodePtr sortList(NodePtr list) 
{

// 
if(list == null || list->next == null)
    return list; // the list is sorted.

//replace largest node with the first : 

//1- find largest node : 
NodePtr curr, largest,largestPrev;
curr = list;
largest = list;
prev = list;
largestPrev = list;
while(curr != NULL) {
        if(curr->num > largest->num) {
            largestPrev = prev;
            largest = curr;
        }
        prev = curr;
        curr = curr->next;

    }
//largest node is in largest. 

//2- switching firt node and largest node : 
NodePtr tmp;
if(largest != list)
{
    largestPrev->next = list;
    tmp = list->next;
    list->next = largest->next;
    largest->next = tmp;
}

// now largest is the first node of the list.

// calling the function again with the sub list :
//            list minus its first node :
largest->next = sortList(largest->next);


return largest;
}
于 2012-08-05T10:28:21.347 に答える
0

あなたに書くことによってlargest->next上書きされcurr->nextました。そのため、常に上から再起動することになります。

次のことを確認してください。

  1. リストは一貫したままです
  2. リスト反復子は一貫性を保ちます

しかし、全体として、あなたのコードはひどく壊れているようです.ソートロジックには他にもいくつかのエラーがあると思います.

于 2012-08-05T03:31:57.437 に答える