赞
踩
- #include<stdio.h>
- #include<stdlib.h>
-
- #define ElemType int
- #define null NULL
-
- typedef struct LNode{ //链表结点
- ElemType data;
- struct LNode *next;
- }LNode;
-
- typedef struct QNode{ //队列指针
- LNode *front,*rear;
- }QNode;
- //队列初始化
- bool initQueue(QNode *queue){
- LNode *head = (LNode *)malloc(sizeof(LNode));
- //内存空间分配失败
- if(head == null){
- return false;
- }
- head->next = null;
- queue->front = head;
- queue->rear = head;
- return true;
- }
- //队列判空
- bool isEmpty(QNode *queue){
- return queue->front == queue->rear;
- }
- //入队
- bool EnQueue(QNode *queue,ElemType e){
- //链表的入队不用判队列满
- LNode *s = (LNode *)malloc(sizeof(LNode));
- s->data = e;
- s->next = null;
- queue->rear->next = s;
- queue->rear = s;
- return true;
- }
- //出队
- bool DeQueue(QNode *queue,ElemType &x){
- //链表的出队要判队列空
- if(isEmpty(queue)){
- return false;
- }
- //最后一个结点
- if(queue->front->next == queue->rear){
- queue->rear = queue->front;
- }
- LNode *d = queue->front->next;
- x = d->data;
- queue->front->next = d->next;
- free(d);
- return true;
- }
- //队列的删除(保留头结点)
- bool deleteQueue(QNode *queue){
- //队列为空,无元素可删
- if(isEmpty(queue)){
- return false;
- }
- while(queue->front->next != queue->rear){ //删除非最后一个元素
- LNode *d = queue->front->next;
- queue->front->next = d->next;
- free(d);
- }
- //删除最后一个元素需要将尾指针指向头结点
- queue->rear = queue->front;
- free(queue->front->next);
- queue->front->next=null;
- return true;
- }
- //队列的销毁(不保留头结点)
- bool DestoryQueue(QNode *queue){
- //删除队列中元素
- deleteQueue(queue);
- //释放头结点
- free(queue->front);
- queue->front = null;
- queue->rear = null;
- return true;
- }
- //获取队头元素
- bool getQueueHead(QNode *queue,ElemType &x){
- if(isEmpty(queue)){
- return false;
- }
- x = queue->front->next->data;
- return true;
- }
- //队列的打印
- void printQueue(QNode *queue){
- LNode *head = queue->front;
- while(head->next!=null){
- printf("%d\n",head->next->data);
- head=head->next;
- }
- }
- int main(int argc, char *argv[])
- {
- //队列的两个指针在栈空间
- QNode queue;
- initQueue(&queue);
- EnQueue(&queue,1);
- EnQueue(&queue,2);
- EnQueue(&queue,3);
- EnQueue(&queue,4);
- EnQueue(&queue,5);
-
- ElemType x;
- getQueueHead(&queue,x);
- printf("队头元素是%d\n",x);
- getQueueHead(&queue,x);
- printf("队头元素是%d\n",x);
-
- ElemType e;
- DeQueue(&queue,e);
- printf("弹出的元素是%d\n",e);
- printQueue(&queue);
- EnQueue(&queue,6);
- EnQueue(&queue,7);
- printf("---------------\n");
- printQueue(&queue);
-
- //删除队列元素
- //deleteQueue(&queue);
- //printQueue(&queue);
- //bool flag = isEmpty(&queue);
- //printf("元素清空后为空吗%d\n",flag);
-
- //销毁队列元素
- DestoryQueue(&queue);
- bool flag = isEmpty(&queue);
- printf("队列销毁后为空吗%d\n",flag);
-
- return 0;
- }
- //队列初始化
- bool initQueue(QNode *queue){
- queue->front = null;
- queue->rear = null;
- return true;
- }
- //队列判空 queue->front == null || queue->rear == null 或者的判空关系也对
- bool isEmpty(QNode *queue){
- return queue->front == null && queue->rear == null;
- }
- //入队
- bool EnQueue(QNode *queue,ElemType e){
- //链表的入队不用判队满
- LNode *s = (LNode *)malloc(sizeof(LNode));
- s->data = e;
- s->next = null;
- //入队时是第一个元素
- if(queue->rear == null){
- queue->front = s;
- queue->rear = s;
- return true; //没这个return,最终结果也正确,但是第一个结点会在第二个结点没有入队时成环(自己指向自己)
- }
- //入队时不是第一个元素
- queue->rear->next = s;
- queue->rear = s;
- return true;
- }
- //出队
- bool DeQueue(QNode *queue,ElemType &x){
- //链表的出队要判队空
- if(isEmpty(queue)){
- return false;
- }
- LNode *d = queue->front;
- x = d->data;
- queue->front = d->next;
- free(d);
- //删除到最后一个结点了
- if(queue->front == null){
- queue->rear = null;
- }
- return true;
- }
- //队列的销毁
- bool DestoryQueue(QNode *queue){
- //队列为空,无元素可删
- if(isEmpty(queue)){
- return false;
- }
- while(queue->front != null){
- LNode *d = queue->front;
- queue->front = d->next;
- free(d);
- }
- //删完了,queue->rear指针置为null
- queue->rear=null;
- return true;
- }
- //获取队头元素
- bool getQueueHead(QNode *queue,ElemType &x){
- if(isEmpty(queue)){
- return false;
- }
- x=queue->front->data;
- return true;
- }
- //队列的打印
- void printQueue(QNode *queue){
- LNode *head = queue->front;
- while(head!=null){
- printf("%d\n",head->data);
- head=head->next;
- }
- }
- int main(int argc, char *argv[])
- {
- QNode *queue=(QNode *)malloc(sizeof(QNode));
- initQueue(queue);
- EnQueue(queue,1);
- EnQueue(queue,2);
- EnQueue(queue,3);
- EnQueue(queue,4);
- EnQueue(queue,5);
-
- ElemType x;
- getQueueHead(queue,x);
- printf("队头元素是%d\n",x);
-
- getQueueHead(queue,x);
- printf("队头元素是%d\n",x);
-
- ElemType e;
- DeQueue(queue,e);
-
- printf("出队的元素是%d\n",e);
- printQueue(queue);
-
- EnQueue(queue,6);
- EnQueue(queue,7);
- printf("---------------\n");
- printQueue(queue);
-
- bool flag1 = isEmpty(queue);
- printf("元素销毁前为空吗%d\n",flag1);
-
-
- DestoryQueue(queue);
- printf("销毁后的链表打印\n");
- printQueue(queue);
-
- bool flag = isEmpty(queue);
- printf("元素销毁后为空吗%d\n",flag);
-
- return 0;
- }
带头结点和不带头结点的测试方法是有差异的,一个是声明了一个结构体,一个是声明了一个指针指向了堆内存的QNode型对象。
这两种声明方式都能执行出正确的结果, 第一种声明结构体的方式,相当于front指针,rear指针在栈空间声明。销毁链表也不用管这块存储空间,他会随着函数的调用完成而消失。
第二种声明方式,相当于在堆内存中开辟了一个结点,去存储front指针,rear指针。这里我们链表销毁只是释放了LNode结点,并没有将QNode结点释放。这里我们用的是一级指针。一级指针是无法将QNode结点释放的,准确的说,一级指针可以将QNode所占的堆内存回收,但是无法改变main函数中QNode指针的指向,导致main函数中的QNode指针指向了一块被回收的未知区域。
<<链表操作的二级指针问题>>有说明这个问题。
正确的做法是: 我们函数的参数使用二级指针即可。
在main函数中写QNode *head; 不主动为其在堆内存中分配空间,程序依然不报错,是程序默认为其在堆内存中分配了一个结点空间吗?有没有懂C/C++的大佬帮忙解惑一下。
无论是带头结点还是不带头结点的队列的实现方式。我觉得复杂度差不多。
出队的时候都要判断是否为最后一个元素,进而改变尾指针的指向。
最好是两种都实现一下,自己体会一下。
1.双端队列(允许两端插入、两端删除)
2.输入受限的双端队列(允许一端插入、两端删除)
3.输出受限的双端队列(允许两端端插入、一端删除)
队列的变种经常会给出 入队顺序、判断合法的出队顺序。
针对2而言。输入受限,所以根据这一特性,把输出元素序列的第一个元素之前的元素统统入队。
针对3而言,输出受限。所以根据这一特性,先把输出顺序对应好,看元素按顺序从两端入队能否得到此输出序列。
双端队列的实现,如果使用链表实现,需要使用双向链表。如果使用静态数组实现,需要使用逻辑上循环的静态数组。
如有错误,望指正!
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。