高考问答acg.bz 最新地址:VC程序_分块查找
来源：百度文库 编辑：高考问答 时间：2024/05/04 16:49:17
分块查找又称为索引顺序查找，其性能介于顺序查找和二分查找之间。分块查找把线性表分成若干块，每一块中的元素存储顺序是任意的，但是块与块之间必须按关键字大小有序排列。
即前一块中的最大关键字小于后一块中的最小关键字值。{另外还需要建立一个索引表，索引表的一项对应线性表中的一块。索引项由键域和链域组成。键域存放相应块的最大关键字，链域存放指向本块的第一个结点的指针。索引表按关键字值递增顺序排列。}
分块查找的函数分两步进行，首先确定待查找的节点属于哪一块。然后在块内查找要查的点。由于索引表是递增有序的，采用二分查找时，块内个数较少。采用顺序查找，不会对执行速度有太大影响。
上面的几段话中的索引表是什么意思啊？？
请那位大虾解释一下那段加了“{}”的话，本人不甚感激！！！
举个具体的程序例子好吗？
即前一块中的最大关键字小于后一块中的最小关键字值。{另外还需要建立一个索引表，索引表的一项对应线性表中的一块。索引项由键域和链域组成。键域存放相应块的最大关键字，链域存放指向本块的第一个结点的指针。索引表按关键字值递增顺序排列。}
分块查找的函数分两步进行，首先确定待查找的节点属于哪一块。然后在块内查找要查的点。由于索引表是递增有序的，采用二分查找时，块内个数较少。采用顺序查找，不会对执行速度有太大影响。
上面的几段话中的索引表是什么意思啊？？
请那位大虾解释一下那段加了“{}”的话，本人不甚感激！！！
举个具体的程序例子好吗？
索引表里存放相应块的最大关键字，比如放了5,13,56,98，你要查找42,从左开始，先是5，5<42，所以42肯定不在这块，再是13，13<42，也不在这块，再是56,56>42，所以42可能就在56这块了。
简单的说，索引表就像是一本书的目录，而元素就像是书的页数。查找时，先在索引表中查找属于哪一块，就像在目录中找某一章一样，然后再在那一块中查找关键字。