队列的链式存储称为链式队列。链式队列就是一个特殊的单链表,对于这种特殊的单链表,它的插入和删除操作规定在单链表的不同端进行。链式队列的队首和队尾指针分别用front和rear表示。
链式队列要掌握以下基本操作:
1、建立一个空的链式队列
2、判断链式队列是否为空
3、输出链式队列各个结点的值
4、取得链式队列的队首的结点值
5、对链式队列中插入一个值为x的结点
6、删除链式队列中队首节点
“队头删除,队尾插入”
运行环境:Dev-C++5.11
以下是头文件
#ifndef LNKQUEUE_H_INCLUDED#define LNKQUEUE_H_INCLUDED#include <stdio.h>#include <stdlib.h>typedef struct link_node{int info;struct link_node *next;}N;typedef struct {N *front ,*rear;}queue;/*建立一个空的链式队列*/queue *init(){queue *qu;qu=(queue*)malloc(sizeof(queue));qu->front=NULL;qu->rear=NULL;return qu;}/*判断链式队列是否为空*/int isempty(queue *qu){return (qu->front?0:1); } /*取得链式队列队首结点值*/int read (queue *qu){if(!qu->front){printf("\n该链式队列为空\n");exit(1);}return (qu->front->info);}/*输出链式队列各结点的值*/void display (queue *qu){N *p=qu->front;if(!p){printf("该链式队列为空,无法进行打印\n");}else{while(p){printf("%d ",p->info);p=p->next;}}}/*向链式队列中插入一个值为x的结点(队尾插入)*/queue *insert(queue *qu,int x){N *p;p=(N*)malloc(sizeof(N));p->info=x;p->next=NULL;if(!qu->front){qu->front=qu->rear=p;}else{qu->rear->next=p;qu->rear=p;}return qu;}/*删除链式队列中的队首结点*/queue *dele(queue *qu){N *q=qu->front;if(!qu->front){printf("该链式队列为空\n");return qu;}qu->front=q->next;free(q);return qu;} #endif // LNKQUEUE_H_INCLUDED
以下是主程序:
#include "stdio.h"#include "lnkqueue.h"int main (){int x;queue *qu;while(1){qu=init();printf("\n\n创建一个新的,以输入-1为结束\n");scanf("%d",&x);while(x!=-1){qu=insert(qu,x);scanf("%d",&x);}if(isempty(qu)){printf("该链式队列为空!\n"); }else{printf("该链式队列不为空!\n");}display (qu);printf("\n链式队列的队首结点值为:%d\n",read (qu));printf("进行插入操作,请输入要插入的数:");scanf("%d",&x);qu=insert(qu,x);display(qu);printf("\n进行删除操作后:\n"); qu=dele(qu);display(qu);}return 0;}