结构推理
确定一个数据的逻辑结构之后,可以刚不同的方法在计算机内表示这个结构。请说明索引表示方法的基本思想、优缺点以及适用情况。
【正确答案】索引表示方法是一种通过索引项来确定结点位置的存储方法。每个索引项包含一个结点的关键码和该结点的存储位置,把索引项按关键码排序可以构成索引表,从而可将不等长结点数据结构的处理转换成对等长结点的索引表的处理。
数组是一种特殊的索引结构。当结点等长并且元素个数不大时可用教组存储,不需要另建索引表,直接用下标作为关键码,通过计算可以直接得到元素地址。
优点:
①索引表的建立可将不等长结点结构的处理转化为对等长结点结构的处理。
②多级索引的引入可将线性结构转换成树形结构,从而提高检索效率。
缺点:索引要占用额外的空间。
适用于大型结构(例如文件)和不等长结点结构的处理。
【答案解析】