C语言单链队列的表示与实现实例详解

1.概述:

C语言的队列(queue),是指先进先出(FIFO, First-In-First-Out)的线性表。在具体应用中通常用链表或者数组来实现。队列只允许在后端(称为rear)进行插入操作,在前端(称为front)进行删除操作。

单链队列使用链表作为基本数据结果,因此不存在伪溢出的问题,队列长度也没有限制。但插入和读取的时间代价会比较高

2.实例代码:

/* 单链队列——队列的链式存储结构 */
typedef struct QNode
{
 QElemType data;
 struct QNode *next;
}QNode,*QueuePtr;
typedef struct
{
 QueuePtr front,rear; /* 队头、队尾指针 */
}LinkQueue;
/* 链队列的基本操作(9个) */
void InitQueue(LinkQueue *Q)
{ /* 构造一个空队列Q */
 Q->front=Q->rear=malloc(sizeof(QNode));
 if(!Q->front)
  exit(OVERFLOW);
 Q->front->next=NULL;
}
void DestroyQueue(LinkQueue *Q)
{ /* 销毁队列Q(无论空否均可) */
 while(Q->front)
 {
  Q->rear=Q->front->next;
  free(Q->front);
  Q->front=Q->rear;
 }
}
void ClearQueue(LinkQueue *Q)
{ /* 将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);
 }
}
Status QueueEmpty(LinkQueue Q)
{ /* 若Q为空队列,则返回TRUE,否则返回FALSE */
 if(Q.front->next==NULL)
  return TRUE;
 else
  return FALSE;
}
int QueueLength(LinkQueue Q)
{ /* 求队列的长度 */
 int i=0;
 QueuePtr p;
 p=Q.front;
 while(Q.rear!=p)
 {
  i++;
  p=p->next;
 }
 return i;
}
Status GetHead_Q(LinkQueue Q,QElemType *e)
{ /* 若队列不空,则用e返回Q的队头元素,并返回OK,否则返回ERROR */
 QueuePtr p;
 if(Q.front==Q.rear)
  return ERROR;
 p=Q.front->next;
 *e=p->data;
 return OK;
}
void EnQueue(LinkQueue *Q,QElemType e)
{ /* 插入元素e为Q的新的队尾元素 */
 QueuePtr p= (QueuePtr)malloc(sizeof(QNode));
 if(!p) /* 存储分配失败 */
  exit(OVERFLOW);
 p->data=e;
 p->next=NULL;
 Q->rear->next=p;
 Q->rear=p;
}
Status DeQueue(LinkQueue *Q,QElemType *e)
{ /* 若队列不空,删除Q的队头元素,用e返回其值,并返回OK,否则返回ERROR */
 QueuePtr p;
 if(Q->front==Q->rear)
  return ERROR;
 p=Q->front; /* 指向头结点 */
 *e=p->data;
 Q->front=p->next; /* 摘下头节点 */
 if(Q->rear==p)
  Q->rear=Q->front;
 free(p);
 return OK;
}
void QueueTraverse(LinkQueue Q,void(*vi)(QElemType))
{ /* 从队头到队尾依次对队列Q中每个元素调用函数vi() */
 QueuePtr p;
 p=Q.front->next;
 while(p)
 {
  vi(p->data);
  p=p->next;
 }
 printf("\n");
}
时间: 2014-07-05

C语言 数据结构中求解迷宫问题实现方法

C语言 数据结构中求解迷宫问题实现方法 在学习数据结构栈的这一节遇到了求迷宫这个问题,拿来分享一下~ 首先求迷宫问题通常用的是"穷举求解" 即从入口出发,顺某一方向试探,若能走通,则继续往前走,否则原路返回,换另一个方向继续试探,直至走出去. 我们可以先建立一个8*8的迷宫其中最外侧为1的是墙 int mg[M+2][N+2]={ {1,1,1,1,1,1,1,1,1,1}, {1,0,0,1,0,0,0,1,0,1}, {1,0,0,1,0,0,0,1,0,1}, {1,0,0,0,

C++实现迷宫算法实例解析

本文以实例形式描述了C++实现迷宫算法.本例中的迷宫是一个矩形区域,它有一个入口和一个出口.在迷宫的内部包含不能穿越的墙或障碍.障碍物沿着行和列放置,它们与迷宫的矩形边界平行.迷宫的入口在左上角,出口在右下角 本实例迷宫算法的功能主要有: 1.自动生成10*10迷宫图 2.判断是否有迷宫出口,并且画出路线图 具体实现代码如下: # include <iostream> # include <list> # include <sys/timeb.h> # include

C++实现随机生成迷宫地牢

可以用这个地图核心做成一个无限迷宫类的游戏 main.cpp // Author: FreeKnight 2014-09-02 #include "stdafx.h" #include <iostream> #include <string> #include <random> #include <cassert> /* 简单逻辑流程描述: 将整个地图填满土 在地图中间挖一个房间出来 选中某一房间(如果有多个的话)的墙壁 确定要修建某种新

详解数据结构C语言实现之循环队列

本文讲的是循环队列,首先我们必须明白下面几个问题 循环队列的基础知识 1.循环队列需要几个参数来确定 循环队列需要2个参数,front和rear 2.循环队列各个参数的含义 (1)队列初始化时,front和rear值都为零: (2)当队列不为空时,front指向队列的第一个元素,rear指向队列最后一个元素的下一个位置: (3)当队列为空时,front与rear的值相等,但不一定为零: 3.循环队列入队的伪算法 (1)把值存在rear所在的位置: (2)rear=(rear+1)%maxsize

深入浅析C语言中堆栈和队列

1.堆和栈 (1)数据结构的堆和栈 堆栈是两种数据结构. 栈(栈像装数据的桶或箱子):是一种具有后进先出性质的数据结构,也就是说后存放的先取,先存放的后取.这就如同要取出放在箱子里面底下的东西(放入的比较早的物体),首先要移开压在它上面的物体(放入的比较晚的物体). 堆(堆像一棵倒过来的树):是一种经过排序的树形数据结构,每个结点都有一个值.通常所说的堆的数据结构,是指二叉堆.堆的特点是根结点的值最小(或最大),且根结点的两个子树也是一个堆.由于堆的这个特性,常用来实现优先队列,堆的存取是随意,

优先队列(priority_queue)的C语言实现代码

优先队列(priority_queue)和一般队列(queue)的函数接口一致,不同的是,优先队列每次出列的是整个队列中最小(或者最大)的元素. 本文简要介绍一种基于数组二叉堆实现的优先队列,定义的数据结构和实现的函数接口说明如下: 一.键值对结构体:KeyValue 复制代码 代码如下: // =============KeyValue Struct==================================typedef struct key_value_struct KeyValu

C++ 自定义栈实现迷宫求解

C++ 自定义栈实现迷宫求解 一:迷宫求解 是一个锻炼我们的算法求解能力的问题,它的实现方法有很多:今天我们就介绍其中的用栈求解的方法. 二:什么是栈: 大家应该都有往袋子里装东西的经历,在往袋子里装满东西之后,当我们去取的时候,总是先从最后放进去的东西的地方去取.也就是后进先出(FILO).虽然栈的单向性用起来会没有链表那样可以在任意位置对数据进行操作,但是正因为如此栈也带来了很大的方便. 三:迷宫求解 现在我们要在下面的迷宫寻找一条可行的路径 1 1 1 1 1 1 1 1 1 1 1 0

使用C/C++语言生成一个随机迷宫游戏

迷宫相信大家都走过,毕竟书本啊啥啥啥的上面都会有迷宫,主要就是考验你的逻辑思维.那么我们学习C/C++也是需要学习到逻辑思维方式的,那今天我就来分享一下,如何用C/C++打造一个简单的随机迷宫游戏.(代码的话我只截取了如何创建迷宫的代码,如果想要全套代码的话可以加群:558502932,群内有很多C/C++学习资料提供学习,大家一起交流进步) 完整版的迷宫游戏效果如下: 代码如下: //创建迷宫 void CreateMaze(int x,int y) { //定义4个方向 int dir[4]

C语言使用广度优先搜索算法解决迷宫问题(队列)

本文实例讲述了C语言使用广度优先搜索算法解决迷宫问题.分享给大家供大家参考,具体如下: 变量 head 和 tail 是队头和队尾指针, head 总是指向队头, tail 总是指向队尾的下一个元素.每个点的 predecessor 成员也是一个指针,指向它的前趋在 queue 数组中的位置.如下图所示: 广度优先是一种步步为营的策略,每次都从各个方向探索一步,将前线推进一步,图中的虚线就表示这个前线,队列中的元素总是由前线的点组成的,可见正是队列先进先出的性质使这个算法具有了广度优先的特点.广

C++ 迷宫游戏实现代码

C++ 迷宫游戏实现代码 题目 通过让游戏角色自动寻找迷宫出口,走出迷宫,来练习C++面向对象之封装的基础知识.迷宫图如下所示,其中X表示墙. 1.程序分析 走出去的原理:遵循右手规则或左手规则.右手扶墙走,就会走出迷宫,反之,亦然. step1 创建迷宫类,打印出迷宫地图. step2 创建走迷宫的人的类. 2.程序实现 MazeMap.h #ifndef MAZEMAP_H #define MAZEMAP_H #include <iostream> #include <Windows

使用C语言来解决循环队列问题的方法

题目描述: 大家都知道数据结构里面有一个结构叫做循环队列.顾名思义,这是一个队列,并且是循环的.但是现在,淘气的囧哥给这个循环队列加上了一些规矩,其中有5条指令: (1) Push K, 让元素K进队列. (2) Pop,对头元素出队列. (3) Query K,查找队列中第K个元素,注意K的合法性. (4) Isempty,判断队列是否为空. (5) Isfull,判断队列是否已满. 现在有N行指令,并且告诉你队列大小是M. 输入: 第一行包含两个整数N和M.1<=N,M<=100000.

C语言循环队列的表示与实现实例详解

1.概述: C语言的队列(queue),是先进先出(FIFO, First-In-First-Out)的线性表数据结构.在具体应用中通常用链表或者数组来实现.队列只允许在后端(称为rear)进行插入操作,在前端(称为front)进行删除操作. 循环队列可以更简单的防止伪溢出的发生,但是队列大小是固定的. 2.实例代码: /* 队列的顺序存储结构(循环队列) */ #define MAX_QSIZE 5 /* 最大队列长度+1 */ typedef struct { QElemType *base

Java语言面向对象编程思想之类与对象实例详解

在初学者学Java的时候,面向对象很难让人搞懂,那么今天小编就来为大家把这个思想来为大家用极为简单的方法理解吧. 首先我们来简单的阐述面向对象的思想. 面向对象: 官方的语言很抽象,我们把官方的解释和定义抛开.想想,自己有什么,对!!我们自己有手脚眼口鼻等一系列的器官.来把自己所具有的器官就可以看作我们的属性,自己是不是可以喜怒哀乐和嬉笑怒骂,这些是不是我们的行为,那么自己的具有的属性加自己有的行为就称为一个对象. 注意!!我们自己,一个个体是一个对象,因为,你是你,我是我,我们虽然有相同的,但

C语言实现进制转换函数的实例详解

C语言实现进制转换函数的实例详解 前言: 写一个二进制,八进制,十六进制转换为十进制的函数 要求: 函数有两个参数,参数(1)是要转换为十进制的进制数,参数(2)是标示参数(1)是什么进制(2,8,16标示二进制,八进制,十六进制). 要有报错信息,比如参数是1012,但参数(2)是2,显然是进制数表示有错误. 系统表 pg_proc 存储关于函数的信息 内部函数在编译之前需要先定义在 pg_proc.h 中,src/include/catalog/pg_proc.h CATALOG(pg_pr

C语言中 值传递和指针传递实例详解

C语言中 值传递和指针传递实例详解 在C语言中,函数的参数和返回值的传递方式有两种:值传递和指针传递. 值传递和指针传递初学者总会有一种朦胧的感觉,所以建议把指针传递的概念摸透,才能熟练应用. 值传递示例:x其实是n的一份临时拷贝,所以并不会改变n的值. #include <stdio.h> #include <windows.h> void Fun(int x) { x = 1; } int main() { int n = 2; Fun(n); printf("%d\

python基于mysql实现的简单队列以及跨进程锁实例详解

通常在我们进行多进程应用开发的过程中,不可避免的会遇到多个进程访问同一个资源(临界资源)的状况,这时候必须通过加一个全局性的锁,来实现资源的同步访问(即:同一时间里只能有一个进程访问资源). 举个例子如下: 假设我们用mysql来实现一个任务队列,实现的过程如下: 1. 在Mysql中创建Job表,用于储存队列任务,如下: create table jobs( id auto_increment not null primary key, message text not null, job_s

C语言数据结构树的双亲表示法实例详解

1.树的双亲表示法: 树的双亲表示法 2./* bo6-4.c 树的双亲表存储(存储结构由c6-4.h定义)的基本操作(14个) */ Status InitTree(PTree *T) { /* 操作结果: 构造空树T */ (*T).n=0; return OK; } void DestroyTree() { /* 由于PTree是定长类型,无法销毁 */ } typedef struct { int num; TElemType name; }QElemType; /* 定义队列元素类型

C语言单向链表的表示与实现实例详解

1.概述: C语言中的单向链表(单链表)是链表的一种,其特点是链表的链接方向是单向的,对链表的访问要通过顺序读取从头部开始. 链表中最简单的一种是单向链表,它包含两个域,一个信息域和一个指针域.这个链接指向列表中的下一个节点,而最后一个节点则指向一个空值. 如下图所示: 一个单向链表包含两个值: 当前节点的值和一个指向下一个节点的链接 一个单向链表的节点被分成两个部分.第一个部分保存或者显示关于节点的信息,第二个部分存储下一个节点的地址.单向链表只可向一个方向遍历. 链表最基本的结构是在每个节点

C语言main函数的三种形式实例详解

在C语言中,main()函数有三种形式. 1.无参数 #include <stdio.h> int main(void) { printf("Hello World!\n"); return 0; } 2.有两个参数 习惯上第一个参数是整型argc,保存了外部调用命令的参数个数,第二个参数是指针数组或二级指针argv,以字符串形式保存了与argc对应的参数,如下例子: #include <stdio.h> int main(int argc, char* arg

C语言单循环链表的表示与实现实例详解

1.概述: 对于一个循环链表来说,其首节点和末节点被连接在一起.这种方式在单向和双向链表中皆可实现.要转换一个循环链表,可以选择开始于任意一个节点然后沿着列表的任一方向直到返回开始的节点.再来看另一种方法,循环链表可以被视为"无头无尾".这种列表很利于节约数据存储缓存, 假定你在一个列表中有一个对象并且希望所有其他对象迭代在一个非特殊的排列下. 指向整个列表的指针可以被称作访问指针. 用单向链表构建的循环链表 循环链表中第一个节点之前就是最后一个节点,反之亦然.循环链表的无边界使得在这