利用链表进行问题的解决

利用链表实现:
假如学校的DNS镜像服务器内存里有2亿条左右域名记录，每条域名信息里记录了3个东西“域名、IP地址、资源(比如www、ftp之类)”，该镜像服务器每天根据权威域名服务器下发的变动表(假如以文件形式下发)做一次更新。现在我们要来做这个事情，实现这个DNS镜像服务器核心算法的设计，做到高效的域名解析和域名数据更新。

为了实现高效的域名解析和更新操作，可以使用哈希表和链表结合的方式存储域名信息。
具体实现如下：
1.定义一个域名信息结构体DNSnode，包括域名、IP地址、资源。

typedef struct DNSnode{
    char domain[256];
    char ip[16];
    char resource[32];
    struct DNSnode *next;
}DNSnode;
2.使用哈希表存储每个域名信息的指针。为了减少哈希冲突，可以采用链地址法解决冲突。定义一个DNS缓存结构体DNSCache，包括哈希表大小、哈希表数组指针、每个哈希槽的链表头指针。

#define HASH_SIZE 100000
typedef struct DNSCache{
    int size;
    DNSnode **hashtable;
    DNSnode *head[HASH_SIZE];
}DNSCache;

其中，size表示哈希表大小，hashtable表示哈希表数组指针，head数组表示每个哈希槽的链表头指针。
3.实现哈希函数，根据域名将其映射到哈希表中的一个槽中。

int hash(char *domain){
    int hash = 0;
    int len = strlen(domain);
    for(int i = 0; i < len; i++){
        hash = (hash << 5) + hash + domain[i];
    }
    return hash % HASH_SIZE;
}

实现插入、查找、删除操作。
插入操作：

void insertDNS(DNSCache *cache, char *domain, char *ip, char *resource){
    int key = hash(domain);
    DNSnode *temp = cache->head[key];
    while(temp != NULL){
        if(strcmp(temp->domain, domain) == 0){
            strcpy(temp->ip, ip);
            strcpy(temp->resource, resource);
            return;
        }
        temp = temp->next;
    }
    DNSnode *new_node = (DNSnode*)malloc(sizeof(DNSnode));
    strcpy(new_node->domain, domain);
    strcpy(new_node->ip, ip);
    strcpy(new_node->resource, resource);
    new_node->next = cache->head[key];
    cache->head[key] = new_node;
    cache->size++;
}

查找：

DNSnode *findDNS(DNSCache *cache, char *domain){
    int key = hash(domain);
    DNSnode *temp = cache->head[key];
    while(temp != NULL){
        if(strcmp(temp->domain, domain) == 0){
            return temp;
        }
        temp = temp->next;
    }
    return NULL;
}

删除操作：

void deleteDNS(DNSCache *cache, char *domain){
    int key = hash(domain);
    DNSnode *temp = cache->head[key];
    DNSnode *prev = NULL;
    while(temp != NULL){
        if(strcmp(temp->domain, domain) == 0){
            if(prev == NULL){
                cache->head[key] = temp->next;
            }else{
                prev->next = temp->next;
            }
            free(temp);
            cache->size--;
            return;
        }
        prev = temp;
        temp = temp->next;
    }
}

5.实现域名解析和更新操作。
域名解析操作，根据传入的域名在哈希表中查找对应的域名信息，如果找到则返回IP地址，否则返回NULL。

char *resolveDNS(DNSCache *cache, char *domain){
    DNSnode *node = findDNS(cache, domain);
    if(node == NULL){
        return NULL;
    }else{
        return node->ip;
    }
}

域名更新操作，根据传入的变动表文件名，解析其中每一条域名记录，对于已有的域名进行更新操作，对于新增的域名进行插入操作，对于已被删除的域名进行删除操作。

void updateDNS(DNSCache *cache, char *filename){
    FILE *fp = fopen(filename, "r");
    if(fp == NULL){
        printf("Error: file not found!\n");
        return;
    }

    char line[512];
    while(fgets(line, 512, fp) != NULL){
        char domain[256];
        char ip[16];
        char resource[32];
        int index = 0;
        int i = 0;
        while(line[index] != ' '){
            domain[i++] = line[index++];
        }
        domain[i] = '\0';
        index++;
        i = 0;
        while(line[index] != ' '){
            ip[i++] = line[index++];
        }
        ip[i] = '\0';
        index++;
        i = 0;
        while(line[index] != '\n'){
            resource[i++] = line[index++];
        }
        resource[i] = '\0';
        DNSnode *node = findDNS(cache, domain);
        if(node == NULL){
            // insert new node
            insertDNS(cache, domain, ip, resource);
        }else{
            // update existing node
            strcpy(node->ip, ip);
            strcpy(node->resource, resource);
        }
    }

    fclose(fp);

    // delete non-existing nodes
    for(int i = 0; i < HASH_SIZE; i++){
        DNSnode *temp = cache->head[i];
        while(temp != NULL){
            char *ip = resolveDNS(cache, temp->domain);
            if(ip == NULL){
                deleteDNS(cache, temp->domain);
            }
            temp = temp->next;
        }
    }
}