《设计并实现一个集合数据结构Set》由会员分享，可在线阅读，更多相关《设计并实现一个集合数据结构Set（9页珍藏版）》请在金锄头文库上搜索。
1、设计并实现一个集合数据结构Set。一个集合中没有重复元素，支持下列运算：(1) boolea n add(E o)如果set中尚未存在指定的元素o,则添加此元素。(1)boolea n addAll(Set c)如果set中没有指定集合c中的所有元素，则将其添加到此set中。(1)void clea r()移除set中的所有元素。boolea n contain s(E o)如果set包含指定的元素o,则返回true。boolea n contain sAII(Set c)如果此set包含指定集合c中的所有元素，则返回true。boolea n isEmpty()如果set不包含元素，则返回t
2、rue。boolea n r emove(E o)如果set中存在指定的元素o,则将其移除。boolea n r emoveAll(Set c)移除set中那些包含在指定集合c中的元素。boolea n r etai nAII(Set c)仅保留set中那些包含在集合c中的元素。int size()返回set中的元素数(其容量)。E toA rr ay()返回包含此set中所有元素的数组要求：1用类或函数实现集合数据结构的存储和运算，实现的类或函数放在一个头文件“Set.h”中， 可以被别的函数使用；2设计另外的函数，利用已实现的“Set.h ”中集合的相关功能，实现任意两个集合的并、交、 差
3、和补运算。2 List工具设计一个列表(List)是一个元素的序列，元素可以重复。用户可以根据元素的整数索引(在列 表中的位置)访问元素，并搜索列表中的元素。List支持下列运算：(1) boolea n add(E o)向列表的尾部追加指定的元素。(2) void add(i nt in dex, E eleme nt)在列表的指定位置插入指定元素。(3) void clea r()从列表中移除所有元素(可选操作)。(4) boolea n contain s(E o)如果列表包含指定的元素，则返回true。(5) E get(i nt in dex)返回列表中指定位置的元素。(6) i n
4、t in dexOf(E o)返回列表中首次出现指定元素的索引，如果列表不包含此元素，则返回-1。(7) boolea n isEmpty()如果列表不包含元素，则返回true。(8) i nt lastI ndexOf(E o)返回列表中最后出现指定元素的索引，如果列表不包含此元素，则返回-1。(9) E r emove(i nt in dex)移除列表中指定位置的元素。(10) boolea n r emove(E o)移除列表中出现的首个指定元素。(11) boolea n r emoveAII(List c)从列表中移除指定List c中包含的所有元素(可选操作)。(12) E set
5、(i nt in dex, E eleme nt)用指定元素替换列表中指定位置的元素。(13) i nt size()返回列表中的元素数。要求：1用类或函数实现List数据结构的存储和运算，实现的类或函数放在一个头文件“List.h”中， 可以被别的函数使用；2设计另外的函数，利用已实现的“List.h”中的相关功能，实现任意两个列表的合并运算。3 LinkedList工具设计LinkedList是List的链式实现，其具体的功能和实现要求同List。4 Stack和Queue工具设计Stack是后进先出(LIFO)的堆栈。它支持以下运算：boolea n empty()测试堆栈是否为空。1E
6、 peek()查看栈顶元素而不移除它。2E pop()移除栈顶元素并作为此函数的值返回该元素。3E push(E item)把项压入栈顶。Queue是先进先出(FIFO)的队列。它支持以下运算：1boolea n empty()测试队列是否为空。2E peek()查看队头元素而不移除它。3E DeQueue()移除队头元素并作为此函数的值返回该元素。4E DeQueue(E item)把元素插入队尾。要求：1用类或函数实现Stack和Queue数据结构的存储和运算，实现的类或函数分别放在头文 件“Stack.h”和“Queue.h”中，可以被别的函数使用；2设计一个函数，利用已经实现的“Sta
7、ck.h”中Stack的相关功能，实现一个任意序列的 逆置操作；设计另外的一个函数，利用已经实现的“Queue.h”中Queue的相关功能，实 现任意两个队列的合并运算。5 HashTable工具设计实现一个哈希表HashTable将键映射到相应的值。它支持以下运算：void clea r()将此哈希表清空，使其不包含任何键。E get(Object key)返回此哈希表中指定键所映射到的值。boolea n isEmpty()测试此哈希表是否为空。K keys()返回此哈希表中的所有的键的集合。E put(K key, V value)将指定key映射到此哈希表中的指定value。E r e
8、move(Object key)从哈希表中移除该键及其相应的值。int size()返回此哈希表中的键的数量。String toSt rin g()返回此Hashtable元素的字符串表示形式，其形式为ASCII字符“，”(逗号加空格) 分隔开的、括在括号中的一组条目。E values()返回此Hashtable中所包含值的集合。要求：1用类或函数实现HashTable数据结构的存储和运算，实现的类或函数放在头文件 “HashTable.h”中，可以被别的函数使用；2设计一个函数，利用已经实现的“HashTable.h”中的相关功能，实现一个集体中人名的 哈希表。6 Tree工具设计实现一个二
9、叉树Bi nary Tree,它支持以下运算：BiT ree In itBiT ree()构造空二叉树。Void Dest royBiT ree ()销毁二叉树。BiT ree Cr eateBiT ree ()创建一棵非空二叉树。Boolea n IsEmpty()判断二叉树是否为空。BiT ree Root()返回此二叉树的根节点。E Value(BiTree p)返回此二叉树中节点p的值。Void Assig n( BiT ree p, E e)将此二叉树中节点p的值赋为e。BiT ree Paren t(BiT ree p)返回此二叉树中节点p的双亲。BiT ree LeftChild
10、(BiT ree p)返回此二叉树中节点p的左孩子。BiT ree RightChild(BiTree p)返回此二叉树中节点p的右孩子。Void InsertLChild(BiTree p, BiTree c)(可选操作)向此二叉树插入一棵子树c (c的右子树为空)作为p的左孩子，p原来的左子树变为c的 右子树。Void InsertRChild(BiTree p, BiTree c)(可选操作)向此二叉树插入一棵子树c(c的右子树为空)作为p的右孩子，p原来的右子树变为c的 右子树。Void DeleteLChild(BiTree p)(可选操作)删除此二叉树中p节点的左子树。Void D
11、eleteRChild(BiTree p)(可选操作)删除此二叉树中p节点的左子树。int Depth()返回此二叉树的深度。String PreOrderTraver se()返回二叉树的先序遍历序列。String InOrderTr ave rse()返回二叉树的中序遍历序列。String PostO rderTraver se()返回二叉树的后序遍历序列。String Level OrderTraver se()返回二叉树的层次遍历序列。要求：1用类或函数实现BinaryTree数据结构的存储和运算，实现的类或函数放在头文件“Bi nary Tree.h”中，可以被别的函数使用；2设计一
12、个函数，利用已经实现的“BinaryTree.h”中的相关功能，输出一棵二叉树的所有叶 子节点。7 BinarySortTree 工具设计实现一个二叉排序树Binar ySo rtTr ee,它支持以下运算：BiT ree In itBST ree()构造空二叉排序树。Void Dest royBST ree ()销毁二叉排序树。BiT ree Sea rchBSTree (key)查找二叉排序树中关键字等于key的元素，若找到，返回该元素在树中的位置，否则返回 空。Void Inser tBSTree(E e)若此二叉排序树中不存在关键字等于e.key的元素，则插入e。Void Delete
13、BST ree(E e)若此二叉排序树中存在关键字等于e.key的元素，则删除之。String Tr ave rseBSTree()返回此二叉树的中序遍历序列。要求：1用类或函数实现BinarySortTree数据结构的存储和运算，实现的类或函数放在头文件“Bi nar yS or tTree.h”中，可以被别的函数使用；2利用已经实现的“Bi nary Tree.h”中的相关功能，对一个已知的学生成绩表文件按照学号为 关键字生成对应的二叉排序树索引文件，并利用该文件实现相应的查找操作。8 BTree工具设计实现一个B-树BTree它支持以下运算：BTr ee In itBT ree()构造空
14、B-树。Void Dest royBT ree ()销毁B-树。BTree Sea rchBTree(key)查找B-树中关键字等于key的元素，若找到，返回该元素在树中的位置，否则返回空。Void Inser tBT ree(E e)若此B-树中不存在关键字等于e.key的元素，则插入e。Void DeleteBT ree(E e)若此B-树中存在关键字等于e.key的元素，则删除之。String Tr ave rseBTree()返回此B-树的中序遍历序列。要求：1用类或函数实现BTree数据结构的存储和运算，实现的类或函数放在头文件“BTree.h”中, 可以被别的函数使用；2利用已经实
15、现的“BT ree.h”中的相关功能，对一个已知的学生成绩表文件按照学号为关键 字生成对应的B-树索引文件，并利用该文件实现相应的查找操作。9简明汉语词典编制一个简单的词典系统，该系统要求实现词典的建立、词条的追加、维护、查询功能。 要求：(1) 词典用一个独立的文件存放，词条信息包括：词名、读音、词性、词义等；(2) 词典建立索引，该索引用分块索引或建树实现，索引也作为独立的文件放在外存；(3) 系统要求有简单的界面实现在词条追加、更改和查询时的人机交互。10基于顺序索引的通讯录编写一个简单的通讯录管理，要求实现查询、排序、修改等功能。要求 通讯录用一个独立的文件存放； 建立索引，索引也作为独立的文件放在外存； 录入或修改：录入或修改通讯信息 查询/统计：按关键字查询或统计。11基于顺序索引的员工管理每个员工的信息包括：编号、姓名、性别、出生年月、学历、职务、电话、住址等。实现对
