table-2-完整.zip

#include <stdio.h> #include <stdlib.h> #include <assert.h> #include "table.h" #define TABLE_SLOTS_SIZE 10 struct table_node { struct table_element e; struct table_node *next; }; struct table { struct table_node **slots; int count; // number of elements int size; // number of slots struct table_node *iter; // iterator }; /* 这里是全局变量table_error的定义 */ const struct table_element table_error = {-1, -1}; /* 在堆里创建一个空的查找表，如果成功则返回该对象的地址（指针），否则返回ＮＵＬＬ */ struct table *table_init() { struct table *t = NULL; t = (struct table *)malloc(sizeof(struct table)); if (t == NULL) return NULL; assert(t != NULL); t->slots = NULL; t->count = 0; t->size = 0; t->iter = NULL; t->slots = (struct table_node **)calloc(TABLE_SLOTS_SIZE, sizeof(struct table_node *)); if (t->slots == NULL) { free(t); return NULL; } assert(t->slots != NULL); t->size = TABLE_SLOTS_SIZE; return t; } /* 释放查找表t */ void table_free(struct table *t) { struct table_node *node = NULL; int i; assert(t != NULL); assert(t->slots != NULL); for (i = 0; i < t->size; i++) { // t->slots[0] 表达式就是0号单向链表的head指针 while (t->slots[i] != NULL) { // 1.把这个节点从链中摘出来 node = t->slots[i]; t->slots[i] = node->next; // 2. 释放node指针指向的节点 free(node); t->count--; } } assert(t->count == 0); free(t->slots); free(t); return; } /* 返回查找表中的数据元素个数 */ int table_count(struct table *t) { assert(t != NULL); assert(t->slots != NULL); return t->count; } /* 把一个查找表中的数据元素清空，完成之后 count = 0 */ void table_clear(struct table *t) { struct table_node *node = NULL; int i; assert(t != NULL); assert(t->slots != NULL); for (i = 0; i < t->size; i++) { // t->slots[0] 表达式就是0号单向链表的head指针 while (t->slots[i] != NULL) { // 1.把这个节点从链中摘出来 node = t->slots[i]; t->slots[i] = node->next; // 2. 释放node指针指向的节点 free(node); t->count--; } } assert(t->count == 0); return; } /* 判断查找表是否为空，如果为空则返回1，否则返回0 */ int table_isempty(struct table *t) { assert(t != NULL); assert(t->slots != NULL); return (t->count == 0); } /* 判断是否有下一个数据元素，如果有则返回1，否则返回0 */ int table_hasnext(struct table *t) { int i; assert(t != NULL); assert(t->slots != NULL); // 1. 当iter== NULL的时候 if (t->iter == NULL) { for (i = 0; i < t->size; i++) { if (t->slots[i] != NULL) { t->iter = t->slots[i]; return 1; } } } // 2. 当iter != NULL的时候 if (t->iter != NULL) { if (t->iter->next != NULL) { t->iter = t->slots[i]; return 1; } else { i = t->iter->e.key % t->size + 1; // 计算iter所在slot的下一个slot for (; i < t->size; i++) { if (t->slots[i] != NULL) { t->iter = t->slots[i]; return 1; } } } } return 0; // 没有下一个 } /* 如果有，则返回下一个数据元素，该操作的前提条件：hasnext()要为1 */ struct table_element table_next(struct table *t) { assert(t != NULL); assert(t->slots != NULL); return t->iter->e; } /* 将查找表中的迭代指针复位 */ void table_rewind(struct table *t) { assert(t != NULL); assert(t->slots != NULL); t->iter = NULL; return; } /* 将数据元素（key, value）放入查找表中 --- */ void table_put(struct table *t, int key, int value) //void table_put(struct table *t, struct table_element e); { struct table_node *p = NULL; struct table_node *node = NULL; assert(t != NULL); assert(t->slots != NULL); // 1. 先查找，看key的元素是否存在 ，如果存在就是set p = t->slots[key % t->size]; // 计算出key应该在哪个slot中 while (p != NULL) { if (p->e.key == key) { p->e.value = value; return; } p = p->next; } // 2. 没有找到，再进行插入 node = (struct table_node *)malloc(sizeof(struct table_node)); if (node == NULL) { perror("malloc failed in table_put() !!"); exit(1); } assert(node != NULL); node->e.key = key; node->e.value = value; node->next = NULL; // 插入 node->next= t->slots[key % t->size]; //1. t->slots[key % t->size] = node; t->count++; table_rewind(t); return; } /* 删除查找表中，key的数据元素，并返回删除的数据元素。 当查找表中，存在key的数据元素，则删除它并返回该元素 当查找表中，不存在key的数据元素，则返回table_error以表示不存在相应的元素 */ struct table_element table_remove(struct table *t, int key) { struct table_node *node = NULL; struct table_node *p = NULL; struct table_element ret; assert(t != NULL); assert(t->slots != NULL); // 1.没有前驱节点的情况,就是第一个节点如果是key节点 if (t->slots[key % t->size]->e.key == key) { node = t->slots[key % t->size]; t->slots[key % t->size] = node->next; ret = node->e; free(node); t->count--; table_rewind(t); return ret; } // 2.有前驱节点的情况 p = t->slots[key % t->size]; while (p != NULL && p->next != NULL) { if (p->next->e.key == key) { node = p->next; p->next = node->next; ret = node->e; free(node); t->count--; table_rewind(t); return ret; } p = p->next; } return table_error; } /* 在查找表中查找key对应的数据元素，并返回该数据元素。 当查找表中，存在key的数据元素，则返回该元素 当查找表中，不存在key的数据元素，则返回table_error以表示不存在相应的元素 */ struct table_element table_get(struct table *t, int key) { struct table_node *p = NULL; assert(t != NULL); assert(t->slots != NULL); p = t->slots[key % t->size]; while (p != NULL) { if (p->e.key == key) { return p->e; } p = p->next; } return table_error; }