@BigBobo, вот обещанный ответ.
Программка, которая делает двусвязный список и сортирует его,
вызывая функцию сортировки слиянием из list2.h (см. http://pastebin.com/EVwuTAiF)
Сортировка устойчивая, сложность O(N log N).
Особенностью этих списков является передача в функции манипулирования данными
не адреса пользовательской структуры а адреса ссылок на следующий/предыдущий
элементы списка, которые находятся внутри такой структуры.
Для доступа к данным по возвращаемому функциями из list2.h указателю используется макрос list_entry().
Такой подход позволяет обрабатывать заранее не известные в функциях работы
со списком структуры пользователя, а также размещать одну и ту же структуру
в разных списках (естественно, для каждого списка свои переменные связи).
// lisort.c test "list2.h" sorting functions
// gcc -std=gnu99 -I../include ...
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/time.h>
long long
mtime()
{
struct timeval t;
gettimeofday(&t, NULL);
long long mt = (long long)t.tv_sec * 1000 + t.tv_usec / 1000;
return mt;
}
#include "list2.h"
struct data1 {
int no;
char *val;
List2 list;
};
int cmp1 (List2 *p1, List2 *p2)
{
struct data1 *d1 = list_entry(p1, struct data1, list),
*d2 = list_entry(p2, struct data1, list);
return strcmp(d1->val, d2->val);
}
int cmp2 (const void *v1, const void *v2)
{
struct data1 *d1 = (typeof(d1))v1, *d2 = (typeof(d2))v2;
return strcmp(d1->val, d2->val);
}
void
print_data1_list (const char *msg, List2head *t)
{
puts(msg);
List2 *listitem;
struct data1 *p;
list2_for_each (listitem, t) {
p = list_entry(listitem, struct data1, list);
printf ("%d [%s]\n", p->no, p->val);
}
}
void
get_data1_list (const char *msg, List2head *t)
{
puts(msg);
char str[1000];
int i = 0;
struct data1 *p;
while (fgets(str, 1000, stdin)) {
str[strlen(str) - 1] = 0;
p = (typeof(p))malloc(sizeof(*p));
p->no = ++i;
p->val = strdup(str);
list2_add_tail(&p->list, t);
}
}
void
genlist (List2head *t, int n)
{
char str[100];
srand(0);
for (int i = 0; i < n; i++) {
sprintf(str, "%d", rand());
struct data1 *p = (typeof(p))malloc(sizeof(*p));
p->no = i + 1;
p->val = strdup(str);
list2_add_tail(&p->list, t);
}
}
void
fill_a (struct data1 a[], int n)
{
char str[100];
srand(0);
for (int i = 0; i < n; i++) {
sprintf(str, "%d", rand());
a[i].no = i + 1;
a[i].val = strdup(str);
}
}
#define N 1000000
int
main ()
{
LIST2_HEAD(t1);
get_data1_list("enter test1 strings (end ^D)", &t1);
print_data1_list("test1 source data", &t1);
list2_sort(&t1, cmp1);
print_data1_list("test1 sort (l_mergesort()) data", &t1);
INIT_LIST2_HEAD(&t1);
genlist(&t1, N);
long long mtime(), start = mtime();
list2_sort(&t1, cmp1);
printf ("list2_sort: %d %lld msec\n",
(int)list2_power(&t1), mtime() - start);
struct data1 *a = (typeof(a))malloc(sizeof(*a) * N);
fill_a(a, N);
start = mtime();
qsort (a, N, sizeof(*a), cmp2);
printf ("system qsort: %d %lld msec\n",
N, mtime() - start);
}
Пример использования
avp@avp-ubu1:~/src/dispro/BM/tst$ g++ -O2 -I ../include/ lisort.c
avp@avp-ubu1:~/src/dispro/BM/tst$ ./a.out
enter test1 strings (end ^D)
1
qq
a
qq
qq
test1 source data
1 [1]
2 [qq]
3 [a]
4 [qq]
5 [qq]
test1 sort (l_mergesort()) data
1 [1]
3 [a]
2 [qq]
4 [qq]
5 [qq]
list2_sort: 1000000 663 msec
system qsort: 1000000 602 msec
avp@avp-ubu1:~/src/dispro/BM/tst$
На всякий случай повторю тут функцию сортировки из list2.h
/*
* Слияние списков, завершающихся next == 0,
* в соответствии с fcmp(elem1, elem2) (returns N < 0, 0 for EQUAL or N > 0)
* l1, l2 указатели на первые элементы списков
* указатели prev становятся неактуальными
*/
static List2 *
merge2lists (List2 *l1, List2 *l2, int (*fcmp)(List2 *e1, List2 *e2))
{
List2 result = {0, 0}, *cur = &result;
while (l1 && l2)
if (fcmp(l1, l2) <= 0) {
cur->next = l1; cur = l1; l1 = l1->next;
} else {
cur->next = l2; cur = l2; l2 = l2->next;
}
cur->next = (l1 ? l1 : l2); // оставшиеся элементы запишем в хвост result
return result.next;
}
/*
* Сортировка списка по указателю на его первый элемент
* в соответствии с fcmp(elem1, elem2) (returns N < 0, 0 for EQUAL or N > 0)
* указатели prev становятся неактуальными
*/
static List2 *
l_mergesort (List2 *list, int (*fcmp)(List2 *e1, List2 *e2))
{
if (list == 0 || list->next == 0) return list;
List2 *a = list, *b = list->next;
// хитро делим список пополам. b бежит через элемент
while (b && b->next) {
list = list->next; b = b->next->next;
}
b = list->next;
list->next = 0; // разделим, terminate первую половину
return merge2lists(l_mergesort(a, fcmp), l_mergesort(b, fcmp), fcmp);
}
/*
* mergesort двусвязного списка
* в соответствии с fcmp(elem1, elem2) (returns N < 0, 0 for EQUAL or N > 0)
*/
static void
list2_sort (List2head *list, int (*fcmp)(List2 *e1, List2 *e2))
{
if (list->size < 2)
return;
List2 *slist = l_mergesort(list->head, fcmp), *p = 0;
list->head = slist;
// восстановим указатели prev
while (slist) {
slist->prev = p;
p = slist;
slist = slist->next;
}
list->tail = p;
}
Динамически выделяемую память я здесь просто не освобождаю. Вообще-то это надо делать.
Что непонятно, спрашивайте. Постараюсь объяснить.