请教两个C语言数据结构与算法的问题，请看图，谢谢了

如题所述

推荐答案 2013-05-16

#include <stdio.h>
#include <stdlib.h>
int c = 0;
//int arr[] = {29, 10, 23, 24, 55, 20, 84, 27, 68, 11, 21, 77};
int store[15];
int hash(int a[], int len, int key)
{
    int k = -1;
    if (key < 0)
        return -1;

    k = key % 13;
    printf("%d %% 13: %d ", key, k);
    while(a[k++] != -1 && (k - 1) < len)
        ;
    if(k - 1 != key % 13)
        c++;
    printf("----> key: %d\n", k - 1);
    if (k >= len + 1)
        return -1;
    if (a[k - 1] == -1)
        return k - 1;
    return -1;
}
int count_sort(int a[], int len)
{
    int *target = NULL;
    int c[10 + 1] = {0}; // Base 0, 1, 2,... 10;
    int i;
    target = malloc(len * sizeof(int) + 1);
    for (i = 0; i < 10 + 1; i ++)
        c[i] = 0;
    for (i = 0; i < len; i ++)
        c[a[i]] ++;
    for (i = 0; i < 10 + 1; i ++)
        c[i + 1] += c[i];
    for (i = len - 1; i >= 0 ; i --)
        target[c[a[i]]--] = a[i];
    for (i = 0; i < len; i ++)
        a[i] = target[i + 1];
    free(target);
    return 0;
}
/*
* b[i] = a[i] % m;
*/
int count_sort2(int a[], int b[], int len)
{
    int *target = NULL;
    int c[10 + 1] = {0}; // Base 0, 1, 2,... 10;
    int i;
    target = malloc(len * sizeof(int) + 1);
    for (i = 0; i < 10 + 1; i ++)
        c[i] = 0;
    for (i = 0; i < len; i ++)
        c[b[i]] ++;
    for (i = 0; i < 10 + 1; i ++)
        c[i + 1] += c[i];
    for (i = len - 1; i >= 0 ; i --) {
        target[c[b[i]]--] = a[i];
    }
    for (i = 0; i < len; i ++)
        a[i] = target[i + 1];
    free(target);
    return 0;
}
int num_n(int n, int base, int id)
{
    int exp = 1;
    int i;
    for (i = 0; i < id - 1; i ++)
        exp *= base;
    return n % (exp * base) / exp;
}
int base_sort(int arr[], int len, int width)
{
    int i;
    int j;
    int *arr_b = NULL;
    int *arr_r = NULL;
    arr_b = malloc(len * sizeof(int));
    if (!arr_b) {
        printf("malloc err\n");
        return -1;
    }
    arr_r = malloc(len * sizeof(int));
    if (!arr_r) {
        printf("malloc err\n");
        free(arr_b);
        return -1;
    }
    for (i = 0; i < len; i ++)
        arr_b[i] = arr[i];
    for (j = 0; j < width; j++) {
        for (i = 0; i < len; i ++) {
            arr_r[i] = num_n(arr[i], 10, j + 1);
        }
        count_sort2(arr, arr_r, len);
    }
    free(arr_r);
    free(arr_b);
    return 0;
}
int main()
{
    int i;
    int arr[] = {503, 87, 512, 61, 908, 170, 897, 275, 653, 426};
    for (i = 0; i < sizeof(arr) / sizeof(int); i ++)
        printf("%d ", arr[i]);
    printf("\n----------\n");
    base_sort(arr, sizeof(arr) / sizeof(int), 1);
    for (i = 0; i < sizeof(arr) / sizeof(int); i ++)
        printf("%d ", arr[i]);
    printf("\n----------\n");
    base_sort(arr, sizeof(arr) / sizeof(int), 2);
    for (i = 0; i < sizeof(arr) / sizeof(int); i ++)
        printf("%d ", arr[i]);
    printf("\n----------\n");
    base_sort(arr, sizeof(arr) / sizeof(int), 3);
    for (i = 0; i < sizeof(arr) / sizeof(int); i ++)
        printf("%d ", arr[i]);
    printf("\n----------\n");
}