网站建设微信群,免费简约ppt模板,北京城建道桥建设有限公司网站,罗定网站建设《数据结构、算法与应用C语言描述》使用C语言实现数组队列
定义
队列的定义
队列#xff08;queue#xff09;是一个线性表#xff0c;其插入和删除操作分别在表的不同端进行。插入元素的那一端称为队尾#xff08;back或rear#xff09;#xff0c;删除元素的那一端称…《数据结构、算法与应用C语言描述》使用C语言实现数组队列
定义
队列的定义
队列queue是一个线性表其插入和删除操作分别在表的不同端进行。插入元素的那一端称为队尾back或rear删除元素的那一端称为队首front。
队列的抽象数据类型 数组队列实现代码
_17queue.h
抽象类栈。
/*
Project name : allAlgorithmsTest
Last modified Date: 2022年8月13日17点38分
Last Version: V1.0
Descriptions: 队列的抽象类
*/
#pragma once
#ifndef _QUEUE_H_
#define _QUEUE_H_
templateclass T
class queue
{
public:virtual ~queue() {}virtual bool empty() const 0;//返回true,当且仅当队列为空virtual int size() const 0;//返回队列中元素个数virtual T front() 0;//返回头元素的引用virtual T back() 0;//返回尾元素的引用virtual void pop() 0;//删除首元素virtual void push(const T theElement) 0;//把元素theELment加入队尾
};
#endif_18arrayQueue.h
/*
Project name : allAlgorithmsTest
Last modified Date: 2022年8月13日17点38分
Last Version: V1.0
Descriptions: 数组存储的队列的头文件
*/
#pragma once
#ifndef _ARRAYQUEUE_H_
#define _ARRAYQUEUE_H_
#includesstream
#includeiostream
#include _1myExceptions.h
#include _17queue.h
#include cmath
/*测试函数*/
void arrayQueueTest();using namespace std;
templateclass T
class arrayQueue : public queueT
{
public:/*成员函数*/arrayQueue(int initialCapacity 10);~arrayQueue() { delete[] queue; }bool empty() const { return theFront theBack; }int size() const //返回队列的元素个数{return (queueLength - theFront theBack) % queueLength;}void clear() { theFront theBack 0; }/*清空队列中的元素*/int capacity() const { return queueLength-1; }//返回第一个元素T front(){if (theFront theBack)throw queueEmpty();return queue[(theFront 1) % queueLength];}//返回最后一个元素T back(){if (theFront theBack)throw queueEmpty();return queue[theBack];}//删除队首元素void pop(){if (theFront theBack)throw queueEmpty();theFront (theFront 1) % queueLength;queue[theFront].~T();}//向队尾插入元素theElementvoid push(const T theElement);/*调整队列容量大小*/void resizeQueue(int newLength);void meld(arrayQueueT a, arrayQueueT b);//合并队列a,b到当前队列void split(arrayQueueT a, arrayQueueT b);//将当前队列分成两个队列a,b/*重载操作符*//*重载[]操作符*/T operator[](int i){ return queue[(theFront i 1) % queueLength]; }/*友元函数*/friend istream operator T(istream in, arrayQueueT m);//输出但是不pop()元素friend ostream operator T(ostream out, arrayQueueT m);
private:int theFront; // 第一个元素的前一个位置int theBack; // 最后一个元素的位置int queueLength; // 队列的容量实质上比队列容量(不包含queueFront指向的那一个位置)大1T* queue; // 指向队列首地址的指针
};
/*友元函数*/
/*操作符*/
templateclass T
istream operator(istream in, arrayQueueT 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(cinElement);}return in;
}
/*操作符*/
templateclass T
ostream operator(ostream out, arrayQueueT m)
{int size m.size();for (int i 0; i size; i)out m.queue[(m.theFront i 1) % m.queueLength] ;out endl;return out;
}
/*成员函数*/
/*构造函数*/
templateclass T
arrayQueueT::arrayQueue(int initialCapacity)
{if (initialCapacity 1){ostringstream s();s Initial capacity initialCapacity Must be 0;throw illegalParameterValue(s.str());}queue new T[initialCapacity1];queueLength initialCapacity1;theFront theBack 0;
}/*向队尾插入元素theElement*/
templateclass T
void arrayQueueT::push(const T theElement)
{//首先检查队列是否已满如已满则将队列容量加倍if ((theBack 1) % queueLength theFront)resizeQueue(2 * (queueLength-1)); theBack (theBack 1) % queueLength;queue[theBack] theElement;
}
/*调整队列容量大小*/
templateclass T
void arrayQueueT::resizeQueue(int newLength)
{T* temp new T[newLength 1];int size min((*this).size(), newLength);for (int i 0; i size; i)temp[i] queue[(theFront i 1) % queueLength]; queueLength newLength1;theFront newLength;theBack size - 1;delete[] queue;queue temp;
}/*
创建一个新的队列该表包含了a和b中的所有元素其中a和b的元素轮流出现表中的首
元素为a中的第一个元素。在轮流排列元素时如果某个队列的元素用完了则把另一个队列的其
余元素依次添加在新队列的后部。代码的复杂性应与两个输入队列的长度呈线性比例关系。
归并后的线性队列是调用对象*this
*/
template class T
void arrayQueueT::meld(arrayQueueT a, arrayQueueT b)
{(*this).clear();int i 0;while (i a.size() i b.size()){push(a[i]);push(b[i]);i;}while (i a.size()){push(a[i]);i;}while (i b.size()){push(b[i]);i;}
}/*生成两个线性队列a和ba包含*this中索引为奇数的元素b包含其余的元素*/
templateclass T
void arrayQueueT::split(arrayQueueT a, arrayQueueT b)
{a.clear();b.clear();int size (*this).size();for (int i 0; i size; i){if (i % 2 0)a.push(queue[(theFront i 1) % queueLength]);elseb.push(queue[(theFront i 1) % queueLength]);}
}
#endif_18arrayQueue.cpp
/*
Project name : allAlgorithmsTest
Last modified Date: 2022年8月13日17点38分
Last Version: V1.0
Descriptions: 测试_18arrayQueue.h头文件中的所有函数
*/
#include iostream
#include time.h
#include _18arrayQueue.h
using namespace std;/*测试函数*/
void arrayQueueTest()
{cout endl *********************************arrayQueueTest()函数开始************************************* endl;arrayQueueint a;//测试输入和输出cout endl 测试友元函数******************************************* endl;cout 输入输出************************ endl;cin a;cout arrayQueue 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()************************** endl;cout arrayQueue a is: a;a.push(99);a.push(22);cout arrayQueue a is: a;cout front()************************* endl;cout a.front() a.front() endl;cout back()************************** endl;cout a.back() a.back() endl;cout pop()*************************** endl;cout before pop arrayQueue a is: a;a.pop();a.pop();cout after pop arrayQueue a is: a;cout resizeQueue()******************* endl;cout before resizeQueue a.capacity() a.capacity()endl;a.resizeQueue(4);cout after resizeQueue a.capacity() a.capacity() endl;cout arrayQueue a is: a;cout a.front() a.front() endl;cout a.back() a.back() endl;a.push(88);cout after resizeQueue a.capacity() a.capacity() endl;cout meld()************************** endl;arrayQueueint b;cin b;cout arrayQueue a is: a;cout arrayQueue b is: b;arrayQueueint c;c.meld(a, b);cout arrayQueue c is: c;cout split()************************* endl;arrayQueueint d;arrayQueueint e;c.split(d, e);cout arrayQueue c is: c;cout arrayQueue d is: d; cout arrayQueue e is: e;cout endl 测试成员函数性能*************************************** endl;cout push()************************** endl;arrayQueueint f;double clocksPerMillis double(CLOCKS_PER_SEC) / 1000;clock_t startTime clock();for (int i 0; i 100000000; i)f.push(i);double pushTime (clock() - startTime) / clocksPerMillis;cout 10000 push took pushTime ms endl;cout *********************************arrayQueueTest()函数结束************************************* endl;}main.cpp
/*
Project name : allAlgorithmsTest
Last modified Date: 2022年8月13日17点38分
Last Version: V1.0
Descriptions: main()函数控制运行所有的测试函数
*/
#include iostream
#include _18arrayQueue.hint main()
{arrayQueueTest();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
