顺序查找算法和折半查找算法代码

⑴ 编程实现顺序查找("哨兵"的使用)与折半查找(有序表)算法.

顺序查找
#include
<stdio.h>
#include
<stdlib.h>
#define
MAX_LENGTH
100typedef
int
KeyType;
typedef
struct
{
KeyType
*elem;
int
length;
}SSTable;
//顺序表的存储结构
int
Search_Seq(SSTable
ST,
KeyType
key){
int
i;
ST.elem[0]
=
key;
//“哨兵”，如果顺序表中不存在要查找的数据的话，则查找指针必定指向该哨兵
for(i
=
ST.length;
ST.elem[i]
!=
key;
i--)
;
return
i;
//找到的话，则i
!=
0,否则i
=
0
}
void
main()
{
int
i,
key;
SSTable
T;
T.elem
=
(KeyType
*)malloc(sizeof(KeyType));
printf("How
Many
Entries
Do
You
Want
input\n");
scanf("%d",
&T.length);
for(i=1;
i<=T.length;
i++){
printf("Please
input
the
%dth
entries
\n",
i);
scanf("%d",
&T.elem[i]);
}
for
(i=1;
i<=T.length;
i++)
printf("%5d",T.elem[i]);
//显示已经输入的所有数据
printf("\nPlease
input
the
data
you
want
to
search\n");
scanf("%d",
&key);
i
=
Search_Seq(T,key);
printf("the
search
data
is
locate
the
%dth(0
indicate
can
not
find)\n",i);
}
折半查找
#include
<stdio.h>
#include
<stdlib.h>
int
binSearch(const
int
*Array,int
start,int
end,int
key)
{
int
left,right;
int
mid;
left=start;
right=end;
while
(left<=right)
{
mid=(left+right)/2;
if
(key<Array[mid])
{
right=mid-1;
}
else
if(key>Array[mid])
{
left=mid+1;
}
else
return
mid;
}
return
-1;
}
void
main()
{
int
A[]={10,20,30,40,50,60,70,80};
int
n;
printf("Please
search
num:");
scanf("%d",&n);
int
index=binSearch(A,0,8,n);
if(index==-1)
{
printf("no
num");
}
else
{
printf("index=%d",index+1);
}
}

⑵ C语言折半查找法详细代码（假如有10个已排好序的数）

折半查找即二分查找，思想是：在一组有序的数据中查找一个数据，首先将要查找的数据与这组数中间的值比较，如果要查找的数据比它小，则在左半部分中继续查找；若比中间值大，则在右半部分中继续查找，相等的话就表示已找到，直接返回。

这样，每次查找都可以将查找范围缩小一半，以此达到O(log N)的时间复杂度。

折半查找代码如下：

intbsearchWithoutRecursion(intarray[],intlow,inthigh,inttarget)
{
while(low<=high)
{
intmid=(low+high)/2;

if(array[mid]>target)
high=mid-1;
elseif(array[mid]<target)
low=mid+1;
else
returnmid;
}
return-1;
}

⑶ 求查找算法（折半查找法，顺序查找法，分别在一个程序里）“动画演示”程序源代码，一共两个源代码

折半搜索（英语：half-interval search），也称二分搜索（英语：binary search）、对数搜索（英语：logarithmic search），是一种在有序数组中查找某一特定元素的搜索算法。

搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。

折半查找法是效率较高的一种查找方法。假设有已经按照从小到大的顺序排列好的五个整数a0~a4，要查找的数是X，其基本思想是： 设查找数据的范围下限为l=0，上限为h=4，求中点m=（l+h）/2，用X与中点元素am比较，若X等于am，即找到，停止查找；否则，若X大于am，替换下限l=m+1，到下半段继续查找；若X小于am，换上限h=m-1，到上半段继续查找；如此重复前面的过程直到找到或者l>h为止。如果l>h，说明没有此数，打印找不到信息，程序结束。

函数实现如下：

bin_search(intA[],intn,intkey){
intlow,high,mid;
low=0;
high=n-1;
while(low<=high)
{
mid=(low+high)/2;
if(A[mid]==key)returnmid;
if(A[mid]<key){
low=mid+1;
}
if(A[mid]>key){
high=mid-1;
}
}
return-1;
}
C语言实现代码
#include<stdio.h>intmain()
{
inta[11]={0,1,2,3,4,5,6,7,8,9,10},min=0,max=10,mid,n;//max为数列长度，a[0]作为第一个数组元素
printf("请输入您要查找的数:
");
scanf("%d",&n);
while(min+1!=max)
{
mid=(min+max)/2;
if(n>a[mid])min=mid;
elseif(n<a[mid])max=mid;
else
{
printf("输入的数在数列的第%d位
",mid);
exit(0);
}
}
if(n==a[max])
{
max+=1;
printf("
输入的数在数列的第%d位
",max);
}
elseif(n==a[min])
{
min+=1;
printf("
输入的数在数列的第%d位
",min);
}
elseif(n!=a[mid])
printf("
输入的数不在数列中");
}
Dev-c++实现
#include<stdio.h>
#include<stdlib.h>
voidmain()
{
inta[15]={1,2,3,4,5,6,7,8,9,10,11,12,13,15};
intn,m,top,bot,mid;
top=m=1;//此处修改top=0;m=1;
bot=14;
printf("pleaseinputanumber:");
scanf("%d",&n);
while(top<=bot)
{
mid=(top+bot)/2;
if(n==a[mid])
{
printf("这是第%d个元素的值。
",mid+1);
m=0;
break;
}
elseif(n>a[mid])
top=mid+1;
elseif(n<a[mid])
bot=mid-1;
}
if(m)
printf("无此数。
");
system("PAUSE");
return0;
}

顺序查找是按照序列原有顺序对数组进行遍历比较查询的基本查找算法。

对于任意一个序列以及一个给定的元素，将给定元素与序列中元素依次比较，直到找出与给定关键字相同的元素，或者将序列中的元素与其都比较完为止。

函数实现如下：

intsq_search(keytypekeyp[],intn,keytypekey)
{
inti;
for(i=0;i<n;i++)
if(key[i]==key)
returni;//查找成功
return-1;//查找失败
}

上面只是算法实现函数，对于动画部分，自己用moveto，lineto描点划线的方式实现吧。

⑷ 用C语言编写顺序查找和二分查找（折半查找）

顺序查找：在一个已知无序队列中找出与给定关键字相同的数的具体位置。原理是让关键字与队列中的数从第一个开始逐个比较，直到找出与给定关键字相同的数为止。复杂度为o(n).

二分查找又称折半查找，它是一种效率较高的查找方法。
【二分查找要求】：1.必须采用顺序存储结构 2.必须按关键字大小有序排列。
【优缺点】折半查找法的优点是比较次数少，查找速度快，平均性能好;其缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。
【算法思想】首先，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。
重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。
【算法复杂度】假设其数组长度为n，其算法复杂度为o（log（n））

#include <stdio.h>

//二分查找：
int search(int a[],int x,int n) //x为要查找的元素，n为数组长度
{
int mid=0;
int low=0;
int high=n;
while(low<=high)
{
mid=(low+high)/2;
if(a[mid]==x)
{ return mid; }
else if(x<a[mid])
{ high=mid-1; }
else
{ low=high+1; }
}
return -1;
}
//顺序查找：
int search1(int a[],int x,int n) //x为要查找的元素，n为数组长度
{
int i;
for(i=0;i<n;i++)
{
if(a[i]==x)
return i;
}
return -1;
}

int main()
{
int i,a[10],x;
for(i=0;i<10;i++)
scanf("%d",&a[i]);
printf("请输入要查找的元素");
scanf("%d",&x);
if(search(a,x,10)!=-1)printf("查找的元素在数组中的位置为%d.\n",search(a,x,10));
else printf("该元素不在数组中\n");
if(search1(a,x,10)!=-1)printf("查找的元素在数组中的位置为%d.\n",search1(a,x,10));
else printf("该元素不在数组中\n");
return 0;
}

⑸ 数据结构与算法顺序查找和折半查找

1.顺序查找
又称线性查找，主要用于在线性表中进行查找。

一般线性表的顺序查找：
从线性表的一端开始，逐个检查关键字满足给定条件。若查找到某个元素的关键字满足给定条件则查找成功，返回该元素在线性表中的位置。若已经查找到表的另一端，但还没有查找到符合给定条件的元素，则返回查找失败的信息。

有序表的顺序查找：
假设表L是按关键字从小到大排列的，查找的顺序是从前往后，待查找元素的关键字为key。当查找到第i个元素时，发现第i个元素对应的关键字小于key，但第i+1个元素对应的关键字大于key，这时就可以返回查找失败的信息。

2.折半查找
又称二分查找，它仅适用于有序的顺序表

首先将给定值key与表中间位置的元素比较，若相等，则查找成功，返回该元素的存储位置。若不等，则所需查找的元素只能在中间元素以外的前半部分或后半部分。然后在缩小的范围内继续进行同样的查找，如此重复，直到找到为止。或确定表中没有所需要查找的元素，则查找不成功，返回查找失败的信息。

3.分块查找
又称按索引顺序查找，它吸取了顺序查找和折半查找各自的优点，既有动态结构，又适于快速查找

将查找表分为若干子块。块内的元素可以无序，但块之间是有序的，第一个块中的最大关键字小于第二个块中的所有记录的关键字，以此类推。再建立一个索引表，索引表中的每个元素含有各块的最大关键字和各块中的第一个元素的地址，索引表按关键字有序排列

⑹ C++折半查找 求源代码

#include<stdio.h>

intsearch(intlow,inthigh,intn,intnum[]);//函数声明

voidmain()
{
inti,n,num[20];
for(i=0;i<=19;i++)
{
num[i]=i+10;
printf("%d",num[i]);
}
printf("输入要查找的数：");
scanf("%d",&n);
printf("%d
",search(0,19,n,num));
}
intsearch(intlow,inthigh,intn,intnum[])//折半查找的函数

{
intmid;
mid=(low+high)/2;
if(n==num[mid])
returnmid;
elseif(n>num[mid])
search(mid+1,high,n,num);
else
search(low,mid-1,n,num);
}

⑺ VB 编程中的顺序查找和折半查找怎么编的

1.顺序查找没什么说的，就是
for(int
i=0;i<len;i++)
if(arr[i]==data)
return
i;
return
-1;
2.折半就是设计low,high
int
low=0;
int
high=len-1;
int
mid;
while(low<=high)
{
mid=(low+high)/2;
if(data>arr[mid])
low=mid+1;
else
if(data<arr[mid])
high=mid-1;
else
return
mid;
}
缉弧光旧叱搅癸些含氓return
-1;

⑻ C语言编写数据结构查找算法

实验五 查找的实现
一、 实验目的
1．通过实验掌握查找的基本概念；
2．掌握顺序查找算法与实现；
3．掌握折半查找算法与实现。
二、 实验要求
1． 认真阅读和掌握本实验的参考程序。
2． 保存程序的运行结果，并结合程序进行分析。
三、 实验内容
1、建立一个线性表，对表中数据元素存放的先后次序没有任何要求。输入待查数据元素的关键字进行查找。为了简化算法，数据元素只含一个整型关键字字段，数据元素的其余数据部分忽略不考虑。建议采用前哨的作用，以提高查找效率。
2、查找表的存储结构为有序表，输入待查数据元素的关键字利用折半查找方法进行查找。此程序中要求对整型量关键字数据的输入按从小到大排序输入。
一、顺序查找
顺序查找代码：
#include"stdio.h"
#include"stdlib.h"
typedef struct node{
intkey;
}keynode;
typedef struct Node{
keynoder[50];
intlength;
}list,*sqlist;
int Createsqlist(sqlist s)
{
inti;
printf("请输入您要输入的数据的个数:\n");
scanf("%d",&(s->length));
printf("请输入您想输入的%d个数据;\n\n",s->length);
for(i=0;i<s->length;i++)
scanf("%d",&(s->r[i].key));
printf("\n");
printf("您所输入的数据为:\n\n");
for(i=0;i<s->length;i++)
printf("%-5d",s->r[i].key);
printf("\n\n");
return1;
}
int searchsqlist(sqlist s,int k)
{
inti=0;
s->r[s->length].key=k;
while(s->r[i].key!=k)
{

i++;
}
if(i==s->length)
{
printf("该表中没有您要查找的数据！\n");
return-1;
}
else
returni+1;
}
sqlist Initlist(void)
{
sqlistp;
p=(sqlist)malloc(sizeof(list));
if(p)
returnp;
else
returnNULL;
}
main()
{
intkeyplace,keynum;//
sqlistT;//
T=Initlist();
Createsqlist(T);
printf("请输入您想要查找的数据的关键字:\n\n");
scanf("%d",&keynum);
printf("\n");
keyplace=searchsqlist(T,keynum);
printf("您要查找的数据的位置为:\n\n%d\n\n",keyplace);
return2;
}
顺序查找的运行结果：
二、折半查找
折半查找代码：
#include"stdio.h"
#include"stdlib.h"
typedef struct node{
intkey;
}keynode;
typedef struct Node{
keynoder[50];
intlength;
}list,*sqlist;
int Createsqlist(sqlist s)
{
inti;
printf("请输入您要输入的数据的个数:\n");
scanf("%d",&(s->length));
printf("请由大到小输入%d个您想输入的个数据;\n\n",s->length);
for(i=0;i<s->length;i++)
scanf("%d",&(s->r[i].key));
printf("\n");
printf("您所输入的数据为:\n\n");
for(i=0;i<s->length;i++)
printf("%-5d",s->r[i].key);
printf("\n\n");
return1;
}
int searchsqlist(sqlist s,int k)
{
intlow,mid,high;
low=0;
high=s->length-1;
while(low<=high)
{
mid=(low+high)/2;
if(s->r[mid].key==k)
returnmid+1;
elseif(s->r[mid].key>k)
high=mid-1;
else
low=mid+1;
}
printf("该表中没有您要查找的数据!\n");
return-1;
}
sqlist Initlist(void)
{
sqlistp;
p=(sqlist)malloc(sizeof(list));
if(p)
returnp;
else
returnNULL;
}
main()
{
intkeyplace,keynum;//
sqlistT;//
T=Initlist();
Createsqlist(T);
printf("请输入您想要查找的数据的关键字:\n\n");
scanf("%d",&keynum);
printf("\n");
keyplace=searchsqlist(T,keynum);
printf("您要查找的数据的位置为:\n\n%d\n\n",keyplace);
return2;
}
折半查找运行结果：
三、实验总结：
该实验使用了两种查找数据的方法（顺序查找和折半查找），这两种方法的不同之处在于查找方式和过程不同，线性表的创建完全相同，程序较短，结果也一目了然。

⑼ 用C语言编写顺序查找和二分查找（折半查找）

#include<stdio.h>
#defineLENGTH20

voidSequenceSearch(int*fp,intLength);
voidSearch(int*fp,intlength);
voidSort(int*fp,intlength);

voidmain()
{
intcount;
intarr[LENGTH];

printf("请输入你的数据的个数:
");
scanf("%d",&count);
printf("请输入%d个数据
",count);
for(inti=0;i<count;i++)
{
scanf("%d",&arr[i]);
}

intchoise=0;
do
{
printf("1.使用顺序查询.
2.使用二分查找法查找.
3.退出
");
scanf("%d",&choise);

if(choise==1)
SequenceSearch(arr,count);
elseif(choise==2)
Search(arr,count);
elseif(choise==3)
break;
}while(choise==1||choise==2||choise==3);
}

voidSequenceSearch(int*fp,intLength)
{
intdata;
printf("开始使用顺序查询.
请输入你想要查找的数据.
");
scanf("%d",&data);

for(inti=0;i<Length;i++)
if(fp[i]==data)
{
printf("经过%d次查找，查找到数据%d.
",i+1,data);
return;
}

printf("经过%d次查找，未能查找到数据%d.
",i,data);
}

voidSearch(int*fp,intlength)
{
intdata;
printf("开始使用顺序查询.
请输入你想要查找的数据.
");
scanf("%d",&data);
printf("由于二分查找法要求数据是有序的，现在开始为数组排序.
");
Sort(fp,length);
printf("数组现在已经是从小到大排列,下面将开始查找.
");

intbottom,top,middle;

bottom=0;
top=length;

inti=0;
while(bottom<=top)
{
middle=(bottom+top)/2;
i++;
if(fp[middle]<data)
{
bottom=middle+1;
}
elseif(fp[middle]>data)
{
top=middle-1;
}
else
{
printf("经过%d次查找，查找到数据%d.
",i,data);
return;
}
}
printf("经过%d次查找，未能查找到数据%d.
",i,data);
}

voidSort(int*fp,intlength)
{
printf("现在开始为数组排序，排列结果将是从小到大.
");

inttemp;
for(inti=0;i<length;i++)
for(intj=0;j<length-i-1;j++)
if(fp[j]>fp[j+1])
{
temp=fp[j];
fp[j]=fp[j+1];
fp[j+1]=temp;
}

printf("排序完成!
下面输出排序后的数组:
");
for(intk=0;k<length;k++)
{
printf("%5d",fp[k]);
}
printf("
");

}

⑽ 怎样用C语言实现带监视哨的简单顺序查找算法和折半查找算法并计算其比较次数

哎，我就辛苦辛苦了啦。

以下是可以编译运行的代码，在VC6.0下通过。

#include <stdio.h>
#define LENGTH 20

void SequenceSearch(int *fp,int Length);
void Search(int *fp,int length);
void Sort(int *fp,int length);

void main()
{
int count;
int arr[LENGTH];

printf("请输入你的数据的个数:\n");
scanf("%d",&count);
printf("请输入%d个数据\n",count);
for(int i=0;i<count;i++)
{
scanf("%d",&arr[i]);
}

int choise=0;
do
{
printf("1.使用顺序查询.\n2.使用二分查找法查找.\n3.退出\n");
scanf("%d",&choise);

if(choise==1)
SequenceSearch(arr,count);
else if(choise==2)
Search(arr,count);
else if(choise==3)
break;
} while (choise==1||choise==2||choise==3);
}

void SequenceSearch(int *fp,int Length)
{
int data;
printf("开始使用顺序查询.\n请输入你想要查找的数据.\n");
scanf("%d",&data);

for(int i=0;i<Length;i++)
if(fp[i]==data)
{
printf("经过%d次查找，查找到数据%d.\n",i+1,data);
return ;
}

printf("经过%d次查找，未能查找到数据%d.\n",i,data);
}

void Search(int *fp,int length)
{
int data;
printf("开始使用顺序查询.\n请输入你想要查找的数据.\n");
scanf("%d",&data);
printf("由于二分查找法要求数据是有序的，现在开始为数组排序.\n");
Sort(fp,length);
printf("数组现在已经是从小到大排列,下面将开始查找.\n");

int bottom,top,middle;

bottom=0;
top=length;

int i=0;
while (bottom<=top)
{
middle=(bottom+top)/2;
i++;
if(fp[middle]<data)
{
bottom=middle+1;
}
else if(fp[middle]>data)
{
top=middle-1;
}
else
{
printf("经过%d次查找，查找到数据%d.\n",i,data);
return;
}
}
printf("经过%d次查找，未能查找到数据%d.\n",i,data);
}

void Sort(int *fp,int length)
{
printf("现在开始为数组排序，排列结果将是从小到大.\n");

int temp;
for(int i=0;i<length;i++)
for(int j=0;j<length-i-1;j++)
if(fp[j]>fp[j+1])
{
temp=fp[j];
fp[j]=fp[j+1];
fp[j+1]=temp;
}

printf("排序完成!\n下面输出排序后的数组:\n");
for(int k=0;k<length;k++)
{
printf("%5d",fp[k]);
}
printf("\n");

}

我粗略的测试了下，没有什么问题，有问题的话可以网络给我留言，当然，程序很容易，你可以自己修改。