数据结构和算法

当前位置:首页>数据结构和算法

数据结构

时间:2019-04-17   访问量:8

数据结构具体指同一类数据元素中,各元素之间的相互关系,包括三个组成成分,数据的逻辑结构数据的存储结构数据运算结构

数据(Data)

数据的逻辑结构

数据的存储结构

由数据元素之间的关系在计算机中有两种不同的表示方法——顺序表示和非顺序表示,从则导出两种储存方式,顺序储存结构和链式储存结构

数据的逻辑结构和物理结构是密不可分的两个方面,一个算法的设计取决于所选定的逻辑结构,而算法的实现依赖于所采用的存储结构

常见数据结构

数组

把具有相同类型的若干变量按有序的形式组织起来。这些按序排列的同类数据元素的集合称为数组

两个特点:相同类型、有序

这个数组不等于PHP的数组。PHP数组本质是一个哈希表。通过数组实现

img

链表

链表是一种物理存储单元上非连续、非顺序的存储结构 ,由一系列结点(链表中每一个元素称为结点)组成,结点可以在运行时动态生成。每个结点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域。 PHP SPL标准库中有SplDoublyLinkedList (双向链表)

img

链表的操作:插入、遍历、查找、删除

$dlist=new SplDoublyLinkedList();
$dlist->push(1);//追加到末端$dlist->add(1,3);//在index=1添加//遍历 for($dlist->rewind();$dlist->valid();$dlist->next()){  echo $dlist->current()."<br/>";
 }

是只能在某一端插入和删除的特殊[线性表]。它按照先进后出的原则存储数据,先进入的数据被压入栈底,最后的数据在栈顶,需要读数据的时候从栈顶开始弹出数据(最后一个数据被第一个读出来)。

PHP中SPL标准库中有对应的实现 SplStack

栈的两个操作 出栈pop、入栈push

$q = new SplStack();
$q[] = 1;
$q[] = 2;
$q[] = 3;
$q->push(4);
$q->push(5);echo $q->pop();//5

队列

一种特殊的[线性表],它只允许在表的[前端](front)进行删除操作,而在表的末端(rear)进行插入操作。进行插入操作的端称为队尾,进行删除操作的端称为队头。队列是按照“先进先出”或“后进后出”FIFO的原则组织数据的。队列中没有元素时,称为空队列。

PHP SPL标准库中有SplQueue

队列的两个操作 入队列enqueue、出队列dequeue

$q = new SplQueue();
$q->enqueue(array("FooBar", "foo"));
$q->enqueue(array("FooBar", "bar"));
$q->enqueue(array("FooBar", "msg", "Hi there!"));

$f = $q->dequeue();

它是由n(n>=1)个有限节点组成一个具有层次关系的[集合]。是一对多的关系。

(1)有且仅有一个结点 K0,他对于关系N来说没有前驱,称K0为树的根结点。简称为根(root))。 

(2)除K0外,K中的每个结点,对于关系N来说有且仅有一个前驱。

(3)K中各结点,对关系N来说可以有m个后继(m>=0)。

img

1. 二叉树

除了叶以外的结点,都有两个子。(叶就是在它和根的路径上,没有比他更远的结点了,也可以理解为,只有一个结点和它相连,并且它不是根,那么他就是叶)

2. 二叉搜索树

二叉搜索树,也称有序二叉树,排序二叉树,是指一棵空树或者具有下列性质的二叉树:

  1. 若任意节点的左子树不空,则左子树上所有结点的值均小于它的根结点的值;

  2. 若任意节点的右子树不空,则右子树上所有结点的值均大于它的根结点的值;

  3. 任意节点的左、右子树也分别为二叉查找树。

  4. 没有键值相等的节点。

3. 树的遍历

堆是一种特殊的树形数据结构,每个结点都有一个值。通常我们所说的堆的数据结构,是指二叉堆。堆的特点是根结点的值最小(或最大),且根结点的两个子树也是一个堆。 比如我们查找top N 就可以用堆

img

PHP中有堆的实现SplMaxHeap (大端堆)、SplMaxHeap (小端堆)

散列表【HashTable】

K=>V结构。若结构中存在关键字和K相等的记录,则必定在f(K)的存储位置上。由此,不需比较便可直接取得所查记录。称这个对应关系f为散列函数(Hash function),按这个思想建立的表为[散列表]。

冲突

若 key1 ≠ key2 ,而 f(key1) = f(key2),这种情况称为冲突(Collision)。

构造哈希函数

常见的构造哈希表的方法有 5 种:

(1)直接定址法

说白了,就是小学时学过的一元一次方程

即 f(key) = a * key + b。其中,a和b 是常数。

(2)数字分析法

假设关键字是R进制数(如十进制)。并且哈希表中可能出现的关键字都是事先知道的,则可选取关键字的若干数位组成哈希地址。

选取的原则是使得到的哈希地址尽量避免冲突,即所选数位上的数字尽可能是随机的。

(3)平方取中法

取关键字平方后的中间几位为哈希地址。通常在选定哈希函数时不一定能知道关键字的全部情况,仅取其中的几位为地址不一定合适;

而一个数平方后的中间几位数和数的每一位都相关, 由此得到的哈希地址随机性更大。取的位数由表长决定。

(4)除留余数法

取关键字被某个不大于哈希表表长 m 的数 p 除后所得的余数为哈希地址。

即 f(key) = key % p (p ≤ m)

这是一种最简单、最常用的方法,它不仅可以对关键字直接取模,也可在折叠、平方取中等运算之后取模。

注意:p的选择很重要,如果选的不好,容易产生冲突。根据经验,一般情况下可以选p为素数

冲突解决

1)开放定址法

如果两个数据元素的哈希值相同,则在哈希表中为后插入的数据元素另外选择一个表项。 当程序查找哈希表时,如果没有在第一个对应的哈希表项中找到符合查找要求的数据元素,程序就会继续往后查找,直到找到一个符合查找要求的数据元素,或者遇到一个空的表项

2)拉链法

将哈希值相同的数据元素存放在一个链表中,在查找哈希表的过程中,当查找到这个链表时,必须采用线性查找方法。在这种方法中,哈希表中每个单元存放的不再是记录本身,而是相应同义词单链表的头指针。

图是由结点的有穷集合V和边的集合E组成。其中,为了与树形结构加以[区别],在图结构中常常将结点称为顶点,边是顶点的有序偶对,若两个顶点之间存在一条边,就表示这两个顶点具有相邻关系。

2.PNG-64.8kB

学习资料:


上一篇:数组

下一篇:排序算法-冒泡排序

在线咨询

点击这里给我发消息 售前咨询专员

点击这里给我发消息 售后服务专员

在线咨询

免费通话

24小时免费咨询

请输入您的联系电话,座机请加区号

免费通话

微信扫一扫

微信联系
返回顶部