set和map的简单实现_haodynasty的博客-程序员秘密

技术标签： set  实现  算法学习  map  

1.Set的简单实现

set是利用二叉查找树来实现的,而且为了查找方便，添加了另外两个指针，一个指向下一个最小结点，一个指向上一个最大结点。

iset.h

 

//利用二叉查找树实现set
#ifndef ISET_H
#define ISET_H

template<class T>
struct Node{
	T data;
	Node<T> *rchild, *lchild; //左右孩子
	Node<T> *parent;					//父结点
	Node<T> *next, *pre; 			//下一个最小和上一个最大的结点
	Node(){
		rchild = lchild = parent = 0;
		next = pre = 0;
	}
};

template<class T>
class ISet{
	public:
		ISet();
		ISet(T a[], int n);
		~ISet();
		int size();
		bool isEmpty();
		bool contains(T t);
		T* toArray();
		void add(T t);
		void remove(T t);
		void addAll(T a[], int n);
		void removeAll();
		void clear();
		void print();
		
		//下面实现迭代器
		typedef Node<T>* iterator;
    typedef const Node<T>* const_iterator;
    iterator Iterator();
    const_iterator Iterator() const;
    iterator next();
    const_iterator next() const;
    iterator pre();
    const_iterator pre() const;
    bool hasNext();
		bool hasPre();   
		//还可以操作符重载，++，--，+实现通用的迭代器 
	private:
		Node<T>* root;
		Node<T> *head, *tail;		//头（最小）和尾（最大）
		void clear(Node<T>* &root);
		int size(Node<T>* root);
		void print(Node<T>* root);
		void toArray(Node<T>* root, T* &a, int *i);
		void deleteNode(Node<T>* &root, Node<T>* r, Node<T>* pre);//删除结点p
		void preSet(Node<T>* t);
		void nextSet(Node<T>* t);
};
#endif

 iset.cpp

 

#include <iostream>
#include "iset.h"
using namespace std;


template<class T>
ISet<T>::ISet(){
	head = tail = root = NULL;
}

template<class T>
ISet<T>::ISet(T a[], int n){
	head = tail = root = NULL;
	addAll(a, n);
}
	
template<class T>
ISet<T>::~ISet(){
	clear();
}

template<class T>
int ISet<T>::size(){
	return size(root);
}

template<class T>
bool ISet<T>::isEmpty(){
	if(!root) return true;
	return false;
}

template<class T>
bool ISet<T>::contains(T t){
	Node<T>* r = root;
	while(r){
		if(r->data == t) break;
		r = (r->data > t)?r->lchild:r->rchild;
	}
	//如果没找到，返回false
	if(!r) return false;
	return true;
}

template<class T>
T* ISet<T>::toArray(){
	T *a = new T[size()];
	int i = 0;
	toArray(root, a, &i);
	return a;
}

template<class T>
void ISet<T>::add(T x){
	Node<T>* r = root, *m = NULL, *n = NULL;
	if(r == NULL){
		Node<T>* t = new Node<T>;
		t->data = x;
		root = t;//必须设置新的root结点，因为t和root在内存指向位置不同
	}else{
		Node<T>* p = r;
		//查找待插入结点位置
		while(r){
			if(r->data == x){
				return;
			}
			p = r;
			if(r->data > x){
				n = r;
				r = r->lchild;
			}else{
				m = r;
				r = r->rchild;
			}
		}
		Node<T>* t = new Node<T>;
		t->data = x;
		if(p->data > x){//插入左
			p->lchild = t;
			p->pre = t;
		}else{
			p->rchild = t;
			p->next = t;
		}
		t->parent = p;
		preSet(t);
		nextSet(t);
		if(m && m!=p) nextSet(m);
		if(n && n!=p) preSet(n);
	}
}

template<class T>
void ISet<T>::remove(T x){
	if(!root) return;
	Node<T>* pre = NULL, *r = root;
	//查找待删除结点位置(pre是r的前序结点)
	while(r){
			if(r->data == x){
				break;
			}
				
			pre = r;
			r = (r->data > x)?r->lchild:r->rchild;
	}
	//没找到
	if(!r){ cout<<"没有待删除的值："<<x<<endl; return;}
	//如果pre == NULL说明是root结点
	deleteNode(root, r, pre);
}

template<class T>
void ISet<T>::addAll(T a[], int n){
	if(n <= 0) return;
	for(int i=0; i<n; i++){
		add(a[i]);
	}
}

template<class T>
void ISet<T>::removeAll(){
	clear();
}

template<class T>
void ISet<T>::clear(){
	clear(root);
	//注：当clear之后，root也被delete，故而重新置为NULL
	root = NULL;
}
	
template<class T>
void ISet<T>::print(){
	print(root);
}

template<class T>
void ISet<T>::print(Node<T>* root){
	if(root){
		cout<<root->data<<" ";
		print(root->lchild);
		print(root->rchild);
	}
}

template<class T>
void ISet<T>::clear(Node<T>* &root){
	if(root){
		clear(root->lchild);
		clear(root->rchild);
		delete root;
	}
}

template<class T>	
int ISet<T>::size(Node<T>* root){
	if(!root) return 0;
	else{
		return size(root->lchild)+size(root->rchild)+1;
	}
}

template<class T>
void ISet<T>::toArray(Node<T>* root, T* &a, int *i){
	if(root){
		a[(*i)++] = root->data;
		toArray(root->lchild, a, i);
		toArray(root->rchild, a, i);
	}
}

//r为待删除结点，pre为r的双亲
template<class T>
void ISet<T>::deleteNode(Node<T>* &root, Node<T>* r, Node<T>* pre){
	Node<T>* p;
	//先修改待删除r的pre,next结点指针
	if(r->pre){
		r->pre->next = r->next;
	}
	if(r->next){
		r->next->pre = r->pre;
	}
	if(!r->rchild && !r->lchild){			//如果是叶子结点
		if(pre){
			if(pre->lchild == r){
				pre->lchild = NULL;
			}else{
				pre->rchild = NULL;
			}
		}else{
			root = NULL;
		}
		delete r;
	}else if(r->rchild && r->lchild){			//如果左右子树都有(还有一种处理办法就是用右子树的最左结点替换待删除结点，然后删除最左结点)
		p = r;
		//寻找右子树的最左结点
		r = r->rchild;
		while(r->lchild){
		 r = r->lchild;
		}
		//将删除结点的左结点接到找到的最左结点之后
		r->lchild = p->lchild;
		r->lchild->parent = r;
		//删除结点(如果pre是空，说明删除结点是根结点,不用改变前序结点指针)
		if(pre){
			if(pre->lchild == p){ 
				pre->lchild = p->rchild;
			}else{ 
				pre->rchild = p->rchild;
			}
			p->rchild->parent = pre;
		}else{
			p->rchild->parent = NULL;
			root = p->rchild;
		}
		delete p;
	}else if(r->lchild){			//如果只有左子树
		p = r;
		if(pre){
			if(pre->lchild == p) pre->lchild = r->lchild;
			else pre->rchild = r->lchild;
			r->lchild->parent = pre;
		}else{
			r->lchild->parent = NULL;
			root = r->lchild;
		}

		delete p;
	}else{					//如果只有右子树
		p = r;
		if(pre){
			if(pre->lchild == p) pre->lchild = r->rchild;
			else pre->rchild = r->rchild;
			r->rchild->parent = pre;
		}else{
			r->rchild->parent = NULL;
			root = r->rchild;
		}
		delete p;
	}
}


template<class T>
void ISet<T>::preSet(Node<T>* t){
	if(!t) return;
	Node<T>* p;
	//如果t有左孩子，则pre就是左孩子的最右结点
	p = t->lchild;
	if(p){
		while(p->rchild){
				p = p->rchild;
		}
		t->pre = p;
	}else{//p是空
		p = t;
		if(!t->parent){
			t->pre = NULL;
		}else if(t->parent->lchild == t){//若p为左孩子,则回朔，直到遇到结点是右孩子
			while(p->parent){
				if(p->parent->rchild == p) break;
				p = p->parent;
			}
			t->pre = p->parent;
		}else{																		//若p为右孩子,则pre是其父
			t->pre = t->parent;
		}
	}
}

template<class T>
void ISet<T>::nextSet(Node<T>* t){
	if(!t) return;
	Node<T>* p;
	//如果t有右孩子，则next就是有孩子的最左结点
	p = t->rchild;
	if(p){
		while(p->lchild){
			p = p->lchild;
		}
		t->next = p;
	}else{
		p = t;
		if(!t->parent){
			t->next = NULL;
		}else if(t->parent->rchild == t){
			while(p->parent){
				if(p->parent->lchild == p) break;
				p = p->parent;
			}
			t->next = p->parent;
		}else{
			t->next = p->parent;
		}
	}
}

template<class T>
typename ISet<T>::iterator ISet<T>::Iterator(){
	if(!root) return NULL;
	Node<T>* p = root;
	while(p->lchild){
		p = p->lchild;
	}
	head = p;
	p = root;
	while(p->rchild){
		p = p->rchild;
	}
	tail = p;
	return head;
}

template<class T>
typename ISet<T>::const_iterator ISet<T>::Iterator() const{
	if(!root) return NULL;
	Node<T>* p = root;
	while(p->lchild){
		p = p->lchild;
	}
	head = p;
	p = root;
	while(p->rchild){
		p = p->rchild;
	}
	tail = p;
	return head;
}

template<class T>
typename ISet<T>::iterator ISet<T>::next(){
	Node<T>* t;
	if(head){
		t = head;
		head = head->next;
		return t;
	}
	return NULL;
}

template<class T>
typename ISet<T>::const_iterator ISet<T>::next() const{
	Node<T>* t;
	if(head){
		t = head;
		head = head->next;
		return t;
	}
	return NULL;
}

template<class T>
typename ISet<T>::iterator ISet<T>::pre(){
	Node<T>* t;
	if(tail){
		t = tail;
		tail = tail->pre;
		return t;
	}
	return NULL;
}

template<class T>
typename ISet<T>::const_iterator ISet<T>::pre() const{
	Node<T>* t;
	if(tail){
		t = tail;
		tail = tail->pre;
		return t;
	}
	return NULL;
}

template<class T>
bool ISet<T>::hasNext(){
	if(head) return true;
	return false;
}

template<class T>
bool ISet<T>::hasPre(){
	if(tail) return true;
	return false;
}

main.cpp

 

#include <iostream>
#include "iset.cpp"
using namespace std;

int main(){
	int a[] = {19, 38,1,41,39,54,6,3};
	ISet<int> s(a, 8);
	s.print();
	cout<<endl;
	/*
	int n = s.size();
	cout<<"size:"<<n<<endl;
	cout<<"isEmpty:"<<s.isEmpty()<<endl;
	cout<<"contains 4:"<<s.contains(4)<<endl;
	cout<<"contains 90:"<<s.contains(90)<<endl;
	
	
	int *k = new int[n];
	k = s.toArray();
	for(int i=0; i<n; i++){ cout<<k[i]<<" ";}
	cout<<endl;
	delete k;
	
	cout<<"添加5\n";
	s.add(5);
	cout<<"size:"<<s.size()<<endl;
	s.print();
	
	cout<<"\n添加10\n";
	s.add(10);
	cout<<"size:"<<s.size()<<endl;
	s.print();
	
	cout<<"\n删除10\n";
	s.remove(10);
	s.print();
	
	cout<<"\n添加三个集合(一个重合)";
	int m[] = {4,12,6};
	s.addAll(m, 3);
	cout<<"\nsize:"<<s.size()<<endl;
	s.print();
	
	s.removeAll();
	cout<<"\nsize:"<<s.size()<<endl;
	s.print();
	*/
	
	ISet<int>::iterator ite = s.Iterator();
	while(s.hasNext()){
		cout<<s.next()->data<<" ";
	}
	
	s.remove(41);
	
	cout<<endl;
	ite = s.Iterator();
	while(s.hasNext()){
		cout<<s.next()->data<<" ";
	}
	
	s.add(10);
	
	cout<<endl;
	while(s.hasPre()){
		cout<<s.pre()->data<<" ";
	}
	
	cout<<endl;
	return 0;
}
 

 

 

2.Map的简单实现

map也是利用二叉树实现

imap.h

 

//二叉排序树
#ifndef IMAP_H
#define IMAP_H

//数据域，里面存放结点数据
template<class K, class V>
struct Data{
	K key;			//结点数据
	V value;
};

template<class K, class V>
struct Node{
	Data<K, V> data;
	Node<K, V> *rchild, *lchild;
	Node(){
		rchild = lchild = 0;
	}
};

template<class K, class V>
class IMap{
	public:
		IMap();
		~IMap();
		int size();
		bool isEmpty();
		bool containsKey(K key);
    bool containsValue(V value);
		V get(K key);
		void put(K key, V value);			//若插入的值已经存在，则更新value
		V remove(K key);
		void clear();
		void print();
	private:
		Node<K, V>* root;
		Node<K, V>* pre;//用于递归插入时，记录前序结点
		void print(Node<K, V>* root);
		void clear(Node<K, V>* &root);
		int size(Node<K, V>* root);
		void containsValue(Node<K, V>* root, V value, bool *b);
		void deleteNode(Node<K, V>* &root, Node<K, V>* r, Node<K, V>* pre);//删除结点p
};
#endif

 imap.cpp

 

#include <iostream>
#include "imap.h"
using namespace std;

template<class K, class V>
IMap<K, V>::IMap(){
	pre = NULL;
	root = NULL;
}

template<class K, class V>
IMap<K, V>::~IMap(){
	clear();
}

template<class K, class V>
int IMap<K, V>::size(){
	return size(root);
}

template<class K, class V>
bool IMap<K, V>::isEmpty(){
	if(!root) return true;
	return false;
}
		
template<class K, class V>
bool IMap<K, V>::containsKey(K key){
	Node<K, V>* r = root;
	while(r){
		if(r->data.key == key) break;
		r = (r->data.key > key)?r->lchild:r->rchild;
	}
	//如果没找到，返回false
	if(!r) return false;
	return true;
}

template<class K, class V>
bool IMap<K, V>::containsValue(V value){
	bool b = false;
	containsValue(root, value, &b);
	return b;
}

template<class K, class V>
V IMap<K, V>::get(K key){
	Node<K, V>* r = root;
	while(r){
		if(r->data.key == key) break;
		r = (r->data.key > key)?r->lchild:r->rchild;
	}
	if(!r) return 0;
	return r->data.value;
}

template<class K, class V>
void IMap<K, V>::put(K key, V value){
	cout<<"插入<"<<key<<", "<<value<<">\n";
	Node<K, V>* r = root;
	if(r == NULL){
		Node<K, V>* t = new Node<K, V>;
		t->data.key = key;
		t->data.value = value;
		t->lchild = t->rchild = NULL;
		root = t;//必须设置新的root结点，因为t和root在内存指向位置不同
	}else{
		Node<K, V>* p = r;
		//查找待插入结点位置
		while(r){
			//如果已经存在，则更新value
			if(r->data.key == key){
				r->data.value = value;
				return;
			}
			p = r;
			r = (r->data.key > key)?r->lchild:r->rchild;
		}
		Node<K, V>* t = new Node<K, V>;
		t->data.key = key;
		t->data.value = value;
		t->lchild = t->rchild = NULL;
		if((p->data).key > key){//插入左
			p->lchild = t;
		}else{
			p->rchild = t;
		}
	}
}

template<class K, class V>
V IMap<K, V>::remove(K key){
	if(!root) return 0;
	Node<K, V>* pre = NULL, *r = root;
	//查找待删除结点位置(pre是r的前序结点)
	while(r){
			if(r->data.key == key){
				break;
			}
				
			pre = r;
			r = (r->data.key > key)?r->lchild:r->rchild;
	}
	//没找到
	if(!r) return 0;
	//如果pre == NULL说明是root结点
	deleteNode(root, r, pre);
	return r->data.value;
}

template<class K, class V>
void IMap<K, V>::clear(){
	clear(root);
	root = NULL;
}

template<class K, class V>
void IMap<K, V>::print(){
	print(root);
}

template<class K, class V>
void IMap<K, V>::print(Node<K, V>* root){
	if(root){
		cout<<root->data.value<<" ";
		print(root->lchild);
		print(root->rchild);
	}
}

template<class K, class V>
void IMap<K, V>::clear(Node<K, V>* &root){
	if(root){
		clear(root->lchild);
		clear(root->rchild);
		delete root;	
	}
}

template<class K, class V>
int IMap<K, V>::size(Node<K, V>* root){
	if(!root) return 0;
	else{
		return size(root->lchild)+size(root->rchild)+1;
	}
}

template<class K, class V>
void IMap<K, V>::containsValue(Node<K, V>* root, V value, bool *b){
	if(root){
		if(root->data.value == value){ 
			*b = true;
			return;
		}
		containsValue(root->lchild, value, b);
		containsValue(root->rchild, value, b);
	}
}

template<class K, class V>
void IMap<K, V>::deleteNode(Node<K, V>* &root, Node<K, V>* r, Node<K, V>* pre){
	Node<K, V>* p;
	if(!r->rchild && !r->lchild){			//如果是叶子结点
		if(pre){
			if(pre->lchild == r){
				pre->lchild = NULL;
			}else{
				pre->rchild = NULL;
			}
		}else{
			root = NULL;
		}
		delete r;
	}else if(r->rchild && r->lchild){			//如果左右子树都有(还有一种处理办法就是用右子树的最左结点替换待删除结点，然后删除最左结点)
		p = r;
		//寻找右子树的最左结点
		r = r->rchild;
		while(r->lchild){
		 r = r->lchild;
		}
		//将删除结点的左结点接到找到的最左结点之后
		r->lchild = p->lchild;
		//删除结点(如果pre是空，说明删除结点是根结点,不用改变前序结点指针)
		if(pre){
			if(pre->lchild == p) pre->lchild = p->rchild;
			else pre->rchild = p->rchild;
		}else{
			root = p->rchild;
		}
		delete p;
	}else if(r->lchild){			//如果只有左子树
		p = r;
		if(pre){
			if(pre->lchild == p) pre->lchild = r->lchild;
			else pre->rchild = r->lchild;
		}else{
			root = r->lchild;
		}
		delete p;
	}else{					//如果只有右子树
		p = r;
		if(pre){
			if(pre->lchild == p) pre->lchild = r->rchild;
			else pre->rchild = r->rchild;
		}else{
			root = r->rchild;
		}
		delete p;
	}
}

 main.cpp

 

#include <iostream>
#include "imap.cpp"
using namespace std;

int main(){
	IMap<int, int> map;
	cout<<"当前map："<<map.isEmpty()<<endl;
	cout<<"当前map长度："<<map.size()<<endl;
	map.print();
	
	int key[] = {0,1,2,3,4,5,6,7,8,9};
	int value[] = {21,34,32,34,56,6,78,76,111,13};
	for(int i=0; i<10; i++){
		map.put(key[i], value[i]);
	}
	cout<<"当前map长度："<<map.size()<<endl;
	map.print();
	cout<<endl;
	
	bool b = map.containsKey(5);
	if(b) cout<<"包含键5："<<map.get(5)<<endl;
	else cout<<"不包含键5\n";
		
	b = map.containsKey(12);
	if(b) cout<<"包含键12："<<map.get(12)<<endl;
	else cout<<"不包含键12\n";
		
	b = map.containsValue(111);
	if(b) cout<<"包含值111："<<111<<endl;
	else cout<<"不包含值111\n";
	
	b = map.containsValue(211);
	if(b) cout<<"包含值211："<<211<<endl;
	else cout<<"不包含值211\n";
		
	cout<<"移除6\n";
	map.remove(6);
	cout<<"当前map长度："<<map.size()<<endl;
	map.print();
	cout<<endl;
	
	cout<<"移除90\n";
	map.remove(90);
	map.print();
	cout<<endl;
	
	return 0;
}
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://blog.csdn.net/haodynasty/article/details/84271618

智能推荐

qt跟随鼠标动态绘制_基于QCustomPlot绘图，鼠标跟随动态显_weixin_39979516的博客-程序员秘密

#include "MyTracer.h"XxwTracer::XxwTracer(QCustomPlot*_plot, TracerType _type, QObject *parent): QObject(parent),m_plot(_plot),m_type(_type){m_visible= true;m_tracer= Q_NULLPTR;//跟踪的点m_label = Q_NULLP...

手写一个简单到SpirngMVC框架_野狗道人 | jay的博客-程序员秘密

前提：spring对于java程序员来说，无疑就是吃饭到筷子。在每次编程工作到时候，我们几乎都离不开它，相信无论过去，还是现在或是未来到一段时间，它仍会扮演着重要到角色。自己对spring有一定的自我见解，所以参考网上的视频和文章，整理出一套简单的SpirngMVC。内容较多，项目地址先贴出来，接下来大概讲下流程。手写简单的SpringMvc框架。主要分为几个步骤：扫描包下面的文件。根据扫描到到文件，初始化bean工厂。根据@Controller @RequestMapping 注解，处理映

已开源！通过高度驱动的注意力网络改善城市场景语义分割 | CVPR2020_AI算法修炼营的博客-程序员秘密

点击上方“AI算法修炼营”，选择加星标或“置顶”标题以下，全是干货论文地址：https://arxiv.org/abs/2003.05128代码地址：https://github.co...

jdk8_Stream流使用-映射_silly8543的博客-程序员秘密

map()实现类型转换接收一个函数作为方法参数，这个函数会被应用到集合中每一个元素上，并最终将其映射为一个新的元素案例：将List 转换Listpublic class MapDemo { static class KeyValue { private Integer key; private String value; public KeyValue(Integer key, String value) { thi

使用MATLAB多项式曲线拟合实现_chungle的博客-程序员秘密

使用MATLAB多项式曲线拟合实现&amp;lt;script&amp;gt;&amp;lt;/script&amp;gt;%多项式曲线拟合x=[-3.6 -1.8 0 3.3 4 5 6 6.4 7 7.4 8 8.6 9 10 15 26 27 28 29 30 31 32 33 34 35 36 37 38 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 5...

STM32_adc_zgc261的博客-程序员秘密

static void RCC_Configuration(void);static void GPIO_Configuration(void);static void ADC_Configuration(void);static void DMA_Configuration(void); void SetupADC(void) { RCC_Configur

随便推点

【转帖】C继承和多态_christina123y的博客-程序员秘密

<br /> 今天由于工作需要，暂时搁置一下，今晚先不学习鸟哥了， 因为今天还有任务需要完成。但根据自己遇到的问题，进行一篇好文章的转帖。以后需要的时候可以用。<br /> <br />从 http://www.congci.com/item/cjichengduotai 中转<br /> <br /> 1、引言<br />继承和多态是面向对象语言最强大的功能。有了继承和多态，我们可以完成代码重用。在C中有许多技巧可以实现多态。本文的目的就是演示一种简单和容易的技术，在C中应用继承和多态。通过创建一个V

servlet3.0新特性AsyncContext_为爱停留的博客-程序员秘密

在servlet同步请求中，当一个http请求过来的时候，务器端tomcat的线程池都要分配一个线程去处理这个请求，如果这个请求耗时很长，则这个线程会一直占用，则tomcat线程池容易爆满在servlet3.0新特性AsyncContext出现之后，及tomcat7之后，当服务端，开启AsyncContext处理的时候，就可以释放这个线程，供其他客户端使用，这样可以大大提高整个系统的并发性，但是服务端需要保存客户端状态信息，占用一定的内存资源，下面举一个实例：@[email protected]

QT编译Mysql驱动文件_波妞ιουε宗介的博客-程序员秘密

QT编译Mysql驱动文件

设计模式之适配器模式(Adapter)_silly8543的博客-程序员秘密

将一个类的接口转换成客户期望的另一个接口

u-boot-2009.08在mini2440上的移植 增加yaffs2文件系统_chungle2011的博客-程序员秘密

http://www.linuxidc.com/Linux/2011-05/35982p5.htm移植环境1，主机环境：VMare下CentOS 5.5 ，1G内存。2，集成开发环境：Elipse IDE3，编译编译环境：arm-linux-gcc v4.4.3，arm-none-eabi-gcc v4.5.1。4，开发板：mini2440，2M nor

STM32F4开发板----ADC（005）_klaus_x的博客-程序员秘密

ADC的认识1 ADC初始化参数/* Exported types ------------------------------------------------------------*//** * @brief ADC Init structure definition */typedef struct{ uint32_t ADC_Resoluti...

推荐文章

热门文章

相关标签