. 算法设计题 已知待散列的线性表为（45，16，40，69，23，33，48，96，13，38），散列用的一维地址空间为[0..12]，假定选用的散列函数是H(K)= K mod 7，若发生冲突采用链地址法处理。（1）图形化展示线性表在散列表中的数据布局。（2）假设每一个元素的查找概率相等，求该散列表的平均查找长度。用c语言实现代码。

(1) 线性表在散列表中的数据布局如下图所示：

0 -> 48
1 -> 16 -> 23 -> 38 -> 96
2 -> 33
3 -> 45
4 -> 40
5
6 -> 69 -> 13

(2) 平均查找长度为：ASL = (n + ∑(di^2))/n，其中n为关键字个数，di为第i个链表的长度。

根据散列函数H(K)= K mod 7，可以得到散列表的桶数为7，因此n=10。

对于每个桶，可以计算出其链表的长度，如下所示：

Bucket 0: 1
Bucket 1: 4
Bucket 2: 1
Bucket 3: 1
Bucket 4: 1
Bucket 5: 0
Bucket 6: 2

因此，可以得到平均查找长度为：

ASL = (n + ∑(di^2))/n
    = (10 + (1^2 + 4^2 + 1^2 + 1^2 + 1^2 + 0^2 + 2^2))/10
    = 2.4

C语言实现代码如下：

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

#define BUCKET_SIZE 7

typedef struct node {
    int key;
    struct node *next;
} Node;

int hash(int key) {
    return key % BUCKET_SIZE;
}

void insert(Node *buckets[], int key) {
    int index = hash(key);
    Node *new_node = (Node *) malloc(sizeof(Node));
    new_node->key = key;
    new_node->next = NULL;

    if (buckets[index] == NULL) {
        buckets[index] = new_node;
    } else {
        Node *current = buckets[index];
        while (current->next != NULL) {
            current = current->next;
        }
        current->next = new_node;
    }
}

int search(Node *buckets[], int key) {
    int index = hash(key);
    Node *current = buckets[index];

    while (current != NULL) {
        if (current->key == key) {
            return 1;
        }
        current = current->next;
    }

    return 0;
}

int main() {
    Node *buckets[BUCKET_SIZE] = {NULL};
    int keys[] = {45, 16, 40, 69, 23, 33, 48, 96, 13, 38};
    int i, n = sizeof(keys) / sizeof(int);
    float asl = 0.0;

    for (i = 0; i < n; i++) {
        insert(buckets, keys[i]);
    }

    for (i = 0; i < BUCKET_SIZE; i++) {
        int di = 0;
        Node *current = buckets[i];
        while (current != NULL) {
            di++;
            current = current->next;
        }
        asl += di * di;
    }

    asl = (n + asl) / n;

    printf("ASL = %.1f\n", asl);

    return 0;
}