数据结构：实验二队列的基本功能实现

川长思鸟来 2023-07-11 12:35 66阅读 0赞

# 实验二 队列的基本功能实现 #

## 一、实验目的 ##

1、掌握用 VC上机调试队列的基本方法；  
2、掌握队列的基本操作，以顺序表示、链式表示两种存储方式实现队列的建立、插入、删除算法。

## 二、实验环境 ##

1、PC微机；  
2、Windows 操作系统；  
3、VC6.0或以上

## 三、实验内容 ##

在队列的顺序表示和链式表示两种方式中选择一种存储方式，实现队列的创建、插入、删除算法；编写程序、定义相应的变量，上机调式实现本次实验内容。

## 四、实验步骤、测试及结果 ##

1.代码

#include<stdio.h>
    #include<stdlib.h>
    #include<assert.h>
    
    #define ERROR  0
    #define OK     1
    #define TRUE   1
    #define FALSE  0
    #define QUEUESIZE 10
    
    typedef int Status;
    typedef int QElemtype;
    
    typedef struct QNode{
        
    	QElemtype *base;
    	int front;
    	int rear;
    }SqQueue;
    
    //初始化
    void InitQueue(SqQueue *Q)
    {
        
    	Q->base=(QElemtype*)malloc(sizeof(QElemtype)*QUEUESIZE);
    	assert(Q->base!=NULL);
    	Q->front=Q->rear=0; 
    }
    
    //入队
    Status EnQueue(SqQueue *Q,QElemtype e)
    {
        
    	if(Q->rear==QUEUESIZE)
    	{
        
    		return ERROR;
    	}
    	Q->base[Q->rear]=e;
    	Q->rear++;
    	return OK;
    }
    
    //判断是否为空
    Status QueueEmpty(SqQueue *Q)
    {
        
    	if(Q->front==Q->rear)
    	{
        
    		return TRUE;
    	}
    	return FALSE;
    }
    
    //求长度
    Status QueueLength(SqQueue Q)
    {
        
    	return Q.rear-Q.front;
    }
    
    //获取队头元素
    Status GetHead(SqQueue *Q,QElemtype *e)
    {
        
    	if(Q->front==Q->rear)
    	{
        
    		return ERROR;
    	}
    	*e=Q->base[Q->front];
    	return OK;
    }
    
    //销毁
    void DestoryQueue(SqQueue *Q)
    {
        
    	if(Q->base)      //队列Q存在 
    	{
        
    		free(Q->base);
    	}
    	Q->base=NULL;
    	Q->front=Q->rear=0;
    }
    
    //清空
    
    void ClearQueue(SqQueue *Q)
    {
        
    	Q->front=Q->rear=0;
    }
    
    //出队
    Status DeQueue(SqQueue *Q,QElemtype *e)
    {
        
    	if(Q->front==Q->rear)
    	{
        
    		return ERROR;
    	}
    	*e=Q->base[Q->front];
    	Q->front++;
    	return OK;
    }
    
    //遍历
    void QueueTraverse(SqQueue Q,void(*visit)(QElemtype))
    {
        
    	int i=Q.front;
    	while(i!=Q.rear)
    	{
        
    		visit(Q.base[i]);
    		i++;
    	}
    	printf("\n");
    } 
    void Print(QElemtype e)
    {
        
    	printf("%d ",e);
    }
    //主函数
    int main()
    {
        
    	QElemtype i,e,d;
    	SqQueue Q;
    	InitQueue(&Q);
    	printf("请输入队列的%d个元素：\n",QUEUESIZE);
    	for(i=0;i<QUEUESIZE;i++)
    	{
        
    		scanf("%d",&d);
    		EnQueue(&Q,d);
    	}
    	printf("队列的元素为:");
    	QueueTraverse(Q,Print);
    	printf("队列长度为：%d\n",QueueLength(Q));
    	int k=QueueLength(Q);
    	printf("连续%d次由对头删除元素，队尾插入元素:\n",k/2);
    	for(i=0;i<k/2;i++)
    	{
        
    		DeQueue(&Q,&e);
    		printf("删除的队列的元素是：%d,请输入插入的元素：",e);
    		scanf("%d",&d);
    		EnQueue(&Q,d);
    	}
    	printf("新的队列元素为：\n");
    	QueueTraverse(Q,Print);
    	
    	int n=GetHead(&Q,&e);
    	if(n)printf("对头元素为：%d\n",e);
    	else {
        
    		printf("队空!\n");	return -1;
    	}
    	ClearQueue(&Q);
    	printf("清空队列后队列是否为空：%d\t(1:为空 ,0:不为空)\n",QueueEmpty(&Q));
    	DestoryQueue(&Q);
    	printf("销毁队列后:\nQ.base=%u\tQ.front=%d\tQ.rear=%d\t\n",Q.base,Q.front,Q.rear);
    	return 0; 
    }

1.  运行结果  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5nemlsaGM_size_16_color_FFFFFF_t_70]

## 五、实验小结 ##

1.队列是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。允许插入的端是队尾，允许删除的端是队头。  
2. 顺序存储就是用数组实现，比如有一个ｎ个元素的队列，数组下标0的一端是队头，入队操作就是通过数组下标一个个顺序追加，不需要移动元素，但是如果删除队头元素，后面的元素就要往前移动，对应的时间复杂度就是O(n)。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5nemlsaGM_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200305161716429.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5nemlsaGM=,size_16,color_FFFFFF,t_70