数据结构 查找算法
查找 实验1内容:给出在一个无序
表
关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf
A中采取顺序查找算法查找值为x的元素的算法。
# include “iostream.h”
# include “iomanip.h”
Int search( int A[], int x , int n) {
int i =1;
while (i
=n)
return -1;
else
return i ;
}
Viod main()
{
Int a[]={2,5,56,10,12,15,8,19,25,32},n,d,i;
Printf(“A数组”\n”下标”);
For (i=0;i<10;i++)
Printf(“%3d”,i);
For (i=0;i<10;i++)
Printf(“%3d”,a[i]);
Printf(“\n输入值:”);
Scanf(“%d”,&d);
N=search(a,d,10)
If (n>=0)
Printf(“A[n]\n”,d);
else
Printf(“未找到\n”);
}
实验2:使用哈希函数H(K)=3KMOD11,并采用链地址法处理冲突。试对KEY={22,41,53,46,30,13,01,67}构造哈希表,求等概率下ASL,并设计构造哈希表算法。
******自己做:(使用哈希函数H(K)=3KMOD11,并采用开放地址法处理冲突,所求下一个
地址函数d1=h(k);d=(d+((7k mod 10)+1)%11 (i=2,3….)。试在0~10的算列空间对 ii-1
KEY={22,41,53,46,30,13,01,67}构造哈希表,求等概率下ASL,并设计构造哈希表算法。)
# include “iostream.h”
# include “iomanip.h”
# include “malloc.h”
# define M 11
# define N 8
Typedef struct node
{ int key;
Struct node *next;
}hashnode;
Void chash() //创建hash
{
int x[]={22,41,53,46,30,13,1,67},I,j};
Hashnode *p;
For (i=0;ikey=x[i];
j=(3*x[i])%m;
p->next=ht[j].next; //将P节点插入到ht[j]之后
ht[j] .next=p;
}
}
Void dhash() //删除hash
{
int s=0,s1,i,j;
Hashnode *p;
Printf(“输出哈希表\n”);
For (i=0;ikey”, p->key);
P= p->next;
}
S+=s1;
Printf(”\n”);
}
Printf(“ASL:”,s*1.0/n\n); }
Void main()
{chash();dhansh();}
p=(hashnode*)malloc(sizeof(hashnode));
p->key=x[i];
j=(3*x[i])%m;
p->next=ht[j].next; //将P节点插入到ht[j]之后
ht[j] .next=p;
}
}
实验3:使用哈希函数H(K)=3KMOD11,并采用链地址法处理冲突。设计一个算法删除一
个指定的元素。
Int delnode()
{
Hashnode *p , *q ;
Int s,i;
Printf(“删除元素:”,p);
Scanf(“%d”,&s);
I=(3*s)%M;
P=ht[i].next;q=p;
While (p!=null&&p->key!=s)
{
Printf(“p->key:”, p->key);
Q=p;
P=p->next;
}
If (p!=null&&p==q) //p为第一个节点
{
Ht[i].next=p->next;
Free(p);
Return 1;
}
Else if (p!=null) //p不为其他节点
{
q->next=p->next;
Free(p);
Return 1;
}
Else
{
Pintf(“元素没有找到。\n”)
}
}
Void main()
{
Int n;
Chash();
N=delnode();
If (n==1)
Dhash();
}