链队列的实现及应用

crossoverpptx 2023-03-28 原文

本文记录单链队列（队列的链式存储结构）的数据结构定义及基本操作的算法描述，并对算法进行简单应用。

采用C语言实现，其中应用了少数C++特性，比如引用等。

源程序

//LinkQueue.cpp
#include <stdio.h>
#include <stdlib.h>

#define MAXQSIZE 5
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define OVERFLOW -2

typedef int Status;
typedef int QElemType;

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

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

//构造一个空队列Q
Status InitQueue(LinkQueue &Q)
{
	Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));
	if(!Q.front)
		exit(OVERFLOW);
	Q.front->next=NULL;
	return OK;
}

//销毁队列Q
Status DestroyQueue(LinkQueue &Q)
{
	while(Q.front)
	{
		Q.rear=Q.front->next;
		free(Q.front);
		Q.front=Q.rear;
	}
	return OK;
}

//把Q清为空队列
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 OK;
}

//若队列Q为空队列，则返回TRUE,否则返回FALSE
Status QueueEmpty(LinkQueue Q)
{
	if(Q.front==Q.rear)
		return TRUE;
	else
		return ERROR;
}

//返回Q的元素个数，即队列的长度
int QueueLength(LinkQueue Q)
{
	int i=0;
	QueuePtr p;
	p=Q.front;
	while(Q.rear!=p)
	{
		i++;
		p=p->next;
	}
	return i;
}

//若队列不空，则用e返回Q的队头元素，并返回OK;否则返回ERROR
Status GetHead(LinkQueue Q,QElemType &e)
{
	QueuePtr p;
	if(Q.front==Q.rear)
		return ERROR;
	p=Q.front->next;
	e=p->data;
	return OK;
}

//插入元素e作为新的队尾元素
Status EnQueue(LinkQueue &Q,QElemType e)
{
	QueuePtr p=(QueuePtr)malloc(sizeof(QNode));
	if(!p)
		exit(OVERFLOW);
	p->data=e;
	p->next=NULL;
	Q.rear->next=p;
	Q.rear=p;
	return OK;
}

//若队列不空，则删除Q的队头元素，用e返回其值，并返回OK；否则返回ERROR
Status DeQueue(LinkQueue &Q,QElemType &e)
{
	QueuePtr p;
	if(Q.front==Q.rear)
		return ERROR;
	p=Q.front->next;
	e=p->data;
	Q.front->next=p->next;
	if(Q.rear==p)
		Q.rear=Q.front;
	free(p);
	return OK;
}

//从队头到队尾依次对队列Q中每个元素调用函数visit()。一旦visit失败，则操作失败
Status QueueTraverse(LinkQueue Q,void (*visit)(QElemType))
{
	QueuePtr p;
	p=Q.front->next;
	while(p)
	{
		visit(p->data);
		p=p->next;
	}
	printf("\n");
	return OK;
}

void visit(QElemType i)
{
	printf("%d ",i);
}

int main()
{
	int i;
	QElemType d;
	LinkQueue q;
	i=InitQueue(q);
	if(i)
		printf("成功地构造了一个空队列！\n");
	printf("初始化队列后，队列空否？%d(1：空 0：否)，",QueueEmpty(q));
	printf("队列长度为：%d\n",QueueLength(q));
	EnQueue(q,-5);
	EnQueue(q,5);
	EnQueue(q,10);
	printf("插入3个元素（-5,5,10）后，队列长度为：%d\n",QueueLength(q));
	printf("现在队列空否？%d(1：空 0：否)\n",QueueEmpty(q));
	printf("现在队列中的元素为：");
	QueueTraverse(q,visit);
	i=GetHead(q,d);
	if(i==OK)
		printf("队头元素为：%d\n",d);
	DeQueue(q,d);
	printf("删除了队头元素：%d\n",d);
	i=GetHead(q,d);
	if(i==OK)
		printf("新的队头元素为：%d\n",d);
	ClearQueue(q);
	printf("清空队列后，q.front=%u q.rear=%u q.front->next=%u\n",q.front,q.rear,q.front->next);
	DestroyQueue(q);
	printf("销毁队列后，q.front=%u q.rear=%u\n",q.front,q.rear);
    return 0;
}

运行结果

成功地构造了一个空队列！
初始化队列后，队列空否？1(1：空 0：否)，队列长度为：0
插入3个元素（-5,5,10）后，队列长度为：3
现在队列空否？0(1：空 0：否)
现在队列中的元素为：-5 5 10
队头元素为：-5
删除了队头元素：-5
新的队头元素为：5
清空队列后，q.front=10555928 q.rear=10555928 q.front->next=0
销毁队列后，q.front=0 q.rear=0

队列的 front LinkQueue rear 算法与数据结构

有关链队列的实现及应用的更多相关文章

ruby - 将差异补丁应用于字符串/文件 - 2
对于具有离线功能的智能手机应用程序，我正在为Xml文件创建单向文本同步。我希望我的服务器将增量/差异(例如GNU差异补丁)发送到目标设备。这是计划:Time=0Server:hasversion_1ofXmlfile(~800kiB)Client:hasversion_1ofXmlfile(~800kiB)Time=1Server:hasversion_1andversion_2ofXmlfile(each~800kiB)computesdeltaoftheseversions(=patch)(~10kiB)sendspatchtoClient(~10kiBtransferred)Cl
ruby-on-rails - Rails 应用程序之间的通信 - 2
我构建了两个需要相互通信和发送文件的Rails应用程序。例如，一个Rails应用程序会发送请求以查看其他应用程序数据库中的表。然后另一个应用程序将呈现该表的json并将其发回。我还希望一个应用程序将存储在其公共(public)目录中的文本文件发送到另一个应用程序的公共(public)目录。我从来没有做过这样的事情，所以我什至不知道从哪里开始。任何帮助，将不胜感激。谢谢! 最佳答案无论Rails是什么，几乎所有Web应用程序都有您的要求，大多数现代Web应用程序都需要相互通信。但是有一个小小的理解需要你坚持下去，网站不应直接访问彼此
ruby - 无法运行 Rails 2.x 应用程序 - 2
我尝试运行2.x应用程序。我使用rvm并为此应用程序设置其他版本的ruby:$rvmuseree-1.8.7-head我尝试运行服务器，然后出现很多错误:$script/serverNOTE:Gem.source_indexisdeprecated,useSpecification.Itwillberemovedonorafter2011-11-01.Gem.source_indexcalledfrom/Users/serg/rails_projects_terminal/work_proj/spohelp/config/../vendor/rails/railties/lib/r
ruby-on-rails - Rails 应用程序中的 Rails : How are you using application_controller. rb 是新手吗？ - 2
刚入门rails，开始慢慢理解。有人可以解释或给我一些关于在application_controller中编码的好处或时间和原因的想法吗？有哪些用例。您如何为Rails应用程序使用应用程序Controller？我不想在那里放太多代码，因为据我了解，每个请求都会调用此Controller。这是真的？最佳答案 ApplicationController实际上是您应用程序中的每个其他Controller都将从中继承的类(尽管这不是强制性的)。我同意不要用太多代码弄乱它并保持干净整洁的态度，尽管在某些情况下ApplicationContr
ruby-on-rails - 如何在我的 Rails 应用程序 View 中打印 ruby 变量的内容？ - 2
我是一个Rails初学者，但我想从我的RailsView(html.haml文件)中查看Ruby变量的内容。我试图在ruby中打印出变量(认为它会在终端中出现)，但没有得到任何结果。有什么建议吗？我知道Rails调试器，但更喜欢使用inspect来打印我的变量。最佳答案您可以在View中使用puts方法将信息输出到服务器控制台。您应该能够在View中的任何位置使用Haml执行以下操作:-puts@my_variable.inspect 关于ruby-on-rails-如何在我的R
ruby - 如何根据特征实现 FactoryGirl 的条件行为 - 2
我有一个用户工厂。我希望默认情况下确认用户。但是鉴于unconfirmed特征，我不希望它们被确认。虽然我有一个基于实现细节而不是抽象的工作实现，但我想知道如何正确地做到这一点。factory:userdoafter(:create)do|user,evaluator|#unwantedimplementationdetailshereunlessFactoryGirl.factories[:user].defined_traits.map(&:name).include?(:unconfirmed)user.confirm!endendtrait:unconfirmeddoenden
ruby - 分布式事务和队列，ruby，erlang，scala - 2
我有一个涉及多台机器、消息队列和事务的问题。因此，例如用户点击网页，点击将消息发送到另一台机器，该机器将付款添加到用户的帐户。每秒可能有数千次点击。事务的所有方面都应该是容错的。我以前从未遇到过这样的事情，但一些阅读表明这是一个众所周知的问题。所以我的问题。我假设安全的方法是使用两阶段提交，但协议(protocol)是阻塞的，所以我不会获得所需的性能，我是否正确？我通常写Ruby，但似乎Redis之类的数据库和Rescue、RabbitMQ等消息队列系统对我的帮助不大——即使我实现某种两阶段提交，如果Redis崩溃，数据也会丢失，因为它本质上只是内存。所有这些让我开始关注erlang和
ruby-on-rails - 如何在 Gem 中获取 Rails 应用程序的根目录 - 2
是否可以在应用程序中包含的gem代码中知道应用程序的Rails文件系统根目录？这是gem来源的示例:moduleMyGemdefself.included(base)putsRails.root#returnnilendendActionController::Base.send:include,MyGem谢谢，抱歉我的英语不好最佳答案我发现解决类似问题的解决方案是使用railtie初始化程序包含我的模块。所以，在你的/lib/mygem/railtie.rbmoduleMyGemclassRailtie使用此代码，您的模块将在
世界前沿3D开发引擎HOOPS全面讲解——集3D数据读取、3D图形渲染、3D数据发布于一体的全新3D应用开发工具 - 2
无论您是想搭建桌面端、WEB端或者移动端APP应用，HOOPSPlatform组件都可以为您提供弹性的3D集成架构，同时，由工业领域3D技术专家组成的HOOPS技术团队也能为您提供技术支持服务。如果您的客户期望有一种在多个平台（桌面/WEB/APP，而且某些客户端是“瘦”客户端）快速、方便地将数据接入到3D应用系统的解决方案，并且当访问数据时，在各个平台上的性能和用户体验保持一致，HOOPSPlatform将帮助您完成。利用HOOPSPlatform，您可以开发在任何环境下的3D基础应用架构。HOOPSPlatform可以帮您打造3D创新型产品，HOOPSSDK包含的技术有：快速且准确的CAD
叮咚买菜基于 Apache Doris 统一 OLAP 引擎的应用实践 - 2
导读：随着叮咚买菜业务的发展，不同的业务场景对数据分析提出了不同的需求，他们希望引入一款实时OLAP数据库，构建一个灵活的多维实时查询和分析的平台，统一数据的接入和查询方案，解决各业务线对数据高效实时查询和精细化运营的需求。经过调研选型，最终引入ApacheDoris作为最终的OLAP分析引擎，Doris作为核心的OLAP引擎支持复杂地分析操作、提供多维的数据视图，在叮咚买菜数十个业务场景中广泛应用。作者｜叮咚买菜资深数据工程师韩青叮咚买菜创立于2017年5月，是一家专注美好食物的创业公司。叮咚买菜专注吃的事业，为满足更多人“想吃什么”而努力，通过美好食材的供应、美好滋味的开发以及美食品牌的孵

链队列的实现及应用

源程序

运行结果

有关链队列的实现及应用的更多相关文章

随机推荐