数据结构线性表的（折半查找）二分查找和快速排序 C语言

Bertha 。 2024-03-31 09:47 64阅读 0赞

线性表的定义

typedef struct
    {
        int key;//关键字项
    
    } ElemType;//数据类型
    typedef struct
    {
        int r[MAXSIZE+1];//存储空间基地址
        int length;//当前表长
    } SSTable;//顺序表的结构类型为SSTable

折半查找（二分查找）

int Search_Bin(SSTable *T,int key)//折半查找
    {
        //在顺序表T中折半查找等于key的元素
        int mid;
        int low=1;
        int high;
        high=T->length;//设置查找区间初值
        while(low<=high)
        {
            mid=(low+high)/2;
            if(key==T->r[mid])return 0 ;//找到待查找元素并返回0
            else if(key<T->r[mid]) high=mid-1;//继续在前一子表进行查找
            else low=mid+1;//继续在后一子表进行查找
        }
        return -1;//查找不到该元素
    }

快速排序

int Partition (SSTable *T,int low,int high)
    {
        //对顺序表T中的子表r[low，high]进行一趟排序并返回枢轴位置
    
        int pivotkey;
        T->r[0]=T->r[low];//用子表的第一个记录做枢轴记录
        pivotkey=T->r[low];//用枢轴记录关键字并保存在prvotkey中
        while(low<high)//从表的两端交替的向中间扫描
        {
            while(low<high&&T->r[high]>=pivotkey) high--;
            T->r[low]=T->r[high];//将比枢轴记录小的移到低端
            while(low<high&&T->r[low]<=pivotkey) low++;
            T->r[high]=T->r[low];//将比枢轴大的移到高端
        }
        T->r[low]=T->r[0];//枢轴记录到位
        return low;//返回枢轴位置
    }
    void QSort(SSTable *T,int low,int high)
    {
        //调用前置初值：low=1，high=T->length；
        //对顺序表T里面的子序列T->r[low,high]做快序排列
        int pivotlc;
        if(low<high)//长度大于1
        {
            pivotlc=Partition(T,low,high);//将T->r[low,high]一分为二，pivotlc是枢轴位置
            QSort(T,low,pivotlc-1);//对左子表递归排序
            QSort(T,pivotlc+1,high);//对右子表递归排序
    
        }
    }

主函数

int main()
    {
        int i;//用于控制循环
        int a,key;
        SSTable array;
        SSTable *T=&array;//定义一个结构体变量的指针T
        printf("请输入元素个数\n");
        scanf("%d",&T->length);
        printf("请输入数据\n");
        for(i=1; i<=T->length; i++)
        {
            scanf("%d",&T->r[i]);
        }
    
    
        QSort(T,1,T->length);//
        printf("快速排序的排序结果为：\n");
        for(i=1; i<=T->length; i++)
    
        {
            printf("%d\n",T->r[i]);
    
        }
        printf("请输入待查找元素：\n");
        scanf("%d",&key);
        a=Search_Bin(T,key);
        if(a==-1)
            printf("查找失败\n");
        else printf("查找成功\n");
    
        return 0;
    }

全部函数

#include <stdio.h>
    #include <stdlib.h>
    #define MAXSIZE 100//线性表可能到达的最大长度
    typedef struct
    {
        int key;//关键字项
    
    } ElemType;//数据类型
    typedef struct
    {
        int r[MAXSIZE+1];//存储空间基地址
        int length;//当前表长
    } SSTable;//顺序表的结构类型为SSTable
    
    int Search_Bin(SSTable *T,int key)//折半查找
    {
        //在顺序表T中折半查找等于key的元素
        int mid;
        int low=1;
        int high;
        high=T->length;//设置查找区间初值
        while(low<=high)
        {
            mid=(low+high)/2;
            if(key==T->r[mid])return 0 ;//找到待查找元素并返回0
            else if(key<T->r[mid]) high=mid-1;//继续在前一子表进行查找
            else low=mid+1;//继续在后一子表进行查找
        }
        return -1;//查找不到该元素
    }
    int Partition (SSTable *T,int low,int high)
    {
        //对顺序表T中的子表r[low，high]进行一趟排序并返回枢轴位置
    
        int pivotkey;
        T->r[0]=T->r[low];//用子表的第一个记录做枢轴记录
        pivotkey=T->r[low];//用枢轴记录关键字并保存在prvotkey中
        while(low<high)//从表的两端交替的向中间扫描
        {
            while(low<high&&T->r[high]>=pivotkey) high--;
            T->r[low]=T->r[high];//将比枢轴记录小的移到低端
            while(low<high&&T->r[low]<=pivotkey) low++;
            T->r[high]=T->r[low];//将比枢轴大的移到高端
        }
        T->r[low]=T->r[0];//枢轴记录到位
        return low;//返回枢轴位置
    }
    void QSort(SSTable *T,int low,int high)
    {
        //调用前置初值：low=1，high=T->length；
        //对顺序表T里面的子序列T->r[low,high]做快序排列
        int pivotlc;
        if(low<high)//长度大于1
        {
            pivotlc=Partition(T,low,high);//将T->r[low,high]一分为二，pivotlc是枢轴位置
            QSort(T,low,pivotlc-1);//对左子表递归排序
            QSort(T,pivotlc+1,high);//对右子表递归排序
    
        }
    }
    int main()
    {
        int i;//用于控制循环
        int a,key;
        SSTable array;
        SSTable *T=&array;//定义一个结构体变量的指针T
        printf("请输入元素个数\n");
        scanf("%d",&T->length);
        printf("请输入数据\n");
        for(i=1; i<=T->length; i++)
        {
            scanf("%d",&T->r[i]);
        }
    
    
        QSort(T,1,T->length);//
        printf("快速排序的排序结果为：\n");
        for(i=1; i<=T->length; i++)
    
        {
            printf("%d\n",T->r[i]);
    
        }
        printf("请输入待查找元素：\n");
        scanf("%d",&key);
        a=Search_Bin(T,key);
        if(a==-1)
            printf("查找失败\n");
        else printf("查找成功\n");
    
        return 0;
    }