① 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
}