| 表示有序集的一个新的数据结构 |
| |
| 引用本文： | 王晓东,傅清祥.表示有序集的一个新的数据结构[J].福州大学学报(自然科学版),1995(5):12-18. |
| |
| 作者姓名： | 王晓东 傅清祥 |
| |
| 作者单位： | 福州大学计算机科学与技术系 |
| |
| 基金项目： | 福建省自然科学基金,国家教委留学回国人员基金 |
| |
| 摘 要： | 提出一个表示有序集的新的数据结构。该数据结构能在Ｏ（ｌｏ｜Ｓ｜）时间内实现对有序集Ｓ的搜索、插入、删除，删除最小元和删除最大元的运算。在Ｏ（ｌ）时间内对Ｓ实现找最小元和找最大元，找Ｓ中的元素ｘ的前驱和后继等运算。因此该数据结构能高效地同时实现抽象数据类型字典和双向优先队列，并保持有序链表的优点。
|
| 关 键 词： | 链表 树 字典 优先队列 |
A New Data Structure for Ordered Sets |
| |
| Wang Xiaodong,Fu Qingxiang.A New Data Structure for Ordered Sets[J].Journal of Fuzhou University(Natural Science Edition),1995(5):12-18. |
| |
| Authors: | Wang Xiaodong Fu Qingxiang |
| |
| Institution: | Wang Xiaodong;Fu Qingxiang(Department of Computer Science and Technology, Fuzhou University,Fuzhou,350002) |
| |
| Abstract: | This paper presents a new data structure trichromatic tree for ordered sets.If set S is represented by a trichromatic tree then operations of searching, inserting,deleting,deletemining and deletemaxing take time O(log|S|)and operations of minning,maxing,predecessing and successing take time O(1).Therefore,the data structure can simullaneously realize the abstract date-type dictionary and the low-end priority queue efficiently. |
| |
| Keywords: | linked list tree dictionary priority queue |
| 本文献已被 CNKI 等数据库收录！ |
| 点击此处可从《福州大学学报(自然科学版)》浏览原始摘要信息 |
| 点击此处可从《福州大学学报(自然科学版)》下载免费的PDF全文 |
