Реализую сортировку списка вставками. Пример такой сортировки подсмотрел здесь же и переделал под свой список. Вот сортировка:
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 до того места, где про это рассказывается.
list * next
, аstruct list * next
, либо делатьtypedef
.