循环队列

#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;

}