建哈希表

鼯鼠

假设有1000个值小于10000的正整数，用构造散列表的方法将1000个正整数按由小到大的次序放入表中。（负载因子a=1）试写出你的排序算法。
（显然散列中的数应被散列函数从小到大排列，换句话说，散列函数应是一个单调递增的函数。很容易想到f（x）=[x/10]+1，其中[x]表示不大于x的最大整数。此函数的值域为{x | x∈[1，1000]且x∈N+}，编程是为了方便起见，将函数改为f（x）=[x/10]以便操作，值域为{x | x∈[0，999]且x∈N+}。冲突采用拉链法来解决，每个链表中用插入排序法排序，最后按顺序输出。时间复杂度O（n）。）
#include <stdio.h>
#include <stdlib.h>

typedef struct node{
int number;
struct node *next;
}Node;

int main(void){
int i,first=1;
Node *hash[1000]={NULL};
for(i=0;i<1000;i++){
int inp,fx;
scanf("%d",&inp);
fx=inp/10;
if(hash[fx]==NULL){
hash[fx]=(Node *)malloc(sizeof(Node));
hash[fx]->number=inp;
hash[fx]->next=NULL;
}else if(hash[fx]->number>inp){
Node *temp;
temp=(Node *)malloc(sizeof(Node));
temp->number=inp;
temp->next=hash[fx];
hash[fx]=temp;
}else{
Node *temp,*insert;
for(temp=hash[fx]; temp->next!=NULL;temp=temp->next)
if(temp->next->number>inp)
break;
insert=(Node *)malloc(sizeof(Node));
insert->number=inp;
insert->next=temp->next;
temp->next=insert;
}
}

for(i=1;i<1000;i++){
Node *temp;
for(temp=hash;temp!=NULL;temp=temp->next)
if(first){
printf("%d",temp->number);
first=0;
}else
printf(" %d",temp->number);
}
return 0;
}

[此贴子已经被作者于2006-6-12 11:33:39编辑过]

鼯鼠

哈希表的一个应用

作者: 姚建飞

#include <stdio.h>
#include <conio.h>
#include <ctype.h>
#define L 50 /*定义哈希表长*/
#define M 47 /*定义p值*/
#define N 30 /*定义名单长*/
char z[22];
struct old{char *name;char *py;int k;};
struct old oldlist[L];/*原始表*/
struct hterm
{ char *name;char *py;
int k;int si;
};
struct hterm hlist[L];/*哈希表*/
int i,adr,sum,d;
char ch1;
float average;
/**********************************/
void chash()
{for (i=0;i<L;i++)
{hlist.name="";
hlist.py="";
hlist.k=0;
hlist.si=0;
};
for (i=0;i<N;i++)
{ sum=0;
adr=(oldlist.k)%M;
d=adr;
if(hlist[adr].si==0)
{hlist[adr].k=oldlist.k;
hlist[adr].name=oldlist.name;
hlist[adr].py=oldlist.py;
hlist[adr].si=1;
}
else
{do
{d=(d+((oldlist.k))%10+1)%M;/*伪随机*/
sum=sum+1;
}
while (hlist[d].k!=0);
hlist[d].k=oldlist.k;
hlist[d].name=oldlist.name;
hlist[d].py=oldlist.py;
hlist[d].si=sum+1;
}
}
}

/***************************************/
void findhlist()
{ int s0;char r,g;
clrscr();/*清屏*/
for (r=0;r<20;r++){z[r]=0;};
gotoxy(1,1);printf("查找：copyright by 姚建飞 2003.6");
gotoxy(5,10);printf("请拼音后回车！");
gotoxy(5,12);scanf("%s",z);
s0=0;
for (r=0;r<20;r++){s0=z[r]+s0;};
gotoxy(5,13); printf("%d",s0);
/*for (i=0;i<L;i++)*/
sum=1;
adr=s0%M;
d=adr;
if(hlist[adr].k==s0)
{
gotoxy(18,18);printf(" ");
gotoxy(18,18);printf("%s",hlist[d].name);
gotoxy(18,19);printf("%s",hlist[d].py);
gotoxy(18,20);
printf("搜索 %d 次",sum);
getch();
}
else
{if (hlist[adr].k==0)
{gotoxy (18,18);
printf("无记录! ");
getch();
}
else
{g=0;
for (i=0;g==0;i++)
{d=(d+s0%10+1)%M; /*伪随机*/
sum=sum+1;
if (hlist[d].k==0)
{gotoxy (18,18);
printf("无记录! ");
g=1;getch();
};
gotoxy(18,18);
printf("%s",hlist[d].name);
gotoxy(18,19);
printf("%s",hlist[d].py);
gotoxy(18,20);
printf("搜索 %d 次",sum);
getch();
if (hlist[d].k==s0)
{ g=1;
gotoxy(18,21);
printf("搜索 %d 次成功!",sum);
getch();
};
};

};

};

}

/***************************************/
void inp() /*输入表*/
{
char *f;
int r,s0;

oldlist[0].name="桂芳芳";oldlist[0].py="guifanfan";
oldlist[1].name="姚建飞";oldlist[1].py="yaojianfei";
oldlist[2].name="杨扬";oldlist[2].py="yangyang";
oldlist[3].name="朱玉环";oldlist[3].py="zhuyuhuang";
oldlist[5].name="陈曦";oldlist[5].py="chenxi";
oldlist[6].name="张雷";oldlist[6].py="zhanglei";
oldlist[7].name="盛永海";oldlist[7].py="shenyonghai";
oldlist[8].name="陈道全";oldlist[8].py="chengdaoquan";
oldlist[9].name="陆道清";oldlist[9].py="ludaoqing";
oldlist[10].name="龚云祥";oldlist[10].py="gongyunxiang";
oldlist[11].name="孙振兴";oldlist[11].py="sunzhenxing";
oldlist[12].name="孙容飞";oldlist[12].py="sunrongfei";
oldlist[13].name="孙明龙";oldlist[13].py="sunminglong";
oldlist[14].name="张浩";oldlist[14].py="zhanghao";
oldlist[15].name="田苗";oldlist[15].py="tianmiao";
oldlist[16].name="姚建中";oldlist[16].py="yaojianzhong";
oldlist[17].name="姚建清";oldlist[17].py="yaojianqing";
oldlist[18].name="姚建华";oldlist[18].py="yaojianhua";
oldlist[19].name="张海峰";oldlist[19].py="yaohaifeng";
oldlist[20].name="陈言号";oldlist[20].py="chengyanhao";
oldlist[21].name="姚秋锋";oldlist[21].py="yaoqiufeng";
oldlist[22].name="钱鹏程";oldlist[22].py="qianpengcheng";
oldlist[23].name="姚海峰";oldlist[23].py="yaohaifeng";
oldlist[24].name="卞艳";oldlist[24].py="bianyan";
oldlist[25].name="凌蕾";oldlist[25].py="linglei";
oldlist[26].name="李伟";oldlist[26].py="liwei";
oldlist[27].name="黄海燕";oldlist[27].py="huanhaiyan";
oldlist[28].name="刘殿琴";oldlist[28].py="liudianqin";
oldlist[29].name="李云";oldlist[29].py="liyun";

/*
请在此输入数据,同时修改程序开头的 M　L N

*/
for (i=0;i<N;i++)
{
s0=0;
f=oldlist.py;

for (r=0;*(f+r) != '\0';r++){s0=*(f+r)+s0;};

oldlist.k=s0;

};

}

/****************************************/
void dhash() /*显示哈希表*/
{ char LON=17;
clrscr();
if (LON>L){LON=L;};
gotoxy(1,1);printf("哈希表：copyright by 姚建飞 2003.6");
gotoxy(1,2);printf("地址:");
for(i=0;i<LON;i++)
{gotoxy(1,i+3);
printf("%-3d",i);
};
gotoxy(9,2);printf("关键字:");
for(i=0;i<LON;i++)
{gotoxy(10,i+3);
printf("%-6d",hlist.k);
};
gotoxy(19,2);printf("姓名:");
for(i=0;i<LON;i++)
{gotoxy(19,3+i);
printf("%s",hlist.name);
};
gotoxy(28,2);printf("拼音:");
for(i=0;i<LON;i++)
{gotoxy(28,i+3);
printf("%s",hlist.py);
};
gotoxy(40,2);printf("搜索长度:");
for(i=0;i<LON;i++)
{gotoxy(43,i+3);
printf("%2d",hlist.si);
};
gotoxy(53,2);printf("H(key):");
for(i=0;i<LON;i++)
{gotoxy(53,i+3);
printf("%2d",(hlist.k)%M);
};
average=0;
for (i=0;i<L;i++)
{average=average+hlist.si;};
average=average/N;
gotoxy(10,23);
printf("平均搜索长度：ASL(%d)=%f",N,average);

gotoxy(20,24);
printf("任意键下一屏!");
ch1=getch();

if (L>15)
{
clrscr();
if (LON>L-15){LON=L-15;};
gotoxy(1,1);printf("哈希表：copyright by 姚建飞 2003.6");
gotoxy(1,2);printf("地址:");
for(i=0;i<LON;i++)
{gotoxy(1,i+3);
printf("%-3d",i+15);
};
gotoxy(9,2);printf("关键字:");
for(i=0;i<LON;i++)
{gotoxy(10,i+3);
printf("%-6d",hlist[i+15].k);
};
gotoxy(19,2);printf("姓名:");
for(i=0;i<LON;i++)
{gotoxy(19,3+i);
printf("%s",hlist[i+15].name);
};
gotoxy(28,2);printf("拼音:");
for(i=0;i<LON;i++)
{gotoxy(28,i+3);
printf("%s",hlist[i+15].py);
};
gotoxy(40,2);printf("搜索长度:");
for(i=0;i<LON;i++)
{gotoxy(43,i+3);
printf("%2d",hlist[i+15].si);
};
gotoxy(53,2);printf("H(key):");
for(i=0;i<LON;i++)
{gotoxy(53,i+3);
printf("%2d",(hlist[i+15].k)%M);
};
average=0;
for (i=0;i<L;i++)
{average=average+hlist.si;};
average=average/N;
gotoxy(10,23);
printf("平均搜索长度：ASL(%d)=%f",N,average);

gotoxy(20,24);
printf("任意键下一屏! ");
ch1=getch();
};
if (L>30)
{
clrscr();
if (LON>L-30){LON=L-30;};
gotoxy(1,1);printf("哈希表：copyright by 姚建飞 2003.6");
gotoxy(1,2);printf("地址:");
for(i=0;i<LON;i++)
{gotoxy(1,i+3);
printf("%-3d",i+30);
};
gotoxy(9,2);printf("关键字:");
for(i=0;i<LON;i++)
{gotoxy(10,i+3);
printf("%-6d",hlist[i+30].k);
};
gotoxy(19,2);printf("姓名:");
for(i=0;i<LON;i++)
{gotoxy(19,3+i);
printf("%s",hlist[i+30].name);
};
gotoxy(28,2);printf("拼音:");
for(i=0;i<LON;i++)
{gotoxy(28,i+3);
printf("%s",hlist[i+30].py);
};
gotoxy(40,2);printf("搜索长度:");
for(i=0;i<LON;i++)
{gotoxy(43,i+3);
printf("%2d",hlist[i+30].si);
};
gotoxy(53,2);printf("H(key):");
for(i=0;i<LON;i++)
{gotoxy(53,i+3);
printf("%2d",(hlist[i+30].k)%M);
};
average=0;
for (i=0;i<L;i++)
{average=average+hlist.si;};
average=average/N;
gotoxy(10,23);
printf("平均搜索长度：ASL(%d)=%f",N,average);

gotoxy(20,24);
printf("任意键下一屏! ");
ch1=getch();
};
if (L>45)
{
clrscr();
if (LON>L-45){LON=L-45;};
gotoxy(1,1);printf("哈希表：copyright by 姚建飞 2003.6");
gotoxy(1,2);printf("地址:");
for(i=0;i<LON;i++)
{gotoxy(1,i+3);
printf("%-3d",i+45);
};
gotoxy(9,2);printf("关键字:");
for(i=0;i<LON;i++)
{gotoxy(10,i+3);
printf("%-6d",hlist[i+45].k);
};
gotoxy(19,2);printf("姓名:");
for(i=0;i<LON;i++)
{gotoxy(19,3+i);
printf("%s",hlist[i+45].name);
};
gotoxy(28,2);printf("拼音:");
for(i=0;i<LON;i++)
{gotoxy(28,i+3);
printf("%s",hlist[i+45].py);
};
gotoxy(40,2);printf("搜索长度:");
for(i=0;i<LON;i++)
{gotoxy(43,i+3);
printf("%2d",hlist[i+45].si);
};
gotoxy(53,2);printf("H(key):");
for(i=0;i<LON;i++)
{gotoxy(53,i+3);
printf("%2d",(hlist[i+45].k)%M);
};
average=0;
for (i=0;i<L;i++)
{average=average+hlist.si;};
average=average/N;
gotoxy(10,23);
printf("平均搜索长度：ASL(%d)=%f",N,average);

gotoxy(20,24);
printf("任意键返回! ");
ch1=getch();
};

}
/**************************************/
void main()
{inp(); /*输入原表*/
chash ();/*建哈希表*/
a: clrscr();
gotoxy(21,2);
textcolor(GREEN);
cprintf("欢迎使用本程序------------编者:姚建飞");
printf("\n");
gotoxy(22, 4);
textcolor(GREEN);
cprintf(" 1. 显示哈希表");
printf("\n");
gotoxy(22, 6);
textcolor(GREEN);
cprintf(" 2. 查找");
printf("\n");
gotoxy(22, 8);
textcolor(GREEN);
cprintf(" x. 退出");
printf("\n");
gotoxy(22, 12);
cprintf(" 请输入选择: ");
printf("\n");
gotoxy(24,14);
ch1=getch();
if (ch1==0x78){ textcolor(GREEN);
cprintf("谢谢使用本程序,你已经退出本程序!");printf("\n"); exit();};/*"x":退出*/
if (ch1==0x31){dhash();};/*表的属性*/
if (ch1==0x32){ findhlist();};/*查找*/
goto a;

}