K
/users/15759/bigbobo Here's the answer.A program that makes a two-track list and sorts it,
Calling the merger function from list2.h (see annex). http://pastebin.com/EVwuTAiF) Steady, complex O(N log N).The specificity of these lists is the transfer to the data manipulation function.
not the user ' s address but the references to the following/former
List elements that are within such a structure.Macs list_entry() is used to access data on re-entry functions from list2.h.This approach allows for the processing of previously unknown work functions
with a user structure list, as well as the same structure
on different lists (naturally for each list its variables).// 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);
}
Example of useavp@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$
Just in case I repeat this sorting function from 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;
}
Dynamic memory I'm not free here. Actually, we should do that.What's not clear, ask. I'll try to explain.
,(3, 9, 12) / Main (1,2,3,4,5,6,8,9,12)
