精华内容
下载资源
问答
  • 顺序表查找:顺序查找,哨兵查找 有序表查找:折半查找,插值查找,斐波那契查找

    前言

    搜索引擎就是利用了查找的技术,查找方式按照操作方式有两大种,分别是静态查找和动态查找。静态查找只做查找,动态查找在查找过程中插入不存在的元素,删除已存在的元素。
    本篇只讨论有关静态查找的内容
    找不到返回-1

    顺序表查找

    顺序表查找分为顺序查找和优化的哨兵查找。

    顺序查找

    int Sequential_Search(int *a,int n,int key)
    {
    	int i;
    	for(i=0;i<n;i++)
    	{
    		if(a[i]==key)
    			return i;
    	}
    	return -1;
    
    }
    

    哨兵查找

    在优化的查找中,设置了一个哨兵,免去了查找过程中每次比较后都要判断查找位置是否越界。总数据较多时,效率提高很大

    int Sequential_Search1(int *a,int n,int key)
    {
    	int i;
    	a[-1] = key;//设置哨兵
    	i = n;
    	while(a[i]!=key)
    	{
    		i--;
    	}
    	return i;//返回-1则说明查找失败
    }
    

    有序表查找

    有序表就是有排列顺序的表
    折半查找适用于数据量较大的
    插值查找适用于表长比较大,关键字分布广的
    斐波那契适用于数据分布极端不均匀的

    折半查找

    int Binary_Search(int *a,int n,int key)
    {
    	int low,high,mid;
    	low = 0;//定义最低下标为记录首位
    	high = 9;//定义最高下标为记录末尾
    	while(low<=high)
    	{
    		mid = (low+high)/2;//折半
    		if(key<a[mid])
    			high = mid-1;
    		else if(key>a[mid])
    			low = mid+1;
    		else
    			return mid;
    	}
    	return -1;
    }
    

    插值查找

    插值查找的核心在于插值的计算公式。查找关键字key与查找表中最大最小记录的关键字比较后的查找方法。
    代码就是折半查找中注释折半那一行替换为查找这一行就行了

    mid = low+(high-low)*(key-a[low])/(a[high]-a[low]);//插值
    

    斐波那契查找

    斐波那契查找利用了黄金分割率原理实现
    查找的核心在于:
    当key = a[mid]时,查找成功;

    当key < a[mid]时,新范围是第low到mid-1个,此时范围个数为F[k-1]-1个;

    当key 》 a[mid]时,新范围是第mid+1到high个,此时范围个数为F[k-2]-1个;

    图解

    int Fibonacci_Search(int *a,int n,int key)
    {
    
    	int F[30];
    	F[0] = 0;
    	F[1] = 1;
    	for(int m = 2;m<30;m++)
    		F[m] = F[m-1]+F[m-2];//斐波那契数组
    
    	int low,high,mid,i,k;
    	low = 0;//定义最低下标为记录首位
    	high = n;//定义最高下标为记录末尾
    	k = 0;
    	while(n>F[k]-1)//记录n位于斐波那契数列的位置
    		k++;
    	for(i=n;i<F[k]-1;i++)//将不满的数值补全
    		a[i] = a[n];
    	while(low<=high)
    	{
    		mid = low+F[k-1]-1;//计算当前分隔的下标
    		if(key<a[mid])
    		{
    			high = mid-1;//最高下标调整到mid-1处
    			k = k-1;//斐波那契下标减一位
    		}
    		else if(key>a[mid])//若查找记录大于分隔记录
    		{
    			low = mid+1;//最低下标调整到mid+1处
    			k = k-2;//斐波那契下标减一二位
    		}
    		else
    		{
    			if(mid<=n)
    				return mid;
    			else
    				return n;//若mid=n,说明是补全数值,返回n
    		}
    	}
    	return -1;
    }
    }
    

    真正实现代码功能

    花了较长时间把这些代码的功能实现了。
    注意创建一个比较自由的数组,我们可以用顺序表的结构体来表示数组,但是还有一种方法,与结构体表示有异曲同工之妙,首先创建一个数组,然后往其中填充数据,再用一个子函数求出数据长度。
    顺序表数据是自己填充
    有序表是系统自带,长度固定为9

    #include<stdio.h>
    #include<stdlib.h>
    
    #define M 20
    
    void Init(int *a);//初始化数组
    void Display(int *a);//显示数组
    int number(int *a);//求数据长度
    int Sequential_Search(int *a,int n,int key);//顺序查找
    int Sequential_Search1(int *a,int n,int key);//顺序哨兵查找
    int Binary_Search(int *a,int n,int key);//有序表折半查找
    int Interpolation_Search(int *a,int n,int key);//有序表插值查找
    int Fibonacci_Search(int *a,int n,int key);//有序表斐波那契查找
    
    int main()
    {
    	int i,x,n;
    	int len;
    	int a[20];
    	Init(a);
    	printf("顺序表为:");
    	Display(a);
    	len = number(a);
    	printf("数据长度为%d\n",len);
    	int b[12] = {1,16,24,35,47,59,62,73,88,99};
    	printf("排序表为:");
    	Display(b);
    	while(1)
    	{
    		printf("1.顺序表查询 2.顺序表哨兵查询 3.有序表折半查找 4.有序表插值查找 5.有序表斐波那契查找\n");
    		scanf("%d",&x);
    		switch(x)
    		{
    		case 1:
    			printf("顺序表查询的数:\n");
    			scanf("%d",&n);
    			i = Sequential_Search(a,len,n);
    			printf("此数的数组下标:%d\n",i);
    			break;
    		case 2:
    			printf("顺序表查询的数:\n");
    			scanf("%d",&n);
    			i = Sequential_Search1(a,len,n);
    			printf("此数的数组下标:%d\n",i);
    			break;
    		case 3:
    			printf("有序表查询的数:\n");
    			scanf("%d",&n);
    			i = Binary_Search(b,9,n);
    			printf("此数的数组下标:%d\n",i);
    			break;
    		case 4:
    			printf("有序表查询的数:\n");
    			scanf("%d",&n);
    			i = Interpolation_Search(b,9,n);
    			printf("此数的数组下标:%d\n",i);
    			break;
    		case 5:
    			printf("有序表查询的数:\n");
    			scanf("%d",&n);
    			i = Fibonacci_Search(b,9,n);
    			printf("此数的数组下标:%d\n",i);
    			break;
    		}
    	}
    }
    
    void Init(int *a)
    {
    	int i = 0;
    	int x = 0;
    	printf("请输入数据,-1时结束且长度不得大于20:\n");
    	while(x!=-1)
    	{
    		scanf("%d",&x);
    		if(x!=-1)
    		{
    			a[i] = x;
    			i++;
    		}
    	}
    	a[i] = '\0';
    }
    
    void Display(int *a)
    {
    	for(int i=0;a[i]!='\0';i++)
    	{
    		printf("%d ",a[i]);
    	}
    	printf("\n");
    }
    
    int number(int *a)
    {
    	int i;
    	for(i =0;a[i]!='\0';)
    	{
    		i++;
    	}
    	return i;
    }
    
    int Sequential_Search(int *a,int n,int key)
    {
    	int i;
    	for(i=0;i<n;i++)
    	{
    		if(a[i]==key)
    			return i;
    	}
    	return -1;
    
    }
    
    int Sequential_Search1(int *a,int n,int key)
    {
    	int i;
    	a[-1] = key;//设置哨兵
    	i = n;
    	while(a[i]!=key)
    	{
    		i--;
    	}
    	return i;//返回-1则说明查找失败
    }
    
    int Binary_Search(int *a,int n,int key)
    {
    	int low,high,mid;
    	low = 0;//定义最低下标为记录首位
    	high = 9;//定义最高下标为记录末尾
    	while(low<=high)
    	{
    		mid = (low+high)/2;//折半
    		if(key<a[mid])
    			high = mid-1;
    		else if(key>a[mid])
    			low = mid+1;
    		else
    			return mid;
    	}
    	return -1;
    }
    
    int Interpolation_Search(int *a,int n,int key)
    {
    	int low,high,mid;
    	low = 0;
    	high = 9;
    	while(low<=high)
    	{
    		mid = low+(high-low)*(key-a[low])/(a[high]-a[low]);//插值
    		if(key<a[mid])
    			high = mid-1;
    		else if(key>a[mid])
    			low = mid+1;
    		else
    			return mid;
    	}
    	return -1;
    }
    
    int Fibonacci_Search(int *a,int n,int key)
    {
    
    	int F[30];
    	F[0] = 0;
    	F[1] = 1;
    	for(int m = 2;m<30;m++)
    		F[m] = F[m-1]+F[m-2];//斐波那契数组
    
    	int low,high,mid,i,k;
    	low = 0;//定义最低下标为记录首位
    	high = n;//定义最高下标为记录末尾
    	k = 0;
    	while(n>F[k]-1)//记录n位于斐波那契数列的位置
    		k++;
    	for(i=n;i<F[k]-1;i++)//将不满的数值补全
    		a[i] = a[n];
    	while(low<=high)
    	{
    		mid = low+F[k-1]-1;//计算当前分隔的下标
    		if(key<a[mid])
    		{
    			high = mid-1;//最高下标调整到mid-1处
    			k = k-1;//斐波那契下标减一位
    		}
    		else if(key>a[mid])//若查找记录大于分隔记录
    		{
    			low = mid+1;//最低下标调整到mid+1处
    			k = k-2;//斐波那契下标减一二位
    		}
    		else
    		{
    			if(mid<=n)
    				return mid;
    			else
    				return n;//若mid=n,说明是补全数值,返回n
    		}
    	}
    	return -1;
    }
    

    运行结果

    运行结果

    后记

    本篇确实是只用一片代码柔和了五个算法,实在有些罗嗦,但是功能确实是全部实现的。
    今天的内容就是静态查找的基本操作及其内容,喜欢我的多多支持哦~

    展开全文
  • 静态查找表在查找的过程中不改变表的状态---不插入也不删除,适合不变动或者不经常变动的查找,顺序表可以使有序的也可以是无序的,如果是有序的可以使用折半查找,每查找一次,就把范围缩小一半,如果是无序的就...

    静态查找表在查找的过程中不改变表的状态---不插入也不删除,适合不变动或者不经常变动的查找,顺序表可以使有序的也可以是无序的,如果是有序的可以使用折半查找,每查找一次,就把范围缩小一半,如果是无序的就只能从表的一端开始逐一查找了。

    本文先用Create_Seq(SSTable &ST,ElemType r[],int n)构造一个无序的静态查找表,然后调用函数void Ascend(SSTable &ST)重建静态查找表为按照关键字为非降序排列,然后就可以进行折半查找指定的元素。

    #include<stdio.h>
    #include<malloc.h>
    #include<process.h>
    #define ERROR 0
    
    //数据元素的类型
    struct ElemType
    {
    	int key;
    };
    //静态查找表的顺序存储结构
    struct SSTable
    {
    	ElemType *elem;//数据元素的存储空间的基地址,(0号单元不用)
    	int length;//表的长度
    };
    //对于两个数值型变量的比较约定为如下的宏定义
    #define EQ(a,b) ((a) == (b))
    #define LT(a,b) ((a) < (b))
    #define LQ(a,b) ((a) <= (b))
    
    //由n个数据元素的数组r,构造静态查找表ST
    void Create_Seq(SSTable &ST,ElemType r[],int n)
    {
    	int i;
    	//ST.elem=(ElemType*)calloc(n+1,sizeof(ElemType));//动态生成n+1个数据元素空间,0号单元不用
    	ST.elem=(ElemType*)malloc((n+1)*sizeof(ElemType));
    	if(!ST.elem)
    		exit(ERROR);
    	for(i=1;i<=n;i++)
    		ST.elem[i]=r[i-1];//将数组的元素依次赋值给ST
    	ST.length = n;
    }
    //重建静态查找表为按照关键字为非降序排列
    void Ascend(SSTable &ST)
    {
    	int i,j,k;
    	for(i=1;i<ST.length;i++)
    	{
    		k=i;
    		ST.elem[0]=ST.elem[i];//待比较的元素存入0号单元
    		for(j=i+1;j<=ST.length;j++)
    		{
    			if(LT(ST.elem[j].key,ST.elem[0].key))
    			{
    				k=j;
    				ST.elem[0]=ST.elem[j];
    			}
    		}
    		if(k != i)//有更小的值则交换
    		{
    			ST.elem[k]=ST.elem[i];
    			ST.elem[i]=ST.elem[0];
    		}
    	}
    }
    //在有序表ST中,折半查找关键字等于key的数据元素,返回在表中的位置(查找有序的顺序表)
    int Search_Bin(SSTable &ST,long key)
    {
    	int low,mid,high;
    	low=1;
    	high=ST.length;//置区间初值
    	while(low <= high)
    	{
    		mid=(low+high)/2;
    		if(EQ(ST.elem[mid].key,key))
    			return mid;
    		else if(LT(key,ST.elem[mid].key))
    			high=mid-1;//继续在前半个区间查找
    		else
    			low=mid+1;//继续在后半个区间查找
    	}
    	<span style="color:#ff0000;">return 0;//没有查找到</span>
    }
    //打印ST中的元素
    void Traverse(SSTable ST)
    {
    	ElemType *p;
    	int i;
    	p=++ST.elem;
    	for(i=1;i<=ST.length;i++,p++)
    		printf("%d ",p->key);
    	printf("\n");
    }
    //顺序表的有序查找
    void main()
    {
    	SSTable st;
    	int i;
    	int s;
    	ElemType r[5]={51,60,55,36,52};//数据元素
    	Create_Seq(st,r,5);//建立无序的顺序查找表
    	Ascend(st);//将无序的查找表重建为按照关键字非降序排列的查找表
    	Traverse(st);
    	printf("请输入你要查找值得关键字:");
    	scanf("%d",&s);
    	i=Search_Bin(st,s);
    	if(i)
    		printf("%d 是第%d个记录的关键字\n",st.elem[i].key,i);
    	else
    		printf("没找到!");
    }
    
    (1)静态查找表的顺序存储结构

    struct SSTable
    {
    ElemType *elem;//数据元素的存储空间的基地址,(0号单元不用)
    int length;//表的长度
    };

    (2)由n个数据元素的数组r,构造静态查找表ST:


    (3)程序的运行结果:


    (4)

    折半查找算法的流程图:



    展开全文
  • 上次我们介绍了图的关键路径算法的实现,这次介绍查找这一章的第一个程序:顺序表和有序表(静态查找表)查找算法的实现。还是老规矩:程序在码云上可以下载。 地址:...

    上次我们介绍了图的关键路径算法的实现,这次介绍查找这一章的第一个程序:顺序表和有序表(静态查找表)查找算法的实现。

    还是老规矩:

    程序在码云上可以下载。
    地址:https://git.oschina.net/601345138/DataStructureCLanguage.git

    图这一章的程序做完以后,后面的程序就明显好做多了。

    这次的程序没啥好说的,就是顺序表每个数据元素加了一个关键字。其他操作差不多,仅此而已。

    关于顺序表的实现,可以参考:《 数据结构编程笔记三:第二章 线性表 顺序表的实现》,我就是拿这个程序改造之后变成了第九章的程序。

    直接看代码吧:

    //*********************引入头文件**********************************
    #include <stdio.h>
    #include <stdlib.h>  //使用了malloc、free函数 
    
    //********************自定义符号常量******************************** 
    
    #define OVERFLOW -2         //内存溢出错误常量
    #define ILLEGAL -1          //非法操作错误常量 
    #define OK 1                //表示操作正确的常量 
    #define ERROR 0             //表示操作错误的常量
    #define LIST_INIT_SIZE 100  //线性表存储空间的初始分配量
    #define EQ(a,b) ((a)==(b))  //相等 
    #define LT(a,b) ((a)< (b))  //小与
    #define LQ(a,b) ((a)<= (b)) //小与等于 
    
    //*********************自定义数据类型*******************************
    
    typedef int Status;   //状态码类型为int  
    typedef int KeyType;  //关键字类型为int 
    typedef struct{       //元素类型 
    
        //关键字域 
        KeyType key;
    }ElemType; 
    
    //------------------静态查找表的顺序存储结构------------------- 
    typedef struct{
    
        //数据元素存储空间基址,建表时按实际长度分配,0号单元留空
        ElemType *elem; 
    
        //表长度,表中记录数 
        int length;
    }SSTable;
    
    //**************************顺序表的主要操作************************* 
    
    //1.--------------------静态查找表的初始化操作---------------------------- 
    
    /*
        函数:InitSSTable_Seq
        参数:SSTable &ST 静态查找表引用 
        返回值:状态码,操作成功返回OK 
        作用:初始化静态查找表,构造一个空静态查找表
    */
    Status InitSSTable_Seq(SSTable &ST){
    
        //申请查找表内存空间,0号单元留空。
        ST.elem = (ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType) + 1); 
    
        //若内存分配失败,退出程序
        if(!ST.elem){  
            printf("内存申请失败!\n");   
            exit(OVERFLOW); 
        }//if
    
        //设置静态查找表ST的长度为0
        ST.length = 0;
    
        //操作成功 
        return OK;    
    }//InitSSTable_Seq
    
    //2.----------------------输入静态查找表元素的操作-------------------
    
    /*
        函数:SSTableInput_Seq
        参数:SSTable &ST 静态查找表引用 
        返回值:状态码,操作成功返回OK 
        作用:顺序表插入元素的函数
    */
    Status SSTableInput_Seq(SSTable &ST) {
    
        //n代表元素的个数,i用作循环变量 
        int n, i;
    
        //直到用户输入正确为止 
        while(1){
    
            //先确定元素的个数
            printf("->您想输入几个元素,请输入个数,最多不可以超过100  "); 
            scanf("%d", &n);
    
            //检查元素个数n是否合法 
            if(n < 1 || n > 100) { 
    
                //如果输入非法数据,就提醒用户重新输入
                printf("您的输入非法,请重新输入!!!\n");
            }//if
    
            //若输入合法则退出循环 
            break;
        }//while
    
        //输入静态查找表数据
        printf("请输入静态查找表ST的元素,中间用空格隔开,最多不可以超过100个元素\n");
        for(i = 1; i <= n; i++) { 
    
            //初始化每一个元素
            scanf("%d", &ST.elem[i].key); 
        }//for 
    
        //静态查找表个数为元素个数n 
        ST.length = n;
    
        //操作成功 
        return OK;
    }//SSTableInput_Seq
    
    //3.------------------判断静态查找表是否为空-------------------
    
    /*
        函数:SSTableEmpty_Seq
        参数:SSTable ST 静态查找表ST 
        返回值:状态码,若静态查找表为空表返回TRUE,否则返回FALSE 
        作用:判断静态查找表是否为空 
    */
    Status SSTableEmpty_Seq(SSTable ST){
    
        //查看表长是否为0 
        return ST.length == 0;
    }//SSTableEmpty_Seq
    
    //4.----------------------静态查找表的输出操作------------------
    
    /*
        函数:Print
        参数:KeyType e 关键字的值e 
        返回值:状态码,操作成功返回OK,否则返回ERROR 
        作用:元素访问函数
    */
    Status Print(KeyType e){
    
        //采用控制台输出方式打印关键字e 
        printf("%3d ", e);
    
        //操作成功 
        return OK;
    }//Print
    
    /*
        函数:SSTableTraverse_Seq
        参数:SSTable ST 静态查找表ST 
              Status(* Visit)(KeyType) 函数指针,指向元素访问函数 
        返回值:状态码,操作成功返回OK,否则返回ERROR 
        作用:遍历静态查找表函数
    */
    Status SSTableTraverse_Seq(SSTable ST, Status(* Visit)(KeyType)){
    
        //访问静态查找表中每一个元素一次且仅一次 
        for(int i = 1; i <= ST.length; ++i) { 
    
            //一旦访问失败则遍历失败
            //if(!Visit(ST.elem[i].key)) <=> if(Visit(ST.elem[i].key) == ERROR)
            if(!Visit(ST.elem[i].key)) {
                return ERROR;
            }//if 
        }//for 
    
        //输出换行使结果美观 
        printf("\n");
    
        //操作成功 
        return OK;
    }//SSTableTraverse_Seq
    
    
    
    //5.----------------------顺序表的顺序查找算法------------------ 
    
    /*
        函数:SSTableTraverse_Seq
        参数:SSTable ST 静态查找表ST 
              KeyType key 被查找的关键字 
        返回值:若找到,则函数值为该元素在表中的位置,否则为0
        作用:在顺序表ST中顺序查找其关键字等于key的数据元素。
    */
    int Search_Seq(SSTable ST, KeyType key){
    
        //i是循环变量,存储了关键字在表中的位置 
        int i; 
    
        //0号单元不放被查找数据元素,放关键字,作用相当于"哨兵",
        //好处在于不必时时提防数组越界问题 
        ST.elem[0].key = key;
    
        //从后向前查找,直至找到元素或遇到哨兵为止 
        for(i = ST.length; !EQ(ST.elem[i].key, key); --i);
    
        //返回关键字在表中的位置i 
        return i;  
    }//Search_Seq 
    
    //6.-----------------------静态查找表的排序操作-------------------
    
    /*
        函数:SortSSTable_Seq
        参数:SSTable &ST 静态查找表引用 
        返回值:若找到,则函数值为该元素在表中的位置,否则为0
        作用:排序顺序表中元素,使顺序表变为有序表,以便于对有序表进行查找 
    */
    Status SortSSTable_Seq(SSTable &ST) {
        //将线性表中的元素排序,使用冒泡法,
        /*传统冒泡排序中每一趟排序操作只能找到一个最大值或最小值,
          我们考虑利用在每趟排序中进行正向和反向两遍冒泡的方法
          一次可以得到两个最终值(最大者和最小者),从而使排序趟数几乎减少了一半*/ 
    
        //对空表做排序没意义 
        if(SSTableEmpty_Seq(ST)) { 
            return ERROR; 
        }//if 
    
        int low = 1, high = ST.length, tmp, j;    
    
        while (low < high) {
    
            //正向冒泡,找到最大者 
            for (j = low; j < high; ++j) { 
                if (ST.elem[j].key > ST.elem[j + 1].key){  
                    tmp = ST.elem[j].key; 
                    ST.elem[j].key = ST.elem[j + 1].key;
                    ST.elem[j + 1].key = tmp;  
                }//if   
            }//for 
    
            //修改high值, 前移一位
            --high;
    
            //反向冒泡,找到最小者
            for (j = high; j > low; --j) {
                if (ST.elem[j].key < ST.elem[j - 1].key) {  
                    tmp = ST.elem[j].key; 
                    ST.elem[j].key = ST.elem[j - 1].key;
                    ST.elem[j - 1].key = tmp;  
                }//if
            }//for
    
            //修改low值,后移一位 
            ++low; 
        }//while  
    } //SortSSTable_Seq
    
    //7.----------------------有序表的折半查找算法------------------
    
    /*
        函数:Search_Bin
        参数:SSTable ST 静态查找表ST 
        返回值:若找到,则函数值为该元素在表中的位置,否则为0 
        作用:在有序表ST中折半查找其关键字等于key的数据元素
    */
    int Search_Bin(SSTable ST, KeyType key){
    
        //置区间初值
        int low = 1, high = ST.length, mid;
    
        //当low > high时查找结束 
        while(low <= high){
    
            //计算出mid 
            mid = (low + high) / 2;
    
            //找到待查元素
            if(EQ(key, ST.elem[mid].key)) {
                return mid;
            }//if
            //继续在前半区间进行查找 
            else if(LT(key,ST.elem[mid].key)) {
                high = mid - 1;
            }//else if 
            //继续在后半区间进行查找
            else { 
                low = mid + 1;
            }//else 
        }//while 
    
        //顺序表中不存在待查元素
        return 0; 
    }//Search_Bin 
    
    //8.-----------------------静态查找表的销毁操作--------------------
    
    /*
        函数:DestorySSTable_Seq
        参数:SSTable &ST 静态查找表引用 
        返回值:无 
        作用:销毁静态查找表ST
    */
    void DestorySSTable_Seq(SSTable &ST){
    
        //释放静态查找表内存空间 
        free(ST.elem);
    
        //指针置空 
        ST.elem = NULL;
    
        printf("内存空间释放成功!\n");  
    } //DestorySSTable_Seq
    
    //***************************************主函数******************************************** 
    int main(int argc,char *argv[]){ 
    
        //声明顺序查找表ST 
        SSTable ST; 
    
        //关键字         
        KeyType key;
    
        //状态标志
        Status flag;
    
        printf("\n***************************顺序表及有序表查找算法测试***************************\n");
    
        printf("->创建一个静态查找(顺序)表,请按要求进行操作\n"); 
        InitSSTable_Seq(ST);
        SSTableInput_Seq(ST);
        printf("->您创建的静态查找表包含的所有元素如下:\n");
        SSTableTraverse_Seq(ST, Print);
    
        printf("->请输入您想在顺序表中查找的元素:\n");
        scanf("%d", &key);
        flag=Search_Seq(ST, key); 
        if(!flag) { 
           printf("查找失败!\n"); 
        }//if 
        else {
           printf("查找成功!该元素在表中的位置为%d,表中该位置元素值为%d。\n",
                flag, ST.elem[flag].key);
        }//else
    
        printf("对顺序表排序,准备进行有序表查找。\n");
        SortSSTable_Seq(ST);
        printf("->排序后顺序表变为有序表,表中所有元素依次是:\n");
        SSTableTraverse_Seq(ST, Print);
    
        printf("->请输入您想在有序表中查找的元素:\n");
        scanf("%d", &key);
        flag=Search_Bin(ST, key); 
        if(!flag) {
           printf("查找失败!\n"); 
        }//if 
        else {
           printf("查找成功!该元素在表中的位置为%d,表中该位置元素值为%d。\n",
                flag, ST.elem[flag].key);
        }//else
    
        printf("->销毁静态查找表ST:");
        DestorySSTable_Seq(ST); 
    
        return 0;   
    }//main 

    输入数据来自书上P219页。

    程序运行时输出:

    ->创建一个静态查找(顺序)表,请按要求进行操作
    ->您想输入几个元素,请输入个数,最多不可以超过100  11
    请输入静态查找表ST的元素,中间用空格隔开,最多不可以超过100个元素
    05 13 19 21 37 56 64 75 80 88 92
    ->您创建的静态查找表包含的所有元素如下:
      5  13  19  21  37  56  64  75  80  88  92
    ->请输入您想在顺序表中查找的元素:
    12
    查找失败!
    对顺序表排序,准备进行有序表查找。
    ->排序后顺序表变为有序表,表中所有元素依次是:
      5  13  19  21  37  56  64  75  80  88  92
    ->请输入您想在有序表中查找的元素:
    88
    查找成功!该元素在表中的位置为10,表中该位置元素值为88。
    ->销毁静态查找表ST:内存空间释放成功!
    
    --------------------------------
    Process exited with return value 0
    Press any key to continue . . .

    总结:顺序表排序后变为有序表,查找效率有所提升。

    下次的文章会介绍动态查找表也就是二叉排序树的实现。感谢大家一直以来的关注和支持。再见!

    展开全文
  • 静态查找表

    2020-06-01 21:38:24
    静态查找表只查找,不进行插入或删除。 静态查找表的操作有: Create(&ST, n)构造一个含有 n 个数据元素的静态查找表 Destory(&ST) 销毁表 ST,前提是表存在 Search(ST, kval) 若 ST 中存在其关键字等于 kval 的...

    静态查找表只查找,不进行插入或删除。

    静态查找表的操作有:
    Create(&ST, n)构造一个含有 n 个数据元素的静态查找表

    Destory(&ST) 销毁表 ST,前提是表存在

    Search(ST, kval) 若 ST 中存在其关键字等于 kval 的数据元素,则函数值为该元素的值,或在查找表中的位置,否则为空。

    Traverse(ST)  按照某种次序输出 ST 中的每个数据元素

    静态查找表的顺序存储表示:

     

    typedef struct
    {
       ElemType *elem;//数据元素存储空间基址,建表时按实际长度分配,0号单元留空
       int length;//表中元素个数
    }SSTable;
    

    1、静态查找的方法

     

    (1)顺序查找

     

    int Search_Seq(SSTable ST,KeyType kval)
    {//在顺序表 ST中顺序查找其关键字等于 kval 的数据元素,若找到,则函数值为该元素在表中的位置
       ST.elem[0].key=kval;//设置哨兵
       for(i=ST;length; ST.elem[i].key != kval; --i);//从后往前找
       return i;//找不到时,i为0
    }
    

    平均查找长度:查找过程中先后和给定值进行比较的关键字个数的期望值称做查找算法的平均查找长度。

     

    顺序查找的平均查找长度是 (n+1)/2

    (2)折半查找

    折半查找又称二分查找。

     

    int Search_Bin(SSTable ST, KeyType kval)
    {//在有序表ST中折半查找其关键字等于 kval 的数据元素,若找到,则函数值为该元素在表中的位置,否则为0
       low=1; high=ST.length;//置区间初值
       while(low<=high)
       {
          mid=(low+high)/2;
          if(kval == ST.elem[mid].key)  return mid;//找到查找元素
          else
               if(kval < ST.elem[mid].key) high=mid-1;
               else   low=mid+1;
       }
       return 0;//顺序表中不存在待查元素
    }
    

    折半查找的平均查找长度为

     

          ASL = (n+1)/n * log2 (n+1) - 1;

    (3)分块查找

    分块查找又称索引顺序查找,其性能介于顺序查找和折半查找之间,它适合对关键字“分块有序”的查找表进行查找操作。

    块间有序,块内无序。查找表中的记录按其关键字的大小分成若干块,前一块的最大关键字小于后一块的最大关键字,而各块内部的关键字不一定有序。

    查找的过程分为两步进行:先在索引表中进行折半或顺序查找,以确定待查记录“所在块”;然后在已限定的那一块中进行顺序查找。

     

     

     

    展开全文
  • C语言数据结构静态动态查找表实验

    千次阅读 2020-07-07 12:57:41
    算法2:采用顺序存储结构创建静态查找表--有序表,对有序表进行二分查找 */ #include<stdio.h> #include<stdlib.h> #define EQ(a,b) ((a)==(b)) #define LT(a,b) ((a)<(b)) #define LQ(a,b) ((a)<...
  • 数据结构-静态查找表查找方法

    千次阅读 2019-10-24 17:01:15
    1.顺序查找 从表的一端开始,逐个将记录的关键字和给定值比较,若找到一个记录的关键字与给定值相等,则查找成功;若整个表中记录均比较...设查找表元素存储在一维数组r[1,…,n]中,在表中的元素已经按关键字递增...
  • 静态查找表 顺序查找表 顺序表与线性链表都可以表示静态查找表。两者的实现静态查找表相似,这里以顺序表为例。 顺序查找就是从表中最后一个记录开始,逐个进行记录关键字与给定值的比较,若某个记录的关键字和给定...
  • 根据查找表的定义,我们可以知道静态查找表的功能就是查询(查询某个元素是否在表中,查询某个特定元素的各种属性) 所以静态查找表的基本操作: 1.Create(&ST,n); 操作结果:构造一个含n个数据元素的静态查找...
  • 静态查找表算法

    千次阅读 2019-05-30 11:50:45
    算法2:采用顺序存储结构创建静态查找表——有序表,对有序表进行二分查找; #include <stdio.h> #include <stdlib.h> typedef int KeyType; //typedef float KeyType //typedef char...
  • 数据结构(21)--查找之静态查找表

    千次阅读 2016-03-07 14:30:05
    1.静态查找表 查找的定义:给定一个值k,在含有n个结点的表(或文件)中找出关键字等于给定值k的结点,若找到,则查找成功,输出该结点在表中的位置;否则查找失败,输出查找失败的信息。 查找表是由具有同...
  • 1.静态查找表 2.静态查找的三种方法 2.1顺序查找 2.1.1概念 2.1.2分类 2.1.3源代码示例 2.1.4性能分析 2.2二分查找 2.2.1实现算法前提 2.2.2实现思路(以升序为例) 2.2.3源代码示例 2.2.4性能分析 2.3...
  • 静态查找表的顺序存储结构

    千次阅读 2014-05-18 08:40:28
    //参考书目:《数据结构(C语言版)》严蔚敏,第9章,静态查找表的顺序存储结构。 void main(void) { SSTable st; KeyType key = 3; Create(&st, 10); SearchScanf_Seq(&st); //printf("%d %s %d",st.elem->key, ...
  • 引言:  查找表一般
  • 实验七 静态查找表的查找

    千次阅读 多人点赞 2017-12-23 21:35:31
    ZZU的学弟学妹们不要抄作业哦~(`Д´) 一、实验目的 ...2.建立有序顺序查找表,并在此查找表上实现二分查找操作。   三、实验要求 1.建立顺序查找表,并在此查找表上实现顺序查找操作。 根...
  •  对查找表经常进行的操作有:1、查找某个"特定的"数据元素是否在查找表中;2、检索某个"特定的"数据元素的各种属性;3、在查找表中插入一个数据元素;4、从查找表中删去某个数据元素。对查找表只作前两种统称为...
  • 顺序有序表查找顺序查找定义:从线性表中的第一个(或最后一个)数据元素开始,逐个进行数据元素关键字和给定值的比较,若某个数据元素的关键字和给定值相等则查找成功;如果直到最后一个(或第一个)数据元素,...
  • 静态查找表的建立及顺序查找操作

    千次阅读 2011-07-10 15:19:11
    查找是数据结构中很重要的一部分,最近在看查找表,首先是静态查找表静态查找表可以以顺序表和线性链表来表示,用Search函数来顺序查找,从表中最后一个记录开始,逐个进行记录的关键字和给定值进行比较,如果相等...
  • 有序表查找---折半查找算法

    万次阅读 2019-03-10 20:00:31
    折半查找的基本思想是:在有序表中,取中间值为比较对象,如果给定的值和中间值的关键字相等,则查找成功;若给定值小于中间记录的关键字,则在中间记录的左半区继续查找;若给定的值大于中间值的关键字,则在中间...
  • 数据结构:静态查找动态查找

    千次阅读 2019-03-15 15:32:10
    首先无论是静态查找还是动态查找,都要有查找的对象,也就是包含很多同类型数据的“”,这个“”可以理解为一个由同类型数据元素组成的一个“集合”,该集合可以用各种容器来存储,例如数组、链表、树等,我们...
  • 有关在静态查找表中对特定关键字进行顺序查找、折半查找或者分块查找,都是在查找表中各关键字被查找概率相同的前提下进行的。 例如查找表中有 n 个关键字,表中每个关键字被查找的概率都是 1/n。在等概率的情况,...
  • 数据结构:静态查找表(顺序表)

    千次阅读 2015-05-08 22:57:49
    printf("\t\t | [1]创建静态查找表 |\n");  printf("\t\t | [2]销毁静态查找表 |\n"); printf("\t\t | [3]顺序查找 |\n"); printf("\t\t | [4]折半查找 |\n"); printf("\t\t | ...
  • 数据的静态查找:顺序表查找有序表的折半查找 顺序查找: 将数据与待查找的元素相比较,如果找到相同的元素,就表示查找成功,否则查找失败。值得注意的是,在程序中设置了一个哨兵项,位于数组的第0个合肥位置,...
  • 查找8.2 顺序8.2.1 顺序查找基本思想顺序存储结构下的顺序查找算法平均查找长度8.2.2 有序表的折半查找折半查找的算法思想折半查找算法一般代码二叉搜索树 8.2 顺序 采用顺序存储结构的数据称为顺序。...
  • 查找算法 | 静态(次优查找树)详细分析

    千次阅读 多人点赞 2018-11-04 11:36:05
    前面章节所介绍的有关在静态查找表中对特定关键字进行顺序查找、折半查找或者分块查找,都是在查找表中各关键字被查找概率相同的前提下进行的。 例如查找表中有 n 个关键字,表中每个关键字被查找的概率都是 1/n。...
  • 一、顺序的顺序查找 1、顺序查找的一端开始,逐个检测每个记录是不是要查的记录。找到则查找成功,一直找到另一端还没找到则失败。 1)顺序存储结构下的顺序查找 #include using namespace std; typedef ...
  • 数据结构之查找表

    千次阅读 2018-11-12 18:30:57
    今天学习数据结构看到了一个词-静态查找表,还有与之对应的动态查找表,然后我发现。 啊,这是个啥,好像知道又好像不知道,不就是查找吗,干嘛弄这些专业的说法,回头翻了一下数据结构的书,才发现......。 唉,...
  • #include<iostream> using namespace std; SqList L; int number=0; Status InitList_Sq(SqList &...L){ //构造一个空的顺序L L.elem = new ElemType[MAXSIZE]; //为顺序分配空间 if (!L.elem) exit(O...
  • 查找(一)静态表查找

    千次阅读 2015-07-06 21:47:13
    静态表查找包括:顺序表查找有序表查找静态表查找、索引表查找 具体原理这里不叙述,详见严蔚敏《数据结构》。1、顺序表查找//SequenceTableSearch.c#include #include #include <string.h>typedef char ...
  • 查找表分类:静态查找表和动态查找表静态查找表:只查找,而不进行插入,删除。 动态查找表:在查找过程中同时插入查找表中不存在的数据元素,或者从查找表中删除已经存在的某个数据元素。 静态表...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 40,955
精华内容 16,382
关键字:

创建静态有序查找表