树型结构模拟域名查询系统

基本实现

说明

  • 实现了创建、查询、写文件、读文件、联网查询(不是请求的DNS服务器)
  • 我的开发环境是Linux,所以在Windows上跑的时候需要改一些地方。
  • 修改的第一个地方是,system(“clear”)改为system(“cls”)
  • 第二个就是将联网查询函数用到的库文件更改为windows上的库文件,我看到MSDN上面有文档,但是我是鸽子王,就没去改…MSDN文档
  • 为了避免程序当中存在过多的“幻数”,我将一些数值进行了宏定义。
  • 最后就是,我个人比较喜欢将程序函数分割在一个库文件内,main.c只作为程序入口

可以进行的改进

  • 可以写一个修改ip地址的函数
  • 可以将联网查询到的ip写到文件里面,(但是已经写好的创建函数就需要再次切割,提供接口)
  • 可以在定义的节点结构体中,添加一个ttl(解析有效时间)数据域以及上次查询的时间,以此确定是否联网查询并更新域名ip
  • 是否可以将改程序记录的ip地址写到计算机的hosts文件内
  • 争取不当一个鸽子

创建树

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
/*创建树函数*/
Status CreateTree(CSTree *T)
{

ElemType data[d_length] = {"\0"};
ElemType ip[ip_length];
CSNode *p=NULL,*t,*q=NULL;
Pointer P;
int i=0,j=0,k=0;

while(1)
{
//将辅助指针的内容全部变成\0
memset(P.point,'\0', sizeof(P));
system("clear");
/*windows用户将clear改成cls即可*/
printf("\n\t======| Tips:输入N中断输入操作! |======\n");
printf("\t请输入域名:\n");
scanf("%s",data);
/*中断输入操作*/
if(!strcmp(data,"N")||!strcmp(data,"n"))
break;
printf("\t请输入IP:\n");
scanf("%s",ip);

i=0,j=0,k=0;
ElemType temp[temp_length]={'\0'};
while (data[i]!='\0')
/*域名每一段都用‘.’隔开,所以每次都将获取到的一段存储起来,并用辅助指针pointer存储每一段的节点地址,等到整个域名分段完成后,
从pointer中逆序读出节点地址,完成树的创建*/
{
temp[j++] = data[i++];
/*截取每一段域的值,然后保存到新建的节点,最后用一个辅助指针保存这个节点的指针地址*/
if(data[i]=='0'||data[i]=='\0')
{
p = (CSNode *)malloc(sizeof(CSNode));
strcpy(p->data,temp);
strcpy(p->ip,"NULL");
p->firstchild = p->nextsib = NULL;

P.point[k] = p;
P.last = k;
k++;

for(int n=0;n<temp_length;n++)
temp[n] = '\0';

j = 0;
i++;
}
}

t = *T;
while(P.last>=0)
/*逆序建立一个树(孩子兄弟法),需要将上面过程保存在pointer中的每个节点全部连接起来*/
{
p = P.point[P.last];

if((t->firstchild)==NULL)
{
t->firstchild = p;
t = p;
}
else
{
t = t->firstchild;
while (t!=NULL)
{
q = t;
t = t->nextsib;
}
q->nextsib = p;
t = p;
}
P.last--;
}
strcpy(p->ip,ip);
system("clear");
}
FILE *fp = fopen("data.txt","w");
WriteToFile((*T)->firstchild,fp);
fclose(fp);
return OK;
}

搜索树

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
/*搜索树*/
Status SearchTree(CSTree T)
{
ElemType data[d_length]={'\0'};
char req_ip[ip_length];
CSNode *p,*t;
Pointer P;
int i=0,j=0,k=0;

FILE *fp = fopen("data.txt","r");
ReadFromFile(&(T->firstchild),fp);
fclose(fp);

while (1)
{
memset(P.point,'\0', sizeof(P));
system("clear");
/*windows用户将clear改成cls即可*/
printf("\n\t======| Tips:输入N中断输入操作! |======\n");
printf("\t请输入域名:\n");
scanf("%s",data);
/*中断输入操作*/
if(!strcmp(data,"N")||!strcmp(data,"n"))
break;

i=0,j=0,k=0;
ElemType temp[temp_length]={'\0'};
while (data[i]!='\0')
/*域名每一段都用‘.’隔开,所以每次都将获取到的一段存储起来,并用辅助指针pointer存储每一段的节点地址,等到整个域名分段完成后,
从pointer中逆序读出节点地址,完成树的创建*/
{
temp[j++] = data[i++];
/*截取每一段域的值,然后保存到新建的节点,最后用一个辅助指针保存这个节点的指针地址*/
if(data[i]=='0'||data[i]=='\0')
{
p = (CSNode *)malloc(sizeof(CSNode));
strcpy(p->data,temp);
strcpy(p->ip,"NULL");
p->firstchild = p->nextsib = NULL;

P.point[k] = p;
P.last = k;
k++;

for(int n=0;n<temp_length;n++)
temp[n] = '\0';

j = 0;
i++;
}
}

t = T;
while (P.last>=0)
{
p = P.point[P.last];
t = t->firstchild;
if(!(t->firstchild) && strcmp(p->data,t->data)!=0)
t = t->nextsib;
if(t == NULL)
{
char op;
printf("\n\t本地缓存无此域名的IP!");
printf("\n\t是否联网查询?(Y/N)");
scanf("%s",&op);
if(op=='Y'||op=='y')
{
GetIpFromDNS(data,req_ip);

printf("\n\tThe IP is:%s",req_ip);
break;
}
else if(op=='N'||op=='n')
{
printf("本次请求动作被终止!");
break;
}
else
{
printf("参数输入错误!");
break;
}
}
P.last--;
}
if(t!=NULL)
{
printf("\n\tThe IP is:%s",t->ip);
}

sleep(sleep_time);
printf("\n\n\t按任意键继续...");
getchar();
}
return OK;
}

写文件

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void WriteToFile(CSTree T,FILE *fp)
{
char Ltag = '0',Rtag = '0';
if(T)
{
fputs(T->data,fp);
fputs("\t",fp);
fputs(T->ip,fp);
fputs("\t",fp);
if(T->firstchild!=NULL)
Ltag = '1';
fwrite(&Ltag, sizeof(char),1,fp);
fputs("\t",fp);

if(T->nextsib!=NULL)
Rtag = '1';
fwrite(&Rtag, sizeof(char),1,fp);
fputs("\t",fp);
fputs("\n",fp);

WriteToFile(T->firstchild,fp);
WriteToFile(T->nextsib,fp);
}
}

读文件

1
2
3
4
5
6
7
8
9
10
11
12
13
void ReadFromFile(CSTree *T,FILE *fp)
{
CSTree p;
char Ltag = '0',Rtag = '0';
p = (CSTree)malloc(sizeof(CSNode));
p->firstchild = p->nextsib = NULL;
fscanf(fp,"%s\t%s\t%c\t%c",p->data,p->ip,&Ltag,&Rtag);
*T = p;
if(Ltag == '1')
ReadFromFile(&(*T)->firstchild,fp);
if(Rtag == '1')
ReadFromFile(&(*T)->nextsib,fp);
}

欢迎界面及菜单

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
void Welcome()
{
printf("\n\n\n");
printf("\t\t=======================================================\n");
printf("\t\t* *\n");
printf("\t\t* Welcome to use *\n");
printf("\t\t* *\n");
printf("\t\t* the simple domain inquiry system *\n");
printf("\t\t* *\n");
printf("\t\t=======================================================\n");
}

void Menu()
{
system("clear");
printf("\n\n\n");
printf("\t\t=======================================================\n");
printf("\t\t* *\n");
printf("\t\t* Domain Inquiry System *\n");
printf("\t\t* *\n");
printf("\t\t* [1]域名信息输入 *\n");
printf("\t\t* [2]域名信息查询 *\n");
printf("\t\t* [0]退出 *\n");
printf("\t\t* *\n");
printf("\t\t=======================================================\n");

}

拓展实现

联网获取域名IP

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
void GetIpFromDNS(char *hostname,char *res)
/*int getaddrinfo(const char *node, // e.g. "www.example.com" or IP
const char *service, // e.g. "http" or port number
const struct addrinfo *hints, //指定一些基本值
struct addrinfo **res);//得到链表*/
{
struct addrinfo hints; //<netdb.h>
struct addrinfo *ailist; //<netdb.h>
struct sockaddr_in *sinp;//<sys/types.h>
char buf[INET_ADDRSTRLEN];
char *port = "80";
const char *addr; //记录查到的ip并转换为点分10进制

int isRequest;
hints.ai_family = AF_UNSPEC; /* hint 的限定设置 */
hints.ai_socktype = 0; /* 这里可是设置 socket type . 比如 SOCK——DGRAM */
hints.ai_flags = AI_PASSIVE; /* flags 的标志很多 。常用的有AI_CANONNAME; */
hints.ai_protocol = 0; /* 设置协议 一般为0,默认 */
hints.ai_addrlen = 0; /* 下面不可以设置,为0,或者为NULL */

isRequest = getaddrinfo(hostname,port,&hints,&ailist);
if(isRequest < 0)
{
printf("请求上级DNS服务器失败!");
return;
}

/*处理返回的信息*/
sinp = (struct sockaddr_in *)ailist->ai_addr;
addr = inet_ntop(AF_INET, &sinp->sin_addr, buf, INET_ADDRSTRLEN);
strcpy(res,addr);
}

完整程序代码

说明

如果是windows用户,请将代码中的system(“clear”)之语句更改为cls!

main.c

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
#include "functions.h"

int main() {
int op;
CSTree T;
T = (CSNode *)malloc(sizeof(CSNode));
T->firstchild = T->nextsib = NULL;

Welcome();
sleep(sleep_time);

while (1)
{
Menu();
printf("请输入功能选项:");
scanf("%d",&op);
system("clear");

switch(op)
{
case 1:
CreateTree(&T);
break;
case 2:
SearchTree(T);
break;
case 0:
exit(0);
default:
printf("非法的输入!请重新输入!");
break;
}
}
}

functions.h

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
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
//
// Created by tangger on 19-11-4.
//

#ifndef WORK_FUNCTIONS_H
#define WORK_FUNCTIONS_H
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <netdb.h>
#include <sys/socket.h>
#include <sys/types.h>
#include <unistd.h>
#include <netinet/in.h>
#include <arpa/inet.h>

#define ElemType char
#define d_length 50
#define ip_length 20
#define p_length 30
#define temp_length 20
#define sleep_time 2

/*node declaration*/
typedef struct CSNode{
ElemType data[d_length];
ElemType ip[ip_length];
struct CSNode * firstchild,*nextsib;
}CSNode,*CSTree;

typedef struct Pointer{
CSNode *point[p_length];
int last;
}Pointer;

typedef enum {
OK = 0,ERROR = 1
}Status;

Status CreateTree(CSTree *T);
Status SearchTree(CSTree T);
void WriteToFile(CSTree T,FILE *fp);
void ReadFromFile(CSTree *T,FILE *fp);
void GetIpFromDNS(char *hostname,char *res);
void Welcome();
void Menu();

/*创建树函数*/
Status CreateTree(CSTree *T)
{

ElemType data[d_length] = {"\0"};
ElemType ip[ip_length];
CSNode *p=NULL,*t,*q=NULL;
Pointer P;
int i=0,j=0,k=0;

while(1)
{
//将辅助指针的内容全部变成\0
memset(P.point,'\0', sizeof(P));
system("clear");
/*windows用户将clear改成cls即可*/
printf("\n\t======| Tips:输入N中断输入操作! |======\n");
printf("\t请输入域名:\n");
scanf("%s",data);
/*中断输入操作*/
if(!strcmp(data,"N")||!strcmp(data,"n"))
break;
printf("\t请输入IP:\n");
scanf("%s",ip);

i=0,j=0,k=0;
ElemType temp[temp_length]={'\0'};
while (data[i]!='\0')
/*域名每一段都用‘.’隔开,所以每次都将获取到的一段存储起来,并用辅助指针pointer存储每一段的节点地址,等到整个域名分段完成后,
从pointer中逆序读出节点地址,完成树的创建*/
{
temp[j++] = data[i++];
/*截取每一段域的值,然后保存到新建的节点,最后用一个辅助指针保存这个节点的指针地址*/
if(data[i]=='0'||data[i]=='\0')
{
p = (CSNode *)malloc(sizeof(CSNode));
strcpy(p->data,temp);
strcpy(p->ip,"NULL");
p->firstchild = p->nextsib = NULL;

P.point[k] = p;
P.last = k;
k++;

for(int n=0;n<temp_length;n++)
temp[n] = '\0';

j = 0;
i++;
}
}

t = *T;
while(P.last>=0)
/*逆序建立一个树(孩子兄弟法),需要将上面过程保存在pointer中的每个节点全部连接起来*/
{
p = P.point[P.last];

if((t->firstchild)==NULL)
{
t->firstchild = p;
t = p;
}
else
{
t = t->firstchild;
while (t!=NULL)
{
q = t;
t = t->nextsib;
}
q->nextsib = p;
t = p;
}
P.last--;
}
strcpy(p->ip,ip);
system("clear");
}
FILE *fp = fopen("data.txt","w");
WriteToFile((*T)->firstchild,fp);
fclose(fp);
return OK;
}

/*搜索树*/
Status SearchTree(CSTree T)
{
ElemType data[d_length]={'\0'};
char req_ip[ip_length];
CSNode *p,*t;
Pointer P;
int i=0,j=0,k=0;

FILE *fp = fopen("data.txt","r");
ReadFromFile(&(T->firstchild),fp);
fclose(fp);

while (1)
{
memset(P.point,'\0', sizeof(P));
system("clear");
/*windows用户将clear改成cls即可*/
printf("\n\t======| Tips:输入N中断输入操作! |======\n");
printf("\t请输入域名:\n");
scanf("%s",data);
/*中断输入操作*/
if(!strcmp(data,"N")||!strcmp(data,"n"))
break;

i=0,j=0,k=0;
ElemType temp[temp_length]={'\0'};
while (data[i]!='\0')
/*域名每一段都用‘.’隔开,所以每次都将获取到的一段存储起来,并用辅助指针pointer存储每一段的节点地址,等到整个域名分段完成后,
从pointer中逆序读出节点地址,完成树的创建*/
{
temp[j++] = data[i++];
/*截取每一段域的值,然后保存到新建的节点,最后用一个辅助指针保存这个节点的指针地址*/
if(data[i]=='0'||data[i]=='\0')
{
p = (CSNode *)malloc(sizeof(CSNode));
strcpy(p->data,temp);
strcpy(p->ip,"NULL");
p->firstchild = p->nextsib = NULL;

P.point[k] = p;
P.last = k;
k++;

for(int n=0;n<temp_length;n++)
temp[n] = '\0';

j = 0;
i++;
}
}

t = T;
while (P.last>=0)
{
p = P.point[P.last];
t = t->firstchild;
if(!(t->firstchild) && strcmp(p->data,t->data)!=0)
t = t->nextsib;
if(t == NULL)
{
char op;
printf("\n\t本地缓存无此域名的IP!");
printf("\n\t是否联网查询?(Y/N)");
scanf("%s",&op);
if(op=='Y'||op=='y')
{
GetIpFromDNS(data,req_ip);

printf("\n\tThe IP is:%s",req_ip);
break;
}
else if(op=='N'||op=='n')
{
printf("本次请求动作被终止!");
break;
}
else
{
printf("参数输入错误!");
break;
}
}
P.last--;
}
if(t!=NULL)
{
printf("\n\tThe IP is:%s",t->ip);
}

sleep(sleep_time);
printf("\n\n\t按任意键继续...");
getchar();
}
return OK;
}

void WriteToFile(CSTree T,FILE *fp)
{
char Ltag = '0',Rtag = '0';
if(T)
{
fputs(T->data,fp);
fputs("\t",fp);
fputs(T->ip,fp);
fputs("\t",fp);
if(T->firstchild!=NULL)
Ltag = '1';
fwrite(&Ltag, sizeof(char),1,fp);
fputs("\t",fp);

if(T->nextsib!=NULL)
Rtag = '1';
fwrite(&Rtag, sizeof(char),1,fp);
fputs("\t",fp);
fputs("\n",fp);

WriteToFile(T->firstchild,fp);
WriteToFile(T->nextsib,fp);
}
}

void ReadFromFile(CSTree *T,FILE *fp)
{
CSTree p;
char Ltag = '0',Rtag = '0';
p = (CSTree)malloc(sizeof(CSNode));
p->firstchild = p->nextsib = NULL;
fscanf(fp,"%s\t%s\t%c\t%c",p->data,p->ip,&Ltag,&Rtag);
*T = p;
if(Ltag == '1')
ReadFromFile(&(*T)->firstchild,fp);
if(Rtag == '1')
ReadFromFile(&(*T)->nextsib,fp);
}

void GetIpFromDNS(char *hostname,char *res)
/*int getaddrinfo(const char *node, // e.g. "www.example.com" or IP
const char *service, // e.g. "http" or port number
const struct addrinfo *hints, //指定一些基本值
struct addrinfo **res);//得到链表*/
{
struct addrinfo hints; //<netdb.h>
struct addrinfo *ailist; //<netdb.h>
struct sockaddr_in *sinp;//<sys/types.h>
char buf[INET_ADDRSTRLEN];
char *port = "80";
const char *addr; //记录查到的ip并转换为点分10进制

int isRequest;
hints.ai_family = AF_UNSPEC; /* hint 的限定设置 */
hints.ai_socktype = 0; /* 这里可是设置 socket type . 比如 SOCK——DGRAM */
hints.ai_flags = AI_PASSIVE; /* flags 的标志很多 。常用的有AI_CANONNAME; */
hints.ai_protocol = 0; /* 设置协议 一般为0,默认 */
hints.ai_addrlen = 0; /* 下面不可以设置,为0,或者为NULL */

isRequest = getaddrinfo(hostname,port,&hints,&ailist);
if(isRequest < 0)
{
printf("请求上级DNS服务器失败!");
return;
}

/*处理返回的信息*/
sinp = (struct sockaddr_in *)ailist->ai_addr;
addr = inet_ntop(AF_INET, &sinp->sin_addr, buf, INET_ADDRSTRLEN);
strcpy(res,addr);
}

void Welcome()
{
printf("\n\n\n");
printf("\t\t=======================================================\n");
printf("\t\t* *\n");
printf("\t\t* Welcome to use *\n");
printf("\t\t* *\n");
printf("\t\t* the simple domain inquiry system *\n");
printf("\t\t* *\n");
printf("\t\t=======================================================\n");
}

void Menu()
{
system("clear");
printf("\n\n\n");
printf("\t\t=======================================================\n");
printf("\t\t* *\n");
printf("\t\t* Domain Inquiry System *\n");
printf("\t\t* *\n");
printf("\t\t* [1]域名信息输入 *\n");
printf("\t\t* [2]域名信息查询 *\n");
printf("\t\t* [0]退出 *\n");
printf("\t\t* *\n");
printf("\t\t=======================================================\n");

}
#endif //WORK_FUNCTIONS_H