php双向数据结构 php 结构体
数据结构— 循环链表、双向(循环)链表
链表的两头连接,形成了一个环状链表,称为循环链表。
创新互联坚持“要么做到,要么别承诺”的工作理念,服务领域包括:成都做网站、网站建设、企业官网、英文网站、手机端网站、网站推广等服务,满足客户于互联网时代的尉犁网站设计、移动媒体设计的需求,帮助企业找到有效的互联网解决方案。努力成为您成熟可靠的网络建设合作伙伴!
约瑟夫环问题,是一个经典的循环链表问题,题意是:已知 n 个人(以编号1,2,3,…,n分别表示)围坐在一张圆桌周围,从编号为 k 的人开始顺时针报数,数到 m 的那个人出列;他的下一个人又从 1 还是顺时针开始报数,数到 m 的那个人又出列;依次重复下去,要求找到最后出列的那个人。
例如有 5 个人,要求从编号为 3 的人开始,数到 2 的那个人出列:
出列顺序依次为:
编号为 3 的人开始数 1,然后 4 数 2,所以 4 先出列;
4 出列后,从 5 开始数 1,1 数 2,所以 1 出列;
1 出列后,从 2 开始数 1,3 数 2,所以 3 出列;
3 出列后,从 5 开始数 1,2 数 2,所以 2 出列;
最后只剩下 5 自己,所以 5 出列。
循环链表和动态链表唯一不同在于它的首尾连接,这也注定了在使用循环链表时,附带的最多的操作就是遍历链表。在遍历的过程中,尤其要注意循环链表虽然首尾相连,但并不表示该链表没有第一个节点和最后一个结点。所以,不要随意改变头指针的指向。
整个链表只能单方向从表头访问到表尾,这种结构的链表统称为 “单向链表”或“单链表”。
如果算法中需要频繁地找某结点的前趋结点,单链表的解决方式是遍历整个链表,增加算法的时间复杂度,影响整体效率。
为了快速便捷地解决这类问题,在单向链表的基础上,给各个结点额外配备一个指针变量,用于指向每个结点的直接前趋元素。这样的链表被称为“双向链表”或者“双链表”。
双向链表中的结点有两个指针域,一个指向直接前趋,一个指向直接后继。(链表中第一个结点的前趋结点为NULL,最后一个结点的后继结点为NULL)
结点的具体构成:
双向链表创建的过程中,每一个结点需要初始化数据域和两个指针域,一个指向直接前趋结点,另一个指向直接后继结点。
创建一个双向链表line(1,2,3):
比如在(1,2,3)中插入一个结点 4,变成(1,4,2,3)。
实现效果图:
在双向链表中插入数据时,首先完成图中标注为 1 的两步操作,然后完成标注为 2 的两步操作;反之,如果先完成 2,就无法通过头指针访问结点 2,需要额外增设指针,虽然能实现,但较前一种麻烦。
双链表删除结点时,直接遍历链表,找到要删除的结点,然后利用该结点的两个指针域完成删除操作。
在(1,4,2,3)中删除结点 2:
双向链表的查找操作和单链表的实现方法完全一样,从链表的头结点或者首元结点开始遍历,这里不做过多解释。
更改链表中某结点的数据域的操作是在查找的基础上完成的。通过遍历找到存储有该数据元素的结点后,直接更改其数据域就可以。
其实就是双向链表和循环链表的结合体
例如:约瑟夫环问题其实还可以这样玩:如果顺时针报数,有人出列后,顺时针找出出列位置的下一个人,开始反方向(也就是逆时针)报数,有人出列后,逆时针找出出列位置的下一个人,开始顺时针报数。依次重复,直至最后一个出列。
有兴趣可以自行尝试,这里就不再分析了,因为本质就是双向链表和循环链表。
如何使用php实现一个双向队列的数据结构有几种方式
不建议直接用php来做队列,php的array操作虽然勉强能做伪队列,但问题也来了,如果是大量的数据呢?php会不会内存问题直接挂了?
建议:测试的话用用还凑合,但真正去用的话双向队列,用redis的list类型吧,可以满足你的需求,同时数量级上也不是问题,单向队列
httpsqs,rabbitmq等
再看看别人怎么说的。
PHP 数据结构队列(SplQueue)和优先队列(SplPriorityQueue)简单使用实例
队列这种数据结构更简单,就像我们生活中排队一样,它的特性是先进先出(FIFO)。
PHP
SPL中SplQueue类就是实现队列操作,和栈一样,它也可以继承双链表(SplDoublyLinkedList)轻松实现。
SplQueue类摘要如下:
SplQueue简单使用如下:
复制代码
代码如下:
$queue
=
new
SplQueue();
/**
*
可见队列和双链表的区别就是IteratorMode改变了而已,栈的IteratorMode只能为:
*
(1)SplDoublyLinkedList::IT_MODE_FIFO
|
SplDoublyLinkedList::IT_MODE_KEEP
(默认值,迭代后数据保存)
*
(2)SplDoublyLinkedList::IT_MODE_FIFO
|
SplDoublyLinkedList::IT_MODE_DELETE
(迭代后数据删除)
*/
$queue-setIteratorMode(SplDoublyLinkedList::IT_MODE_FIFO
|
SplDoublyLinkedList::IT_MODE_DELETE);
//SplQueue::enqueue()其实就是
SplDoublyLinkedList::push()
$queue-enqueue('a');
$queue-enqueue('b');
$queue-enqueue('c');
//SplQueue::dequeue()其实就是
SplDoublyLinkedList::shift()
print_r($queue-dequeue());
foreach($queue
as
$item)
{
echo
$item
.
PHP_EOL;
}
print_r($queue);
而优先队列SplPriorityQueue是基于堆(后文介绍)实现的。
SplPriorityQueue的类摘要如下:
SplPriorityQueue简单使用:
$pq
=
new
SplPriorityQueue();
$pq-insert('a',
10);
$pq-insert('b',
1);
$pq-insert('c',
8);
echo
$pq-count()
.PHP_EOL;
//3
echo
$pq-current()
.
PHP_EOL;
//a
/**
*
设置元素出队模式
*
SplPriorityQueue::EXTR_DATA
仅提取值
*
SplPriorityQueue::EXTR_PRIORITY
仅提取优先级
*
SplPriorityQueue::EXTR_BOTH
提取数组包含值和优先级
*/
$pq-setExtractFlags(SplPriorityQueue::EXTR_DATA);
while($pq-valid())
{
print_r($pq-current());
//a
c
b
$pq-next();
}
PHP数据结构和算法学习求指点
C语言是所有高级编程语言的入门语言,所以数据结构中算法一般都使用C语言来表示,这样大家都能看懂。学习数据结构和算法是与语言无关的,C语言只是它实现的一种方式,不用太在乎的。建议你把C语言的基础知识学习一下,这样看起来就不会太累了。
数据结构算法在php编程中的作用?
数据结构是在整个计算机科学与技术领域上广泛被使用的术语。它用来反映一个数据的内部构成,即一个数据由那些成分数据构成,以什么方式构成,呈什么结构。数据结构有逻辑上的数据结构和物理上的数据结构之分。逻辑上的数据结构反映成分数据之间的逻辑关系,而物理上的数据结构反映成分数据在计算机内部的存储安排。数据结构是数据存在的形式。 数据结构是信息的一种组织方式,其目的是为了提高算法的效率,它通常与一组算法的集合相对应,通过这组算法集合可以对数据结构中的数据进行某种操作。
使用php实现的基本的数据结构和算法,什么二叉树、二叉搜索树、AVL树、B树、链表和常见排序、搜索算法等等,而且全部是使用面向对象来实现的,确是是很强。
php有什么数据结构可以实现双向索引查询
数组就是典型的数据结构了,使用数组操作函数,就可以实现单向和多向队列了。 操作函数有: array_shift array_unshift array_push array_pop
本文题目:php双向数据结构 php 结构体
文章起源:http://myzitong.com/article/hhceod.html