点击刷新
以下内容只是学习记录：
一、定义
队列是一种先进先出的线性表。在表的一端进行插入（队尾），另一端删除元素（对头）实现形式有：顺序队列（顺序表实现）和链式队列（链式表实现）
二、代码编写
1、链队列实现：
结构体定义及功能函数声明：
#ifndef __LINKQUEUE_H__
#define __LINKQUEUE_H__
#include <stdio.h>
#include "malloc.h"
#include "assert.h"
#define ElemType int
typedef struct QueueNode
{
ElemType data;
struct QueueNode *next;
}QueueNode;
typedef struct LinkQueue
{
QueueNode *front;
QueueNode *tail;
}LinkQueue;
void InitQueue(LinkQueue *p);
void EnQueue(LinkQueue *p, ElemType x);
void ShowQueue(LinkQueue *p);
void DeQueue(LinkQueue *p);
void GetHead(LinkQueue *p, ElemType *v);
int Length(LinkQueue *p);
void ClearQueue(LinkQueue *p);
void DestroyQueue(LinkQueue *p);
#endif
功能函数编写：
#include "LinkQueue.h"
void InitQueue(LinkQueue *p)
{
QueueNode *s = (QueueNode *)malloc(sizeof(QueueNode));
s->data = 0;
assert(s != NULL);
p->front = p->tail = s;
p->tail->next = NULL;
}
void EnQueue(LinkQueue *p, ElemType x)
{
QueueNode *s = (QueueNode *)malloc(sizeof(QueueNode));
assert(s != NULL);
s->data = x;
s->next = NULL;
p->tail->next = s;
p->tail = s;
p->front->data++;
}
void ShowQueue(LinkQueue *p)
{
QueueNode *s = p->front->next;
printf("Front->");
while (s != NULL)
{
printf("%d->", s->data);
s = s->next;
}
printf("Tail\n");
}
void DeQueue(LinkQueue *p)
{
if (p->front == p->tail)
return;
QueueNode *s = p->front->next;
p->front->next = s->next;
free(s);
s = NULL;
if (p->front->next == NULL)
p->tail = p->front;
p->front->data--;
}
void GetHead(LinkQueue *p, ElemType *v)
{
if (p->front == p->tail)
return;
QueueNode *s = p->front->next;
*v = s->data;
}
int Length(LinkQueue *p)
{
return p->front->data;
}
void ClearQueue(LinkQueue *p)
{
if (p->front == p->tail)
return;
QueueNode *s = p->front->next;
while (s != NULL)
{
p->front->next = s->next;
free(s);
s = p->front->next;
}
p->tail = p->front;
p->front->data = 0;
}
void DestroyQueue(LinkQueue *p)
{
ClearQueue(p);
free(p->front);
p->tail = p->front = NULL;
}
Main函数编写：
#include "LinkQueue.h"
void main()
{
LinkQueue Q;
InitQueue(&Q);
ElemType elem;
for (int i = 1; i <= 10; ++i)
{
EnQueue(&Q, i);
}
ShowQueue(&Q);
DeQueue(&Q);
ShowQueue(&Q);
GetHead(&Q, &elem);
printf("队头元素：%d\n", elem);
ClearQueue(&Q);
int len = Length(&Q);
printf("队列长度为：%d", len);
}
2、顺序队列实现
结构体定义及功能函数声明：
#ifndef __SEQQUEUE_H__
#define __SEQQUEUE_H__
#include "stdio.h"
#include "malloc.h"
#include "assert.h"
#define ElemType int
#define MAXSIZE 8
typedef struct Queue
{
ElemType *base;
int front;
int rear;
}Queue;
void InitQueue(Queue *Q);
void EnQueue(Queue *Q, ElemType x);
void Show(Queue *Q);
void DeQueue(Queue *Q);
int Length(Queue *Q);
void GetHead(Queue *Q, ElemType *v);
void ClearQueue(Queue *Q);
void DestroyQueue(Queue *Q);
#endif
功能函数编写：
#include "SeqQueue.h"
void InitQueue(Queue *Q)
{
Q->base = (ElemType *)malloc(sizeof(ElemType) * MAXSIZE);
assert(Q->base != NULL);
Q->front = Q->rear = 0;
}
void EnQueue(Queue *Q, ElemType x)
{
if (Q->rear >= MAXSIZE)
return;
Q->base[Q->rear++] = x;
}
void Show(Queue *Q)
{
for (int i = Q->front; i < Q->rear; i++)
{
printf("%d ",Q->base[i]);
}
printf("\n");
}
void DeQueue(Queue *Q)
{
if (Q->front == Q->rear)
return;
Q->front++;
}
int Length(Queue *Q)
{
return Q->rear - Q->front;
}
void GetHead(Queue *Q, ElemType *v)
{
if (Q->front == Q->rear)
return;
*v = Q->base[Q->front];
}
void ClearQueue(Queue *Q)
{
Q->front = Q->rear = 0;
}
void DestroyQueue(Queue *Q)
{
free(Q->base);
Q->base = NULL;
}
Main函数编写：
#include "SeqQueue.h" void main() { Queue Q; InitQueue(&Q); for (int i = 1; i <= 5; i++) { EnQueue(&Q, i); } Show(&Q); DeQueue(&Q); Show(&Q); int len = Length(&Q); printf("长度为：%d", len); }
3、循环队列实现
基础概念：
输入自然数：x
周期：n
x%n的取值范围：0~n-1
结构体定义及功能函数声明：
#ifndef __CSEQQUEUE_H__ #define __CSEQQUEUE_H__ #include "stdio.h" #include "malloc.h" #include "assert.h" #define ElemType int #define MAXSIZE 8 typedef struct Queue { ElemType *base; int front; int rear; }Queue; void InitQueue(Queue *Q); void EnQueue(Queue *Q, ElemType x); void Show(Queue *Q); void DeQueue(Queue *Q); int Length(Queue *Q); void GetHead(Queue *Q, ElemType *v); void ClearQueue(Queue *Q); void DestroyQueue(Queue *Q); #endif
功能函数编写：
#include "CSeqQueue.h" void InitQueue(Queue *Q) { Q->base = (ElemType *)malloc(sizeof(ElemType) * MAXSIZE); assert(Q->base != NULL); Q->front = Q->rear = 0; } void EnQueue(Queue *Q, ElemType x) { if ((Q->rear + 1) % MAXSIZE == Q->front) return; Q->base[Q->rear] = x; Q->rear = (Q->rear + 1) % MAXSIZE; } void Show(Queue *Q) { for (int i = Q->front; i != Q->rear;) { printf("%d ", Q->base[i]); i = (i + 1) % MAXSIZE; } printf("\n"); } void DeQueue(Queue *Q) { if (Q->front == Q->rear) return; Q->front = (Q->front + 1) % MAXSIZE; } int Length(Queue *Q) { return (Q->rear - Q->front + MAXSIZE) % MAXSIZE; } void GetHead(Queue *Q, ElemType *v) { if (Q->front == Q->rear) return; *v = Q->base[Q->front]; } void ClearQueue(Queue *Q) { Q->front = Q->rear = 0; } void DestroyQueue(Queue *Q) { free(Q->base); Q->base = NULL; }
Main函数编写：
#include "CSeqQueue.h" void main() { Queue Q; InitQueue(&Q); for (int i = 1; i <=10; i++) { EnQueue(&Q, i); } Show(&Q); DeQueue(&Q); EnQueue(&Q, 99); Show(&Q); /*int len = Length(&Q); printf("长度为：%d", len);*/ }
© 著作权归作者所有
举报
发表评论
0/200
