查找算法有序存储
⑴ 如果数据是有序的,可以采用二分查找算法以获得更高的效率对吗
摘要 二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。
⑵ 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;
}
折半查找运行结果：
三、实验总结：
该实验使用了两种查找数据的方法（顺序查找和折半查找），这两种方法的不同之处在于查找方式和过程不同，线性表的创建完全相同，程序较短，结果也一目了然。
⑶ 什么是查找法
算法思想：
将数列按有序化(递增或递减)排列，查找过程中采用跳跃式方式查找，即先以有序数列的中点位置为比较对象，如果要找的元素值小于该中点元素，则将待查序列缩小为左半部分，否则为右半部分。通过一次比较，将查找区间缩小一半。
折半查找是一种高效的查找方法。它可以明显减少比较次数，提高查找效率。但是，折半查找的先决条件是查找表中的数据元素必须有序。
算法步骤描述：
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；否则输出未找到信息。
⑷ 顺序查找法适用于查找顺序存储或链式存储的线性表
对。
链式存储的线性表的存取机制是顺序的，要想查找位置为i的元素必须采用顺序查找法；
顺序存储的线性表的存取机制是随机的，要想查找位置为i的元素直接用下标法就可以了。
如果要查找元素e在线性表中的位置那么对这两种存储结构而言，必须采用顺序查找法了。
(4)查找算法有序存储扩展阅读：
线性表结构特点：
1、均匀性：虽然不同数据表的数据元素可以是各种各样的，但对于同一线性表的各数据元素必定具有相同的数据类型和长度。
2、有序性：各数据元素在线性表中的位置只取决于它们的序号，数据元素之前的相对位置是线性的，即存在唯一的“第一个“和“最后一个”的数据元素，除了第一个和最后一个外，其它元素前面均只有一个数据元素(直接前驱)和后面均只有一个数据元素（直接后继）。
⑸ 程序设计问题，查找算法性能研究，帮下忙谢啦
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
static const int ARRAY_MAX = 10000;
typedef int DataType;
class SequentialStorage
{
public:
DataType data[ARRAY_MAX];
int top;
SequentialStorage()
{
top = -1;
}
void insertData(DataType data)
{
if(top == ARRAY_MAX-1)
return;
this->data[++top] = data;
}
int find(DataType data)
{
for(int i = 0;i <= top;i++)
{
if(this->data[i] == data)
return i;
}
return -1;
}
};
class OrderlySequenceStorage
{
public:
DataType data[ARRAY_MAX];
int top;
OrderlySequenceStorage()
{
top = -1;
}
void insertData(DataType data)//插入排序
{
if(top == ARRAY_MAX-1)
return;
int i = top;
while(this->data[i] > data&&i != -1)
{
this->data[i+1] = this->data[i];
i--;
}
this->data[i+1] = data;
top++;
}
int find(DataType data)//普通查找
{
for(int i = 0;i <= top;i++)
{
if(this->data[i] == data)
return i;
}
return -1;
}
int find2(DataType data)//二分法
{
if(this->data[0] > data||this->data[top] < data)
return -1;
if(this->data[0] == data)
return 0;
if(this->data[top] == data)
return top;
int a = 0;
int b = top;
while(true)
{
if(a == b-1)
return -1;
if(this->data[(a+b)/2] == data)
return (a+b)/2;
else if(this->data[(a+b)/2] < data)
a = (a+b)/2;
else
b = (a+b)/2;
}
}
};
typedef struct node
{
DataType data;
struct node *pNext;
}LLSNode;
class LinkedListStorage
{
public:
LLSNode *pHead;
LinkedListStorage()
{
pHead = NULL;
}
void insertData(DataType data)
{
LLSNode *p = (LLSNode *)malloc(sizeof(LLSNode));
p->data = data;
p->pNext = pHead;
pHead = p;
}
LLSNode *find(DataType data)
{
LLSNode *p = pHead;
while(p)
{
if(p->data == data)
return p;
p = p->pNext;
}
return NULL;
}
};
typedef struct node2
{
DataType data;
struct node2 *lchild,*rchild;
}BSTNode;
class BinarySortTree
{
public:
BSTNode *pRoot;
BinarySortTree()
{
pRoot = NULL;
}
void insertData(DataType data)
{
BSTNode *f,*p = pRoot;
while(p)
{
f = p;
if(data < p->data)
p = p->lchild;
else
p = p->rchild;
}
p = (BSTNode *)malloc(sizeof(BSTNode));
p->data = data;
p->lchild = NULL;
p->rchild = NULL;
if(pRoot == NULL)
pRoot = p;
else
if(data < f->data)
f->lchild = p;
else
f->rchild = p;
}
BSTNode *find(DataType data)
{
if(pRoot == NULL)
return NULL;
else
return recursion(data,pRoot);
}
BSTNode *recursion(DataType data,BSTNode *p)
{
if(data == p->data||p == NULL)
return p;
else if(data < p->data)
return recursion(data,p->lchild);
else
return recursion(data,p->rchild);
}
void print()
{
if(pRoot != NULL)
printR(pRoot);
}
void printR(BSTNode *p)
{
if(p->lchild != NULL)
printR(p->lchild);
printf("%d\t",p->data);
if(p->rchild != NULL)
printR(p->rchild);
}
};
class CPUTime
{
public:
_int64 getCPUCycleCount(void)
{
_asm _emit 0x0F
_asm _emit 0x31
}
long long arr[1000];
int count;
long long lastCPUCycleCount;
int randCount;
CPUTime()
{
for(int i = 0;i < 1000;i++)
arr[i] = 0;
count = -1;
lastCPUCycleCount = getCPUCycleCount();
randCount = 0;
}
void setTimePoint()
{
arr[++count] = getCPUCycleCount()-lastCPUCycleCount;
lastCPUCycleCount = getCPUCycleCount();
}
int rand()
{
randCount++;
int temp = getCPUCycleCount()%20000;
return (temp*(randCount+temp))%10007;
}
};
int main()
{
SequentialStorage ss;
OrderlySequenceStorage oss;
LinkedListStorage lls;
BinarySortTree bst;
DataType temp1;
CPUTime cpuTime;
for(int i = 0;i < 2000;i++)
{
temp1 = cpuTime.rand();
ss.insertData(temp1);
oss.insertData(temp1);
lls.insertData(temp1);
bst.insertData(temp1);
}
DataType temp[7];
for(int i = 0;i < 7;i++)
temp[i] = ss.data[cpuTime.rand()%2000];
cpuTime.setTimePoint();
for(int i = 0;i < 7;i++)
{
ss.find(temp[i]);
cpuTime.setTimePoint();
}
for(int i = 0;i < 7;i++)
{
oss.find(temp[i]);
cpuTime.setTimePoint();
}
for(int i = 0;i < 7;i++)
{
oss.find2(temp[i]);
cpuTime.setTimePoint();
}
for(int i = 0;i < 7;i++)
{
lls.find(temp[i]);
cpuTime.setTimePoint();
}
for(int i = 0;i < 7;i++)
{
bst.find(temp[i]);
cpuTime.setTimePoint();
}
int count = 1;
printf("各项存储结构查找已存在数据的时间（cpu周期）：\n");
printf("储存方式\t\t数据1\t数据2\t数据3\t数据4\t数据5\t数据6\t平均\n");
int a[9];
for(int i = 1;i < 8;i++)
a[i] = (int)cpuTime.arr[count++];
a[8] = (a[1]+a[2]+a[3]+a[4]+a[5]+a[6]+a[7])/7;
printf("顺序存储\t\t%d\t%d\t%d\t%d\t%d\t%d\t%d\n",a[1],a[2],a[3],a[4],a[5],a[6],a[8]);
for(int i = 1;i < 8;i++)
a[i] = (int)cpuTime.arr[count++];
a[8] = (a[1]+a[2]+a[3]+a[4]+a[5]+a[6]+a[7])/7;
printf("有序顺序存储(普通)\t%d\t%d\t%d\t%d\t%d\t%d\t%d\n",a[1],a[2],a[3],a[4],a[5],a[6],a[8]);
for(int i = 1;i < 8;i++)
a[i] = (int)cpuTime.arr[count++];
a[8] = (a[1]+a[2]+a[3]+a[4]+a[5]+a[6]+a[7])/7;
printf("有序顺序存储(二分法)\t%d\t%d\t%d\t%d\t%d\t%d\t%d\n",a[1],a[2],a[3],a[4],a[5],a[6],a[8]);
for(int i = 1;i < 8;i++)
a[i] = (int)cpuTime.arr[count++];
a[8] = (a[1]+a[2]+a[3]+a[4]+a[5]+a[6]+a[7])/7;
printf("链表存储\t\t%d\t%d\t%d\t%d\t%d\t%d\t%d\n",a[1],a[2],a[3],a[4],a[5],a[6],a[8]);
for(int i = 1;i < 8;i++)
a[i] = (int)cpuTime.arr[count++];
a[8] = (a[1]+a[2]+a[3]+a[4]+a[5]+a[6]+a[7])/7;
printf("二叉排序树存储\t\t%d\t%d\t%d\t%d\t%d\t%d\t%d\n",a[1],a[2],a[3],a[4],a[5],a[6],a[8]);
system("pause");
}
//我按照课题的要求写的c++具体实现的代码，楼主可以编译运行着试试，你可以参考一下
//我这搜索的是储存结构里已存在的数据，你也可以按题目的要求用随机生成的数据
//楼主留下qq吧，我等会把流程图发给你
//至于其他的，楼主还是自己试着写写看吧
⑹ 查找算法的作用
查找就是在一个数据集合里查找到你需要的数据，查找算法就是在查找过程中使用的算法。查找算法有好多，最基础的就是线性表查找。
因为提到了算法，所以需要注意的是时间复杂度跟空间复杂度，进而涉及到数据的存储方式，比如数组，链表，矩阵，树，图等等数据结构，这些数据结构可以帮助你降低算法的复杂度。
如果有兴趣，随便找本数据结构书翻翻，里面或多或少都会有讲解。用关键字标识一个数据元素，查找时根据给定的某个值，在表中确定一个关键字的值等于给定值的记录或数据元素。在计算机中进行查找的方法是根据表中的记录的组织结构确定的。顺序查找也称为线形查找，从数据结构线形表的一端开始，顺序扫描，依次将扫描到的结点关键字与给定值k相比较，若相等则表示查找成功；若扫描结束仍没有找到关键字等于k的结点，表示查找失败。二分查找要求线形表中的结点按关键字值升序或降序排列，用给定值k先与中间结点的关键字比较，中间结点把线形表分成两个子表，若相等则查找成功；若不相等，再根据k与该中间结点关键字的比较结果确定下一步查找哪个子表，这样递归进行，直到查找到或查找结束发现表中没有这样的结点。分块查找也称为索引查找，把线形分成若干块，在每一块中的数据元素的存储顺序是任意的，但要求块与块之间须按关键字值的大小有序排列，还要建立一个按关键字值递增顺序排列的索引表，索引表中的一项对应线形表中的一块，
⑺ 索引顺序查找算法
索引查找是在索引表和主表(即线性表的索引存储结构)上进行的查找。索引查找的过程是：首先根据给定的索引值K1，在索引表上查找出索引值等于KI的索引项，以确定对应予表在主表中的开始位置和长度，然后再根据给定的关键字K2，茬对应的子表中查找出关键字等于K2的元素(结点)。对索引表或子表进行查找时，若表是顺序存储的有序表，则既可进行顺序查找，也可进行二分查找，否则只能进行顺序查找。
设数组A是具有mainlist类型的一个主表，数组B是具有inde)dist类型的在主表A 上建立的一个索引表，m为索引表B的实际长度，即所含的索引项的个数，KI和K2分别为给定待查找的索引值和关键字(当然它们的类型应分别为索引表中索引值域的类型和主表中关键字域在索引存储中，不仅便于查找单个元素，而且更便于查找一个子表中的全部元素。当需要对一个子袁中的全部元素依次处理时，只要从索引表中查找出该子表的开始位置即可。由此开始位置可以依次取出该子表中的每一个元素，所以整个查找过程的时间复杂度为，若不是采用索引存储，而是采用顺序存储，即使把它组织成有序表而进行二分查找时，索引查找一个子表中的所有元素与二分查找一个子表中的所有元素相比。
若在主表中的每个子表后都预留有空闲位置，则索引存储也便于进行插入和删除运算，因为其运算过程只涉及到索引表和相应的子表，只需要对相应子表中的元素进行比较和移动，与其它任何子表无关，不像顺序表那样需涉及到整个表中的所有元素，即牵一发而动全身。
在线性表的索引存储结构上进行插入和删除运算的算法，也同查找算法类似，其过程为：首先根据待插入或删除元素的某个域(假定子表就是按照此域的值划分的)的值查找索引表，确定出对应的子表，然后再根据待插入或删除元素的关键字，在该子表中做插入或删除元素的操作。因为每个子表不是顺序存储，就是链接存储，所以对它们做插入或删除操作都是很简单的。
不知道答案与兄台的问题是否一致，也是网上找的，不对请见谅哈~~
⑻ 二分法查找为什么只适用于顺序存储
举个例子，在1 2 6 4 5 7 8 9 10中，你要用二分法查找6，你得先把6跟中间的5比较，6很明显大于5，所以就只能在5 7 8 9 10中查找，这样很明显找不到，所以二分法必须要求用于顺序排列的数，如果不是顺序排列的，二分法就完全没有意义
⑼ 查找算法性能研究（顺序存储、有序顺序存储、链表存储、二叉排序树存储）
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
static const int ARRAY_MAX = 10000;
typedef int DataType;
class SequentialStorage
{
public:
DataType data[ARRAY_MAX];
int top;
SequentialStorage()
{
top = -1;
}
void insertData(DataType data)
{
if(top == ARRAY_MAX-1)
return;
this->data[++top] = data;
}
int find(DataType data)
{
for(int i = 0;i <= top;i++)
{
if(this->data[i] == data)
return i;
}
return -1;
}
};
class OrderlySequenceStorage
{
public:
DataType data[ARRAY_MAX];
int top;
OrderlySequenceStorage()
{
top = -1;
}
void insertData(DataType data)//插入排序
{
if(top == ARRAY_MAX-1)
return;
int i = top;
while(this->data[i] > data&&i != -1)
{
this->data[i+1] = this->data[i];
i--;
}
this->data[i+1] = data;
top++;
}
int find(DataType data)//普通查找
{
for(int i = 0;i <= top;i++)
{
if(this->data[i] == data)
return i;
}
return -1;
}
int find2(DataType data)//二分法
{
if(this->data[0] > data||this->data[top] < data)
return -1;
if(this->data[0] == data)
return 0;
if(this->data[top] == data)
return top;
int a = 0;
int b = top;
while(true)
{
if(a == b-1)
return -1;
if(this->data[(a+b)/2] == data)
return (a+b)/2;
else if(this->data[(a+b)/2] < data)
a = (a+b)/2;
else
b = (a+b)/2;
}
}
};
typedef struct node
{
DataType data;
struct node *pNext;
}LLSNode;
class LinkedListStorage
{
public:
LLSNode *pHead;
LinkedListStorage()
{
pHead = NULL;
}
void insertData(DataType data)
{
LLSNode *p = (LLSNode *)malloc(sizeof(LLSNode));
p->data = data;
p->pNext = pHead;
pHead = p;
}
LLSNode *find(DataType data)
{
LLSNode *p = pHead;
while(p)
{
if(p->data == data)
return p;
p = p->pNext;
}
return NULL;
}
};
typedef struct node2
{
DataType data;
struct node2 *lchild,*rchild;
}BSTNode;
class BinarySortTree
{
public:
BSTNode *pRoot;
BinarySortTree()
{
pRoot = NULL;
}
void insertData(DataType data)
{
BSTNode *f,*p = pRoot;
while(p)
{
f = p;
if(data < p->data)
p = p->lchild;
else
p = p->rchild;
}
p = (BSTNode *)malloc(sizeof(BSTNode));
p->data = data;
p->lchild = NULL;
p->rchild = NULL;
if(pRoot == NULL)
pRoot = p;
else
if(data < f->data)
f->lchild = p;
else
f->rchild = p;
}
BSTNode *find(DataType data)
{
if(pRoot == NULL)
return NULL;
else
return recursion(data,pRoot);
}
BSTNode *recursion(DataType data,BSTNode *p)
{
if(data == p->data||p == NULL)
return p;
else if(data < p->data)
return recursion(data,p->lchild);
else
return recursion(data,p->rchild);
}
void print()
{
if(pRoot != NULL)
printR(pRoot);
}
void printR(BSTNode *p)
{
if(p->lchild != NULL)
printR(p->lchild);
printf("%d\t",p->data);
if(p->rchild != NULL)
printR(p->rchild);
}
};
class CPUTime
{
public:
_int64 getCPUCycleCount(void)
{
_asm _emit 0x0F
_asm _emit 0x31
}
long long arr[1000];
int count;
long long lastCPUCycleCount;
int randCount;
CPUTime()
{
for(int i = 0;i < 1000;i++)
arr[i] = 0;
count = -1;
lastCPUCycleCount = getCPUCycleCount();
randCount = 0;
}
void setTimePoint()
{
arr[++count] = getCPUCycleCount()-lastCPUCycleCount;
lastCPUCycleCount = getCPUCycleCount();
}
int rand()
{
randCount++;
int temp = getCPUCycleCount()%20000;
return (temp*(randCount+temp))%10007;
}
};
int main()
{
SequentialStorage ss;
OrderlySequenceStorage oss;
LinkedListStorage lls;
BinarySortTree bst;
DataType temp1;
CPUTime cpuTime;
for(int i = 0;i < 2000;i++)
{
temp1 = cpuTime.rand();
ss.insertData(temp1);
oss.insertData(temp1);
lls.insertData(temp1);
bst.insertData(temp1);
}
DataType temp[7];
for(int i = 0;i < 7;i++)
temp[i] = ss.data[cpuTime.rand()%2000];
cpuTime.setTimePoint();
for(int i = 0;i < 7;i++)
{
ss.find(temp[i]);
cpuTime.setTimePoint();
}
for(int i = 0;i < 7;i++)
{
oss.find(temp[i]);
cpuTime.setTimePoint();
}
for(int i = 0;i < 7;i++)
{
oss.find2(temp[i]);
cpuTime.setTimePoint();
}
for(int i = 0;i < 7;i++)
{
lls.find(temp[i]);
cpuTime.setTimePoint();
}
for(int i = 0;i < 7;i++)
{
bst.find(temp[i]);
cpuTime.setTimePoint();
}
int count = 1;
printf("各项存储结构查找已存在数据的时间（cpu周期）：\n");
printf("储存方式\t\t数据1\t数据2\t数据3\t数据4\t数据5\t数据6\t平均\n");
int a[9];
for(int i = 1;i < 8;i++)
a[i] = (int)cpuTime.arr[count++];
a[8] = (a[1]+a[2]+a[3]+a[4]+a[5]+a[6]+a[7])/7;
printf("顺序存储\t\t%d\t%d\t%d\t%d\t%d\t%d\t%d\n",a[1],a[2],a[3],a[4],a[5],a[6],a[8]);
for(int i = 1;i < 8;i++)
a[i] = (int)cpuTime.arr[count++];
a[8] = (a[1]+a[2]+a[3]+a[4]+a[5]+a[6]+a[7])/7;
printf("有序顺序存储(普通)\t%d\t%d\t%d\t%d\t%d\t%d\t%d\n",a[1],a[2],a[3],a[4],a[5],a[6],a[8]);
for(int i = 1;i < 8;i++)
a[i] = (int)cpuTime.arr[count++];
a[8] = (a[1]+a[2]+a[3]+a[4]+a[5]+a[6]+a[7])/7;
printf("有序顺序存储(二分法)\t%d\t%d\t%d\t%d\t%d\t%d\t%d\n",a[1],a[2],a[3],a[4],a[5],a[6],a[8]);
for(int i = 1;i < 8;i++)
a[i] = (int)cpuTime.arr[count++];
a[8] = (a[1]+a[2]+a[3]+a[4]+a[5]+a[6]+a[7])/7;
printf("链表存储\t\t%d\t%d\t%d\t%d\t%d\t%d\t%d\n",a[1],a[2],a[3],a[4],a[5],a[6],a[8]);
for(int i = 1;i < 8;i++)
a[i] = (int)cpuTime.arr[count++];
a[8] = (a[1]+a[2]+a[3]+a[4]+a[5]+a[6]+a[7])/7;
printf("二叉排序树存储\t\t%d\t%d\t%d\t%d\t%d\t%d\t%d\n",a[1],a[2],a[3],a[4],a[5],a[6],a[8]);
system("pause");
}
//我按照课题的要求写的c++具体实现的代码，楼主可以编译运行着试试，你可以参考一下
//我这搜索的是储存结构里已存在的数据，你也可以按题目的要求用随机生成的数据
//楼主留下qq吧，我等会把流程图发给你
//至于其他的，楼主还是自己试着写写看吧
另外,站长团上有产品团购,便宜有保证
⑽ 查找算法的二分查找
二分查找又称折半查找，它是一种效率较高的查找方法。
【二分查找要求】：1.必须采用顺序存储结构2.必须按关键字大小有序排列。
【优缺点】折半查找法的优点是比较次数少，查找速度快，平均性能好;其缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。【算法思想】首先，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。【算法复杂度】假设其数组长度为n，其算法复杂度为o（log（n））
下面提供一段二分查找实现的伪代码:
BinarySearch(max,min,des)
mid-des thenmax=mid-1elsemin=mid+1return max
折半查找法也称为二分查找法，它充分利用了元素间的次序关系，采用分治策略，可在最坏的情况下用O(log n)完成搜索任务。它的基本思想是，将n个元素分成个数大致相同的两半，取a[n/2]与欲查找的x作比较，如果x=a[n/2]则找到x，算法终止。如 果xa[n/2]，则我们只要在数组a的右 半部继续搜索x。