/* * Copyright (c)2017,煙臺大學計算機與控制工程學院 * All rights reserved. * 文件名稱：項目2.cbp * 作 者：孫仁圓 * 完成日期：2017年12月27日 * 版 本 號：v1.0 * 問題描述： 已知一個關鍵字序列為if、while、for、case、do、break、else、struct、union、int、double、float、char、long、bool， 共15個字符串，哈希函數H(key)為關鍵字的第一個字母在字母表中的序號，哈希表的表長為26。 （1）若處理沖突的方法采用線性探測法，請設計算法，輸出每個關鍵字對應的H(key)，輸出哈希表，并求成功情況下的平均查找長度。 （2）若處理沖突的方法采用鏈地址法，請設計算法，輸出哈希表，并計算成功情況和不成功情況下的平均查找長度。 * 輸入描述：無 * 程序輸出：測試數據 */ #include <stdio.h> #include <string.h> #define N 15 #define M 26 int H(char *s) {return ((*s-'a'+1)%M); }int main() {char *s[N]= {"if", "while", "for", "case", "do", "break", "else", "struct", "union", "int", "double", "float", "char", "long", "bool"};int i, j, k;char HT[M][10];int Det[M]; //存放探測次數for(i=0; i<M; i++){HT[i][0]='\0';Det[i]=0;}printf("字符串 key\tH(key)\n");printf("------------------------\n");for(i=0; i<N; i++){j=H(s[i]); //求哈希值printf("%s\t\t%d\n", s[i],j);k=0; //探測次數初值while(1){k++; //累加探測次數if(HT[j][0]=='\0') //當不沖突時，直接放到該處{strcpy(HT[j], s[i]);break;}else //沖突時，采用線性探查法求下一個地址{j=(j+1)%M;}}Det[j]=k;}printf("---------------------\n");printf("哈希表\n");printf("位置\t字符串\t探查次數\n");printf("---------------------\n");for(i=0; i<M; i++)printf("%d\t%s\t%d\n", i, HT[i], Det[i]);printf("---------------------\n");k=0;for(i=0; i<M; i++)k+=Det[i];printf("查找成功情況下的平均查找長度 %f\n", 1.0*k/N);return 0; }

#include <stdio.h> #include <string.h> #include <malloc.h> #define N 15 #define M 26 typedef struct node //定義哈希鏈表的節點類型 {char *key;struct node *next; } LNode;typedef struct {LNode *link; } HTType;int H(char *s) //實現哈希函數 {return ((*s-'a'+1)%M); }//構造哈希表 void Hash(char *s[], HTType HT[]) {int i, j;LNode *q;for(i=0; i<M; i++) //哈希表置初值HT[i].link=NULL;for(i=0; i<N; i++) //存儲每一個關鍵字{q=(LNode*)malloc(sizeof(LNode)); //創建新節點q->key = (char*)malloc(sizeof(strlen(s[i])+1));strcpy(q->key, s[i]);q->next=NULL;j=H(s[i]); //求哈希值if(HT[j].link==NULL) //不沖突，直接加入HT[j].link=q;else //沖突時，采用前插法插入{q->next = HT[j].link;HT[j].link=q;}} }//輸出哈希表 void DispHT(HTType HT[]) {int i;LNode *p;printf("哈希表\n");printf("位置\t關鍵字序列\n");printf("---------------------\n");for(i=0; i<M; i++){printf(" %d\t", i);p=HT[i].link;while(p!=NULL){printf("%s ", p->key);p=p->next;}printf("\n");}printf("---------------------\n"); }//求查找成功情況下的平均查找長度 double SearchLength1(char *s[], HTType HT[]) {int i, k, count = 0;LNode *p;for(i=0; i<N; i++){k=0;p=HT[H(s[i])].link;while(p!=NULL){k++; //p!=NULL，進入循環就要做一次查找if(strcmp(p->key, s[i])==0) //若找到，則退出break;p=p->next;}count+=k;}return 1.0*count/N; //成功情況僅有N種 }//求查找不成功情況下的平均查找長度 double SearchLength2(HTType HT[]) {int i, k, count = 0; //count為各種情況下不成功的總次數LNode *p;for(i=0; i<M; i++){k=0;p=HT[i].link;while(p!=NULL){k++;p=p->next;}count+=k;}return 1.0*count/M; //不成功時，在表長為M的每個位置上均可能發生 } int main() {HTType HT[M];char *s[N]= {"if", "while", "for", "case", "do", "break", "else", "struct", "union", "int", "double", "float", "char", "long", "bool"};Hash(s, HT);DispHT(HT);printf("查找成功情況下的平均查找長度 %f\n", SearchLength1(s, HT));printf("查找不成功情況下的平均查找長度 %f\n", SearchLength2(HT));return 0; }

總結

以上是生活随笔為你收集整理的第十四周 项目2 - 用哈希法组织关键字的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。