順序查找演算法和折半查找演算法代碼

⑴ 編程實現順序查找("哨兵"的使用)與折半查找(有序表)演算法.

順序查找
#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");

}

我粗略的測試了下，沒有什麼問題，有問題的話可以網路給我留言，當然，程序很容易，你可以自己修改。