精华内容
下载资源
问答
  • 有序表的查找

    2018-03-06 23:14:15
    int Search_Bin(SSTable ST, KeyType ...若找到,则函数值为 //该元素在表中的位置,否则为0. low = 1; high = ST.length; //置区间初值 while(low <= high){ mid = (low + high) / 2; if(EQ(key, ST.elem[...
    int Search_Bin(SSTable ST, KeyType key){
    //在有序表ST中折半查找其关键字等于key的数据元素。若找到,则函数值为
    //该元素在表中的位置,否则为0.
    low = 1; high = ST.length; //置区间初值
    while(low <= high){
    mid = (low + high) / 2;
    if(EQ(key, ST.elem[mid].key))
    return mid; //找到待查元素
    else if(LT(key, ST.elem[mid.key]))
    high = mid - 1; //继续在前半区间进行查找
    else
    low = mid + 1; //继续在后半区间进行查找
    }
    return 0; //表中不存在待查元素
    }//Search_Bin
    展开全文
  • 静态查找表

    2020-06-01 21:38:24
    静态查找表只查找,不进行插入或删除。...Search(ST, kval) 若 ST 中存在其关键字等于 kval 的数据元素,则函数值为该元素的值,或在查找表中的位置,否则为空。 Traverse(ST) 按照某种次序输出 ST 中的每个数据元

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

    静态查找表的操作有:
    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)分块查找

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

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

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

     

     

     

    展开全文
  • 线性表中的元素递增有序且按顺序存储于计算机内,要求设计一个算法,完成用最少时间在表中查找数值为x的元素,若找到将其与其后继元素交换位置,若表中没有,插入此元素仍使线性表有序递增。 1.代码实现: /*算法...

    线性表中的元素递增有序且按顺序存储于计算机内,要求设计一个算法,完成用最少时间在表中查找数值为x的元素,若找到将其与其后继元素交换位置,若表中没有,插入此元素仍使线性表有序递增。

    1.代码实现:

    /*算法思想:题目关键字:最少时间:折半查找法(二分法)
    与后继交换位置(考虑无后继情况),插入后仍递增有序(插入数据后进行位置变换)*/
    #include"head.h"
    //折半查找法
    int BinarySearch(SeqList &L ,int x) {
    	int low = 0, high = L.length - 1, mid;
    	while (low<=high)
    	{
    		mid = (low + high) / 2;//找中间值
    		if (L.data[mid]==x)//先与中间值比较
    		{
    			return mid;//相等就返回其值
    		}
    		else if (L.data[mid]<x)//如果中间值小于x,则向后半段查找
    		{
    			low = mid + 1;
    		}
    		else//如果中间值大于x,则向前半段查找
    		{
    			high = mid - 1;
    		}
    	}
    	return -1;//如果没有找到,返回-1
    }
    //整体函数:查找、交换、插入
    void SearchExchangeInsert(SeqList& L, int x) {
    	int mid, temp;
    	mid = BinarySearch(L, x);
    	if (mid!=-1&&mid!=L.length-1)//x值存在且不在最后一位(最后一位没有后继元素)
    	{
    		temp = L.data[mid];
    		L.data[mid] = L.data[mid + 1];
    		L.data[mid + 1] = temp;
    	}
    	if (mid==-1)//x值不存在
    	{
    		int i = L.length - 1;
    		for (;L.data[i]>x;i--)//从表的后面往前判断,找到大于x的元素
    		{
    			L.data[i + 1] = L.data[i];//后移元素
    		}
    		L.data[i + 1] = x;//插入x
    		L.length = L.length + 1;//插入一个元素后表长加1
    	}
    }
    int main() {
    	SeqList L;
    	InitList(L);
    	printf("请输入顺序表内容:\n");
    	for (int i = 0; i < InitSize; i++) {//手动输入最初数组长度个数的数
    		scanf_s("%d", &L.data[i]);
    		L.length++;
    	}
    	printf("顺序表内容为:\n");
    	printList(L);
    	SearchExchangeInsert(L, 4);
    	printf("操作后顺序表内容为:\n");
    	printList(L);
    }
    

    2.注意点

    1. 有序顺序表中最快查找法为折半查找法(二分查找法),时间复杂度为O(logn),顺序查找的时间复杂度为O(n),折半查找法的讲解请查看“数据结构笔记7”
    2. 写程序时将一些公共函数放在了头文件中,没有头文件无法运行程序,具体详解参考“数据结构笔记2”
    展开全文
  • 有序递增顺序表L中,使用最少的时间查找数值为x的元素,若找到则将其与后继元素位置交换,若找不到则将其插入表中并使表中并使表中的元素仍然递增有序。 二 算法思想 对于有序递增顺序表的查找问题,我们可以...

    一 概述

    在有序递增顺序表L中,使用最少的时间查找数值为x的元素,若找到则将其与后继元素位置交换,若找不到则将其插入表中并使表中并使表中的元素仍然递增有序。

    二 算法思想

    对于有序递增顺序表的查找问题,我们可以采用顺序查找,也可以使用折半查找。显然后者比前者效率高,所以使用折半查找会比较快。

    三 代码实现

    顺序查找:从表的一端开始,依次将记录的关键字和给定的值进行比较,若某个记录的关键字和给定的值相等,则查找成功;反之,若扫描整个表后,仍未找到关键字和给定值相等的记录,则查找失败。顺序查找方法既适用于线性表的顺序存储结构,又使用于线性表的链式存储结构。

    #include<iostream>//输入头 
    using namespace std;//标准输入输出
    
    typedef int Status;
    typedef int ElemType;
    
    #define MAXSIZE 100
    #define ERROR -1
    #define OK 0
    
    typedef struct {
    	ElemType *elem;
    	int length;
    }SqList; 
    
    Status init_Queue(SqList &L){
    	
    	L.elem = new ElemType[MAXSIZE]; //初始化最大长度的顺序表 
    	
    	if(!L.elem){
    		return ERROR; //初始化失败 
    	}
    	
    	L.length = 0; //初始时数据表为空 
    	return OK;
    }
    
    Status FindAndSwop_Queue(SqList &L,ElemType x) {
    	
    	ElemType temp;
    	int i=0,j=0;
    
    	while(i<L.length) {
    		if(L.elem[i]==x && i != L.length -1) {
    			temp = L.elem[i];
    			L.elem[i] = L.elem[i+1];
    			L.elem[i+1] = temp;
    			break;
    		}
    		
    		if(x > L.elem[L.length-1]){
    			L.elem[L.length] = x;
    			L.length++;
    		}else if(L.elem[i] < x && x < L.elem[i+1]){
    			for(j = L.length - 1; j >= i+1; j--){
    				L.elem[j+1] = L.elem[j];
    			}
    			++L.length;
    			L.elem[i+1] = x;
    			break; 
    		}
    		i++;
    	}
    
    	return OK;
    }
    
    int main(){
    	SqList L;
    	ElemType x;
    	 
    	cout<<"1.初始化顺序表!\n";
    	cout<<"2.输入6个不同的数字!\n";
    	cout<<"3.查询x并且保持有序的序列!\n";
    	cout<<"0.退出!"<<endl<<endl;
    	
    	int elect = -1;
    	
    	while(elect !=0){
    		cout<<"请选择你的后续操作:"; 
    		cin>>elect;
    		switch(elect){
    			case 1:
    				if(!init_Queue(L)){
    					cout<<"初始化顺序表成功!"<<endl; 
    				}else{
    					cout<<"初始化顺序表失败!"<<endl; 
    				}
    				break;
    			case 2:
    				cout<<"请输入6不同数字:" ;
    				for(int i = 0; i < 6; i++){
    					cin>>L.elem[i];
    					L.length = 6; 
    				}
    				break;
    			case 3:
    				cout<<"请输入要查找的数字:"; 
    				cin>>x; 
    				FindAndSwop_Queue(L,x);
    				cout<<"查询x并且保持有序的序列为:" ;
    				for(int i = 0; i < L.length; i++ ){
    				 cout<<L.elem[i]<<" ";
    				} 
    				cout<<endl; 
    				break;
    		}
    	}
    	return 0;
    }
    

    顺序查找的结果:

      

    折半查找(二分查找):折半查找是一种效率比较高的查找方法,但是,折半查找要求线性表必须采用顺序存储结构,而且表中的元素按关键字有序排序。该算法已经定义了递增,所以在折半查找的过程中,从表中间记录开始,如果给定值和中间记录关键字相等,则查找成功;如果给定值大于或者小于中间记录的关键字,则在表中大于或者小于中间记录的那一半中查找,这样重复操作,直到查找成功,或者在某一步中查找区间为空,则代表查找失败。

    折半查找每一次查找比较都使查找范围缩小一半,与顺序查找相比,很显然会提高查找效率。为了标记查找过程中每一次的查找区间,我们可以定义low和high来表示当前查找区间的下界和上界,mid为区间的中间位置。

    /*
    折半查找的步骤:
    1.设置查找区间初值,low为1,high为表长度
    2.当low小于high时,循环执行一下操作:
        。min取值为low和high的中间值;
        。将给定值key与中间位置记录的关键字进行比较,若相等则查找成功,返回中间位置mid;
        。若不相等则利用中间位置记录将表对分成前,后两个子表。如果key比中间位置记录的关键字
          小,则high重新取值为mid-1,否则low重新取值为mid+1;
    3.循环结束,说明查找区间为空,则查找失败,返回0;
    */
    #include<iostream>//输入头 
    using namespace std;//标准输入输出
    
    typedef int Status;
    typedef int ElemType;
    
    #define MAXSIZE 100
    #define ERROR -1
    #define OK 0
    
    typedef struct {
    	ElemType *elem;
    	int length;
    }SqList; 
    
    Status init_Queue(SqList &L){
    	
    	L.elem = new ElemType[MAXSIZE]; //初始化最大长度的顺序表 
    	
    	if(!L.elem){
    		return ERROR; //初始化失败 
    	}
    	
    	L.length = 0; //初始时数据表为空 
    	return OK;
    }
    
    Status FindAndSwop_Queue(SqList &L,ElemType x) {
    	
    	ElemType temp;
    	int low = 0, high = L.length-1, mid,i;
    
    	while(low <= high) {
    		//在循环体中初始化mid值,是为了在动态变化中mid值也会动态变化。 
    		mid = (low+high)/2;
    		//mid < L.length表示若是最后一个元素与x相等,则不存在与其后继交换的操作。 
    		if(L.elem[mid] == x && mid < L.length - 1){
    			temp = L.elem[mid];
    			L.elem[mid] = L.elem[mid+1];
    			L.elem[mid+1] = temp;
    			break; 
    		}else if(L.elem[mid] < x) {
    			low = mid + 1;
    		}else{
    			high = mid -1;
    		}
    	}
    	
    	if(low > high){
    		//当high<low的时候,说明查找区间不存在,也即没有关键字为x的元素,此时选择插入值为x的元素 
    		//于此同时可得,关键字为x的元素值属于区间L.elem[high]<x<L.elem[low]; 
    		for(i = L.length - 1; i > high ; i--) { 
    			L.elem[i+1] = L.elem[i];
    		}
    			++L.length;
    			L.elem[i+1] = x;
    	} 
    	return OK;
    }
    
    int main(){
    	SqList L;
    	ElemType x;
    	 
    	cout<<"1.初始化顺序表!\n";
    	cout<<"2.输入6个不同的数字!\n";
    	cout<<"3.查询x并且保持有序的序列!\n";
    	cout<<"0.退出!"<<endl<<endl;
    	
    	int elect = -1;
    	
    	while(elect !=0){
    		cout<<"请选择你的后续操作:"; 
    		cin>>elect;
    		switch(elect){
    			case 1:
    				if(!init_Queue(L)){
    					cout<<"初始化顺序表成功!"<<endl; 
    				}else{
    					cout<<"初始化顺序表失败!"<<endl; 
    				}
    				break;
    			case 2:
    				cout<<"请输入6不同数字:" ;
    				for(int i = 0; i < 6; i++){
    					cin>>L.elem[i];
    					L.length = 6; 
    				}
    				break;
    			case 3:
    				cout<<"请输入要查找的数字:"; 
    				cin>>x; 
    				FindAndSwop_Queue(L,x);
    				cout<<"查询x并且保持有序的序列为:" ;
    				for(int i = 0; i < L.length; i++ ){
    				 cout<<L.elem[i]<<" ";
    				} 
    				cout<<endl; 
    				break;
    		}
    	}
    	return 0;
    }

    折半查找的结果:

      

    四 顺序查找与折半查找的特点

    顺序查找的优点:对于表结构无任何要求,既适用于顺序结构,也适用于链式结构,无论记录是否按关键字有序均可应用。

    顺序查找的缺点:平均查找长度较大,查找效率较低,所以当表长很大的时候,不适合使用顺序查找

    折半查找的优点:折半查找的次数比较少,查询效率高。

    折半查找的缺点:折半查找对表结构要求比较高,只能用于顺序存储的有序表,查找前需要排序,而排序本身是一种费时的运算。同时为了保持顺序表的有序性,对有序表进行插入和删除时,平均比较和移动表中一半元素,同样比较费时,故折半查找不适合数据元素经常变动的线性表

    展开全文
  • 通过键盘创建有若干个元素(可以是整型数值单链表,实现对单链表初始化,对已建立顺序插入操作、删除操作、查找操作、遍历输出单链表。 要求各个操作均以函数形式实现,并且主函数调用各个函数...
  • ( 2 )顺序表的第 3 个位置插入 67 ,并输出此时顺序表中的各元素值。 ( 3 )删除顺序表中的第 6 个数据元素,并输出此时顺序表中的各元素值。 ( 4 )查找顺序表中是否有 75 这个元素,如果有返回该...
  • 1、哈希函数的定义 对于一些查找表来说,它的查找过程是:为给定值按某种顺序和记录集合...记录在表中的位置为关键字的某个函数值 H(key) ,通常称这个函数 H(key) 为哈希函数。 2、哈希表的定义 哈希表定义:根据设定
  • 数组、链表以及树等数据结构,数据存储位置和数据具体数值之间不存在任何关系。因此,面对查找问题时,这些数据结构必须采取逐一比较方法去实现。 而哈希表的设计采用了函数映射思想,将记录存储...
  • 用于查找与指定数值相匹配的数值在数组中的相应位置。如果需要找出匹配元素的位置而不是匹配元素本身,则应该使用MATCH函数而不是 LOOKUP函数。 match 函数经常与其它函数相结合使用,如index 函数等。 ...
  • 现需要修改sql数据库里面一个数值,但不记得哪个位置,哪个表中了。 求能达到以下效果查询语句: 查出“2010冬至”这几个字段所在表,以及所在具体位置! 参见:...
  • 顺序表的插入、删除和查找操作

    千次阅读 2019-05-08 15:29:27
    顺序表中第i个位置插入新元素e。如果i不合法,则返回false,表示插入失败;否则,将顺序表第i个位置元素以及其后元素全部右移一个位置,腾出一个空位置插入新元素e,顺序表长增加1,插入成功,返回true。 ...
  • 有序线性表中查找x元素

    千次阅读 2018-04-25 00:19:31
    要求设计以算法完成用最少时间在表中查找数值为x元素,若找到将其与后继元素位置相交换,若找不到将其插入表中并使表中元素仍递增有序。 分析:顺序存储线性表递增有序,结合题目要求,故可以使用折半查找法...
  • 1)题目:线性表(a1,a2,a3....an)中的元素递增有序且按顺序存储于计算机内,要求设计一算法,完成用最小时间在表中查找数值为x的元素,若找到则将其与后续元素位置交换,若找不到则将其查入表中并使表表中元素仍然...
  • 对元素关键码进行同样计算,把求得数值当做元素存储位置结构按此位置取元素比较,若 关键码相等,则搜索成功 该方式即为哈希(散列)方法,哈希方法使用转换函数称为哈希(散列)函数,构造出来...
  • (1) 用最少时间在表中查找数值为x元素。 (2) 若找到将其与后继元素位置相交换。 (3) 若找不到将其插入表中并使表中元素仍递增有序。 输入 输入:x=3 输入长度:9 输入数据:2 3 5 7 12 15 17 23 45 输出 ...
  • 问题 D: 链表查找(线性表) 时间限制: 1 Sec 内存...(1) 用最少时间在表中查找数值为x元素。 (2) 若找到将其与后继元素位置相交换。 (3) 若找不到将其插入表中并使表中元素仍递增有序。 输入 输入:x=3...
  • 要求设计一算法,完成用最少时间在表中查找数值为x元素,若找到则将其与后继元素位置相交换,若找不到则将其插入表中并使表中元素仍递增有序。 关键字有序顺序表 查找+互换 保序新插入 思路 关注:关于查找:顺序...
  • (1) 用最少时间在表中查找数值为x元素。 (2) 若找到将其与后继元素位置相交换。 (3) 若找不到将其插入表中并使表中元素仍递增有序。 输入 输入:x=3 输入长度:9 输入数据:2 3 5 7 12 15 17 23 45 ...
  • 需要判断待删除节点的位置:是头节点、非头节点,同时还有O(n)的时间复杂度。 要求使用O(1)O(1)O(1)的时间复杂度,这时有个巧妙的方法:将该节点的后继节点的值赋值给自身,更改自身的next指针以...
  • (1) 用最少时间在表中查找数值为x元素。 (2) 若找到将其与后继元素位置相交换。 (3) 若找不到将其插入表中并使表中元素仍递增有序。 输入 输入:x=3 输入长度:9 输入数据:2 3 5 7 12 15 17 23 45 ...
  • (1) 用最少时间在表中查找数值为x元素。 (2) 若找到将其与后继元素位置相交换。 (3) 若找不到将其插入表中并使表中元素仍递增有序。 输入: 输入:x=3 输入长度:9 输入数据:2 3 5 7 12 15 17 23 45 输出:...
  • 采用散列技术将记录存储一块连续存储空间,这块连续存储空间称为散列表或哈希 散列地址: 散列函数得到存储位置,即散列函数值称为散列地址。 冲突 构造散列表时,不同关键字可能得到同一个散列...
  • 问题 D: 链表查找(线性表) ...(1) 用最少时间在表中查找数值为x元素。 (2) 若找到将其与后继元素位置相交换。 (3) 若找不到将其插入表中并使表中元素仍递增有序。 输入 输入:x=3 输入长度:...
  • MATCH函数含义:返回指定数值在指定数组区域中的位置 语法:MATCH(lookup_value, lookup_array, match_type) lookup_value:需要在数据(lookup_array)中查找的值。可以为数值(数字、文本或逻辑值)或对数字、...
  • 顺序查找的复习

    2021-05-14 07:58:47
    这一个难题里,我们要求先向顺序表中插入一些元素,之后再输入我们需要查找的值。你的程序需要输出查找次数以及最终的查找结果。 我们已经把大体的代码框架写好了,你只需要正确的位置补全代码就好了。这道题目...
  • 1. 数组中的重复数字 解法一:将数组排序,快排,排序一个长度为n的数组需要O(nlogn)的时间。 解法二:利用HashMap,记录每个数字出现次数,第一个大于2的即可返回。时间复制度为O(n),需要大小为O(n)的哈希为...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 405
精华内容 162
关键字:

查找数值在表中的位置