#include <stdio.h> #include <stdlib.h> #define container_of(ptr, type, mem)(type *)((unsigned long)ptr -(unsigned long)&((type *)NULL)->mem) struct person { struct person *next; struct person *pre; }; struct boy { struct person p; int age; }; struct person *creat(struct person *head, int age); struct person *choose_sort(struct person *head); struct person *insert_sort(struct person *head); void show(struct person *head); int main() { struct person *head = NULL; head = creat(head, 30); head = creat(head, 20); head = creat(head, 25); head = creat(head, 80); head = creat(head, 60); head = creat(head, 40); head = insert_sort(head); show(head); } struct person *creat(struct person *head, int age) { struct boy *tmp = NULL; struct person *find = NULL; tmp = (struct boy *)malloc(sizeof(struct boy)); tmp->age = age; tmp->p.next = NULL; tmp->p.pre = NULL; if(NULL == head) { head = &tmp->p; head->next = head; head->pre = head; return head; } find = head; while(find->next != head) { find = find->next; } find->next = &tmp->p; tmp->p.pre = find; tmp->p.next = head; head->pre = &tmp->p; return head; } #if 0 struct person *choose_sort(struct person *head) { struct person *tmp = NULL; struct boy *min = NULL; struct person *newhead = NULL; struct person *tail = NULL; struct boy *find = NULL; while(head) { tmp = head; min = container_of(head, struct boy, p); do { find = container_of(tmp, struct boy, p); if(find->age < min->age) { min = find; } tmp = tmp->next; } while(tmp != head); struct person *min_p = &min->p; if(min_p == head && head->next != head) { head = head->next; head->pre = min_p->pre; min_p->pre->next = head; min_p->pre = NULL; min_p->pre = NULL; } else { if(min_p == head && head->next == head) { head->next = NULL; head->pre = NULL; head = head->next; } else { min_p->pre->next = min_p->next; min_p->next->pre = min_p->pre; min_p->next = NULL; min_p->pre = NULL; } } if(NULL == newhead) { newhead = min_p; newhead->next = newhead; newhead->pre = newhead; tail = newhead; continue; } tail->next = min_p; min_p->pre = tail; min_p->next = newhead; newhead->pre = min_p; tail = min_p; } return newhead; } #else struct person *choose_sort(struct person *head) { struct person *tmp = NULL; struct boy *min = NULL; struct person *newhead = NULL; struct person *tail = NULL; struct boy *find = NULL; while(head) { tmp = head; min = container_of(head, struct boy, p); do { find = container_of(tmp, struct boy, p); if(find->age < min->age) { min = find; } tmp = tmp->next; } while(tmp != head); if(&min->p == head && head->next != head) { head = head->next; head->pre = min->p.pre; min->p.pre->next = head; min->p.pre = NULL; min->p.next = NULL; } else { if(&min->p == head && head->next == head) { head->next = NULL; head->pre = NULL; head = head->next; } else { min->p.pre->next = min->p.next; min->p.next->pre = min->p.pre; min->p.next = NULL; min->p.pre = NULL; } } if(NULL == newhead) { newhead = &min->p; newhead->next = newhead; newhead->pre = newhead; tail = newhead; continue; } tail->next = &min->p; min->p.pre = tail; min->p.next = newhead; newhead->pre = &min->p; tail = &min->p; } return newhead; } #endif struct person *insert_sort(struct person *head) { struct boy *tmp = NULL; struct boy *new = NULL; struct person *find = NULL; struct person *list = NULL; struct person *newhead = NULL; struct person *tail = NULL; struct boy *key = NULL; while(head) { find = head; tmp = container_of(find, struct boy, p); if(head->next == head) { head->next = NULL; head = head->next; find->pre = NULL; } else { head = head->next; head->pre = find->pre; find->pre->next = head; find->pre = NULL; find->next = NULL; } if(NULL == newhead) { newhead = find; newhead->pre = newhead; newhead->next = newhead; continue; } new = container_of(newhead, struct boy, p); if(tmp->age < new->age) { find->next = newhead; find->pre = newhead->pre; newhead->pre->next = find; newhead->pre = find; newhead = find; continue; } list = newhead; do { key = container_of(list, struct boy, p); if(key->age > tmp->age) break; list = list->next; } while(list != newhead); if(key->age < tmp->age) { list->next = find; find->pre = list; find->next = newhead; newhead->pre = find; } else { find->next = list; find->pre = list->pre; list->pre->next = find; list->pre = find; } } return newhead; } void show(struct person *head) { struct person *tmp = NULL; struct boy *find = NULL; tmp = head; do { find = container_of(tmp, struct boy, p); printf("age is %d ", find->age); tmp = tmp->next; } while(tmp != head); printf("------------------------------------- "); do { find = container_of(tmp, struct boy, p); printf("age is %d ", find->age); tmp = tmp->pre; } while(tmp != head); }