当前位置: 首页 > news >正文

队列的链式存储结构及其基本运算实现

前面我们介绍了顺序队列的存储 ,是利用数组存储数据 , 然后删除节点数据和添加节点数据都是在数组完成的 , 有一个弊端就是 ,当我们操作的数量很大时  , 如果数组存储结构就很难队列操作了 ,那就需要利用链式存储结构了 

●链队组成:
    (1) 存储队列元素的单链表
    (2) 指向队头和队尾的链队头结点


d6361e51b3e54a269c7e6528e2234c32.jpeg


●存储结构的定义
       数据节点的定义

typedef struct qnode
{
    ElemType data;
    struct qnode*next;
}QNode;

数据节点就是我们的链队节点,包含数据区和后继指针区


      •链队节点

typedef struct
{
    QNode *front;
    QNode *rear;
}LiQueue;

链队节点就是管理队列的指针 , front 指向单链表的头结点 , rear 指向单链表的尾结点

链队 4 要素

(1)队空条件:   front = rear = NULL


7b2b19240fe34f5d87d4c1dee3ddd595.jpeg

 初始链队内无元素 , 所以指向 NULL

(2)队满条件 : 不考虑


因为存储数据的是链表 , 所以存储容量是灵活的

(3) 进队操作 : 将包含新元素 e 的节点 插入到单链表表尾


4fab25b9975149eb8191d33d1cd6b142.jpeg


我们需要构造一个新节点 ,数据区包含新元素e 的数据 (进队不考虑队满,我们链表优势)

然后队尾节点的后继指针要指向新节点 ,然后我们的队尾指针rear 也要指向新节点

(4) 出队操作: 删除单链表中首个数据节点 , 并将要出队的节点数据保存传出 .


8d7694250fd14d92a59b40dbda52ceed.jpeg


考虑队空因素 , 链队内无元素 ,则无法出队操作

要删除队首指针front所指向的节点 ,首先最好把其位置存储一下,方便后续释放其空间 

然后把 front 指向删除节点的后一个节点即可(我们在覆盖或删除指针前 ,特别注意 我们以后还会不会用到这个指针 ,如果用到 ,我们最后存储或存储之后,再将其删除或覆盖)

初始化队列InitQueue(q)


●构造一个空队列 ,即只创建一个包含队首指针和队尾指针的头结点 ,front和 rear都置为空,
因为是空队列,所以没有元素,不创建元素节点


0bd2e6152fb34409858429e042270731.jpeg


//传入要创建的链队的指针地址
void InitQueue(LiQueue *&q)
{
    //链队头结点申请空间
    q = (LiQueue *)malloc(sizeof(LiQueue));
    //队首尾指针置空
    q->front = q->rear =NULL;
}

 

销毁队列DestroyQueue(q)

● 释放队列占用的存储空间 , 包括链队头结点和所有数据节点的存储空间


f1d3e5174d1148d6ba5f8215623b9d01.jpeg


我们释放链表,当然不会像释放顺序队一样 ,直接把一个数组释放就可以了,因为我们链队的每一个节点都是一个独立的节点 , 他们通过指针指引链接 ,我们需要逐个释放 数据节点 

注意: 当我们释放第一个节点 a1 的时候 ,因为 a1的后继指针存储着后续节点的位置信息 ,所以我们不能直接释放 ,我们需要再定义一个数据节点 r 来存储删除的节点的后继指针 ,从而保证我们能够顺利的找到下一个要删除释放的节点


//传入要释放删除的链队
void DestroyQueue(LiQueue *&q)
{
	//定义指向要删除的节点的变量和 保存后续节点指针的变量
	//初始要删除的节点是链队第一个元素 ,就是链队头节点q的后一个节点
	//为什么第一个不删除 链队头结点呢?因为头结点q 和数据节点的类型不一样,我们后续单独删除释放即可
	QNode *p = q->front;
	QNode *r;
	//先判断链队是否为空,为空无需删除数据节点 ,直接释链队头结点q即可
	if(p!=NULL)
	{
		//初始要删除第一个节点,然后r保存第二个节点的位置, 位置信息存储在p->next;
		r=p->next;
		while(r!=NULL)
		{
			//当我们要删除的节点后无节点
			free(p);
			//释放完p 之后,我们接着释放后一个节点,r赋值给p
			p = r;
			// r向后移动,存储 p 后面的节点
			r = p->next;
		}
	}
	free(p);
	free(q);
}

当我们释放完  倒数第二个数据节点 p 时 , p指向最后一个节点 , r指向空,则跳出了循环, 我们链表最后一个节点未释放 ,我们此时再在循环外释放最后一个链表节点 ,链队头结点q

● 判断队列是否为空 QueueEmpty(q)


    •若链队节点的rear域值为NULL , 表示队列为空,返回true;否则返回flase.
 

e22a197e58b34781bb1ee840525f727a.jpeg


//传入要判断为空的队列
bool QueueEmpty(LiQueue *q)
{
    return(q->rear==NULL);
}

●入队enQueue(q,e)


操作:
    •创建data域为e的数据节点 *p
    •若原队列为空,则将链队节点的两个域均为指向*p节点,否则将*p链到单链表的末尾,
    并让链队节点的rear域指向它


2dfc8d1ec5a34da99a784a3e8db7e6b4.jpeg


//传入要入队的队列,和入队的新元素
void enQueue(LiQueue *&q,ElemType e)
{
    //为新元素创建链表节点
    QNode *p;
    p = (QNode *)malloc(sizeof(QNode));
    p->data = e;
    //因为新节点作为尾结点,所以后继指针置空
    p->next = NULL;
    //插入前,先判断队列是否为空,如果为空,则新元素作为唯一一个节点,
    //队首指针和队尾指针都指向这个节点
    if(q->rear == NULL)
    {
        q->front = q->rear = p;
    }
    else
    {
        //如果原队列不为空,则只用把新节点插入到链表最后一个元素后面,然后把rear指向p
        q->rear->next = p;
        q->rear = p;
    }

}


●出队deQueue(q,e)
  

 操作:
       •若原队列不为空则将第一个数据节点的data域值赋给e,并删除之.
       •若出队前队列中只有一个节点,则需要将链队节点的两个域均置空为NULL,表示队列已空


103f523c8ee84e4d84d42923d3cae48b.jpeg



 我们既然要出队元素,就需要考虑指针 front 和 rear ,我们只是出队一个元素,为什么要注意两个指针呢?因为有的情况,两个指针指向同一个元素,然后我们删除并出队那个元素,我们就需要改变两个指针

①首先,要出队,首先判断队列是否为空, 为空谈何出队

②当我们出队一个元素时候,两个指针都变的时候,那就是出队前,队列里只有一个数据元素,

front和rear都指向 那个元素,出完队 , 我们需要将队首和队尾指针置空

③ 就是我们队列里面不止一个元素,然后我们出队只需要动 front 即可 出完队 ,把front 指向 队列下一个元素即可


bool deQueue(LiQueue*&q,ElemType &e)
{
     QNode *t;
     if ((q->rear==NULL)
       return false;
     t=q->front;
     if (q->front==q->rear)
          q->front=q->rear=NULL;
     else
          q->front=q->front->next;
     e=t->data;
     free(t);
     return true;

}

相关文章:

  • 网站优化 推广/网络营销具有什么特点
  • 视频网站 做综艺 电视台/快速开发网站的应用程序
  • 自己怎么做返利网站/怎么自己刷推广链接
  • 泰安网站制作哪家好/湘潭网站设计外包公司
  • 平顶山网站开发/索引擎优化 seo
  • 大学生想做网站/重庆网站seo技术
  • 算法学习 【第一周】Ⅰ
  • Vue跳转页面隐藏底部导航tabbar的两种方法
  • memo,useCallback(),strapi,fetch,数据加载的提示,处理错误,await
  • Oh-My-Zsh安装与配置
  • “难产”的恒驰5,前途堪忧
  • 威胁情报分析平台
  • AtCoder Beginner Contest 272「ABCDE」
  • 基于虚拟机源码分析move合约(三):整数的位运算和强制转换
  • 【sklearn】模型融合_投票法
  • ASP.NET MVC会计教学管理端项目系列--Log4Net日志组件
  • AD域帐户密码过期,终端802.1x认证自动重连导致AD账号被锁,员工无法上网、办公怎么办?
  • iOS小技能:跳转到地图APP(navForIOSMap)