ShareVB
|
salut,
le pire c'est ce que je croyait jusqu'à ce que je tombe sur un article qui parlait des listes chainées dans la glib...et en fait on peut faire du quicksort sur une liste chainéé...niveau perf ca doit pas forcément être nickel...mais bon : voici un code que j'ai fait pendant un cours de C...
note : ce code reproduit à peut près les list_head doublement chainées du noyau linux...très astucieux dans le principe : un inclu dans la liste dans les données et non les données dans la liste...
désolé pour la longueur que ca va donner :
dans main.c :
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include "list_head.h"
struct test {
int az;
double er;
char m;
LIST_ENTRY(l);
};
LIST_HEAD(test);
int compare(struct list_entry * e1,struct list_entry * e2)
{
struct test *t1 = LIST_GET(e1,test,l);
struct test *t2 = LIST_GET(e2,test,l);
return (t1->m > t2->m ? 1 : -1);
}
int main()
{
struct list_entry *p;
struct list_entry *p2;
struct test *t;
int i;
LIST_INIT(b);
for (i = 0;i < 15;i++)
{
int j = rand() % 15;
t = (struct test *)malloc(1 * sizeof(struct test));
t->az = j;
t->er = j;
t->m = 'a'+j;
LIST_INSERT_FIRST(b,t,test,l);
}
LIST_REMOVE_FIRST(b);
p = b.first;
while (p)
{
struct test *tp = LIST_GET(p,test,l);
printf("%d %lf %c\n",tp->az,tp->er,tp->m);
p2 = p;
p=p->next;
}
printf("---\n");
b.first = list_head_sort(b.first,compare);
p = b.first;
while (p)
{
struct test *tp = LIST_GET(p,test,l);
printf("%d %lf %c\n",tp->az,tp->er,tp->m);
p2 = p;
p=p->next;
}
printf("---\n");
while (p2)
{
struct test *tp = LIST_GET(p2,test,l);
printf("%d %lf %c\n",tp->az,tp->er,tp->m);
p2=p2->prev;
}
system("pause");
}
dans list_head.h :
#ifndef _LIST_HEAD_H_
#define _LIST_HEAD_H_
//store the needed element to be a double-linked list
struct list_entry {
struct list_entry *next;
struct list_entry *prev;
};
//get the offset of the member m in the struct t
#define OFFSET(t,m) (int)&(((struct t *)0)->m)
//get the offset of the member m in the struct pointed by p
#define OFFSET2(p,m) (int)((int)&((p)->m)-(int)(p))
//get the pointer to the beginning of the struct t given a pointer p to the member m
#define BASE_OF(p,t,m) (struct t *)((unsigned char *)p - OFFSET(t,m))
//declare a member m to make a struct a linked list with list_head
#define LIST_ENTRY(m) \
struct list_entry m
//insert at the beginning of h, the element pointed by p of type t* which contains a member m of type struct list_entry
#define LIST_INSERT_FIRST(h,p,t,m) \
(p)->m.prev = 0; \
(p)->m.next = h.first; \
(h).first = (struct list_entry *)((unsigned char*)(p)+OFFSET(t,m)); \
if ((p)->m.next) \
((p)->m.next)->prev = h.first;
//insert element pointed by p after element pointed by p2 given the member m is the list_entry struct
#define LIST_INSERT_AFTER(p,p2,m) \
(p)->m.prev = &((p2)->m); \
(p)->m.next = (p2)->m.next; \
(p2)->m.next = &((p)->m); \
if ((p)->next) \
(p)->next->prev = &((p)->m)
//insert element pointed by p before element pointed by p2 given the member m is the list_entry struct
#define LIST_INSERT_BEFORE(p,p2,m) \
(p)->m.prev = (p2)->m.prev; \
(p)->m.next = &((p2)->m); \
(p2)->m.prev = &((p)->m); \
if ((p)->prev) \
(p)->prev->next = &((p)->m)
//remove element p given the member m is the list_entry struct
#define LIST_REMOVE(p,m) \
if ((p)->m.prev) \
(p)->m.prev->next = (p)->m.next; \
if ((p)->m.next) \
(p)->m.next->prev = (p)->m.prev; \
//remove the first element of h given the member m is the list_entry struct
#define LIST_REMOVE_FIRST(h) \
if (h.first->next) \
h.first->next->prev = 0; \
h.first = h.first->next
//declare the list head struct whose first points to the first element of the list
#define LIST_HEAD() \
struct list_head { \
struct list_entry *first; \
}
//init a variable b to be a list_head
#define LIST_INIT(b) \
struct list_head b; b.first = 0
//get the pointer to the beginning of the struct t (data) given a pointer p to the member m
#define LIST_GET(p,t,m) \
BASE_OF(p,t,m)
/*
* sort the list list with help of compare function
* list : list to sort
* compare : compare function to compare to element of list
* return a pointer to the first element in sorted list (so to the sorted list)
*/
struct list_entry *list_head_sort(struct list_entry *list,int(*compare)(struct list_entry *,struct list_entry *));
#endif
dans un list_head.c :
#include "list_head.h"
/*
* take two lists l1 and l2 and sort/merge them with the compare function compare
* l1, l2 : list to sort/merge
* compare : compare function to compare to elements
*/
static struct list_entry *list_head_sort_merge(struct list_entry *l1,struct list_entry *l2,int(*compare)(struct list_entry *,struct list_entry *))
{
//l is used to insert elements at the end of the result list
//ret is the beginning of the return list
struct list_entry *l = 0,*ret = 0;
//e is the element to insert to the result list
struct list_entry *e = 0;
//if no list to merge : return an empty list
if (!l1 && !l2)
return 0;
//as long as we have an element in one of the lists
while (l1 && l2)
{
//compare the current element of each list
if (compare(l1,l2) > 0)
{
//element in l1 is greater than element in l2
//so process l2
e = l2;
//pass to the next element of l2 since we will remove the current
l2 = l2->next;
}
else
{
//element in l2 is greater than element in l1
//so process l1
e = l1;
//pass to the next element of l1 since we will remove the current
l1 = l1->next;
}
//if the result list is currently not empty
if (l)
//add the selected element at the end
l->next = e;
//else, e is the first element of the result list, so save it in the return value
else
ret = e;
//the previous element of the new last is the current end of the result list
e->prev = l;
//the next element of the new last does not exist
e->next = 0;
//the new current end element of result list is the last selected element
l = e;
}
//if there is elements yet in l1
if (l1)
{
//append it to the end of the result list
//if the result list is currently not empty
if (l)
//add l1 at the end
l->next = l1;
//else, l1 is the result list, so save it in the return value
else
ret = l1;
//link the rest list to the end of result list
l1->prev = l;
}
//if there is elements yet in l2
else
{
//append it to the end of the result list
//if the result list is currently not empty
if (l)
//add l2 at the end
l->next = l2;
//else, l2 is the result list, so save it in the return value
else
ret = l2;
//link the rest list to the end of result list
l2->prev = l;
}
return ret;
}
/*
* sort the list list with help of compare function
* list : list to sort
* compare : compare function to compare to element of list
* return a pointer to the first element in sorted list (so to the sorted list)
*/
struct list_entry *list_head_sort(struct list_entry *list,int(*compare)(struct list_entry *,struct list_entry *))
{
//if we have a list to sort
if (list)
{
//l1 : points to the middle of the list (skip one element at a time)
//l2 : points to the end of the list (skip two elements at a time)
struct list_entry *l1 = list,*l2 = l1->next;
//as long as we are not at list end
while (l2)
{
//l1 skip one element
l1 = l1->next;
//l2 skip two elements
l2 = l2->next;
l2 = (l2 ? l2->next : 0);
}
//split the two parts of the list (middle is pointed by l1)
if (l1->prev)
l1->prev->next = 0;
l1->prev = 0;
//if we have not only one element in list
if (l1 != list)
//process recursively the both part of list to sort locally
return list_head_sort_merge(list_head_sort(list,compare),list_head_sort(l1,compare),compare);
else
//else return the one cell list
return list;
}
else
return 0;
}
bonne prog
ShareVB
|