實現順序查找演算法
A. 哈希查找演算法程序
查找演算法
基本要求：
（1）設計一個菜單將實現的查找演算法的名字顯示出來，並提示用戶對查找演算法進行選擇；
（2）分別實現順序查找、二分查找（折半查找）、二叉排序樹、哈希查找；
（3）哈希函數採用除留余數發，解決沖突的方法大家任選擇一種；
（4）二叉排序樹必須實現構建、查找、插入、刪除四個基本操作；
（5）輸出各種排序的結果並進行比較。*/
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#define MAX 20
typedef struct /*順序結構數據類型*/
h.length++;
h.r[ }
else
if(k<l.r[mid].key) high=mid-1;
else low=mid +1;
}
if(i!=0)
{
printf("l.r[%d].key=%d\n",i,k);
printf("查找成功\n");
}
return ht;
}
void HashSearch(RecordHash ht) /*哈希查找*/
{
int k,i;
page_title("哈希查找");
printf("請輸入要查找的關鍵字:");
scanf("%d",&k);
i=k%13;
if(ht.HashTable[i].key==k)
{
printf("ht.HashTable[%d].key=%d\n",i,k);
printf("查找成功\n");
}
else
{
i=i+1;
for(;i<MAX;i++)
if(ht.HashTable[i].key==k)
{
printf("ht.HashTable[%d].key=%d\n",i,k);
printf("查找成功\n");
break;
}
if(i==MAX) printf("查找失敗\n");
}
return_confirm();
}
void main()
{
RecordList L1,L2;
BSTNode *pt;
RecordHash ht;
int k,i;
printf("\n創建順序查找線性表,輸入0則結束輸入(可不按順序輸入)\n");
L1=creat1();
printf("\n創建二分查找線性表，輸入0則結束輸入(按遞增順序輸入)\n");
L2=creat1();
printf("\n創建二叉排序樹，輸入0則結束輸入\n");
pt=creat2();
printf("\n創建哈希表\n");
ht=creat3();
menu:page_title("請選擇查找方式，輸入0則結束輸入");
printf("順序查找請按1\n二分查找請按2\n二叉排序樹查找請按3\n哈希查找請按4\n推出請按0\n");
switch(getch())
{
case '1':
SeqSearch(L1);
break;
case '2':
Binsrch(L2);
break;
case '3':
page_title("二叉排序樹查找");
printf("請輸入要查找的關鍵字:");
scanf("%d",&k);
SearchBST(pt,k);
break;
case '4':
HashSearch(ht);
break;
case '0':
exit(0);
default :
printf("輸入錯誤，按任意鍵返回");
getch();
}
goto menu;
B. 求查找演算法（折半查找法，順序查找法，分別在一個程序里）「動畫演示」程序源代碼，一共兩個源代碼
折半搜索（英語：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描點劃線的方式實現吧。