循环队列
#include<stdio.h>
#include<stdlib.h>
#defineFALSE0
#defineTRUE1
typedef_BoolBOOL;
typedefintElemType;
//循环队列结构体定义
typedefstruct
{
intfront; //对头
intrear; //队尾
intmaxSize; //允许存储的最大空间数量
ElemType*element; //element表示一维数组首地址指针
}Queue;
//创建一个能容纳mSize个单元的空队列
voidcreate(Queue*Q,intmSize)
{
Q->maxSize =mSize;
Q->element = (ElemType*)malloc(sizeof(ElemType)*mSize);
Q->front =Q->rear = 0;
}
//销毁一个已存在的队列，即释放队列占用的数组空间
voidDestroy(Queue*Q)
{
Q->maxSize = -1;
free(Q->element);
Q->front =Q->rear = -1;
}
//判断队列是否为空，若是，则返回TRUE,否则返回FALSE
BOOLIsEmpty(Queue*Q)
{
return Q->front ==Q->rear;
}
//判断队列是否已满，若是，则返回TRUE,否则返回FALSE
BOOLIsFULL(Queue*Q)
{
return(Q->rear + 1) %Q->maxSize ==Q->front;
}
//获取队头元素，并通过x返回。若是，则返回TRUE,否则返回FALSE
BOOLFront(Queue*Q,ElemType*x)
{
if(IsEmpty(Q))
returnFALSE; //空列处理
*x=Q->element[(Q->front + 1) %Q->maxSize];
returnTRUE;
}
//在队列Q的队尾插入元素x（入栈操作）。操作成功，则返回TRUE,否则返回FALSE
BOOLEnQueue(Queue*Q,ElemTypex)
{
if(IsFULL(Q))
returnFALSE; //溢出列处理
Q->rear = (Q->rear + 1) %Q->maxSize;
Q->element[Q->rear] =x;
returnTRUE;
}
//从队列Q中删除队头元素x（出栈操作）。操作成功，则返回TRUE,否则返回FALSE
BOOLDeQueue(Queue*Q)
{
if(IsEmpty(Q))
returnFALSE; //空队列处理
Q->front = (Q->front + 1) %Q->maxSize;
returnTRUE;
}
//清除队列中的全部元素，但并不释放空间。
voidClear(Queue*Q)
{
Q->front =Q->rear = 0;
}
/*
int output(Queue *Q)
{
int x;
if (IsEmpty(Q))
return FALSE;
while (!IsEmpty(Q))
{
Front(&Q, &x); //获取队头元素，并通过x返回。
DeQueue(&Q); //从队列Q中删除队头元素x
printf("%d", x);
}
return TRUE;
}
void main()
{
Queue *Q = new Queue();
int i,j,x;
create(Q, 10);
printf("请输入要插入队中的元素：\n");
for (i = 0; i < 9; i++)
{
scanf_s("%d", &j);
EnQueue(Q, j); //在队列Q的队尾插入元素i
}
printf("循环队列的元素：");
output(Q);
printf("\n");
Destroy(Q);
}
*/
intoutput(QueueQ)
{
intx;
if(IsEmpty(&Q))
returnFALSE;
while(!IsEmpty(&Q))
{
Front(&Q, &x); //获取队头元素，并通过x返回。
DeQueue(&Q); //从队列Q中删除队头元素x
printf("%d", x);
}
returnTRUE;
}
voidmain()
{
QueueQ;
inti,x;
create(&Q, 10);
for(i = 0; i < 9; i++)
EnQueue(&Q, i); //在队列Q的队尾插入元素i
printf("循环队列的元素：");
output(Q);
printf("\n循环队列的队顶元素：");
Front(&Q, &x);
printf("%d", x);
printf("\n删除一个栈顶元素的循环队列的元素：");
DeQueue(&Q);
output(Q);
printf("\n");
Destroy(&Q);
}
//链式队列(先进先出，后进后出）队尾进队、队头出队
#include<stdio.h>
#include<stdlib.h>
#defineERROR0
#defineOK1
typedefintElemType;
typedefstructNode{
ElemTypeElement; //数据域
structNode*link; //指针域
}Node;
typedefstruct{
structNode*front; //队头指针
structNode*rear; //队尾指针
intn;
}LinkQueue;
//初始化（创建）
intInit(LinkQueue*q){
q->rear =NULL;
q->front =NULL;
q->n = 0;
returnOK;
}
//销毁一个已存在的队列，即释放队列占用的数组空间
voidDestroy(LinkQueue*q){
}
//判断队列是否为空，若是，则返回OK,否则返回ERROR
intIsEmpty(LinkQueue*q){
returnq->n==0;
}
//获取队头元素，并通过x返回。若是，则返回OK,否则返回ERROR
intFront(LinkQueue*q,ElemType*x){
if(IsEmpty(q))
returnERROR;
*x=q->front->Element;
returnOK;
}
//在队列Q的队尾插入元素x（入栈操作）。操作成功，则返回OK,否则返回ERROR
intEnQueue(LinkQueue*q,ElemTypex){
Node*p;
p = (Node*)malloc(sizeof(Node)); //申请新结点空间
if(p !=NULL){
p->Element =x;
p->link =NULL;
if(q->front ==NULL){
q->front = p; //插入的是空队
}
else
{
q->rear->link = p;
}
q->rear = p;
q->n++;
}
returnOK;
}
//从队列Q中删除队头元素x（出栈操作）。操作成功，则返回OK,否则返回ERROR
intDeQueue(LinkQueue*q){
Node*p ;
if(IsEmpty(q))
returnERROR;
p =q->front; //修改队头指针
q->front = p->link;
free(p); //释放已经删除结点空间
q->n--;
returnOK;
}
//清除堆栈中的所有元素，但不释放空间
voidClear(LinkQueue*q){
q->front =q->rear =NULL;
}
//输出
intoutput(LinkQueueq){
intx;
if(IsEmpty(&q))
returnERROR;
while(!IsEmpty(&q)){
Front(&q, &x);
DeQueue(&q);
printf("%d", x);
}
returnOK;
}
intmain(){
inti;
LinkQueueq;
Init(&q);
for(i = 0; i < 10; i++)
EnQueue(&q, i); //在队列Q的队尾插入元素i
printf("链式队列的元素：");
output(q);
Destroy(&q);
printf("\n");
}
优先权队列
#include<stdio.h>
#include<stdlib.h>
#define Error(str) FatalError(str)
#define FatalError(str) fprintf(stderr,"%s\n",str),exit(1)
#define MinPQSize (10)
#define MinData (-32767)
typedef int ElemType;
struct Heapstruct
{
int Capacity;
int Size;
ElemType *Elements;
};
typedef struct Heapstruct *PriorityQueue;
//构造一棵空的优先队列
PriorityQueue Initialize(int MaxNumber)
{
PriorityQueue H;
if (MaxNumber < MinPQSize) //如果队列最大空间小于
Error("Priority queue size is too small!");
H = (PriorityQueue)malloc(sizeof(struct Heapstruct));
if (H == NULL)
FatalError("out of space !");
//分配数组空间，加上一个哨兵的空间
H->Elements = (ElemType*)malloc((MaxNumber + 1)*sizeof(ElemType));
if (H->Elements == NULL)
FatalError("out of space !");
H->Capacity = MaxNumber;
H->Size = 0;
H->Elements[0] = MinData;
return H;
}
//H->Elements[0]是一个哨兵
//判断优先队列是否为空
int IsEmpty(PriorityQueue H)
{
return H->Size == 0;
}
//查找优先队列的最小值
ElemType FindMin(PriorityQueue H)
{
if (!IsEmpty(H))
return H->Elements[1];
Error("Priority queue is empty !");
return H->Elements[0];
}
//判断优先队列是否为满
int IsFull(PriorityQueue H)
{
return H->Size == H->Capacity;
}
//销毁优先队列
void Destroy(PriorityQueue H)
{
free(H->Elements);
free(H);
}
//插入元素
void Insert(ElemType x, PriorityQueue H)
{
int i;
if (IsFull(H))
{
Error("Priority queue is full");
return;
}
for (i = ++H->Size; H->Elements[i / 2] > x; i /= 2)
//插入新元素向上调整建堆
H->Elements[i] = H->Elements[i / 2];
//直到找到位置
H->Elements[i] = x;
}
//删除优先队列最小值
ElemType DeleteMin(PriorityQueue H)
{
int i, Child;
ElemType minElenent, lastElement;
if (IsEmpty(H))
{
Error("Priority queue is empty !");
return H->Elements[0];
}
minElenent = H->Elements[1];
lastElement = H->Elements[H->Size--];
for (i = 1; i * 2 <= H->Size; i = Child)
{
//找最小的元素
Child = i * 2;
if (Child != H->Size && H->Elements[Child + 1] < H->Elements[Child])
Child++;
if (lastElement>H->Elements[Child])
H->Elements[i] = H->Elements[Child];
else
break;
}
H->Elements[i] = lastElement;
return minElenent;
}
//创建空的优先队列
void MakeEmpty(PriorityQueue H)
{
H->Size = 0;
}
int main()
{
PriorityQueue H = Initialize(20);
int ar[] = { 35, 24, 15, 22, 38, 18, 62, 60, 20, 11 };
int i;
for (i = 0; i < 10; i++)
Insert(ar[i], H);
for (i = 0; i < 10; i++)
printf("%d\n", DeleteMin(H));
return 0;
}
