【C语言数据结构】查找-顺序查找&折半查找

分手后的思念是犯贱 2024-02-21 10:25 116阅读 0赞

--------------------

#### 查找-顺序查找&折半查找 ####

*  代码实现

--------------------

## 代码实现 ##

#include<stdio.h>
    #include<stdlib.h>
    #include<stdbool.h>
    
    //将数据元素类型标为int
    typedef int ElemType;
    
    //定义线性表
    typedef struct{
        
        //数据元素数组(0号留空，作为"哨兵"，方便查找)
        ElemType *elem;
        //线性表长度
        int TableLen;
    }SSTable;
    
    //顺序查找(非递归算法)
    int Search_Seq(SSTable ST,ElemType key){
        
        ST.elem[0] = key; //哨兵
    
        //数组下标
        int i;
    
        for(i = ST.TableLen;ST.elem[i]!=key;--i);
    
        return i;
    }
    
    //折半查找(非递归算法)
    int Binary_Search(SSTable ST,ElemType key){
        
        //定义前后指针
        int low = 0,high = ST.TableLen;
        //定义中间指针
        int mid;
    
        while(low<=high){
        
            mid = (low+high)/2;
            if(ST.elem[mid] == key)
                return mid;
            else if(ST.elem[mid] > key)
                high = mid-1;
            else
                low = mid+1;
        }
        return -1;
    }
    
    //折半查找(递归算法)（初始调用时，low为1，high为ST.TableLen）
    int Binary_Search_Rec(SSTable ST,ElemType key,int low,int high){
        
        if(low>high)
            return -1;
        int mid = (low+high)/2;
        if(ST.elem[mid] == key)
            return mid;
        else if(ST.elem[mid] > key)
            return Binary_Search_Rec(ST,key,low,mid-1);
        else
            return Binary_Search_Rec(ST,key,mid+1,high);
    }
    
    //初始化线性表
    void InitTable(SSTable *ST){
        
        ST->TableLen = 0;
    }
    
    //添加线性表元素
    bool AddElem(SSTable *ST,ElemType elem){
        
        //保留0号位为空
        ST->elem[ST->TableLen+1] = elem;
    
        //线性表长度+1
        ST->TableLen++;
    }
    
    int main(){
        
        //定义数组下标
        int index;
    
        //创建顺序表
        SSTable ST;
    
        //初始化线性表
        InitTable(&ST);
    
        //添加线性表元素
        AddElem(&ST,1);
        AddElem(&ST,4);
        AddElem(&ST,3);
        AddElem(&ST,2);
        AddElem(&ST,9);
        AddElem(&ST,8);
        AddElem(&ST,10);
        AddElem(&ST,7);
        AddElem(&ST,6);
        AddElem(&ST,5);
        AddElem(&ST,13);
        AddElem(&ST,421);
        AddElem(&ST,999);
    
        //顺序查找
        printf("顺序查找：\n");
        index = Search_Seq(ST,13);
        if(index == 0)
            printf("未找到数据元素13\n");
        else
            printf("数据元素13的位置为%d\n",index);
    
        index = Search_Seq(ST,19);
        if(index == 0)
            printf("未找到数据元素19\n");
        else
            printf("数据元素19的位置为%d\n",index);
        printf("\n");
    
        //折半查找(非递归)
        printf("折半查找(非递归)：\n");
        index = Binary_Search(ST,13);
        if(index == -1)
            printf("未找到数据元素13\n");
        else
            printf("数据元素13的位置为%d\n",index);
    
        index = Binary_Search(ST,19);
        if(index == -1)
            printf("未找到数据元素19\n");
        else
            printf("数据元素19的位置为%d\n",index);
        printf("\n");
    
        //折半查找(递归)
        printf("折半查找(递归)：\n");
        index = Binary_Search_Rec(ST,13,1,ST.TableLen);
        if(index == -1)
            printf("未找到数据元素13\n");
        else
            printf("数据元素13的位置为%d\n",index);
    
        index = Binary_Search_Rec(ST,19,1,ST.TableLen);
        if(index == -1)
            printf("未找到数据元素19\n");
        else
            printf("数据元素19的位置为%d\n",index);
        printf("\n");
    
    }