struct Node
{//队列结点
int data;
struct Node* pNext;
};
class CQueue
{//队列类(带头结点）
public:
CQueue(void);
~CQueue(void);
bool isEmpty()const;//是否为空
void EnQueue(int num);//入队列
int DeQueue();//出队列
int Front()const;//对头元素
void clearQueue();//清空队列
int Size()const;
void printQueue()const;
private:
Node *front;//头结点
Node *end;//尾结点
int size;//队列大小
};
#include "Queue.h"
#include <cstdlib>
#include <assert.h>
#include <iostream>
using namespace std;
CQueue::CQueue(void)
{
this->front = new Node;
this->front->pNext = NULL;
this->end = this->front;
this->size = 0;
}
void CQueue::EnQueue(int num)
{//入队列
Node* pNum = new Node;
pNum->data = num;
pNum->pNext = NULL;
this->end->pNext = pNum;
this->end = pNum;
this->size++;
}
int CQueue::DeQueue()
{//出队列，返回对头元素值
assert(this->front!=this->end);//队列不空
int result;
Node* pNum = this->front->pNext;
result = pNum->data;
if (pNum==this->end)
{//队列中只有一个元素了
this->front->pNext = NULL;
this->end = this->front;
}
else
{
this->front->pNext = pNum->pNext;
}
delete pNum;
this->size--;
return result;
}
void CQueue::clearQueue()
{//清空队列
if (!this->isEmpty())
{
Node* pNum = this->front->pNext;//指向第一个结点
Node* pre = this->front;
while (pNum!=NULL)
{
pre = pNum;
delete pre;
pNum = pNum->pNext;
}
this->front->pNext = NULL;
this->end = this->front;
this->size = 0;
}
}
void CQueue::printQueue()const
{
if (!this->isEmpty())
{
Node* pNum = this->front->pNext;
while (pNum!=NULL)
{
cout<<pNum->data<<" ";
pNum = pNum->pNext;
}
cout<<endl;
}
}
int CQueue::Size()const
{
return this->size;
}
bool CQueue::isEmpty()const
{
return this->front==this->end;
}
CQueue::~CQueue(void)
{
this->clearQueue();
}
复制代码
复制代码
#include "Queue.h"
#include <iostream>
using namespace std;
void printArray(int data[],int n)
{
int i;
for (i=0;i<n;++i)
{
cout<<data[i]<<" ";
}
cout<<endl;
}
int getRadix(int num,int count)
{//返回num在趟数为count时的数值,0趟最后一位，趟倒数第一位，依次类推
int temp = num,result,nCount=0;
while(nCount<=count)
{
result = temp%10;
temp = temp/10;
nCount++;
}
return result;
}
void RadixSort(int data[],int n,const int count)
{//基数排序,count为趟数
CQueue *queue = new CQueue[10];//下标从到的个队列
int i,j,num,m;
//
for (i=0;i<count;++i)
{
//分配
for (j=0;j<n;++j)
{
num = getRadix(data[j],i);//当前趟数下的基数
queue[num].EnQueue(data[j]);
}
for (j=0;j<10;++j)
{
cout<<"队列"<<j<<":"<<endl;
queue[j].printQueue();
}
//收集
m = 0;
for (j=0;j<10;++j)
{
while (!queue[j].isEmpty())
{
data[m] = queue[j].DeQueue();
m++;
}
}
cout<<"收集趟数: "<<i<<": "<<endl;
printArray(data,n);
}
}
void swap(int& a,int& b)
{
int temp = a;
a = b;
b = temp;
}
int minElement(int data[],int begin,int end)
{
int result=begin,maxNum = data[begin],i;
for (i=begin+1;i<end;++i)
{
if (data[i]<maxNum)
{
maxNum = data[i];
result = i;
}
}
return result;
}
void SelectionSort(int data[],int n)
{//选择排序
int i,num;
//共需要进行n-1轮
for (i=0;i<n-1;++i)
{
num = minElement(data,i,n);
swap(data[i],data[num]);
}
}
void AdjustHeap(int data[],int begin,int end)
{//堆调整data[beginend-1]
int tmp = data[begin];
int c = begin*2,pos = begin;
while(c<=end)
{
if (c<end&&data[c+1]>data[c])
{
c++;
}
if (data[c]>tmp)
{
data[pos] = data[c];
pos = c;
c = c*2;
}
else
break;
}
data[pos] = tmp;
}
void BuildHeap(int data[],int n)
{//初始建小顶堆
int i;
for (i=n/2;i>0;--i)
{
AdjustHeap(data,i,n);
}
}
void HeapSort(int data[],int n)
{//堆排序
int* tdata = new int[n+1];
int i;
tdata[0] = -1;//第一个元素舍弃
for (i=0;i<n;++i)
{
tdata[i+1] = data[i];
}
BuildHeap(tdata,n); //将tdata[1n]建成初始堆
for(i=n-1;i>=1;--i)
{ //对当前无序区进行堆排序，共做n-1趟。
swap(tdata[1],tdata[i+1]);
AdjustHeap(tdata,1,i); //重新调整为堆
}
for (i=0;i<n;++i)
{
data[i] = tdata[i+1];
}
delete[] tdata;
}
void BubbleSort(int data[],int n)
{//冒泡排序
bool isChange = true;
int i,k;
for (k=n-1;k>=1&&isChange==true;--k)
{
isChange = false;
for (i=0;i<k;++i)
{
if (data[i]>data[i+1])
{
swap(data[i],data[i+1]);
isChange = true;
}
}
}
}
void InsertSort(int data[],int n)
{//插入排序
int i,j,pos,num;
for (i=1;i<n;++i)
{
num = data[i];
for (j=0;j<=i-1&&data[i]>data[j];++j);
pos = j;//插入点
for (j=i-1;j>=pos;--j)
{
data[j+1] = data[j];
}
data[pos] = num;
}
}
void QuickSort(int *data,int low,int high)
{//快速排序
int pivot;
int scanUp,scanDown;
int mid;
if(high-low<=0)
return;
else
{
if(high-low==1)
{
if(data[high]<data[low])
swap(data[low],data[high]);
return;
}
mid = (low+high)/2;
pivot = data[mid];
swap(data[low],data[mid]);
scanUp = low+1;
scanDown = high;
do
{
while(scanUp<=scanDown&&data[scanUp]<=pivot)
scanUp++;
while(data[scanDown]>pivot)
scanDown--;
if(scanUp<scanDown)
swap(data[scanUp],data[scanDown]);
}while(scanUp<scanDown);
data[low] = data[scanDown];
data[scanDown] = pivot;
if(low<scanDown-1)
QuickSort(data,low,scanDown-1);
if(scanDown+1<high)
QuickSort(data,scanDown+1,high);
}
}
int main()
{
int a[] = {10,32,55,41,39,12,11,15,20,19,21,22,29,25};
int len = sizeof(a)/sizeof(int);
cout<<"排序前:"<<endl;
printArray(a,len);
//RadixSort(a,len,2);
//SelectionSort(a,len);
//HeapSort(a,len);
//BubbleSort(a,len);
//InsertSort(a,len);
QuickSort(a,0,len);
cout<<"排序后:"<<endl;
printArray(a,len);
system("pause");
return 0;
}
复制代码
本文转自Phinecos(洞庭散人)博客园博客，原文链接：http://www.cnblogs.com/phinecos/archive/2008/07/18/1246322.html，如需转载请自行联系原作者
