IT博客汇
  • 首页
  • 精华
  • 技术
  • 设计
  • 资讯
  • 扯淡
  • 权利声明
    • 登录 注册

    [原]实现哈希表

    yincheng01发表于 2015-05-27 04:36:56
    love 0
    
    1. #include
    2. #include
    3. #include
    5. using namespace std;
    7. #define HASH_LEN 50 //哈希表的长度
    8. #define M 47 //随机数
    9. int NAME_NO=34; //城市名的个数
    11. typedef struct
    12. {
    13. char *py; //名字的拼音
    14. int k; //拼音所对应的整数
    15. }NAME;
    17. NAME NameList[HASH_LEN]; //全局变量NAME
    19. typedef struct //哈希表
    20. {
    21. char *py; //名字的拼音
    22. int k; //拼音所对应的整数
    23. int si; //查找长度
    24. }HASH;
    26. HASH HashList[HASH_LEN]; //全局变量HASH
    28. void InitNameList() //姓名（结构体数组）初始化
    29. {
    30. char *f;
    31. int r,s0,i;
    32. NameList[0].py="harbin";
    33. NameList[1].py="shijiazhuang";
    34. NameList[2].py="lanzhou";
    35. NameList[3].py="kunming";
    36. NameList[4].py="chengdu";
    37. NameList[5].py="changchun";
    38. NameList[6].py="shenyang";
    39. NameList[7].py="xining";
    40. NameList[8].py="xian";
    41. NameList[9].py="zhengzhou";
    42. NameList[10].py="jinan";
    43. NameList[11].py="taiyuan";
    44. NameList[12].py="hefei";
    45. NameList[13].py="wuhan";
    46. NameList[14].py="changsha";
    47. NameList[15].py="nanjing";
    48. NameList[16].py="guiyang";
    49. NameList[17].py="nanning";
    50. NameList[18].py="hangzhou";
    51. NameList[19].py="nanchang";
    52. NameList[20].py="guangzhou";
    53. NameList[21].py="fuzhou";
    54. NameList[22].py="taipei";
    55. NameList[23].py="haikou";
    56. NameList[24].py="huhhot";
    57. NameList[25].py="yinchuan";
    58. NameList[26].py="urumqi";
    59. NameList[27].py="lahsa";
    60. NameList[28].py="macau";
    61. NameList[29].py="beijing";
    62. NameList[30].py="shanghai";
    63. NameList[31].py="hongkong";
    64. NameList[32].py="tianjin";
    65. NameList[33].py="chongqing";
    66. for (i=0;i
    67. {
    68. s0=0;
    69. f=NameList[i].py;
    70. for (r=0;*(f+r)!='\0';r++)
    71. /* 方法：将字符串的各个字符所对应的ASCII码相加，所得的整数做为哈希表的关键字*/
    72. s0=*(f+r)+s0;
    73. NameList[i].k=s0;
    74. }
    75. }
    77. void CreateHashList() //建立哈希表
    78. {
    79. int i;
    80. for (i=0; i
    81. {
    82. HashList[i].py="";
    83. HashList[i].k=0;
    84. HashList[i].si=0;
    85. }
    86. for (i=0;i
    87. {
    88. int sum=0;
    89. int adr=(NameList[i].k)%M; //哈希函数
    90. int d=adr;
    91. if(HashList[adr].si==0) //如果不冲突
    92. {
    93. HashList[adr].k=NameList[i].k;
    94. HashList[adr].py=NameList[i].py;
    95. HashList[adr].si=1;
    96. }
    97. else //冲突
    98. {
    99. do
    100. {
    101. d=(d+NameList[i].k%10+1)%M; //伪随机探测再散列法处理冲突
    102. sum=sum+1; //查找次数加1
    103. }while (HashList[d].k!=0);
    104. HashList[d].k=NameList[i].k;
    105. HashList[d].py=NameList[i].py;
    106. HashList[d].si=sum+1;
    107. }
    108. }
    109. }
    111. int FindList() //查找
    113. {
    115. char name[20]={0};
    116. int s0=0,r,sum=1,adr,d;
    117. printf("\n请输入城市名称:");
    118. scanf("%s",name);
    119. for (r=0;r<20;r++) //求出姓名的拼音所对应的整数(关键字)
    120. s0+=name[r];
    121. adr=s0%M; //使用哈希函数
    122. d=adr;
    123. if(HashList[adr].k==s0) //分3种情况进行判断
    124. {
    125. printf("\n名称:%s 关键字:%d 查找长度为: 1",HashList[d].py,s0);
    126. cout<
    127. return 0;
    128. }
    129. else if (HashList[adr].k==0)
    130. {
    131. printf("无此记录!");
    132. cout<
    133. return 1;
    134. }
    135. else
    136. {
    137. int g=0;
    138. do
    139. {
    140. d=(d+s0%10+1)%M; //伪随机探测再散列法处理冲突
    141. sum=sum+1;
    142. if (HashList[d].k==0)
    143. {
    144. printf("无此记录! ");
    145. cout<
    146. g=1;
    147. return 1;
    148. }
    149. if (HashList[d].k==s0)
    150. {
    151. printf("\n名称:%s 关键字:%d 查找长度为:%d",HashList[d].py,s0,sum);
    152. cout<
    153. g=1;
    154. return 0;
    155. }
    156. }while(g==0);
    157. }
    158. }
    160. void Display() // 显示哈希表
    161. {
    162. int i;
    163. float average=0;
    164. for(i=0; i
    165. {
    166. if(HashList[i].k%M==0)
    167. HashList[i].py="";
    168. }
    169. printf("\n\n地址\t关键字\t\t搜索长度\tH(key)\t 名称\n"); //显示的格式
    170. for(i=0; i
    171. {
    172. printf("%d ",i);
    173. printf("\t%d ",HashList[i].k);
    174. printf("\t\t%d ",HashList[i].si);
    175. printf("\t\t%d ",HashList[i].k%M);
    176. printf("\t %s ",HashList[i].py);
    177. //cout<<" "<<
    178. printf("\n");
    179. //cout<<<" "<<<" "<<<" "<<<" "<<
    180. }
    181. for (i=0;i
    182. average+=HashList[i].si;
    183. average/=NAME_NO;
    184. printf("\n\n平均查找长度：ASL(%d)=%f \n\n",NAME_NO,average);
    185. }
    187. void DeleteList()
    188. {
    189. char name[20]={0};
    190. int s0=0,r,sum=1,adr,d;
    191. printf("\n请输入城市名称:");
    192. scanf("%s",name);
    193. for (r=0;r<20;r++) //求出姓名的拼音所对应的整数(关键字)
    194. s0+=name[r];
    195. adr=s0%M; //使用哈希函数
    196. d=adr;
    197. if(HashList[adr].k==s0) //分3种情况进行判断
    198. {
    199. printf("\n名称:%s 关键字:%d 查找长度为: 1",HashList[d].py,s0);
    200. cout<
    201. cout<<"删除成功！"<
    202. s0=0;
    203. HashList[d].py=""; //名字的拼音
    204. HashList[d].k=0; //拼音所对应的整数
    205. HashList[d].si=0;
    206. }
    207. else if (HashList[adr].k==0)
    208. printf("无此记录!无法执行删除操作!");
    209. else
    210. {
    211. int g=0;
    212. do
    213. {
    214. d=(d+s0%10+1)%M; //伪随机探测再散列法处理冲突
    215. sum=sum+1;
    216. if (HashList[d].k==0)
    217. {
    218. printf("无此记录!无法执行删除操作!");
    219. g=1;
    220. }
    221. if (HashList[d].k==s0)
    222. {
    223. printf("\n名称:%s 关键字:%d 查找长度为:%d",HashList[d].py,s0,sum);
    224. cout<
    225. cout<<"已删除成功！"<
    226. s0=0;
    227. HashList[d].py=""; //名字的拼音
    228. HashList[d].k=0; //拼音所对应的整数
    229. HashList[d].si=0;
    230. //Display();
    231. g=1;
    232. }
    233. }while(g==0);
    234. }
    235. }
    237. void EnterList()
    238. {
    239. /*char name[20]={0};
    240. int s0=0,r,sum=1,adr,d,h;
    241. printf("\n请输入姓名的拼音:");
    242. scanf("%s",name);
    243. for (r=0;r<20;r++) //求出姓名的拼音所对应的整数(关键字)
    244. s0+=name[r];*/
    245. char st[20];
    246. char *xin;
    247. xin=st;
    248. int s0=0,r,sum=1,adr,d,h;
    249. printf("\n请输入城市名称的拼音:");
    250. cin>>xin;
    251. //cout<<
    252. for (r=0;*(xin+r)!='\0';r++)
    253. {
    254. /* 方法：将字符串的各个字符所对应的ASCII码相加，所得的整数做为哈希表的关键字*/
    255. s0=(int)(*(xin+r))+s0;
    256. }
    257. //cout<<
    258. adr=s0%M; //使用哈希函数
    259. d=adr;
    260. if(HashList[adr].k==s0) //分3种情况进行判断
    261. {
    262. printf("\n名称:%s 关键字:%d 查找长度为: 1",HashList[d].py,s0);
    263. cout<
    264. cout<<"已存在于表中，无需插入！"<
    265. }
    266. else if (HashList[d].k==0)
    267. {
    268. printf("插入成功！");
    269. HashList[d].py=xin;
    270. HashList[d].k=s0;
    271. HashList[d].si=1;
    272. h=1;
    273. cout<
    274. }
    275. else
    276. {
    277. int g=0,h=0;
    278. do
    279. {
    280. d=(d+s0%10+1)%M; //伪随机探测再散列法处理冲突
    281. sum=sum+1;
    282. if (HashList[d].k==0)
    283. {
    284. printf("插入成功！");
    285. HashList[d].py=xin;
    286. HashList[d].k=s0;
    287. HashList[d].si=sum;
    288. h=1;
    289. cout<
    290. g=1;
    291. }
    292. if (HashList[d].k==s0)
    293. {
    294. printf("\n名称:%s 关键字:%d 查找长度为:%d",HashList[d].py,s0,sum);
    295. cout<
    296. cout<<"已存在于表中，无需插入！"<
    297. g=1;
    298. }
    299. }while(g==0);
    300. }
    301. if(h==0)
    302. return;
    303. else
    304. {
    305. NAME_NO++;
    306. NameList[NAME_NO-1].py=xin;
    307. int sum=0;
    308. int adr=(NameList[NAME_NO-1].k)%M; //哈希函数
    309. int d=adr;
    310. if(HashList[adr].si==0) //如果不冲突
    311. {
    312. HashList[adr].k=NameList[NAME_NO-1].k;
    313. HashList[adr].py=NameList[NAME_NO-1].py;
    314. HashList[adr].si=1;
    315. }
    316. else //冲突
    317. {
    318. do
    319. {
    320. d=(d+NameList[NAME_NO-1].k%10+1)%M; //伪随机探测再散列法处理冲突
    321. sum=sum+1; //查找次数加1
    322. }while (HashList[d].k!=0);
    323. HashList[d].k=NameList[NAME_NO-1].k;
    324. HashList[d].py=NameList[NAME_NO-1].py;
    325. HashList[d].si=sum+1;
    326. }
    327. }
    328. }
    331. void main()
    333. {
    334. char ch1;
    335. printf("\n 哈希表\n");
    336. printf(" *-------------------------------------------*\n");
    337. printf(" | D. 显示哈希表 |\n");
    338. printf(" | F. 查找 |\n");
    339. printf(" | S. 删除 |\n");
    340. printf(" | E. 插入 |\n");
    341. printf(" | Q. 退出 |\n");
    342. printf(" *-------------------------------------------*\n");
    343. InitNameList();
    344. CreateHashList ();
    345. while(1)
    346. {
    347. printf("\n Option-:");
    348. fflush(stdin);
    349. ch1=getchar();
    350. if (ch1=='D'||ch1=='d')
    351. Display();
    352. else if (ch1=='F'||ch1=='f')
    353. FindList();
    354. else if (ch1=='S'||ch1=='s')
    355. DeleteList();
    356. else if (ch1=='E'||ch1=='e')
    357. EnterList();
    358. else if (ch1=='Q'||ch1=='q')
    359. return;
    360. else
    361. {
    362. printf("\n请输入正确的选择!");
    363. }
    364. }
    365. }


沪ICP备19023445号-2号
友情链接