【C/C++学院】0903-Boost/线性表/哈希存储

boost模板库与线性表

Boost的安装 

使用boost，首先需要进行的环境配置。

#include <iostream>
#include <string>
#include<boost/array.hpp>//区别

using namespace std;

void main()
{
	boost::array<int, 10> myarray = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
	boost::array<int, 10>::iterator ibegin = myarray.begin();
	boost::array<int, 10>::iterator iend = myarray.end();
	for (;ibegin!=iend;ibegin++)
	{
		cout << *ibegin << endl;
	}

	cin.get();
}

线性表顺序存储

Myvector.h

#pragma once

template <class T>
class myvector
{
public:
	myvector();
	~myvector();
	void push_back(T t);
	//增 删 查 改
	T *find(T t);
	void change(T*pos, T t);
	void del(T t);
	void show();
	T operator [](int i);

	void insert(T findt, T t);
public:
	T *p;
	int n;//标记内存长度
	int realn;//实际长度
};

Myvector.cpp

#include "myvector.h"

template <class T>
myvector<T>::myvector()
{
	p = nullptr;
	n = realn = 0;
}

template <class T>
myvector<T>::~myvector()
{
	if (p!=nullptr)
	{
		delete  []p;
		p = nullptr;//清空
	}
}

template <class T>
void myvector<T>::push_back(T t)
{
	if (p==nullptr)
	{
		p = new T;//分配内存
		*p = t;//赋值
		realn = n = 1;
	} 
	else
	{
		T *ptemp = new T[n + 1];//重新分配内存
		for (int i = 0; i < n;i++)
		{
			*(ptemp + i) = *(p + i);//拷贝
		}
		*(ptemp + n) = t;//赋值最后一个元素
		delete []p;

		p = ptemp;

		realn += 1;
		n += 1;
	}
}


template <class T>
void myvector<T>::show()
{
	if (p==NULL)
	{
		return;
	}
	else
	{
	   for (int i = 0; i < realn;i++)
       {
		   cout << p[i] << "  ";
       }
	   cout << "\n";
	}
}

template <class T>
T *  myvector<T>::find(T t)
{
	for (int i = 0; i < realn; i++)
	{
		if (t==*(p+i))
		{
			return p + i;
		}
	}
	return nullptr;
}

template <class T>
void myvector<T>::change(T*pos, T t)
{
	if (pos==nullptr)
	{
		return;
	}
	else
	{
		*pos = t;
	}
}

template <class T>
void myvector<T>::del(T t)
{
	int pos = -1;
	for (int i = 0; i < realn; i++)
	{
		if (t == *(p + i))
		{
			pos = i;
			break;
		}
	}
	if (pos!=-1)
	{
		if (pos== realn-1)
		{
			realn -= 1;
		}
		else 
		{
			for (int i = pos; i < realn-1;i++)
			{
				p[i] = p[i + 1];
			}
			realn -= 1;
		}		
	}
}

template <class T>
void myvector<T>::insert(T findt, T t)
{
	if (n == realn)
	{
		{
		   int pos = -1;
		   for (int i = 0; i < realn; i++)
		   {
			  if (findt== *(p + i))
			   {
				pos = i;
				break;
			    }
		   }
		   if (pos!=-1)
		   {
			   //重新分配内存并拷贝
			   {
				   T *ptemp = new T[n + 1];//重新分配内存

				   for (int i = 0; i < n; i++)
				   {
					   *(ptemp + i) = *(p + i);//拷贝
				   }
				   delete[] p;
				   p = ptemp;
				   realn += 1;
				   n += 1;
			   }

			   for (int  i = realn - 2; i>=pos;i--)
			   {
				    p[i + 1]=p[i];//往前移动

			   }
			   p[pos] = t;
		   }
	    }	
	}
	else
	{
		int pos = -1;
		for (int i = 0; i < realn; i++)
		{
			if (findt == *(p + i))
			{
				pos = i;
				break;
			}
		}
		if (pos != -1)
		{
			for (int i = realn - 1; i >= pos; i--)
			{
				p[i + 1] = p[i];//往前移动

			}
			p[pos] = t;
		    realn += 1;
		}
	}
}

template <class T>
T myvector<T>::operator [](int i)
{
	if (i < 0 || i>=realn)
	{		
		return NULL;
	}
	return  p[i];
}

Main.cpp

#include <iostream>
#include<stdlib.h>
#include <vector>
#include <string>
#include "myvector.h"
#include "myvector.cpp"//因为有template

//一定要学会自己怎么写模板库
//自己写的模板，写的通用是很难的

using namespace std;

void main()
{
	myvector<int> myv1;
	myv1.push_back(11);
	myv1.push_back(12);
	myv1.push_back(13);
	myv1.push_back(14);
	myv1.push_back(15);
	myvector<int> myv2;
	myv2.push_back(31);
	myv2.push_back(32);
	myv2.push_back(33);

	myvector<int> myv3;
	myv3.push_back(131);
	myv3.push_back(132);
	myv3.push_back(133);
	myv3.push_back(1337);

	myvector< myvector<int>* > myvv;//自己写的模板嵌套用指针

	myvv.push_back(&myv1);
	myvv.push_back(&myv2);
	myvv.push_back(&myv3);
	myvv[0]->show();
	myvv[1]->show();
	myvv[2]->show();

	cin.get();
}

void main1()
{
	myvector<int> myv;
	myv.push_back(11);
	myv.push_back(12);
	myv.push_back(13);
	myv.push_back(14);
	myv.push_back(15);
	myv.show();

	cin.get();
}

void main2()
{
	myvector<double> myv;
	myv.push_back(11.2);
	myv.push_back(12.0);
	myv.push_back(13.5);
	myv.push_back(14.9);
	myv.push_back(15.90);
	myv.show();

	cin.get();
}

void main5()
{
	myvector<char *> myv;
	myv.push_back("av");
	myv.push_back("va");
	myv.push_back("cc");
	myv.push_back("tv");

	myv.show();

	cin.get();
}

void main4()
{
	vector<string> myv;//
	myv.push_back("av");
	myv.push_back("va");
	myv.push_back("cc");
	myv.push_back("tv");
	
	cin.get();
}

void main312()
{
	myvector<int> myv;
	myv.push_back(11);
	myv.push_back(12);
	myv.push_back(13);
	myv.push_back(14);
	myv.push_back(15);
	myv.show();
	int *p = myv.find(13);
	cout << p << endl;
	myv.change(p, 23);//
	myv.show();
	myv.del(12);
	myv.insert(23, 99);

	myv.show();

	cout << myv[2] << endl;
	cin.get();
}

线性表链式存储

Node.h

#pragma once
template <class T>
class Node
{
public:
	T t;//数据
	Node *pNext;//指针域 
};

List.h

#pragma once
#include "Node.h"
#include <iostream>

template <class T>
class List
{
public:
	Node<T> *pHead;

public:
	List();
	void add(T t);//尾部插入
	void show();//显示
	Node<T> * find(T t);//查找
	void change(Node<T> *p, T newt);//修改
	int getnum();//获取个数
	bool deletet(T t);
	void sort();
	void deletesame();//删除相同的元素
	bool clear();
	void rev();

	void insert(T oldt, T newt);
	void merge(List & list);

	~List();
};

List.cpp

#include "List.h"

template <class T>
List<T>::List()
{
	this->pHead = nullptr;//设置空节点 
	cout << "链表创建" << endl;
}

template <class T>
List<T>::~List()
{
	cout << "链表销毁" << endl;
}

template <class T>
void List<T>::add(T t)
{
	Node<T> *pnew = new Node<T>;//分配节点
	pnew->t = t;//赋值
	pnew->pNext = nullptr;

	if (pHead==nullptr)
	{		
		this->pHead = pnew;//头结点
	} 
	else
	{
		Node<T> *p = pHead;//获取头结点位置
		while (p->pNext!=nullptr)//循环到尾部
		{
			p = p->pNext;
		}
		p->pNext = pnew;
	}
}

template <class T>
void List<T>::show()
{
	Node<T> *p = pHead;//获取头结点位置
	while (p!= nullptr)//循环到尾部
	{
		cout << p->t << "  ";
		p = p->pNext;
	}
	cout << endl;
}

template <class T>
Node<T> * List<T>::find(T t)
{
	Node<T> *p = pHead;//获取头结点位置
	while (p != nullptr)//循环到尾部
	{
		if (p->t==t)
		{
			return p;
		}	
		p = p->pNext;
	}
	return nullptr;
}

template <class T>
void List<T>::change(Node<T> *p, T newt)
{
	if (p==nullptr)
	{
		return;
	}
	p->t = newt;
}

template <class T>
int  List<T>::getnum()
{
	int i = 0;
	Node<T> *p = pHead;//获取头结点位置
	while (p != nullptr)//循环到尾部
	{
		i++;
		p = p->pNext;
	}
	return i;
}

template <class T>
bool List<T>::deletet(T t)
{
	Node<T> *p = this->find(t);
	if (p==nullptr)
	{
		return  false;
	}
	else
	{		
		if (p==pHead)//头结点
		{
			pHead = p->pNext;
			delete p;
		}
		else
		{
			Node<T> *p1, *p2;
			p1 = pHead;
			p2 = p1->pNext;
			while (p2!=p)//删除一个节点，获取前一个节点
			{
				p1 = p2;
				p2 = p2->pNext;				
			}

			p1->pNext = p2->pNext;//跳过p2
			delete p2;
		}		
		return true;
	}
}


template <class T>
void List<T>::sort()
{
	for (Node<T> *p1 = pHead; p1 != NULL;p1=p1->pNext)
	{
		for (Node<T> *p2 = pHead; p2!= NULL; p2 = p2->pNext)
		{
			if (p1->t < p2->t)
			{
				T temp;
				temp = p1->t;
				p1->t = p2->t;
				p2 -> t = temp;
			}
		}
	}
}


template<class T>
void List<T>::deletesame()//重新生成
{
		Node<T> *p1, *p2;
		p1 = pHead->pNext;
		p2 = pHead;
		while (p1!=nullptr)
		{
			if (p1->t==p2->t)
			{
				//cout << "=";
				p2->pNext = p1->pNext;
				delete p1;
				p1 = p2->pNext;
			}
			else
			{
				p2 =p1;
				p1 = p1->pNext;
			}
		}
}

template<class T>
bool List<T>::clear()
{
	if (pHead ==nullptr)
	{
		return false;
	}

	Node<T> *p1, *p2;
	p1 = pHead->pNext;
	while (p1!=nullptr)
	{
		p2 = p1->pNext;
		delete p1;
		p1 = p2;
	}
	delete pHead;
	pHead = nullptr;
	return true;
}

template<class T>
//递归
void  List<T>::rev()
{
	if (pHead==nullptr || pHead->pNext==nullptr)
	{
		return;
	} 
	else
	{
		Node<T> *p1, *p2, *p3;
		p1 = pHead;
		p2 = p1->pNext;

		while (p2!=nullptr)
		{
			p3 = p2->pNext;
			p2->pNext = p1;
			p1 = p2;
			p2 = p3;
		}
		pHead->pNext= nullptr;
		pHead = p1;
	}
}

template<class T>
void  List<T>::insert(T oldt, T newt)
{

	Node<T> *p = find(oldt);
	if (p!=nullptr)
	{
		Node<T> *p1, *p2;
		p1 = pHead;
		p2 = p1->pNext;
		while (p2 != p)
		{
			p1 = p2;
			p2 = p2->pNext;
		}
		Node<T> *pnew = new Node<T>;
		pnew->t = newt;
		pnew->pNext = p2;
		p1->pNext = pnew;
	}
}

template<class T>
void  List<T>::merge(List & list)
{
	Node<T> *p = pHead;//获取头结点位置
	while (p->pNext != nullptr)//循环到尾部
	{
		p = p->pNext;
	}
	p->pNext = list.pHead;//
}

Main.cpp

#include<iostream>
#include<string>
#include "List.h"
#include "List.cpp"
#include "Node.h"

using namespace std;

void main()
{
	List<int> * pmylist1 = new List<int>;
	pmylist1->add(11);
	pmylist1->add(11);
	pmylist1->add(12);
	pmylist1->add(12);
	
	List<int> * pmylist2 = new List<int>;
	pmylist2->add(11);
	pmylist2->add(11);
	pmylist2->add(12);

	List< List<int> *>  *p=new List< List<int> *>;
	p->add(pmylist1);
	p->add(pmylist2);

	p->pHead->t->show();

	p->pHead->pNext->t->show();
	p->show();

	cin.get();
}

void main213()
{
	List<char *> cmdlist;
	cmdlist.add("china");
	cmdlist.add("calc");
	cmdlist.add("born");
	cmdlist.add("xery");
	cmdlist.show();
	
	cin.get();
}

void main4()
{
	List<int> * pmylist = new List<int>;
	pmylist->add(11);
	pmylist->add(11);
	pmylist->add(12);
	pmylist->add(12);
	pmylist->add(12);
	pmylist->add(12);
	pmylist->add(15);
	pmylist->add(11);
	pmylist->show();


	List<int>  list;
	list.add(1231);
	list.add(1232);
	list.add(1239);
	list.add(1237);
	list.show();
	pmylist->merge(list);
	pmylist->show();
	
	delete pmylist;

	cin.get();
}

void main3()
{
	List<int> * pmylist = new List<int>;
	pmylist->add(11);
	pmylist->add(11);
	pmylist->add(12);
	pmylist->add(12);
	pmylist->add(12);
	pmylist->add(12);
	pmylist->add(15);
	pmylist->add(11);
	pmylist->add(12);
	pmylist->add(12);
	pmylist->add(12);
	pmylist->add(12);
	pmylist->add(15);
	pmylist->show();
	pmylist->sort();
	pmylist->show();
	pmylist->deletesame();
	pmylist->show();
	pmylist->rev();
	pmylist->show();
	pmylist->insert(12, 1100);
	pmylist->show();
	pmylist->clear();
	pmylist->show();

	delete pmylist;

	cin.get();
}

void main1()
{
	List<int> * pmylist =new List<int>;
	pmylist->add(11);
	pmylist->add(12);
	pmylist->add(13);
	pmylist->add(15);
	pmylist->show();
	Node<int > *p = pmylist->find(13);
	pmylist->change(p, 19);
	pmylist->show();
	pmylist->deletet(15);
	pmylist->show();

	delete pmylist;

	cin.get();
}

哈希存储

插入、删除很不方便，查找最方便。O(1).

Hashnode.h

#pragma once
template<class T>
class hashnode
{
public:	
	int key;//索引
	T  t;  //代表数据
	int cn;//代表查找次数
};
//0 1 2 3 4 5 6 7 8 9   索引        //9   10，           
//10 1 2 3 4 5 6 7 8 9    数据   哈希   
//100

Hash.h

#pragma once
#include "hashnode.h"

template<class T>
class Hash
{
public:
	hashnode<T> *p;//p->存储哈希表
	int n;//长度
public:
	 int   myhash(int key );
	 void init(T * pt, int nt);

	 bool  isin(int key,T t);
	 hashnode<T> *  find(int key);
	Hash();
	~Hash();
};

Hash.cpp

#include "Hash.h"

template<class T>
Hash<T>::Hash()
{
	this->n = 10;
	this->p = new hashnode<T>[this->n];
}

template<class T>
Hash<T>::~Hash()
{
	delete[] p;
}

template<class T>
int  Hash<T>::myhash(int key)
{
	return key % n;
}

template<class T>
void Hash<T>::init(T *pt,int  nt)
{
	for (int i = 0; i < 10;i++)
	{
		p[i].key = i;
		p[i].t = pt[i];
		p[i].cn = 0;
	}
}

template<class T>
bool  Hash<T>::isin(int key,T t)
{
	int res = myhash(key);
	if (p[res].t==t)
	{
		return true;
	}
	else
	{
		return false;
	}
}

template<class T>
hashnode<T> *   Hash<T>::find(int key)
{
	int res = myhash(key);
	return  p + res;
}

Main.cpp

#include<iostream>
#include "Hash.h"
#include "Hash.cpp"
#include "hashnode.h"
using namespace std;

void main()
{	
	Hash<int> myhash;
	int a[10] = { 10, 11, 22, 33, 44, 55, 56, 67, 78, 99 };
	myhash.init(a, 10);
	cout << myhash.isin(43,43) << endl;
	hashnode<int > *p = myhash.find(8);
	cout << p->key << endl;
	cout << p->t << endl;

	cin.get();
}