本文目录一览：
- 1、请问这道二分查找的平均长度为什么不能用公式直接算出?
- 2、2．C语言程序设计
- 3、数据结构 哈希表，C语言解答
- 4、如何计算哈希表的ASL
- 5、线性表---解决冲突(c语言)
- 6、为什么高度为2,总结点数是3的二叉排序树，查找成功的平均查找长度为: ASL = (1*1 + 2*2) / 3
请问这道二分查找的平均长度为什么不能用公式直接算出?
设关键字个数为n，在各关键字等概率查找的前提下，
1、顺序查找的平均查找长度asl=(n+1)/2，
2、在n趋于无穷大时，折半查找的asl=((n+1)log2(n+1))/n
-
1，当n大于50时，asl约等于log2(n+1)-1
3、设分块查找中将长为
n
的表分成均等的
b
个块，每块
s
个元素，则
b
=
(n
/
s)上取整，如果索引表中采用顺序查找，则asl=(b+1)/2+(s+1)/2；如果索引表中采用折半查找，则asl=(s+1)/2+log2(b+1)-1
2．C语言程序设计
#include "stdio.h"
#include "string.h"
#include "stdlib.h"
#define NULL 0
#define TRUE 1
#define FALSE 0
typedef struct bitnode{
int data;
int sl; /*查找长度*/
struct bitnode *lchild,*rchild;
}bitnode,*bitree;
/*二杈排序树的查找*/
int searchbst(bitree t,int key,bitree f,bitree *p){
/*在以t为根的树中查找关键字为key的结点,查找成功返回TRUE,
则指针p指向该结点,否则指向上次访问的最后一个结点,返回FALSE,
指针f指向t的双亲,初始调用值为NULL*/
if(!t){
*p=f;
return FALSE;
}
else if(key==t-data){
*p=t;
return TRUE;
}
else if(keyt-data){
return searchbst(t-lchild,key,t,p);
}
else{
return searchbst(t-rchild,key,t,p);
}
}
/*二杈排序树的插入*/
int insertbst(bitree *t,int e,int *count){
/*当t中不存在结点为e的时候插入e并返回TRUE,否则返回FALSE*/
bitree p,s;
if(!searchbst(*t,e,NULL,p)){
s=(bitree)malloc(sizeof(bitnode));
s-data=e;
s-lchild=s-rchild=NULL;
if(!p){
*t=s;
(*t)-sl=1;
(*count)++; /*结点个数加一*/
}
else if(ep-data){
s-sl=p-sl+1;
p-lchild=s;
(*count)++;
}
else{
s-sl=p-sl+1;
p-rchild=s;
(*count)++;
}
return TRUE;
}
else return FALSE;
}
/*二杈排序树的结点删除查找*/
int delschbst(bitree *t,int key,int *count){
if(!t) return FALSE;
else{
if(key==(*t)-data)
return deletebst(t,count);
else if(key(*t)-data)
return delschbst(((*t)-lchild),key,count);
else if(key(*t)-data)
return delschbst(((*t)-rchild),key,count);
}
}
/*二杈排序树的结点删除函数*/
int deletebst(bitree *p,int *count){
bitree q,s;
/*右子树为空只需重接它的左子树*/
if(!(*p)-rchild){
q=*p;
*p=(*p)-lchild;
(*count)--;/*结点个数减一*/
free(q);
}
/*右子树为空只需重接它的左子树*/
else if(!(*p)-lchild){
q=*p;
*p=(*p)-rchild;
(*count)--;
free(q);
}
/*左右子树均非空*/
else{
q=*p;
s=(*p)-lchild;
while(s-rchild){
q=s;
s=s-rchild;
}
(*p)-data=s-data;
if(q!=(*p)) q-rchild=s-lchild;
else q-lchild=s-lchild;
(*count)--;
free(s);
}
return TRUE;
}
/*先序递归遍历*/
int preorder(bitree t,int ssl){
if(t){
ssl+=t-sl;/*总查找长度*/
printf("%d:%d ",t-data,t-sl);
ssl=preorder(t-lchild,ssl);
ssl=preorder(t-rchild,ssl);
}
return ssl;
}
main(){
int i,e;
int ssl=0,count=0;
float asl=0.0;
bitree t=NULL;
for(i=0;i12;i++){
scanf("%d",e);
insertbst(t,e,count);
}
printf("preorder:\n");
ssl=preorder(t,0);
asl=ssl/1.0/count;
printf("\nASL=%d/%d=%f",ssl,count,asl);
printf("\n");
/*删除后遍历*/
printf("The key of delete:");
scanf("%d",e);
delschbst(t,e,count);
ssl=preorder(t,0);
asl=ssl/1.0/count;
printf("\nASL=%d/%d=%f",ssl,count,asl);
printf("\n");
system("pause");
}
数据结构 哈希表，C语言解答
#include stdio.h
#includemalloc.h
#includestring.h
//#include
#define HASH_LEN 50 //哈希表的长度
#define M 47
#define NAME_NO 30 //人名的个数
typedef struct NAME
{
char *py; //名字的拼音
int k; //拼音所对应的整数
}NAME;
NAME NameList[HASH_LEN];
typedef struct hterm //哈希表
{
char *py; //名字的拼音
int k; //拼音所对应的整数
int si; //查找长度
}HASH;
HASH HashList[HASH_LEN];
/*-----------------------姓名（结构体数组）初始化---------------------------------*/
void InitNameList()
{ int i;
char *f;
int r,s0;
NameList[0].py="chenghongxiu";
NameList[1].py="yuanhao";
NameList[2].py="yangyang";
NameList[3].py="zhanghen";
NameList[4].py="chenghongxiu";
NameList[5].py="xiaokai";
NameList[6].py="liupeng";
NameList[7].py="shenyonghai";
NameList[8].py="chengdaoquan";
NameList[9].py="ludaoqing";
NameList[10].py="gongyunxiang";
NameList[11].py="sunzhenxing";
NameList[12].py="sunrongfei";
NameList[13].py="sunminglong";
NameList[14].py="zhanghao";
NameList[15].py="tianmiao";
NameList[16].py="yaojianzhong";
NameList[17].py="yaojianqing";
NameList[18].py="yaojianhua";
NameList[19].py="yaohaifeng";
NameList[20].py="chengyanhao";
NameList[21].py="yaoqiufeng";
NameList[22].py="qianpengcheng";
NameList[23].py="yaohaifeng";
NameList[24].py="bianyan";
NameList[25].py="linglei";
NameList[26].py="fuzhonghui";
NameList[27].py="huanhaiyan";
NameList[28].py="liudianqin";
NameList[29].py="wangbinnian";
for (i=0;iNAME_NO;i++)// *求出各个姓名的拼音所对应的整数
{
s0=0;
f=NameList[i].py;
for (r=0;*(f+r) != '\0';r++) //方法：将字符串的各个字符所对应的ASCII码相加，所得的整数做为哈希表的关键字
s0=*(f+r)+s0;
NameList[i].k=s0;
}
}
/*-----------------------建立哈希表---------------------------------*/
void CreateHashList()
{int i;
for ( i=0; iHASH_LEN;i++)//哈希表的初始化
{
HashList[i].py="";
HashList[i].k=0;
HashList[i].si=0;
}
for (i=0; iNAME_NO;)
{
int sum=0;
int adr=(NameList[i].k) % M; //哈希函数
int d=adr;
if(HashList[adr].si==0) //如果不冲突
{
HashList[adr].k=NameList[i].k;
HashList[adr].py=NameList[i].py;
HashList[adr].si=1;
}
else //冲突
{
do
{
d=(d+((NameList[i].k))%10+1)%M; //伪散列
sum=sum+1; //查找次数加1
}while (HashList[d].k!=0);
HashList[d].k=NameList[i].k;
HashList[d].py=NameList[i].py;
HashList[d].si=sum+1;
}i++;
}
}
/*-------------------------------------查找------------------------------------*/
void FindList()
{ int r;
char name[20]={0};
int s0=0;
int sum=1;
int adr;
int d;
printf("\n\n请输入姓名的拼音: "); //输入姓名
scanf("%s",name);
for ( r=0;r20;r++) //求出姓名的拼音所对应的整数(关键字)
s0+=name[r];
adr=s0 % M; //使用哈希函数
d=adr;
if(HashList[adr].k==s0) //分3种情况进行判断
printf("\n姓名:%s 关键字:%d 查找长度为: 1",HashList[d].py,s0);
else if (HashList[adr].k==0)
printf("无该记录!");
else
{
int g=0;
do
{
d=(d+s0%10+1)%M; //伪散列
sum=sum+1;
if (HashList[d].k==0)
{
printf("无记录! ");
g=1;
}
if (HashList[d].k==s0)
{
printf("\n姓名:%s 关键字:%d 查找长度为:%d",HashList[d].py,s0,sum);
g=1;
}
}while(g==0);
}
}
/*--------------------------------显示哈希表----------------------------*/
void Display()
{int i;
float average=0;
printf("\n\n地址\t关键字\t\t搜索长度\tH(key)\t\t拼音 \n"); //显示的格式
for( i=0; i15; i++)
{
printf("%d ",i);
printf("\t%d ",HashList[i].k);
printf("\t\t%d ",HashList[i].si);
printf("\t\t%d ",(HashList[i].k)%M);
printf("\t %s ",HashList[i].py);
printf("\n");
}
// printf("按任意键继续显示...\n"); //由于数据比较多，所以分屏显示（以便在Win9x／DOS下能看到所有的数据）
// getch();
for( i=15; i30; i++)
{
printf("%d ",i);
printf("\t%d ",HashList[i].k);
printf("\t\t%d ",HashList[i].si);
printf("\t\t%d ",(HashList[i].k)%M);
printf("\t %s ",HashList[i].py);
printf("\n");
}
// printf("按任意键继续显示...\n");
// getch();
for( i=30; i40; i++)
{
printf("%d ",i);
printf("\t%d ",HashList[i].k);
printf("\t\t%d ",HashList[i].si);
printf("\t\t%d ",(HashList[i].k)%M);
printf("\t %s ",HashList[i].py);
printf("\n");
}
//printf("按任意键继续显示...\n");
//getch();
for( i=40; i50; i++)
{
printf("%d ",i);
printf("\t%d ",HashList[i].k);
printf("\t\t%d ",HashList[i].si);
printf("\t\t%d ",(HashList[i].k)%M);
printf("\t %s ",HashList[i].py);
printf("\n");
}
for (i=0;iHASH_LEN;i++)
{average+=HashList[i].si;
average/=NAME_NO;
printf("\n\n平均查找长度：ASL(%d)=%f \n\n",NAME_NO,average);
}
}
/*--------------------------------主函数----------------------------*/
void main()
{
/* ::SetConsoleTitle("哈希表操作"); //Windows API函数,设置控制台窗口的标题
HANDLE hCon = ::GetStdHandle(STD_OUTPUT_HANDLE); //获得标准输出设备的句柄
::SetConsoleTextAttribute(hCon, 10|0); //设置文本颜色
*/
printf("\n------------------------哈希表的建立和查找----------------------");
InitNameList();
CreateHashList ();
while(1)
{ char ch1;
printf("\n\n");
printf(" 1. 显示哈希表\n");
printf(" 2. 查找\n");
printf(" 3. 退出\n");
err:
scanf("%c",ch1);
if (ch1=='1')
Display();
else if (ch1=='2')
FindList();
else if (ch1=='3')
return;
else
{
printf("\n请输入正确的选择!");
goto err;
}
}
}
如何计算哈希表的ASL
哈希表的建立计算：
key： 0 1 2 3 4 5 6 7 8 9 10 11 12
55 68 11 79 14 27 23 84 19 20 10 1
ASL=(1+1+1+1+1+1+3+2+2+6+11)/12
做此类题应注意哈希冲突函数怎么构建，此题采用线性探测法，即如果产生冲突方法为H+1一直到没有冲突为止。哈希表的建立；是依照key依次算对应的哈希码。
线性表---解决冲突(c语言)
开放地址法
1.冲突处理方法一---开放地址法
当发生地址冲突后，求解下一个地址用：
ND
=(
D+di）%m i=1,2,…,k(k=
m-1)
其中:
m为哈希表长度,di为增量序列。增量序列的不同取法，又构成不同的开放地址法。
(1)线性探测再散列
D
=
H(key);
ND
=
(D+di)%m; di取1,2,3,……,m-1
线性探测再散列处理冲突的基本思想:若数据元素在存储地址D发生冲突，则放到存储地址（D＋1）%m；若又发生冲突则放到存储地址（D＋2）%m；若再发生冲突则放到存储地址（D＋3）%m；……；直到碰到第一个为空的存储地址（D＋i）%m，则将数据元素存放在该存储空间。
(2)二次探测再散列
D
=
H(key);
ND
=
(D+di)%m; di取1*1,-1*1,2*2,-2*2,……,K*K,-K*K
(K≤m/2)
(3)双散列法
首先使用第一个散列函数H1(key)及逆行那个散列，一旦发生冲突，则使用第二个函数H2(key)计算改项到达下一个存储地址的增量，其取值p和key有关，范围在1和m之间，并且与m互质的正整数。
D
=
H1(key);
p
=
H2(key);
ND
=
(D+p)%m;
值得提醒的是，对利用开放地址法查了冲突所产生的哈希表中删除一个元素，不能简单地直接删除，因为这样将截断其它具有相同哈希地址的元素的查找地址，所以应设定一个特殊的标志以表明该元素已被删除。
不知道对你是否有用
为什么高度为2,总结点数是3的二叉排序树，查找成功的平均查找长度为: ASL = (1*1 + 2*2) / 3
1) 二叉排序树,高度为2,总结点数n是3,如下:
36
/ \
24 52
要成功查找结点36,需要比较一次,就是与36作比较,所以其查找长度是1
要成功查找结点24,需要比较两次,分别与36和24作比较,所以其查找长度是2
要成功查找结点52,需要比较两次,分别与36和52作比较,所以其查找长度是2
该二叉排序树查找成功的总长度是 1*1+2*2
因为总结点数是3,所以,查找成功的平均查找长度为: ASL = (1*1 + 2*2) / 3 = 5/3
也可以用公式: ASL = [(n+1)/n] * log2(n+1) - 1 = [(3+1)/3] * log2(3+1) - 1 = 5/3
2) 二叉排序树,高度为3,总结点数n是7,如下:
36
/ \
24 52
/ \ / \
10 30 41 90
要成功查找结点36,需要比较一次,就是与36作比较,所以其查找长度是1
要成功查找结点24,需要比较两次,分别与36和24作比较,所以其查找长度是2
要成功查找结点52,需要比较两次,分别与36和52作比较,所以其查找长度是2
要成功查找结点10,需要比较三次,分别与36,24,10作比较,所以其查找长度是3
同样,要成功查找点30,41,90,这每个结点都是需要比较三次,所以每个结点的查找长度都是3
该二叉排序树查找成功的总长度是 1*1+2*2+3*4
因为总结点数是7,所以,查找成功的平均查找长度为: ASL = (1*1+2*2+3*4) / 7 = 17/7
也可以用公式: ASL = [(n+1)/n] * log2(n+1) - 1 = [(7+1)/7] * log2(7+1) - 1 = 17/7
3) 二叉排序树,高度为4,总结点数n是15,如下:
36
/ \
24 52
/ \ / \
10 30 41 90
/ \ / \ / \ / \
8 12 28 31 38 42 61 91
逐个结点计数,查找成功的平均查找长度为:
ASL = (1*1 + 2*2 + 3*4 + 4*8) / 15 = 49/15
也可以用公式: ASL = [(n+1)/n] * log2(n+1) - 1 = [(15+1)/15] * log2(15+1) - 1 = 49/15
