QueueNode.h
template<typename Type,typename Cmp>class PriorityQueue;
template<typename Type, typename Cmp>class QueueNode{
friend class PriorityQueue<Type, Cmp>;
QueueNode(const Type item, QueueNode<Type,Cmp> *next = NULL)
:m_data(item),m_pnext(next){}
private:
Type m_data;
QueueNode<Type,Cmp> *m_pnext;
};
Compare.h
template<typename Type> class Compare{
public:
static bool lt(Type item1, Type item2);
};
template<typename Type> bool Compare<Type>::lt(Type item1, Type item2){
return item1 < item2;
}
struct SpecialData{
friend ostream& operator<<(ostream&, SpecialData &);
int m_ntenor;
int m_npir;
};
ostream& operator<<(ostream& os, SpecialData& out){
os<<out.m_ntenor<<" "<<out.m_npir;
return os;
}
class SpecialCmp{
public:
static bool lt(SpecialData item1, SpecialData item2);
};
bool SpecialCmp::lt(SpecialData item1, SpecialData item2){
return item1.m_npir < item2.m_npir;
}
PriorityQueue.h
#include "QueueNode.h"
#include "Compare.h"
template<typename Type,typename Cmp> class PriorityQueue{
private:
QueueNode<Type,Cmp> *m_prear, *m_pfront;
public:
PriorityQueue():m_prear(NULL),m_pfront(NULL){}
~PriorityQueue(){MakeEmpty();}
void MakeEmpty();
void Append(const Type item);
Type Delete();
Type GetFront();
void Print();
bool IsEmpty(){return m_pfront==NULL;}
};
PriorityQueue.cpp
template<typename Type,typename Cmp> void PriorityQueue<Type,Cmp>::MakeEmpty(){
QueueNode<Type,Cmp> *p = m_pfront;
while(m_pfront != NULL)
{
p = m_pfront;
m_pfront = m_pfront->m_pnext;
delete p;
}
m_prear = NULL;
}
template<typename Type,typename Cmp> void PriorityQueue<Type,Cmp>::Append(const Type item){
QueueNode<Type,Cmp> *p = new QueueNode<Type,Cmp>(item, NULL);
if(IsEmpty())
{
m_pfront = p;
m_prear = p;
}
else
{
m_prear->m_pnext = p;
m_prear = p;
}
}
template<typename Type,typename Cmp> Type PriorityQueue<Type,Cmp>::Delete(){
if(IsEmpty())
{
cout<<"There is no elements!"<<endl;
exit(1);
}
QueueNode<Type,Cmp> *p = m_pfront, *q = m_pfront;
while(p->m_pnext != NULL)
{
if(Cmp::lt(p->m_pnext->m_data,q->m_pnext->m_data))
q = p;
p = p->m_pnext;
}
p = q;q = q->m_pnext;
Type temp = q->m_data;
p->m_pnext = q->m_pnext;
delete q;
return temp;
}
template<typename Type,typename Cmp> Type PriorityQueue<Type,Cmp>::GetFront(){
if(IsEmpty())
{
cout<<"There is no elements!"<<endl;
exit(1);
}
QueueNode<Type,Cmp> *p = m_pfront, *q = m_pfront;
while(p->m_pnext != NULL)
{
if(Cmp::lt(p->m_pnext->m_data,q->m_pnext->m_data))
q = p;
p = p->m_pnext;
}
return q->m_pnext->m_data;
}
template<typename Type,typename Cmp> void PriorityQueue<Type,Cmp>::Print(){
QueueNode<Type,Cmp> *p = m_pfront, *q = m_pfront;
while(p != NULL)
{
cout<<p->m_data<<' ';
p = p->m_pnext;
}
cout<<endl;
}
Sort.h
#include "Data.h"
#include "LinkQueue.h"
template<typename Type> class Sort{
public:
void InsertSort(DataList<Type> &list, int n = -1);
void BinaryInsertSort(DataList<Type> &list, int n = -1);
void ShellSort(DataList<Type> &list, int n = -1);
void BubbleSort(DataList<Type> &list);
void QuickSort(DataList<Type> &list, int left=0, int right=-1);
void SelectSort(DataList<Type> &list);
void HeapSort(DataList<Type> &list);
void MergeSort(DataList<Type> &list);
void RadixSort(DataList<int> &list, int m, int d);
private:
void BubbleSwap(DataList<Type> &list, const int n, int &flag);
void SelectChange(DataList<Type> &list, const int n);
void HeapAdjust(DataList<Type> &list, const int start, const int end);
void Merge(DataList<Type> &list, DataList<Type> &mergedlist, int start, int end);
void MergeDouble(DataList<Type> &list, DataList<Type> &mergedlist, const int start, const int part, const int end);
};
template<typename Type> void Sort<Type>::InsertSort(DataList<Type> &list, int n){
if (-1 == n){
for (int i=1; i<list.Size(); i++){
InsertSort(list, i);
}
return;
}
Element<Type> temp = list.m_pvector[n];
int i;
for(i =n; i >0 ; i--)
{
if(temp > list.m_pvector[i-1])
break;
else
list.m_pvector[i] = list.m_pvector[i-1];
}
list.m_pvector[i] = temp;
}
template<typename Type> void Sort<Type>::BinaryInsertSort(DataList<Type> &list, int n){
if(-1 == n)
{
for(int i = 1; i < list.Size(); i++)
BinaryInsertSort(list ,i);
return ;
}
Element<Type> temp = list.m_pvector[n];
int left = 0, right = n-1;
while(left <= right)
{
int middle = (left + right) / 2;
if(temp < list.m_pvector[middle])
right = middle - 1;
else left = middle + 1;
}
for (int i=n-1; i>=left; i--)
list.m_pvector[i+1] = list.m_pvector[i];
list.m_pvector[left] = temp;
}
template<typename Type> void Sort<Type>::ShellSort(DataList<Type> &list, const int gap){
if(-1 == gap){
int gap = list.Size() / 2;
while(gap){
ShellSort(list,gap);
gap = gap / 2;
}
return ;
}
int i,j;
for(i = gap; i < list.Size(); i++)
{
Element<Type> temp = list.m_pvector[i];
if(temp < list.m_pvector[i-gap])
{
for(j = i - gap; j >=0 && temp < list.m_pvector[j]; j-=gap)
list.m_pvector[j+gap] = list.m_pvector[j];
list.m_pvector[j+gap] = temp;
}
}
}
template<typename Type> void Sort<Type>::BubbleSwap(DataList<Type> &list, const int n, int &flag){
flag = 0;
for(int i = list.Size() - 1; i >= n; i--)
{
if(list.m_pvector[i-1] > list.m_pvector[i])
{
list.Swap(list.m_pvector[i-1], list.m_pvector[i]);
flag = 1;
}
}
}
template<typename Type> void Sort<Type>::BubbleSort(DataList<Type> &list){
int flag = 1, n = 0;
while(++n < list.Size() && flag)
BubbleSwap(list, n, flag);
}
template<typename Type> void Sort<Type>::QuickSort(DataList<Type> &list, int left=0, int right=-1){
if(-1 == right)
right = list.Size() -1 ;
int a = left, b = right;
if(left < right)
{
int pos = left;
Element<Type>temp = list.m_pvector[left];
while(left < right)
{
while(left < right && list.m_pvector[right] >= temp)
--right;
list.m_pvector[left] = list.m_pvector[right];
while(left < right && list.m_pvector[left] <= temp)
++left;
list.m_pvector[right] = list.m_pvector[left];
}
list.m_pvector[left] = temp;
QuickSort(list, a, left - 1);
QuickSort(list, left + 1, b);
}
}
template<typename Type> void Sort<Type>::SelectChange(DataList<Type> &list, const int n){
int j = n;
for(int i = n + 1; i < list.Size(); i++)
{
if(list.m_pvector[i] < list.m_pvector[j])
j = i;
}
if(j != n)
list.Swap(list.m_pvector[n], list.m_pvector[j]);
}
template<typename Type> void Sort<Type>::SelectSort(DataList<Type> &list){
for(int i = 0; i < list.Size()-1; i++)
SelectChange(list, i);
}
template<typename Type> void Sort<Type>::HeapAdjust(DataList<Type> &list, const int start, const int end){
int current = start, child = 2 * current + 1;
Element<Type> temp = list.m_pvector[start];
while(child <= end)
{
if(child < end && list.m_pvector[child] < list.m_pvector[child+1])
child++;
if(temp >= list.m_pvector[child])
break;
else
{
list.m_pvector[current] = list.m_pvector[child];
current = child;
child = 2 * current + 1;
}
}
list.m_pvector[current] = temp;
}
template<typename Type> void Sort<Type>::HeapSort(DataList<Type> &list){
for(int i = (list.Size()-2)/2; i >= 0; i--)
HeapAdjust(list, i, list.Size() - 1);
for(int i = list.Size() - 1; i >= 1; i--)
{
list.Swap(list.m_pvector[0], list.m_pvector[i]);
HeapAdjust(list, 0, i-1);
}
}
template<typename Type> void Sort<Type>::MergeDouble(DataList<Type> &list, DataList<Type> &mergedlist, int start, int part, int end){
int j, k;
for(j = part+1,k=start; start <= part&&j<=end; ++k)
{
if(list.m_pvector[start] < list.m_pvector[j])
mergedlist.m_pvector[k] = list.m_pvector[start++];
else
mergedlist.m_pvector[k] = list.m_pvector[j++];
}
if(start <= part)
{
int i1,i2;
for(i1=k,i2=start; i1<=end,i2<=part; i1++,i2++)
mergedlist.m_pvector[i1] = list.m_pvector[i2];
}
if(j <= end)
{
int i1,i2;
for(i1=k,i2=j; i1<=end,i2<=end; i1++,i2++)
mergedlist.m_pvector[i1] = list.m_pvector[i2];
}
}
template<typename Type> void Sort<Type>::Merge(DataList<Type> &list, DataList<Type> &mergedlist, int start, int end){
if(start == end)
mergedlist.m_pvector[start] = list.m_pvector[start];
else{
DataList<Type> temp(list.m_pvector,list.m_nMaxSize);
int m = (start + end) / 2;
Merge(list, temp, start, m);
Merge(list, temp, m + 1, end);
MergeDouble(temp, mergedlist, start, m, end);
}
}
template<typename Type> void Sort<Type>::MergeSort(DataList<Type> &list){
Merge(list, list, 0, list.Size() - 1);
}
template<typename Type> void Sort<Type>::RadixSort(DataList<int> &list, int m, int d){
LinkQueue<int> *queue = new LinkQueue<int>[d];
int power = 1;
for (int i=0; i<m; i++){
if (i){
power = power * d;
}
for (int j=0; j<list.m_ncurrentsize; j++){
int k = (list.m_pvector[j].GetKey() / power) % d;
queue[k].Append(list.m_pvector[j].GetKey());
}
for (int j=0,k=0; j<d; j++){
while (!queue[j].IsEmpty()){
list.m_pvector[k++].SetKey(queue[j].Delete());
}
}
}
}
Test.cpp
#include <iostream>
#include <cstdlib>
using namespace std;
#include "PriorityQueue.h"
#include "Sort.h"
int main(){
PriorityQueue<int,Compare<int> > queue;
int init[10]={1,9,3,5,0,8,2,4,6,7};
for(int i=0;i<10;i++){
queue.Append(init[i]);
}
queue.Print();
queue.Delete();
queue.Print();
system("pause");
system("cls");
PriorityQueue<SpecialData,SpecialCmp> spe_queue;
int init2[5][2]={{34,2},{64,1},{18,3},{24,2},{55,4}};
SpecialData data[5];
for(int i=0;i<5;i++){
data[i].m_npir=init2[i][1];
data[i].m_ntenor=init2[i][0];
}
for(int i=0;i<5;i++){
spe_queue.Append(data[i]);
}
spe_queue.Print();
cout<<spe_queue.GetFront()<<endl<<endl;
spe_queue.Delete();
spe_queue.Print();
return 0;
}