利用哈希技术统计C源程序关键字出现频度_利用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