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

时间： 2024-09-03 22:40:44

【C/C++学院】0903-Boost/线性表/哈希存储的相关文章

数据结构的C++实现之线性表之链式存储结构以及单链表反转

为了表示每个数据元素ai与其直接后继元素ai+1之间的逻辑关系,对数据ai,除了存储其自身的信息之外,还需存储一个指示其直接后继的信息(即直接后继的存储位置).这两部分信息组成数据元素ai的存储映像,称为结点(Node).N个结点链结成一个链表,即为线性表(a1,a2,...,an)的链式存储结构,因为此链表的每个节点中只包含一个指针域,所以叫做单链表. 我们把链表中的第一个结点的存储位置叫做头指针,,为了更方便地对链表进行操作,如删除第一个结点的特殊情况(第一个结点没有前驱,而要摘除一

大话数据结构之三：线性表

1.定义: 线性表表示0个或者多个数据元素的有限序列线性表的特性有: 除第一个元素外,每一个元素均有一个直接前驱出最后一个元素外,每一个元素均有一个直接后继 2.线性表抽象数据类型 ADT List Data /*线性表的数据对象集合为{a1,a2,...,an},每个元素的类型均为DataType.其中,除第一个元素a1外, 每一个元素有且只有一个直接前驱元素,除了最后一个元素an外,每一个元素有且只有一个直接后继元素. 数据元素直接是一对一的关系.*/ Op

《数据结构与算法 C语言版》—— 2.3线性表的链式表示与实现

2.3线性表的链式表示与实现线性表的顺序存储结构的特点是逻辑关系上相邻的两个元素在物理位置上也相邻,因此可以随机存取表中任一元素,它的存储位置可用一个简单.直观的公式来表示.然而,从另一方面来看,这个特点也造成了这种存储结构的弱点:在作插入或删除操作时,需移动大量元素.本节我们将讨论线性表的另一种表示方法--链式存储结构,其特点是用一组地址任意的存储单元存储线性表中的数据元素.由于它不要求逻辑上相邻的元素在物理位置上也相邻,因此它没有顺序存储结构所具有的弱点,但同时也失去了顺序表随机存取的特点

《算法设计与分析》一一第3章　线性表的遍历

第3章线性表的遍历线性表是一种简单又广泛使用的数据结构.线性表中所有的元素组成线性序列.除头尾之外的每个元素都有唯一的前驱和后继:头元素只有后继,没有前驱,而尾元素只有前驱,没有后继.线性表的特征决定了我们很容易从头至尾依次扫描其中的每一个元素,而这一简单的遍历过程可以解决很多重要的算法问题. 线性表的遍历是在算法的简单性与高效性之间的一种权衡.基于线性表遍历的算法往往原理简单.易于实现和维护:但是其效率往往较低,有较大的提升空间.以线性表遍历为基础,我们可以进行更复杂的算法设计,例如,以遍

顺序存储线性表-数据结构顺序表的操作（c++）

问题描述数据结构顺序表的操作(c++) 求解答谢谢解决方案贴出代码而不是截图.发了帖子你难道自己不看下.这么小的字根本看不清. 解决方案二: 什么是线性表?定义:由n(n>=0)个数据类型相同的数据元素组成的有限序列.特点是:在数据元素的非空有限集合中,除第一个元素无直接前驱,最后一个元素无直接后继外,集合中其余每个元素均有唯一的直接前驱和直接后继.什么是顺序表,在这里回答一下.顺序表就是线性表的顺序存储,其特点是:物理顺序与逻辑顺序是相同的,关系线性化,结点顺序存.线性表顺序存储的表示?

线性表的链式表示

以下为操作链表的算法,该链表为动态单链表. 链表以头指针为索引,头指针指向头节点,头节点指向首节点,以此类推,直到尾节点. 头节点中不存放数据,只存放指向首节点的指针, 设置头节点的目的是为了方便对链表的操作,如果不设置头节点,而是直接由头指针指向首节点, 这样在对头指针后的节点进行插入删除操作时就会与其他节点进行该操作时有所不同,便要作为一种特殊情况来分析操作系统:ubuntu 编译软件:gcc 结果截图: 源代码: #include<stdio.h> #include<stdlib

大话数据结构六：特殊的线性表（栈）

1. 什么是栈? 栈(stack)是限定仅在表尾进行插入和删除操作的线性表. 2. 栈的特点: 1.) 栈又称为后进先出(Last In First out)的线性表,栈元素具有线性关系,即前驱后继关系. 2.) 栈的特殊之处在于:它的栈底是固定的,只允许在栈顶进行插入和删除操作. 3. 栈的顺序存储结构(Java数组实现): // 栈的数组实现, 底层使用数组: public class ArrayStack<T> { private Object[] arr; // 数组首元素作为栈底,因

大话数据结构五：线性表的链式存储结构（双向链表）

1. 双向链表:在单链表的每个结点中,再设置一个指向其前驱结点的指针域,那么在双向链表中的结点都有两个指针域,一个指向直接后继,另一个指向直接前驱. 2. 单链表和双向链表比较: 单链表:总是要从头到尾找结点,只能正遍历,不能反遍历. 双向链表: 可以从头找到尾,也可以从尾找到头,即正反遍历都可以,可以有效提高算法的时间性能,但由于每个结点需要记录两份指针,所以在空间占用上略多一点,这就是通过空间来换时间. 3. Java实现双向链表: // 双向链表 public class DoubleLi

大话数据结构四：线性表的链式存储结构（单向循环链表）

1. 单向循环链表:将单链表尾结点的指针端由空指针改为指向头结点,使整个单链表形成一个环,这种头尾相接的单链表称为单向循环链表. 2. 单向循环链表和单链表实现的区别: 1.)添加一个结点到单向循环链表末尾时,必须使其最后一个结点的指针指向表头结点,而不是象单链表那样置为null. 2.)判断是否到达表尾时,单向循环链表可以判断该结点是否指向头结点,单链表只需要知道是否为null. 3.Java实现单向循环链表: // 单向循环链表 public class CircularLinked