(C语言队列的顺序实现(数据结构十)

梦里梦外; 2022-09-17 10:25 196阅读 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 Queue{
    	ElemType *data;
    	int      head;
    	int      tail;
    	int      capacity;
    }Queue,*pQueue;

3.队列顺序实现

LinerQueue.h中实现代码如下：

#ifndef LINARQUEUE_H
    #define LINARQUEUE_H
    
    #include "head.h"
    
    #define  INIT_QUEUE_CAPACITY 100
    #define  QUEUE_ICREMENT_SIZE 10
    
    typedef struct Queue{
    	ElemType *data;
    	int      head;
    	int      tail;
    	int      capacity;
    }Queue,*pQueue;
    
    
    //初始化队列
    Status InitQueue(pQueue &Q){
    	Q=(pQueue)malloc(sizeof(Queue));
    	if(!Q) return OVERFLOW;
    	Q->data=(ElemType*)malloc(INIT_QUEUE_CAPACITY*sizeof(ElemType));
    	if(!Q->data) return OVERFLOW;
    	Q->head=0;
    	Q->tail=0;
    	Q->capacity=INIT_QUEUE_CAPACITY;
    	return OK;
    }
    //销毁队列
    Status DestroyQueue(pQueue &Q){
    	free(Q->data);
    	Q->head=0;
    	Q->tail=0;
    	Q->capacity=0;
    	free(Q);
    	Q=NULL;
    	return OK;
    }
    //清空队列
    Status ClearQueue(pQueue &Q){
    	if(Q==NULL) return ERROR;
    	Q->head=0;
    	Q->tail=0;
    	Q->capacity=INIT_QUEUE_CAPACITY;
    	return OK;
    }
    //队列是否为空
    Status QueueEmpty(pQueue Q){
    	if(Q==NULL) return ERROR;
    	return Q->head==Q->tail;
    }
    //队列长度
    Status QueueLength(pQueue Q){
    	if(Q==NULL) return ERROR;
    	return Q->tail-Q->head;
    }
    //取得队头数据
    Status GetHead(pQueue Q,ElemType &e){
    	if(QueueLength(Q)==0) return ERROR;
    	e=Q->data[Q->head];
    	return OK;
    }
    //从队尾插入数据
    Status InsertQueue(pQueue &Q,ElemType e){
    	if(QueueLength(Q)>=Q->capacity){
    		Q->data=(ElemType*)realloc(Q->data,(Q->capacity+QUEUE_ICREMENT_SIZE)*sizeof(ElemType));
    		if(!Q->data) return OVERFLOW;
    		Q->capacity+=QUEUE_ICREMENT_SIZE;
    	}
    	Q->data[Q->tail++]=e;
    	return OK;
    }
    //从队头删除数据
    Status DeleteQueue(pQueue &Q,ElemType &e){
    	if(Q==NULL) return ERROR;
    	GetHead(Q,e);
    	for (int i=Q->head+1;i<=Q->tail;i++)
    	{
    		Q->data[i-1]=Q->data[i];
    	}
    	Q->tail--;
    	return OK;
    }
    //用(*visit)()遍历队列
    Status QueueTraverse(pQueue &Q,Status (*visit)(ElemType)){
    	for (int i=Q->tail-1;i>=Q->head;i--)
    	{
    		(*visit)(Q->data[i]);
    	}
    	return OK;
    }
    Status print(ElemType e){
    	printf("%d->",e);
    	return true;
    }
    //输出队列
    Status printQueue(pQueue Q){
    	if(Q==NULL) return ERROR;
    	printf("\ntail->");
    	QueueTraverse(Q,print);
    	printf("head\n");
    	return true;
    }
    
    #endif

4.测试栈

#include "LinerQueue.h"
    void main(){
    	pQueue Q;
    	InitQueue(Q);
    	for (int i=0;i<10;i++)
    	{
    		InsertQueue(Q,i);
    	}
    
    	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.测试结果

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