标题：基数排序
出处：Felix021
时间：Wed, 04 Nov 2009 00:57:09 +0000
作者：felix021
地址：https://www.felix021.com/blog/read.php?1753

内容：
好久没有写了，写错了好久，后来发现是挂在指针上了，真杯具。
#include <stdio.h>
#include <stdlib.h>
#ifdef __GNUC__
    #define WARN_IF_UNUSED __attribute__ ((warn_unused_result))
#else
    #define WARN_IF_UNUSED
#endif


struct node {
    int v;
    struct node *next;
};

struct linklist {
    struct node *head;
    struct node *tail;
};

WARN_IF_UNUSED int init(struct linklist ll[], int n) {
    int i;
    for (i = 0; i < n; ++i) {
        ll[i].head = (struct node *)malloc(sizeof(struct node)); 
        if (ll[i].head == NULL) {
            return 0;
        }
        ll[i].head->next = NULL;
        ll[i].tail = ll[i].head;
    }
    return 1;
}

void dump(struct linklist *ll) {
    struct node *p = ll->head->next;
    while (p != NULL) {
        printf("%d ", p->v);
        p = p->next;
    }
    printf("\n");
}

WARN_IF_UNUSED int push(struct linklist *ll, int v) {
    struct node *p = (struct node *)malloc(sizeof(struct node)); 
    if (p == NULL) {
        return 0;
    }
    p->v = v;
    p->next = NULL;
    ll->tail->next = p;
    ll->tail = p;
    return 1;
}

int isEmpty(struct linklist *ll) {
    return (ll->head->next == NULL) ? 1 : 0;
}


int pop(struct linklist *ll) {
    if (isEmpty(ll)) {
        exit(1);
    }
    struct node *p = ll->head;
    ll->head = p->next;
    free(p);
    return ll->head->v;
}

void radixSort(int a[], int n) {
    struct linklist ll[10];
    int flag, i, j, t, fact = 1;
    if (init(ll, 10) == 0) {
        exit(2);
    }
    do {
        printf("---------------\n");
        flag = 0;
        for (i = 0; i < n; ++i) {
            t = a[i] / fact % 10;
            flag += !!t;
            //printf("%d: %d\n", a[i], t);
            if (push(&ll[t], a[i]) == 0) {
                exit(2);
            }
        }
        for (i = 0, j = 0; i < 10; ++i) {
            printf("%d: ", i);
            dump(&ll[i]);
        }
        for (i = 0, j = 0; i < 10; ++i) {
            while (isEmpty(&ll[i]) == 0) {
                a[j] = pop(&ll[i]);
                j++;
            }
        }
        fact *= 10;
    }while (flag != 0);
}

int main() {
    int a[] = {26,62,187,32,8754359,45324,54654,0,331,321312,12,4324,87,98};
#define N (sizeof(a) / sizeof(int))
    radixSort(a, N);
    int i;
    for (i = 0; i < N; ++i) {
        printf("%d ", a[i]);
    }
    printf("\n");
    return 0;
}



Generated by Bo-blog 2.1.0