头文件
ElemType.h
/****ElemType.h - ElemType的定义*****/
#ifndef ELEMTYPE_H#define ELEMTYPE_H
typedef int ElemType;
int compare(ElemType x, ElemType y);void visit(ElemType e);
#endif /* ELEMTYPE_H */DynaLnkQueue.h
/****DynaLnkQueue.h - 动态链式队列的定义*****/
#if !defined(DYNALNKQUEUE_H)#define DYNALNKQUEUE_H
#include "ElemType.h"
/*------------------------------------------------------------// 链式队列结构的定义------------------------------------------------------------*/
typedef struct Node{ ElemType data; // 元素数据 struct Node *next; // 链式队列中结点元素的指针} QNode, *QueuePtr;
typedef struct{ QueuePtr front; // 队列头指针 QueuePtr rear; // 队列尾指针} LinkQueue;
/*------------------------------------------------------------// 链式队列的基本操作------------------------------------------------------------*/
bool InitQueue(LinkQueue *Q);void DestroyQueue(LinkQueue *Q);bool QueueEmpty(LinkQueue Q);int QueueLength(LinkQueue Q);bool GetHead(LinkQueue Q, ElemType *e);void QueueTraverse(LinkQueue Q, void (*fp)(ElemType));void ClearQueue(LinkQueue *Q);bool EnQueue(LinkQueue *Q, ElemType e);bool DeQueue(LinkQueue *Q, ElemType *e);
#endif
主函数
Lab.cpp
#include <stdio.h>#include <stdlib.h>#include "DynaLnkQueue.h"
int main(){ LinkQueue *Q; ElemType e=3; InitQueue(&Q); DestroyQueue(&Q); QueueEmpty(&Q); QueueLength(&Q); GetHead(&Q,e); QueueTraverse(&Q, visit(e)); ClearQueue(&Q); EnQueue(&Q,e); DeQueue(&Q,&e); system("pause"); return true;}
实现函数
ElemType.cpp
/****ElemType.cpp - ElemType的实现*****/
#include <stdio.h>#include "ElemType.h"
int compare(ElemType x, ElemType y){ return(x-y);}
void visit(ElemType e){ printf("%dn", e);}DynaLnkQueue.cpp
/****DynaLnkQueue.cpp - 动态链式队列，即队列的动态链式存储实现***题目：实验4 队列的动态链式存储实现*
*****/
#include <stdlib.h>#include <malloc.h>#include <memory.h>#include <assert.h>#include "DynaLnkQueue.h"
/*------------------------------------------------------------操作目的： 初始化队列初始条件： 无操作结果： 构造一个空的队列函数参数： LinkQueue *Q 待初始化的队列返回值： bool 操作是否成功------------------------------------------------------------*/bool InitQueue(LinkQueue *Q)//初始化带头结点的队列{ Q->front = Q->rear = (QueuePtr)malloc(sizeof(QNode)); if (!Q->front) { return false; } Q->front->next = NULL; return true;
}
/*------------------------------------------------------------操作目的： 销毁队列初始条件： 队列Q已存在操作结果： 销毁队列Q函数参数： LinkQueue *Q 待销毁的队列返回值： 无------------------------------------------------------------*/void DestroyQueue(LinkQueue *Q){ while(Q->front) { Q->rear = Q->front->next; free(Q->front); Q->front = Q->rear; }
}
/*------------------------------------------------------------操作目的： 判断队列是否为空初始条件： 队列Q已存在操作结果： 若Q为空队列，则返回true，否则返回false函数参数： LinkQueue Q 待判断的队列返回值： bool 是否为空------------------------------------------------------------*/bool QueueEmpty(LinkQueue Q){ if (Q.front!=Q.rear) { return false; } return true;}
/*------------------------------------------------------------操作目的： 得到队列的长度初始条件： 队列Q已存在操作结果： 返回Q中数据元素的个数函数参数： LinkQueue Q 队列Q返回值： int 数据元素的个数------------------------------------------------------------*/int QueueLength(LinkQueue Q){ int i; QueuePtr p= Q.front; while(p) { p = p->next; i++; } return i;}
/*------------------------------------------------------------操作目的： 得到队列首元素初始条件： 队列Q已存在操作结果： 用e返回队列首元素函数参数： LinkQueue Q 队列Q ElemType *e 队列首元素的值返回值： bool 操作是否成功------------------------------------------------------------*/bool GetHead(LinkQueue Q, ElemType *e){ if (Q.front == Q.rear) { return false; } *e = Q.front->data; return true;}
/*------------------------------------------------------------操作目的： 遍历队列初始条件： 队列Q已存在操作结果： 依次对Q的每个元素调用函数fp函数参数： LinkQueue Q 队列Q void (*fp)() 访问每个数据元素的函数指针返回值： 无------------------------------------------------------------*/void QueueTraverse(LinkQueue Q, void (*fp)(ElemType)){ QueuePtr p = Q.front->next; while(p) { fp(p->data); p = p->next; }}
/*------------------------------------------------------------操作目的： 清空队列初始条件： 队列Q已存在操作结果： 将队列清空函数参数： LinkQueue *Q 队列Q返回值： 无------------------------------------------------------------*/void ClearQueue(LinkQueue *Q){ QueuePtr p=Q->front->next; while(p) { p->data = NULL; p= p->next; }}
/*------------------------------------------------------------操作目的： 在队列末尾插入元素e初始条件： 队列Q已存在操作结果： 插入元素e作为队列新的尾结点函数参数： LinkQueue *Q 队列Q ElemType e 待插入的数据元素返回值： bool 操作是否成功------------------------------------------------------------*/bool EnQueue(LinkQueue *Q, ElemType e){ QueuePtr p =(QueuePtr)malloc(sizeof(QNode)); if (!p) { return false; } p->data = e; p->next = NULL; Q->rear->next = p; Q->rear = p; return true;
}
/*------------------------------------------------------------操作目的： 删除链式队列的头结点初始条件： 队列Q已存在操作结果： 删除链式队列的头结点函数参数： LinkQueue *Q 队列Q ElemType *e 待插入的数据元素返回值： bool 操作是否成功------------------------------------------------------------*/bool DeQueue(LinkQueue *Q, ElemType *e){ QueuePtr p =Q->front->next; if (Q->front == Q->rear) { return false; } *e = p->data; Q->front->next = p->next; if (!p->next) { Q->rear = Q->front; } free(p);
return true;}
评论