C语言实现汽车牌照数据的排序和快速查找，用链式基数排序方法和折半查找对汽车记录按关键字进行查找，完整代码

好的，以下是基于链式基数排序和折半查找实现汽车牌照数据排序和快速查找的完整代码：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// 定义车辆信息结构体
typedef struct car_info {
    char plate_number[8];  // 汽车牌照号码
    char owner_name[20];   // 车主姓名
    char brand[20];        // 汽车品牌
    int price;             // 汽车价格
} CarInfo;

// 定义链表节点结构体
typedef struct node {
    CarInfo car;           // 车辆信息
    struct node *next;     // 下一个节点指针
} Node;

// 定义哈希表结构体
typedef struct hash_table {
    int size;              // 哈希表大小
    Node **table;          // 存储节点指针的数组
} HashTable;

// 哈希函数：将牌照号码转换为哈希值
int hash(char *plate_number, int size) {
    int sum = 0;
    for (int i = 0; i < strlen(plate_number); i++) {
        sum += plate_number[i];
    }
    return sum % size;
}

// 初始化哈希表
HashTable *init_hash_table(int size) {
    HashTable *hash_table = (HashTable *) malloc(sizeof(HashTable));
    hash_table->size = size;
    hash_table->table = (Node **) malloc(sizeof(Node *) * size);
    for (int i = 0; i < size; i++) {
        hash_table->table[i] = NULL;
    }
    return hash_table;
}

// 创建节点
Node *create_node(CarInfo car) {
    Node *node = (Node *) malloc(sizeof(Node));
    node->car = car;
    node->next = NULL;
    return node;
}

// 向哈希表中插入节点
void insert_node(HashTable *hash_table, CarInfo car) {
    int index = hash(car.plate_number, hash_table->size);
    Node *node = hash_table->table[index];
    if (node == NULL) {
        hash_table->table[index] = create_node(car);
    } else {
        while (node->next != NULL) {
            node = node->next;
        }
        node->next = create_node(car);
    }
}

// 从哈希表中查找节点
Node *find_node(HashTable *hash_table, char *plate_number) {
    int index = hash(plate_number, hash_table->size);
    Node *node = hash_table->table[index];
    while (node != NULL) {
        if (strcmp(node->car.plate_number, plate_number) == 0) {
            return node;
        }
        node = node->next;
    }
    return NULL;
}

// 销毁哈希表
void destroy_hash_table(HashTable *hash_table) {
    for (int i = 0; i < hash_table->size; i++) {
        Node *node = hash_table->table[i];
        while (node != NULL) {
            Node *temp = node;
            node = node->next;
            free(temp);
        }
    }
    free(hash_table->table);
    free(hash_table);
}

// 获取牌照号码的指定位上的数字
int get_digit(char *plate_number, int digit) {
    if (digit < strlen(plate_number)) {
        return plate_number[strlen(plate_number) - digit - 1] - '0';
    } else {
        return 0;
    }
}

// 链式基数排序
void radix_sort(HashTable *hash_table, int digit) {
    int counts[10] = {0};
    Node *buckets[10] = {NULL};
    for (int i = 0; i < hash_table->size; i++) {
        Node *node = hash_table->table[i];
        while (node != NULL) {
            int d = get_digit(node->car.plate_number, digit);
            if (buckets[d] == NULL) {
                buckets[d] = create_node(node->car);
            } else {
                Node *temp = buckets[d];
                while (temp->next != NULL) {
                    temp = temp->next;
                }
                temp->next = create_node(node->car);
            }
            node = node->next;
        }
    }
    for (int i = 0; i < 10; i++) {
        counts[i] = 0;
    }
    for (int i = 0; i < 10; i++) {
        Node *node = buckets[i];
        while (node != NULL) {
            int index = hash(node->car.plate_number, hash_table->size);
            Node *temp = hash_table->table[index];
            while (temp != NULL) {
                if (strcmp(temp->car.plate_number, node->car.plate_number) == 0) {
                    temp->car = node->car;
                    break;
                }
                temp = temp->next;
            }
            node = node->next;
        }
    }
    for (int i = 0; i < 10; i++) {
        Node *node = buckets[i];
        while (node != NULL) {
            Node *temp = node;
            node = node->next;
            free(temp);
        }
    }
    if (digit > 0) {
        radix_sort(hash_table, digit - 1);
    }
}

// 折半查找
Node *binary_search(HashTable *hash_table, char *plate_number) {
    int left = 0, right = hash_table->size - 1;
    while (left <= right) {
        int mid = (left + right) / 2;
        Node *node = hash_table->table[mid];
        while (node != NULL) {
            if (strcmp(node->car.plate_number, plate_number) == 0) {
                return node;
            } else if (strcmp(node->car.plate_number, plate_number) < 0) {
                node = node->next;
            } else {
                break;
            }
        }
        if (node == NULL || strcmp(node->car.plate_number, plate_number) > 0) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return NULL;
}

// 打印车辆信息
void print_car_info(CarInfo car) {
    printf("Plate number: %s, Owner name: %s, Brand: %s, Price: %d\n", car.plate_number, car.owner_name, car.brand, car.price);
}

int main() {
    // 初始化哈希表
    HashTable *hash_table = init_hash_table(100);

    // 构造车辆信息
    CarInfo car1 = {"A123456", "Tom", "Toyota", 200000};
    CarInfo car2 = {"B234567", "John", "Honda", 150000};
    CarInfo car3 = {"C345678", "Mary", "BMW", 300000};
    CarInfo car4 = {"D456789", "Lucy", "Audi", 250000};

    // 向哈希表中插入车辆信息
    insert_node(hash_table, car1);
    insert_node(hash_table, car2);
    insert_node(hash_table, car3);
    insert_node(hash_table, car4);

    // 链式基数排序
    radix_sort(hash_table, 6);

    // 折半查找
    Node *node1 = binary_search(hash_table, "A123456");
    Node *node2 = binary_search(hash_table, "C345678");

    // 打印查找到的车辆信息
    if (node1 != NULL) {
        print_car_info(node1->car);
    } else {
        printf("Car not found.\n");
    }
    if (node2 != NULL) {
        print_car_info(node2->car);
    } else {
        printf("Car not found.\n");
    }

    // 销毁哈希表
    destroy_hash_table(hash_table);

    return 0;
}

以上代码中，我们首先定义了车辆信息结构体和链表节点结构体，并使用哈希表来存储节点。在哈希表中，我们使用链式法解决哈希冲突，即当两个不同的牌照号码映射到同一个哈希值时，将它们放在同一个链表中。

然后，我们实现了哈希函数、初始化哈希表、创建节点、向哈希表中插入节点、从哈希表中查找节点、销毁哈希表等操作。其中，哈希函数使用了简单的取余方法，可以根据实际需求进行优化。

接着，我们实现了链式基数排序和折半查找。链式基数排序是基于哈希表的排序算法，可以根据汽车牌照号码的每一位进行排序。折半查找是一种高效的查找算法，可以在排序好的数组或链表中查找指定元素。

最后，我们构造了一些车辆信息，向哈希表中插入节点，并进行链式基数排序和折半查找。如果找到了指定的车辆信息，则打印其详细信息；否则输出“Car not found.”。最后，我们销毁哈希表，释放内存。

需要注意的是，以上代码仅供参考，实际应用中可能需要根据实际需求进行修改和优化。