写出以下程序(1)利用实验一建立有序表，采用折半查找实现某一已知的关键字的查找。（2）已知散列函数为H(key)=key%p(p为自定的常数)，冲突处理方法为线性探测法实现散列表的建立(利用插入算法实现)，并输出某一关键字(自己给定)的查找结果及探测次数。

(1)折半查找实现有序表查找：

#include <stdio.h>

#define MAXSIZE 100

typedef struct {
    int key; //关键字，假设为整数类型
    //其他数据项
} RecordType;

typedef struct {
    RecordType r[MAXSIZE+1]; //r[0]不使用
    int length; //记录长度
} SqList;

//折半查找
int BiSearch(SqList L, int key) {
    int low = 1, high = L.length, mid;
    while (low <= high) {
        mid = (low + high) / 2;
        if (L.r[mid].key == key) {
            return mid;
        } else if (L.r[mid].key < key) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return 0; //查找失败
}

int main() {
    SqList L;
    L.length = 5;
    L.r[1].key = 1;
    L.r[2].key = 3;
    L.r[3].key = 5;
    L.r[4].key = 7;
    L.r[5].key = 9;

    int key = 5;
    int pos = BiSearch(L, key);
    if (pos) {
        printf("查找成功，位置为%d\n", pos);
    } else {
        printf("查找失败\n");
    }

    return 0;
}

(2)线性探测法实现散列表的建立：

#include <stdio.h>

#define MAXSIZE 100

typedef struct {
    int key;
    //其他数据项
} DataType;

typedef struct {
    DataType ht[MAXSIZE]; //散列表数组
    int size; //散列表的大小
} HashTable;

//散列函数
int Hash(int key, int p) {
    return key % p;
}

//插入
void Insert(HashTable *H, DataType data) {
    int i = Hash(data.key, H->size); //计算散列地址
    while (H->ht[i].key != 0) { //发生冲突
        i = (i+1) % H->size; //线性探测
    }
    H->ht[i] = data;
}

//查找
int Search(HashTable H, int key) {
    int i = Hash(key, H.size); //计算散列地址
    int cnt = 0; //探测次数
    while (H.ht[i].key != key && H.ht[i].key != 0) { //发生冲突
        i = (i+1) % H.size; //线性探测
        cnt++;
    }
    if (H.ht[i].key == key) {
        printf("查找成功，位置为%d，探测次数为%d\n", i, cnt);
        return i;
    } else {
        printf("查找失败，探测次数为%d\n", cnt);
        return -1;
    }
}

int main() {
    HashTable H;
    H.size = 10; //散列表大小为10

    //插入数据
    DataType data;
    data.key = 1;
    Insert(&H, data);
    data.key = 3;
    Insert(&H, data);
    data.key = 5;
    Insert(&H, data);
    data.key = 7;
    Insert(&H, data);
    data.key = 9;
    Insert(&H, data);

    //查找数据
    int key = 5;
    Search(H, key);

    return 0;
}