首页 > 代码库 > 【原创】算法导论11章带星第4题试解
【原创】算法导论11章带星第4题试解
题目:
我们希望在一个【非常大】的数组上,通过利用直接寻址的方式来实现一个字典。开始时,该数组中可能包含一些无用信息,但要对整个数组进行初始化是不太实际的,因为该数组的规模太大。请给出在大数组上实现直接寻址字典的方案。每个存储对象占用O(1)空间;SEARCH、INSERT和DELETE操作的时间均为O(1);并且对数据结构初始化的时间为O(1)。
(提示:可以利用一个附加数组,处理方式类似于栈,其大小等于实际存储在字典中的关键字数目,以帮助确定大数组中某个给定的项是否有效)
解答:
这个提示非常微妙啊。神马叫“类似于栈”?但参透这个提示真意的话,解决问题也就不远了。
【类似于栈】,可以理解为以栈的方式来加入数据结构,但【可以随机访问】整个栈。
不妨设大数组为array,附加数组为mystack,栈顶指针为top,初始化为 -1。
我们每插入一个数据item,就把该数据通过mystack[++top]的方式添加到栈中,同时,将array[item]的值设为top。
查找的时候,先通过array[item]找到数据在栈中的位置pos,如果pos比栈的容量大,那肯定查找失败;如果pos小于栈的容量且mystack[pos] == item,那么查找成功。剩下的情况都算查找失败。表示为C代码:
if (array[item] <= top && mystack[array[item]] == item)
return 1;
else
return 0;
删除的时候呢?怎么保持提示中所说的“其大小等于实际存储在字典中的关键字数目”?
这里有一个比较hack的方法,分两种情况。
0、栈顶元素要被删除:直接top --
1、栈内元素要被删除:设被删除元素栈内序号为k,则swap(&mystack[k],&mystack[top])之后,【更新array[mystack[top]]的值为k】
为什么呢?
因为array数组存储的是数据在栈中的位置,mystack[top]并没有被删除,但是存储位置改变了,因此,必须修改array[mystack[top]]的值为原栈顶数据在栈中的新位置。
总结:
大概是这么个逻辑:
我要找数据tmp:
(获得了tmp在栈中的位置)
tmp --------> array --------> mystack
(栈中特定位置上是tmp吗?)
【原创】算法导论11章带星第4题试解