① 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;
}
折半查找運行結果：
三、實驗總結：
該實驗使用了兩種查找數據的方法（順序查找和折半查找），這兩種方法的不同之處在於查找方式和過程不同，線性表的創建完全相同，程序較短，結果也一目瞭然。
② 分塊查找演算法中如何對數據分塊
可以實現確定待查找數據的上限和下限，
然後對該區間等分N塊，
那麼這N塊就可以作為分塊查找的塊，
然後將原數組中的元素按區間插入進去，
當然，這樣劃分不能保證每個塊中的元素個數相等，
但是，分塊查找演算法並不嚴格要求每塊中的元素的個數相等。
③ 什麼是查找法
演算法思想：
將數列按有序化(遞增或遞減)排列，查找過程中採用跳躍式方式查找，即先以有序數列的中點位置為比較對象，如果要找的元素值小於該中點元素，則將待查序列縮小為左半部分，否則為右半部分。通過一次比較，將查找區間縮小一半。
折半查找是一種高效的查找方法。它可以明顯減少比較次數，提高查找效率。但是，折半查找的先決條件是查找表中的數據元素必須有序。
演算法步驟描述：
step1 首先確定整個查找區間的中間位置
mid = （ left + right ）/ 2
step2 用待查關鍵字值與中間位置的關鍵字值進行比較；
若相等，則查找成功
若大於，則在後（右）半個區域繼續進行折半查找
若小於，則在前（左）半個區域繼續進行折半查找
Step3 對確定的縮小區域再按折半公式，重復上述步驟。最後，得到結果：要麼查找成功， 要麼查找失敗。
折半查找的存儲結構採用一維數組存放。
折半查找演算法舉例
對給定數列（有序）{ 3，5，11，17，21，23，28，30，32，50}，按折半查找演算法，查找關鍵字值為30的數據元素。
折半查找的演算法討論：
優點: ASL≤log2n，即每經過一次比較,查找范圍就縮小一半。經log2n 次計較就可以完成查找過程。
缺點：因要求有序，所以要求查找數列必須有序，而對所有數據元素按大小排序是非常費時的操作。另外，順序存儲結構的插入、刪除操作不便利。
考慮：能否通過一次比較拋棄更多的部分（即經過一次比較，使查找范圍縮得更小），以達到提高效率的目的。……？
可以考慮把兩種方法（順序查找和折半查找）結合起來，即取順序查找簡單和折半查找高效之所長，來達到提高效率的目的？實際上這就是分塊查找的演算法思想。
例如：[問題分析] 由於數據按升序排列,故用折半查找最快捷.
program binsearch;
const max=10;
var num:array[1..max] of integer;
i,n:integer;
procere search(x,a,b:integer);
var mid:integer;
begin
if a=b then
if x=num[a] then writeln('Found:',a) else writeln('Number not found')
else begin
mid:=(a+b) div 2;
if x>num[mid] then search(x,mid,b);
if x<num[mid] then search(x,a,mid);
if x=num[mid] then writeln('Found:',mid);
end;
end;
begin
write('Please input 10 numbers in order:');
for i:=1 to max do read(num);
write('Please input the number to search:');
readln(n);
search(n,1,max);
end.
Java風格的代碼舉例：
//使用折半法進行查找
int getIndex(int[] nList, int nCount, int nCode) {
int nIndex = -1;
int jMin = 0;
int jMax = nCount - 1;
int jCur = (jMin+jMax)/2;
do
{
if(nList[jCur] > nCode) {
jMax--;
} else if(nList[jCur] < nCode) {
jMin++;
} else if(nList[jCur] == nCode) {
nIndex = jCur;
break;
}
jCur = (jMin + jMax)/2;
} while(jMin < jMax);
return nIndex;
}
二分查找的性能說明
雖然二分查找的效率高，但是要將表按關鍵字排序。而排序本身是一種很費時的運算。既使採用高效率的排序方法也要花費 O(n lg n) 的時間。
二分查找只適用順序存儲結構。為保持表的有序性，在順序結構里插入和刪除都必須移動大量的結點。因此，二分查找特別適用於那種一經建立就很少改動、而又經常需要查找的線性表。
對那些查找少而又經常需要改動的線性表，可採用鏈表作存儲結構，進行順序查找。鏈表上無法實現二分查找
二分查找的C#實現代碼：
using System;
using System.Collections.Generic;
using System.Text;
namespace BinschDemo
{
public class BinschDemo
{
public static int Binsch(int[] a, int key)
{
int low = 1;
int high = a.Length;
while (low <= high)
{
int mid = (low + high) / 2;
if (key == a[mid])
{
return mid; //返回找到的索引值
}
else
{
if (key < a[mid])
high = mid - 1;
else
low = mid + 1;
}
}
return -1; //查找失敗
}
static void Main(string[] args)
{
Console.WriteLine("請輸入10個遞增數字: ");
int[] list = new int[10];
for (int i = 0; i < 10; i++)
{
Console.Write("數字 : ", i);
list = Convert.ToInt32(Console.ReadLine());
}
Console.Write("請輸入一個你要查找的數字:");
int find = Convert.ToInt32(Console.ReadLine());
int result = Binsch(list, find);
Console.WriteLine(result);
}
}
}
分塊查找又索引查找，它主要用於「分塊有序」表的查找。所謂「分塊有序」是指將線性表L（一維數組）分成m個子表（要求每個子表的長度相等），且第i+1個子表中的每一個項目均大於第i個子表中的所有項目。「分塊有序」表應該包括線性表L本身和分塊的索引表A。因此，分塊查找的關鍵在於建立索引表A。
（1）建立索引表A（二維數組）
索引表包括兩部分：關鍵字項（子表中的最大值）和指針項（子表的第一項在線性表L中位置）
索引表按關鍵字有序的。
例如：線性表L（有序）為：1 2 3 4 5 6 7 8 9 10 11 12
分成m=3個子表：{1 2 3 4} {5 6 7 8} {9 10 11 12}
索引表A：二維數組：第一列為每個子表的最大值 ，第二列為每個子表的起始地址
即： 4 0
8 4
12 8
（2）利用索引表A，確定待查項X所在的子表（塊）。
（3）在所確定的子表中可以用「折半查找」法搜索待查項X；若找到則輸出X；否則輸出未找到信息。
④ 索引順序表的查找：編寫利用折半查找確定記錄所在塊的分塊查找演算法，並討論在塊中進行順序查找時使用「監
#include <iostream>
using namespace std;
int s,d,ss,dd;//聲明一些全局變數，方便函數與主函數之間的變數調用。
template <class T>
int BinSearch(T A[],int low,int high,T key)//遞歸實現折半查找
{
int mid;// 初始化中間值的位置
T midvalue;// 初始化中間值
if (low>high)
{
s=A[high];
d=A[low];
ss=high;
dd=low;
return -1;}// 如果low的值大於high的值，輸出-1，並且將此時的low與high的值存儲。
else
{
mid=(low+high)/2;// 中間位置為低位與高位和的一半取整。
midvalue=A[mid];
if (midvalue==key)
return mid;
else if (midvalue < key) //如果關鍵字的值大於中間值
return BinSearch(A,mid+1,high,key);// 遞歸調用函數，搜索下半部分
else
return BinSearch(A,low,mid-1,key);// 否則遞歸調用哦個函數，搜索上半部分
}
}
template <class T>
int shuxuSearch(T A[],int high,T key)// 順序查找
{
int i=0; A[high]=key;// 初始化i，使 A的最高位為key值
while(A[i]!=key)
i++;
return i;// 如果A中有key值，則在i不到n+1時就會輸出，否則，返回high值，說明搜索失敗。
}
int main()
{
int i,key,pos,length,fen,k,j,a,kuai,e;// 定義一些變數
a=0;
k=0;
cout<<"請輸入關鍵字的個數"<<endl;
cin>>length;
int A[length-1]; // 根據輸入關鍵字的個數初始化一個數組進行存儲
cout<<"請輸入要分塊的個數"<<endl;
cin>>fen;
int B[fen-1];
int M[fen-1];
for(i=0;i<fen;i++)
{M[i]=0;}// 初始化兩個數組，一個用來存儲每一塊元素的大小，另一個用來存儲每一塊的中元素的最大值
cout<<"請輸入每個分塊關鍵字的個數"<<endl;
for(i=0;i<fen;i++)
{cin>>B[i];}//使數組B中表示每塊中關鍵字的個數
cout<<"請輸入關鍵字"<<endl;
for(i=0;i<length;i++)
{cin>>A[i];}//輸入所有的關鍵字，存在數組A中
int row,col;
row=fen;
col=length;
int **p2 ;
p2 = new int*[row] ;//聲明一個二維數組
for( i = 0 ; i < row ; i ++ )
p2[i] = new int[col] ;
for( i = 0 ; i < row ; i ++ )
{for( j = 0 ; j < B[i] ; j ++ )
{p2[i][j]=A[k];
k=k+1;}
}//將所有關鍵字，按塊的不同存入二維數組中
cout<<"分塊情況為"<<endl;
for( i = 0 ; i < row ; i ++ )
{
for( j = 0 ;j <B[i] ; j ++ )
{cout<<p2[i][j]<<' ' ;
if(p2[i][j]>=M[i])
M[i]=p2[i][j];
}
cout<<endl;
}//輸出二維數組，檢驗分塊是否為預期
cout<<"每個塊最大元素為"<<endl;
for(i=0;i<fen;i++)
{cout<<M[i]<<endl;}//將每一組的最大元素存入數組M中
cout<<endl<<"請輸入要查找的元素";
cin>>key;//將要查找的關鍵字賦值給key
pos=BinSearch(M,0,length-1,key);//調用折半查找函數，查找關鍵字處於哪個塊中
cout<<"該元素所處的塊是"<<endl;
if (pos!=-1)
{kuai=pos;
cout<<kuai<<endl;
}
else
{kuai=dd;
cout<<kuai<<endl;}//將關鍵字所在的塊輸出。
int *S;
S = new int[kuai] ;
for(i=0;i<B[kuai];i++)
{S[i]=p2[kuai][i];
}//初始化一個一維數組，將 關鍵字所在快的元素重新定義為一個數組S
pos=shuxuSearch(S,B[kuai],key);//在S中順序查找關鍵字
int q=0;
for(i=0;i<kuai;i++)
{q=q+B[i];}
if (pos!=B[kuai])
cout<<"該元素的位置為"<<pos+q<<endl;//如果關鍵字存在，輸出其位置
else
cout<<"不存在該元素"<<endl;//若不存在，輸出"不存在該元素"
cout<<"還要繼續查找嗎？是的話，輸入1，不是的話輸入0"<<endl;
cin>>e; //引入判斷條件，以便多次查找
while ((e!=1)&&(e!=0))
{cout<<"輸入不合法,請重新輸入e"<<endl;
cin>>e;}//保證輸入合法
while (e==1)
{
cout<<endl<<"請輸入要查找的元素";
cin>>key;
pos=BinSearch(M,0,length-1,key);
cout<<"該元素所處的塊是"<<endl;
if (pos!=-1)
{kuai=pos;
cout<<kuai<<endl;
}
else
{kuai=dd;
cout<<kuai<<endl;}
for(i=0;i<B[kuai];i++)
{S[i]=p2[kuai][i];}
pos=shuxuSearch(S,B[kuai],key);
int q=0;
for(i=0;i<kuai;i++)
{q=q+B[i];}
if (pos!=B[kuai])
cout<<"該元素的位置為"<<pos+q<<endl;
else
cout<<"不存在該元素"<<endl;
cout<<"還要繼續查找嗎？是的話，輸入1，不是的話輸入0"<<endl;
cin>>e; //與上面程序一致，通過循環條件保證可以多次進行查找
}
system("pause");
return 0;
}
⑤ http://www.baidu .com/
們我現在有一個C++作業題不會做，特向你們求助，懇請你們能給我些幫助！！！下面是問題的題目及要求，謝謝你的幫助！
一、題目：用分塊查找方法解決在資料庫中查找與關鍵字相同記錄的問題
1． 基本要求：
（1）要求用C++模塊化設計的思想來完成程序的設計；
（2）要求各個功能分別使用函數來完成，主函數和各個函數分別存放在不同的.cpp文件中，要求使用頭文件；
（3）程序調試通過後，完成程序文檔的處理，加必要的注釋。
三、設計方法和基本原理
1． 問題描述：
在一組無序數列中查找某個數據，找到則輸出該數據，否則輸出未找到信息。
2． 問題的解決方案：
根據問題的描述，可以按照要求的功能採用結構化的設計思想。
（1） 數列的賦值要求編寫獨立函數實現；
（2） 將無序數列排序為有序數列可以用「拉鋸法」排序法也可以用其他方法實現，並編寫獨立函數；
（3） 分塊查找的演算法用獨立函數實現
四、主要技術問題的描述
根據三的分析，主要問題在於：
1、排序演算法的實現（不限方法）
2、分塊查找方法的實現
分塊查找又索引查找，它主要用於「分塊有序」表的查找。所謂「分塊有序」是指將線性表L（一維數組）分成m個子表（要求每個子表的長度相等），且第i+1個子表中的每一個項目均大於第i個子表中的所有項目。「分塊有序」表應該包括線性表L本身和分塊的索引表A。因此，分塊查找的關鍵在於建立索引表A。
（1）建立索引表A（二維數組）
索引表包括兩部分：關鍵字項（子表中的最大值）和指針項（子表的第一項在線性表L中位置）
索引表按關鍵字有序的。
例如：線性表L（有序）為：1 2 3 4 5 6 7 8 9 10 11 12
分成m=3個子表：{1 2 3 4} {5 6 7 8} {9 10 11 12}
索引表A：二維數組：第一列為每個子表的最大值 ，第二列為每個子表的起始地址
即： 4 0
8 4
12 8
⑥ 編寫無序順序表順序查找、有序順序表順序查找、二分查找演算法。用c語言。高分急求！
int IdxSerch(SeqList A[],IdxType index[],int b,KeyType k,int n) {
//分塊查找關鍵字為k的記錄，索引表為
index[0..b-1]
int low=0,high=b-1,mid,i;
int s=n/b; //每塊記錄個數
while(low<=high)
{
//在索引表中進行二分查找，找到的位置放在low中
mid=(low+high)/2;
if(index[mid].key<k) low=mid+1；
else high=mid-1;
}
if(low<b)
{
//在順序表中順序查找
for(i=index[low].link;i<=index[low].link+s-1 && i<n;i++)
if(A[i].key==k) return i;
return -1;
}
return -1;
}
typedef struct node
{
KeyType key;
//結點中的關鍵字
struct node *lchild,*rchild; //左、右孩子指針
}BsTree;
BsTree *BstSeareh(BsTree *BST,KeyType k ,BsTree **parent)
{
BsTree *p=BST,*q=NULL; //p指向根結點，q指向*p的雙親
while(p!=NULL)
{
if(k==p->key)
{ //查找成功
*parent=q;
return (p);
}
q=p;
if(k<p->key) p=p->lchild；
//在左子樹中查找
else p=p->rchild; //在右子樹中查找
}
*parent=q;
return (p);
//查找失敗，返回空
}
⑦ 求分塊查找演算法 最好有代碼和詳細注釋
注意：採用「二分查找」時，初始的數組或其他線性表中的每個元素都必須是按一定的順序排列的（從大到小，或從小到大），
該演算法的基本思想：對一個有序數據序列，總是先把查找目標與該序列的中間的元素進行比較，我們假設該序列是由從小到大排列的，if(key > data[mid]),則key一定在data[mid]的又邊，於是，把mid到序列data[end]分成一塊，此時mid = (mid + end) / 2,依次類推
參考程序：
#include<stdio.h>
#define MAXSIZE 26 //定義索引表的最長長度
typedef char TYPE;
int blksearch(TYPE R[],TYPE K);
void main()
{
int num, i;
TYPE R[N + 1];
TYPE K;
for(i = 0;i<N;i++)
R[i]='a'+i;
printf("\nplease input the key number:\n");
K=getchar();
num=blksearch(R,K);
if(num!=-1)
printf("第%d個是關鍵字\n",num+1);
else
printf("查找失敗！\n");
}
int blksearch(TYPE R[],TYPE K) //分塊查找
{
int low1,mid,high1;
low1=0;
high1=N - 1; //二分查找區間上下界初值
while(low1<=high1)
{
mid=(low1+high1)/2;
if(K < R[mid])
high1=mid-1;
else
if(K > R[mid])
low1=mid+1;
else
return mid; //如果找到key，立即返回key的位置
}
return -1;// 只要上面的return語句沒執行，則原數組中無key，返回-1
}