当前位置： > 平面设计 > Photoshop教程 > 文章内容

数据结构折半查找代码(数据结构中折半查找的平均查找长度)

http://www.itjxue.com 2023-04-04 01:14 来源:未知 点击次数:

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;is-length;i++)

scanf("%d",(s-r[i].key));

printf("\n");

printf("您所输入的数据为:\n\n");

for(i=0;is-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;is-length;i++)

scanf("%d",(s-r[i].key));

printf("\n");

printf("您所输入的数据为:\n\n");

for(i=0;is-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].keyk)

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;

}

折半查找运行结果：

三、实验总结：

该实验使用了两种查找数据的方法（顺序查找和折半查找），这两种方法的不同之处在于查找方式和过程不同，线性表的创建完全相同，程序较短，结果也一目了然。

数据结构折半查找代码(数据结构中折半查找的平均查找长度)

数据结构中的折半查找是怎么回事？谁能给个具体例子，谢谢了。

你好　：

这是我之前写的代码希望能对你有所帮助：

思路：

1.　务必是有序数组　（重点！）　

百度百科：（这里偷个懒）半查找法也称为二分查找法，它充分利用了元素间的次序关系，采用分治策略，可在最坏的情况下用O(log n)完成搜索任务。它的基本思想是，将n个元素分成个数大致相同的两半，取a[n/2]与欲查找的x作比较，如果x=a[n/2]则找到x，算法终止。如果xa[n/2]，则我们只要在数组a的左半部继续搜索x（这里假设数组元素呈升序排列）。如果xa[n/2]，则我们只要在数组a的右半部继续搜索x。

这个代码输入为有序数组　，　寻找的值

返回：如果找到返回所在坐标，如果没找到返回最小的整型

/**

*?@param?arr?有序数组

*?@param?target?查找值

*?@return???找到就返回坐标位置，找不到就返回最小值。

*?@throws?Exception

*?@dec?二分查找的非递归算法?，

*?时间复杂度：?o?log（n）???n??n/2??n/4??假设?k次找到?。?n/(2的k次方)?即?2的k次方=n?所以k=?logn

public?static?int??binarySearch(int?arr[],?int?target)?throws?Exception?{????

if(arr==null)?{

throw?new?Exception("ARR?IS?NULL");

}

if(arr.length=0)?{

throw?new?Exception("length??is?illegal");

}

int?low?=?0;

int?high?=?arr.length-1;

while(low=high)?{

if(target==arr[(low+high)/2])?{

return?(low+high)/2;

}else?if(targetarr[(low+high)/2])?{

low?=?(low+high)/2?+1?;

}else?{

high?=?(low+high)/2?-1;

}

return?Integer.MIN_VALUE;??

}

如果有问题欢迎继续交流指教！

数据结构关于数据查找的代码（用C语言）

（1）创建图的邻接矩阵和邻接表

（2）验证图的深度优先、广度优先遍历算法

（3）验证最短路径问题

问题太多了，每个小问题，都可以写不少代码

下面是问题1的代码，其他的问题，网上也很容易找到

// 邻接矩阵表示 :

#include iostream.h

#include stdlib.h

#define INFINITY 0

#define MAX_VERTEX_NUM 10 //最大顶点数

#define MAX_EDGE_NUM 40 //最大边数

typedef enum Graphkind;

typedef char VertexType; //顶点数据类型

typedef struct ArcCell

{

int adj; //无权图，1或0表示相邻否；带权图则是权值。

//int *info;

}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

typedef struct

{

VertexType vexs[MAX_VERTEX_NUM]; //顶点向量

AdjMatrix arcs; //邻接矩阵

int vexnum,arcnum; //图的当前顶点数和弧数。

Graphkind kind;

}MGraph;

int LocateVex(MGraph G,VertexType v1)

{

int i;

for(i=0;iG.vexnum;i++)

if(G.vexs[i]==v1)

return i;

return -1;

}

int CreatUDN(MGraph G)

// 采用数组表示法，构造无向网 G

{

VertexType v1,v2;

int w,j;

cout"输入图的顶点数"endl;

cinG.vexnum;

cout"输入图的弧数"endl;

cinG.arcnum;

for(int i=0;iG.vexnum;i++)

{

cout"输入顶点向量"endl;

cinG.vexs[i];

}

for(i=0;iG.vexnum;i++)

for(j=0;jG.vexnum;j++)

{

G.arcs[i][j].adj=INFINITY;

}

for(int k=0;kG.arcnum;++k) //构造邻接矩阵

{

cout"输入边依附的两个顶点"endl;

cinv1v2;

cout"输入此边的权值"endl;

cinw;

i=LocateVex(G,v1);

j=LocateVex(G,v2);

G.arcs[i][j].adj=w;

G.arcs[j][i].adj=G.arcs[i][j].adj;

}

return 1;

}

void dispMGraph(MGraph G)

{

cout"图的邻接矩阵图是："endl;

for(int i=0;iG.vexnum;i++)

{

for(int j=0;jG.vexnum;j++)

cout" "G.arcs[i][j].adj;

coutendl;

}

void main()

{

MGraph G;

CreatUDN(G);

dispMGraph(G);

}

// 邻接表表示:

#include iostream.h

#include stdlib.h

#define MAX_VERTEX_NUM 20 //最大顶点数

#define MAX_EDGE_NUM 40 //最大边数

int visited[ MAX_VERTEX_NUM];

typedef int VertexType ; //顶点数据类型

typedef struct ArcNode

{

int adjvex;

int weight;

struct ArcNode *nextarc;

}ArcNode;

typedef struct VNode

{

VertexType data;

ArcNode *firstarc;

}VNode,AdjList[MAX_VERTEX_NUM];

typedef struct

{

AdjList vertices;

int vexnum,arcnum;

int kind;

}ALGraph;

void CreateDG(ALGraph G)

{

int i,j,k;

ArcNode *p;

cout"创建一个图:"endl;

cout"顶点数:"; cinG.vexnum;coutendl;

cout"边数:"; cinG.arcnum; coutendl;

for(i=0;iG.vexnum;i++)

{

G.vertices[i].data=i;

G.vertices[i].firstarc=NULL;

}

for(k=0;kG.arcnum;k++)

{

cout"请输入第"k+1"条边:";

cinij;

p=(ArcNode*)malloc(sizeof(ArcNode));

p-adjvex=j;

p-nextarc=G.vertices[i].firstarc;

G.vertices[i].firstarc=p;

}

void Disp(ALGraph G)

{

int i,j;

ArcNode *p;

cout"输出图为:"endl;

for(i=0;iG.vexnum;i++)

{

p=G.vertices[i].firstarc;

j=0;

while(p!=NULL)

{

cout"("i","p-adjvex")";

p=p-nextarc;

j=1;

}

if(j==1)

coutendl;

}

void dfs(ALGraph G,int v) //深度优先遍历

{

ArcNode *p;

coutv" ";

visited[v]=1;

p=G.vertices[v].firstarc;

while(p!=NULL)

{ if(!visited[p-adjvex])

dfs(G,p-adjvex);

p=p-nextarc;

}

return ;

}

void dfs1(ALGraph G)

{

int i;

for(i=0;iG.vexnum;i++)

if(visited[i]==0)

dfs(G,i);

}

void main()

{

ALGraph G;

CreateDG(G);

int v;

Disp(G);

cout"输入顶点:";

cinv;

cout"深度优先序列:";

dfs1(G);

coutendl;

}

补充：

c和c＋＋本来就差不了多少

只需要把#include iostream.h换成#include stdio.h

把cout换成printf，把cin换成scanf

就能把上述c＋＋的代码变化成c的啊

程序实现折半查找算法，要求事先建立一个有序的顺序表

// hgjkg.cpp : 定义控制台应用程序的入口点。

#include "stdafx.h"

#define n 11

int count=0;

int bin_search(int a[],int low,int high,int x) //折半查找函数

{ count++;

int mid;

if(lowhigh) return -1;

else

{

mid=(low+high)/2;

if(x==a[mid]) return mid;

else if(xa[mid])

return bin_search(a,low,mid-1,x);

else

return bin_search(a,mid+1,high,x);

}

int _tmain(int argc, _TCHAR* argv[])

{

int s;

int a[n]={3,5,8,10,15,22,28,30,31,55};

s=bin_search(a,0,9,28);

if(s==-1){

printf("没有找到要查询的数\n");

printf("本次查询总用了 %d 次\n",count);

}

else

{

printf("本次查询总用了 %d 次\n",count);

printf("本次查找到的下标是: %d \n",s);

}

return 0;

}

这程序我已经运行成功了，我是在VS2005环境下运行的