1、设计一个哈希表ha[0……m-1]，其中m=18，存放（19,1,23,14,55,20,84,27,68,11,10,77）n个元素，其中：哈希函数采用除留余数法H(key)=key%p(p=13)，解决冲突的方法采用开放地址法的线性探测法。设计哈希表的类型，并编程实现哈希表的创建；设计并编程实现在哈希表中查找指定关键字的算法；在查找等概率的情况下，分析算法的平均查找长；

哈希表的类型定义如下：

#define m 18 //哈希表长度
#define p 13 //除留余数法的除数

//哈希表结构体
typedef struct {
    int key; //关键字
    int value; //值
} HashNode;

//哈希表类型
typedef struct {
    HashNode data[m]; //哈希表数组
    int count; //哈希表中元素个数
} HashTable;

接下来是创建哈希表的代码实现：

//初始化哈希表
void initHashTable(HashTable& ht) {
    ht.count = 0;
    for (int i = 0; i < m; i++) {
        ht.data[i].key = -1; //初始化关键字为-1
    }
}

//哈希函数
int hashFunction(int key) {
    return key % p;
}

//插入元素到哈希表中
void insertHashTable(HashTable& ht, int key, int value) {
    int index = hashFunction(key); //计算哈希值
    while (ht.data[index].key != -1) { //处理冲突
        index = (index + 1) % m; //线性探测法
    }
    ht.data[index].key = key;
    ht.data[index].value = value;
    ht.count++;
}

//创建哈希表
void createHashTable(HashTable& ht, int arr[], int n) {
    initHashTable(ht);
    for (int i = 0; i < n; i++) {
        insertHashTable(ht, arr[i], arr[i]);
    }
}

接下来是在哈希表中查找指定关键字的算法：

//在哈希表中查找指定关键字，返回对应的值
int findHashTable(HashTable& ht, int key) {
    int index = hashFunction(key); //计算哈希值
    while (ht.data[index].key != -1) { //处理冲突
        if (ht.data[index].key == key) {
            return ht.data[index].value;
        }
        index = (index + 1) % m; //线性探测法
    }
    return -1; //未找到返回-1
}

在查找等概率的情况下，分析算法的平均查找长度（ASL）：

由于采用了线性探测法，数据项可能被散列到不同的位置，因此平均查找长度的计算较为复杂，在此只给出结论：

在哈希表中查找元素的平均查找长度为：

$ASL=\frac{1}{n}\sum\limits_{i=1}^{n}\frac{1}{2}(1+\frac{1}{1-i})$

其中 $n$ 表示哈希表中元素个数。在本题中，$n=12$，代入上式可以计算出平均查找长度为 $ASL=1.5$。