一、 实验内容

1.编写symtab_ll.c

2.使用 python 代码进行测试

二、 实验过程

编写symtab_ll.c

1） 初始化:
初始化时需要分配一个新的结构体节点，并将内容置零，‘next’初始化为NULL

1
2
3
4
5
6
7

symtab *symtab_init(){
    symtab *self = malloc(sizeof(symtab));
    memset(self, '\0', sizeof(symtab));
    self->next = NULL;
    return self;
}

2） 插入:
将新条目插入到链表中，需要遍历链表，检查给定的键是否已经存在。如果不存在，它创建一个新节点，用提供的键和值初始化其条目，并将其追加到链表的末尾。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int symtab_insert(symtab *self, char *key, VAL_T value){
    symtab *ptr = self;
    while(ptr->next != NULL){
        if(strcmp(ptr->entry.key, key) == 0)
            return 0;
        ptr = ptr->next;
    }
    symtab *node = malloc(sizeof(symtab));
    memset(node, '\0', sizeof(symtab));
    entry_init(&node->entry, key, value);
    node->next = NULL;
    ptr->next = node;
    return 1;
}

3） 查找:
查找给定键，先遍历链表，如果找到键，就返回相应的值；否则返回 -1。

1
2
3
4
5
6
7
8
9
VAL_T symtab_lookup(symtab *self, char *key){
    symtab *ptr = self;
    while(ptr != NULL){
        if(strcmp(ptr->entry.key, key) == 0)
            return ptr->entry.value;
        ptr = ptr->next;
    }
    return -1;
}

4） 删除:
从符号表中移除给定键对应的条目，遍历链表，找到匹配的键后删除相应的节点，并释放相关的内存。如果成功删除，则返回 1；否则返回 0。

1
2
3
4
5
6
7
8
9
10
11
12
13
int symtab_remove(symtab *self, char *key){
    symtab *ptr = self, *tmp;
    while(ptr->next != NULL) {
        if(strcmp(ptr->next->entry.key, key) == 0){
            tmp = ptr->next;
            ptr->next = ptr->next->next;
            free(tmp);
            return 1;
        }
        ptr = ptr->next;
    }
    return 0;
}

三、 测试结果

Test.py运行成功

img