1. 首页
  2. 文章中心
  3. 数据结构

数据结构（C语言）-线性表之队列（顺序队列、链式队列）-学习笔记041. 基本介绍2. 顺序队列3. 链式队列

145 阅读 0 评论
我是靠谱客的博主 哭泣嚓茶，这篇文章主要介绍数据结构（C语言）-线性表之队列（顺序队列、链式队列）-学习笔记041. 基本介绍2. 顺序队列3. 链式队列，现在分享给大家，希望可以做个参考。

文章目录

  • 1. 基本介绍
  • 2. 顺序队列
    • 2.1 定义 sequeue.h
    • 2.2 sequeue.c
  • 3. 链式队列
    • 3.1 定义 linkqueue.h
    • 3.2 linkqueue.c

所有代码实现：Tian-hy/c_ds

1. 基本介绍

  • 队列是限制在一端进行插入和另一端进行删除操作的线性表
  • 允许进行存入操作的一端是队尾
  • 允许进行删除操作的是队头
  • 没有元素时是空队
  • 先进先出

2. 顺序队列

2.1 定义 sequeue.h

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#define N 128

typedef int data_t;

typedef struct{
	data_t data[N];
	int front, rear;
}sequeue;

sequeue *sequeue_create(); //创建队列
int sequeue_enqueue(sequeue *sq, data_t x);//入队
data_t sequeue_dequeue(sequeue *sq);//出队
int sequeue_empty(sequeue *sq);//判断队是否为空
int sequeue_full(sequeue *sq);//判断队是否已满
int sequeue_clear(sequeue *sq);//清空队列数据
sequeue *sequeue_free(sequeue *sq);//释放队列空间

2.2 sequeue.c

  • front是队头，rear是队尾指向的空位置，初始化的时候都是指向0
复制代码
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
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "sequeue.h"

sequeue *sequeue_create(){
	sequeue *sq;
	if ((sq = (sequeue *)malloc(sizeof(sequeue))) == NULL){
		return NULL;
	}
	memset(sq->data, 0, sizeof(sq->data));
	sq->front = sq->rear = 0;
	return sq;
}

int sequeue_enqueue(sequeue *sq, data_t x){
	if (sq == NULL){
		printf("sq is NULLn");
		return -1;
	}
	if ((sq->rear+1)%N == sq->front){
		printf("sqeueue is fulln");
		return -1;
	}
	sq->data[sq->rear] = x;
	sq->rear = (sq->rear+1) % N;
	return 0;
}

data_t sequeue_dequeue(sequeue *sq){
	if (sq == NULL){
		printf("sq is NULLn");
		return -1;
	}
	data_t data;
	data = sq->data[sq->front];
	sq->front = (sq->front+1)%N;
	return data;
}

int sequeue_empty(sequeue *sq){
	if (sq == NULL){
		printf("sq is NULLn");
		return -1;
	}
	return sq->front == sq->rear;
}

int sequeue_full(sequeue *sq){
	if (sq == NULL){
		printf("sq is NULLn");
		return -1;
	}
	return (sq->rear+1)%N == sq->front;
}

int sequeue_clear(sequeue *sq){
	if (sq == NULL){
		printf("sq is NULLn");
		return -1;
	}
	sq->front = sq->rear = 0;
	return 0;
}

sequeue *sequeue_free(sequeue *sq){
	if (sq == NULL){
		printf("sq is NULLn");
		return NULL;
	}
	free(sq);
	sq = NULL;
	return NULL;
}

3. 链式队列

  • 插入在队尾进行，删除操作在队头进行，由队头指针和队尾指针控制队
    在这里插入图片描述
  • 空队如下图所示
    在这里插入图片描述

3.1 定义 linkqueue.h

先定义一个结点，在定义一个队列，队列的front指向头结点，队列的rear指向链表的最后一个元素

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
typedef int data_t;

typedef struct node{
	data_t data;
	struct node *next;
}listnode, *linklist;

typedef struct {
	linklist front;
	linklist rear;
}linkqueue;

linkqueue *create();
int enqueue(linkqueue *lq, data_t x);
data_t dequeue(linkqueue *lq);
int empty(linkqueue *lq);
int clear(linkqueue *lq);
linkqueue *queue_free(linkqueue *lq);

3.2 linkqueue.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
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
#include <stdio.h>
#include <stdlib.h>
#include "linkqueue.h"

linkqueue *create(){
	linkqueue *lq;
	lq = (linkqueue *)malloc(sizeof(linkqueue));
	if (lq == NULL)
		return NULL;
	lq->front = lq->rear = (linklist)malloc(sizeof(listnode));
	if (lq->front == NULL)
		return NULL;

	lq->front->next = NULL;
	lq->front->data = 0;
	return lq;
}

int enqueue(linkqueue *lq, data_t x){
	linklist p;
	if ((p = (linklist)malloc(sizeof(listnode))) == NULL){
		return -1;
	}
	p->data = x;
	p->next = NULL;
	lq->rear->next = p;
	lq->rear = p;
	return 0;
}

data_t dequeue(linkqueue *lq){
	linklist p;
	p = lq->front;
	lq->front = lq->front->next;
	free(p);
	p = NULL;
	return lq->front->data;
}

int empty(linkqueue *lq){
	return (lq->front == lq->rear);
}

int clear(linkqueue *lq){
	linklist p;
	while(lq->front != lq->rear){
		p = lq->front;
		lq->front = lq->front->next;
		printf("clear: %dn", p->data);
		free(p);
	}
	return 0;
}

linkqueue *queue_free(linkqueue *lq){
	linklist p;
	while(lq->front){
		p = lq->front;
		lq->front = lq->front->next;
		printf("free: %dn", p->data);
		free(p);
	}
	free(lq);
	return NULL;
}

最后

以上就是哭泣嚓茶最近收集整理的关于数据结构（C语言）-线性表之队列（顺序队列、链式队列）-学习笔记041. 基本介绍2. 顺序队列3. 链式队列的全部内容，更多相关数据结构（C语言）-线性表之队列（顺序队列、链式队列）-学习笔记041.内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
点赞(96)

相关文章

【数据结构初学笔记04】队列的存储实现
【数据结构初学笔记04】队列的存储实现
C/C++队列的链式实现
C/C++队列的链式实现
队列的基本描述，及c和c++分别顺序队列和链式队列实现，利用队列处理农夫过河问题
队列的基本描述，及c和c++分别顺序队列和链式队列实现，利用队列处理农夫过河问题
队列的数组实现和链式实现
队列的数组实现和链式实现
数据结构（C语言）-线性表之队列（顺序队列、链式队列）-学习笔记041. 基本介绍2. 顺序队列3. 链式队列
数据结构（C语言）-线性表之队列（顺序队列、链式队列）-学习笔记041. 基本介绍2. 顺序队列3. 链式队列
链队列的实现
链队列的实现
【数据结构复习04】队列的链式存储实现以及基本操作
【数据结构复习04】队列的链式存储实现以及基本操作
java语言实现链队列一、实现过程二、测试顺序队列的相应方法三、总结
java语言实现链队列一、实现过程二、测试顺序队列的相应方法三、总结

评论列表共有 0 条评论

立即
投稿
返回
顶部