【算法导论】链表队列

        链表队列很简单,之前看到过,没有用程序实现。其原理就是遵循FIFO原则,只能从队首取元素,从队尾插入元素,就和排队模型一样。因此只需要队首指针和队尾指针就可以方便的进行队列操作。因为在最近看的图论算法中,经常用到队列,在这里就先用程序实现链表队列。

        和单链表一样,为了运算方便,我们也在队头节点前附加一个头结点,且头指针指向头结点。其链表队列的示意图如下:

下面是具体的程序实现:

#include<stdio.h>
#include<stdlib.h>

typedef struct node//定义节点的结构体
{
	int data;
	struct node *next;
}linklist;

typedef struct//定义链表
{
	linklist *front,*rear;//定义指向节点的头尾指针
}linkqueue;

void SetNull(linkqueue *q)//置空队列(含空的头节点,便于处理)
{
	q->front=(linklist *)malloc(sizeof(linklist));
	q->front->next=NULL;
	q->rear=q->front;
}

int Empty(linkqueue *q)//判断队列是否为空
{
	if(q->front==q->rear)
		return 1;
	else
		return 0;
}

int Front(linkqueue *q)//取出队列的头元素
{
	if(Empty(q))
	{
		printf("queue is empty!");
		return -1;
	}
	else
		return q->front->next->data;//注意有头指针,该指针的下个元素才是第一个元素
}

void ENqueue(linkqueue *q,int x)//进队列
{
	linklist * newnode=(linklist *)malloc(sizeof(linklist));
    q->rear->next=newnode;
	q->rear=newnode;
	q->rear->data=x;
	q->rear->next=NULL;

}

int DEqueue(linkqueue *q)//出队列
{
	int temp;
	linklist *s;
	if(Empty(q))
	{
		printf("queue is empty!");
		return -1;
	}
	else
	{
		s=q->front->next;
		if(s->next==NULL)
		{
			q->front->next=NULL;
			q->rear=q->front;
		}
		else
			q->front->next=s->next;
		temp=s->data;
		return temp;
	}
}

void main()
{
	linkqueue q;//这里是产生队列q,而不是产生指向队列的指正,是为了方便初始化。
	            //如果为指针的话,必须初始化,则头尾指针无法初始化。

	SetNull(&q);//相当于初始化
	ENqueue(&q,2);//将关键字2入队
	ENqueue(&q,3);//将关键字3入队
	ENqueue(&q,4);//将关键字4入队
	DEqueue(&q);//将关键字2出队
	DEqueue(&q);//将关键字3出队
	int a=0;
    a=Front(&q);//取队头元素

	printf("%d\n",a);
}

注:如果程序出错,可能是使用的开发平台版本不同,请点击如下链接: 解释说明

原文:http://blog.csdn.net/tengweitw/article/details/17170743

作者:nineheadedbird

时间: 2024-10-29 11:59:51

【算法导论】链表队列的相关文章

基本数据结构(算法导论)与python

Stack, Queue Stack是后进先出, LIFO, 队列为先进先出, FIFO 在python中两者, 都可以简单的用list实现, 进, 用append() 出, Stack用pop(), Queue用pop(0), pop的时候注意判断len(l)  对于优先队列, 要用到前面讲到的堆 链表和多重数组 这些数据结构在python中就没有存在的价值, 用list都能轻松实现 散列表 为了满足实时查询的需求而产生的数据结构, 查询复杂度的期望是O(1), 最差为O(n) 问题描述, 对

【算法导论】二叉排序树

二叉排序树 二叉排序树的性质:每个节点的左子树中的所有节点的关键字都小于该节点的关键值,而右子树中的所有节点的关键字都大于该节点的关键值.  二叉排序树的构造 二叉排序树的构造是指将一个给定的数据元素构造为相应的二叉排序树. 基本思想为: 对于任给的一组数据元素{ R1, R2, -, Rn } , 可按以下方法来构造二叉排序树:         (1) 令R1为二叉树的根;          (2) 若R2<R1, 令R2为R1左子树的根结点,否则R2为R1右子树的根结点:         (

【算法导论】红黑树

红黑树          在了解红黑树之前,我们必须先了解二叉搜索树(又称二叉排序树,我在上一篇文章中有介绍),因为红黑树是一种特殊的二叉排序树:在每个节点上增加一个存储位来表示节点的颜色,因此红黑树共有五个域:color,key,lchild,rchild,p.          红黑树的提出:一个高度为h的二叉排序树可以实现任何一种基本的动态集合操作:插入.删除.查找等操作,但是当树才高度比较高时,二叉树就会退化成链表.而红黑树能确保在最坏的情况下,基本的动态集合操作的时间为O(logn).

JavaScript中数据结构与算法(二):队列

  这篇文章主要介绍了JavaScript中数据结构与算法(二):队列,队列是只允许在一端进行插入操作,另一个进行删除操作的线性表,队列是一种先进先出(First-In-First-Out,FIFO)的数据结构,需要的朋友可以参考下 队列是只允许在一端进行插入操作,另一个进行删除操作的线性表,队列是一种先进先出(First-In-First-Out,FIFO)的数据结构 队列在程序程序设计中用的非常的频繁,因为javascript单线程,所以导致了任何一个时间段只能执行一个任务,而且还参杂了异步

看算法导论有感(1)——谈谈算法的五性对用户体验的影响

做程序的人,都知道了算法的5性--可行性,健壮性,有穷性,高效性,可读性. 这15个字谁都会说了,但是,你是否真正的思考过这个对当今程序界最最重要的用户体验的思考. 过去,我也没多做思考,但是,看了mit的算法导论公开课,我却是觉得一个好的算法, 确实严格遵从算法算法五性. ①可行性--算法原则上能够精确地运行,而且人们用笔和纸做有限次运算后即可完成.算法肯定要可行的,不可行的话,是一坨shit,一般可行性是与硬件息息相关.比如,10年前,你要先像现在的搜索引擎一样能够做视搜索,做各种各样的算法

【算法导论】排序算法总结

排序算法总结         从六月初开始看算法导论,陆陆续续看了有2个月了,但实际看的时间只有半个月左右.这期间都忙着找导师.期末考试,同时还回家修养了十来天.真正专心的看算法是在离家返校后,由于没有考试和作业的烦恼,天天都沉浸在算法中,感觉效率较高.这段时间学到的东西较多,下面来总结一下:         学到的排序算法可以分为两类:比较排序.非比较排序.(这些排序算法的详细介绍及c程序实现在本文末都给出了链接,欢迎参考与指正!)         比较排序有:插入排序法.合并排序法.堆排序法

【算法导论】最大流算法

最大流问题就是在容量容许的条件下,从源点到汇点所能通过的最大流量. 1 流网络        网络流G=(v, E)是一个有向图,其中每条边(u, v)均有一个非负的容量值,记为c(u, v) ≧ 0.如果(u, v) ∉ E则可以规定c(u, v) = 0.网络流中有两个特殊的顶点,即源点s和汇点t.  与网络流相关的一个概念是流.设G是一个流网络,其容量为c.设s为网络的源点,t为汇点,那么G的流是一个函数f:V×V →R,满足一下性质:    容量限制:对所有顶点对u,v∈V,满足f(u,

【算法导论】排序 (二):堆排序

四.(1)堆排序 第一次听堆排序是在107lab听忠哥讲的,但是没讲怎么实现.那时刚看了数据结 构的二叉树,还以为要通过指针建立二叉树的方式来实现,觉得挺难的. 其实堆排序实现没有想象中 的那么难. "堆"这个词最初是在堆排序中提出来的,但后来就逐渐指"废料收集储存区",就像程 序设计语言Lisp和Java中所提供的设施那样.我们这里的堆数据结构不是废料收集存储区. 堆排序的 运行时间与归并排序一样为O(n lg n),  但是一种原地(in place)排序. (

【算法导论】排序(一)

虽然久闻大名,但第一次接触算法导论,是看了网易公开课MIT的<算法导论>课,记得 第一集就讲到了 插入排序和归并排序. 几个星期前也买了算法导论这本书,准备慢慢啃~ 这星期主要在看前两 部分,除了对于讲渐进时间.递归式分析这些东西感到云里雾里的,其它的都就 感觉越看越有觉得入 迷,果然不愧是一本经典之作 好吧,开始.本文主要是用C++把书中的算法实现,以及一些笔记. 一.插入排序. 插入算法的设计使用的是增量(incremental)方法:在排好子数组A[1..j- 1]后,将 元素A[ j]