---

第1关：实现折半查找

代码如下：

/*************************************************************date: April 2009copyright: Zhu EnDO NOT distribute this code.
**************************************************************/
//折半查找的顺序表 实现文件
//每个结点的数据是关键码
//
#include <stdio.h>
#include <stdlib.h>
#include "BSlist.h"BSeqList* BSL_Create(int size)
//创建一个顺序表
//与BSL_Free()配对
{BSeqList* blist=(BSeqList*)malloc(sizeof(BSeqList));blist->pkey = (int*)malloc(sizeof(int)*size);blist->max=size;blist->len=0;return blist;
}void BSL_Free(BSeqList* blist)
//释放/删除顺序表
//与BSL_Create()配对
{free(blist->pkey);free(blist);
}int BSL_FindKey(BSeqList* blist, int key)
//在排序的顺序表中查找关键码值为key的结点，返回结点的编号
//返回值大于等于0时表示找到值为key的结点的编号，-1表示没有找到
{/*请在BEGIN和END之间实现你的代码*//*****BEGIN*****/int k = 0;int r = blist->len - 1;while (k <= r) {int m = (k + r) / 2;if (key == blist->pkey[m]) {return m;} else if (key < blist->pkey[m]) {r = m - 1;} else {k = m + 1;}}return -1;/******END******//*请不要修改[BEGIN,END]区域外的代码*/
}int BSL_InsKey(BSeqList* blist, int key)
//在排序的顺序表中插入一个值为key的结点
//返回值大于等于0时表示插入的位置, -1表示表满（无法插入）
{if (blist->len>=blist->max) return -1;int k, r, m;k=0; r=blist->len-1;//寻找插入位置while (k<=r) {m=(k+r)>>1; //m=(k+r)/2if (key == blist->pkey[m]) return -2;若不允许插入已存在的值，则需要此行if (key<blist->pkey[m])  r=m-1;else k=m+1;}//插入位置为k, 腾出k号位置for (r=blist->len; r>k; r--) blist->pkey[r]=blist->pkey[r-1];//key放入k号位置blist->pkey[k]=key;blist->len++;return k;
}int BSL_DelKey(BSeqList* blist, int key)
//在排序的顺序表中删除值为key的结点, 
//存在值为x的结点则返回结点编号, 未找到返回－1
{int k=BSL_FindKey(blist, key);if (k<0) return -1;int i=k;while(i < blist->len-1) {blist->pkey[i] = blist->pkey[i+1];i++;}blist->len --;return k;
}void BSL_Print(BSeqList* blist)
//打印整个顺序表
{if (blist->len==0) {printf("The list is empty.\n");return;}printf("The list contains: ");for (int i=0; i<blist->len; i++) {printf("%d  ", blist->pkey[i]);}printf("\n");
}

第2关：实现散列查找

代码如下：

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include "indLnkHash.h"
LHTable* ILH_Create(int n)
//创建散列表, n为表长度，最佳取值：n取小于等于数据个数的最大质数
{HNode* pn=(HNode*)malloc(sizeof(HNode)*n);for (int i=0; i<n; i++) {pn[i].key=0;pn[i].next=NULL;}LHTable* pt=(LHTable*)malloc(sizeof(LHTable));pt-> pn=pn;pt->n=n;return pt;
}
void ILH_Free(LHTable* pt)
//释放散列表
{if (pt==NULL) return;for (int i=0; i<pt->n; i++) {HNode* curr=pt->pn[i].next;while (curr) {HNode* next=curr->next;free(curr);curr=next;}}free(pt->pn);free(pt);
}
bool ILH_InsKey(LHTable* pt, int x)
//插入关键码x
//返回true，表示插入成功
//返回false，表示插入失败(关键码已经存在)
{/*请在BEGIN和END之间实现你的代码*//*****BEGIN*****/int d=x%pt->n;if (pt->pn[d].key==0) {pt->pn[d].key=x;return true;}else if (pt->pn[d].key==x) return false;HNode* prev=&(pt->pn[d]);HNode* curr=pt->pn[d].next;while (curr && curr->key!=x) {prev=curr; curr=curr->next;}if (curr) return  false;HNode* pnode=(HNode*)malloc(sizeof(HNode));pnode->key=x;pnode->next=NULL;//pt->pn[d].next;prev->next=pnode;return true;/******END******//*请不要修改[BEGIN,END]区域外的代码*/
}
bool ILH_FindKey(LHTable* pt, int x)
//查找关键码x
//返回true表示找到
//返回false表示没找到
{int d=x%pt->n;if (pt->pn[d].key==0) {return false;}else if (pt->pn[d].key==x) return true;HNode* curr=pt->pn[d].next;while (curr && curr->key!=x) curr=curr->next;if (curr) return  true;else return false;
}
bool ILH_DelKey(LHTable* pt, int x)
//删除关键码
//返回true表示该关键码存在，且成功删除
//返回false表示该关键码不存在
{/*请在BEGIN和END之间实现你的代码*//*****BEGIN*****/int d=x%pt->n;//关键码x的散列值dif (pt->pn[d].key==0) {return false;}else if (pt->pn[d].key==x)  {if (pt->pn[d].next ==NULL) pt->pn[d].key=0;else {HNode* first=pt->pn[d].next;pt->pn[d].key=first->key;pt->pn[d].next=first->next;free(first);}return true;}HNode* prev=&(pt->pn[d]);HNode* curr=pt->pn[d].next;while (curr && curr->key!=x) {prev=curr; curr=curr->next;}if (curr==NULL) return false;prev->next=curr->next;free(curr);return true;/******END******//*请不要修改[BEGIN,END]区域外的代码*/
}
void ILH_Print(LHTable *pt)
{for (int i=0; i<pt->n; i++) {printf("%5d:", i);if (pt->pn[i].key) {printf("%d", pt->pn[i].key);HNode* curr=pt->pn[i].next;while (curr) {printf("->%d", curr->key);curr=curr->next;}printf("\n");}else printf("-\n");}
}

---