C语言数据结构顺序表的查找算法

电玩女神 2022-01-23 15:37 290阅读 0赞

/\*  
\*顺序表的查找算法（重点是哨兵的设置）  
\*创建一个数据结构体  
\*创建一个顺序表的结构体  
\*顺序表结构体里面包含 数据数组 和 数组长度  
\*采用两种查找方法 哨兵设置 普通查找  
\*哨兵排序算法的设置的好处是可以降低时间的复杂度 节省 for循环的次数  
\*程序 的步骤分为 初始化顺序表 创建顺序表 查找 输出 测试  
\*/

#include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    #define MAX_SIZE 1024//数据的个数
    typedef  int KeyType;//关键字的数据类型
    typedef  char* ValueType;//标识字符串的数据类型
    typedef int Statu;//返回值的数据类型
    
    #define ERROR 0
    #define OK 1
    typedef struct elementtype
    {
        KeyType key;//关键字
        ValueType value;//数据域
    
    }ElementType;//顺序表中的数据结构体
    typedef struct seqlist
    {
        ElementType *datas;//数据数组
        int length;//顺序表长度
    }SeqList;//顺序表点的结构体数据类型
    void InIt(SeqList*s);//顺序表的初始化
    void test();//测试函数
    void print_seqlist(SeqList*s);//打印顺序表
    Statu search_seqlist1(SeqList*s,KeyType key);//顺序表的节点数据的查找
    Statu search_seqlist2(SeqList*s,KeyType key);//顺序表的节点数据的查找(设置哨兵元素)
    
    void main()
    {
        test();//测试函数
    }
    void InIt(SeqList*s)//顺序表的初始化
    {
        s->datas=(ElementType*)malloc(sizeof(ElementType)*MAX_SIZE);//创建顺序表的储存空间
        s->length=0;//初始化顺序表的长度
    }
    void print_seqlist(SeqList*s)//打印顺序表的元素
    {
        int i;
        for(i=1;i<=s->length;i++)//下标为0的位置不放数据
              printf("%d %s\n",s->datas[i].key,s->datas[i].value);
    
    
    
    }
    Statu search_seqlist1(SeqList*s,KeyType key)//顺序表的节点数据的查找
    {
        int i;
       // printf("%d\n",s->length);
        for(i=1;i<=s->length;i++)
        {
            if(s->datas[i].key==key)
                return i;
        }
        return 0;
    }
    Statu search_seqlist2(SeqList*s,KeyType key)//顺序表的节点数据的查找(设置哨兵元素)
    {
        //好处节省了for循环中循环条件的判断
          //设置哨兵和将第一个数组的位置空下来是一样的
         s->datas[0].key=key;
        int i;
        for(i=s->length-1;s->datas[i].key!=key;i--)
               return i;
    
    
    
    
    
    
    }