热门标签
热门文章
- 1什么是RPC？有哪些RPC框架？
- 2R9000P2021版拯救者 装ubuntu系统相关问题（WiFi、蓝牙、亮度调节，驱动安装）记录总结_r9000p重装蓝牙
- 3解决Spring Boot应用中的内存优化问题
- 4搭建hadoop+spark完全分布式集群环境
- 5软件测试除了做好功能测试自动化测试之外，如何在职位上获得提升？_测试工程师除了功能测试还能做什么
- 6BERT参数计算，RBT3模型结构
- 7Android Studio运行项目_android studio怎么运行当前项目csdn
- 8量化机器人能否实现多资产交易？
- 9深度学习环境配置_ubuntu18及以上_nvcc fatal : failed to preprocess host compiler pr
- 10数据库逻辑设计 完全函数依赖、部分函数依赖、传递函数依赖、码、候选码、主码、范式_数据库部分函数依赖
当前位置: article > 正文
利用哈希技术统计C源程序关键字出现频度_利用hash技术和二分查找技术统计某个c源程序
作者：IT小白 | 2024-07-15 15:47:51
赞
踩
利用hash技术和二分查找技术统计某个c源程序
一：题目
1、题目内容：
利用Hash技术统计某个C源程序中的关键字出现的频度
2、基本要求：
扫描一个C源程序，用Hash表存储该程序中出现的关键字，并统计该程序中的关键字出现的频度。用线性探测法解决Hash冲突。设Hash函数为：
Hash(key)[(key的第一个字母序号)*100+(key的最后一个字母序号)] MOD 41
二：总体设计（流程图）
三、详细设计
1、定义结构体
typedef struct mykey {
char data[M];//关键字
int con = 0;//冲突次数
int num = -1;//出现次数，-1表示没有
}mykey;
- 1
- 2
- 3
- 4
- 5
2、初始化
void init(); //初始化结构体数组
void create(); //建立关键词Hash表
void menu(); //显示操作菜单
//用户进入程序时自动初始化，更好的提供服务
- 1
- 2
- 3
- 4
3、读取文件（统计关键字）
void choose(int n); //选择读取的文件
void readFile(); //读取文件
void test(int n); //检测某文件
//用户能自己选择文件，选择完后进行统计，完成之后进行提示
- 1
- 2
- 3
- 4
4、打印hash表
void myprint(); //打印Hash表，输出到test.txt
- 1
打印完整hash表，存储到test.txt里面，保持数据有序，一目了然
5、查找关键字
void find();
//用户可以自行查找关键字，查看其频率和冲突次数
- 1
- 2
6、其他
bool isChar(char a);
//判断字符是否是字母
void isKey(char str[]);
//判断是否是关键字
- 1
- 2
- 3
- 4
四：全部代码（运行环境：vs2019或VC6.0、dev5.40）
vc6.0、dev5.40
#include<stdio.h> #include<stdlib.h> #include<string.h> #include <fstream> #define N 41 //37个关键字 char key[37][10] = { "auto","break","bool","case","char","const","continue","default", "do","double","else","enum","extern","float","false","for","goto","if","int","inline", "long","register","return","restrict","short","signed","sizeof","static","struct", "switch","typedef","true","union","unsigned","void","volatile","while" }; typedef struct mykey { char data[10]; int con ;//冲突次数 int num ;//出现次数，-1表示没有 }mykey; mykey my[N]; //hash表 int sum = 0, m,i; //总的关键字数，m用于选项 FILE* fi; //所要读取文件指针 FILE* fo; //所要写的文件指针 void init(); //初始化结构体数组 bool isChar(char a); //判断字符是否是字母 void isKey(char str[]); //判断是否是关键字 void myprint(); //打印Hash表，输出到test.txt void test(int n); //检测某文件 void choose(int n); //选择读取的文件 void readFile(); //读取文件 void find(); //查找某个关键词 void menu(); //显示操作菜单 void create(); //建立关键词Hash表 int main() { create(); menu(); return 0; } void init() {//指针为空，初始化数据 fi = NULL; sum = 0; for (int i = 0; i < N; i++) { if (my[i].num != -1) {//hash表中该位置是否有关键词 my[i].num = 0; } } } bool isChar(char a) { if (a >= 'a' && a <= 'z' || a >= 'A' && a <= 'Z') return true; else return false; } void isKey(char str[]) { int n = strlen(str); int y = (str[0] * 100 + str[n - 1]) % N; int i = 0; do { i++; if (strcmp(my[y].data, str) == 0) {//与hash表中关键词比较是否相同 if(my[y].num==-1) break; sum++;//相同关键词总数加1 my[y].num++;//出现次数加1 break; } else { y = (y + 1) % N; } } while (i <= N); } void find() { char fin[10]; bool flag = false; do { printf("请正确输入要查找的关键词:\n"); scanf("%s", fin); getchar(); for (int i = 0; i < N; i++) { if (strcmp(key[i], fin) == 0) { flag = true; break; } } } while (flag == false); int n = strlen(fin); int y = (fin[0] * 100 + fin[n - 1]) % N; bool isfind = false; int i = 0; do { i++; if (strcmp(my[y].data, fin) == 0) { isfind = true; break; } else { y = (y + 1) % N; } } while (i <= N); if (isfind == false) printf("很遗憾，该hash表内没有此关键词\n"); else printf("hash表位置：%d 关键字：%s 冲突次数：%d 出现次数：%d\n", y, my[y].data, my[y].con, my[y].num); printf("当前操作已完成\n继续查找？（y继续）\n"); if (getchar() == 'y') find(); else{ init(); menu(); } } void myprint() { printf("关键词总数:%d\n", sum); fprintf(fo, "%s %d\n", "关键词总数:", sum); char s1[13] = "hash表位置:"; char s2[7] = "无数据"; char s3[11] = "出现次数:"; char s4[11] = "冲突次数:"; char s5[9] = "关键字:"; for (int i = 0; i < N; i++) { char c[3] = " ";//用于对齐 if (i < 10) strcpy(c, " "); if (my[i].num == -1) { printf("hash表位置:%d%s无数据\n", i, c); fprintf(fo, "%s %d%s %s\n", s1, i, c, s2); } else { printf("hash表位置:%d%s关键字:%s 冲突次数:%d 出现次数:%d\n", i, c, my[i].data, my[i].con, my[i].num); fprintf(fo, "%s %d %s", s1, i, c); fprintf(fo, "%s %s ", s5, my[i].data); fprintf(fo, "%s %d ", s4, my[i].con); fprintf(fo, "%s %d\n", s3, my[i].num); } } fclose(fo);//关闭并保存文件 printf("已打印hash表\n"); printf("你可以做如下操作:\n"); printf("0.退出，1.返回菜单，2.查找某关键词\n"); do { printf("请输入正确的操作编号!\n"); scanf("%d", &m); } while (m < 0 || m>2); switch (m) { case 0: printf("感谢使用!"); exit(0); break; case 1: init(); menu(); break; case 2: find(); break; } } void readFile() { char ch; while (!feof(fi)) { //feof()函数检测文件是否结束 char word[20]; //存储一段连续字母 int i = 0; ch = fgetc(fi); //fgetc()从头取一个字符，读多少字节光标后移多少字节 while (!isChar(ch) && !feof(fi)) //取一个字母 ch = fgetc(fi); while (isChar(ch) && !feof(fi)) { //如果是字母且文件未结束,一次循环读取一段字母 if (i == 10) { while (isChar(ch) && !feof(fi)) { ch = fgetc(fi); } i = 0; break; } else { word[i++] = ch; ch = fgetc(fi); } } word[i] = '\0'; isKey(word); //检测是否为关键字 } } void menu() { system("cls"); printf("利用哈希技术统计C源程序关键字出现频度\n"); printf("你可以选择如下操作:\n"); printf("0.退出，1.测试\n"); do { printf("请输入正确的操作编号!\n"); scanf("%d", &m); } while (m != 0 && m != 1); test(m); } void test(int n) { choose(n); if (fi == NULL) { printf("no file\n"); system("pause"); menu(); } else { readFile(); printf("文件读取成功"); printf("你可以做如下操作：\n"); printf("0.退出，1.打印hash表内容，2.返回菜单，3.查找某关键词\n"); do { printf("请输入正确的操作编号!\n"); scanf("%d", &m); } while (m < 0 || m>3); switch (m) { case 0: printf("感谢使用!"); exit(0); break; case 1: myprint(); break; case 2: init(); menu(); break; case 3: find(); break; } } } void choose(int n) { switch (n) { case 0: printf("感谢使用!"); exit(0); break; case 1: char filename[20]; puts("请输入C文件名："); scanf("%s", filename); fi=fopen(filename, "r"); fo=fopen("test.txt", "w"); break; } } void create() { for (i = 0; i < N; i++) { my[i].con=0; my[i].num=-1; } for (i = 0; i < 37; i++) { int n = strlen(key[i]); int y = (key[i][0] * 100 + key[i][n - 1]) % N; //计算关键词hash值 if (my[y].num == -1) {//若不冲突 my[y].num++; strcpy(my[y].data, key[i]); } else { //冲突 my[y].con++; //冲突加1 for(int j = 0; j < N; j++) { //寻找下一个没有存放关键词的地方 int x = ++y % N; if (my[x].num == -1) { //找到下一个没有存放关键词的地方 my[x].num++; strcpy(my[x].data, key[i]); break; } } } } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
- 111
- 112
- 113
- 114
- 115
- 116
- 117
- 118
- 119
- 120
- 121
- 122
- 123
- 124
- 125
- 126
- 127
- 128
- 129
- 130
- 131
- 132
- 133
- 134
- 135
- 136
- 137
- 138
- 139
- 140
- 141
- 142
- 143
- 144
- 145
- 146
- 147
- 148
- 149
- 150
- 151
- 152
- 153
- 154
- 155
- 156
- 157
- 158
- 159
- 160
- 161
- 162
- 163
- 164
- 165
- 166
- 167
- 168
- 169
- 170
- 171
- 172
- 173
- 174
- 175
- 176
- 177
- 178
- 179
- 180
- 181
- 182
- 183
- 184
- 185
- 186
- 187
- 188
- 189
- 190
- 191
- 192
- 193
- 194
- 195
- 196
- 197
- 198
- 199
- 200
- 201
- 202
- 203
- 204
- 205
- 206
- 207
- 208
- 209
- 210
- 211
- 212
- 213
- 214
- 215
- 216
- 217
- 218
- 219
- 220
- 221
- 222
- 223
- 224
- 225
- 226
- 227
- 228
- 229
- 230
- 231
- 232
- 233
- 234
- 235
- 236
- 237
- 238
- 239
- 240
- 241
- 242
- 243
- 244
- 245
- 246
- 247
- 248
- 249
- 250
- 251
- 252
- 253
- 254
- 255
- 256
- 257
- 258
- 259
- 260
- 261
- 262
- 263
- 264
- 265
- 266
- 267
- 268
- 269
vs2019
#include<stdio.h> #include<stdlib.h> #include<string.h> #include <fstream> #define N 41 //37个关键字(蓝色字体) char key[37][10] = { "auto","break","bool","case","char","const","continue","default", "do","double","else","enum","extern","float","false","for","goto","if","int","inline", "long","register","return","restrict","short","signed","sizeof","static","struct", "switch","typedef","true","union","unsigned","void","volatile","while" }; typedef struct mykey { char data[10]; int con = 0;//冲突次数 int num = -1;//出现次数，-1表示没有 }mykey; mykey my[N]; //hash表 int sum = 0, m; //总的关键字数，m用于选项 FILE* fi; //所要读取文件指针 FILE* fo; //所要写的文件指针 void init(); //初始化结构体数组 bool isChar(char a); //判断字符是否是字母 void isKey(char str[]); //判断是否是关键字 void myprint(); //打印Hash表，输出到test.txt void test(int n); //检测某文件 void choose(int n); //选择读取的文件 void readFile(); //读取文件 void find(); //查找某个关键词 void menu(); //显示操作菜单 void create(); //建立关键词Hash表 int main() { system("color f0"); create(); menu(); return 0; } void init() {//指针为空，初始化数据 fi = NULL; sum = 0; for (int i = 0; i < N; i++) { if (my[i].num != -1) {//hash表中该位置是否有关键词 my[i].num = 0; } } } bool isChar(char a) { if (a >= 'a' && a <= 'z' || a >= 'A' && a <= 'Z') return true; else return false; } void isKey(char str[]) { int n = strlen(str); int y = (str[0] * 100 + str[n - 1]) % N; int i = 0; do { i++; if (strcmp(my[y].data, str) == 0) {//与hash表中关键词比较是否相同 sum++;//相同关键词总数加1 my[y].num++;//出现次数加1 break; } else { y = (y + 1) % N; } } while (i <= N); } void find() { char fin[10]; bool flag = false; do { printf("请正确输入要查找的关键词:\n"); scanf_s("%s", fin, 10); getchar(); for (int i = 0; i < N; i++) { if (strcmp(key[i], fin) == 0) { flag = true; break; } } } while (flag == false); int n = strlen(fin); int y = (fin[0] * 100 + fin[n - 1]) % N; bool isfind = false; int i = 0; do { i++; if (strcmp(my[y].data, fin) == 0) { isfind = true; break; } else { y = (y + 1) % N; } } while (i <= N); if (isfind == false) printf("很遗憾，该hash表内没有此关键词\n"); else printf("hash表位置：%d 关键字：%s 冲突次数：%d 出现次数：%d\n", y, my[y].data, my[y].con, my[y].num); printf("当前操作已完成\n继续查找？（y继续）\n"); if (getchar() == 'y') find(); else { init(); menu(); } } void myprint() { printf("关键词总数:%d\n", sum); fprintf(fo, "%s %d\n", "关键词总数:", sum); char s1[13] = "hash表位置:"; char s2[7] = "无数据"; char s3[11] = "出现次数:"; char s4[11] = "冲突次数:"; char s5[9] = "关键字:"; for (int i = 0; i < N; i++) { char c[3] = " ";//用于对齐 if (i < 10) strcpy_s(c, " "); if (my[i].num == -1) { printf("hash表位置:%d%s无数据\n", i, c); fprintf(fo, "%s %d%s %s\n", s1, i, c, s2); } else { printf("hash表位置:%d%s关键字:%s 冲突次数:%d 出现次数:%d\n", i, c, my[i].data, my[i].con, my[i].num); fprintf(fo, "%s %d %s", s1, i, c); fprintf(fo, "%s %s ", s5, my[i].data); fprintf(fo, "%s %d ", s4, my[i].con); fprintf(fo, "%s %d\n", s3, my[i].num); } } fclose(fo);//关闭并保存文件 printf("已打印hash表\n"); printf("你可以做如下操作:\n"); printf("0.退出，1.返回菜单，2.查找某关键词\n"); do { printf("请输入正确的操作编号!\n"); scanf_s("%d", &m); } while (m < 0 || m>2); switch (m) { case 0: printf("感谢使用!"); exit(0); break; case 1: init(); menu(); break; case 2: find(); break; } } void readFile() { char ch; while (!feof(fi)) { //feof()函数检测文件是否结束 char word[20]; //存储一段连续字母 int i = 0; ch = fgetc(fi); //fgetc()从头取一个字符，读多少字节光标后移多少字节 while (!isChar(ch) && !feof(fi)) //取一个字母 ch = fgetc(fi); while (isChar(ch) && !feof(fi)) { //如果是字母且文件未结束,一次循环读取一段字母 if (i == 10) { while (isChar(ch) && !feof(fi)) { ch = fgetc(fi); } i = 0; break; } else { word[i++] = ch; ch = fgetc(fi); } } word[i] = '\0'; isKey(word); //检测是否为关键字 } } void menu() { system("cls"); init(); printf("利用哈希技术统计C源程序关键字出现频度\n"); printf("你可以选择如下操作:\n"); printf("0.退出，1.测试\n"); do { printf("请输入正确的操作编号!\n"); scanf_s("%d", &m); } while (m != 0 && m != 1); test(m); } void test(int n) { choose(n); if (fi == NULL) { printf("no file\n"); system("pause"); menu(); } else { readFile(); printf("文件读取成功"); printf("你可以做如下操作：\n"); printf("0.退出，1.打印hash表内容，2.返回菜单，3.查找某关键词\n"); do { printf("请输入正确的操作编号!\n"); scanf_s("%d", &m); } while (m < 0 || m>3); switch (m) { case 0: printf("感谢使用!"); exit(0); break; case 1: myprint(); break; case 2: init(); menu(); break; case 3: find(); break; } } } void choose(int n) { switch (n) { case 0: printf("感谢使用!"); exit(0); break; case 1: char filename[20]; puts("请输入C文件名："); scanf_s("%s", filename, 20); fopen_s(&fi, filename, "r"); fopen_s(&fo, "test.txt", "w"); break; } } void create() { for (int i = 0; i < 37; i++) { int n = strlen(key[i]); int y = (key[i][0] * 100 + key[i][n - 1]) % N; //计算关键词hash值 if (my[y].num == -1) {//若不冲突 my[y].num++; strcpy_s(my[y].data, key[i]); } else { //冲突 my[y].con++; //冲突加1 int count = -1, x; while (count++ < N) { //寻找下一个没有存放关键词的地方 x = ++y % N; if (my[x].num == -1) { //找到下一个没有存放关键词的地方 my[x].num++; strcpy_s(my[x].data, key[i]); break; } } } } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
- 111
- 112
- 113
- 114
- 115
- 116
- 117
- 118
- 119
- 120
- 121
- 122
- 123
- 124
- 125
- 126
- 127
- 128
- 129
- 130
- 131
- 132
- 133
- 134
- 135
- 136
- 137
- 138
- 139
- 140
- 141
- 142
- 143
- 144
- 145
- 146
- 147
- 148
- 149
- 150
- 151
- 152
- 153
- 154
- 155
- 156
- 157
- 158
- 159
- 160
- 161
- 162
- 163
- 164
- 165
- 166
- 167
- 168
- 169
- 170
- 171
- 172
- 173
- 174
- 175
- 176
- 177
- 178
- 179
- 180
- 181
- 182
- 183
- 184
- 185
- 186
- 187
- 188
- 189
- 190
- 191
- 192
- 193
- 194
- 195
- 196
- 197
- 198
- 199
- 200
- 201
- 202
- 203
- 204
- 205
- 206
- 207
- 208
- 209
- 210
- 211
- 212
- 213
- 214
- 215
- 216
- 217
- 218
- 219
- 220
- 221
- 222
- 223
- 224
- 225
- 226
- 227
- 228
- 229
- 230
- 231
- 232
- 233
- 234
- 235
- 236
- 237
- 238
- 239
- 240
- 241
- 242
- 243
- 244
- 245
- 246
- 247
- 248
- 249
- 250
- 251
- 252
- 253
- 254
- 255
- 256
- 257
- 258
- 259
- 260
- 261
- 262
- 263
- 264
- 265
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/IT小白/article/detail/830070
推荐阅读
相关标签
