首页 > 代码库 > 【原创】算法导论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题试解