广州外贸网站建设公司,济南建设网站的公司哪家好,设计签名的小程序,做国外衣服的网站有哪些上篇文章中#xff0c;给出了对于模拟实现中功能的补全#xff0c;本篇文章将优先介绍一个新的容器之后引入什么是适配器#xff0c;以及适配器的使用方法#xff0c;再通过适配器的思想来完成对于#xff0c;、优先级队列_的实现。
目录 1. deque:
1.1 什么是deque给出了对于模拟实现中功能的补全本篇文章将优先介绍一个新的容器之后引入什么是适配器以及适配器的使用方法再通过适配器的思想来完成对于、优先级队列_的实现。
目录 1. deque:
1.1 什么是deque
1.2 deque的大致原理以及其特点
2. 适配器
2.1 什么是适配器
3. Stack的模拟实现
3.1 功能实现push、pop: 3.2 功能实现top,size,empty: 3.3 测试
4. queue的模拟实现
4.1 queue的功能实现
4.2 测试
编辑5. priority_queue的模拟实现
5.1 基本框架
5.2 插入push以及向上调整函数Adjustup:
5.3 向下调整函数Adjustdown以及删除pop: 5.4 其余功能函数
5.5 测试:
6. 仿函数
6.1 仿函数的实现
6.2 测试 1. deque:
1.1 什么是deque 在对的相关实现原理进行介绍前首先来总结之前介绍的两种容器、的优缺点 对于在前面对其进行模拟实现的文章中提到可以将看作之前数据结构中的顺序表其特点是存储空间在物理以及逻辑上的连续性。因此借由连续性可以得出的优点在于通过下标可以对空间中的内容进行随机访问。并且缓存命中较高对于其缺点则是头部或者中间进行插入、删除元素时的效率过低以及一次性开辟较多空间时带来的损耗 对于同样提到可以将其看作成带哨兵位头结点的双向循环链表其特点是存储空间在逻辑上连续但是在物理上不连续。因此其优点在于任意位置的插入、删除数据时的效率以及按需申请空间不会造成浪费。但是由于其在物理上并不连续因此不能使用下标来对中的内容进行访问且缓存命中较低 不难看出两者的优点几乎可以看作对于对于二者缺点的补充。而本部分介绍的容器则可以看作是对于二者优点的一种结合。 1.2 deque的大致原理以及其特点
对于其内存管理方式采用了中控的方法具体原理如下 其中中控所代表的空间是一个指针数组里面保存了若干个指针每个指针指向了一块空间
对于开辟空间的大小有相同、不同两种方式这里采用相同进行解释即每块空间均可以存储个整型数据。对于上述容器如果需要进行头插则首先再开辟一块新的空间这里命名为然后在中插入数据即可具体结构如下 不过需要注意进行头插时插入数据的顺序并不是从前向后插入数据而是从后向前依次插入数据例如先后向插入数据。插入效果如下 在对上述结构进行尾插时只需要通过指针数组找到最后一个进行插入数据即可。即 在对于进行删除数据时例如进行头插假设删除一个数据效果如下 如果再删除一个数据此时中为空在删除数据后销毁效果如下 不难发现对于虽然其存储空间在物理上仍然保持一定的连续性但是其头删却不会向一样需要进行挪动覆盖来完成。
对于的尾删只需要找到最后一个数据所处的位置进行删除即可。 通过上述例子不难发现对于其头插、头删、尾插、尾删均有着不错的效率。并且其存储空间的结构则结合了连续空间以及不连续空间。可以说是综合了的优点并且对二者的缺点进行了一定程度的互补。 不过却并不能彻底代替和。对于其一大优点是可以通过下标来随意访问空间中的内容对于。虽然也可以实现下标访问但是其实现方法以及原理相对于 过于复杂。下面将对于实现原理进行简单的介绍。 假设需要利用下标访问第个位置的内容则可以算出需要访问的数据在第几块开辟的空间中再利用%就可以计算出需要访问的内容在空间中的具体位置。但是如果进行过次头插操作则计算时需要先剪掉油茶数据的个数即利用进行后续的计算。不过需要注意这种计算方法需要建立在每个能存储数据的个数都是相同的。 不过在对容器中间元素进行删除时为了保持每个的大小都是相同的并不能直接对于空间进行删除只能通过逐个挪动数据的方法来完成。这种方法与进行头插友删时的弊端一样效率较低。 因此将每个的空间保持一样大可以很好的满足下标访问功能的实现但是却不利于实现对于容器中间部分内容的删除以及插入。如果不限制每个存储空间的大小保持一致有利于实现容器中间部分内容的插入以及删除但是却不利于实现下标访问。前面矛盾。不过 在库中采取的方式是每个存储空间的大小保持一致。具体实现原理过于复杂本文不再过多叙述。 总结不难得出的头插头删尾插尾删均有不错的效率在接下来实现中将借助来完成实现。 2. 适配器
2.1 什么是适配器 适配器是一种设计模式(设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总结)该种模式是将一个类的接口转换成客户希望的另外一个接口。 上述给出的关于适配器的概念中提到了适配器是一种设计模式这种模式是将一个类的接口转换成另一个接口。例如对于上面给出的容器可以将其看作一个接口在对于栈和队列这两种结构的实现中引入这种接口通过中的成员函数来完成对于栈和队列的实现。对于中的成员函数大体如下 3. Stack的模拟实现
上面说到了可以利用适配器这种设计模式将作为接口来完成对于的实现具体原理如下
namespace violent1
{templateclass T, class Container dequeTclass Stack{private:Container _con;};
}
在上述代码中将容器作为一种模板引入在这个类中通过模板参数来创建成员变量_。此时_具有的所有性质因此此处也不需要编写额外的构造函数来对于成员变量进行初始化。在后面对于功能的实现中直接调用中的成员函数即可 3.1 功能实现push、pop:
直接调用的成员函数即可。
void push(const T x){_con.push_back(x);}void pop(){_con.pop_back();} 3.2 功能实现top,size,empty:
const T top(){return _con.back();}size_t size(){return _con.size();}bool empty(){return _con.empty();} 3.3 测试
通过下面的代码对于进行测试
int main()
{violent1::Stackint s;s.push(1);s.push(2);s.push(3);s.push(4);while (!s.empty()){cout s.top() ;s.pop();}return 0;
}
运行结果如下: 4. queue的模拟实现 原理与实现所用的方法基本相同只需要注意栈和队列二者本身的不同的性质即可。具体代码如下 4.1 queue的功能实现
namespace violent2
{templateclass T, class Container dequeTclass queue{public:void push(const T x){_con.push_back(x);}void pop(){_con.push_front();}const T front(){return _con.front();}const T back(){return _con.back();}size_t size(){return _con.size();}bool empty(){return _con.empty();}private:Container _con;};
} 4.2 测试
通过下面的代码对的功能进行测试
void test2()
{violent2::queueint q;q.push(1);q.push(2);q.push(3);q.push(4);cout 功能测试队列:;while (!q.empty()){cout q.front() ;q.pop();}
}
结果如下
5. priority_queue的模拟实现
5.1 基本框架
对于_虽然称之为优先级队列但是在结构上更贴近于数据结构中的堆
(注对于堆的介绍可以在一起学数据结构8——二叉树中堆的代码实现_子结点与父结交换位置-CSDN博客查看
这里不再进行过多的叙述只给出大体流程 对于_的适配器的选择为最佳。在插入结点时首先插入到堆最后的叶子结点上再利用向上调整函数对于结点的大小关系进行调整。这里默认为实现大堆即任意一个父结点都大于子结点。 对于结点的删除由于直接删除根结点可能会破坏堆的结构因此一般选择交换最后一个叶子结点与根结点删除此时的最后的叶子结点利用向下调整函数对此时的根结点进行调整。 大体框架如下
#includeiostream
#includevector
using namespace std;namespace violent3
{templateclass T, class Container vectorTclass priority_queue{public:private:Container _con;};
} 5.2 插入push以及向上调整函数Adjustup:
void push(const T x){_con.push_back(x);Adjustup(_con.size() - 1);}
void Adjustup(int child){int parent (child - 1) / 2;while (child 0){if (_con[child] _con[parent]){swap(_con[child], _con[parent]);child parent;parent (child - 1) / 2;}else{break;}}} 5.3 向下调整函数Adjustdown以及删除pop:
void pop(){swap(_con[0], _con[_con.size() - 1]);_con.pop_back();Adjustdown(0);}
void Adjustdown(int parent){size_t child parent * 2 1;while (child _con.size()){if (child 1 _con.size() _con[child] _con[child 1]){child;}if (_con[parent] _con[child]){swap(_con[child], _con[parent]);parent child;child parent * 2 1;}else{break;}}} 5.4 其余功能函数
size_t size(){return _con.size();}bool empty(){return _con.empty();}const T Top(){return _con[0];} 5.5 测试:
利用下面的代码对上述结构进行测试
void test3()
{violent3::priority_queueint pq;pq.push(1);pq.push(2);pq.push(6);pq.push(2);pq.push(3);while (!pq.empty()){cout pq.Top() ;pq.pop();}
}
结果如下 6. 仿函数
6.1 仿函数的实现
上面所建立的堆是大堆如果想建立一个小堆需要改变中的方向但是针对于上方的实现方式每次更改建立的堆的类型时都需要对符号进行更改过于繁琐为了解决这个问题引入仿函数
对于仿函数其并不是一个函数而是类例如文章中需要用于判断建立大小堆的函数也就是比较函数因此建立两个类分别命名为即
templateclass Tclass less{public:bool operator()(const T x, const T y){return x y;}};templateclass Tclass greater{public:bool operator()(const T x, const T y){return x y;}};
在_的类前将上面的类作为一个模板参数假设在没有明确要求的情况下默认建立大堆则模板参数如下
templateclass T, class Container vectorT, class compare greaterT
在类中将模板参数实例化出一个对象这里命名为在需要对于父、子结点进行比较时直接将这两个结点放入到中具体代码如下
void Adjustup(int child){int parent (child - 1) / 2;compare com;while (child 0){if (com(_con[child], _con[parent])){swap(_con[child], _con[parent]);child parent;parent (child - 1) / 2;}else{break;}}}void Adjustdown(int parent){size_t child parent * 2 1;compare com;while (child _con.size()){if (child 1 _con.size() com(_con[child1],_con[child])){child;}if (com(_con[child],_con[parent])){swap(_con[child], _con[parent]);parent child;child parent * 2 1;}else{break;}}} 6.2 测试
利用下面的代码测试仿函数建立大堆小堆
大堆
void test3()
{/*violent3::priority_queueint,dequeint,greaterint pq;*/violent3::priority_queueint pq;pq.push(1);pq.push(2);pq.push(6);pq.push(2);pq.push(3);while (!pq.empty()){cout pq.Top() ;pq.pop();}
}
效果如下 小堆
void test3()
{violent3::priority_queueint,dequeint,lessint pq;/*violent3::priority_queueint pq;*/pq.push(1);pq.push(2);pq.push(6);pq.push(2);pq.push(3);while (!pq.empty()){cout pq.Top() ;pq.pop();}
}
效果如下
