论拉链法及其典型应用

摘要

本文试图介绍数据结构中的一个特别有用的方法——拉链法。文章分两部分。一第部分,作者力图全面系统地讨论拉链法的概念与原理,并以单向均匀链表为主给出了拉链、解链、链表查找（寻链）、插入与删除等链表操作算法。然后,全表介绍了单向不均匀链表、多向链表、循环链表的概念。第二部分,作者从杂凑法构造的散列表、多重栈与多重队列、树与图等典型数据结构型式中的一些困难问题入手,讨论拉链法在克服这些困难问题时在这些结构型式中的应用,并在讨论中指出应用的条件和范围,进而得出评价数据结构中的方法是否是一个好方法的条件。 拉链法是数据结构中的一个行之有效的。方法,也是应用软件设计的强有力的工具。本文将系统地阐述拉链法的概念、原理、算法以及几种典型的应用,并给出评价数据结构中的方法是否是一个好方法的条件。