代码

#include "router.h"
#include <cstddef>

struct Node {//字典树节点，left为0,right为1,full为该节点是否有对应地址的entry
	Node* left = NULL;
	Node* right = NULL;
	bool full = false;
	RoutingTableEntry entry;
};

unsigned reverse(unsigned addr) {
	unsigned char * array = (unsigned char *) &addr;
	unsigned char x = array[0];
	array[0] = array[3];
	array[3] = x;
	x = array[2];
	array[2] = array[1];
	array[1] = x;//调整地址端序	
	return addr;
}
class Tree{
	Node root;
	public: void insertEntry(RoutingTableEntry entry) {
		unsigned addr = entry.addr, length = entry.len;
		addr = reverse(addr);
		Node* current = &root;//从根开始往下走
		for (int i = 1; i <= length; i++) {
			if ((addr >> 32 - i) & 1) {//该位值为1
				if (current->right == NULL)
					current->right = new Node;
				current = current->right;
			}
			else {
				if (current->left == NULL)
					current->left = new Node;
				current = current->left;
			}
		}
		current->full = true;
		current->entry = entry;
	}
	public: void deleteEntry(RoutingTableEntry entry) {		
		unsigned addr = entry.addr, length = entry.len;//精确匹配
		addr = reverse(addr);
		Node* current = &root;
		for (int i = 1; i <= length; i++) {
			if ((addr >> 32 - i) & 1) {//该位值为1
				if (current->right == NULL)
					return;
				current = current->right;
			}
			else {
				if (current->left == NULL) 
					return;
				current = current->left;
			}
		}
		if (!current->full)
			return;
		current->full = false;
	}
	public: RoutingTableEntry* query(unsigned addr) {
		addr = reverse(addr);
		RoutingTableEntry* result = NULL;
		Node * current = &root;
		if (current-> full)
			result = &current->entry;
		for (int i = 1; i <= 32; i++) {
			if ((addr >> 32 - i) & 1) {//该位值为1,向右走
				if (current->right == NULL)
					return result;
				current = current->right;
			}
			else {
				if (current->left == NULL) 
					return result;
				current = current->left;
			}
			if (current->full)
				result = &(current->entry);
		}
		return result;
	}
};
Tree table;
void init (int n, int q, const RoutingTableEntry *a) {
	for (int i = 0; i < n; i++) {
            table.insertEntry(a[i]);
        }
    return;
}
/**
 * @brief 插入/删除一条路由表表项
 * @param insert 如果要插入则为 true ，要删除则为 false
 * @param entry 要插入/删除的表项
 *
 * 插入时如果已经存在一条 addr 和 len 都相同的表项，则替换掉原有的。
 * 删除时按照 addr 和 len **精确** 匹配。
 */
void update(bool insert, RoutingTableEntry entry) {
	if (insert)
		table.insertEntry(entry);
	else
		table.deleteEntry(entry);
	return;
}

/**
 * @brief 进行一次路由表的查询，按照最长前缀匹配原则
 * @param addr 需要查询的目标地址，大端序
 * @param nexthop 如果查询到目标，把表项的 nexthop 写入
 * @param if_index 如果查询到目标，把表项的 if_index 写入
 * @return 查到则返回 true ，没查到则返回 false
 */
bool prefix_query(uint32_t addr, uint32_t *nexthop, uint32_t *if_index) {
	RoutingTableEntry* result = table.query(addr);
	if (result == NULL)
		return false;
	*nexthop = result->nexthop;
	*if_index = result->if_index;
	return true;
}

评测结果