【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();
}
