数据结构与算法 - 查找

文章目录

第1关：实现折半查找

代码如下：

/*************************************************************
    date: April 2009
    copyright: Zhu En
    DO 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;}voidBSL_Free(BSeqList* blist)//释放/删除顺序表//与BSL_Create()配对{free(blist->pkey);free(blist);}intBSL_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;}elseif(key < blist->pkey[m]){
            r = m -1;}else{
            k = m +1;}}return-1;/******END******//*请不要修改[BEGIN,END]区域外的代码*/}intBSL_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;}intBSL_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;}voidBSL_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;}voidILH_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;}elseif(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;}elseif(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;elsereturn 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;}elseif(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]区域外的代码*/}voidILH_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");}elseprintf("-\n");}}