1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 |
/*基数排序,单向链表实现*/ /*时间复杂度:O(P(N+B)),P:排序趟数,N元素个数,B桶数*/ #include <stdio.h> #include <math.h> #include <stdlib.h> #include <time.h> typedef struct ptrNode { int element; struct ptrNode *next; }Node; typedef Node Head; typedef Node *List; void printList(List L) { if(L == NULL) { printf("Null List\n"); return; } List p = L; while(p->next != NULL) { printf("%d ", p->next->element); p = p->next; } printf("\n\n"); } void radixSort(List L, int n) { int r, i, j; List p, b; /*定义10个桶*/ Node N[10]; for(j = 0; j < n; j++ ) { /*桶初始化为空*/ for( i = 0; i < 10; i++) N[i].next = NULL; p = L->next; while( p != NULL ) { /*获取个,十,百位*/ r = (int)(p->element / pow(10, j)) % 10; /*将b指向对应桶的链表尾端*/ b = &N[r]; while( b->next != NULL ) b = b->next; b->next = p; //链接到对应桶最末尾元素 p = p->next; //p指向下一个链表元素 b->next->next = NULL; //对应桶中末尾元素指向NULL } /*将桶中元素链接回List, 注意只要将首节点链接过去 * 即可,之后定位到末尾元素再链接下一个桶*/ p = L; for( i = 0; i < 10; i++ ) { /*如果桶不为空*/ if( N[i].next != NULL ) { p->next = N[i].next; /*将p指向链表尾端*/ while( p->next != NULL ) p = p->next; } } } } int main(int argc, char **argv) { List tmp; //指向新申请内存指针 Head head; //此为结构体变量,不是指针,作为头部 List p = &head; //p 为指针,时刻指向链表末尾 srand(time(NULL)); p->next = NULL; /*随机生成10个3位数的整数*/ for( int i = 0; i < 10; i++ ) { tmp = malloc(sizeof(struct ptrNode)); tmp->element = rand() % 1000; tmp->next = NULL; printf("Get element = %d\n", tmp->element); p->next = tmp; //链接结构体到链表 p = tmp; //p移动至链表末尾 } printf("\nBefore sort:\n"); printList(&head); radixSort(&head, 3); printf("After radixSort:\n"); printList(&head); p = head.next; while( p != NULL ) { tmp = p->next; free(p); p = tmp; } return 0; } |