做泌尿科网站价格,wordpress 文章 标题,伊春seo,论坛推广案例在数据结构之《栈》章节中学习了线性表中除了顺序表和链表外的另一种结构——栈#xff0c;在本篇中我们将继续学习另一种线性表的结构——队列#xff0c;在通过本篇的学习后#xff0c;你将会对栈的结构有充足的了解#xff0c;在了解完结构后我们还将进行栈的实现。一起…在数据结构之《栈》章节中学习了线性表中除了顺序表和链表外的另一种结构——栈在本篇中我们将继续学习另一种线性表的结构——队列在通过本篇的学习后你将会对栈的结构有充足的了解在了解完结构后我们还将进行栈的实现。一起加油吧 1.队列的结构与定义
概念只允许在一端进行插入数据操作在另⼀端进行删除数据操作的特殊线性表队列具有先进先出FIFO(First In First Out)
入队列进行插入操作的一端称为队尾 出队列进行删除操作的一端称为队头 那么在队列的底层结构应该选择的是数组还是链表呢接下来就来分析看看 在使用数组作为队列的底层结构时由于队列的性质要求先进先出所以可以使用size来表示数组内的有效元素个数这样在入队列时就可以直接在数组的size位置插入数据但是在出队列时为了将数组内的首个元素也就是数组下标为0的位置移除这就需要将数组从下标为1的位置开始整体都向前移动一位所以在出队列的时间复杂度为O(N) 在使用单链表作为队列的底层结构时由于队列的性质要求先进先出所以如果只用一个phead指针指向链表的第一个节点那么就会使得在入队列时要找到链表的尾节点就需要通过遍历链表才能实现这就会使得时间复杂度为O(N),所以为了解决以上这种缺陷就在创建一个指针指向链表的尾节点在入队列是就可以直接找到尾节点这样就可以使得无论是入队列还是出队列时间复杂度都为O(1) 通过以上的分析就可以得出在实现队列时底层结构选择单链表是最优解 2.队列的实现
在实现队列的代码中在Queue.h头文件中定义队列的结构以及队列中各个函数的声明在Queue.c文件内完成各个函数的定义在test.c文件内对实现的各个函数进行测试
2.1队列结构的定义
在队列结构的定义中创建一个结构体QueueNode来表示节点该节点内部有两个成员变量data来存放节点的数据next指针来存放下一个节点的地址之后还需再创建一个结构体Queue来存放指向链表的第一个节点和尾节点的指针并且在这个结构体内还创建一个成员变量size来表示链表中节点的个数这样是为了在之后的计算队列有效数据个数时直接将size的值提取出来就可实现了
//队列结构的定义
typedef int QDataType;
typedef struct QueueNode
{QDataType data;//节点内的数据struct QueueNode* next;//指向下一个节点的指针}QueueNode;typedef struct Queue
{struct QueueNode* phead;//指向第一个节点的指针struct QueueNode* ptail;//指向尾节点的指针int size;//节点的个数}Queue; 2.2队列的初始化
要完成队列的初始化函数首先要在Queue.h内完成函数的声明
//初始化队列
void QueueInit(Queue* pq);
将该函数命名为QueueInit函数的参数为存放指向头尾节点指针的结构体指针
完成了函数的声明接下来就是在Queue.c函数内完成函数的定义 因为以下函数中的pq指针是存放指向头尾节点指针的结构体指针该指针不能为空因此要将pq进行assert断言 //初始化队列
void QueueInit(Queue* pq)
{assert(pq);pq-phead pq-ptail NULL;pq-size 0;
} 2.2判断队列是否为空
要完成队列判空函数首先要在Queue.h内完成函数的声明
bool QueueEmpty(Queue* pq);
将该函数命名为QueueEmpty函数的为存放指向头尾节点指针的结构体指针函数的放回类型是布尔类型当队列为空时放回true不为空就放回false
完成了函数的声明接下来就是在Queue.c函数内完成函数的定义 因为以下函数中的pq指针是存放指向头尾节点指针的结构体指针该指针不能为空因此要将pq进行assert断言 在队列为空时就是指向第一个队列的指针phead和指向队列的尾部的指针ptail都为空所以该函数的返回值就为pq-phead NULL pq-ptail NULL //队列判空
bool QueueEmpty(Queue* pq)
{assert(pq);return pq-phead NULL pq-ptail NULL;
} 2.3入队列
要完成入队列函数首先要在Queue.h内完成函数的声明
//入队列
void QueuePush(Queue* pq, QDataType x);
将该函数命名为QueuePush函数的参数有两个第一个为存放指向头尾节点指针的结构体指针,第二个为要插入的数据
完成了函数的声明接下来就是在Queue.c函数内完成函数的定义 因为以下函数中的pq指针是存放指向头尾节点指针的结构体指针该指针不能为空因此要将pq进行assert断言在实现数据的入队列前要为数据申请新的节点空间在此使用malloc来实现申请完之后在将要入队列的数据x存放到新节点newnode中之后在将新节点插入到链表时要分以下两种情况一种是phead指针指向为空时也就是这时链表内一个节点都没有这时就要将phead和ptail都newnode另外一种情况是phead指针指向不为空时这时就先使得ptail的next指针指向newnode之后再将ptail指向新节点newnode最后在完成以上操作后要将有效个数size1 //入队列
void QueuePush(Queue* pq, QDataType x)
{assert(pq);QueueNode* newnode (QueueNode*)malloc(sizeof(QueueNode));if (newnode NULL){perror(malloc fail!);exit(1);}newnode-data x;newnode-next NULL;if (pq-phead NULL){pq-phead pq-ptail newnode;}else{pq-ptail-next newnode;pq-ptail newnode;}pq-size;
} 2.4出队列
要完成出队列函数首先要在Queue.h内完成函数的声明
//出队列
void QueuePop(Queue* pq);
将该函数命名为QueuePop函数的参数为存放指向头尾节点指针的结构体指针
完成了函数的声明接下来就是在Queue.c函数内完成函数的定义 因为以下函数中的pq指针是存放指向头尾节点指针的结构体指针该指针不能为空因此要将pq进行assert断言同时在出队列时队列内不能一个节点都没有所以要判断队列内不为空因此要将!QueueEmpty进行assert断言 之后在出队列也就是删除单链表的第一个节点时分为以下两种情况第一种是指针phead和指针ptail指向同一个节点也就是链表中只有一个节点这时就直接释放该节点之后再将phead和ptail置为空另外一种情况是指针phead和指针ptail不相同这时就先创建一个新的指针变量Next指向原来的phead的next指针指向的节点之后将phead指向的节点释放后在将phead指针置为Next指向的节点 最后在完成以上操作后要将有效个数size-1 //出队列
void QueuePop(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));if (pq-phead pq-ptail){free(pq-phead);pq-phead pq-ptail NULL;}else{QueueNode* Next pq-phead-next;free(pq-phead);pq-phead Next;}pq-size--;} 2.5取队列头数据
要完成取队列头数据函数首先要在Queue.h内完成函数的声明
//取队列头数据
QDataType QueueFront(Queue* pq);
将该函数命名为QueueFront函数的参数存放指向头尾节点指针的结构体指针函数的放回值就为队列的头数据也就是单链表的第一个节点存放的数据
完成了函数的声明接下来就是在Queue.c函数内完成函数的定义 因为以下函数中的pq指针是存放指向头尾节点指针的结构体指针该指针不能为空因此要将pq进行assert断言同时在出队列时队列内不能一个节点都没有所以要判断队列内不为空因此要将!QueueEmpty进行assert断言在队列中的头数据就为phead指针指向的节点内存放的数据 因此该函数直接放回pq-phead-data即可 //取队列头数据
QDataType QueueFront(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq-phead-data;
} 2.6取队尾数据
要完成取队列尾数据函数首先要在Queue.h内完成函数的声明
//取队列尾数据
QDataType QueueBack(Queue* pq);
将该函数命名为QueueBack函数的参数为存放指向头尾节点指针的结构体指针函数的放回值就为队列的尾数据也就是单链表的最后一个节点存放的数据
完成了函数的声明接下来就是在Queue.c函数内完成函数的定义 因为以下函数中的pq指针是存放指向头尾节点指针的结构体指针该指针不能为空因此要将pq进行assert断言同时在出队列时队列内不能一个节点都没有所以要判断队列内不为空因此要将!QueueEmpty进行assert断言在队列中的尾数据就为ptail指针指向的节点内存放的数据 因此该函数直接放回pq-ptail-data即可 //取队列尾数据
QDataType QueueBack(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq-ptail-data;
} 2.7队列有效数据个数
要完成队列有效数据个数函数首先要在Queue.h内完成函数的声明
//队列有效数据个数
int QueueSize(Queue* pq);
将该函数命名为QueueSize函数的参数为存放指向头尾节点指针的结构体指针函数的返回值就为队列内有效的数据个数
完成了函数的声明接下来就是在Queue.c函数内完成函数的定义 因为以下函数中的pq指针是存放指向头尾节点指针的结构体指针该指针不能为空因此要将pq进行assert断言因为队列内的有效数据个数就为结构体Queue内的成员变量size的值 所以该函数直接放回pq-size即可 //队列有效数据个数
int QueueSize(Queue* pq)
{assert(pq);return pq-size;
} 2.8队列的销毁
要完成队列的销毁函数首先要在Queue.h内完成函数的声明
//销毁队列
void QueueDestory(Queue* pq);
将该函数命名为QueueDestory 函数的参数为存放指向头尾节点指针的结构体指针
完成了函数的声明接下来就是在Queue.c函数内完成函数的定义 因为以下函数中的pq指针是存放指向头尾节点指针的结构体指针该指针不能为空因此要将pq进行assert断言同时在出队列时队列内不能一个节点都没有所以要判断队列内不为空因此要将!QueueEmpty进行assert断言 在销毁过程中通过遍历的方法来用free释放链表的所有节点最后再将指针phead和指针ptail置为空将有效数据个数赋值为0 //销毁队列
void QueueDestory(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));QueueNode* pcur pq-phead;while (pcur){QueueNode* Next pcur-next;free(pcur);pcur Next;}pq-phead pq-ptail NULL;pq-size 0;
} 3.队列实现完整代码
Queue.h
#pragma once
#includestdio.h
#includestdlib.h
#includeassert.h
#includestdbool.h//队列结构的定义
typedef int QDataType;
typedef struct QueueNode
{QDataType data;//节点内的数据struct QueueNode* next;//指向下一个节点的指针}QueueNode;typedef struct Queue
{struct QueueNode* phead;//指向第一个节点的指针struct QueueNode* ptail;//指向尾节点的指针int size;//节点的个数}Queue;
//初始化队列
void QueueInit(Queue* pq);
//销毁队列
void QueueDestory(Queue* pq);
//入队列
void QueuePush(Queue* pq, QDataType x);
//出队列
void QueuePop(Queue* pq);
//队列判空
bool QueueEmpty(Queue* pq);
//取队列头数据
QDataType QueueFront(Queue* pq);
//取队列尾数据
QDataType QueueBack(Queue* pq);
//队列有效数据个数
int QueueSize(Queue* pq); Queue.c
#includeQueue.h//初始化队列
void QueueInit(Queue* pq)
{assert(pq);pq-phead pq-ptail NULL;pq-size 0;
}//销毁队列
void QueueDestory(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));QueueNode* pcur pq-phead;while (pcur){QueueNode* Next pcur-next;free(pcur);pcur Next;}pq-phead pq-ptail NULL;pq-size 0;
}//队列判空
bool QueueEmpty(Queue* pq)
{assert(pq);return pq-phead NULL pq-ptail NULL;
}//入队列
void QueuePush(Queue* pq, QDataType x)
{assert(pq);QueueNode* newnode (QueueNode*)malloc(sizeof(QueueNode));if (newnode NULL){perror(malloc fail!);exit(1);}newnode-data x;newnode-next NULL;if (pq-phead NULL){pq-phead pq-ptail newnode;}else{pq-ptail-next newnode;pq-ptail newnode;}pq-size;
}//出队列
void QueuePop(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));if (pq-phead pq-ptail){free(pq-phead);pq-phead pq-ptail NULL;}else{QueueNode* Next pq-phead-next;free(pq-phead);pq-phead Next;}pq-size--;}//取队列头数据
QDataType QueueFront(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq-phead-data;
}//取队列尾数据
QDataType QueueBack(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq-ptail-data;}//队列有效数据个数
int QueueSize(Queue* pq)
{assert(pq);return pq-size;
}
