链式队列的基本操作C语言详解

待我称王封你为后i 2023-07-18 06:00 13阅读 0赞

**链式队列有带头结点，和不带头结点的，我这里是带头结点的。  
逻辑结构如图  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5MTY2NQ_size_16_color_FFFFFF_t_70]  
编译环境vc6.0,代码如下：**

/* 首元结点是指链表中存储线性表中第一个数据元素的结点。 初始化：队头指针和队尾指针都指向头结点（不是首元结点） 队满状态：只要还有内存，理论上不会满 进队操作：插入到链尾，尾指针指向新的尾结点 出头操作：删除首元结点（不是头结点），头指针指向新首元结点 */
    
    #include <stdio.h>
    #include <stdlib.h>
    
    //结点结构
    typedef struct QNode
    { 
    	int data;
    	struct QNode* next;
    }QNode,*Queueptr;
    
    //链表结构
    typedef struct
    { 
    	Queueptr front, rear;    //对头，队尾指针
    }LinkQueue;
    
    //************************初始化**************************
    int InitLinkQueue(LinkQueue* Q)
    { 
    	Q->front = Q->rear = (QNode*)malloc(sizeof(QNode));			 //建立头结点
    	if (!Q->rear || !Q->front)
    	{ 
    		return 0;
    		printf("动态分配内存失败\n");
    	}
    	Q->front->next = NULL;										//初始化为空
    	return 1;
    }
    
    //************************判断是否非空**************************
    int IsEmpty(LinkQueue Q)
    { 
    	if (Q.front == Q.rear)									//头尾指针同时指向头结点为空
    		return 1;
    	else return 0;
    }
    
    //************************入队**************************
    int EnQueue(LinkQueue* Q, int e)
    { 
    	Queueptr s = (Queueptr)malloc(sizeof(QNode));         //动态申请内存
    	if (s == NULL)
    		return 0;
    	s->data = e;
    	s->next = NULL;                                    //s插入到链尾巴，所有next指针指向空
    	Q->rear->next = s;									//插入
    	Q->rear = s;										//尾指针指向新的尾结点
    	return 1;
    }
    
    //************************出队**************************
    int DeQueue(LinkQueue* Q, int* e)
    { 
    	Queueptr p;
    	if (Q->front == Q->rear)						//队空
    		return 0;
    	p = Q->front->next;                           //将欲删除的结点暂存给p
    	*e = p->data;										//获取元素值
    	Q->front->next = p->next;						//删除Q->front->next, Q->front时头结点，Q->front->next 时首元结点
    
    	if (Q->rear == p)							  //若删除后只剩下头结点，将尾指针指向头结点
    		Q->rear = Q->front;
    	free(p);
    	return 1;
    }
    
    //************************遍历输出**************************
    int LinkQueueTraverse(LinkQueue Q)
    { 
    	Queueptr p;                   //结点指针
    	if (IsEmpty(Q))
    	{ 
    		printf("链表为空\n");
    		return 0;
    	}
    	p = Q.front->next;              //p指向首元结点
    	while (p)
    	{ 
    		printf("%-5d", p->data);
    		p = p->next;
    	}
    	return 1;
    }
    
    int main()
    { 
    	int i, e, n;						//e入队元素，n入队元素个数
    	LinkQueue Q;
    	InitLinkQueue(&Q);							//初始化
    	printf("初始化成功\n");
    
    	printf("请输入,入队元素个数\n");
    	scanf("%d", &n);
    	for (i = 0; i < n; i++)
    	{ 
    		printf("请输入第%d个元素值", i + 1);
    		scanf("%d", &e);
    		if (EnQueue(&Q, e))
    			printf("入队成功\n");
    		else printf("入队失败\n");
    	}
    
    	if (DeQueue(&Q, &e))
    		printf("\n元素%d出队\n", e);
    	else printf("出队失败\n");
    
    	printf("遍历输出\n");
    	LinkQueueTraverse(Q);
    	return 0;
    }

**测试案例：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5MTY2NQ_size_16_color_FFFFFF_t_70 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5MTY2NQ_size_16_color_FFFFFF_t_70]: /images/20230528/99c4dbe238a04c68825972994d27afb9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5MTY2NQ_size_16_color_FFFFFF_t_70 1]: /images/20230528/406311fc97304d27a7b651399166d61a.png