文章目录

数据结构 P7 基础查找简介查找概论查找算法 顺序查找顺序查找的实现顺序查找的优化 有序查找折半查找及实现差值查找及实现斐波那契查找简介 线性索引查找分块索引查找及实现稠密索引查找简介倒排索引查找简介 哈希表查找简介二叉排序树简介更多内容

数据结构 P7 基础查找

简介

查找概论

查找概念

查找（Searching）就是根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素

查找表

查找表（Search Table）是由同一类型的数据元素构成的集合

关键字

关键字（Key）是数据元素中某个数据项的值

主关键字与次关键字

若此关键字可以唯一地标识一个记录，则称此关键字为主关键字（Primary Key）

可以识别多个数据元素的关键字，则称为次关键字（Secondary Key）

举个栗子

查找算法

静态查找表

静态查找表（Static Search Table）只作查找操作的操作表

1.查询某个特定的数据元素是否在查找表中 2.检索某个特定的数据元素的各种属性

动态查找表

动态查找表（Dynamic Search Table）在查找过程中同时插入查找表中不存在的数据元素，或者从查找表中删除已经存在的某个数据元素

1.查找时插入数据元素 2.查找时删除数据元素

---

顺序查找

顺序查找（Sequential Search）又叫线性查找，是最基本的查找技术，它的查找过程是：从表中第一个（或最后一个）记录开始，逐个进行记录的关键字和给定值比较，若某个记录的关键字和给定值相等，则查找成功，找到所查的记录；如果直到最后一个记录，其关键字和给定值比较都不等时，则表中没有所查的记录，查找不成功

有序查找

有序查找就是先对表进行有序排列在进行查找的方法

线性索引查找

索引就是把一个关键字与它对应的记录相关联的过程，一个索引由若干个索引项构成，每个索引项至少应包含关键字和其对应的记录在存储器中的位置等信息

所谓线性索引就是索引项集合组织为线性结构，也称为索引表

哈希表查找

哈希表（Hash Table）也称为散列表

哈希技术是在记录的存储位置和它的关键字之间建立一个确定的对应关系f，使得每个关键字key对应一个存储位置f

二叉排序树查找

二叉排序树（Binary Sort Tree）又称为二叉查找树，它或者是一颗空树

顺序查找

顺序查找（Sequential Search）又叫线性查找，是最基本的查找技术，它的查找过程是：从表中第一个（或最后一个）记录开始，逐个进行记录的关键字和给定值比较，若某个记录的关键字和给定值相等，则查找成功，找到所查的记录；如果直到最后一个记录，其关键字和给定值比较都不等时，则表中没有所查的记录，查找不成功

顺序查找的实现

这里以之前线性顺序表的程序为基础编写查找算法

之前已经实现了一定的查找算法

这里是查找指定位置和指定内容的内容 其实这里的指定位置或者指定内容就是关键字

所以这里重新建立一个函数来写一下最简单的顺序查找算法

顺序查找算法

sqlist.h

int sqsearch(sqlink L,data_t key);//顺序表查找算法

sqlist.c

int sqsearch(sqlink L,data_t key){ int i; for(i = 1;i <= L->last;i++){ if(L->data[i] == key){ return i; } } return 0; }//顺序表查找算法

test.c

int search_test(){ //创建表 sqlink L; L = sqlist_create(); int a[]={0,3,5,7,9,11,12,13,14,15}; int n =sizeof(a)/sizeof(int); sqlist_arrayinsert(L,a,n,0); sqlist_show(L); //查找算法 int s,key; printf("请选择查找算法\n"); printf("0.退出1.顺序查找："); scanf("%d",&s); switch(s){ case 0:break; case 1:printf("input key:"); scanf("%d",&key); printf("%d\n",sqsearch(L,key)); break; default:printf("不在范围内请重新输入!\n"); } }

测试程序

顺序查找的优化

当然最简单的顺序查找固然简单，但是当数据增多后上面的算法需要遍历所有的数据在输出最终的结果，每次还需要与数据的长度做比较，因此这里对基本的算法做出优化

顺序查找优化算法

sqlist.h

int sqsearch2(sqlink L,data_t key);//顺序表查找算法优化

sqlist.c

int sqsearch2(sqlink L,data_t key){ int i; L->data[0] = key; i = L->last; while(L->data[i] != key){ i--; } return i; }//顺序表查找算法优化

test.c

int search_test(){ //创建表 sqlink L; L = sqlist_create(); int a[]={0,3,5,7,9,11,12,13,14,15}; int n =sizeof(a)/sizeof(int); sqlist_arrayinsert(L,a,n,0); sqlist_show(L); //查找算法 int s,key; printf("请选择查找算法\n"); printf("0.退出1.顺序查找2.顺序查找优化："); scanf("%d",&s); switch(s){ case 0:break; case 1:printf("input key:"); scanf("%d",&key); printf("%d\n",sqsearch(L,key)); break; case 2:printf("input key:"); scanf("%d",&key); printf("%d\n",sqsearch2(L,key)); break; default:printf("不在范围内请重新输入!\n"); } }

测试程序

有序查找

折半查找及实现

折半查找（Binary Search）技术，又称为二分查找。它的前提是线选表中的记录必须是关键码有序，线性表必须采用顺序存储

折半查找的基本思想：在有序表中，取中间记录作为记录的关键字，则在中间记录的左半区继续查找；若给定值大于中间记录的关键字，则在中间记录的右半区继续查找

折半查找算法

sqlist.h

int bnsearch(sqlink L,data_t key);//折半查找算法

sqlist.c

int bnsearch(sqlink L,data_t key){ int low,high,mid; low = 1; high = L->last; while(low <= high){ mid = (low + high)/2; if(key < L->data[mid]){ high = mid - 1; }else if(key > L->data[mid]){ low = mid + 1; }else{ return mid; } } return 0; }//折半查找算法

test.c

int search_test(){ //创建表 sqlink L; L = sqlist_create(); int a[]={0,3,5,7,9,11,12,13,14,15}; int n =sizeof(a)/sizeof(int); sqlist_arrayinsert(L,a,n,0); sqlist_show(L); //查找算法 int s,key; printf("请选择查找算法\n"); printf("0.退出1.顺序查找2.顺序查找优化3.折半查找;："); scanf("%d",&s); switch(s){ case 0:break; case 1:printf("input key:"); scanf("%d",&key); printf("%d\n",sqsearch(L,key)); break; case 2:printf("input key:"); scanf("%d",&key); printf("%d\n",sqsearch2(L,key)); break; case 3:printf("input key:"); scanf("%d",&key); printf("%d\n",bnsearch(L,key)); break; default:printf("不在范围内请重新输入!\n"); } }

测试程序

差值查找及实现

插值查找（Interpolation Search）是根据要查找的关键字key与查找表中最大最小记录的关键字比较后的查找方法

其核心就在于插值的计算公式 key-a[low]/a[high]-a[low]

差值查找算法

sqlist.h

int bnsearch(sqlink L,data_t key);//折半查找算法

sqlist.c

int bnsearch2(sqlink L,data_t key){ int low,high,mid; low = 1; high = L->last; while(low <= high){ mid = low + (high - low) * (key - L->data[low]) / (L->data[high] - L->data[low]); if(key < L->data[mid]){ high = mid - 1; }else if(key > L->data[mid]){ low = mid + 1; }else{ return mid; } } return 0; }//插值查找算法

test.c

int search_test(){ //创建表 sqlink L; L = sqlist_create(); int a[]={0,3,5,7,9,11,12,13,14,15}; int n =sizeof(a)/sizeof(int); sqlist_arrayinsert(L,a,n,0); sqlist_show(L); //查找算法 int s,key; printf("请选择查找算法\n"); printf("0.退出1.顺序查找2.顺序查找优化3.折半查找;4.插值查找："); scanf("%d",&s); switch(s){ case 0:break; case 1:printf("input key:"); scanf("%d",&key); printf("%d\n",sqsearch(L,key)); break; case 2:printf("input key:"); scanf("%d",&key); printf("%d\n",sqsearch2(L,key)); break; case 3:printf("input key:"); scanf("%d",&key); printf("%d\n",bnsearch(L,key)); break; case 4:printf("input key:"); scanf("%d",&key); printf("%d\n",bnsearch2(L,key)); break; default:printf("不在范围内请重新输入!\n"); } }

测试程序

斐波那契查找简介

折半查找是从中间分，也就是说，每一次查找总是一分为二，无论数据偏大还是偏小，很多时候这都未必就是最合理的做法，斐波那契查找（Fibonacci Search），它是利用了黄金分割原理来实现的

线性索引查找

分块索引查找及实现

分块有序是把数据集的记录分成若干块，并且这些块需要满足两个条件：块内无序和块间有序

分块索引的索引项结构分三个数据项： 1.最大关键码，它存储每一块中的最大关键字，这样的好处就是可以使得在它之后的下一块中的最小关键字也能比这一块最大的关键字要大 2.存储了快中的记录个数，以便与循环时使用 3.用于指向块首数据元素的指针，便于开始对这一块记录进行遍历

稠密索引查找简介

稠密索引是指在线索引中将数据集中的每个记录对应一个索引项，对于稠密索引这个索引表来说，索引项一定是按照关键码有序的排列

倒排索引查找简介

搜索技术最简单的查找方法倒排索引 其中记录号表存储具有相同次关键字的所有记录的记录号，这样的索引方法就是倒排索引（Inverted Index）

哈希表查找简介

哈希表（Hash Table）也称为散列表 哈希技术是在记录的存储位置和它的关键字之间建立一个确定的对应关系f，使得每个关键字key对应一个存储位置f

二叉排序树简介

二叉排序树（Binary Sort Tree），又称为二叉查找树。它或者是一颗空树，或者是具有下列性质的二叉树 若它的左子树不空，则左子树上所有结点的值均小于它的根结构的值 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值 它的左、右子树也分别为二叉排序树

更多内容