程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> 【C/C++學院】0903-Boost/線性表/哈希存儲

【C/C++學院】0903-Boost/線性表/哈希存儲

編輯:C++入門知識

【C/C++學院】0903-Boost/線性表/哈希存儲


boost模板庫與線性表

Boost的安裝

使用boost,首先需要進行的環境配置。

\
#include 
#include 
#include//區別

using namespace std;

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

	cin.get();
}

 

線性表順序存儲

 

Myvector.h

#pragma once

template 
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 
myvector::myvector()
{
	p = nullptr;
	n = realn = 0;
}

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

template 
void myvector::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 
void myvector::show()
{
	if (p==NULL)
	{
		return;
	}
	else
	{
	   for (int i = 0; i < realn;i++)
       {
		   cout << p[i] << "  ";
       }
	   cout << "\n";
	}
}

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

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

template 
void myvector::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 
void myvector::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 
T myvector::operator [](int i)
{
	if (i < 0 || i>=realn)
	{		
		return NULL;
	}
	return  p[i];
}

Main.cpp

#include 
#include
#include 
#include 
#include "myvector.h"
#include "myvector.cpp"//因為有template

//一定要學會自己怎麼寫模板庫
//自己寫的模板,寫的通用是很難的

using namespace std;

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

	myvector myv3;
	myv3.push_back(131);
	myv3.push_back(132);
	myv3.push_back(133);
	myv3.push_back(1337);

	myvector< myvector* > 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 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 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 myv;
	myv.push_back("av");
	myv.push_back("va");
	myv.push_back("cc");
	myv.push_back("tv");

	myv.show();

	cin.get();
}

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

void main312()
{
	myvector 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 Node
{
public:
	T t;//數據
	Node *pNext;//指針域 
};

List.h

#pragma once
#include "Node.h"
#include 

template 
class List
{
public:
	Node *pHead;

public:
	List();
	void add(T t);//尾部插入
	void show();//顯示
	Node * find(T t);//查找
	void change(Node *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 
List::List()
{
	this->pHead = nullptr;//設置空節點 
	cout << "鏈表創建" << endl;
}

template 
List::~List()
{
	cout << "鏈表銷毀" << endl;
}

template 
void List::add(T t)
{
	Node *pnew = new Node;//分配節點
	pnew->t = t;//賦值
	pnew->pNext = nullptr;

	if (pHead==nullptr)
	{		
		this->pHead = pnew;//頭結點
	} 
	else
	{
		Node *p = pHead;//獲取頭結點位置
		while (p->pNext!=nullptr)//循環到尾部
		{
			p = p->pNext;
		}
		p->pNext = pnew;
	}
}

template 
void List::show()
{
	Node *p = pHead;//獲取頭結點位置
	while (p!= nullptr)//循環到尾部
	{
		cout << p->t << "  ";
		p = p->pNext;
	}
	cout << endl;
}

template 
Node * List::find(T t)
{
	Node *p = pHead;//獲取頭結點位置
	while (p != nullptr)//循環到尾部
	{
		if (p->t==t)
		{
			return p;
		}	
		p = p->pNext;
	}
	return nullptr;
}

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

template 
int  List::getnum()
{
	int i = 0;
	Node *p = pHead;//獲取頭結點位置
	while (p != nullptr)//循環到尾部
	{
		i++;
		p = p->pNext;
	}
	return i;
}

template 
bool List::deletet(T t)
{
	Node *p = this->find(t);
	if (p==nullptr)
	{
		return  false;
	}
	else
	{		
		if (p==pHead)//頭結點
		{
			pHead = p->pNext;
			delete p;
		}
		else
		{
			Node *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 
void List::sort()
{
	for (Node *p1 = pHead; p1 != NULL;p1=p1->pNext)
	{
		for (Node *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
void List::deletesame()//重新生成
{
		Node *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
bool List::clear()
{
	if (pHead ==nullptr)
	{
		return false;
	}

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

template
//遞歸
void  List::rev()
{
	if (pHead==nullptr || pHead->pNext==nullptr)
	{
		return;
	} 
	else
	{
		Node *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
void  List::insert(T oldt, T newt)
{

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

template
void  List::merge(List & list)
{
	Node *p = pHead;//獲取頭結點位置
	while (p->pNext != nullptr)//循環到尾部
	{
		p = p->pNext;
	}
	p->pNext = list.pHead;//
}

Main.cpp

#include
#include
#include "List.h"
#include "List.cpp"
#include "Node.h"

using namespace std;

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

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

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

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

	cin.get();
}

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

void main4()
{
	List * pmylist = new List;
	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  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 * pmylist = new List;
	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 * pmylist =new List;
	pmylist->add(11);
	pmylist->add(12);
	pmylist->add(13);
	pmylist->add(15);
	pmylist->show();
	Node *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 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 Hash
{
public:
	hashnode *p;//p->存儲哈希表
	int n;//長度
public:
	 int   myhash(int key );
	 void init(T * pt, int nt);

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

Hash.cpp

#include "Hash.h"

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

template
Hash::~Hash()
{
	delete[] p;
}

template
int  Hash::myhash(int key)
{
	return key % n;
}

template
void Hash::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
bool  Hash::isin(int key,T t)
{
	int res = myhash(key);
	if (p[res].t==t)
	{
		return true;
	}
	else
	{
		return false;
	}
}

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

Main.cpp

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

void main()
{	
	Hash 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 *p = myhash.find(8);
	cout << p->key << endl;
	cout << p->t << endl;

	cin.get();
}

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved