基本数据结构和散列表

1、 基本数据结构和散列表 1动态集合概念：算法所操作的集合，可以随着时间的改变而增大、缩小或产生其他变化。动态集合上的操作：SEARCH(S，k)INSERT(S，x)DELETE(S，x)MINIMUM(S)MAXIMUM(S)SUCCESSOR(S，x)PREDECESSOR(S，x)2基本数据结构栈队列链表有根树3栈和队列栈和队列都是动态集合，在这种结构中，可以用DELETE操作去掉的元素是预先规定好的。栈队列LIFO、压入、弹出、上溢、下溢FIFO、入队、出队、上溢、下溢4链表在链表这种数据结构中，各对象按线性顺序排序。链表中的顺序是由各对象中的指针所决定的。双链表：包含next域和pr

2、ev域LIST-INSERT(L，x)操作LIST-DELETE(L，x)操作5链表引入哨兵：一个空链表仅含哨兵元素非空链表，表头关键字为9，表尾关键字为1执行LIST-INSERT(L，x)操作，插入关键字为25的新对象，称成为新表头执行LIST-DELETE(L，x)操作，删掉表尾，新表尾为关键字为4的对象6链表-有根树二叉树：分支数无限制的有根树：7时间性能比较8散列表散列表示散列函数开放寻址法完全散列9散列表K关键字地址hh(k)一种能把关键字K映射成记录的存储地址的函数散列函数h散列地址散列法散列表h(k)关键码 地址转换用散列法表示的字典10直接寻址表与散列表U（关键字全域）094

3、76111散列表需要解决的问题碰撞 若某个散列函数H对于不相等的关键字key1和key2得到相同的散列地址，即： H(key1)=H(key2)， 则将该现象称为碰撞，而发生冲突的这两个关键字则称为该散列函数 H 的同义词。12链接法解决碰撞 链接法：将所有关键字为同义词的结点链接在同一个单链表中。13开放寻址法 当冲突发生时，使用某种方法在散列表中形成一个探查序列，沿着此探查序列逐个单元地检索，直到找到给定的关键字，或者碰到一个开放的地址为止。 开放寻址法好处在于根本不用指针，而是计算出要存取的各个槽。这样一来，由于不用存储指针而节省了空间，从而可以用同样的空间来提供更多的槽，其潜在效果就是

4、可以减少碰撞，提高查找速度。14一致散列 假设每一个关键字的探查序列是的m！种排列中的任一种的可能性是相同的。 有三种技术常用来计算开放寻址法中的探查序列：线性探查、二次探查、双重探查。这几种技术都能保证对每个关键字k，都是的一个排列。15常用技术 线性探查 二次探查 双重探查16线性探查 基本思想：将散列表看成是一个环形表dd+1, d+2, , m-10,1, , d-1若地址为 d ( 即 H(key)=d )用线形探查法解决冲突，求下一个开放地的公式为： di=(d+i)%m i=1,2,s (1sm-1) 其中：d=H(key)存在的问题：一次群集17二次探查 二次探查法的探查序列依

5、次是12， -12， 22， -22，等，也就是说，发生冲突时，将同义词来回散列在第一个地址d=H(key)的两端。由此可知，发生冲突时，求下一个开放地址的公式为： d2i-1=(d+i2)%m d2i=(d-i2)%m (1i(m-1)/2) 虽然二次探查法减少了堆积的可能性，但是二次探查法不容易探查到整个散列表空间，只有当表长 m 为4j+3 的素数时，才能探查到整个表空间，这里j为某一正整数。也存在二次群集的问题。18双重散列 这种方法使用两个散列函数 H1 和 H2 ，其中 H1 和前面的 H 一样，以关键字为自变量，产生一个1到 m-1之间的、并和m互素的数作为对散列地址的补偿。若H

6、1（key)=d 发生冲突，则再计算 H2（key)，得到的探查序列为： （d+H2（key)%m ， （d+2H2（key)%m ， （d+3H2（key)%m ，由此可知，双散列函数探查法求下一个开放地址的公式为：di= （d+iH2（key)%m (1i(m-1)19 这三种技术都不能实现一致散列的假设，因为它们能产生的不同探查序列数都不超过m2个（一致散列要求有m！个探查序列）。 在这三种技术中，双重散列能产生的探查序列数最多，因而能给出最好的结果。20散列函数一个好的散列函数应（近似地）满足简单一致散列的假设：每个关键字都等可能地散列到m个槽位的任何一个之中去，并与其他的关键字已被散列到哪一个槽位中无关。将关键字解释为自然数：多数散列函数都假定关键字域为自然数集N=0，1，2，。如果所给关键字不是自然数，则必须有一种方式将其解释为自然数。 例：标识符pt可以被解释为十进制整数对（112，116），因为在ASCII字符集中，p=112，t=116。然后，按128为基数来表示，pt即为（112*128）+116=14452.21 除法散列法乘法散列法散列函数通过取k除以