网站开发php程序员,做响应网站,网站建设与维护试卷论文,wordpress主题祥情在那改鼠鼠我呀#xff0c;今天写一个基于C语言关于队列的博客#xff0c;如果有兴趣的读者老爷可以抽空看看#xff0c;很希望的到各位老爷观点和点评捏#xff01; 在此今日#xff0c;也祝各位小姐姐女生节快乐啊#xff0c;愿笑容依旧灿烂如初阳#xff0c;勇气与童真永不…鼠鼠我呀今天写一个基于C语言关于队列的博客如果有兴趣的读者老爷可以抽空看看很希望的到各位老爷观点和点评捏 在此今日也祝各位小姐姐女生节快乐啊愿笑容依旧灿烂如初阳勇气与童真永不退色 目录
1.队列的概念及结构 2.对列的实现
2.1.queue.h
2.2.queue.c
2.3.test.c
2.4.定义队列
2.5.初始化队列
2.6.队尾入队列
2.7.对头出队列
2.8.获取队列队头元素
2.9.获取队列队尾元素
2.10.获取队列中有效元素的个数
2.11.检测队列是否为空如果为空返回非零结果非空返回0
2.12.销毁队列 3.分析运行结果
4.ending 1.队列的概念及结构
队列只允许在一端进行插入数据操作在另一端进行删除数据操作的特殊线性表队列中的数据元素具有先进先出 FIFO(First In First Out) 的特点。
队尾进行插入操作的一端称为队尾。
对头进行删除操作的一端称为队头 。
咱们画一个队列的想象图就很好理解上面几个概念 其实很好理解队列里面的数据元素就像排队一样先进入队列的数据元素当然先出队列了。 2.对列的实现
队列也可以数组和链表的结构实现使用链表的结构实现更优一些因为如果使用数组的结构出队列在数组头上出数据效率会比较低。
而队列用链表实现的方案也是多种多样只要满足队列的定义即可。鼠鼠我今天写一个方案本方案基于无头单向非循环链表各位佬们可以看看啊俺先把三个文件和运行结果呈现如下
2.1.queue.h
#pragma once
#includestdio.h
#includeassert.h
#includestdlib.h
#includestdbool.htypedef int QDatatype;typedef struct QNode
{QDatatype _data;struct QNode* _next;
}QNode;typedef struct Queue
{int k;QNode* head;QNode* tail;
}Queue;//初始化队列
void QueueInit(Queue* q);//队尾入数据
void QueuePush(Queue* q, QDatatype data);//对头出数据
void QueuePop(Queue* q);//获取队列对头元素
QDatatype QueueFront(Queue* q);//获取队列队尾元素
QDatatype QueueBack(Queue* q);//获取队列中有效元素个数
int QueueSize(Queue* q);//检测队列是否为空如果为空返回非零结果非空返回0
bool QueueEmpty(Queue* q);//销毁队列
void QueueDestory(Queue* q);
2.2.queue.c
#define _CRT_SECURE_NO_WARNINGS
#includequeue.hvoid QueueInit(Queue* q)
{assert(q);q-head q-tail NULL;q-k 0;
}void QueuePush(Queue* q, QDatatype data)
{assert(q);QNode* tmp (QNode*)malloc(sizeof(QNode));if (tmp NULL){perror(malloc fail);return;}tmp-_data data;tmp-_next NULL;if (q-tail NULL){q-head q-tail tmp;}else{q-tail-_next tmp;q-tail tmp;}q-k;
}void QueuePop(Queue* q)
{assert(q);assert(q-k 0);QNode* next q-head-_next;free(q-head);q-head next;if (q-head NULL){q-tail NULL;}q-k--;
}QDatatype QueueFront(Queue* q)
{assert(q);assert(q-k 0);return q-head-_data;
}QDatatype QueueBack(Queue* q)
{assert(q);assert(q-k 0);return q-tail-_data;
}int QueueSize(Queue* q)
{assert(q);return q-k;
}bool QueueEmpty(Queue* q)
{assert(q);return q-tail NULL;
}void QueueDestory(Queue* q)
{assert(q);QNode* tmp q-head;while (tmp){QNode* next tmp-_next;free(tmp);tmp next;}q-k 0;q-head q-tail NULL;
}
2.3.test.c
#define _CRT_SECURE_NO_WARNINGS
#includequeue.hint main()
{Queue q;QueueInit(q);QueuePush(q, 0);QueuePush(q, 1);QueuePush(q, 1);QueuePush(q, 2);QueuePush(q, 3);QueuePush(q, 4);QueuePush(q, 5);QueuePush(q, 6);printf(%d\n, QueueSize(q));printf(%d , QueueFront(q));printf(%d\n, QueueBack(q));printf(%d , QueueFront(q));QueuePop(q);while (!QueueEmpty(q)){printf(%d , QueueFront(q));QueuePop(q);}printf(\n%d\n, QueueSize(q));QueueDestory(q);return 0;
} 运行结果如图至于为什么是这些个结果我们详细看以下鼠鼠的队列方案是如何实现的。 2.4.定义队列
typedef int QDatatype;typedef struct QNode
{QDatatype _data;struct QNode* _next;
}QNode;typedef struct Queue
{int k;QNode* head;QNode* tail;
}Queue;
老样子我们将int重命名成QDatatype方便以后代码的维护。
让后定义并重命名结构体QNode充当队列节点 这些节点根据数据元素的入队列或者出队列按需申请或者释放。QNode中成员_data用来存放数据元素QNode中成员_next用来链接下一个节点。
又由于基于无头单向非循环链表以下简称链表实现的队列在入队列和出队列时分别需要链表尾插和头删而且经常需要知道队列中数据元素的个数我们定义并重命名结构体Queue来维护上面需求Queue中成员k用来记录队列中数据元素个数成员head用来指向链表头节点成员tail用来指向链表尾节点。
大概这样子 2.5.初始化队列
void QueueInit(Queue* q)
{assert(q);q-head q-tail NULL;q-k 0;
}
断言防止传入的结构体变量地址为空因为这个地址不可能为空。将head和tail置成NULL将k置成0即可。
2.6.队尾入队列
void QueuePush(Queue* q, QDatatype data)
{assert(q);QNode* tmp (QNode*)malloc(sizeof(QNode));if (tmp NULL){perror(malloc fail);return;}tmp-_data data;tmp-_next NULL;if (q-tail NULL){q-head q-tail tmp;}else{q-tail-_next tmp;q-tail tmp;}q-k;
}
断言防止传入的结构体变量地址为空这点以下不在赘述。 队尾入队列其实就是链表尾插先动态申请一个结构体QNode空间充当新节点这个新节点的存放好想插入的数据元素再让新节点链接好队列链接队列是要区分队列是否为空k加一即可。
2.7.对头出队列
void QueuePop(Queue* q)
{assert(q);assert(q-k 0);QNode* next q-head-_next;free(q-head);q-head next;if (q-head NULL){q-tail NULL;}q-k--;
}
断言防止队列为空仍然出队列。常规来说再进行链表头删、k减一即可完成出队列但要注意如果队列中只有一个数据元素或者说链表只有一个节点时如果按常规操作的话会使得tail变成野指针用上面一个if语句很好处理问题。
2.8.获取队列队头元素
QDatatype QueueFront(Queue* q)
{assert(q);assert(q-k 0);return q-head-_data;
} 断言防止队列为空仍然获取对头元素。返回head指向的节点成员_data即可。
2.9.获取队列队尾元素
QDatatype QueueBack(Queue* q)
{assert(q);assert(q-k 0);return q-tail-_data;
} 断言防止队列为空仍然获取对尾元素。返回tail指向的节点成员_data即可。
2.10.获取队列中有效元素的个数
int QueueSize(Queue* q)
{assert(q);return q-k;
}
根据设定可知返回k即可。
2.11.检测队列是否为空如果为空返回非零结果非空返回0
bool QueueEmpty(Queue* q)
{assert(q);return q-tail NULL;
}
若tail指向NULL说明队列为空或者说链表为空则q-tailNULL为真返回真。若队列不为空逻辑跟队列为空逻辑相反返回假。
2.12.销毁队列
void QueueDestory(Queue* q)
{assert(q);QNode* tmp q-head;while (tmp){QNode* next tmp-_next;free(tmp);tmp next;}q-k 0;q-head q-tail NULL;
}
遍历链表将节点这些节点都是动态申请的都释放掉再将head和tail置成NULL并将k置成0即可。 3.分析运行结果
佬们请看 第一条语句定义一个结构体Queue变量q
第二条语句初始化结构体变量q
第三条到第十条语句数据元素0、1、1、2、3、4、5、6依次入队列执行完后队列想象图为 第十一条语句执行printf函数打印队列有效元素个数为8并换行。
第十二条和第十三条语句均执行printf函数分别打印对头元素0和队尾元素6换行。
第十四条语句 执行printf函数打印对头元素0。
第十五条语句对头元素0出队列执行完第十五条语句后队列想象图为 接下来while循环当队列不为空时打印对头元素再对头元素出队列。所以分别打印1、1、2、3、4、5、6。执行完while循环后队列为空或者说链表为空。
再接下来打印队列有效元素个数为0印证队列为空。再销毁队列。
4.ending 感谢阅读有不对的地方欢迎像本鼠拿捏玩偶一样拿捏鼠鼠捏
