数据结构-006-链队

比眉伴天荒 2023-02-27 08:21 5阅读 0赞

## 链队列的定义 ##

队列的链式表示称为链队列。如下图：  
![在这里插入图片描述][20200817154612798.png_pic_center]

链队列分为带头结点和不带头结点的链队列  
链队列的存储结构：

typedef struct QNode{
        	
    	DataType data;	
    	struct QNode* next;
    }LQNode, *PQNode;
    typedef struct{
        	
    	PQNode front, rear;
    }LinkQueue;

## 1.初始化链队列 ##

int InitQueue(LinkQueue *Q){
        	
    	Q->front=Q->rear=(PQNode)malloc(sizeof(LQNode));
    	if(!Q->front){
        printf("初始化队列失败！\n");return 0;}
    	Q->front->next=NULL;
    	return 1;
    }

## 2．判队空 ##

int QueueEmpty(LinkQueue Q){
        
    	if(Q.front==Q.rear)	
    		return 1;
    	else	
    		return 0;
    }

## 3.入队 ##

**操作步骤：**

1.  生成新结点。
2.  在队尾指针所指位置插入新结点。
3.  队尾指针后移，指向新的队尾。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzY3MzE1Ng_size_16_color_FFFFFF_t_70_pic_center]

int EnQueue(LinkQueue *Q,DataType e){
        	
    	PQNode p;
    	p=(PQNode)malloc(sizeof(LQNode));
    	if(!p){
        
    		printf("内存分配失败，不能完成入队操作！\n");
    	  return 0;}
    	p->data=e;
    	p->next=NULL;	/*初始化入队结点*/
    	Q->rear->next=p;
    	Q->rear=p;
    	return 1;
    }

## 4.出队 ##

**操作步骤：**

1.  判断所给链队列是否为空，若空则产生下溢出错误，算法结束。否则执行步骤（2）。
2.  删除队头指针所指结点。
3.  如果被删结点是队列的最后一个结点，则移动队尾指针，使其指向头结点。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzY3MzE1Ng_size_16_color_FFFFFF_t_70_pic_center 1]

int DeQueue(LinkQueue *Q,DataType *e){
        	
    	PQNode p;
    	if(Q->front==Q->rear){
        
    		printf("队列已空，不能完成出队操作！\n");return 0;}
    	p=Q->front->next;
    	*e=p->data;
    	Q->front->next=p->next;	
    	free(p);
    	if(Q->rear==p)  /*若删的是最后一个结点，移动尾指针*/
    		Q->rear=Q->front;
    	return 1;
    }

## 5.销毁队列 ##

int DestroyQueue(LinkQueue *Q){
        	
    	while(Q->front){
        
    		   Q->rear=Q->front->next;
    		   free(Q->front);
    		   Q->front=Q->rear;
    	}	
    	return 1;
    }

## 完整代码： ##

#include<stdio.h>
    #include<stdlib.h>
    typedef int QElemType;
    typedef struct QNode{
        
    	QElemType data;
    	struct QNode *next;
    }Qnode,*QuenePtr;
    typedef struct{
        
    	QuenePtr front;
    	QuenePtr rear;
    }LinkQuene;
    void Initquene(LinkQuene &s){
        
    	s.front=(QuenePtr)malloc(sizeof(Qnode));
    	if(!s.front)
    		exit(-1);
    	s.rear=s.front;
    	s.front->next=NULL;
    }
    void enquene(LinkQuene &s,QElemType e){
        
    	QuenePtr p=(QuenePtr)malloc(sizeof(Qnode));
    	if(!p)
    		exit(-1);
    	p->data=e;
    	p->next=NULL;
    	s.rear->next=p;
    	s.rear=p;
    }
    void dequene(LinkQuene &s,QElemType &e){
        
    	if(s.front==s.rear){
        
    		printf("error");
    		exit(0);
    	}
    	QuenePtr p=s.front->next;
    	e=p->data;
    	s.front->next=p->next;
    	if(s.rear==p){
        
    		s.rear=s.front;
    	}
    	free(p);
    }
    int Destory(LinkQuene &s){
        
    	while(s.front){
        
    		s.rear=s.front->next;
    		free(s.front);
    		s.front=s.rear;
    	}
    	if(s.front==s.rear){
        
    		return 1;
    	}
    	return 0;
    }
    void print(LinkQuene s,int n){
        
    	QuenePtr p=s.front->next;
    	while(p!=s.rear){
        
    		printf("%d ",p->data);
    		p=p->next;
    	}
    	printf("%d",p->data);
    	printf("\n");
    }
    int main(){
        
    	LinkQuene s;
    	Initquene(s);
    	int n,m,x;
    
    	while(true){
        
    		printf("========================\n");
    		printf("Input number:\n");
    		printf("1-enqueue   2-dequeue\n");
    		printf("3-print  4-delete\n");
    				printf("========================\n");
    		int x;
    		
    		scanf("%d",&x);
    		if(x==1){
        
    				printf("========================\n");
    			printf("Enter how many Numbers are entered:\n");
    			int nn=0;
    			scanf("%d",&nn);
    			n+=nn;
    					printf("========================\n");
    			printf("Input number:\n");
    			for(int i=0;i<nn;i++){
        
    				scanf("%d",&m);
    				enquene(s,m);
    			}
    		}else if(x==2){
        
    			dequene(s,x);
    					printf("========================\n");
    			printf("%d out",x);
    			printf("\n");
    			print(s,n-1);		
    		}else if(x==3){
        
    			printf("========================\n");
    			print(s,n);
    			printf("========================\n");
    		}else{
        
    			int a=Destory(s);
    			if(a==1){
        
    					
    				
    				printf("========================\n");
    				printf("=delete success!");
    				printf("========================\n");
    			}
    			else{
        
    				
    				printf("error!");	
    			}
    		}
    	}
    
    	return 0;
    }

[20200817154612798.png_pic_center]: /images/20230209/783e89c059524f6f9310b3920e469f58.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzY3MzE1Ng_size_16_color_FFFFFF_t_70_pic_center]: /images/20230209/7f70e999ffb4420a9b17007574f4bf73.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzY3MzE1Ng_size_16_color_FFFFFF_t_70_pic_center 1]: https://img-blog.csdnimg.cn/20200817160006421.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzY3MzE1Ng==,size_16,color_FFFFFF,t_70#pic_center