学做ppt的网站,两性做受技巧视频网站,做网站简介,怎么买做淘宝优惠券网站数据结构——队列 一、队列的概念二、队列的实现方式三、队列所需要的接口四、接口的详细实现4.1初始化4.2销毁4.3入队4.5出队4.6获取队头元素4.7获取队尾元素4.8获取队列元素个数4.9判空 五、完整代码5.1Queue.h5.2Queue.c5.3test.c 一、队列的概念
队列#xff1a;只允许在… 数据结构——队列 一、队列的概念二、队列的实现方式三、队列所需要的接口四、接口的详细实现4.1初始化4.2销毁4.3入队4.5出队4.6获取队头元素4.7获取队尾元素4.8获取队列元素个数4.9判空 五、完整代码5.1Queue.h5.2Queue.c5.3test.c 一、队列的概念
队列只允许在一端进行插入数据操作在另一端进行删除数据操作的特殊线性表
队列具有先进先出FIFO(First In First Out)
入队列进行插入操作的一端称为队尾 。
出队列进行删除操作的一端称为队头。二、队列的实现方式
队列可以用数组和链表的结构实现使用链表的结构实现更优一些因为如果使用数组的结构出队列在数组头上出数据效率会比较低。
三、队列所需要的接口
//初始化
void QueueInit(Queue* pq);//销毁
void QueueDestory(Queue* pq);//入队
void QueuePush(Queue* pq, Queuedatatype x);//出队
void QueuePop(Queue* pq);//获取队头元素
Queuedatatype QueueFront(Queue* pq);//获取队尾元素
Queuedatatype QueueBack(Queue* pq);//获取队列元素个数
int Queuesize(Queue* pq);//判空
bool QueueEmpty(Queue* pq);四、接口的详细实现
4.1初始化
初始化我们需要将pq-phead和pq-ptail都置为NULL并且将pq-size置为0
oid QueueInit(Queue* pq)
{assert(pq);pq-phead NULL;pq-ptail NULL;pq-size 0;
}4.2销毁
销毁首先定义一个cur指针保存头节点phead的地址接下来利用cur!NULL使得循环往下走在循环内定义一个next的指针来更新地址并且用free来释放内存出循环后将pq-phead,pq-ptail都置为NULL,并且将pq-size置为0。
void QueueDestory(Queue* pq)
{assert(pq);Queuenode* cur pq-phead;while (cur){Queue* next cur-next;free(cur);cur next;}pq-phead pq-ptail NULL;pq-size 0;
}4.3入队
入队入队有两种情况。第一种队内无其他元素第二种队内有其他元素。 ①、队内无其他元素直接让pq-phead pq-ptail newnode; ②、队内有其它元素如果队列不为NULL,我们需要让pq-ptail-next指向newnode,并且最后再让pq-ptail指向newnode.
oid QueuePush(Queue* pq, Queuedatatype x)
{assert(pq);Queuenode* newnode (Queuenode*)malloc(sizeof(Queuenode));if (newnode NULL){perror(malloc fail);return;}newnode-data x;newnode-next NULL;//队内无其它元素if (pq-phead NULL){assert(pq-ptail NULL);pq-phead pq-ptail newnode;}else{//链接pq-ptail-next newnode;pq-ptail newnode;}pq-size;
}
4.5出队
出队出队列大体上分为两种情况有节点和无节点。 ①、如果队列中没有节点就不能进行出队操作我们这时可以用assert(!QueueEmpty(pq)); 来进行判断。 ②、队列中有节点时又可以分为一个节点和多个节点之分如果队列中只有一个节点时我们直接用free 置空如果队列中有多个节点时首先、创建一个next用来保存phead的下一个节点的地址我们free(phead)再让phead等于我们的next。
// 出队
void QueuePop(Queue * pq)
{assert(pq);assert(!QueueEmpty(pq));//一个节点if (pq-phead-next NULL){free(pq-phead);pq-phead pq-ptailNULL;}//多个节点else{//头删Queuenode* next pq-phead-next;free(pq-phead);pq-phead next;}pq-size--;
}4.6获取队头元素
//获取队头元素
Queuedatatype QueueFront(Queue* pq)
{assert(pq);return pq-phead-data;
}4.7获取队尾元素
//获取队尾元素
Queuedatatype QueueBack(Queue* pq)
{assert(pq);return pq-ptail-data;
}4.8获取队列元素个数
//获取队列元素个数
int Queuesize(Queue* pq)
{assert(pq);return pq-size;
}4.9判空
如果pq-size0时便证明队列为NULL。
//判空
bool QueueEmpty(Queue* pq)
{assert(pq);return pq-size 0;
}五、完整代码
5.1Queue.h
#pragma once
#includestdio.h
#includeassert.h
#includestdlib.h
#includestdbool.htypedef int Queuedatatype;
//定义队列结构
typedef struct Queuenode
{struct Queuenode* next;Queuedatatype data;
}Queuenode;typedef struct Queue
{Queuenode* phead;Queuenode* ptail;int size;
}Queue;//初始化
void QueueInit(Queue* pq);//销毁
void QueueDestory(Queue* pq);//入队
void QueuePush(Queue* pq, Queuedatatype x);//出队
void QueuePop(Queue* pq);//获取队头元素
Queuedatatype QueueFront(Queue* pq);//获取队尾元素
Queuedatatype QueueBack(Queue* pq);//获取队列元素个数
int Queuesize(Queue* pq);//判空
bool QueueEmpty(Queue* pq);5.2Queue.c
#define _CRT_SECURE_NO_WARNINGS 1
#includeQueue.h
//初始化
void QueueInit(Queue* pq)
{assert(pq);pq-phead NULL;pq-ptail NULL;pq-size 0;
}//销毁
void QueueDestory(Queue* pq)
{assert(pq);Queuenode* cur pq-phead;while (cur){Queue* next cur-next;free(cur);cur next;}pq-phead pq-ptail NULL;pq-size 0;
}//入队
void QueuePush(Queue* pq, Queuedatatype x)
{assert(pq);Queuenode* newnode (Queuenode*)malloc(sizeof(Queuenode));if (newnode NULL){perror(malloc fail);return;}newnode-data x;newnode-next NULL;if (pq-phead NULL){assert(pq-ptail NULL);pq-phead pq-ptail newnode;}//链接pq-ptail-next newnode;pq-ptail newnode;pq-size;
}// 出队
void QueuePop(Queue * pq)
{assert(pq);assert(!QueueEmpty(pq));//一个节点if (pq-phead-next NULL){free(pq-phead);pq-phead pq-ptailNULL;}//多个节点else{//头删Queuenode* next pq-phead-next;free(pq-phead);pq-phead next;}pq-size--;
}//获取队头元素
Queuedatatype QueueFront(Queue* pq)
{assert(pq);return pq-phead-data;
}//获取队尾元素
Queuedatatype QueueBack(Queue* pq)
{assert(pq);return pq-ptail-data;
}//获取队列元素个数
int Queuesize(Queue* pq)
{assert(pq);return pq-size;
}//判空
bool QueueEmpty(Queue* pq)
{assert(pq);return pq-size 0;
}5.3test.c
#define _CRT_SECURE_NO_WARNINGS 1
#includeQueue.h
void test1()
{Queue q;QueueInit(q);QueuePush(q, 1);QueuePush(q, 2);QueuePush(q, 3);QueuePush(q, 4);printf(Size:%d\n, Queuesize(q));while (!QueueEmpty(q)){printf(%d , QueueFront(q));QueuePop(q);}}
int main()
{test1();return 0;
}
