首页 > 其他分享 >数据结构-C语言描述（队列的链表实现）

数据结构-C语言描述（队列的链表实现）

时间：2024-03-31 14:29:26浏览次数：19  
标签：Node Queue eletype 队首 C语言 链表 front 数据结构 rear

概述

在日常生活中，先进先出似乎更加符合我们的日常认知。

 排队的人群中，队首的人总是先离开，而队尾的人总是后离开。

1.队列的基本原理和操作

我们知道队列也是一种线性表，而今天我们就用非顺序储存结构（链表）来实现它。

首先我们先明确队列的基本操作原理：因为同时涉及到队首和队尾的操作，所以仅用一个头指针是不好解决问题的，所以在这里我们采用双指针的方式（即分别用两个指针*front、*rear指向队首和队尾）。然后再考虑一下队列中还要有什么元素？当然是队列的长度size了。接着是节点的常规定义：

#include <stdio.h>
#include <stdlib.h>

#define eletype int

typedef struct Node {
    eletype data;
    struct Node* next;
} Node;

typedef struct Queue {
    Node *front;           //定义两个指针，*front指向队首，*rear指向队尾
    Node *rear;
    int size;    
} Queue;

2.队列的创建

队列的创建需要将先前出现的变量进行初始化：

void QueueCreat (Queue *q) {
    q->front=NULL;
    q->rear=NULL;
    q->size=0;
}

3.队列的销毁

销毁只需要从队首开始逐步将队列的空间释放掉,注意每释放一次就要将队首指针更新一次：

void QueueDestroy (Queue *q) {
    while(q->front){
        Node* temp=q->front;         
        q->front=q->front->next; //然后更新队首指针，直到循环条件中q->front==NULL
        free(temp);          //释放队首指针的空间
    }
    q->rear=NULL;
    q->size=0;
}

4.入队

入队操作需要Queue *q、eletype element作为传入的参数。而我们要做的就是将element存入一个节点的数据域， 再将该节点更新为新的队首节点：

void QueuePush (Queue *q,eletype element) {
    Node* new_Node=(Node*)malloc(sizeof(Node));
    new_Node->data=element;
    new_Node->next=NULL;             
    if(q->rear==NULL){
        q->front=q->rear=new_Node;  //判断是否为空队列，若是，队首队尾指针都指向新节点即可
    } else {
        new_Node->next=q->rear;     //若否，则将新节点链接到q->rear,并更新队尾节点
        q->rear=new_Node;
    }
    q->size++;
}

5.出队

删除元素是在队首进行的，需要将队首空间释放，且更新队首指针(注意要判断队列是否为空，并打印相关提示信息),最后将队首元素带回：

eletype QueuePop (Queue *q) {
    if(q->front==NULL){
        printf("Queue is empty!\n");
        exit(1);                          
    }
    eletype result=q->front->data;
    Node *temp=q->front;         
    q->front=q->front->next;     //更新队首指针
    free(temp);                  //定义一个*temp来接收q->front,并将其释放掉
    q->size--;
    return result;
}

6.获取队首元素

eletype QueueTop (Queue *q) {
    return q->front->data;
}

7.获取队列的长度

int QueueGetsize (Queue *q) {
    return q->size;    
}

8.完整源码

#include <stdio.h>
#include <stdlib.h>

#define eletype int

typedef struct Node {
    eletype data;
    struct Node* next;
} Node;

typedef struct {
    Node *front;       //定义两个指针，*front指向队首，*rear指向队尾
    Node *rear;
    int size;    
} Queue;

void QueueCreat (Queue *q) {
    q->front=NULL;
    q->rear=NULL;
    q->size=0;
}

void QueueDestroy (Queue *q) {
    while(q->front){
        Node* temp=q->front;
        q->front=q->front->next; //然后更新队首指针，直到循环条件中q->front==NULL
    	free(temp);              //释放队首指针的空间
	}
    q->rear=NULL;
    q->size=0;
}

void QueuePush (Queue *q,eletype element) {
    Node* new_Node=(Node*)malloc(sizeof(Node));
    new_Node->data=element;
    new_Node->next=NULL;             
    if(q->rear==NULL){
        q->front=q->rear=new_Node;  //判断是否为空队列，若是，队首队尾指针都指向新节点即可
    } else {
        q->rear->next=new_Node;     //若否，则将新节点链接到q->rear,并更新队尾节点
        q->rear=new_Node;
    }
    q->size++;
}

eletype QueuePop (Queue *q) {
    if(q->front==NULL){
        printf("Queue is empty!\n");
        exit(1);                          
    }
    eletype result=q->front->data;
    Node *temp=q->front;        
    q->front=q->front->next;   //更新队首指针
    free(temp);                //定义一个*temp来接收q->front,并将其释放掉
	q->size--;
    return result;
}

eletype QueueTop (Queue *q) {
    if(q->front==NULL){
    	printf("Queue is empty!\n");
		exit(1); 
	}
	return q->front->data;
}

int QueueGetsize (Queue *q) {
    return q->size;    
}

int main (){
	Queue q;
	QueueCreat (&q);
	QueuePush (&q,10);
	QueuePush (&q,20);
	QueuePush (&q,30);
	printf("出队元素为：%d\n",QueuePop (&q));
	printf("队首元素为：%d\n",QueueTop (&q));
	printf("队列的大小为：%d\n",QueueGetsize (&q));
}

总结

在完整源码调试的时候遇到了一个问题，其运行结果如下：

发现队首元素的输出有误！！！

后来发现问题出在释放空间的时候，

原错误代码：

eletype QueuePop (Queue *q) {
    if(q->front==NULL){
        printf("Queue is empty!\n");
        exit(1);                          
    }
    eletype result=q->front->data;
    Node *temp=q->front;        
    free(temp);                        //定义一个*temp来接收q->front,并将其释放掉
    q->front=q->front->next;   //更新队首指针
    q->size--;
    return result;
}

 修改后的正确代码：

eletype QueuePop (Queue *q) {
    if(q->front==NULL){
        printf("Queue is empty!\n");
        exit(1);                          
    }
    eletype result=q->front->data;
    Node *temp=q->front;        
    q->front=q->front->next;   //更新队首指针
    free(temp);                       //定义一个*temp来接收q->front,并将其释放掉
    q->size--;
    return result;
}

 

 很明显，将两句代码的执行顺序调换一下后（即前者是先释放空间后更新头指针。而后者是先更新头指针在释放空间），队首元素的输出就正确了。

这是什么原因呢？这个问题请帮忙大家想想看……

标签：Node,Queue,eletype,队首,C语言,链表,front,数据结构,rear
From： https://blog.csdn.net/MaverickCoder/article/details/137190697

相关文章

  • 【数据结构与算法篇】动态顺序表及相关OJ算法题
    【数据结构与算法篇】动态顺序表及相关OJ算法题......
  • 初始C语言
    自我简绍：本人双非院校大一新生，集成电路设计与集成系统专业。我认为C语言是学习其他语言的基础，可以为以后学其他语言打好基础，很有必要好好学习学习，并且网上有很多项目都是开源的，可以很好的去实际。未来编程目标：首先将C语言系统的仔细学一下，然后再学学数据结构与算法。我想......
  • 【C语言】贪吃蛇【附源码】
    欢迎来到英杰社区https://bbs.csdn.net/topics/617804998一、游戏说明：一个基于C语言链表开发的贪吃蛇游戏：1.按方向键上下左右，可以实现蛇移动方向的改变。2.短时间长按方向键上下左右其中之一，可实现蛇向该方向的短时间加速移动。3.按空格键可实现暂停，暂停后按任意键继......
  • C语言 键盘输入与屏幕输出——数据的格式化屏幕输出
    目录顺序结构C语言如何实现数据的输入和输出？数据的格式化屏幕输出printf（）格式字符printf（）的格式修饰符顺序结构一般而言，顺序结构程序涉及如下三个基本操作：*输入数据*处理数据*输出数据顺序结构的特点 *自上而下，依次按顺序执行C语言如何实现数据的输入和输出？......
  • 算法复习：链表
    链表定义structListNode{intval;ListNode*next;ListNode(intx):val(x),next(nullptr){}};链表的遍历：ListNodep=head; while(p!=null)p=p.next; 找到链表的尾结点：p=head; while(p.next!=null)p=p.next;链表节点的个数：     p=head......
  • 数据结构之结构体进阶——pair
    前言：当结构体中只有两个元素时，去定义结构体时太过于繁琐了，在C++中有特定的函数可以简化这种结构体的定义。 pair的定义：有两个元素的结构体，其中为first，second元素，其中first，second的类型可以自己定义。 pair的创建：文字解释：官方给予的定义：template<classT1,class......
  • C语言实现半定规划（Semidefinite Programming, SDP）算法
    目录前言A.建议B.简介一代码实现A.半定规划的基本概念B.使用C语言进行半定规划建模二时空复杂度A.时间复杂度B.空间复杂度C.实际考虑三优缺点A.优点B.缺点C.总结四现实中的应用前言A.建议1.学习算法最重要的是理解算法的每一步，而不是记住算法。2.......
  • C语言实现随机游走算法（Random Walks）
    目录前言A.建议B.简介一代码实现二时空复杂度A.时间复杂度：B.空间复杂度：C.总结：三优缺点A.优点：B.缺点：C.总结：四现实中的应用前言A.建议1.学习算法最重要的是理解算法的每一步，而不是记住算法。2.建议读者学习算法的时候，自己手动一步一步地运行算法。B.......
  • C语言入门：数组与指针的关系
    目录深入理解指针操作指针的基本概念指针与数组的关系指针与函数动态内存分配与释放内存分配函数内存释放函数动态内存管理注意事项深入理解指针操作、动态内存分配与释放是C语言编程中的核心技能。以下内容将进一步详细阐述这些主题，旨在帮助开发者更好地掌握指针......
  • 00342第四章 结构化程序设计 思考题和练习题（C语言）
    一、单项选择题1.若从键盘输入字符串"HOWAREYOU?"，可以直接使用库函数【】。        A.scanf    B.getstr    C.gets    D.都不能直接使用2.C语言的库函数中，可以输出double型变量值的是【】。        A.getchar   ......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99