Сортировка двойного связанного списка по возрастанию - PullRequest
Новая
       59

Сортировка двойного связанного списка по возрастанию

0 голосов
/ 26 марта 2020

Я работал над школьным проектом и столкнулся с этой проблемой.

Я пытаюсь сохранить список с помощью mallo c, но этот фрагмент кода, похоже, не работает. 

column_t *sorted_insert(column_t *lst, char col3[MAX_SIZE], long int rep){

if (!lst || rep < lst->rep)
{
    column_t *new = (column_t*) malloc(sizeof(column_t));
    strcpy(new->col3, col3);
    new->rep = rep;
    new->next = lst;
    new->previous = NULL;
    lst = new;
    if (lst->next)
        lst->next->previous = new;
}else
{
    lst->next = sorted_insert(lst->next,col3,rep);
    lst->next->previous = lst;
}

return lst;
}

Пытался вызвать функцию: 

sorted_insert(lst,"Test",0);
printf("%s",lst->col3);

И как нет выхода. Программа просто закрывается.

ОБНОВЛЕНИЕ @Vlad из Москвы 

column_t *sorted_insert(column_t *lst, char col3[MAX_SIZE], long int rep){

if (lst == NULL|| rep < lst->rep)
{
    column_t *new = malloc(sizeof(column_t));

    if (new != NULL)
    {
        strcpy(new->col3, col3);
        new->rep = rep;
        new->previous = NULL;
        new->next = lst;
        if (lst != NULL)
            lst->previous = new;

    }

    lst = new;
}else
{

    column_t *new = sorted_insert(lst->next, col3, rep);
    if (new != NULL)
    {
        lst->next = new;
        new->previous = lst;
    }

}

return lst;
}

Изменен вызов на: 

lst = sorted_insert(lst,tmp->col3,w);
display(lst);

Вывод:

enter image description here

Вывод списка правильный сейчас, но не отсортирован по возрастанию.

Ответы [ 2 ]

2 голосов
/ 26 марта 2020

Кажется, проблема в том, как вы вызываете функцию.

Вызов должен выглядеть следующим образом: 

column_t *lst = NULL;
lst = sorted_insert(lst,"Test",0);

Вот упрощенная демонстрационная программа, которая использует вашу функцию sorted_insert с небольшими изменениями и без учета элемента данных типа символьного массива. 

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

struct Node
{
    int data;
    struct Node *prev;
    struct Node *next;
};

struct Node * sorted_insert( struct Node *head, int data )
{
    if ( head == NULL || data < head->data )
    {
        struct Node *new_node = malloc( sizeof( struct Node ) );

        if ( new_node != NULL )
        {
            new_node->data = data;
            new_node->prev = NULL;
            new_node->next = head;
            if ( head != NULL ) head->prev = new_node;
        }

        head = new_node;
    }
    else
    {
        struct Node *new_node = sorted_insert( head->next, data );
        if ( new_node != NULL )
        {
            head->next = new_node;
            new_node->prev = head;
        }
    }

    return head;
}

void display( struct Node *head )
{
    for ( ; head != NULL; head = head->next )
    {
        printf( "%d -> ", head->data );
    }

    puts( "null" );
}

int main(void) 
{
    struct Node *head = NULL;

    const size_t N = 10;

    srand( ( unsigned int )time( NULL ) );

    for ( size_t i = 0; i < N; i++ )
    {
        head = sorted_insert( head, rand() % N );
        display( head );
    }

    return 0;
}

Его вывод может выглядеть как 

8 -> null
3 -> 8 -> null
3 -> 8 -> 9 -> null
1 -> 3 -> 8 -> 9 -> null
1 -> 1 -> 3 -> 8 -> 9 -> null
1 -> 1 -> 3 -> 6 -> 8 -> 9 -> null
1 -> 1 -> 3 -> 3 -> 6 -> 8 -> 9 -> null
1 -> 1 -> 3 -> 3 -> 4 -> 6 -> 8 -> 9 -> null
1 -> 1 -> 3 -> 3 -> 4 -> 5 -> 6 -> 8 -> 9 -> null
1 -> 1 -> 3 -> 3 -> 4 -> 5 -> 6 -> 8 -> 9 -> 9 -> null
0 голосов
/ 27 марта 2020

Предостережение: Поскольку кажется, что у вас все еще есть проблемы даже с ответом Влада, я придумала переработанную версию [которая может или не может быть тем, что вы хотели].

Я использую два списка. Добавьте необработанные входные строки в первый список, но просто увеличьте счетчик, если он дублирует существующую запись списка.

Итак, теперь у нас есть список, в котором есть один элемент для каждой уникальной строки и ее частота / количество повторений.

Затем переместите записи во второй список, отсортировав их по частоте.

Итак, вот код. Как я уже упоминал в моих комментариях, рекурсивное решение не масштабируется и, более того, медленнее. По крайней мере, это может помочь вам адаптировать вашу версию. YMMV ... 

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

#define MAX_SIZE    16

typedef struct column column_t;
struct column {
    column_t *next;
    column_t *prev;
    long rep;
    char col3[MAX_SIZE];
};

column_t *
newnode(char *col3)
{
    column_t *new = malloc(sizeof(column_t));

    strcpy(new->col3,col3);

    new->prev = NULL;
    new->next = NULL;

    new->rep = 1;

    return new;
}

// addnode -- add string to basic list
column_t *
addnode(column_t *head,char *col3)
{
    column_t *cur;
    column_t *prev;
    column_t *new;

    do {
        // add to empty list
        if (head == NULL) {
            new = newnode(col3);
            head = new;
            break;
        }

        // find matching node for string
        prev = NULL;
        for (cur = head;  cur != NULL;  cur = cur->next) {
            if (strcmp(cur->col3,col3) == 0)
                break;
            prev = cur;
        }

        // increment count on existing node
        if (cur != NULL) {
            cur->rep += 1;
            break;
        }

        // append to tail of list
        new = newnode(col3);
        prev->next = new;
        new->prev = prev;
    } while (0);

    return head;
}

column_t *
sorted_insert(column_t *head,column_t *new)
{
    column_t *cur;
    column_t *prev;

    do {
        new->next = NULL;
        new->prev = NULL;

        // add to empty list
        if (head == NULL) {
            head = new;
            break;
        }

        // find next higher node count
        prev = NULL;
        for (cur = head;  cur != NULL;  cur = cur->next) {
            if (cur->rep > new->rep)
                break;
            prev = cur;
        }

        // insert before a node that is higher
        if (cur != NULL) {
            prev = cur->prev;

            if (prev != NULL)
                prev->next = new;

            new->prev = prev;
            new->next = cur;

            // inserting before the head of the list
            if (cur == head)
                head = new;
            break;
        }

        // new node is higher than all -- append to tail of list
        new->prev = prev;
        if (prev != NULL)
            prev->next = new;
    } while (0);

    return head;
}

void
listprint(column_t *head,const char *tag)
{
    column_t *cur;

    for (cur = head;  cur != NULL;  cur = cur->next)
        printf("%s %s - %ld\n",tag,cur->col3,cur->rep);
}

int
main(void)
{
    column_t *orig = NULL;
    char *input[] = {
        "DA", "DA",
        "JL",
        "FF",
        "JD",
        "FF",
        "PQ", "QP",
        "QP", "QP", "QP",
        NULL
    };

    for (char **str = input;  *str != NULL;  ++str)
        orig = addnode(orig,*str);

    listprint(orig,"ORIG");

    column_t *sorted = NULL;
    column_t *next;
    for (;  orig != NULL;  orig = next) {
        next = orig->next;
        sorted = sorted_insert(sorted,orig);
    }

    listprint(sorted,"SORT");

    return 0;
}
...