链式队列的实现 |flying0033
/* 队列是一种先进先出线性表,队列是线性表的特化 也具有线性表的性质分为:顺序队列与链式队列 链式队列与线性表的单链表相似只不过链式队列只 允许从头部进行删除、尾部进行插入.需要为链式队列 创建一个头结点包括两个指针,指向队头的指针(front) 与指向队尾的指针(rear).当两个指针相等时队列为空*/#ifndef LINKQUEUE_H#define LINKQUEUE_H
typedef int ElemType;//队列的数据类型
typedef struct node{
ElemType data; //队列的数据类型
struct node *next; //指向下一个结点
}QueNode,*QuePtr;
typedef struct{
QuePtr front; //指向队头的指针
QuePtr rear; //指向队尾的指针
}LinkQueue;
void InitQueue(LinkQueue *q); //初始化队列
void CreateQueue(LinkQueue *q); //创建队列
void EnQueue(LinkQueue *q,ElemType e); //进队操作,将元素e压入队列中
void DeQueue(LinkQueue *q,ElemType *e); //出队操作,将出队的元素存入*e中
int GetQueueLength(LinkQueue *q); //获取队列的长度
void Print(LinkQueue *q); //打印队列的元素
void Clear(LinkQueue *q); //清空队列
void TopQueue(LinkQueue *q,ElemType *e); //返回队头的元素
#endif //LINKQUEUE_H
#include "LinkQueue.h"
#include <stdio.h>
#include <stdlib.h>
void InitQueue(LinkQueue *q) //初始化队列
{
q->front = q->rear = (QuePtr)malloc(sizeof(QueNode)); //初始化队头与队尾的指针指向头结点
q->front->next = NULL;
}
void CreateQueue(LinkQueue *q) //创建队列
{
InitQueue(q);
printf("请输入要进队的元素以CTRL+Z结尾\n");
int k;
while((scanf("%d",&k)) != EOF)
EnQueue(q,k);
}
void EnQueue(LinkQueue *q,ElemType e) //将元素e进队
{
QuePtr temp = (QuePtr)malloc(sizeof(QueNode)); //创建新结点
if(temp) //如果内存分配成功
{
temp->data = e; //初始化新结点的数据为e
temp->next = NULL; //队列只能从队尾插入所以下一个结点初始化为NULL
q->rear->next = temp; //将队尾结点的指针指向新结点,如果新结点为第一个结点则q->rear->next相当于q->front->next
q->rear = temp; //将指向队尾的指针指向新结点
}
}
void DeQueue(LinkQueue *q,ElemType *e) //队头的结点出队,将出队的结点的元素存入*e
{
if(q->front == q->rear) //队列为空
return;
QuePtr temp = q->front->next; //初始化temp为要出队的结点的指针
if(q->front->next == q->rear) //如果要出队的结点为最后一个结点,使q->rear指向头结点防止出现悬空的指针
q->rear = q->front;
*e = temp->data; //将出队的数据元素存入*e
q->front->next = temp->next; //使下一个结点成为队头,如果没有下一个结点则为NULL
free(temp); //删除要出队的结点
}
bool IsEmpty(LinkQueue *q) //判断队列是否为空
{
if(q->front == q->rear)
return true;
return false;
}
int GetQueueLength(LinkQueue *q) //返回队列的长度
{
QuePtr temp = q->front;
int i = 0;
while(temp != q->rear)
{
++i;
temp = temp->next;
}
return i;
}
void Clear(LinkQueue *q) //清空队列
{
QuePtr temp = q->front->next;
while(temp)
{
QuePtr tp = temp;
temp = temp->next;
free(tp);
}
temp = q->front;
q->front = q->rear = NULL;
free(temp);
}
void Print(LinkQueue *q) //打印队列的元素
{
if(q->front == q->rear)
return;
QuePtr temp = q->front->next;
while(temp != q->rear)
{
printf("%d ",temp->data);
temp = temp->next;
}
printf("%d",temp->data);
printf("\n");
}
void TopQueue(LinkQueue *q,ElemType *e) //返回队头的结点元素存入*e
{
if(q->front == q->rear)
return;
*e = q->front->next->data;
}
#include "LinkQueue.h"
#include <stdio.h>
int main()
{
LinkQueue q;
CreateQueue(&q);
Print(&q);
int top;
TopQueue(&q,&top);
printf("队头的元素为:%d\n",top);
int len = GetQueueLength(&q);
int k;
printf("将队列中的所有元素出队:\n");
for(int i = 0;i < len;++i)
{
DeQueue(&q,&k);
printf("%d ",k);
}
printf("\n");
Clear(&q);
return 0;
}
作者：flying0033 发表于2011-12-23 23:58:54 原文链接
页:
[1]