C++ 映射简单实现，有序链式结构存储，C++模板编程及运算符重载。
ADT过程
更多C/C++内容，关注，私信 “代码” 获取
链式结构体
更多C/C++内容，关注，私信 “代码” 获取
映射具体实现
更多C/C++内容，关注，私信 “代码” 获取
完整代码
#include <iostream>
#include <string>
using namespace std;
/*
1.map存储的是pair类型
2.具有自动排序功能
3.first 重复的处理：后面的覆盖前面的
*/
//ADT
template <typename K,typename E>
{
public:
virtual ~map(){};
virtual bool empty()const = 0;
virtual int size() const = 0;
virtual void insert(const pair<const K, E>& element) = 0;
virtual void erase(const K& key) = 0;
virtual pair<const K, E>* find(const K& key)const = 0;
};
//链表存储
template <typename K,typename E>
struct pairNode
{
pair<const K, E> element;//存储是数对类型
pairNode<K, E>* next;//指针域
pairNode(){}
pairNode(const pair<const K, E>& element):element(element){}
pairNode(const pair<const K, E>& element, pairNode<K, E>* next)
:element(element), next(next){}
};
//具体实现
template <typename K,typename E>
{
public:
//构造函数析构函数
listMap(){
firstNode = NULL;
mapSize = 0;
}
~listMap(){
pairNode<K, E>* nextNode;
while (firstNode)
{
nextNode = firstNode->next;
delete firstNode;
firstNode = nextNode;
}
}
bool empty()const{
return mapSize == 0;
}
int size() const
{
return mapSize;
}
void insert(const pair<const K, E>& element)
{
//有序存储
//1.先找到插入的合适位置
//指定位置插入：相邻的两个指针
pairNode<K, E>* pMove = firstNode, *pMoveFront=NULL;
//找第一次大于插入元素的键的位置
while (pMove != NULL&&pMove->element.first < element.first)
{
pMoveFront = pMove;
pMove = pMove->next;
}
//做重复处理 4 3
if (pMove != NULL&&pMove->element.first == element.first)
{
//插入元素值覆盖掉原来的值
pMove->element.second = element.second;
return;
}
//确定要插入,首先创建插入的结点
pairNode<K, E>* newNode = new pairNode<K, E>(element, pMove);
//头部的处理
if (pMoveFront == NULL)
firstNode = newNode;
else
pMoveFront->next = newNode;
mapSize++ ;
}
void erase(const K& key)
{
//链表的指定位置删除
pairNode<K, E>* pMove = firstNode, *pMoveFront=NULL;
//直接找等于：没有找到
while (pMove != NULL&&pMove->element.first < key)
{
pMoveFront = pMove;
pMove = pMove->next;
}
if (pMove != NULL&&pMove->element.first == key)
{
if (pMoveFront == NULL)
firstNode = pMove->next;//删除的是表头，表头给下一个结点
else
pMoveFront->next = pMove->next;
delete pMove;
mapSize--;
}
}
pair<const K, E>* find(const K& key)const
{
//链表的指定位置删除
pairNode<K, E>* pMove = firstNode, *pMoveFront;
//直接找等于：没有找到
while (pMove != NULL&&pMove->element.first < key)
{
pMoveFront = pMove;
pMove = pMove->next;
}
if (pMove != NULL&&pMove->element.first == key)
{
return &pMove->element;
}
return NULL;
}
//扩增作用
void output(ostream& out)const
{
for (pairNode<K, E>* pMove = firstNode; pMove != NULL; pMove = pMove->next)
{
cout << "[" << pMove->element.first << "]:" << pMove->element.second <<"\t";
}
cout << endl;
}
protected:
//数据成员设计
int mapSize;
pairNode<K, E>* firstNode;//表示整个map的存储空间
};
template<typename K ,typename E>
ostream &operator<<(ostream& out, const listMap<K, E>& x)
{
x.output(out);
return out;
}