(C语言)队列的链式实现(数据结构十一)

╰+哭是因爲堅強的太久メ 2022-09-17 10:25 187阅读 0赞

1.数据类型定义

在代码中为了清楚的表示一些错误和函数运行状态，我们预先定义一些变量来表示这些状态。在head.h头文件中有如下定义：

//定义数据结构中要用到的一些变量和类型
    #ifndef HEAD_H
    #define HEAD_H
    
    #include <stdio.h>
    #include <malloc.h>
    #include <stdlib.h>
    
    #define TRUE  1
    #define FALSE 0
    #define OK    1
    #define ERROR  0
    #define INFEASIBLE -1
    #define OVERFLOW   -2    //分配内存出错
    
    typedef int  Status;     //函数返回值类型
    typedef int  ElemType;   //用户定义的数据类型
    
    #endif

2.数据结构实现

typedef struct Node{
    	ElemType data;
    	struct Node* next;
    }Node,*pNode;
    
    typedef struct LinkQueue{
    	pNode head;
    	pNode tail;
    	int  length;
    }LinkQueue,*pLinkQueue;

3.队列链式实现

LinkQueue.h代码实现如下：

#ifndef LINKQUEUE_H
    #define LINKQUEUE_H
    
    #include "head.h"
    
    typedef struct Node{
    	ElemType data;
    	struct Node* next;
    }Node,*pNode;
    
    typedef struct LinkQueue{
    	pNode head;
    	pNode tail;
    	int  length;
    }LinkQueue,*pLinkQueue;
    
    //初始化队列
    Status InitQueue(pLinkQueue &Q){
    	Q=(pLinkQueue)malloc(sizeof(LinkQueue));
    	if(!Q) return OVERFLOW;
    	pNode p=(pNode)malloc(sizeof(Node));
    	if(!p) return OVERFLOW;
    	p->next=NULL;
    	Q->head=p;
    	Q->tail=p;
    	Q->length=0;
    	return OK;
    }
    
    //队列长度
    Status QueueLength(pLinkQueue Q){
    	if(Q==NULL) return ERROR;
    	return Q->length;
    }
    //队列是否为空
    Status QueueEmpty(pLinkQueue Q){
    	
    	return QueueLength(Q)==0;
    }
    
    
    
    //取得队头数据
    Status GetHead(pLinkQueue Q,ElemType &e){
    	if(QueueLength(Q)<1) return ERROR;
    	e=Q->head->next->data;
    	return true;
    }
    //从队尾插入数据
    Status InsertQueue(pLinkQueue &Q,ElemType e){
    	pNode q=Q->tail;
    	pNode p=(pNode)malloc(sizeof(Node));
    	p->data=e;
    	p->next=NULL;
    	Q->tail=p;
    	q->next=Q->tail;
    	Q->length++;
    	return true;
    }
    //从队头删除数据
    Status DeleteQueue(pLinkQueue &Q,ElemType &e){
    	if(QueueLength(Q)<1) return ERROR;
    	if(QueueLength(Q)==1){
    		e=Q->tail->data;
    	}else{
    		pNode p=Q->head;
    		Q->head=p->next;
    		e=Q->head->data;
    		free(p);
    	}
    	Q->length--;
    	return true;
    }
    //用(*visit)()遍历队列
    Status QueueTraverse(pLinkQueue &Q,Status (*visit)(ElemType)){
    	pNode p=Q->head;
    	do{
    		p=p->next;
    		(*visit)(p->data);
    	}while((p!=Q->tail));
    	return true;
    }
    Status print(ElemType e){
    	printf("%d<<",e);
    	return true;
    }
    //输出队列
    Status printQueue(pLinkQueue Q){
    	if(QueueLength(Q)<1) return ERROR;
    	printf("\nhead<<");
    	QueueTraverse(Q,print);
    	printf("tail\n");
    	return true;
    }
    //清空队列
    Status ClearQueue(pLinkQueue &Q){
    	while(!QueueEmpty(Q)){
    		ElemType e;
    		DeleteQueue(Q,e);
    	}
    	return OK;
    }
    //销毁队列
    Status DestroyQueue(pLinkQueue &Q){
    	ClearQueue(Q);
    	free(Q->head);
    	free(Q->tail);
    	free(Q);
    	Q=NULL;
    	return OK;
    }
    
    #endif

4.测试队列

#include "LinkQueue.h"
    void main(){
    	pLinkQueue Q;
    	InitQueue(Q);
    	for (int i=0;i<10;i++)
    	{
    		InsertQueue(Q,i);
    	}
    
    	 printQueue(Q);
    
    	 ElemType e2;
    	 DeleteQueue(Q,e2);
    	 printf("\n删除队列头：%d",e2);
    
    
     	printQueue(Q);
     
     	printf("\n队列长度：%d",QueueLength(Q));
    
     	ElemType e;
     	GetHead(Q,e);
     	printf("\n队列头:%d",e);
     
    
    	ClearQueue(Q);
     	DestroyQueue(Q);
     	
    
    }

5.测试结果如下

head<<0<<1<<2<<3<<4<<5<<6<<7<<8<<9<<tail
    
    删除队列头：0
    head<<1<<2<<3<<4<<5<<6<<7<<8<<9<<tail
    
    队列长度：9
    队列头:1