算法导论-11.2-四

2013-11-08

算法导论-11.2-4题目：说明在散列表内部，如何通过将所有未占用的槽位链成一个自由表，来分配和去配元素的存

算法导论-11.2-4

题目：

说明在散列表内部，如何通过将所有未占用的槽位链成一个自由表，来分配和去配元素的存储空间。假定一个槽位可以存储一个标志、一个元素加上一个或两个指针。所有的字典操作和自由链表操作应具有O(1)的期望运行时间。该自由链表是双链表吗？或者，是不是单链表就足够了？

思考：

已知（1）所有未占用的槽位链成一个自由链表（2）槽位即slot（3）Hash(x)返回x所属于的slot

一个slot存储以下内容，占用和未占用时表示的含义不同

struct node{int key;bool flag;//0:free，1:usedint pre;int next;};

当这个slot未占用时，取值如下：

struct node{int key;//没有意义，初始化为-1bool flag;//0:freeint pre;//自由链表中上一个空闲slot，没有则为-1int next;//自由链表中下一个空闲slot，没有则为-1};

当这个slot被占用时，取值如下：

struct node{int key;//关键字bool flag;//1:usedint pre;//具有相同Hash值的下一个结点int next;//具有相同Hash值的上一个结点};

插入操作时，从自由链表中取出一个空闲slot，填入关键字x，修改指针，链表相应的队列中，具体可以分为以下几种情况：

（1）x所属的slot未被占用，则

step1：把这个slot从自由链表中移出

step2：填入关键字x

step3：修改指针，在这种情况下其next和pre都置为-1

（2）x所属的slot已经被占用，令占用这个slot的关键是y，y也属于这个slot，则

step1：从自由链表中取出一个空闲的slot，这个slot肯定不是x所属的slot，只是拿过来用

step2：填入关键字x

step3：修改指针，把slot链表入到“以x所属的slot为头结点的队列”中

（3）x所属的slot已经被占用，令占用这个slot的关键是y，y不属于这个slot，通过（2）可知，这个情况是有可能的

step1：从自由链表中取出一个空闲的slot，这个slot肯定不是x所属的slot，也不是y所属的slot，只是拿过来用

step2：在新slot中填入关键字y，修改指针，让y使用这个新slot，而把原来的slot空出来还给x

step3：在x所属的slot中填入关键字x

step4：修改“x所属的slot”指针，类似(1)-step3

删除操作时，令待删除的关键字是x，释放x所占用的slot，具体可以分为以下几种情况

（1）x所占用的slot正是x所属的slot，且slot->next=-1，即所有关键字中只有x属于这个slot，x被删除后，slot就空闲了

step1：释放slot到自由链表中

（2）x所占用的slot正是x所属的slot，但还有别的关键字中只有x属于这个slot，应该优先使用关键所属于的slot，而释放“不自己关键字的、临时拿过来用的”slat

step1：从以slot为头结点的队列中另选一个slot2，slot2的关键字属于slot而不属于slot2，只是因为slot被占用，所以才用slot2

step2：把slot2的内容填入slot

step3：修改指针，让slot代替slot2存在于队列中，不同的是slot还是队列头

step4：释放slot2到自由链表中

（3）x所占用的slot不是x所属的slot，这个种情况下，这个slot一定不是队列头，还有别的关键字存在于队列中，并且占用了x所属的slot

step1：把x所占用的slot从“以x所属的slot为头的队列”中移出

step2：释放slot到自由链表中

查找操作，如果理解了插入和删除，查找操作就比较简单了，令待查找的关键字是x，也可分为几种情况

（1）x所属的slot未被占用，即不存在与x相同slot的关键字，当然也不存在x了

（2）x所属的slot被占用了，但它所存的关键不属于这个slot，与（1）相同，不存在与x相同slot的关键字

（3）x所属的slot被占用了，且它所存的关键属于这个slot，即存在与x相同slot的关键字，只是不知这个关键字是不是x，需要进一步查找

插入和删除过程中反复提到的“从自由链表中取出一个空闲的slot”和“释放slot到自由链表中”这两个操作比较简单，见代码中的解释

代码：

#include <iostream>#include <string>using namespace std;//slot结点struct node{int key;//关键字bool flag;//0:free，1:usedint pre;int next;};int Free = 0;//自由链表的头slot//计算x所属的slotint Hash(int x){return x % 20;}//从自由链表中取出一个空闲的slot，指定取出的编号为h的slotint RemoveSlotFromFree(node *A, int h){//标记为usedA[h].flag = 1;//修改指针移出自由链表if(A[h].pre >= 0)A[A[h].pre].next = A[h].next;else Free = A[h].next;//如果被移出的刚好是表头slot，还要更新表头slot的位置if(A[h].next >= 0)A[A[h].next].pre = A[h].pre;//返回取出的slot的编号return h;}//将编号为h的slot释放到自由链表中void FreeSlotToFree(node *A, int h){//标记为freeA[h].flag = 0;//修改指针，插入到链表头A[h].next = Free;A[h].pre = -1;A[h].key = -1;//更新自由链表的头slotFree = h;}//查找操作int Search(node *A, int x){int h = Hash(x);//(1)x所属的slot未被占用，即不存在与x相同slot的关键字，当然也不存在x了//(2)x所属的slot被占用了，但它所存的关键不属于这个slot，与(1)相同，不存在与x相同slot的关键字if(A[h].flag == 0 || Hash(A[h].key) != h)return -1;//(3)x所属的slot被占用了，且它所存的关键属于这个slot//即存在与x相同slot的关键字，只是不知这个关键字是不是x，需要进一步查找//查找方法就是遍历以slot为头的队列int p = h;while(p >=0 && A[p].key != x)p = A[p].next;if(A[p].key == x)return p;else return -1;}//插入操作时，从自由链表中取出一个空闲slot，填入关键字x，修改指针，链表相应的队列中，void Insert(node *A, int x){//是否已经存在if(Search(A, x) >= 0){cout<<"error:exit"<<endl;return ;}//计算x所属的slotint h = Hash(x);//(1)x所属的slot未被占用if(A[h].flag == 0){//step1：把这个slot从自由链表中移出int t = RemoveSlotFromFree(A, h);//step2：填入关键字xA[t].key = x;//step3：修改指针，在这种情况下其next和pre都置为-1A[t].next = -1;A[t].pre = -1;}//（2）x所属的slot已经被占用，令占用这个slot的关键是y，y也属于这个slotelse if(Hash(A[h].key) == h){//step1：从自由链表中取出一个空闲的slot，这个slot肯定不是x所属的slot，只是拿过来用int t = RemoveSlotFromFree(A, Free);//step2：填入关键字xA[t].key = x;//step3：修改指针，把slot链表入到“以x所属的slot为头结点的队列”中A[t].next = -1;A[h].next = t;A[t].pre = h;}//（3）x所属的slot已经被占用，令占用这个slot的关键是y，y不属于这个slot，//通过（2）可知，这个情况是有可能的else{//step1：从自由链表中取出一个空闲的slot，这个slot肯定不是x所属的slot，也不是y所属的slotint t = RemoveSlotFromFree(A, Free);//step2：在新slot中填入关键字y，修改指针，让y使用这个新slot，而把原来的slot空出来还给xA[t] = A[h];A[A[h].pre].next = t;if(A[h].next >= 0)A[A[h].next].pre = t;//step3：在x所属的slot中填入关键字xA[h].key = x;//step4：修改“x所属的slot”指针，类似(1)-step3A[h].next = -1;A[h].pre = -1;}}//删除操作时，令待删除的关键字是x，释放x所占用的slotvoid Delete(node *A, int x){//是否存在int ret = Search(A, x);if(ret < 0){cout<<"error:not exit"<<endl;return ;} //(1)x所占用的slot正是x所属的slot，且slot->next=-1//即所有关键字中只有x属于这个slot，x被删除后，slot就空闲了if(ret == Hash(x) && A[ret].next == -1){FreeSlotToFree(A, ret);}//(2)x所占用的slot正是x所属的slot，但还有别的关键字中只有x属于这个slot//应该优先使用关键所属于的slot，而释放“不自己关键字的、临时拿过来用的”slatelse if(ret == Hash(x) && A[ret].next != -1){//step1：从以slot为头结点的队列中另选一个slot2//slot2的关键字属于slot而不属于slot2，只是因为slot被占用，所以才用slot2int next = A[ret].next;//next就是slot2的编号//step2：把slot2的内容填入slotA[ret] = A[A[ret].next];//step3：修改指针，让slot代替slot2存在于队列中，不同的是slot还是队列头A[A[ret].next].pre = ret;//step4：释放slot2到自由链表中FreeSlotToFree(A, next);}//(3)x所占用的slot不是x所属的slot,这个种情况下，这个slot一定不是队列头//还有别的关键字存在于队列中，并且占用了x所属的slotelse if(ret != Hash(x)){//step1：把x所占用的slot从“以x所属的slot为头的队列”中移出A[A[ret].pre].next = A[ret].next;if(A[ret].next >= 0)A[A[ret].next].pre = A[ret].pre;//step2：释放slot到自由链表中FreeSlotToFree(A, ret);}}//输出slotvoid Print(node *A){int i;for(i = 0; i < 20; i++)cout<<A[i].flag<<' '<<A[i].key<<' '<<A[i].next<<' '<<A[i].pre<<endl;}int main(){int i;//构造一个拥有20个slot的散列表node A[20];for(i = 0; i < 20; i++){//初始时，所有slot都为freeA[i].flag = 0;if(i == 19)A[i].next = -1;else A[i].next = i + 1;A[i].pre = i - 1;A[i].key = -1;}//teststring str;int x;while(1){cin>>str;if(str == "I"){x = rand() % 100;cout<<x<<endl;Insert(A, x);}else if(str == "D"){cin>>x;Delete(A, x);}else if(str == "P")Print(A);}return 0;}

1楼liuzhanchen1987昨天 20:52: 代码好多，注释很详细！很好！

热点排行

编程

算法导论-11.2-四