当前位置：文档之家 › C语言 顺序查找和折半查找

C语言 顺序查找和折半查找

  • 格式：docx
  • 大小：14.91 KB
  • 文档页数：3

下载文档原格式

  / 3

合集下载

查找排序

查找排序
Low指向待查元素 所在区间的下界 mid指向待查元素所在 区间的中间位臵 high指向待查元素所 在区间的上界
解：① 先设定3个辅助标志: low,high,mid， 显然有：mid= (low+high)/2 ② 运算步骤：
(1) low =1,high =11 ,故mid =6 ，待查范围是 [1,11]； (2) 若 S[mid] < key，说明 key[ mid+1,high] ， 则令：low =mid+1;重算 mid＝ (low+high)/2；. (3) 若 S[mid] > key，说明key[low ,mid-1]， 则令：high =mid–1;重算 mid ； (4)若 S[ mid ] = key，说明查找成功，元素序号=mid; 结束条件： （1）查找成功 ： S[mid] = key （2）查找不成功 ： high＜low （意即区间长度小于0）
while(low<=high)
{ mid=(low+high)/2; if(ST[mid].key= = key) return (mid); /*查找成功*/
else if( key< ST[mid].key) high=mid-1; /*在前半区间继续查找*/ else } return (0); /*查找不成功*/
4 5 6 7
0
1
2
90
10
(c)
20
40
K=90
80
30
60
Hale Waihona Puke 25(return i=0 )
6
讨论：怎样衡量查找效率？
——用平均查找长度（ASL）衡量。
如何计算ASL？

折半查找程序

折半查找程序

先看看这个，下面有例子折半查找：二分查找又称折半查找，优点是比较次数少，查找速度快，平均性能好；其缺点是要求待查表为有序表，且插入删除困难。

因此，折半查找方法适用于不经常变动而查找频繁的有序列表。

首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。

重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。

算法要求算法复杂度下面提供一段二分查找实现的伪代码:BinarySearch(max,min,des)mid-<(max+min)/2while(min<=max)mid=(min+max)/2if mid=des thenreturn midelseif mid >des thenmax=mid-1elsemin=mid+1return max折半查找法也称为二分查找法，它充分利用了元素间的次序关系，采用分治策略，可在最坏的情况下用O(log n)完成搜索任务。

它的基本思想是，将n个元素分成个数大致相同的两半，取a[n/2]与欲查找的x作比较，如果x=a[n/2]则找到x，算法终止。

如果x<a[n/2]，则我们只要在数组a的左半部继续搜索x（这里假设数组元素呈升序排列）。

如果x>a[n/2]，则我们只要在数组a的右半部继续搜索x。

二分查找法一般都存在一个临界值的BUG，即查找不到最后一个或第一个值。

可以在比较到最后两个数时，再次判断到底是哪个值和查找的值相等。

C语言代码int BinSearch(SeqList * R，int n , KeyType K ){ //在有序表R[0..n-1]中进行二分查找，成功时返回结点的位置，失败时返回-1int low=0，high=n-1，mid；//置当前查找区间上、下界的初值if(R[low].key==K){return low ;}if(R[high].key==k)return high;while(low<=high){ //当前查找区间R[low..high]非空mid=low+((high-low)/2)；//使用(low + high) / 2 会有整数溢出的问题（问题会出现在当low + high的结果大于表达式结果类型所能表示的最大值时，这样，产生溢出后再/2是不会产生正确结果的，而low+((high-low)/2)不存在这个问题if(R[mid].key==K){return mid；//查找成功返回}if(R[mid].key>K)high=mid-1; //继续在R[low..mid-1]中查找elselow=mid+1；//继续在R[mid+1..high]中查找}if(low>high)return -1；//当low>high时表示查找区间为空，查找失败} //BinSeareh折半查找程序举例程序要求：1.在main函数中定义一个20个元素的int数组，完成初始化和显示操作。

c语言查找算法

c语言查找算法

c语言查找算法
C语言是一种广泛使用的编程语言，它具有高效、简单、易学等特点，因此在各个领域都有广泛的应用。

在C语言中，查找算法是一种非常
重要的算法，它可以帮助我们在大量数据中快速查找到我们需要的数据。

下面我们将详细介绍C语言中的查找算法。

一、顺序查找算法
顺序查找算法是一种最简单的查找算法，它的基本思想是从数据的第
一个元素开始逐个比较，直到找到目标元素或者遍历完整个数据。

顺
序查找算法的时间复杂度为O(n)，其中n为数据的长度。

二、二分查找算法
二分查找算法也称为折半查找算法，它的基本思想是将数据分成两部分，然后判断目标元素在哪一部分中，再在该部分中继续进行查找，
直到找到目标元素或者确定目标元素不存在。

二分查找算法的时间复
杂度为O(logn)，其中n为数据的长度。

三、哈希查找算法
哈希查找算法是一种利用哈希表进行查找的算法，它的基本思想是将数据通过哈希函数映射到哈希表中，然后在哈希表中查找目标元素。

哈希查找算法的时间复杂度为O(1)，但是它需要额外的空间来存储哈希表。

四、树查找算法
树查找算法是一种利用树结构进行查找的算法，它的基本思想是将数据构建成一棵树，然后在树中查找目标元素。

树查找算法的时间复杂度为O(logn)，但是它需要额外的空间来存储树结构。

总结：
C语言中的查找算法有顺序查找算法、二分查找算法、哈希查找算法和树查找算法。

不同的算法适用于不同的场景，我们可以根据实际情况选择合适的算法来进行查找。

在实际应用中，我们还可以将不同的算法进行组合，以达到更高效的查找效果。

c语言数据结构查找算法大全

c语言数据结构查找算法大全

printf("This number does not exist in this array.\n");
else
printf("a[%d]=%d\n",p,x);
}
9.2.2 折半查找(二分查找)
使用折半查找必须具备两个前提条件:
（1）要求查找表中的记录按关键字有序(设,从小到大有序) （2）只能适用于顺序存储结构
}
※折半查找算法性能分析:
在折半查找的过程中，每经过一次比较，查找范围都要缩小一半，所 以折半查找的最大查找长度为
MSL=[log2 n]+1
当n足够大时，可近似的表示为log2(n)。可见在查找速度上，折半查找 比顺序查找速度要快的多，这是它的主要优点。
结论：折半查找要求查找表按关键字有序，而排序是一 种很费时的运算；另外，折半查找要求表是顺序存储的，为 保持表的有序性，在进行插入和删除操作时，都必须移动大 量记录。因此，折半查找的高查找效率是以牺牲排序为代价 的，它特别适合于一经建立就很少移动、而又经常需要查找 的线性表。
查找技术分为： 1 静态查找表技术 顺序查找、折半查找、索引顺序查找 2 动态查找表技术 二叉查找树 3哈希表技术 哈希表技术
※查找算法的衡量指标
在查找一个记录时所做的主要操作是关键字的比较， 所以通常把查找过程中对关键字的平均比较次数作为衡量 一个查找算法效率优劣的标准，并称平均比较次数为平均 查找长度（Average Search Length）。平均查找长度的 定义为：
high2=N-1;
/*N为查找表的长度，high2为块在表中的末地址*/
else
high2=ID[low1+1].addr-1;

非常全C语言常用算法

非常全C语言常用算法

一、基本算法1．交换（两量交换借助第三者）例1、任意读入两个整数，将二者的值交换后输出。

main(){int a,b,t;scanf("%d%d",&a,&b);printf("%d,%d\n",a,b);t=a; a=b; b=t;printf("%d,%d\n",a,b);}【解析】程序中加粗部分为算法的核心，如同交换两个杯子里的饮料，必须借助第三个空杯子。

假设输入的值分别为3、7，则第一行输出为3，7；第二行输出为7，3。

其中t为中间变量，起到“空杯子”的作用。

注意：三句赋值语句赋值号左右的各量之间的关系！【应用】例2、任意读入三个整数，然后按从小到大的顺序输出。

main(){int a,b,c,t;scanf("%d%d%d",&a,&b,&c);/*以下两个if语句使得a中存放的数最小*/if(a>b){ t=a; a=b; b=t; }if(a>c){ t=a; a=c; c=t; }/*以下if语句使得b中存放的数次小*/if(b>c) { t=b; b=c; c=t; }printf("%d,%d,%d\n",a,b,c);}2．累加累加算法的要领是形如“s=s+A”的累加式，此式必须出现在循环中才能被反复执行，从而实现累加功能。

“A”通常是有规律变化的表达式，s在进入循环前必须获得合适的初值，通常为0。

例1、求1+2+3+……+100的和。

main(){int i,s;s=0; i=1;while(i<=100){s=s+i; /*累加式*/i=i+1; /*特殊的累加式*/}printf("1+2+3+...+100=%d\n",s);}【解析】程序中加粗部分为累加式的典型形式，赋值号左右都出现的变量称为累加器，其中“i = i + 1”为特殊的累加式，每次累加的值为1，这样的累加器又称为计数器。

c语言折中查找法

c语言折中查找法

c语言折中查找法折中查找法（也称为二分查找法）是一种在有序数组中查找特定元素的搜索算法。

搜索过程从数组的中间元素开始，如果中间元素正好是目标值，则搜索过程结束；如果目标值大于或小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且同样从中间元素开始比较。

如果在某一步骤数组为空，则代表找不到。

这种搜索算法每一次比较都使搜索范围缩小一半。

以下是一个用C语言实现的折中查找法：c复制代码#include<stdio.h>int binarySearch(int arr[], int l, int r, int x){if (r >= l) {int mid = l + (r - l) / 2;if (arr[mid] == x)return mid;if (arr[mid] > x)return binarySearch(arr, l, mid - 1, x); return binarySearch(arr, mid + 1, r, x); }return-1;}int main(void){int arr[] = {2, 3, 4, 10, 40};int n = sizeof(arr) / sizeof(arr[0]);int x = 10;int result = binarySearch(arr, 0, n - 1, x);(result == -1) ? printf("Element is not present in array"): printf("Element is present at index %d", result);return0;}这个程序首先定义了一个数组arr[]，然后使用binarySearch()函数查找特定的元素x。

如果x在数组中，函数将返回其索引；否则，返回-1。

数据结构——查找,顺序查找,折半查找

实验五查找的应用一、实验目的：1、掌握各种查找方法及适用场合，并能在解决实际问题时灵活应用。

2、增强上机编程调试能力。

二、问题描述1.分别利用顺序查找和折半查找方法完成查找。

有序表（3,4,5,7,24,30,42,54,63,72,87,95）输入示例：请输入查找元素：52输出示例：顺序查找：第一次比较元素95第二次比较元素87 ……..查找成功，i=**/查找失败折半查找：第一次比较元素30第二次比较元素63 …..2.利用序列（12,7,17,11,16,2,13,9,21,4）建立二叉排序树，并完成指定元素的查询。

输入输出示例同题1的要求。

三、数据结构设计（选用的数据逻辑结构和存储结构实现形式说明）（1）逻辑结构设计顺序查找和折半查找采用线性表的结构，二叉排序树的查找则是建立一棵二叉树，采用的非线性逻辑结构。

（2）存储结构设计采用顺序存储的结构，开辟一块空间用于存放元素。

（3）存储结构形式说明分别建立查找关键字，顺序表数据和二叉树数据的结构体进行存储数据四、算法设计（1）算法列表（说明各个函数的名称，作用，完成什么操作）序号 名称 函数表示符 操作说明1 顺序查找 Search_Seq 在顺序表中顺序查找关键字的数据元素2 折半查找 Search_Bin 在顺序表中折半查找关键字的数据元素3 初始化 Init 对顺序表进行初始化，并输入元素4 树初始化 CreateBST 创建一棵二叉排序树5 插入 InsertBST 将输入元素插入到二叉排序树中6 查找 SearchBST在根指针所指二叉排序树中递归查找关键字数据元素 （2）各函数间调用关系（画出函数之间调用关系）typedef struct { ElemType *R; int length;}SSTable;typedef struct BSTNode{Elem data; //结点数据域 BSTNode *lchild,*rchild; //左右孩子指针}BSTNode,*BSTree; typedef struct Elem{ int key; }Elem;typedef struct {int key;//关键字域}ElemType;（3）算法描述int Search_Seq(SSTable ST, int key){//在顺序表ST中顺序查找其关键字等于key的数据元素。

《数据结构(C语言版 第2版)》(严蔚敏 著)第七章练习题答案

《数据结构（C语言版第2版）》（严蔚敏著）第七章练习题答案第7章查找1．选择题（1）对n个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为（）。

A．(n-1)/2B．n/2C．(n+1)/2D．n答案：C解释：总查找次数N=1+2+3+…+n=n(n+1)/2，则平均查找长度为N/n=(n+1)/2。

（2）适用于折半查找的表的存储方式及元素排列要求为（）。

A．链接方式存储，元素无序B．链接方式存储，元素有序C．顺序方式存储，元素无序D．顺序方式存储，元素有序答案：D解释：折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。

（3）如果要求一个线性表既能较快的查找，又能适应动态变化的要求，最好采用()查找法。

A．顺序查找B．折半查找C．分块查找D．哈希查找答案：C解释：分块查找的优点是：在表中插入和删除数据元素时，只要找到该元素对应的块，就可以在该块内进行插入和删除运算。

由于块内是无序的，故插入和删除比较容易，无需进行大量移动。

如果线性表既要快速查找又经常动态变化，则可采用分块查找。

（4）折半查找有序表（4，6，10，12，20，30，50，70，88，100）。

若查找表中元素58，则它将依次与表中（）比较大小，查找结果是失败。

A．20，70，30，50B．30，88，70，50C．20，50D．30，88，50答案：A解释：表中共10个元素，第一次取⎣(1+10)/2⎦=5，与第五个元素20比较，58大于20，再取⎣(6+10)/2⎦=8，与第八个元素70比较，依次类推再与30、50比较，最终查找失败。

（5）对22个记录的有序表作折半查找，当查找失败时，至少需要比较（）次关键字。

A．3B．4C．5D．6答案：B解释：22个记录的有序表，其折半查找的判定树深度为⎣log222⎦+1=5，且该判定树不是满二叉树，即查找失败时至多比较5次，至少比较4次。

（6）折半搜索与二叉排序树的时间性能（）。

C语言常用算法


} 插入法排序的要领就是每读入一个数立即插入到最终存放的数组中，每次插入都使得该数组有序。
例 2、任意读入 10 个整数，将其用插入法按降序排列后输出。
#define n 10
main()
{int a[n],i,j,k,x;
scanf("%d",&a[0]); /*读入第一个数，直接存到 a[0]中*/
if(b>c) { t=b; b=c; c=t; } printf("%d,%d,%d\n",a,b,c);}
2．累加
C 语言常用算法
累加算法的要领是形如“s=s+A”的累加式，此式必须出现在循环中才能被反复执行，从而
实现累加功能。“A”通常是有规律变化的表达式，s 在进入循环前必须获得合适的初值，通常为 0。
C 语言常用算法
②除第 1 个数以外，再从其余 n-1 个数中找出最小数（即 n 个数中的次小数）的下标，将此数 与第 2 个数交换位置；
③重复步骤①n-1 趟，即可完成所求。
例 1、任意读入 10 个整数，将其用选择法按升序排列后输出。
#define n 10
main()
{int a[n],i,j,k,t;
3．查找
（1）顺序查找（即线性查找） 顺序查找 的思路是：将待 查找的量与数组中 的每一个元素进 行比较，若有一个 元素与之相等
则找到；若没有一个元素与之相等则找不到。 例 1、任意读入 10 个数存放到数组 a 中，然后读入待查找数值，存放到 x 中，判断 a 中有无与 x 等值的数。 #define N 10 main() {int a[N],i,x; for(i=0;i<N;i++) scanf("%d",&a[i]); /*以下读入待查找数值*/

数据结构(C语言版)9-12章练习 答案 清华大学出版社

数据结构（C语言版）9-12章练习答案清华大学出版社9-12章数据结构作业答案第九章查找选择题1、对n个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为( A )A．（n+1）/2 B. n/2 C. n D. [（1+n）*n ]/2 2. 下面关于二分查找的叙述正确的是 ( D )A. 表必须有序，表可以顺序方式存储，也可以链表方式存储B. 表必须有序且表中数据必须是整型，实型或字符型 C. 表必须有序，而且只能从小到大排列 D. 表必须有序，且表只能以顺序方式存储3. 二叉查找树的查找效率与二叉树的( （1）C)有关, 在 (（2)C ）时其查找效率最低 (1): A. 高度 B. 结点的多少 C. 树型 D. 结点的位置(2): A. 结点太多 B. 完全二叉树 C. 呈单枝树 D. 结点太复杂。

4. 若采用链地址法构造散列表，散列函数为H（key）=key MOD 17，则需 (（1）A)个链表。

这些链的链首指针构成一个指针数组，数组的下标范围为 (（2）C) （1） A．17 B. 13 C. 16 D. 任意（2） A．0至17 B. 1至17 C. 0至16 D. 1至16判断题1．Hash表的平均查找长度与处理冲突的方法无关。

(错) 2. 若散列表的负载因子α<1，则可避免碰撞的产生。

（错）3. 就平均查找长度而言，分块查找最小，折半查找次之，顺序查找最大。

（错）填空题1. 在顺序表（8,11,15,19,25,26,30,33,42,48,50）中，用二分（折半）法查找关键码值20，需做的关键码比较次数为 4 .算法应用题1. 设有一组关键字{9,01,23,14,55,20,84,27}，采用哈希函数：H（key）=key mod7 ，表长为10，用开放地址法的二次探测再散列方法Hi=(H(key)+di) mod 10解决冲突。

要求：对该关键字序列构造哈希表，并计算查找成功的平均查找长度。

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
{
int len=len_LIST(LIST);
linkqueue *s;
s=LIST->next;
int a[100];
for(int i=0;i<len;i++)
{
a[i]=s->data;
s=s->next;
}
int k=0,l=0,h=len-1;int m;
while(l<=h)
{
k++;
p=LIST->next;
while(p!=NULL)
{
printf("%c ",p->data);
p=p->next;
}
printf("\n");
int len=len_LIST(LIST);
printf("长度为%d\n",len);
}
void creat_LIST(linkqueue *LIST)
print_LIST(LIST);
}
void shunxu(linkqueue *LIST)
{
int i=0,k=1;
printf("输入您要查找的元素:");
getchar();
temp=getchar();
linkqueue *p;
p=LIST->next;
for(;p!=NULL;p=p->next)
C语言顺序查找、折半查找
#include<stdio.h>
#include<malloc.h>
typedef struct dui{
char data;
struct dui *next;
}linkqueue;
char temp;
void init_LIST(linkqueue *LIST)
{
LIST->next=NULL;
{
char x;
linkqueue *p,*s;
s=LIST;
while((x=getchar())!='#')
{
p=(linkqueue *)malloc(sizeof(linkqueue));
p->data=x;
p->next=NULL;
s->next=p;
s=p;
}
printf("您创建的列表是：");
{
i++;
if(p->data==temp) {printf("####顺序查找####\n您要查找的元素在第%d位,比较了%d次\n",i,i); k=0;break;}
}
if(k) printf("####顺序查找####\n您要查找的元素不存在。\n");
}
void zheban(linkqueue *LIST)
m=(l+h)/2;
if(a[m]==temp) {printf("####折半查找####\n位置：%d,查找次数：%d\n",m+1,k);break;} //位置m+1
if(a[m]>temp) h=m-1;
else l=m+1;
}
if(!(l<=h)) printf("####折半查找####\n查无此数");
}
void main()
{
linkqueue *LIST;
LIST=(linkqueue *)malloc(sizeof(linkqueue));
init_LIST(LIST);
crБайду номын сангаасat_LIST(LIST);
shunxu(LIST);
zheban(LIST);
}
}
int len_LIST(linkqueue *LIST)
{
int i=0;
linkqueue *p;
p=LIST->next;
while(p!=NULL)
{
p=p->next;
i++;
}
return i;
}
void print_LIST(linkqueue *LIST)
{
linkqueue *p;