数据结构——顺序队列与链式队列的实现-1
https://developer.aliyun.com/article/1507982
6、出队
C语言实现如下所示：
bool out_seqqueue(seq_pqueue q,datatype *D) { //判断队列是否空 if(is_empty_seqqueue(q)){ printf("队列已空!\n"); return false; } //出队 q->front=(q->front+1)%MAXSIZE; *D=q->data[q->front]; return true; }
7、打印队列
C语言实现如下所示：
void show_seqqueue(seq_pqueue q) { int i; if(is_empty_seqqueue(q)) return; //非空时，从对头打印到队尾 for(i=(q->front+1)%MAXSIZE;i!=(q->rear+1)%MAXSIZE;i=(i+1)%MAXSIZE) { printf("%d\t",q->data[i]); } printf("\n"); }
8、队列的顺序表实现源码
seqqueue.h
#ifndef __SEQQUEUE_H__ #define __SEQQUEUE_H__ #include <stdio.h> #include <stdlib.h> #include <stdbool.h> #define MAXSIZE 10 typedef int datatype; typedef struct seqqueue{ datatype data[MAXSIZE]; int front,rear; }seq_queue,*seq_pqueue; extern seq_pqueue init1_seqqueue(void); extern void init_seqqueue(seq_pqueue *Q); extern bool is_full_seqqueue(seq_pqueue q); extern bool is_empty_seqqueue(seq_pqueue q); extern bool in_seqqueue(datatype data,seq_pqueue q); extern bool out_seqqueue(seq_pqueue q,datatype *D); extern void show_seqqueue(seq_pqueue q); #endif
seqqueue.c
#include "seqqueue.h" seq_pqueue init1_seqqueue(void) { seq_pqueue q; q=(seq_pqueue)malloc(sizeof(seq_queue)); if(q==NULL) { perror("malloc"); exit(-1); } q->front=q->rear=MAXSIZE-1; return q; } void init_seqqueue(seq_pqueue *Q) { *Q=(seq_pqueue)malloc(sizeof(seq_queue)); if((*Q)==NULL) { perror("malloc"); exit(-1); } (*Q)->front=(*Q)->rear=MAXSIZE-1; return; } //判断队列是否满 bool is_full_seqqueue(seq_pqueue q) { if((q->rear+1)%MAXSIZE == q->front) return true; else return false; } //入队 bool in_seqqueue(datatype data,seq_pqueue q) { //判断队列是否满 if(is_full_seqqueue(q)){ printf("队列已满!\n"); return false; } //入队 q->rear=(q->rear+1)%MAXSIZE; q->data[q->rear]=data; return true; } //判断队列是否空 bool is_empty_seqqueue(seq_pqueue q) { if(q->rear == q->front) return true; else return false; } //出队 bool out_seqqueue(seq_pqueue q,datatype *D) { //判断队列是否空 if(is_empty_seqqueue(q)){ printf("队列已空!\n"); return false; } //出队 q->front=(q->front+1)%MAXSIZE; *D=q->data[q->front]; return true; } void show_seqqueue(seq_pqueue q) { int i; if(is_empty_seqqueue(q)) return; //非空时，从对头打印到队尾 for(i=(q->front+1)%MAXSIZE;i!=(q->rear+1)%MAXSIZE;i=(i+1)%MAXSIZE) { printf("%d\t",q->data[i]); } printf("\n"); }
test.c
#include "seqqueue.h" /* 用循环队列实现如下功能： * 用户从键盘输入整数，程序将其入队; * 用户从键盘输入字母，程序将队头元素出队; * 并在每一次出队和入队之后打印队列元素。 */ int main(int argc, const char *argv[]) { seq_pqueue q; datatype data,t,ret; init_seqqueue(&q); while(1) { printf("请输入一个整数或字符:"); ret=scanf("%d",&data); //输入整数时，入队 if(ret == 1) { if(in_seqqueue(data,q)) show_seqqueue(q); } else { //输入为字符时 if(out_seqqueue(q,&t)) { printf("out:%d\n",t); show_seqqueue(q); } //清空输入缓冲区 while(getchar()!='\n'); } } return 0; }
Makefile
CC = gcc CFLAGS = -o0 -g -Wall SRC=seqqueue.c test.c OBJS=test $(OBJS):$(SRC) $(CC) $(CFLAGS) -o $@ $^ .PHONY:clean clean: rm -rf $(OBJS) *.o
- "-o0"表示优化级别为0，即关闭优化。这将导致生成的可执行文件较大，但是可以方便地进行调试。
- "-g"表示生成调试信息，以便在调试程序时可以查看变量的值、函数的调用栈等信息。
- "-Wall"表示启用所有警告，编译器将会显示所有可能的警告信息，帮助开发人员发现潜在的问题。
编译结果测试:
四、队列的链表实现
1、数据结构定义
对于链表，在进行 队列的定义 之前，我们需要考虑以下几个点：
1）队列数据的存储方式，以及队列数据的数据类型；
2）队列的大小；
3）队首指针；
4）队尾指针；
我们可以定义一个 队列 的 结构体，C语言实现如下所示：
typedef int datatype; typedef struct linkqueuenode{ datatype data; /* 数据域 */ struct linkqueuenode *next; /* 指针域 */ }linkqueue_node,*linkqueue_pnode; typedef struct linkqueue{ linkqueue_pnode front,rear; /* 链队列指针 */ }link_queue,*link_pqueue;
2、初始化创造队列
C语言实现如下所示：
void init_linkqueue(link_pqueue *Q) { //申请front和rear的空间 *Q=(link_pqueue)malloc(sizeof(link_queue)); if((*Q)==NULL) { perror("malloc"); exit(-1); } //申请头结点空间 (*Q)->front=(linkqueue_pnode)malloc(sizeof(linkqueue_node)); if((*Q)->front==NULL) { perror("malloc"); exit(-1) ; } (*Q)->front->next=NULL; (*Q)->rear=(*Q)->front; return; }
3、判断队列是否空
C语言实现如下所示：
bool is_empty_linkqueue(link_pqueue q) { if(q->rear == q->front) return true; else return false; }
4、入队
C语言实现如下所示：
bool in_linkqueue(datatype data,link_pqueue q) { linkqueue_pnode new; //申请数据结点空间 new=(linkqueue_pnode)malloc(sizeof(linkqueue_node)); if(new==NULL) { puts("入队失败！"); return false; } //将数据存储在申请的空间 new->data=data; //将new指向的结点插入到链式队列中 new->next=q->rear->next; q->rear->next=new; //让rear指针指向新的队尾结点 q->rear=q->rear->next; return true; }
5、出队
C语言实现如下所示：
bool out_linkqueue(link_pqueue q,datatype *D) { linkqueue_pnode t; //判断队列是否空 if(is_empty_linkqueue(q)){ printf("队列已空!\n"); return false; } //出队 t=q->front; q->front =q->front->next; *D=q->front->data; free(t); return true; }
6、打印队列
C语言实现如下所示：
void show_linkqueue(link_pqueue q) { linkqueue_pnode p; if(is_empty_linkqueue(q)) return; //非空时，从对头打印到队尾 for(p=q->front->next;p!=NULL;p=p->next) { printf("%d\t",p->data); } printf("\n"); }
7、队列的链表实现源码
linkqueue.h
#ifndef __LINKQUEUE_H__ #define __LINKQUEUE_H__ #include <stdio.h> #include <stdlib.h> #include <stdbool.h> typedef int datatype; typedef struct linkqueuenode{ datatype data; struct linkqueuenode *next; }linkqueue_node,*linkqueue_pnode; typedef struct linkqueue{ linkqueue_pnode front,rear; }link_queue,*link_pqueue; extern void init_linkqueue(link_pqueue *Q); extern bool is_empty_linkqueue(link_pqueue q); extern bool in_linkqueue(datatype data,link_pqueue q); extern bool out_linkqueue(link_pqueue q,datatype *D); extern void show_linkqueue(link_pqueue q); #endif
linkqueue.c
#include "linkqueue.h" void init_linkqueue(link_pqueue *Q) { //申请front和rear的空间 *Q=(link_pqueue)malloc(sizeof(link_queue)); if((*Q)==NULL) { perror("malloc"); exit(-1); } //申请头结点空间 (*Q)->front=(linkqueue_pnode)malloc(sizeof(linkqueue_node)); if((*Q)->front==NULL) { perror("malloc"); exit(-1) ; } (*Q)->front->next=NULL; (*Q)->rear=(*Q)->front; return; } //入队 bool in_linkqueue(datatype data,link_pqueue q) { linkqueue_pnode new; //申请数据结点空间 new=(linkqueue_pnode)malloc(sizeof(linkqueue_node)); if(new==NULL) { puts("入队失败！"); return false; } //将数据存储在申请的空间 new->data=data; //将new指向的结点插入到链式队列中 new->next=q->rear->next; q->rear->next=new; //让rear指针指向新的队尾结点 q->rear=q->rear->next; return true; } bool is_empty_linkqueue(link_pqueue q) { if(q->rear == q->front) return true; else return false; } //出队 bool out_linkqueue(link_pqueue q,datatype *D) { linkqueue_pnode t; //判断队列是否空 if(is_empty_linkqueue(q)){ printf("队列已空!\n"); return false; } //出队 t=q->front; q->front =q->front->next; *D=q->front->data; free(t); return true; } void show_linkqueue(link_pqueue q) { linkqueue_pnode p; if(is_empty_linkqueue(q)) return; //非空时，从对头打印到队尾 for(p=q->front->next;p!=NULL;p=p->next) { printf("%d\t",p->data); } printf("\n"); }
test.c
#include "linkqueue.h" /* 用链式队列实现如下功能： * 用户从键盘输入整数，程序将其入对; * 用户从键盘输入字母，程序将队头元素出队; * 并在每一次出队和入队之后打印队列元素。 */ int main(int argc, const char *argv[]) { link_pqueue q; datatype data,t,ret; init_linkqueue(&q); while(1) { printf("请输入一个整数或字符:"); ret=scanf("%d",&data); //输入整数时，入对 if(ret == 1) { if(in_linkqueue(data,q)) show_linkqueue(q); } else { //输入为字符时 if(out_linkqueue(q,&t)) { printf("out:%d\n",t); show_linkqueue(q); } //清空输入缓冲区 while(getchar()!='\n'); } } return 0; }
Makefile
CC = gcc CFLAGS = -o0 -g -Wall SRC=linkqueue.c test.c OBJS=test $(OBJS):$(SRC) $(CC) $(CFLAGS) -o $@ $^ .PHONY:clean clean: rm -rf $(OBJS) *.o
- "-o0"表示优化级别为0，即关闭优化。这将导致生成的可执行文件较大，但是可以方便地进行调试。
- "-g"表示生成调试信息，以便在调试程序时可以查看变量的值、函数的调用栈等信息。
- "-Wall"表示启用所有警告，编译器将会显示所有可能的警告信息，帮助开发人员发现潜在的问题。
编译结果测试:
