文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > IT/计算机 > 一种基于哈希链表的多关键字排序算法
侵权投诉

一种基于哈希链表的多关键字排序算法

哈希表

ISSN1009-3044E-maihxsjl@ccce.net.CrlCompuferKnowledgeandTechnology电奠知识与技术http://www.dnzs.net.cnV01.6.No.4,February2010.PP.859—860Tel:+86..551.—56909635690964一种基于哈希链表的多关键字排序算法

董万归

(大理学院数学与计算机学院,云南大理671003)

摘要:该文结合哈希表提出一种多关键字的排序算法,该算法根据数据元素的关键字转换,利用哈希表的地址映射实现数据元素在有序序列中的位置。从而通过减少关键字比较及移动使排序算法得到优化。算法基于哈希表改进而来,在特殊多关键字排序中具有一定的应用。

关键词:排序;哈希链表;关键字;算法设计

中图分类号:TP301文献标识码:A文章编号:1009—3044(2010)04-0859-02

ASortAlgorithmofManyKeywordsBasedonHashTable

DONGWan—gui

(MathematicsandComputerCollege,DaliCoHege,Dali671003,China)

Abstract:ThispaperpresentsaSortAlgorithmofmanykeyword.sbasedonhashtable,Thealgorithmbasedondataelementsofthekey—wordconversion,Hashtableusingtheaddressmappingdataelementsinanorderlysequenceoflocations,TherebyreducingthekeywordcomparisonandsortingalgorithmSOthatthemobileoptimized.Algorithmbasedonthehashtabletoimprovefrom,fnspecificmanykey—wordsinacertainsortofapplication.

Keywords:sort;hashtable;multiplekeywords;algorithmdesign

排序,就是要将一个序列R。,R:,.一,R。使之按关键字K。,K2。…,K。递增(或递减)排列起来,使得结果序列Rd,R。,…,R。中满足K。。≤k≤…≤K。。(或K。。≥K&≥…≥K0川。排序是程序设计中一种基本常用的操作,在实际程序设计中应用非常广泛,因此排序算法的好坏直接影响到程序的执行操作,进而影响到数据库的执行效率。在其它很多问题巾,排序都是作为其中的一个基本过程,排序算法的好坏直接影响到熬个问题解决的效率。当前,排序算法种类繁多,但就其排序时所遵循的原则而言,大致可分为五大类:插人排序、交换排序、选择排序、归并排序和基数排序。算法性能的好坏则主要是从时间复杂度、空问复杂度和稳定性i个方面考虑Ⅲ。这些传统的排序方法大部分都是基于关键字的比较和序列元素的交换操作来实现,然而,对于一些实际应用中需要处理的数据却要求对多关键字进行排序,所以征对多关键字特定数据经过转换后的特定排序算法可以大大提高数据处理的速度。本文所描述的排序算法就是根据数据元素的关键字转换,利用哈希链表的地址映射实现数据元素枉有序序列中的位置,从而通过减少关键字比较及移动使排序算法得到优化。

l算法描述

算法是基于多关键字转换及哈希链表来实现的,其基本思想是:根据多关键字的特点将其转换为单关键字,并将原始序列当成哈希链表闭:然后,对原始哈希链表进行一遍扫描根据转换过程中的哈希位置确定数据元素在哈希链表中的位置。假设待排数据元素有N个,数据元素的关键字比较有M个其排序优先级为K。>K2>…>KM,K。…K。的范围为Lc"lJm。对于数据的存储可以定义如下结构来实现:

typedefstm('t

{

Elemtypekl,k2,…,km;/*m个关键字定义4/

inttirol;/*m个关键字对应的权值定义}/

intl【m1;/*m个关键字的范围定义4,

…/半其它信息定义t/

Longnodeposition;/木存放转换后的哈希位置+/

NodeType+prior,*next;

lNodeType;

NodeTypeHead,data;

具体算法描述如下:

第一步:将原始数据序列存放到以Head为链表头的哈希链表中j在放人的过程中对任意一个元素i利用公式k=data.d1]4data.1121"data.113]*…*data.1【m】+data.r[21*data.1131"data。114]*…¥data.1【m】+…+data.邢就可p2ff算-出第i个元素在哈希链表中的位置k,将k放人辅助链表哈希位置变量nodeposition中。

第二步:对哈希链表利用哈希位置nodeposifion进行单关键字排序。由于利用了链表进行操作可以使数据元素的移动转化为链收稿日期:2009-12-23

作者简介:董万归(1976-),男,讲师,研究方向为数据库应用和算法研究。

本栏目责任编辑:澍媛媛万 方数据-。t一一*- 软件设计开发-s859

第1页

你可能喜欢

  • 链表排序
  • 双向链表
  • 哈希函数
  • 链表操作实验
  • c语言链表
  • 哈希COD
  • 焦点技术
  • 焦点课题

热门文档

相关文档

  • 【论文】一种基于哈希链表的多关键字排序算法

    一种基于哈希链表的多关键字排序算法_专业资料。该文结合哈希表提出一种多关键字的排序算法,该算法根据数据元素的关键字转换,利用哈希表的地址映射实现数据元素在...

  • 多关键字排序

    多关键字排序_电脑基础知识_IT/计算机_专业资料。C++编写的代码,... 数据结构课程设计报告-多... 17页 免费 一种基于哈希链表的多关... 3页 ...

  • 【论文】一种新的基于哈希函数的排序算法

    一种新的基于哈希函数的排序算法_专业资料。提出一种哈希函数分档的排序算法。... 一种基于哈希链表的多关... 35人阅读 2页 1.00 NTRUSign签名算法中...

  • 基于链表的排序

    (2)基于链表的排序算法实现 2、数据结构设计; 3、主要算法设计; 4、编程及上机实现; 5、撰写课程设计报告,包括: (1)设计题目; (2)摘要和关键字; (3)正文...

  • 一种哈希表快速查找的改进方法

    ( Count) 进行对比 排序; 或者 在使 用基本的 ...对于 上述 两种方 法, 第 一种方法每个元素需要多...哈希地 址的 关键字放在同一个链表 中, 称 为...

  • 数据结构第22讲_哈希表和插入排序1

    9.3.1 什么是哈希表 9.3.2 哈希函数的构造方法...2.排序算法的稳定性排序码(Key) 作为排序依据的...(多关键字排序、基数排序) #define MAXSIZE 20 /...

  • 从头到尾彻底解析Hash_表算法

    10页 7下载券 一种基于哈希链表的多关... 3页 1下载券喜欢此文档的还...第二步:找出 Top 10 算法一:普通排序 我想对于排序算法大家都已经不陌生了, ...

  • Java中的算法排序

    排序的关键字 1. 时间复杂度:整个排序算法运行所...{ int hash = 0; long x = 0L; char[] ...如果数据链表的长度为 0 或 1,则返回 2. 将原始...

  • 哈希算法

    (key)和处理冲突方法将一组关键字 映象到一个有限...由于 ASCII 字符的值最多为 127,如果输入的 key,...使用哈希算法可以提高查询速度,如果 使用链表,查询时...

  • Hash算法

    Hash 算法: hash 算法的意义在于提供了一种快速存取数据的方法,它用一种算法...将具有同一散列地址的记录存储在一条线性链表 中。例,除留余数法中,设关键字...

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email