数据结构(9)--链队列的定义以及相关操作的实现

时间：2020-12-21 10:20:23

参考书籍：数据结构（C语言版）严蔚敏吴伟民编著清华大学出版社

1.队列的定义

  栈是一种后进先出的数据结构，而在实际问题中还经常使用一种“先进先出” (FIFO---First  In First Out)的数据结构：即插入在表一端进行，而删除在表的另一端进行，我们将这种数据结构称为队或队列，把允许插入的一端叫队尾(rear) ，把允许删除的一端叫队头(front)。如图所示是一个有5 个元素的队列。入队的顺序依次为a1、 a2 、a3 、a4  、 a5 ，出队时的顺序将依然是a1、 a2 、a3 、a4  、 a5 。

  显然，队列也是一种运算受限制的线性表，所以又叫先进先出表。  

2.队列的存储

2.1顺序队列

顺序队列的类型定义如下：
#define  maxsize 100/*队列的最大容量*/
typedef char QElemtype;
struct  Queue
 {   QElemtype data[maxsize ];  //队员的存储空间
     int front;  //队头队尾指针
     int rear;   //队尾指针
 };
    定义一个顺序队的变量：      Queue  Q;
    队列的数据区为：Q.data[0]---Q.data[maxsize -1]
    队头指针：Q.front    队尾指针：Q.rear
    约定队头指针指向队头元素，队尾指针指向队尾元素后面一个位置（这样的设置是为了某些运算的方便，并不是唯一的方法）。 

    空队列：Q.front = Q.rear = 0

    这种存储结构容易产生“假溢出”现象，在下一篇博客中会具体说明。

2.2链队列

链队列的类型定义如下：

typedef char QElemType;
typedef struct QNode{
QElemType data;
struct QNode *next;
}QNode;
typedef struct{
QNode *f;//队头指针
QNode *r;//队尾指针
}LinkQueue;

3.链队列相关操作的实现

3.1 链队列定义

#include<stdio.h>
#include<stdlib.h>
//队列要在队头执行删除（出队）操作，早队尾执行插入（入队）操作，故需要知道队头位置和队尾位置即可唯一确定一个队列
//和线性表类似，也有2种存储表示：顺序队列和链队列
//本实例实现链队列
//判断队列是否为空：Q.f == Q.r
#define NULL 0
typedef char QElemType;

typedef struct QNode{
QElemType data;
struct QNode *next;
}QNode;

typedef struct{
QNode *f;//队头指针
QNode *r;//队尾指针
}LinkQueue;

3.2初始化空队列

//初始化一个带有头节点的空队列
void initQueue(LinkQueue &Q){
Q.f = Q.r = (QNode *)malloc(sizeof(QNode));
Q.f->next = NULL;
}

3.3销毁一个队列

//销毁队列
void destroyQueue(LinkQueue &Q){
while(Q.f){
QNode *p = Q.f->next;
free(Q.f);
Q.f = p;
}
}

3.4入队操作

//入队操作,在队尾插入
void enQueue(LinkQueue &Q, QElemType e){
QNode *p = (QNode *)malloc(sizeof(QNode));
p->data = e;
p->next = NULL;
Q.r->next = p;
Q.r = p;
}

3.5出队操作

//出队操作，在队头删除,并用e返回删除的元素
void deQueue(LinkQueue &Q, QElemType &e){
if(Q.f == Q.r){
printf("队列为空，删除操作失败！\n");
return;
}
QNode *p = Q.f->next;
e = p->data;
Q.f->next = p->next;
//如果要删除的是尾指针(整个队列此时只有一个元素)，还需要修改尾指针
if(p == Q.r)
Q.r = Q.f;
free(p);
printf("元素%c出队\n", e);
}

3.6利用入队操作创建队列

//利用入队操作创建一个队列,他拥有n个元素
void createQueue(LinkQueue &Q, int n){
int i = 0;
printf("请输入%d个字符元素：\n", n);
while(i < n){
char dataTmp;
scanf("%c", &dataTmp);
enQueue(Q, dataTmp);
i++;
getchar();//吃掉换行符
}
}

3.7打印队列

void printQueue(LinkQueue Q){
QNode *p = Q.f->next;
while(p){
printf("%c ", p->data);
p = p->next;
}
printf("\n\n");
}

4.演示

void main(){
LinkQueue Q;//定义一个队列
initQueue(Q);
createQueue(Q, 5);
printQueue(Q);
printf("执行入队操作：");
printf("输入您要插入的字符串数据：");
QElemType e;
scanf("%c", &e);
enQueue(Q, e);
printQueue(Q);

printf("执行出队操作：");
deQueue(Q, e);
printQueue(Q);
}


数据结构(9)--链队列的定义以及相关操作的实现

标签：

相关文章