C语言实现链队列基本操作

246 阅读 0 评论 163 点赞

我是靠谱客的博主尊敬小刺猬，这篇文章主要介绍C语言实现链队列基本操作，现在分享给大家，希望可以做个参考。

队列的链式存储结构实现，相比于循环队列实现要复杂一些，但是没有队满的限制。

头文件声明

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <stdio.h>
#include <stdlib.h>

/**
 * 队列的链式存储实现
 * [带头结点的单链表]
 * [-类似于链栈，队列的链式存储实现也不会出现队满的情况]
 */
//数据类型
typedef int ElemType;

//定义节点
typedef struct SqQueueNode
{
 ElemType data;//数据域
 struct SqQueueNode* next; //指针域
}SqQueueNode;
//定义队列
typedef struct SqQueueLink{
 SqQueueNode* front;//队头指针
 SqQueueNode* rear;//队尾指针
}SqQueueLink;

//初始化队列
void InitQueueLink(SqQueueLink* q);
//判断队空
int EmptyQueueLink(SqQueueLink q);
//入队操作
void EnQueueLink(SqQueueLink *q,ElemType e);
//出队操作
void DeQueueLink(SqQueueLink q,ElemType *e);
//获取队列长度
int LengthQueueLink(SqQueueLink q);
//打印队列
void printSqQueueLink(SqQueueLink q);
//获取队头元素
void GetHeadLink(SqQueueLink q,ElemType* e);

函数实现

复制代码

#include "SqQueueLink.h"

//初始化队列
void InitQueueLink(SqQueueLink* q){
 //创建头结点
 SqQueueNode* pNode=(SqQueueNode*)malloc(sizeof(SqQueueNode));
 pNode->next=NULL;//指针域置空[数据域不存储任何内容]
 //初始化队列-[使队头指针和队尾指针指向头结点]
 q->front=pNode;
 q->rear=pNode;
}

//判断队空
int EmptyQueueLink(SqQueueLink q){
 return q.front==q.rear;
}

//入队操作
void EnQueueLink(SqQueueLink *q,ElemType e){
 //创建新的数据元素节点
 SqQueueNode* newNode=(SqQueueNode*)malloc(sizeof(SqQueueNode));
 newNode->data=e;//指定数据域
 newNode->next=NULL;//指针域置空
 //入队操作[从队尾入队]
 q->rear->next=newNode;
 q->rear=newNode;
}

//出队操作
void DeQueueLink(SqQueueLink q,ElemType *e){
 //[从队头出队]
 SqQueueNode* p=NULL;
 //是否队空
 if (q.front==q.rear)
  return;
 p=q.front->next;//获取首节点
 *e=p->data;
 //使队头指针指向下一节点
 q.front->next=p->next;
 //如果原队列中只有一个节点，要将队尾指针和队头指针均指向同一节点-置空
 if (q.rear==p)
  q.rear=q.front;
 //释放原首节点
 free(p);
}

//获取队列长度
int LengthQueueLink(SqQueueLink q){
 //辅助指针
 SqQueueNode* pNode=q.front->next;
 int count=0;
 //获取队列长度
 while (pNode!=q.rear)
 {
  count++;
  pNode=pNode->next;
 }
 return count;
}

//打印队列
void printSqQueueLink(SqQueueLink q){
 //辅助指针
 SqQueueNode* p=q.front->next;
 while (p!=q.rear)
 {
  printf("%4d",p->data);
  p=p->next;
 }
 printf("n");
}

//获取队头元素
void GetHeadLink(SqQueueLink q,ElemType* e){
 //判断队列是否为空
 if (q.front==q.rear)
  return;
 //获取队头元素的值
 *e=q.front->next->data;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include "SqQueueLink.h"


//初始化队列
void InitQueueLink(SqQueueLink* q){
 //创建头结点
 SqQueueNode* pNode=(SqQueueNode*)malloc(sizeof(SqQueueNode));
 pNode->next=NULL;//指针域置空[数据域不存储任何内容]
 //初始化队列-[使队头指针和队尾指针指向头结点]
 q->front=pNode;
 q->rear=pNode;
}

//判断队空
int EmptyQueueLink(SqQueueLink q){
 return q.front==q.rear;
}

//入队操作
void EnQueueLink(SqQueueLink *q,ElemType e){
 //创建新的数据元素节点
 SqQueueNode* newNode=(SqQueueNode*)malloc(sizeof(SqQueueNode));
 newNode->data=e;//指定数据域
 newNode->next=NULL;//指针域置空
 //入队操作[从队尾入队]
 q->rear->next=newNode;
 q->rear=newNode;
}

//出队操作
void DeQueueLink(SqQueueLink q,ElemType *e){
 //[从队头出队]
 SqQueueNode* p=NULL;
 //是否队空
 if (q.front==q.rear)
  return;
 p=q.front->next;//获取首节点
 *e=p->data;
 //使队头指针指向下一节点
 q.front->next=p->next;
 //如果原队列中只有一个节点，要将队尾指针和队头指针均指向同一节点-置空
 if (q.rear==p)
  q.rear=q.front;
 //释放原首节点
 free(p);
}

//获取队列长度
int LengthQueueLink(SqQueueLink q){
 //辅助指针
 SqQueueNode* pNode=q.front->next;
 int count=0;
 //获取队列长度
 while (pNode!=q.rear)
 {
  count++;
  pNode=pNode->next;
 }
 return count;
}

//打印队列
void printSqQueueLink(SqQueueLink q){
 //辅助指针
 SqQueueNode* p=q.front->next;
 while (p!=q.rear)
 {
  printf("%4d",p->data);
  p=p->next;
 }
 printf("n");
}

//获取队头元素
void GetHeadLink(SqQueueLink q,ElemType* e){
 //判断队列是否为空
 if (q.front==q.rear)
  return;
 //获取队头元素的值
 *e=q.front->next->data;
}

函数测试

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include "SqQueueLink.h"

int main(int argc,char** argv){
 //声明队列
 SqQueueLink sqLink;
 int i;
 ElemType data;
 //初始化队列
 InitQueueLink(&sqLink);
 //判断队列是否为空
 printf("is Empty?%dn",EmptyQueueLink(sqLink));
 //入队操作
 for (i=0;i<=20;i++)
 {
  EnQueueLink(&sqLink,i+1);
 }
 //判断队列是否为空
 printf("is Empty?%d,len=%dn",EmptyQueueLink(sqLink),LengthQueueLink(sqLink));
 //打印队列
 printSqQueueLink(sqLink);
 //出队列操作
 DeQueueLink(sqLink,&data);
 //判断队列是否为空
 printf("is Empty?%d,len=%dn",EmptyQueueLink(sqLink),LengthQueueLink(sqLink));
 //打印队列
 printSqQueueLink(sqLink);
 //获取队头元素的值
 GetHeadLink(sqLink,&data);
 printf("the first node value is %dn",data);
 return 0;
}