# 实验六

答：本人现在优化前缀树（字典树）还是不会（高程时写时复制的字典树也没会）

贴几个类似实验的网页吧，谁要是会可以指点一下我。

{% embed url="<https://clv-iclucia.github.io/2024/01/18/UCAS-Network-Lab-8-ip-lookup/>" %}

{% embed url="<https://blog.csdn.net/JJ1018RR/article/details/117090461>" %}

***

5.10更新

在尝试4bit前缀树无果后，经助教指点返回优化2Bits树，最后在概率情况下极限通过了16000us的测试。

当然4Bit理论效率应该是稳过的，但是我没有那个脑子写对。

所以如果你像我一样没有脑子，就死命优化2bit树吧。

oj的前两个测试只是测试是否正确的，只要你测试为1就行。

第三个测试既有2倍的测试还有<16000us的检测。

关于这个<16000其实比较tricky,你不能看你的机子如果你的机子的硬件配置很差会跑很慢，一切以oj平台为准，能过就是过了。

还有一个比较作弊的方式，如果你的2倍效率做不到的话，你让你的普通前缀树usleep一会。（）

所以我就写一点自己不是很聪明的想法吧，感觉没啥参考价值。

最后，ai是写不对的，别想了，靠自己写。

1.普通前缀树

建树很简单，一位位往下造就行，注意子网掩码即可。然后查就子网掩码一位位移往下搜就行，搜到最深。

```
typedef struct TrieNode {
    uint32_t net;           // 网络地址
    int prefix_len;         // 前缀长度
    int port;               // 端口号
    struct TrieNode* left;   // 0分支
    struct TrieNode* right;  // 1分支
} TrieNode;
/ IP地址转换函数
static uint32_t ip_str_to_uint(const char* ip_str) {
    unsigned a, b, c, d;
    sscanf(ip_str, "%u.%u.%u.%u", &a, &b, &c, &d);
    return (a << 24) | (b << 16) | (c << 8) | d;
}
static TrieNode* create_node(uint32_t net, int prefix_len, int port) {
    TrieNode* node = (TrieNode*)calloc(1, sizeof(TrieNode));
    node->net = net;
    node->prefix_len = prefix_len;
    node->port = port;
    return node;
}

// return an array of ip represented by an unsigned integer, size is TEST_SIZE
uint32_t* read_test_data(const char* lookup_file){
    FILE* fp = fopen(lookup_file, "r");
    uint32_t* ips = malloc(TEST_SIZE * sizeof(uint32_t));
    char line[20];
    
    for (int i=0; fgets(line, sizeof(line), fp); i++) {
        ips[i] = ip_str_to_uint(line);
    }
    fclose(fp);
    return ips;
   // fprintf(stderr,"TODO: %s\n",__func__);
    //return NULL;
}

```

造树和遍历树就是二叉树的思维＋子网掩码，很容易。

2.2bit树

2bit树是个四叉树，所以有00，01,10,11四个节点可能性。因此树节点该这样：

```
typedef struct tree_advance_t{
    int port;
    int line;
    struct tree_advance_t *child[16];
}  tree_advance;

```

create\_advance\_node和普通树类似，注意奇偶会不会省一位即可。

建树需要两位两位地匹配，00,01,10,11四种情况四叉树，我这里全分类讨论硬匹配建树的。

找树也是，两位一点一点硬找。

但是我觉得这个东西没法优化了（以我的能力），所以建议大家再加上一点路径压缩或者剪枝。

最后，4位的16叉树本人大脑过载没法写出高效的代码。


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://blueroaring-njus-organization.gitbook.io/njucs_25spring_network-exp_additional/shi-yan-liu.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.