AI 助理
备案控制台
开发者社区 开发与运维 文章 正文

【数据结构】C语言实现链队列(附完整运行代码)

2024-03-30 129
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 【数据结构】C语言实现链队列(附完整运行代码)

一.了解项目功能

在本次项目中我们的目标是实现一个链队列:

该链队列使用动态内存分配空间,可以用来存储任意数量的同类型数据.

队列结点(QNode)需要包含两个要素:数据域data,指针域next.

队列结点(QNode)逻辑结构图示如下:

  提供的功能有:

  1.  队列的初始化.
  2.  队列的入队.
  3.  队列的出队.
  4.  队列的长度.
  5.  队列的判空.
  6.  队列取队头元素.
  7.  队列取队尾元素.
  8.  队列的销毁

二.项目功能演示

要编写一个链队列项目，首先要明确我们想要达到的效果是什么样，下面我将用vs2022编译器来为大家演示一下链队列程序运行时的样子：

三.逐步实现项目功能模块及其逻辑详解

通过第二部分对项目功能的介绍，我们已经对链队列的功能有了大致的了解，虽然看似需要实现的功能很多，貌似一时间不知该如何下手，但我们可以分步分模块来分析这个项目的流程，最后再将各部分进行整合，所以大家不用担心，跟着我一步一步分析吧！

！！！注意，该部分的代码只是为了详细介绍某一部分的项目实现逻辑，故可能会删减一些与该部分不相关的代码以便大家理解，需要查看或拷贝完整详细代码的朋友可以移步本文第四部分。

1.实现链队列程序菜单

菜单部分的逻辑比较简单，就是利用C语言printf函数打印出这个菜单界面即可。但要注意菜单的标序要和后续switch...case语句的分支相应,以免导致后续执行语句错乱的问题.基础问题就不过多赘述了，代码如下：

该部分功能实现代码如下: 

void QMenu()
{
  printf("**********************************\n");
  printf("******请选择要进行的操作    ******\n");
  printf("******1.链队列入队          ******\n");
  printf("******2.链队列出队          ******\n");
  printf("******3.取队首元素          ******\n");
  printf("******4.取队尾元素          ******\n");
  printf("******5.队列判空            ******\n");
  printf("******6.查询当前队列长      ******\n");
  printf("******7.清空队列            ******\n");
  printf("******0.退出链队列程序      ******\n");
  printf("**********************************\n");
  printf("请选择:>");
 
}

2.实现链程序功能可循环使用

由于我们要实现  的功能可以反复使用的逻辑，且至少在一开始执行一次,因此我们选择do...while的循环语句来实现这一部分的逻辑.

该部分功能实现代码如下:

 int main()
    {
        Que Q;//创建队头尾指针结构体
        QueueInit(&Q);//初始化
 
        int swi = 0;//创建变量swi作为do...while循环的终止条件,以及switch语句的运行条件
        do          //使用do...while实现
        {
 
            QMenu();
            scanf("%d", &swi);
 
            switch (swi)
            {
            case 0:
                // 释放队列内存
                QueueDestroy(&Q);
            
                printf("您已退出程序:>\n");
 
                break;
 
            case 1:
                printf("请输入要入队的数据:>");
                QDatatype pushback_data = 0;
                scanf("%d", &pushback_data);
 
                QueuePush(&Q, pushback_data);
 
                printf("已成功入队:>\n");
                break;
 
            case 2:
                QueuePop(&Q);
                printf("出队成功:>\n");
 
                break;
 
            case 3:
                printf("队首元素为:");
                QDatatype e = QueueFront(&Q);
                printf("%d\n", e);
                break;
 
            case 4:
                printf("队尾元素为:");
                QDatatype n = QueueBack(&Q);
                printf("%d\n", n);
               
                break;
 
            case 5:
                if (!QueueEmpty(&Q))
                {
                    printf("当前队列不为空:>\n");
                }
                else
                {
                    printf("当前队列为空\n");
                }
                break;
 
            case 6:
               printf("当前队列长度为:");
               int size= QueueSize(&Q);
               printf("%d\n", size);
                break;
 
            case 7:
                QueueDestroy(&Q);
                QueueInit(&Q);
                printf("队列已清空:>\n");
                break;
 
            default:
                printf("输入错误,请重新输入\n");
                break;
            }
        } while (swi);
 
        return 0;
    }

3.创建链队列

创建链队列结点的结构体应该包括:存储数据的数据域data,以及存储下一个结点地址的指针域next.

图示如下:

因此我们创建QNode结构体类型时应由一个数据成员类型及一个指向该结构体的结构体指针组成.

然后队列特殊与单链表的点出现了:队列额外需要一个指向队头的队头指针,以及一个指向队尾的队尾指针,以及一个记录队长的整型size.

为了避免设计函数时要传好几个参数的情况,我们将这三个变量额外封装一个结构体,这样只要给函数传结构体变量就可以在函数内部访问这三个变量了.

如果有朋友对队列的两个结构体还搞不太清楚,可以这样理解:Queue结构体中的head指针相当于链表中的头指针,它的使用方式和链表中的头指针完全相同.然后在此基础上,只是多一个tail指针记录尾,多一个整型记录队列长度.

综上,该部分代码如下:

#pragma once
#define _CRT_SECURE_NO_WARNINGS 1
 
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
 
typedef int QDatatype;
 
typedef struct QueueNode//一个是结点结构
{
  struct QueueNode* next;
  QDatatype data;
}QNode;
 
 
typedef struct Queue//一个是队列整体结构
{
  QNode* head;
  QNode* tail;
  int size ;
}Que;

4.链队列的初始化.

回忆我们在链表部分对链表的初始化仅仅是将头指针置为NULL.而到了链队列这里,我们还多出两个需要处理的变量,一个是尾指针tail,一个是链队列长度size.

因此我们封装一个初始化函数将这3个变量一起初始化.

链队列结构初始化部分代码逻辑图示如下:

综上,该部分代码如下:

void QueueInit(Que* pq)
{
  assert(pq);
 
  pq->head = pq->tail = NULL;
  pq->size = 0;
 
}

5.链队列的入队.

链队列在入队时思路如下:

  • 开辟新结点
  • 判断队列是否为空队列
  • 为空则将新结点"头插"进队列
  • 不为空则将新结点"尾插"进队列

综上,该部分代码如下:

void QueuePush(Que* pq, QDatatype x) //入队是尾插
{
    //创建新结点
  QNode* newnode = (QNode*)malloc(sizeof(QNode));
  if (newnode == NULL)
  {
    perror("malloc fail");
    return;
  }
    //新结点赋值
  newnode->data = x;
  newnode->next = NULL;
    
    //当队列为空时,入队相当于头插
  if (pq->head == NULL)
  {
    assert(pq->tail == NULL);
        //head为空,tail不为空就出事了,即队头为空但是队尾不为空
    //将head和tail一起指向newnode
    pq->head = pq->tail = newnode;
    
  }
  else//否则就是尾插
  {
        //尾插直接将新结点链接在原来的队尾后面
    pq->tail->next = newnode;
        //然后更新队尾
    pq->tail = newnode;
  }
    
    //新结点插入成功后队列长度要+1
  pq->size++;
 
}

6.链队列的出队.

链队列在出队思路如下:

  • 判断队列是否为空队列
  • 如果是,抛出异常终止程序
  • 如果不是,则判断队列中是否仅剩一个结点
  • 如果只剩一个结点,释放该结点,然后将head和tail置为空
  • 如果不是只剩一个结点,那么使用一个指针记录下当前队头的下一个结点的位置
  • 释放当前队头结点,然后更新队头指针
  • 最后队列长度-1

综上,该部分代码如下:

void QueuePop(Que* pq)//出队是头删,删前先判空
{
  assert(pq);
  assert(!QueueEmpty(pq));//assert为假会终止程序
 
  QNode* cur = pq;
 
  if (pq->head->next == NULL)
  {
    free(pq->head);
    pq->head = pq->tail = NULL;
  }
  else
  {
    QNode* next = pq->head->next;
    free(pq->head);
    pq->head = next;
  }
 
  pq->size--;
 
}

7.链队列的长度.

求链队列的长度,因为我们有设计记录链队列长度的变量size,因此我们直接返回结构体中的size成员的值即可.

int QueueSize(Que* pq)
{
  assert(pq);
 
  return pq->size;
 
}

8.链队列的判空.

判断队列是否为空,我们可以返回(pq->size==0)表达式的值:

  • 如果队列为空,则size=0,则pq->size==0表达式为真,函数返回true.
  • 如果队列不为空,则size不等于0,则pq->size==0表达式为假,函数返回false.

综上,该部分代码如下: 

bool QueueEmpty(Que* pq)//判空!为空返回真!
{
  assert(pq);
 
  return pq->size==0;
}

9.链队列取队头元素.

取队头元素思路:

  • 判断队列是否为空
  • 为空抛出异常
  • 不为空返回队头指针指向的头节点的数据域

综上,该部分代码如下: 

QDatatype QueueFront(Que* pq)
{
  assert(pq);
  assert(!QueueEmpty(pq));
 
  return pq->head->data;
 
}

10.链队列取队尾元素.

取队尾元素思路:

  • 判断队列是否为空
  • 为空抛出异常
  • 不为空返回队尾指针指向的尾节点的数据域

综上,该部分代码如下:

QDatatype QueueBack(Que* pq)
{
  assert(pq);
  assert(!QueueEmpty(pq));
 
  return pq->tail->data;
 
}

11.链队列的销毁

链队列的销毁思路:

  • 从头遍历队列的元素,逐一释放链队列中的结点
  • 释放完将队头指针和队尾指针置为NULL,将队列长度size置为0.

综上,该部分代码如下:

void QueueDestroy(Que* pq)
{
  assert(pq);
 
  QNode* cur = pq->head;
  while (cur)
  {
    QNode* next = cur->next;
    free(cur);
    cur = next;
  }
  pq->head = pq->tail = NULL;
  pq->size = 0;
 
}

四.项目完整代码

我们将程序运行的代码分别在三个工程文件中编辑,完整代码如下:

test.c文件

#include"Queue.h"
  //因为链队列头指针是必须的
  //而在队尾插入则尾指针同样也是必须的
  //因此我们不妨设置两个指针,一个记录队头,一个记录队尾
  //为方便起见,多个数据我们把头指针和尾指针再封装一个结构体
 
  //单链表不设置尾指针的原因是它不能解决尾删问题
 
    int main()
    {
        Que Q;//初始化
        QueueInit(&Q);
 
        int swi = 0;//创建变量swi作为do...while循环的终止条件,以及switch语句的运行条件
        do          //使用do...while实现
        {
 
            QMenu();
            scanf("%d", &swi);
 
            switch (swi)
            {
            case 0:
                // 释放队列内存
                QueueDestroy(&Q);
            
                printf("您已退出程序:>\n");
 
                break;
 
            case 1:
                printf("请输入要入队的数据:>");
                QDatatype pushback_data = 0;
                scanf("%d", &pushback_data);
 
                QueuePush(&Q, pushback_data);
 
                printf("已成功入队:>\n");
                break;
 
            case 2:
                QueuePop(&Q);
                printf("出队成功:>\n");
 
                break;
 
            case 3:
                printf("队首元素为:");
                QDatatype e = QueueFront(&Q);
                printf("%d\n", e);
                break;
 
            case 4:
                printf("队尾元素为:");
                QDatatype n = QueueBack(&Q);
                printf("%d\n", n);
               
                break;
 
            case 5:
                if (!QueueEmpty(&Q))
                {
                    printf("当前队列不为空:>\n");
                }
                else
                {
                    printf("当前队列为空\n");
                }
                break;
 
            case 6:
               printf("当前队列长度为:");
               int size= QueueSize(&Q);
               printf("%d\n", size);
                break;
 
            case 7:
                QueueDestroy(&Q);
                QueueInit(&Q);
                printf("队列已清空:>\n");
                break;
 
            default:
                printf("输入错误,请重新输入\n");
                break;
            }
        } while (swi);
 
        return 0;
    }

Queue.c 文件

#include"Queue.h"
 
void QueueInit(Que* pq)
{
  assert(pq);
 
  pq->head = pq->tail = NULL;
  pq->size = 0;
 
}
void QueueDestroy(Que* pq)
{
  assert(pq);
 
  QNode* cur = pq->head;
  while (cur)
  {
    QNode* next = cur->next;
    free(cur);
    cur = next;
  }
  pq->head = pq->tail = NULL;
  pq->size = 0;
 
}
 
void QueuePush(Que* pq, QDatatype x) //入队是尾插
{
  QNode* newnode = (QNode*)malloc(sizeof(QNode));
  if (newnode == NULL)
  {
    perror("malloc fail");
    return;
  }
  newnode->data = x;
  newnode->next = NULL;
 
  if (pq->head == NULL)//头插
  {
    assert(pq->tail == NULL);//head为空,tail不为空就出事了,队头为空但是队尾不为空
    
    pq->head = pq->tail = newnode;
    
  }
  else//尾插
  {
    pq->tail->next = newnode;
    pq->tail = newnode;
  }
 
  pq->size++;
 
}
 
 
void QueuePop(Que* pq)//出队是头删
{
  assert(pq);
  assert(pq->head!=NULL);//***
 
  QNode* cur = pq;
 
  if (pq->head->next == NULL)
  {
    free(pq->head);
    pq->head = pq->tail = NULL;
  }
  else
  {
    QNode* next = pq->head->next;
    free(pq->head);
    pq->head = next;
  }
 
  pq->size--;
 
}
 
int QueueSize(Que* pq)
{
  assert(pq);
 
  return pq->size;
 
}
 
bool QueueEmpty(Que* pq)//判空!为空返回真!
{
  assert(pq);
 
  return pq->size==0;
}
 
QDatatype QueueFront(Que* pq)
{
  assert(pq);
  assert(!QueueEmpty(pq));
 
  return pq->head->data;
 
}
QDatatype QueueBack(Que* pq)
{
  assert(pq);
  assert(!QueueEmpty(pq));
 
  return pq->tail->data;
 
}
 
void QMenu()
{
  printf("**********************************\n");
  printf("******请选择要进行的操作    ******\n");
  printf("******1.链队列入队          ******\n");
  printf("******2.链队列出队          ******\n");
  printf("******3.取队首元素          ******\n");
  printf("******4.取队尾元素          ******\n");
  printf("******5.队列判空            ******\n");
  printf("******6.查询当前队列长      ******\n");
  printf("******7.清空队列            ******\n");
  printf("******0.退出链队列程序      ******\n");
  printf("**********************************\n");
  printf("请选择:>");
 
}

Queue.h文件

#pragma once
#define _CRT_SECURE_NO_WARNINGS 1
 
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
 
typedef int QDatatype;
 
typedef struct QueueNode//一个是结点结构
{
  struct QueueNode* next;
  QDatatype data;
}QNode;
 
 
typedef struct Queue//一个是队列整体结构
{
  QNode* head;
  QNode* tail;
  int size ;
}Que;
 
void QueueInit(Que* pq);
void QueueDestroy(Que* pq);
 
void QueuePush(Que* pq,QDatatype x);
void QueuePop(Que* pq);
 
int QueueSize(Que* pq);
 
bool QueueEmpty(Que* pq);
 
QDatatype QueueFront(Que* pq);
QDatatype QueueBack(Que* pq);
 
void QMenu();

结语

希望这篇链队列的实现详解能对大家有所帮助,欢迎大佬们留言或私信与我交流.


学海漫浩浩,我亦苦作舟!关注我,大家一起学习,一起进步!

数据结构栈与队列篇思维导图:


文章标签：
C语言
存储
编译器
关键词：
数据结构c语言
C语言数据结构
数据结构代码
C语言代码
数据结构C语言代码
修修修也
目录
相关文章
ephemerals__
|
15天前
|
C语言
【数据结构】栈和队列（c语言实现）（附源码）
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表，遵循“先进后出”原则；队列则在一端插入、另一端删除，遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现，并提供了完整的代码示例。栈和队列在实际应用中非常广泛，如二叉树的层序遍历和快速排序的非递归实现等。
ephemerals__
90 9
ephemerals__
|
14天前
|
存储 搜索推荐 算法
【数据结构】树型结构详解 + 堆的实现（c语言）（附源码）
本文介绍了树和二叉树的基本概念及结构，重点讲解了堆这一重要的数据结构。堆是一种特殊的完全二叉树，常用于实现优先队列和高效的排序算法（如堆排序）。文章详细描述了堆的性质、存储方式及其实现方法，包括插入、删除和取堆顶数据等操作的具体实现。通过这些内容，读者可以全面了解堆的原理和应用。
ephemerals__
57 16
ephemerals__
|
14天前
|
C语言
【数据结构】二叉树（c语言）（附源码）
本文介绍了如何使用链式结构实现二叉树的基本功能，包括前序、中序、后序和层序遍历，统计节点个数和树的高度，查找节点，判断是否为完全二叉树，以及销毁二叉树。通过手动创建一棵二叉树，详细讲解了每个功能的实现方法和代码示例，帮助读者深入理解递归和数据结构的应用。
ephemerals__
63 8
ephemerals__
|
16天前
|
存储 C语言
【数据结构】手把手教你单链表（c语言）（附源码）
本文介绍了单链表的基本概念、结构定义及其实现方法。单链表是一种内存地址不连续但逻辑顺序连续的数据结构，每个节点包含数据域和指针域。文章详细讲解了单链表的常见操作，如头插、尾插、头删、尾删、查找、指定位置插入和删除等，并提供了完整的C语言代码示例。通过学习单链表，可以更好地理解数据结构的底层逻辑，提高编程能力。
ephemerals__
44 4
ephemerals__
|
16天前
|
C语言
【数据结构】双向带头循环链表（c语言）（附源码）
本文介绍了双向带头循环链表的概念和实现。双向带头循环链表具有三个关键点：双向、带头和循环。与单链表相比，它的头插、尾插、头删、尾删等操作的时间复杂度均为O(1)，提高了运行效率。文章详细讲解了链表的结构定义、方法声明和实现，包括创建新节点、初始化、打印、判断是否为空、插入和删除节点等操作。最后提供了完整的代码示例。
ephemerals__
37 0
這～悸ベ雨落憂殇
|
存储 缓存 C语言
数据结构——双链表（C语言）
数据结构——双链表（C语言）
這～悸ベ雨落憂殇
46 0
7fa6b5ui5pmtk
|
5月前
|
存储
数据结构——双向链表（C语言版）
数据结构——双向链表（C语言版）
7fa6b5ui5pmtk
31 2
7fa6b5ui5pmtk
|
5月前
|
算法 C语言
数据结构——单向链表（C语言版）
数据结构——单向链表（C语言版）
7fa6b5ui5pmtk
45 2
Darknesscor
|
测试技术 C语言
数据结构单链表的实现（C语言）
数据结构单链表的实现（C语言）
Darknesscor
26 0
ForcibleBugMaker
|
6月前
|
存储 缓存 程序员
初阶数据结构之---顺序表和链表（C语言）
初阶数据结构之---顺序表和链表（C语言）
ForcibleBugMaker
86 1

热门文章

最新文章

  • 1
    C语言中的逗号操作符
  • 2
    《C语言及程序设计》实践参考——改造链表
  • 3
    C语言连接MySQL数据库
  • 4
    C语言中用于计算数组长度的函数 “strlen（） ”。
  • 5
    C语言预处理之二-----宏定义那点事儿
  • 6
    《C语言程序设计进阶教程》一第3章 预防、检测及消除bug
  • 7
    《C语言及程序设计》实践项目——数据的输入
  • 8
    C语言库函数大全及应用实例十
  • 9
    C语言中大小写字母的转化
  • 10
    【C语言进阶】字符串函数与内存函数的学习与模拟实现（上）
  • 1
    `geopandas`是一个开源项目，它为Python提供了地理空间数据处理的能力。它基于`pandas`库，并扩展了其对地理空间数据（如点、线、多边形等）的支持。`GeoDataFrame`是`geopandas`中的核心数据结构，它类似于`pandas`的`DataFrame`，但包含了一个额外的地理列（通常是`geometry`列），用于存储地理空间数据。
    69
  • 2
    “解锁Python高级数据结构新姿势：图的表示与遍历，让你的算法思维跃升新高度
    40
  • 3
    Redis数据结构—跳跃表 skiplist 实现源码分析
    64
  • 4
    逆袭之路！用 Python 玩转图的 DFS 与 BFS，让数据结构难题无处遁形
    65
  • 5
    Python中的列表（List）和元组（Tuple）是两种重要的数据结构
    53
  • 6
    【数据结构OJ题】链表分割
    32
  • 7
    【数据结构常见七大排序（三）上】—交换排序篇【冒泡排序】And【快速排序】
    45
  • 8
    【数据结构常见七大排序（二）】—选择排序篇【直接选择排序】And【堆排序】
    33
  • 9
    【数据结构常见七大排序（一）】—插入排序篇【直接插入排序】And【希尔排序】
    45
  • 10
    【数据结构OJ题】链表的回文结构
    39

    • 相关课程

    更多
  • Go语言核心编程 - 数据结构和算法
  • 你的第一门C语言课
  • C语言学习教程
  • Go语言核心编程 - 基础语法、数组、切片、Map

    • 相关电子书

    更多
  • 如何使用Tair增强数据结构构建丰富在线实时场景
  • Apache Flink 流式应用中状态的数据结构定义升级
  • 低代码开发师（初级）实战教程
    • 下一篇
    阿里云OSS设置跨域访问