任务描述
本关要求通过补全函数ILH_InsKey和ILH_DelKey来分别实现插入和删除操作。
相关知识
本关讨论散列存储，散列函数使用除留余数法，冲突解决方法采用独立链表地址法。假设有 8 个关键码： 7 , 15 , 23 , 31 , 12 , 14 , 10 , 17 ，采用散列函数hash(key)=key%7，其存储结构图如图 1 所示，它由 7 个独立链表组成，散列值相同的关键码在同一个链表里，独立链表的头结点组成散列表，一共 7 行，编号 0 , 1 , … , 6 。独立链表的每个结点是一个 struct HNode 结构，其定义如下：
struct HNode {int key; //假设关键码为整数HNode* next;};
在散列表中，如果表项的key字段等于 0 （假设有效的关键码值不等于 0 ），则表示该行是一条空链表，例如图 1 中编号为 4 和编号为 6 的行。
散列表的开始地址保存在pn中，散列表的行数为n（图 1 中，n=7），将pn和n组织成结构：
struct LHTable {HNode* pn; //指向散列表，每个表结点是独立链表的表头结点int n; //散列表的长度，一般取（小于等于数据个数的最大）质数};
定义如下操作，各操作函数的功能详见下面给出的代码文件 indLnkHash.cpp 的代码框架：
LHTable* ILH_Create(int n);
void ILH_Free(LHTable* pt);
bool ILH_InsKey(LHTable* pt, int x);
bool ILH_FindKey(LHTable* pt, int x);
bool ILH_DelKey(LHTable* pt, int x);
void ILH_Print(LHTable *pt);
编程要求
本关的编程任务是补全 step2/indLnkHash.cpp 文件中的ILH_InsKey和ILH_DelKey函数来分别实现插入和删除操作。
- 具体请参见后续测试样例。
本关涉及的代码文件 indLnkHash.cpp 的代码框架如下：
#include <stdio.h> #include <stdlib.h> #include <time.h> #include "indLnkHash.h" LHTable* ILH_Create(int n) //创建散列表, n为表长度，最佳取值：n取小于等于数据个数的最大质数 { HNode* pn=(HNode*)malloc(sizeof(HNode)*n); for (int i=0; i<n; i++) { pn[i].key=0; pn[i].next=NULL; } LHTable* pt=(LHTable*)malloc(sizeof(LHTable)); pt-> pn=pn; pt->n=n; return pt; } void ILH_Free(LHTable* pt) //释放散列表 { if (pt==NULL) return; for (int i=0; i<pt->n; i++) { HNode* curr=pt->pn[i].next; while (curr) { HNode* next=curr->next; free(curr); curr=next; } } free(pt->pn); free(pt); } bool ILH_InsKey(LHTable* pt, int x) //插入关键码x //返回true，表示插入成功 //返回false，表示插入失败(关键码已经存在) { // 请在此添加代码，补全函数ILH_InsKey /********** Begin *********/ /********** End **********/ } bool ILH_FindKey(LHTable* pt, int x) //查找关键码x //返回true表示找到 //返回false表示没找到 { int d=x%pt->n; if (pt->pn[d].key==0) { return false; } else if (pt->pn[d].key==x) return true; HNode* curr=pt->pn[d].next; while (curr && curr->key!=x) curr=curr->next; if (curr) return true; else return false; } bool ILH_DelKey(LHTable* pt, int x) //删除关键码 //返回true表示该关键码存在，且成功删除 //返回false表示该关键码不存在 { // 请在此添加代码，补全函数ILH_DelKey /********** Begin *********/ /********** End **********/ } void ILH_Print(LHTable *pt) { for (int i=0; i<pt->n; i++) { printf("%5d: ", i); if (pt->pn[i].key) { printf("%d ", pt->pn[i].key); HNode* curr=pt->pn[i].next; while (curr) { printf("-> %d ", curr->key); curr=curr->next; } printf("\n"); } else printf("-\n"); } }
测试说明
本关的测试文件是 step2/Main.cpp ，测试过程如下：
- 平台编译 step2/Main.cpp ，然后链接相关程序库并生成 exe 可执行文件；
- 平台运行该 exe 可执行文件，并以标准输入方式提供测试输入；
- 平台获取该 exe 可执行文件的输出，然后将其与预期输出对比，如果一致则测试通过；否则测试失败。
输入输出格式说明
输入格式： 首先输入一个正整数n，创建一个长n的散列表。 然后输入多个操作：如果输入 “insert” ，则后面跟一个数x，表示将x插入；如果输入 “delete” ，则后面跟一个数x，表示将x删除；如果输入 “end” ，表示输入结束。
输出格式： 输出n个独立链表。
以下是平台对 step2/Main.cpp 的样例测试集：
样例输入： 11 insert 54 insert 77 insert 94 insert 89 insert 14 insert 45 insert 76 insert 23 insert 43 insert 47 end
样例输出： 0: 77 1: 89 -> 45 -> 23 2: - 3: 14 -> 47 4: - 5: - 6: 94 7: - 8: - 9: - 10: 54 -> 76 -> 43
开始你的任务吧，祝你成功
AC_Code
#include <stdio.h> #include <stdlib.h> #include <time.h> #include "indLnkHash.h" LHTable* ILH_Create(int n) //创建散列表, n为表长度，最佳取值：n取小于等于数据个数的最大质数 { HNode* pn=(HNode*)malloc(sizeof(HNode)*n); for (int i=0; i<n; i++) { pn[i].key=0; pn[i].next=NULL; } LHTable* pt=(LHTable*)malloc(sizeof(LHTable)); pt-> pn=pn; pt->n=n; return pt; } void ILH_Free(LHTable* pt) //释放散列表 { if (pt==NULL) return; for (int i=0; i<pt->n; i++) { HNode* curr=pt->pn[i].next; while (curr) { HNode* next=curr->next; free(curr); curr=next; } } free(pt->pn); free(pt); } bool ILH_InsKey(LHTable* pt, int x) //插入关键码x //返回true，表示插入成功 //返回false，表示插入失败(关键码已经存在) { /*请在BEGIN和END之间实现你的代码*/ /*****BEGIN*****/ int d=x%pt->n; if (pt->pn[d].key==0) { pt->pn[d].key=x; return true; } else if (pt->pn[d].key==x) return false; HNode* prev=&(pt->pn[d]); HNode* curr=pt->pn[d].next; while (curr && curr->key!=x) {prev=curr; curr=curr->next;} if (curr) return false; HNode* pnode=(HNode*)malloc(sizeof(HNode)); pnode->key=x; pnode->next=NULL;//pt->pn[d].next; prev->next=pnode; return true; /******END******/ /*请不要修改[BEGIN,END]区域外的代码*/ } bool ILH_FindKey(LHTable* pt, int x) //查找关键码x //返回true表示找到 //返回false表示没找到 { int d=x%pt->n; if (pt->pn[d].key==0) { return false; } else if (pt->pn[d].key==x) return true; HNode* curr=pt->pn[d].next; while (curr && curr->key!=x) curr=curr->next; if (curr) return true; else return false; } bool ILH_DelKey(LHTable* pt, int x) //删除关键码 //返回true表示该关键码存在，且成功删除 //返回false表示该关键码不存在 { /*请在BEGIN和END之间实现你的代码*/ /*****BEGIN*****/ int d=x%pt->n;//关键码x的散列值d if (pt->pn[d].key==0) { return false; } else if (pt->pn[d].key==x) { if (pt->pn[d].next ==NULL) pt->pn[d].key=0; else { HNode* first=pt->pn[d].next; pt->pn[d].key=first->key; pt->pn[d].next=first->next; free(first); } return true; } HNode* prev=&(pt->pn[d]); HNode* curr=pt->pn[d].next; while (curr && curr->key!=x) {prev=curr; curr=curr->next;} if (curr==NULL) return false; prev->next=curr->next; free(curr); return true; /******END******/ /*请不要修改[BEGIN,END]区域外的代码*/ } void ILH_Print(LHTable *pt) { for (int i=0; i<pt->n; i++) { printf("%5d:", i); if (pt->pn[i].key) { printf("%d", pt->pn[i].key); HNode* curr=pt->pn[i].next; while (curr) { printf("->%d", curr->key); curr=curr->next; } printf("\n"); } else printf("-\n"); } }
