内部排序
代码更新地址:https://github.com/myourys/Algorithm/blob/master/InternalSort.cpp


BubbingSort         冒泡排序 O(n^2)
SimpleSelectSort    简单选择排序 O(n^2)
QuickSort           快速排序O(n*logn)
InsertSort          插入排序O(n^2)
BInsertSort         折半插入排序O(n^2)
ShellSort           希尔排序 O(N*(logN))
RadixSort           基数排序O(nlog(r)m)
MergeSort           归并排序O(n*log(n))
HeapSort            堆排序O(n*log(n)
BucketSort          桶排序O(N)~O(n^2)
/*=============================================================================
#     FileName: InternalSort.cpp
#         Desc: 内部排序算法
#       Author: Hector
#        Email: myourys@gmail.com
#     HomePage: http://www.yiwuye.com
#      Version: 0.0.1
#   LastChange: 2013-03-25 00:02:24
#      History:
=============================================================================*/

#include<iostream>
#include <stdlib.h>
#include <ctime>
using namespace std;

void swap(int &a,int &b)
{
    int t = a;
    a = b;
    b = t;
}

/*
 * 冒泡排序
 * O(n^2) =  (n-1)*n/2
 *
 */
void BubbingSort(int s[],int n)
{
    int i,j;
    for(i=0;i<n-1;i++)
        for(j=i+1;j<n;j++)
            if(s[j]<s[i])
                swap(s[i],s[j]);
}

/*
 * 简单选择排序
 * O(n^2) =  (n-1)*n/2
 * 对冒泡的一种改进,减少交换次数,如果内循环元素比外循环元素大,则记下位置和大小,内循环完成后得到最大的数
 * 每次外循环将最大(小)的数放在前面
 */
void SimpleSelectSort(int s[],int n)
{
    int i,j,t,pos;
    for(i=0;i<n-1;i++)
    {
        t=s[i];
        pos = i;
        for(j=i+1;j<n;j++)
        {
            if(s[j]<t)
            {
                pos = j;
                t = s[j];
            }
        }
        if(i!=pos)
            swap(s[i],s[pos]);
    }
}

/*
 * 快速排序
 * O(n*logn)
 * 以开头第一个元素为中间点,大的放在前面,小的放在后边,递归排序
 * 分别从后往前搜索,将大数放前面,然后从前往后搜索,将小的放在后边
 */
void QuickSort(int s[],int begin,int end)
{
    if(begin>=end) return; //重合点
    // a,b 为前后搜索的定位点,e为中间点
    int a = begin,b = end;
    int e = a;

    //从后往前搜索
    for(b=end;b>a;b--)
    {
        if(s[b]<s[e])
        {
            swap(s[e],s[b]);
            e=b;
            //从前往后搜索
            for(a = a+1;a<b;a++)
            {
                if(s[a]>s[e])
                {
                    swap(s[e],s[a]);
                    e=a;
                    break;//反方向搜索
                }
            }
        }
    }
    QuickSort(s,begin,e-1);
    QuickSort(s,e+1,end);
}

/*
 * 插入排序
 * O(n^2) 
 * 算法适用于少量数据的排序
 *⒈ 从第一个元素开始,该元素可以认为已经被排序
 *⒉ 取出下一个元素,在已经排序的元素序列中从后向前扫描
 *⒊ 如果该元素(已排序)大于新元素,将该元素移到下一位置
 *⒋ 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置
 *⒌ 将新元素插入到下一位置中
 *⒍ 重复步骤2
 */

void InsertSort(int s[],int n)
{
    int i,j;
    for(i=0;i<n-1;i++) //i前面都是排好序的数列
       for(j=i+1;j>0 && s[j] < s[j-1];j--) // 大数往前面冒泡
           swap(s[j],s[j-1]);

}
/*
 * 折半插入排序
 * O(n^2)
 * 只能减少插入排序的比较次数,移动次数不变
 */
void BInsertSort(int s[],int n)
{
    int i,j,begin,end,mid,t;
    for(i=0;i<n-1;i++) //i前面都是排好序的数列
        if(s[i+1]<s[i])
        {
            begin = 0;
            end = i;
            // 找到最接近的右侧点
            while(begin<=end)
            {
                mid = (begin+end)/2;
                if(s[i+1]<s[mid])
                    end = mid-1;
                else
                    begin = mid+1;
            }
            t = s[i+1];
            //记录后移
            for(j=i;j>=begin;j--)
                s[j+1]=s[j];
            s[begin]= t;
        }
}

/*
 * 希尔排序
 * O(N*(logN)2)
 * 希尔排序是插入排序的一种。
 * 如此例第一次分为5组,上下为一组,然后每组排序
 * 8,1,3,0,9           得到: 8,2,4,6,9
 * 7,2,4,6,5                 7,1,3,0,5
 * 然后分为5/2=2组,每组排列...
 * 直至分为1组就是有序了
 */
void ShellSort(int s[],int n)
{
    int i,j;
    for(int gap =n/2;gap>0;gap /=2) //每次折半
        for(i=gap;i<n;i++) //从第二行数据开始,直接插入排序
        {
            for(j=i-gap;j>=0 && s[j+gap]<s[j];j-=gap) //与之前一列数据比较,此处参考插入排序
                swap(s[j],s[j+gap]);
        }
}

/*
 * 基数排序
 * O (nlog(r)m),其中r为所采取的基数,而m为堆数
 * 在某些时候,基数排序法的效率高于其它的比较性排序法
 * 即:先按个位排序,然后按十位排序...
 */

void RadixSort(int m[],int n)
{
    int w = 6,j,k,r=1; //最大6位数
    for(int i = 1;i<=w;i++)
    {
        for(j=1;j<n;j++) //插入排序
            for(k=j-1;k>=0 && m[k+1]/r % 10 < m[k]/r %10;k--)
                swap(m[k],m[k+1]);

        r*=10;
    }
}



/*
 * 堆排序
 */

/*
 * 归并排序
 * O(N*logN)
 * 将两个有效数列合并成一个,因此可以考虑分成两个1组,2组合并成1组,直至整个数列完成
 */
void Merge(int a[], int b[], int low, int mid, int high)  //将A序列的两组(low-mid,mid+1-high),合并到同大小的b中
{
    int k = low;
    int begin1 = low;
    int end1 = mid;
    int begin2 = mid + 1;
    int end2 = high;
    while(k <= high )
    {
        if(begin1 > end1) //第1组完成,将第二组附加上去
            b[k++] = a[begin2++];
        else if(begin2 > end2)
            b[k++] = a[begin1++];
        else
        {
            if(a[begin1] <= a[begin2])
                b[k++] = a[begin1++];
            else
                b[k++] = a[begin2++];
        }
    }
}


//合并序列
void SubMerge(int a[], int b[], int ibegin, int mid,int iend)
{
   int pos = ibegin,i,j;
   for(i=ibegin,j=mid;i<=mid-1&&j<=iend;)
   {
       if(a[i]>a[j])
           b[pos++] = a[j++];
       else
           b[pos++] = a[i++];
   }
   while(i<=mid-1)
       b[pos++] = a[i++];
   while(j<=iend)
       b[pos++] = a[j++];

   //同时保持a也有序
   for(i=ibegin;i<=iend;i++)
	   a[i]=b[i];
}

/*
 * 将a中的从seg开始,长度为size的数排好序
 */

void SubMergeSort(int a[], int b[], int seg, int size)
{
    if(size>=2)
    {
        SubMergeSort(a,b,seg,size/2);//前一半合并到b中
        SubMergeSort(a,b,seg+size/2,size-size/2);//后一半合并到b中
		SubMerge(b,a,seg,seg+size/2,seg +size-1); //保持a,b都有序
    }
}

void MergeSort(int a[],int size)
{
	int *t=a;
    int *temp=new int[size];
	for(int i=0;i<size;i++)
		temp[i]=a[i];
	SubMergeSort(a,temp,0,size);
    delete []temp;
}

/*
 * 堆排序 [采用数组排序]
 * O(N * logN)
 * 1.父结点的键值总是大于或等于(小于或等于)任何一个子节点的键值。
 * 2.每个结点的左子树和右子树都是一个二叉堆(都是最大堆或最小堆)
 * i结点的父结点下标就为(i – 1) / 2,孩子2 * i + 1和2 * i + 2
 * 由于每次重新恢复堆的时间复杂度为O(logN),共N - 1次重新恢复堆操作,再加上前面建立堆时N / 2次向下调整,
 * 每次调整时间复杂度也为O(logN)。二次操作时间相加还是O(N * logN)。故堆排序的时间复杂度为O(N * logN)
 */
void MiniHeap(int a[],int n); //堆话数组 ->建立最小堆
void MinHeapFixdown(int a[],int i,int n); //调整堆元素
void HeapSort(int a[],int n)
{
	int* t = new int[n];
	for(int i=0;i<n;i++)
		t[i]=a[i];
	MiniHeap(t,n);//建立堆
	for(int i=0;i<n;i++)
	{
		a[i] = t[0];
		t[0] = t[n-i-1];//删除堆顶,并调整堆,使堆顶是最小元素
		MinHeapFixdown(t,0,n-i);
	}
	delete []t;
}

void MiniHeap(int a[],int n) //堆话数组 ->建立最小堆
{
	//i 从最后一个不是叶子节点的位置开始调整堆
	for(int i= n/2 - 1;i>=0;i--)
		MinHeapFixdown(a,i,n);
}

void MinHeapFixdown(int a[],int i,int n) //大数下沉,自下而上
{
	int child = 2*i+1; //左孩子
	if(child>=n)//无左右孩子
		return;
	if(child+1<n && a[child+1]<a[child]) //找到左右孩子最小的
		child++;
	if(a[child]>=a[i]) //如果本身就是有序的
		return;
	swap(a[i],a[child]);
	MinHeapFixdown(a,child,n);//孩子继续下沉
}

/*
 * 桶排序
 * 类似Hash,采用分治的思想
 * O(N)-O(N^2)
 */

struct Bucket //桶结构
{
    int* s;
    int size;
    Bucket()
    {
        s =NULL;
        size = 0;
    }
};

void BucketSort(int a[],int n)
{
	Bucket b[1000]; //1千个桶
    for(int i=0;i<1000;i++)
        b[i].s = new int[n];
    //假如数在[0~1,000,000) 之间,分桶
    int t;
    for(int i = 0;i<n;i++)
    {
        t = a[i]/1000;
        b[t].s[b[t].size++] = a[i];
    }
    int pos =0;
    for(int i=0;i<1000;i++)
    {
        if(b[i].size >0)
        {
            QuickSort(b[i].s,0,b[i].size-1); //桶中数字排序
            for(int j=0;j<b[i].size;j++)
                a[pos++] = b[i].s[j];
        }
        delete []b[i].s;
    }
}

int main()
{
	int Flag = 0;
	while(Flag < 10)
	{
		Flag++;
		int n = 1000000;
		int* s =new int[n];
		for(int i=0;i<n;i++)
			s[i] = rand() %1000000; //注rand()产生的数在0到RAND_MAX之间
		srand(time(NULL));
		clock_t ibegin, iend;
		ibegin = clock();
		switch(Flag)
		{
		case 19:
			cout<<"冒泡排序【BubbingSort】:"<<endl;
			BubbingSort(s,n);break;
		case 29:
			cout<<"简单选择排序【SimpleSelectSort】:"<<endl;
			SimpleSelectSort(s,n);break;
		case 3:
			cout<<"快速排序【QuickSort】:"<<endl;
			QuickSort(s,0,n-1);break;
		case 49:
			cout<<"插入排序【InsertSort】:"<<endl;
			InsertSort(s,n);break;
		case 59:
			cout<<"折半插入排序【BInsertSort】:"<<endl;
			BInsertSort(s,n);break;
		case 6:
			cout<<"希尔排序【ShellSort】:"<<endl;
			ShellSort(s,n);break;
		case 7:
			cout<<"归并排序【MergeSort】:"<<endl;
			MergeSort(s,n);break;
		case 8:
			cout<<"堆排序【MiniHeap】:"<<endl;
			HeapSort(s,n);break;
		case 99:
			cout<<"基数排序【RadixSort】:"<<endl;
			RadixSort(s,n);break;
		case 10:
			cout<<"桶排序【BucketSort】:"<<endl;
	            BucketSort(s,n);break;
		}
		iend = clock();
		if(iend - ibegin>0.1)
			cout<<"时间(毫秒):"<<iend - ibegin<<endl;
		//for(int i =0;i<n;i++)
		//	cout<<s[i]<<"  ";
        delete []s;
	    cout<<endl;
	}

    return 0;
}

题 目: 布尔表达式的翻译程序

针对布尔表达式的文法:

B-> TB′
B′-> and T B′|ε
T-> FT ′
T′-> or  FT′|ε
F-> not F |true|false |(B)| i rop i

利用递归下降分析法编制、调试其语法及语义分析程序,生成的中间代码为逆波兰式。编制好分析程序后,设计若干用例,上机测试并通过所设计的分析程序。

设计原则

1.属性文法

属性文法是在上下文无关文法的基础上,允许每个文法符号x(终结符或非终结符)根据处理的需要,定义与x相关联的属性。如x的类型x.type,x的值x.val,x的存储位置x.place等。对属性的处理有计算、传递信息等,属性处理的过程也就是语义处理过程。当然,处理时必须遵循一定的规则。为此,为每个文法规则式定义一组属性的计算规则,称为语义规则。

下面给出属性文法的形式定义:

一个属性文法形式上定义为一个三元组AG,AG=(G,V,E)。其中G表示一个上下文无关文法;V表示属性的有穷集;E表示属性的断言或谓词的有穷集。

2.递归下降分析法

递归子程序法是比较简单直观易于构造的一种语法分析方法。

实现思想:文法中每个非终结符对应一个递归过程(子程序),每个过程的功能是识别由该非终结符推出的串,当某非终结符的产生式有多个候选式时能够按LL(1)形式可唯一地确定选择某个候选式进行推导。

3.逆波兰表达式

逆波兰表达式,它的语法规定,表达式必须以逆波兰表达式的方式给出。逆波兰表达式又叫做后缀表达式。

逆波兰表达式是一种十分有用的表达式,它将复杂表达式转换为可以依靠简单的操作得到计算结果的表达式。例如(a+b)*(c+d)转换为ab+cd+*。

它的优势在于只用两种简单操作,入栈和出栈就可以搞定任何普通表达式的运算。 其运算方式如下:

如果当前字符为变量或者为数字,则压栈,如果是运算符,则将栈顶两个元素弹出作相应运算,结果再入栈,最后当表达式扫描完后,栈里的就是结果。

在Windows7 下利用VS2005开发,开发语言为C++。

课程设计和完整代码下载地址:课设

 

思路:先层次遍历一遍找出最后一个节点,然后目的变为求这个节点的深度。然后我们用循环一层一层找到它的上一层,找到一次,深度加1,最终可以得到二叉树的深度。

/*——– 求深度——层次遍历二叉树 ————–*/
template
int BiTree::LevelDepth()
{
Queue*> que;
TreeNode *p,*q;
que.EnQueue(root);
int deep = 1;
while(!que.QueueEmpty())
{
que.DeQueue(p);
if(p->lchild) que.EnQueue(p->lchild);
if(p->rchild) que.EnQueue(p->rchild);
}
q = p;
while(q != root)
{
que.Clear();
que.EnQueue(root);
while(!que.QueueEmpty())
{
que.DeQueue(p);
if(q == p->lchild || q == p->rchild){deep++;q = p;break;}
if(p->lchild) que.EnQueue(p->lchild);
if(p->rchild) que.EnQueue(p->rchild);
}
}
return deep;
}
#endif

[CODE lang=”c”]
// 名 称 (Unit Name) : 链表List.h 头文件
// 支 持 (Support) : http://www.ourys.com
#ifndef _LIST_H
#define _LIST_H
template
class List;
/*———— 用友元类做节点 ————–*/
template
class ListNode{
public:
ListNode():next(NULL){} //用构造函数初始化指针
friend class List;
private:
DataType data;
ListNode* next;
};
/*———— 链表的定义 ————–*/
template
class List{
public:
List(); //构造带头节点的链表
~List(); //销毁线性表
void ClearList(); //将表重置为空表
bool ListEmpty(); //若为空表存在返回True
int ListLength(); //返回表中数据元素个数
bool GetElem(int i,DataType &e);//用e返回表中第i个元素的值
bool ListInsert(int i,DataType e);//在第i个元素后插入值e
bool ListDelete(int i,DataType &e);//删除第i个元素的值并返回
private:
ListNode* head; //头节点
int len; //链表长度
};
/*———— 构造带头节点的链表 ————–*/
template
List::List()
{
if(!(head=(ListNode*)malloc(sizeof(ListNode)))) exit(1);
len=0;
}
/*———— 销毁链表 ————–*/
template
List::~List()
{
DataType e;
while(len!=0) ListDelete(1,e);
free(head);
head=NULL;
}
/*———— 销毁链表 ————–*/
template
bool List::ListEmpty()
{
return len==0? true:false;
}
/*———— 返回表中数据元素个数 ————–*/
template
int List::ListLength()
{
return len;
}
/*———— 用e返回表中第i个元素的值 ————–*/
template
bool List::GetElem(int i, DataType &e)
{
if(ilen||len==0) return false;
else{
ListNode* p=head;
for(i;i>0;i–) p=p->next;
e=p->data;
return true;
}
}
/*———— 在第i个元素后插入值e ————–*/
template
bool List::ListInsert(int i,DataType e)
{
if(ilen) return false;
else{
ListNode* p;
if(!(p=(ListNode*)malloc(sizeof(ListNode)))) exit(1);
p->data=e;
if(i==0) {p->next=head->next;head->next=p;}
else{
ListNode* temp=head;
for(i;i>0;i–) temp=temp->next;
p->next=temp->next;
temp->next=p;
}
len++;
return true;
}

}
/*———— 删除第i个元素的值并返回 ————–*/
template
bool List::ListDelete(int i,DataType &e)
{
if(ilen) return false;
else{
ListNode* p=head;
ListNode* temp;
for(i;i>1;i–) p=p->next;
temp=p->next;
e=temp->data;
p->next=p->next->next;
free(temp);
temp=NULL;
len–;
return true;
}
}
#endif

/*—————- 基本测试文件 http://ourys.com原创,做人要厚道,转帖请标明来处 ——- Author:Hector ——-*/

#include
#include “List.h”
using namespace std;
int main()
{
List my;
int i,temp;
for(i=0;i for(i=0;i0;i–)
{
my.ListDelete(i,temp);
cout<

[CODE=cplusplus]
/*//////////////////////////////////////////////////////////////////////////////
// 名 称 (Unit Name) : 数组Array.h 头文件
// 作 者 (Author) : Hector(张伟)
// 邮 箱 (E-mail) : ourys@qq.com
// 支 持 (Support) : http://www.ourys.com
// 备 注 (Remarks) : 关于可变参数的头文件参照:http://www.ourys.com/post/56.html
//////////////////////////////////////////////////////////////////////////////*/
#ifndef _ARRAY_H
#define _ARRAY_H
#include //可变参数的头文件
#define MAX_ARRAY_DIM 8 //数组元素最大维数
template
class Array{
public:
Array(int _dim,…); //构造_dim维数组
~Array(); //销毁数组
bool Locate(va_list ap,int &off); //求出该元素在A中的相对地址off
bool Value(DataType* e,…); //e被赋值为数组的相应元素(stdarg.h不能传引用,所以用传地址的形式)
bool Assign(DataType e,…); //将e赋值为数组的相应的元素值
private:
DataType* base; //数组元素基址
int dim; //数组维数
int* bounds; //数组维界基址
int* constants; //数组映像函数常量基址

};
/*———— 构造函数,构造_dim维数组 ————–*/
template
Array::Array(int _dim,…)
{
int elemtotal=1,i;
va_list ap;
if(_dim<1||_dim>MAX_ARRAY_DIM) exit(1);
dim=_dim;
if(!(bounds=(int*)malloc(dim*sizeof(int)))) exit(1);
va_start(ap,_dim);
for(i=0;i bounds[i]=va_arg(ap,int); //把各维的长度赋值给bounds[dim]
if(bounds[i]<0) exit(1); //如果维的长度为0错误
elemtotal*=bounds[i]; //elemtotal 为元素总个数
}
va_end(ap); //保持健壮性
if(!(base=(DataType*)malloc(elemtotal*sizeof(DataType)))) exit(1);
if(!(constants=(int*)malloc(dim*sizeof(int)))) exit(1);
constants[dim-1]=1;
for(i=dim-2;i>=0;–i) constants[i]=bounds[i+1]*constants[i+1];
}
/*———— 销毁数组 ————–*/
template
Array::~Array()
{
if(base) free(base);
if(bounds) free(bounds);
if(constants) free(constants);
bounds=constants=NULL;
base=NULL;
dim=0;
}
/*———— 求出该元素在A中的相对地址off ————–*/
template
bool Array::Locate(va_list ap, int &off)
{
int ind;
for(int i=0;i {
ind=va_arg(ap,int);
if(ind<0||ind>=bounds[i]) exit(1);
off+=constants[i]*ind;
}
va_end(ap);
return true;
}
/*———— e被赋值为数组的相应元素 ————–*/
template
bool Array::Value(DataType* e, …)
{
va_list ap;
int off=0;
va_start(ap,e);
if(!Locate(ap,off)) return false;
*e=*(base+off);
return true;
}
/*———— 将e赋值为数组的相应的元素值 ————–*/
template
bool Array::Assign(DataType e, …)
{
va_list ap;
int off=0;
va_start(ap,e);
if(!Locate(ap,off)) return false;
*(base+off)=e;
return true;
}

#endif

/*—————- 基本测试文件 ——- Author:Hector ——-*/

#include
#include “Array.h”
using namespace std;
int main()
{
int i,j,k,dim=3,bound1=3,bound2=4,bound3=5;
char temp=0;
Array my(dim,bound1,bound2,bound3);
for(i=0;i for(j=0;j for(k=0;k my.Assign(‘c’,i,j,k);
for(i=0;i for(j=0;j for(k=0;k my.Value(&temp,i,j,k);
cout< }
return 0;
}

[/CODE]

[CODE=cplusplus]
/*//////////////////////////////////////////////////////////////////////////////

// 名 称 (Unit Name) : 队列 Queue.h 头文件

// 作 者 (Author) : Hector(张伟)

// 邮 箱 (E-mail) : ourys@qq.com

// 支 持 (Support) : http://www.ourys.com

// 备 注 (Remarks) :

//////////////////////////////////////////////////////////////////////////////*/

#ifndef _QUEUE_H

#define _QUEUE_H

#define QUEUE_INIT_SIZE 100 //初始队列的最大长度

#define QUEUEINCREMENT 10 //每次新增的长度

template

class Queue{

public:

Queue(); //构造函数,创建一个新的队列

bool EnQueue(DataType e); //插入一个值为e的队尾元素

bool GetHead(DataType &e); //取出队头元素

bool DeQueue(DataType &e); //删除队头元素

bool QueueEmpty(); //判断是否非空

bool Clear(); //清空队列

~Queue(); //销毁队列

private:

DataType *front;

DataType *rear;

int queuesize;

};

/*———— 构造函数,创建一个新的队列 ————–*/

template

Queue::Queue()

{

if(!(front=(DataType*)malloc(QUEUE_INIT_SIZE*sizeof(DataType)))) exit(1);

rear=front;

queuesize=QUEUE_INIT_SIZE;

}

/*———— 插入一个值为e的队尾元素 ————–*/

template

bool Queue::EnQueue(DataType e)

{

if(rear-front>=queuesize){

if(!(front=(DataType*)realloc(front,(queuesize+QUEUEINCREMENT)*sizeof(DataType)))) exit(1);

rear=front+queuesize;

queuesize+=QUEUEINCREMENT;

}

*rear++=e;

return true;

}

/*———— 取出队头元素 ————–*/

template

bool Queue::GetHead(DataType &e)

{

if(rear==front) return false;

e=*front;

return true;

}

/*———— 删除队头元素 ————–*/

template

bool Queue::DeQueue(DataType &e)

{

if(rear==front) return false;

e=*front;

DataType* temp;

temp=front;

while(temp!=rear) //为了删除后的空间继续利用,所有元素都向前移一位

{

*temp=*(temp+1);

temp++;

}

rear–;

return true;

}

/*———— 判断是否非空 ————–*/
template
bool Queue::QueueEmpty()
{
return rear==front? 1:0;
}

/*———— 清空队列 ————–*/
template
bool Queue::Clear()
{
rear=front;
return true;
}

/*———— 销毁队列 ————–*/

template

Queue::~Queue()

{

free(front);

}

#endif

/*—————- 基本测试文件 ——- Author:Hector ——-*/

#include
#include “Queue.h”
using namespace std;
int main()
{
Queue my;
int temp;
for(int i=2;i<10;i++)
{
my.EnQueue(i);
my.GetHead(temp);
cout< }
for(int i=2;i<10;i++)
{
my.DeQueue(temp);
cout< }
my.DestroyQueue();
return 0;
}
[/CODE]

[CODE=cplusplus]
/*//////////////////////////////////////////////////////////////////////////////
// 名 称 (Unit Name) : 队列 Queue.h 头文件
// 作 者 (Author) : Hector(张伟)
// 邮 箱 (E-mail) : ourys@qq.com
// 支 持 (Support) : http://www.ourys.com
// 备 注 (Remarks) :
//////////////////////////////////////////////////////////////////////////////*/
typedef int Datatype;
typedef struct tagQNode{
Datatype data;
struct tagQNode* next;
}*QNode;
typedef struct {
QNode front;
QNode rear;
}*LinkQueue;
/*———— 构造一个空的队列 ————–*/
LinkQueue InitQueue()
{
LinkQueue q;
q->front=(QNode)malloc(sizeof(struct tagQNode));
if(!q->front) exit(1);
q->rear=q->front;
q->front->next=NULL;
return q;
}
/*———— 销毁队列 ————–*/
int DestroyQueue(LinkQueue q)
{
while(q->front){
q->rear=q->front->next;
free(q->front);
q->front=q->rear;
}
return 1;
}
/*———- 插入一个为e的队尾元素 ———–*/
void EnQueue(LinkQueue q,Datatype e)
{
QNode p=(QNode)malloc(sizeof(struct tagQNode));
p->data=e;
p->next=NULL;
q->rear->next=p;
q->rear=p;
}

/*———- 删除一个队头元素,并返回 ———-*/
Datatype DeQueue(LinkQueue q)
{
if(q->front==q->rear) return 0;
Datatype e=q->front->next->data;
QNode p=q->front->next;
q->front->next=p->next;
if(q->rear==p) q->rear=q->front;
free(p);
return e;
}

/*—————- 基本测试文件 ——- Author:Hector ——-*/
#include
#include
#include “Queue.h”
int main(void)
{
LinkQueue queue=InitQueue();
EnQueue(queue,5);
return 0;
}
[/CODE]