查找search

2023-10-15 20:32:10

二分查找BinarySearch

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

#define Maxsize 30

typedef int ValueType;
typedef int IndexType;
typedef int LengthType;

typedef struct BSearchTable{
    ValueType *ValueTable;
    LengthType RealLength;
}BSearchTable;

void InitTable(BSearchTable *BSTable, ValueType Table[])
{
    BSTable->ValueTable=(ValueType *)malloc(sizeof(ValueType)*Maxsize);
    LengthType Length=0;
    for (int i=0; i<Maxsize; i++){
        if (Table[i]!=0){
            BSTable->ValueTable[i]=Table[i];
            Length++;
            continue;
        }
        break;
    }
    BSTable->RealLength=Length;
}

void BSTSort(BSearchTable *BSTable)
{
    if (BSTable->RealLength<=1){return;}
    IndexType MinIndex;
    ValueType MinValue;
    for (int i=0; i<BSTable->RealLength; i++){
        MinIndex=i;
        MinValue=BSTable->ValueTable[MinIndex];
        for (int j=i+1; j<BSTable->RealLength; j++){
            if (MinValue>BSTable->ValueTable[j]){
                MinValue=BSTable->ValueTable[j];
                MinIndex=j;
            }
        }
        if (MinIndex!=i){
            BSTable->ValueTable[MinIndex]=BSTable->ValueTable[i];
            BSTable->ValueTable[i]=MinValue;
        }
    }
}

void ThroughTable(BSearchTable BSTable)
{
    for (int i=0; i<BSTable.RealLength; i++){
        printf("%d ", BSTable.ValueTable[i]);
    }
    printf("\n");
}

IndexType BinarySearch(BSearchTable BSTable, ValueType SearchValue)
{
    IndexType LowIndex=0, HidhIndex=BSTable.RealLength-1, MinIndex;
    while (HidhIndex>=LowIndex){
        MinIndex=(LowIndex+HidhIndex)/2;
        if (BSTable.ValueTable[MinIndex]==SearchValue){
            return MinIndex;
        }else if(SearchValue>BSTable.ValueTable[MinIndex]){
            LowIndex=MinIndex+1;
        }else if(SearchValue<BSTable.ValueTable[MinIndex]){
            HidhIndex=MinIndex-1;
        }
    }
    return -1;
}

int main(int argc, char const *argv[])
{
    BSearchTable BSTable;
    ValueType Table[Maxsize]={16, 2, 5, 20, 18, 100, 60, 50, 90, 200, 230, 35, 46, 78, 390, 123, 231, 98, 259, 55};
    InitTable(&BSTable, Table);
    BSTSort(&BSTable);
    ThroughTable(BSTable);
    IndexType Index=BinarySearch(BSTable, 90);
    printf("%d\n", Index);
    return 0;
}

分块查找BlockSearch

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

#define Maxsize 30
#define NodeMaxsize 5
typedef int ValueType;
typedef int IndexType;
typedef int LengthType;
typedef int MarkType;

typedef struct BlockingNode
{
    MarkType Mark;  // 用于标记链表节点有没数据
    ValueType MaxValue;
    IndexType LowIndex, HighIndex;
    struct BlockingNode *NextBlockingNode;
}BlockingNode, *Blocking;

typedef struct BlockValueArray
{
    LengthType ArrayRealLength;
    ValueType ValueArray[Maxsize];
}BlockValueArray;


void InitValueArray(BlockValueArray *BSValueArray, ValueType ValueArray[])
{
    LengthType RLength=0;
    for (int i=0; i<Maxsize; i++){
        if (ValueArray[i]!=0){
            BSValueArray->ValueArray[i]=ValueArray[i];
            RLength++;
            continue;
        }
        BSValueArray->ArrayRealLength=RLength;
        break;
    }
}

void InitBlockSearchIndexList(Blocking *BSIndexList)
{
    BlockingNode *NowNode=(BlockingNode *)malloc(sizeof(BlockingNode));
    NowNode->NextBlockingNode=NULL;
    *BSIndexList=NowNode;
    (*BSIndexList)->Mark=0;
    BlockingNode *NextNode;
    LengthType ResidueLength=Maxsize-NodeMaxsize;  
    while (ResidueLength>0){
        NextNode=(BlockingNode *)malloc(sizeof(BlockingNode));
        NextNode->Mark=0;
        NextNode->NextBlockingNode=NULL;
        NowNode->NextBlockingNode=NextNode;
        NowNode=NextNode;
        ResidueLength=ResidueLength-NodeMaxsize;
    }
}

void CreateBlockSearchIndexList(Blocking *BSIndexList, BlockValueArray *BlockSearchValueArray)
{
    IndexType NowIndex=0, Index, TempMaxIndex;
    BlockingNode *TempNowNode;
    ValueType TempMaxValue, TempValue;
    BlockingNode *BSNowNode=*BSIndexList;
    while (BSNowNode&&BSNowNode->Mark==0){
        BSNowNode->LowIndex=NowIndex;
        BSNowNode->HighIndex=NowIndex-1;
        BSNowNode->MaxValue=BlockSearchValueArray->ValueArray[NowIndex];
        for (Index=NowIndex; Index<BlockSearchValueArray->ArrayRealLength; Index++){
            if (Index-NowIndex==NodeMaxsize){break;}
            if (BSNowNode->Mark==0){
                BSNowNode->Mark=1;
            }
            // 调整值的位置
            TempValue=BlockSearchValueArray->ValueArray[Index];
            TempNowNode=*BSIndexList;
            while (TempNowNode!=BSNowNode){
                if (TempNowNode->MaxValue>TempValue){
                    TempMaxValue=BlockSearchValueArray->ValueArray[TempNowNode->LowIndex];
                    TempMaxIndex=TempNowNode->LowIndex;
                    for (int i=TempNowNode->LowIndex; i<=TempNowNode->HighIndex; i++){
                        if (BlockSearchValueArray->ValueArray[i]>TempMaxValue){
                            TempMaxValue=BlockSearchValueArray->ValueArray[i];
                            TempMaxIndex=i;
                        }
                    }
                    BlockSearchValueArray->ValueArray[TempMaxIndex]=TempValue;
                    TempValue=TempMaxValue;
                    // 更新当前节点的MaxValue
                    TempMaxValue=BlockSearchValueArray->ValueArray[TempNowNode->LowIndex];
                    for (int i=TempNowNode->LowIndex; i<=TempNowNode->HighIndex; i++){
                        if (BlockSearchValueArray->ValueArray[i]>TempMaxValue){
                            TempMaxValue=BlockSearchValueArray->ValueArray[i];
                        }
                    }
                    TempNowNode->MaxValue=TempMaxValue;
                }
                TempNowNode=TempNowNode->NextBlockingNode;
            }
            BlockSearchValueArray->ValueArray[Index]=TempValue;
            if (BSNowNode->HighIndex-BSNowNode->LowIndex<NodeMaxsize-1){
                if (BlockSearchValueArray->ValueArray[Index]>BSNowNode->MaxValue){
                    BSNowNode->MaxValue=BlockSearchValueArray->ValueArray[Index];
                }
                BSNowNode->HighIndex++;
            }
        }
        NowIndex=Index;
        BSNowNode=BSNowNode->NextBlockingNode;
    }
}

void BloackingValueInsert(Blocking *BSIndexList, BlockValueArray *BlockSearchValueArray, ValueType InsertValue)
{
    if (BlockSearchValueArray->ArrayRealLength==Maxsize){return;}
    BlockSearchValueArray->ValueArray[BlockSearchValueArray->ArrayRealLength]=InsertValue;
    BlockSearchValueArray->ArrayRealLength++;
    BlockingNode *NowNode=*BSIndexList;
    while (NowNode){
        NowNode->Mark=0;
        NowNode=NowNode->NextBlockingNode;
    }
    CreateBlockSearchIndexList(BSIndexList, BlockSearchValueArray);
}

void BlockingDelete(Blocking *BSIndexList, BlockValueArray *BlockSearchValueArray, ValueType DeleteValue)
{   
    if (BlockSearchValueArray->ArrayRealLength==0){return;}
    for (int i=0; i<BlockSearchValueArray->ArrayRealLength; i++){
        if (BlockSearchValueArray->ValueArray[i]==DeleteValue){
            BlockSearchValueArray->ArrayRealLength--;
            BlockSearchValueArray->ValueArray[i]=BlockSearchValueArray->ValueArray[BlockSearchValueArray->ArrayRealLength];
            BlockingNode *NowNode=*BSIndexList;
            while (NowNode){
                NowNode->Mark=0;
                NowNode=NowNode->NextBlockingNode;
            }
            CreateBlockSearchIndexList(BSIndexList, BlockSearchValueArray);
            break;
        }
    }
}

IndexType BlockingSearch(Blocking *BSIndexList, BlockValueArray *BlockSearchValueArray, ValueType SearchValue)
{
    IndexType SearchIndex=-1;
    BlockingNode *BSNowNode=*BSIndexList;
    while (BSNowNode&&BSNowNode->Mark==1){
        if (BSNowNode->MaxValue>=SearchValue){
            for (int i=BSNowNode->LowIndex; i<=BSNowNode->HighIndex; i++){
                if (BlockSearchValueArray->ValueArray[i]==SearchValue){
                    SearchIndex=i;
                    return SearchIndex;
                }
            }
        }
        BSNowNode=BSNowNode->NextBlockingNode;
    }
    return SearchIndex;
}

void PrintBlockArray(Blocking *BSIndexList, BlockValueArray *BlockSearchValueArray)
{
    BlockingNode *NowNode=*BSIndexList;
    while (NowNode&&NowNode->Mark==1){
        printf("<||>%d ->[", NowNode->MaxValue);
        for (int i=NowNode->LowIndex; i<=NowNode->HighIndex; i++){
            printf("%d ", BlockSearchValueArray->ValueArray[i]);
        }
        printf("] ");
        NowNode=NowNode->NextBlockingNode;
    }
    printf("\n");
}




int main(int argc, char const *argv[])
{
    Blocking BlockSearchIndexList;
    InitBlockSearchIndexList(&BlockSearchIndexList);
    BlockValueArray BlockSearchValueArray;
    ValueType ValueArray[Maxsize]={100, 50, 500, 200, 15, 12, 8, 90, 300, 250, 150, 18, 450, 320, 115, 250, 400};
    InitValueArray(&BlockSearchValueArray, ValueArray);

    CreateBlockSearchIndexList(&BlockSearchIndexList, &BlockSearchValueArray);
    PrintBlockArray(&BlockSearchIndexList, &BlockSearchValueArray);

    BloackingValueInsert(&BlockSearchIndexList, &BlockSearchValueArray, 166);
    PrintBlockArray(&BlockSearchIndexList, &BlockSearchValueArray);
    BloackingValueInsert(&BlockSearchIndexList, &BlockSearchValueArray, 266);
    PrintBlockArray(&BlockSearchIndexList, &BlockSearchValueArray);
    BloackingValueInsert(&BlockSearchIndexList, &BlockSearchValueArray, 666);
    BloackingValueInsert(&BlockSearchIndexList, &BlockSearchValueArray, 556);
    PrintBlockArray(&BlockSearchIndexList, &BlockSearchValueArray);
    printf("%d\n", BlockingSearch(&BlockSearchIndexList, &BlockSearchValueArray, 300));
    printf("%d\n", BlockingSearch(&BlockSearchIndexList, &BlockSearchValueArray, 3100));

    BlockingDelete(&BlockSearchIndexList, &BlockSearchValueArray, 200);
    PrintBlockArray(&BlockSearchIndexList, &BlockSearchValueArray);
    return 0;
}

哈希查找HashSearch

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

#define HashMaxsize 13

typedef int ValueType;
typedef int IndexType;

typedef struct HSearchTable
{
    ValueType Value;
    struct HSearchTable *NextHashNode;
}HSearchTable[HashMaxsize], HashNode;

void InitHashTable(HSearchTable HSTable)
{
    for (int i=0; i<HashMaxsize; i++){
        HSTable[i].Value=INT_MAX;
        HSTable[i].NextHashNode=NULL;
    }
}

IndexType HashFunc(ValueType Value)
{
    IndexType Index=Value%HashMaxsize;
    return Index;
}

void HashInsert(HSearchTable HSTable, ValueType Value)
{
    IndexType Index=HashFunc(Value);
    if (HSTable[Index].Value==INT_MAX){
        HSTable[Index].Value=Value;
        return;
    }
    HashNode *NewHashNode=(HashNode *)malloc(sizeof(HashNode));
    NewHashNode->Value=Value;
    NewHashNode->NextHashNode=NULL;
    if (HSTable[Index].NextHashNode==NULL){
        HSTable[Index].NextHashNode=NewHashNode;
        return;
    }
    HashNode *NowHashNode=HSTable[Index].NextHashNode;
    while (NowHashNode->NextHashNode!=NULL){
        NowHashNode=NowHashNode->NextHashNode;
    }
    NowHashNode->NextHashNode=NewHashNode;
}

void HashDelete(HSearchTable HSTable, ValueType Value)
{
    IndexType Index=HashFunc(Value);
    if (HSTable[Index].Value==Value){
        if (HSTable[Index].NextHashNode==NULL){
            HSTable[Index].Value=INT_MAX;
        }else{
            HSTable[Index].Value=HSTable[Index].NextHashNode->Value;
            HSTable[Index].NextHashNode=HSTable[Index].NextHashNode->NextHashNode;
        }
        return;
    }
    HashNode *NowHashNode=HSTable[Index].NextHashNode;
    if (NowHashNode->Value==Value){
        HSTable[Index].NextHashNode=NowHashNode->NextHashNode;
        return;
    }
    HashNode *LastNode=NowHashNode;
    NowHashNode=NowHashNode->NextHashNode;
    while (NowHashNode){
        if (NowHashNode->Value==Value){
            LastNode->NextHashNode=NowHashNode->NextHashNode;
            return;
        }
        NowHashNode=NowHashNode->NextHashNode;
    }
}

IndexType HashSearch(HSearchTable HSTable, ValueType Value)
{
    IndexType Index=HashFunc(Value);
    if (HSTable[Index].Value==Value){
        return 0;
    }
    HashNode *NowHashNode=HSTable[Index].NextHashNode;
    IndexType EisitIndex=1;
    while (NowHashNode){
        if (NowHashNode->Value==Value){
            return EisitIndex;
        }
        EisitIndex++;
        NowHashNode=NowHashNode->NextHashNode;
    }
    return -1;
}

void ThroughHashNode(HSearchTable HSTable, IndexType Index)
{
    if (Index<0||Index>HashMaxsize){return;}
    if (HSTable[Index].Value!=INT_MAX){
        printf("%d ", HSTable[Index].Value);
        if (HSTable[Index].NextHashNode){
            HashNode *NowHashNode=HSTable[Index].NextHashNode;
            while (NowHashNode){
                printf("%d ", NowHashNode->Value);
                NowHashNode=NowHashNode->NextHashNode;
            }
        }
    }
    printf("\n");
}

void ThroughHash(HSearchTable HSTable)
{
    for (int i=0; i<HashMaxsize; i++){
        ThroughHashNode(HSTable, i);
    }
}

int main(int argc, char const *argv[])
{
    HSearchTable HSTable;
    InitHashTable(HSTable);
    ValueType Values[]={16, 2, 5, 20, 18, 100, 60, 50, 90, 200, 230, 35, 46, 78, 190, 123, 231, 98, 259, 55, 31, 44, 57};
    for (int i=0; i<23; i++){
        HashInsert(HSTable, Values[i]);
    }
    HashDelete(HSTable, 200);
    printf("%d\n", HSTable[5].NextHashNode->NextHashNode->Value);
    printf("%d \n", HashSearch(HSTable, 31));
    printf("%d \n", HashSearch(HSTable, 313));
    ThroughHashNode(HSTable, 5);
    printf("Through______________________\n");
    ThroughHash(HSTable);
    return 0;
}

码农公寓

相关文章