SCAU华南农业大学数据结构oj 实验五
8610 顺序查找
Description
编写Search_Seq函数，实现在一个无序表ST中采用顺序查找算法查找值为key的元素的算法.
#include"malloc.h" /* malloc()等 */
#include"stdio.h"
#include"stdlib.h"
typedef int ElemType;
typedef struct /*静态查找表的顺序存储结构 */
{
ElemType *elem; /* 数据元素存储空间基址，建表时按实际长度分配，0号单元留空 */
int length; /* 表长度 */
}SSTable;
void Creat_Seq(SSTable &ST,int n)
{ /* 操作结果: 构造一个含n个数据元素的静态顺序查找表ST(数据来自数组r) */
int i,temp;
ST.elem=(ElemType *)malloc((n+1) * sizeof(ElemType)); /* 动态生成n个数据元素空间(0号单元不用) */
if(!(ST).elem)
{
printf("ERROR\n");
exit(0);
} /*内存分配失败结束程序*/
for(i=1;i<=n;i++)
{
scanf("%d",&temp);
*(ST.elem+i)=temp; /* 依次赋值给ST */
}
ST.length=n;
}
int Search_Seq(SSTable &ST,ElemType key)
{ /* 在顺序表ST中顺序查找其关键字等于key的数据元素。若找到，则函数值为 */
/* 该元素在表中的位置，否则为0。算法9.1 */
}
main()
{
SSTable ST;
int loc,key;
int n;
scanf("%d",&n);
Creat_Seq(ST,n);
//printf("Please input the key value：");
scanf("%d",&key);
loc = Search_Seq(ST,key);
if(loc!=0)
printf("The element position is %d.\n",loc);
else
printf("The element is not exist.\n");
}
输入格式
第一行:元素个数n
第二行：依次输入n个元素的值
第三行：输入要查找的关键字key的值
输出格式
输出分两种情形：
1.如果key值存在，则输出其在表中的位置x(表位置从1开始),格式为The element position is x.
2.如果key值不存在输出："The element is not exist."
输入样例
6
1 3 5 7 9 10
5
输出样例
The element position is 3.
#include"malloc.h" /* malloc()等 */
#include"stdio.h"
#include"stdlib.h"
typedef int ElemType;
typedef struct /*静态查找表的顺序存储结构 */
{
ElemType *elem; /* 数据元素存储空间基址，建表时按实际长度分配，0号单元留空 */
int length; /* 表长度 */
}SSTable;
void Creat_Seq(SSTable &ST,int n)
{ /* 操作结果: 构造一个含n个数据元素的静态顺序查找表ST(数据来自数组r) */
int i,temp;
ST.elem=(ElemType *)malloc((n+1) * sizeof(ElemType)); /* 动态生成n个数据元素空间(0号单元不用) */
if(!(ST).elem)
{
printf("ERROR\n");
exit(0);
} /*内存分配失败结束程序*/
for(i=1;i<=n;i++)
{
scanf("%d",&temp);
*(ST.elem+i)=temp; /* 依次赋值给ST */
}
ST.length=n;
}
int Search_Seq(SSTable &ST,ElemType key)
{
for(int i=ST.length;i>=1;--i)
{
if(ST.elem[i]==key)
{
return i;
}
}
return 0;
}
main()
{
SSTable ST;
int loc,key;
int n;
scanf("%d",&n);
Creat_Seq(ST,n);
//printf("Please input the key value：");
scanf("%d",&key);
loc = Search_Seq(ST,key);
if(loc!=0)
printf("The element position is %d.\n",loc);
else
printf("The element is not exist.\n");
}
解析：顺序查找很简单，从后往前找，找到了返回值，没什么说的
8621 二分查找
Description
编写Search_Bin函数，实现在一个递增有序数组ST中采用折半查找法确定元素位置的算法.
输入格式
第一行:元素个数n
第二行：依次输入n个元素的值（有序）
第三行：输入要查找的关键字key的值
输出格式
输出分两种情形：
1.如果key值存在，则输出其在表中的位置x(表位置从0开始),格式为The element position is x.
2.如果key值不存在输出："The element is not exist."
输入样例
6
1 3 5 7 9 10
5
输出样例
The element position is 2.
#include <iostream>
#include <vector>
using namespace std;
int bs(vector<int> &man,int key)
{
int low=0;
int high=man.size()-1;
while(low<=high){
int mid=low+(high-low)/2;
if(man[mid]==key)
{
return mid;
}
else if(man[mid]<key)
{
low=mid+1;
}
else
{
high=mid-1;
}
}
return -1;
}
int main()
{
int n;
cin>>n;
vector<int> man(n);
for(int i=0;i<man.size();i++)
{
cin>>man[i];
}
int key;
cin>>key;
int res=bs(man,key);
if(res!=-1)
{
cout <<"The element position is "<<res<<"."<< endl;
}
else
{
cout<<"The element is not exist."<<endl;
}
return 0;
}
解析：二分查找的原理也很简单，不断与中间值mid比较，如果小了就跟小的那一半的中间值比，如果大了就跟大的那一半的中间值比，不断循环直到找到或者low<high
8622 哈希查找
Description
使用哈希函数：H(k)=3*k MOD length，并采用开放定址法处理冲突。试对输入的关键字序列构造哈希表，哈希表长度为length，求等概率情况下查找成功的平均查找长度，并设计构造哈希表的完整的算法。本题给出部分代码，请补全Hash函数和解决冲突的collison函数。
#include"malloc.h" /* malloc()等 */
#include"stdlib.h" /* exit() */
#include"stdio.h"
#define EQ(a,b) ((a)==(b))
#define SUCCESS 1
#define UNSUCCESS 0
#define NULLKEY -1 /*哈希表无元素时值为-1*/
typedef int ElemType;
int length;
typedef struct
{
ElemType *elem; /* 数据元素存储基址，动态分配数组 */
int count; /* 当前数据元素个数 */
}HashTable;
void InitHashTable(HashTable *H)
{ /* 操作结果: 构造一个长度为length的哈希表,length为全局变量 */
int i;
(*H).count=0; /* 当前元素个数为0 */
(*H).elem=(ElemType*)malloc(length*sizeof(ElemType));
if(!(*H).elem)
exit(0); /* 存储分配失败 */
for(i=0;i<length;i++)
(*H).elem[i]=NULLKEY; /* 未填记录的标志 */
}
unsigned Hash(ElemType K)
{ /* 一个简单的哈希函数*/
}
void collision(int *p) /*线性探测再散列 */
{ /* 开放定址法处理冲突 */
}
int SearchHash(HashTable H,ElemType K,int *p,int *c)
{ /* 在开放定址哈希表H中查找关键码为K的元素,若查找成功,以p指示待查数据 */
/* 元素在表中位置,并返回SUCCESS;否则,以p指示插入位置,并返回UNSUCCESS */
/* c用以计冲突次数，其初值置零，供建表插入时参考。算法9.17 */
*p=Hash(K); /* 求得哈希地址 */
while(H.elem[*p]!=NULLKEY&&!EQ(K,H.elem[*p]))
{ /* 该位置中填有记录,并且关键字不相等 */
(*c)++;
if(*c<length)
collision(p); /* 求得下一探查地址p */
else
break;
}
if EQ(K,H.elem[*p])
return SUCCESS; /* 查找成功，p返回待查数据元素位置 */
else
return UNSUCCESS; /* 查找不成功(H.elem[p].key==NULLKEY)，p返回的是插入位置 */
}
int InsertHash(HashTable *H,ElemType e)
{ /* 查找不成功时插入数据元素e到开放定址哈希表H中，并返回查找长度 */
int c,p;
c=0;
if(SearchHash(*H,e,&p,&c)) /* 表中已有与e有相同关键字的元素 */
printf("哈希表中已有元素%d。\n",e);
else{ /* 插入e */
(*H).elem[p]=e;
++(*H).count;
}
return c+1; /*查找长度为冲突次数加1*/
}
void TraverseHash(HashTable H)
{ /* 按哈希地址的顺序打印哈希表，无元素位置用X表示 */
int i;
printf("HashTable Address:0～%d\n",length-1);
for(i=0;i<length;i++)
if(H.elem[i]==NULLKEY) /* 有数据 */
printf("X ");
else
printf("%d ",H.elem[i]);
printf("\n");
}
main()
{
float i=0,j=0;
ElemType e;
HashTable H;
//printf("Input Table length:");
scanf("%d",&length);
InitHashTable(&H);
//printf("Input key words sequence, -1 conclusion input：");
scanf("%d",&e);
while(e!=-1)
{
j ++; /*j记录输入元素个数*/
i = i + InsertHash(&H,e); /*i记录查找长度的和*/
scanf("%d",&e);
}
TraverseHash(H);
printf("Average search length=%f\n",i/j);
}
输入格式
第一行：输入哈希表的长度；
第二行：输入关键字序列，用空格分隔，-1结束(-1不作为关键字)。
输出格式
第一行：输出哈希表里的数据，未使用的单元用X表示；
第二行：输出平均查找长度,格式为"Average search length="。
输入样例
11
22 41 53 46 30 13 1 67 -1
输出样例
22 X 41 30 1 53 46 13 67 X X
Average search length=2.000000
#include"malloc.h" /* malloc()等 */
#include"stdlib.h" /* exit() */
#include"stdio.h"
#define EQ(a,b) ((a)==(b))
#define SUCCESS 1
#define UNSUCCESS 0
#define NULLKEY -1 /*哈希表无元素时值为-1*/
typedef int ElemType;
int length;
typedef struct
{
ElemType *elem; /* 数据元素存储基址，动态分配数组 */
int count; /* 当前数据元素个数 */
}HashTable;
void InitHashTable(HashTable *H)
{ /* 操作结果: 构造一个长度为length的哈希表,length为全局变量 */
int i;
(*H).count=0; /* 当前元素个数为0 */
(*H).elem=(ElemType*)malloc(length*sizeof(ElemType));
if(!(*H).elem)
exit(0); /* 存储分配失败 */
for(i=0;i<length;i++)
(*H).elem[i]=NULLKEY; /* 未填记录的标志 */
}
unsigned Hash(ElemType K)
{ /* 一个简单的哈希函数*/
return 3*K % length;
}
void collision(int *p) /*线性探测再散列 */
{ /* 开放定址法处理冲突 */
(*p) = ((*p) +1) % length;
}
int SearchHash(HashTable H,ElemType K,int *p,int *c)
{ /* 在开放定址哈希表H中查找关键码为K的元素,若查找成功,以p指示待查数据 */
/* 元素在表中位置,并返回SUCCESS;否则,以p指示插入位置,并返回UNSUCCESS */
/* c用以计冲突次数，其初值置零，供建表插入时参考。算法9.17 */
*p=Hash(K); /* 求得哈希地址 */
while(H.elem[*p]!=NULLKEY&&!EQ(K,H.elem[*p]))
{ /* 该位置中填有记录,并且关键字不相等 */
(*c)++;
if(*c<length)
collision(p); /* 求得下一探查地址p */
else
break;
}
if(EQ(K,H.elem[*p] ))
return SUCCESS; /* 查找成功，p返回待查数据元素位置 */
else
return UNSUCCESS; /* 查找不成功(H.elem[p].key==NULLKEY)，p返回的是插入位置 */
}
int InsertHash(HashTable *H,ElemType e)
{ /* 查找不成功时插入数据元素e到开放定址哈希表H中，并返回查找长度 */
int c,p;
c=0;
if(SearchHash(*H,e,&p,&c)) /* 表中已有与e有相同关键字的元素 */
printf("哈希表中已有元素%d。\n",e);
else{ /* 插入e */
(*H).elem[p]=e;
++(*H).count;
}
return c+1; /*查找长度为冲突次数加1*/
}
void TraverseHash(HashTable H)
{ /* 按哈希地址的顺序打印哈希表，无元素位置用X表示 */
int i;
for(i=0;i<length;i++)
if(H.elem[i]==NULLKEY) /* 有数据 */
printf("X ");
else
printf("%d ",H.elem[i]);
printf("\n");
}
main()
{
float i=0,j=0;
ElemType e;
HashTable H;
//printf("Input Table length:");
scanf("%d",&length);
InitHashTable(&H);
//printf("Input key words sequence, -1 conclusion input：");
scanf("%d",&e);
while(e!=-1)
{
j ++; /*j记录输入元素个数*/
i = i + InsertHash(&H,e); /*i记录查找长度的和*/
scanf("%d",&e);
}
TraverseHash(H);
printf("Average search length=%f\n",i/j);
}
解析：Hash函数是将将关键字 K 映射到哈希表的一个位置，比如代码中使用固定乘数 3，目的是扩大关键字的差异，减少冲突。取模运算是保证返回值在 [0, length-1] 范围内，符合哈希表下标要求。collision函数是用来处理哈希冲突，当哈希冲突发生时，线性探测会依次检查下一个位置，直到找到空槽或遍历整个表。
DAMO开发者矩阵，由阿里巴巴达摩院和中国互联网协会联合发起，致力于探讨最前沿的技术趋势与应用成果，搭建高质量的交流与分享平台，推动技术创新与产业应用链接，围绕“人工智能与新型计算”构建开放共享的开发者生态。
更多推荐
32
0- 0
已为社区贡献3条内容
所有评论(0)