1

Реализую сортировку списка вставками. Пример такой сортировки подсмотрел здесь же и переделал под свой список. Вот сортировка:

void sort(list *root){
    list *p, *key;
    list *result = root;
    root = root->next;      /* Головой стал следующий элемент */
    result->next = NULL;    /* Первый элемент отсортированного списка */

    while(root->next != NULL){
        key = root;
        root = root->next;
        if(key->data < result->data){   /* Вставляем результат в голову */
            key->next = result;
            result = key;
        }else{
            p = result;
            while(p->next != NULL){     /* Бежим по уже сформированному результату */
                if(p->next->data > key->data)
                    break;
                p = p->next;
            }
            key->next = p->next;
            p->next = key;
        }
    }
    root = result;
}

Создается он таким способом:

struct list* create(int a){
    struct list *root;
    root = (struct list*)malloc(sizeof(struct list));
    root->data = a;
    root->next = NULL;
    return root;
}

Все остальное можно посмотреть здесь для экономии места: https://ideone.com/qAKlIl

Список используется в такой задаче: надо заполнить его элементами определенной последовательности и измерить время сортировки. Результаты реализации этого списка потребуются при написании карманной сортировки. Поэтому я не уверен, правильно ли я реализовал список, в особенности его создание и сортировку. Для создания нужно знать значение, которое будет храниться в голове списка. Мне это не очень нравится. Можно обойтись как-то без инициализации при создании, а записывать данные в элементы уже непосредственно при заполнении списка последовательностью?

Сортировка мне тоже не нравится. Вот, например, заполняем список так:

for(int i = 1; i < 10; i++){
    //temp = addelem(temp, i);
    push(root, i*16 % 9);
}

Здесь push - это добавление в конец списка, root - голова, созданная так:

root = create(0);

То есть список содержит два ноля: один в голове и один где-то еще. Это видно по результату printlist. Но после сортировки printlist показывает только один ноль. Что произошло?

И еще: почему компилятор чистого си ругается на это определение элемента?

struct list{
    int data;
    list *next;
};

В С++ программа компилируется нормально, а компилятор си выдает ошибки. Думаю, не зря в си список определяется при помощи typedef и имени структуры в конце, но я еще не дочитал K&R до того места, где про это рассказывается.

1
  • 1
    Ругается потому, что в чистом си нужно писать не list * next, а struct list * next, либо делать typedef.
    – insolor
    31 авг 2015 в 21:30

1 ответ 1

4

В C вы должны указывать ключевое слово struct перед именем структуры. Имена обычных идентификаторов и имена структур находятся в различных пространствах имен именно благодаря обязательному указанию ключевого слова struct.

Поэтому вы должны написать

struct list{
    int data;
    struct list *next;
};

Иначе компилятор сообщит, что имя list не объявлено.

Функция сортировки неверная, так как уже в первых строчках функции

void sort(list *root){
    list *p, *key;
    list *result = root;
    root = root->next; 
    //...

вы обращаетесь к полю next, не проверяя при этом, равен ли нулю указатель root.

Также имеются проблемы с логикой работы функции. Представьте, что список имеет два элемента:

         ---------------     ---------------
root --->| node1 | next| --->| node2| NULL | 
         ---------------     ---------------

В этом случае вы положили result равным root

list *result = root;

А root положили равным root->next

root = root->next;

То есть получилась следующая картина

           ---------------
result --->| node1| NULL | 
           ---------------
           ---------------
root   --->| node2| NULL | 
           ---------------

Далее у вас идет цикл

while(root->next != NULL){
    //...
}

Так как теперь root->next равен NULL, то цикл ни разу не выполняется.

В результате функция просто завершает сою работу

   //... 
   root = result;
}

Однако узел node2 так и не попал в новый отсортированный список. Он просто "потерялся".

Вы можете использовать в качестве примера следующую демонстрационную программу

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

struct list
{
    int data;
    struct list *next;
};

struct list * insert( struct list *node, int data )
{
    struct list *tmp = malloc( sizeof( struct list ) );

    if ( tmp != NULL )
    {
        tmp->data = data;

        if ( node != NULL )
        {
            tmp->next = node->next;
            node->next = tmp;
        }
        else
        {
            tmp->next = NULL;
        }
    }

    return tmp;
}

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

struct list * clear( struct list *node )
{
    while ( node != NULL )
    {
        struct list *tmp = node;
        node = node->next;

        free( tmp );
    }

    return node;
}

struct list * sort( struct list *root )
{
    struct list *new_root = NULL;

    while ( root != NULL )
    {
        struct list *node = root;
        root = root->next;

        if ( new_root == NULL || node->data < new_root->data )
        {
            node->next = new_root;
            new_root = node;
        }
        else
        {
            struct list *current = new_root;
            while ( current->next != NULL && !( node->data < current->next->data ) )
            {                   
                  current = current->next;
            }                

            node->next = current->next;
            current->next = node;
        }
    }

    return new_root;
}

#define N   10

int main()
{
    int a[N] = { 7, 3, 2, 1, 0, 0, 0, 5, 9, 4 };
    struct list *root = NULL;
    struct list **tmp = &root;

    for ( size_t i = 0; i < N; i++ )
    {
        *tmp = insert( *tmp, a[i] );
        tmp = &( *tmp )->next;
    }

    display( root );
    printf( "\n" );

    root = sort( root );

    display( root );
    printf( "\n" );

    root = clear( root );
}    

Ее вывод на консоль следующий:

7 3 2 1 0 0 0 5 9 4 
0 0 0 1 2 3 4 5 7 9 
2
  • "Поэтому вы должны написать Иначе компилятор сообщит, что имя List не объявлено." Сделал так, как вы сказали, но ошибки не исчезли. Компилятор перестал ругаться на определение структуры, зато ему не понравились определения функций. Typedef решил проблему. Читаю дальше сообщение.
    – typemoon
    31 авг 2015 в 21:41
  • 1
    @typemoon Это всего лишь означает, что вы не везде поставили ключевое слово struct перед именем структуры в своей программе. 31 авг 2015 в 21:42

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.