苏州seo优化外包公司,官方网站优化价格,WordPress黑镜主题,全球设计中心《数据结构、算法与应用C语言描述》使用C语言实现数组双端队列
定义
队列的定义
队列#xff08;queue#xff09;是一个线性表#xff0c;其插入和删除操作分别在表的不同端进行。插入元素的那一端称为队尾#xff08;back或rear#xff09;#xff0c;删除元素的那一…《数据结构、算法与应用C语言描述》使用C语言实现数组双端队列
定义
队列的定义
队列queue是一个线性表其插入和删除操作分别在表的不同端进行。插入元素的那一端称为队尾back或rear删除元素的那一端称为队首front。
队列的抽象数据类型 链表队列代码
数组双端队列实现
_19deque.h
/*
Project name : allAlgorithmsTest
Last modified Date: 2022年8月13日17点38分
Last Version: V1.0
Descriptions: 无序的双端队列的抽象类的头文件
*/
#pragma once
#ifndef _DEQUE_H_
#define _DEQUE_H_
templateclass T
class deque
{
public:virtual ~deque() {}virtual bool empty() const 0;//返回true,当且仅当队列为空virtual int size() const 0;//返回队列中元素个数virtual T front() 0;//返回头元素的引用virtual T back() 0;//返回尾元素的引用virtual void pop_front() 0;//删除首元素virtual void pop_back() 0;//删除尾元素virtual void push_front(const T theElement) 0;//把元素theELment加入队首virtual void push_back(const T theElement) 0;//把元素theELment加入队尾
};
#endif_20arrayDeque.h
/*
Project name : allAlgorithmsTest
Last modified Date: 2022年8月13日17点38分
Last Version: V1.0
Descriptions: 数组存储的无序的双端队列类的头文件
*/
#pragma once
#ifndef _ARRAYDEQUE_H_
#define _ARRAYDEQUE_H_
#includesstream
#includeiostream
#include _1myExceptions.h
#include _19deque.h
/*测试函数*/
void arrayDequeTest();
templateclass T
class arrayDeque : public dequeT
{
public:/*成员函数*//*构造函数*/arrayDeque(int initialCapacity 10);/*析构函数*/~arrayDeque() {delete[] deque;}bool empty() const { return theFront theBack; };//返回true,当且仅当队列为空int size() const { return (dequeLength - theFront theBack)%dequeLength; };//返回队列中元素个数int capacity() const {return dequeLength - 1;}void clear() { theFront theBack 0; }T front();//返回头元素的引用T back();//返回尾元素的引用void pop_front();//删除首元素void pop_back();//删除尾元素void push_front(const T theElement);//把元素theELment加入队首void push_back(const T theElement);//把元素theELment加入队尾/*调整队列容量大小*/void resizeDeque(int newLength);void meld(arrayDequeT a, arrayDequeT b);void split(arrayDequeT a, arrayDequeT b);/*重载操作符*//*重载[]操作符*/T operator[](int i) { return deque[(theFront i 1) % dequeLength]; }/*友元函数*/friend istream operator T(istream in, arrayDequeT m);//输出但是不pop()元素friend ostream operator T(ostream out, arrayDequeT m);
private:int theFront; // 第一个元素的前一个位置int theBack; // 最后一个元素的位置int dequeLength; // 队列的容量实质上比队列容量(不包含queueFront指向的那一个位置)大1T* deque;
};/*友元函数*/
/*操作符*/
templateclass T
istream operator(istream in, arrayDequeT m)
{int numberOfElement 0;cout Please enter the number of element:;while (!(in numberOfElement)){in.clear();//清空标志位while (in.get() ! \n)//删除无效的输入continue;cout Please enter the number of element:;}T cinElement;for (int i 0; i numberOfElement; i){cout Please enter the element i 1 :;while (!(in cinElement)){in.clear();//清空标志位while (in.get() ! \n)//删除无效的输入continue;cout Please enter the element i 1 :;}m.push_back(cinElement);}return in;
}
/*操作符*/
templateclass T
ostream operator(ostream out, arrayDequeT m)
{int size m.size();for (int i 0; i size; i)out m.deque[(m.theFront i 1) % m.dequeLength] ;out endl;return out;
}/*构造函数*/
templateclass T
arrayDequeT::arrayDeque(int initialCapacity)
{if (initialCapacity 1){ostringstream s();s Initial capacity initialCapacity Must be 0;throw illegalParameterValue(s.str());}deque new T[initialCapacity 1];dequeLength initialCapacity 1;theFront theBack 0;
}
/*返回头元素的引用*/
templateclass T
T arrayDequeT::front()
{if(theFront theBack)throw queueEmpty();return deque[(theFront 1) % dequeLength];
}
/*返回尾元素的引用*/
templateclass T
T arrayDequeT::back()
{if (theFront theBack)throw queueEmpty();return deque[theBack];
}
/*删除首元素*/
templateclass T
void arrayDequeT::pop_front()
{/*检查是否为空为空就抛出异常*/if (theFront theBack)throw queueEmpty();/*不为空就删除首元素*/theFront (theFront 1) % dequeLength;deque[theFront].~T();
}
/*删除尾元素*/
templateclass T
void arrayDequeT::pop_back()
{/*检查是否为空为空就抛出异常*/if (theFront theBack)throw queueEmpty();/*不为空就删除尾元素*/deque[theBack].~T();if (theBack 0)theBack dequeLength - 1;elsetheBack--;
}
/*把元素theELment加入队首*/
templateclass T
void arrayDequeT::push_front(const T theElement)
{/*判断队列是否满了如果满了就调整容量为原来的两倍*/if ((theFront 1) % dequeLength theBack)resizeDeque(2 * (dequeLength-1));deque[theFront] theElement;if (theFront 0)theFront dequeLength - 1;elsetheFront theFront - 1;
}
/*把元素theELment加入队尾*/
templateclass T
void arrayDequeT::push_back(const T theElement)
{/*判断队列是否满了如果满了就调整容量为原来的两倍*/if ((theBack 1) % dequeLength theFront)resizeDeque(2 * (dequeLength - 1));theBack (theBack 1) % dequeLength;deque[theBack] theElement;
}/*调整队列容量大小*/
templateclass T
void arrayDequeT::resizeDeque(int newLength)
{T* temp new T[newLength 1];int size min((*this).size(), newLength);for (int i 0; i size; i)temp[i] deque[(theFront i 1) % dequeLength];dequeLength newLength 1;theFront newLength;theBack size - 1;delete[] deque;deque temp;
}/*
创建一个新的队列该表包含了a和b中的所有元素其中a和b的元素轮流出现表中的首
元素为a中的第一个元素。在轮流排列元素时如果某个队列的元素用完了则把另一个队列的其
余元素依次添加在新队列的后部。代码的复杂性应与两个输入队列的长度呈线性比例关系。
归并后的线性队列是调用对象*this
*/
template class T
void arrayDequeT::meld(arrayDequeT a, arrayDequeT b)
{(*this).clear();int i 0;while (i a.size() i b.size()){push_back(a[i]);push_back(b[i]);i;}while (i a.size()){push_back(a[i]);i;}while (i b.size()){push_back(b[i]);i;}
}/*生成两个线性队列a和ba包含*this中索引为奇数的元素b包含其余的元素*/
templateclass T
void arrayDequeT::split(arrayDequeT a, arrayDequeT b)
{a.clear();b.clear();int size (*this).size();for (int i 0; i size; i){if (i % 2 0)a.push_back(deque[(theFront i 1) % dequeLength]);elseb.push_back(deque[(theFront i 1) % dequeLength]);}
}#endif_20arrayDeque.cpp
/*
Project name : allAlgorithmsTest
Last modified Date: 2022年8月13日17点38分
Last Version: V1.0
Descriptions: 测试_20arrayDeque.h头文件中的所有函数
*/
#include iostream
#include _20arrayDeque.h
using namespace std;
/*测试函数*/
void arrayDequeTest()
{cout endl *********************************arrayDequeTest()函数开始************************************* endl;arrayDequeint a;//测试输入和输出cout endl 测试友元函数******************************************* endl;cout 输入输出************************ endl;cin a;cout arrayDeque a is: a;cout endl 测试成员函数******************************************* endl;cout empty()************************* endl;cout a.empty() a.empty() endl;cout size()************************** endl;cout a.size() a.size() endl;cout capacity()********************** endl;cout a.capacity() a.capacity() endl;cout push_front()******************** endl;cout before push_front() arrayDeque a is: a;a.push_front(99);a.push_front(22);cout after push_front() arrayDeque a is: a;cout push_back()********************* endl;cout before push_back() arrayDeque a is: a;a.push_back(99);a.push_back(22);cout after push_back() arrayDeque a is: a;cout front()************************* endl;cout a.front() a.front() endl;cout back()************************** endl;cout a.back() a.back() endl;cout pop_front()********************* endl;cout before pop_front arrayDeque a is: a;a.pop_front();a.pop_front();cout after pop_front arrayDeque a is: a;cout pop_back()********************** endl;cout before pop_back arrayDeque a is: a;a.pop_back();a.pop_back();cout after pop_back arrayDeque a is: a;cout resizeDeque()******************* endl;cout before resizeDeque a.capacity() a.capacity() endl;a.resizeDeque(4);cout after resizeDeque a.capacity() a.capacity() endl;cout resizeDeque a is: a;cout a.front() a.front() endl;cout a.back() a.back() endl;a.push_back(88);cout after resizeDeque a.capacity() a.capacity() endl;cout meld()************************** endl;arrayDequeint b;cin b;cout arrayDeque a is: a;cout arrayDeque b is: b;arrayDequeint c;c.meld(a, b);cout arrayDeque c is: c;cout split()************************* endl;arrayDequeint d;arrayDequeint e;c.split(d, e);cout arrayDeque c is: c;cout arrayDeque d is: d;cout arrayDeque e is: e;cout *********************************arrayDequeTest()函数结束************************************* endl;}_1main.cpp
/*
Project name : allAlgorithmsTest
Last modified Date: 2022年8月13日17点38分
Last Version: V1.0
Descriptions: main()函数控制运行所有的测试函数
*/
#include iostream
#include _20arrayDeque.hint main()
{arrayDequeTest();return 0;
}_1myExceptions.h
/*
Project name : allAlgorithmsTest
Last modified Date: 2022年8月13日17点38分
Last Version: V1.0
Descriptions: 综合各种异常
*/
#pragma once
#ifndef _MYEXCEPTIONS_H_
#define _MYEXCEPTIONS_H_
#include string
#includeiostreamusing namespace std;// illegal parameter value
class illegalParameterValue
{public:illegalParameterValue(string theMessage Illegal parameter value){message theMessage;}void outputMessage() {cout message endl;}private:string message;
};// illegal input data
class illegalInputData
{public:illegalInputData(string theMessage Illegal data input){message theMessage;}void outputMessage() {cout message endl;}private:string message;
};// illegal index
class illegalIndex
{public:illegalIndex(string theMessage Illegal index){message theMessage;}void outputMessage() {cout message endl;}private:string message;
};// matrix index out of bounds
class matrixIndexOutOfBounds
{public:matrixIndexOutOfBounds(string theMessage Matrix index out of bounds){message theMessage;}void outputMessage() {cout message endl;}private:string message;
};// matrix size mismatch
class matrixSizeMismatch
{public:matrixSizeMismatch(string theMessage The size of the two matrics doesnt match){message theMessage;}void outputMessage() {cout message endl;}private:string message;
};// stack is empty
class stackEmpty
{public:stackEmpty(string theMessage Invalid operation on empty stack){message theMessage;}void outputMessage() {cout message endl;}private:string message;
};// queue is empty
class queueEmpty
{public:queueEmpty(string theMessage Invalid operation on empty queue){message theMessage;}void outputMessage() {cout message endl;}private:string message;
};// hash table is full
class hashTableFull
{public:hashTableFull(string theMessage The hash table is full){message theMessage;}void outputMessage() {cout message endl;}private:string message;
};// edge weight undefined
class undefinedEdgeWeight
{public:undefinedEdgeWeight(string theMessage No edge weights defined){message theMessage;}void outputMessage() {cout message endl;}private:string message;
};// method undefined
class undefinedMethod
{public:undefinedMethod(string theMessage This method is undefined){message theMessage;}void outputMessage() {cout message endl;}private:string message;
};
#endif
