数据结构顺序查找与折半查找

格式：pdf
大小：75.41 KB
文档页数：1

数据结构顺序查找与折半查找

1，顺序查找

顺序查找⼜称线性查找，它对顺序表和链表都适⽤。

（1）以下给出相关函数

1 typedef struct{

2 ElemType *elem; //元素存储空间地址，建表时按实际长度分配，0号单元留空

3 int TableLen; //表的长度

4 }SSTable;

5 int Search_Seq(SSTable ST,ElemType key)

6 {

7 ST.elem[0]=key; //把要查找的关键字放在0号位置，称“哨兵”

8 for(int i=ST.TableLen;ST.elem!=key;i--) //从后往前找

9 {

10 return i; //若表中不存在关键字为key的元素，将查找i=0时退出循环

11 }

12 }

在上述算法中，将ST.elem[0]称为“哨兵”。引⼊它的⽬的是使得Search_Seq内的循环不必判断数组是否会越界。因为满⾜i=0时，循环⼀定

会跳出。除此之外，引⼊“哨兵”可以避免很多不必要的判断语句，从⽽提⾼算法的执⾏效率。

（2）算法效率分析

当每个元素查找概率相同时，平均查找长度ASL=（n+1)/2, 查找不成功时，需要⽐较整个顺序表，所以⽐较次数时（n+1)次，从⽽顺序查找

不成功的平均查找长度为(n+1)。

2.有序表的顺序查找（假设从⼩到⼤排列）

有序表的顺序查找成功的平均查找长度与⼀般的线性表⼀样，即（n+1)/2.

当查找失败时，待查找的元素为key,当查找第i个元素时，发现第i个元素的对应的关键字⼩于key,但第i+1个元素对应的关键字⼤于key,这时

就可以返回查找失败的信息。

查找失败的平均查找长度为ASL=n/2+n/(n+1).

3.折半查找

前提：折半查找仅适⽤于有序的顺序表。

折半查找原理：将给定的key与中间元素⽐较，直到查到要找的元素。

以下是相关函数

1 int Binary_Search(SeqList L,ElemType key){

2 int low=0,high=L.TableLen-1,mid;//low指向表头，high指向表尾，mid中间值

3 while(low<=high)

4 {

5 mid=(low+high)/2;

6 if(L.elem[mid]==key) //中间值等于要查找元素

7 return mid;

8 else if(L.elem[mid]

9 low=mid+1;

10 else

11 hign=mid-1; //要查找元素在中间值左边

12 }

13 }

查找成功的时间复杂度为log2n，平均情况下⽐顺序查找效率⾼⼀些。

引⼊⼀个思考题，我们已经知道顺序查找成功的时间复杂度为(n+1)/2,折半查找的时间复杂度为，log2n那么折半查找的效率

⼀定⽐顺序查找⾼吗？

答案是否定的，假设我们查找的元素在顺序表的第⼀个位置，那么顺序查找只需要查找1次就可以，⼆折半查找需要很多

次，时间复杂度只是查找的平均时间复杂度的反映。

数据结构-折半查找,哈希查找

第 1 页共 3 页一、实验目的

熟练掌握顺序查找，折半查找和哈希表等算法的程序实现。

二、实验内容

1、实现折半查找的算法

编写一个程序，输出在顺序表（1,2,3,4,,6,7,8,9,10）中采用折半查找方法查找关键字9的过程

要求：输出查找过程中的比较对象和被查找元素的位置。

2、实现哈希表的相关运算算法

编写程序实现哈希表的构造过程。

要求：建立关键字序列（16,74,60,43,54,90,46,31,29,88,77）对应的哈希表A[0...12]，哈希函数为H（k）=k%p，并采用开放定址法中的线性探测法解决冲突。输出构造完成后的哈希表。

程序源代码及运行结果（运行结果可以截图，也可以文字描述分析）

#include

int fun(int a[],int key)

{

int high=9;

int low=0;

int mid=(high+low)/2;

printf("与之相比较的值为:");

while(high>=low)

{

if(key==a[mid])

{

printf("%-2d",a[mid]);

printf("\nkey为数组中第%d个元素\n",mid+1);

break;

}

if(key

{ printf("%-2d",a[mid]);

high=mid-1;

mid=(high+low)/2;

}

if(key>a[mid])

{ printf("%-2d",a[mid]); 第 2 页共 3 页 low=mid+1;

数据结构顺序表查找(c++)

#include

template

class arrlist{

private:

T *alist;

int maxsize;

int curlen;

int position;

public:

arrlist(const int size){

maxsize=size;

alist=new T[maxsize];

curlen=position=0;

}

~arrlist(){

delete[] alist;

}

void clear(){

delete[] alist;

curlen=position=0;

alist=new T[maxsie];

}

bool getpos(int&p,const T value){

int i;

for(i=0;i<10;i++)

if(value==alist[i]){

p=i;

return true;

}

return false;

}

bool append(const T value){

int i;

if(curlen==maxsize)

{cout<<"表满"<

return false;}

for(i=curlen;i

alist[i]=value;

curlen++;

return true;}

};

void main(){

arrlist a(100); int i,A[10]={0,1,2,3,4,5,6,77,8,9},u=77,q=0;

for(i=0;i<=9;i++)

a.append(A[i]);

a.getpos(q,u);

cout<

算法与数据结构的顺序查找

#include "stdio.h"

#include"stdlib.h"

#include"string.h"

#define MAX 31

typedef struct

{ int *k;

int *elem;

char *aa;

int length;

}SSTable;

int lw_Search(SSTable ST,int key)

{

int i;

ST.elem[0]=key;

for(i=ST.length;ST.elem[i]!=ST.elem[0];--i);

return i;

}

int lw_Search2(SSTable ST,int n,int key)

{

int low=1;int high=ST.length;int mid,a=0;

while(low<=high)

{

mid=(low+high)/2;

printf("第%d次查找:在[%d,%d]中找到元素ST[%d]: %d\n",++a,low,high,mid,ST.k[mid]);

if(ST.k[mid]==key)

return mid;

else if(ST.k[mid]>key)

high=mid-1;

else

low=mid+1;

}

return 0;

}

int lw_bubble(SSTable ST,int n)

{int i,j,temp;int *a;

for(i=1;i

for(j=i+1;j<=n;j++)

if(ST.k[i]>ST.k[j])

{ temp=ST.k[i];

ST.k[i]=ST.k[j];

ST.k[j]=temp;

}

int lw_prit(SSTable ST,int n)

{

int i;int *a;

for(i=1;i

printf("%-8d",ST.k[i]);

数据结构——折半查找源代码

数据结构折半查找源代码

源代码：

折半查找：

#include//cout,cin

#include"process.h"//exit()

#include"stdio.h"//EOF,NULL

typedef int T; //定义关键字的类型,这里就以整形来处理

//查找表类定义

template

struct Node

{

T key; //关键字域

........ //其他域,可以自己根据需要添加

};

template

class SSearch {

private:

Node *ST;

int len;//表长

public:

SSearch();//

~SSearch();//析构函数，删除表空间

void Create(int n); //创建时根据用户实际需求,再为相应的数据元素赋值

void Display(); //输出静态表中的数据元素

int SeSearch(T key); //从表中最后一个元素开始顺序查找

void Ascendsort(); //升序排列

int BiSearch_1(T key);//折半查找，非递归算法

int BiSearch_2(T key);//折半查找，递归算法

int BiSearch2(int x,int y,T key);

};

template

SSearch::SSearch()

{//

ST=NULL;

len=0; }

template

SSearch::~SSearch()

{//释放表空间

delete [] ST;

len=0;

}

template

void SSearch::Create(int n)

{

len=n;

ST=new Node[len];

下载提示

1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

数据结构顺序查找与折半查找

合集下载

数据结构-折半查找,哈希查找

数据结构顺序表查找(c++)

算法与数据结构的顺序查找

数据结构——折半查找源代码

文档推荐

最新文档