你的位置:首页 > 信息动态 > 新闻中心
信息动态
联系我们

【数据结构/C语言版】【队列】(链式+顺序)

2021/10/17 15:48:17

链式

#include<iostream>
#include<cstdlib>
using namespace std;
#define QElemType int 
#define Status int 

typedef struct QNode {
	QElemType data;
	struct QNode* next;
}QNode, * QueuePtr;

typedef struct {
	QueuePtr front;
	QueuePtr rear;
}LinkQueue;

Status InitQueue(LinkQueue& Q)
{
	Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode));
	if (!Q.front)
		exit(_OVERFLOW);
	Q.front->next = NULL;
	return 1;
}

Status DestroyQueue(LinkQueue& Q)
{
	while (Q.front) {
		Q.rear = Q.front->next;
		free(Q.front);
		Q.front = Q.rear;
	}
	return 1;
}

Status ClearQueue(LinkQueue& Q)
{
	QueuePtr p, q;
	Q.rear = Q.front;
	p = Q.front->next;
	Q.front->next = NULL;
	while (p) {
		q = p;
		p = p->next;
		free(q);
	}
	return 1;
}

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

int QueueLength(LinkQueue Q)
{
	int ans = 0;
	QueuePtr p = Q.front;
	while (p != Q.rear) {
		ans++;
		p = p->next;
	}
	return ans;
}

Status GetHead(LinkQueue Q, QElemType& e)
{
	if (Q.front == Q.rear)
		return 0;
	e = Q.front->next->data;
	return 1;
}

Status EnQueue(LinkQueue& Q, QElemType e)
{
	QueuePtr p = (QueuePtr)malloc(sizeof(QNode));
	if (!p)
		exit(_OVERFLOW);
	p->data = e;
	p->next = Q.rear->next;
	Q.rear->next = p;
	Q.rear = p;
	return 1;
}

Status DeQueue(LinkQueue& Q, QElemType& e)
{
	QueuePtr p;
	if (Q.front == Q.rear)
		return 0;
	p = Q.front->next;//f r(p)
	e = p->data;
	Q.front->next = p->next;
	if (Q.front->next == NULL)  // 特判
		Q.front = Q.rear;
	free(p);
	return 1;
}

void visit(QElemType a) {
	cout << a << " ";
}

Status QueueTraverse(LinkQueue& Q, void(*visit)(QElemType))
{
	QueuePtr p = Q.front->next;
	while (p) {
		visit(p->data);
		p = p->next;
	}
	cout << endl;
	return 1;
}

int main()
{
	return 0;
}

顺序(循环队列)

#include<iostream>
#include<cstdlib>
using namespace std;
#define QElemType int
#define Status int
#define MAXQSIZE 100

typedef struct {
	QElemType* base;
	int front;
	int rear;
}SqQueue;

Status InitQueue(SqQueue& Q)
{
	Q.base = (QElemType*)malloc(sizeof(QElemType));
	if (!Q.base)
		exit(_OVERFLOW);
	Q.front = Q.rear = 0;
	return 1;
}

Status QueueEmpty(SqQueue Q)
{
	if (Q.front == Q.rear)
		return 1;
	return 0;
}

Status DestroyQueue(SqQueue& Q)
{
	while (!QueueEmpty(Q)) {
		free(&Q.base[Q.front]);
		Q.front = (Q.front + 1) % MAXQSIZE;
	}
}

int QueueLength(SqQueue Q)
{
	return (Q.rear - Q.front + MAXQSIZE) % MAXQSIZE;
}

Status ClearQueue(SqQueue& Q)
{
	if (QueueEmpty(Q))
		return 0;
	int len = QueueLength(Q);
	while (len--) {
		Q.base[Q.front] = 0;
		Q.front = (Q.front + 1) % MAXQSIZE;
	}
	Q.front = Q.rear = 0;
	return 1;
}

Status GetHead(SqQueue Q, QElemType& e)
{
	if (QueueEmpty(Q))
		return 0;
	e = Q.base[Q.front];
	return 1;
}

Status EnQueue(SqQueue& Q, QElemType e)
{
	if ((Q.rear + 1) % MAXQSIZE == Q.front)
		return 0;
	Q.base[Q.rear] = e;
	Q.rear = (Q.rear + 1) % MAXQSIZE;
	return 1;
}

Status DeQueue(SqQueue& Q, QElemType& e)
{
	if (QueueEmpty(Q))
		return 0;
	e = Q.base[Q.front];
	Q.front = (Q.front + 1) % MAXQSIZE;
	return 1;
}

void visit(QElemType e)
{
	cout << e << ' ';
}

Status QueueTraverse(SqQueue& Q, Status(*visit)(QElemType))
{
	if (QueueEmpty(Q))
		return 0;
	for (int i = Q.front; i != Q.rear; i++)
	{
		visit(Q.base[i]);
	}
	cout << endl;
	return 1;
}

int main()
{

	return 0;
}