计算机备考资料：数据结构基本概念(十一)

《计算机备考资料：数据结构基本概念(十一)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构：基本概念(十一)Ø处理冲突的方法　　开放定址法　　用开放定址法处理冲突得到的散列表叫做闭散列表。　　所谓开放定址法，就是由关键码得到的散列地址一旦产生了冲突，就去寻找下一个空的散列地址，只要散列表足够大，空的散列地址总能找到，并将记录存入。　　①线性探测法　　当发生冲突时，线性探测法从冲突位置的下一个位置起，依次寻找空的散列地址，即对于键值key，设H(key)=d，闭散列表的长度为m，则发生冲突时，寻找下一个散列地址的公式为：　　Hi=(H(key)+di)%m(di=1，2，…，m-1)。　　线性探测法会出现非同义词之间对同一个散列地址争夺的现象，称为堆积或聚集。　　

2、②二次探测法　　当发生冲突时，二次探测法寻找下一个散列地址的公式为：　　Hi=(H(key)+di)%m(di=12，-12，22，-22，…，q2，-q2且q≤m/2)　　③随机探测法　　当发生冲突时，随机探测法探测下一个散列地址的位移量是一个随机数列，即寻找下一个散列地址的公式为：　　Hi=(H(key)+di)%m(di是一个随机数列，i=1，2，……，m-1)　　拉链法(链地址法)　　用拉链法处理冲突构造的散列表叫做开散列表。　　拉链法的基本思想是：将所有散列地址相同的记录，即所有关键码为同义词的记录存储在一个单链表中——称为同义词子表，在散列表中存储的是所有同义词子表的头

3、指针。　　Ø直接插入排序的基本思想　　直接插入排序的基本思想是：依次将待排序序列中的每一个记录插入到一个已排好序的序列中，直到全部记录都排好序。　　Ø直接插入排序算法的性能　　·时间性能　　最好情况：待排序序列为正序，时间复杂度为O(n);　　最坏情况：待排序序列为逆序，时间复杂度为O(n2)。　　平均情况：待排序序列中各种可能排列的概率相同，时间复杂度为O(n2)。　　·空间性能　　直接插入排序只需要一个记录的辅助空间。　　·稳定性　　直接插入排序是一种稳定的排序方法。　　Ø希尔排序的基本思想　　希尔排序的基本思想是：先将整个待排序记录序列分割成若干个子序列，在子序列内分别进行直

4、接插入排序，待整个序列基本有序时，再对全体记录进行一次直接插入排序。　　Ø希尔排序算法的性能　　·时间性能　　希尔排序算法的时间性能是所取增量的函数，其时间性能在O(n2)和O(nlog2n)之间，当n在某个特定范围时，希尔排序的时间性能约为O(n1.3)。　　·空间性能　　希尔排序只需要一个记录的辅助空间，用于暂存当前待插入的记录。　　·稳定性　　希尔排序是一种不稳定的排序方法。文后寄语：book118是一个专注于电子文档的在线分享平台，用户在此平台上不但可以自由交换文档，还可以分享最新的行业资讯。book118制定了严格的文档审核策略，以保证文档来源的合法性，对有可能引起知识产

5、权纠纷的文档，网站不予收录。同时，道客巴巴采用了行业领先的文档加密及保护技术，最大程度上保证用户上传的文档的版权不被非法侵犯。注册1、会员信息是您在book118网站的身份标识，注册后，您可以浏览文档、在线阅读或下载，建立并管理自己的文档信息库;2、打开网站的首页，点击页面上方的信息条文字"【免费注册】"，在用户注册页面，输入用户名、密码、电子邮件、验证码，阅读"服务协议"，并选中"同意"复选框，最后点击"注册"按钮;3、也可以在"登录"页面，点击"新用户注册"按钮，进入用户注册页面;