|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
根据设定的哈希函数和处理冲突的方法，将一组关键字映射到一个有限的、连续的地址集（区间）上，并以关键字在地址集中的"像"作为记录在表中的存储位置，这种表称为哈希表，这一映射过程称为哈希造表或散列，所得的存储位置称为哈希地址或散列地址。
|
|
|
|
对于哈希表，主要考虑两个问题：一是如何构造哈希函数；二是如何解决冲突。
|
|
|
|
|
|
常用的哈希函数构造方法有直接定址法、数字分析法、平方取中法、折叠法、随机数法和除留余数法等。
|
|
|
|
|
|
常见的处理冲突的方法有开放地址法、链地址法、再哈希法、建立一个公共溢出区。
|
|
|
|
|
|
|
|
（1）虽然哈希表在关键字与记录的存储位置之间建立了直接映像，但由于冲突的产生，使得哈希表的查找过程仍然是一个给定值和关键字进行比较的过程，因此，仍须以平均查找长度衡量哈希表的查找效率。
|
|
|
|
（2）查找过程中须与给定值进行比较的关键字的个数取决于哈希函数、处理冲突的方法和哈希表的装填因子3个因素。哈希表的装填因子定义为
|
|
|
|
|
|
式中，α表示哈希表的装满程度。直观地看，α越小，发生冲突的可能性就越小；反之，α越大，表中已填入的记录越多，再填记录时，发生冲突的可能性就越大，则查找时，给定值需与之进行比较的关键字的个数也就越多。
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
线性表的顺序存储是用一组地址连续的存储单元依次存储线性表中的数据元素，从而使得逻辑关系相邻的两个元素在物理位置上也相邻。在这种存储方式下，存储逻辑关系无须占用额外的存储空间。其优点是可以随机存取表中的元素，缺点是插入和删除操作需要移动大量的元素。
|
|
|
|
一般地，在线性表的顺序存储结构中，第i个元素ai的存储位置为
|
|
|
|
|
|
式中，LOC(a1)为表中第一个元素的存储位置；L为表中每个元素所占空间的大小。
|
|
|
|
|
|
线性表的链式存储是指用节点来存储数据元素，节点的空间可以是连续的，也可以是不连续的，因此存储数据元素的同时必须存储元素之间的逻辑关系。节点空间只有在需要的时候才申请，无须事先分配。最基本的节点结构如下图所示。
|
|
|
|
|
|
|
|
其中，数据域用于存储数据元素的值，指针域则存储当前元素的直接前驱或直接后继信息，指针域中的信息称为指针（链）。n个节点通过指针连成一个链表，若节点中只有一个指针域，则称为线性链表（单链表）。
|
|
|
|
线性表采用链表作为存储结构时，不能进行数据元素的随机访问，但其优点是插入和删除操作不需要移动元素。以下是几种其他链表结构。
|
|
|
|
（1）双向链表。每个节点包含两个指针，指明直接前驱和直接后继元素，可在两个方向上遍历链表。
|
|
|
|
（2）循环链表。表尾节点的指针指向表中的第一个节点，可在任何位置上开始遍历整个链表。
|
|
|
|
（3）静态链表。借助数组来描述线性表的链式存储结构。
|
|
|
|
在链式存储结构中，只需要一个指针（头指针）指向第一个节点，就可以顺序访问到表中的任意一个元素。为了简化对链表状态的判定和处理，特别引入一个不存储数据元素的节点，称为头节点，将其作为链表的第一个节点并令头指针指向该节点。
|
|
|
|
|
|
|
|
|
|
|
|
|
