2. 计算机
  3. 阅读以下函数说明、图和C程序代码，将C程序段中(1)～(6)空缺处的语句填写完整。 [说明] 散列文件的存储单位称为桶(BUCKET)。假如一个桶能存放m个记录，当桶中已有m个同义词(散列函数值相同)的记录时，存放第m+1个同义词会发生“溢出

阅读以下函数说明、图和C程序代码，将C程序段中(1)～(6)空缺处的语句填写完整。 [说明] 散列文件的存储单位称为桶(BUCKET)。假如一个桶能存放m个记录，当桶中已有m个同义词(散列函数值相同)的记录时，存放第m+1个同义词会发生“溢出

admin2013-01-05  51
问题 阅读以下函数说明、图和C程序代码，将C程序段中(1)～(6)空缺处的语句填写完整。
    [说明]
   散列文件的存储单位称为桶(BUCKET)。假如一个桶能存放m个记录，当桶中已有m个同义词(散列函数值相同)的记录时，存放第m+1个同义词会发生“溢出”。此时需要将第m+1个同义词存放到另一个称为“溢出桶”的桶中。相对地，称存放前m个同义词的桶为“基桶”。溢出桶和基桶大小相同，用指针链接。查找指定元素记录时，首先在基桶中查找。若找到，则成功返回，否则沿指针到溢出桶中进行查找。
   例如，设散列函数为Hash(Key)=Key mod7，记录的关键字序列为15，14，21，87，96，293，35，24， 149，19，63，16，103，77，5，153，145，356，51，68，705，453，建立的散列文件内容如图2-27所示。
   
   为简化起见，散列文件的存储单位以内存单元表示。
   函数InsertToHashTable(int NewElemKey)的功能是：若新元素NewElemKey正确插入散列文件中，则返回值0；否则返回值-1。
   采用的散列函数为Hash(NewElemKey)=NewElemKey%P，其中P设定基桶的数目。
   函数中使用的预定义符号如下。
选项
答案这是一道要求读者掌握如何在散列文件中插入一个新的数据元素的编程题。本题的解答思路如下。 在散列文件中插入一个新的数据元素的基本思路是，首先将要插入的元素代入到散列函数中，从而计算出该元素的散列地址。然后按照散列地址，在基桶中查找空闲单元，若找到，则将元素插入，若基桶已满，则在溢出桶中查找空闲单元。若溢出桶中也查找不到，则申请新的溢出桶，然后将元素存入。 在散列文件中查找一个元素的基本思路是，查找指定元素记录时，首先在基桶中查找，若找到，则成功返回，否则沿指针到溢出桶中进行查找。 在本试题中，将元素存储在预先设定的基桶或根据需要申请的溢出桶中，只要基桶中有空闲单元，就将新元素NewElemkey插入在基桶中，若基桶中无空闲单元，则看是否存在溢出桶，若存在，则在溢出桶中查找空闲单元，若不存在溢出桶或溢出桶中无空闲单元，则申请一个溢出桶并存入新元素。 在基桶查找空闲单元时，使用的桶号为Index，由此可知(1)空缺处所填写的内容是“Index=NewElemKey%P”，或“Index=Hash(NewElemKey)”等其他等价形式。 一旦在基桶中找到空闲单元，即“Bucket[1ndex].keyData[i]==NULLKEY”(0≤i＜ITEMS)，则可将元素NewElemkey放入Bucket[Index].keyData[i]，至此元素已经插入散列桶中，函数可返回，因此(2)空缺处所填写的内容是“i＜ITEMS”。反之， 若在基桶中没有找到空闲单元，则需查找溢出桶。“t=Bucket[Index].Link”，指针t首先指向桶号Index的第一个溢出桶。以下的代码完成在溢出桶中查找空闲单元的功能。 [*] 由于每个溢出桶都可以存储ITEMS个元素，因此在溢出桶中查找空闲单元与在基桶中的查找过程相同，代码如下。 [*] 若在指针t指向的溢出桶中找到空闲单元则插入元素，否则，由“t=t-＞Link”得到下一个溢出桶的指针，因此“k＜ITEMS”可作为是否在当前溢出桶中找到空闲单元的判定条件。显然，在桶号Index的基桶和其所有溢出桶都已满的情况下，t的值为空指针。此时才需要申请新的溢出桶并建立链接关系，因此在上面查找溢出桶中空闲单元时，进行指针t的后移“t=t-＞Link’’前应先用front记录t的值，以便于后面建立链接关系。所以(3)空缺处应给front置初值，即所填写的内容是“front=＆Bucket[Index]”，或“front=Bucket+Index”等其他等价形式。 (4)空缺处用于判断该溢出桶是否已满，即所填写的内容是“k=ITEMS(或k＞=ITEMS)”。如果该溢出桶已满，则继续查找下一个溢出桶，直到查找到空闲单元为止。 若所有溢出桶都不存在空闲单元(即t==NULL)，则申请新的溢出桶，并将新的溢出桶的首地址保存在原有的最后一个溢出桶的Link域中(即front-＞Link=s)。因此(5)空缺处所填写的内容是“t==NULL”， (6)空缺处用于建立新申请溢出桶的链接关系——“front-＞Link=s”。
解析
转载请注明原文地址:https://kaotiyun.com/show/nYDZ777K
本试题收录于： 软件设计师下午应用技术考试题库软考中级分类
0

软件设计师下午应用技术考试

软考中级

相关试题推荐
随机试题
最新回复(0)