《StorageStructurePHP数据结构》由会员分享，可在线阅读，更多相关《StorageStructurePHP数据结构（62页珍藏版）》请在金锄头文库上搜索。
1、PHP数据结构,原理和算法分析 李光明，2014年8月,2,主要内容,数据结构基本概念 算法和算法的时间复杂度 常见结构：线性表、 队列、堆栈、树 递归和循环的相互转化 常见查找和排序算法 分解法算法设计技巧 “剥洋葱”法的算法设计技巧 数据结构与算法的综合运用,3,4,什么是数据结构呢？,数据：描述客观事物的符号，如文本、图片、视频 数据元素：组成数据的，有一定意义的基本单位 数据项：一个数据元素可以由若干数据项组成 数据对象：性质相同的数据元素的集合 数据结构：数据结构是计算机用来组织和存储数据的方式! 具体定义:数据结构是指相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素之
2、间的关系组成,数据结构术语图示,数据结构包含的内容,9,数据的逻辑结构,10,数据的物理存储结构,顺序存储结构 顺序存储结构（Sequence Storage Structure）是指在一块连续的存储区域中一个接着一个地存放数据。顺序存储方式把逻辑上相邻的结点存储在物理位置相邻的存储单元中，节点间的逻辑关系由存储单元的邻接关系来体现。一般采用数组或结构数组来描述。线性存储方式主要用于线性逻辑结构的数据存放，而对于图和树等非线性逻辑结构则不适用。 链式存储结构 链式存储结构（Linked Storage Structure）比较灵活，其不要求逻辑上相邻的节点在物理位置上相邻，节点间的逻辑关系由附
3、加的引用字段表示。一个结点的引用字段往往指向下一个节点的存放位置。 索引存储结构 索引存储结构是采用附加的索引表的方式来存储节点信息。索引表由若干索引项组成。索引存储结构中索引项的一般形式为：（关键字、地址）。其中，关键字是能够唯一标识一个节点的数据项。 散列（或哈希）存储结构 散列存储结构是根据节点的关键字直接计算出该节点的存储地址的一种存储方式。,11,运算的效率,判断程序运算效率的方式是什么? 1. 做一个n次的循环, 记录其时间 2. 做一个n次的循环, 记录其次数 3. 用一个计算方式标记这个算法效率的好坏,12,如下两个求和算法哪个好？,O(n),O(1),以下加密算法的执行次数是
4、？,时间复杂度,1. 一般情况下，算法的基本操作重复执行的次数是模块n的某一个函数T（n） 注: 如果一个循环n次的for语句 , 如果里面有3条赋值语句,那么 总执行次数 就是 3n ,所以这个函数 T(n) 就是循环次数 , T(n) = 3n ,语句的执行次数(频度) * 单位执行时间 就是总执行时间 2. 从T(n) 中找到 同数量级(同阶) 函数记作 f(n) ,例如 T(n) = 3n 的同数量级的函数 f(n) = n 注: 如果T(n) = n3 + n2 + n ,则f(n) = n3 3. 这个时候我们就能够计算出时间复杂度了 T(n) = O(f(n) 具体怎么算呢 用
5、T(n) / f(n) 然后求极限值 - (n3 + n2 + n) / n3 = 1+1/n +1/n2 求极限值 是一个常数 1 ,那么时间复杂度就是 O(f(n) 也就是 O(n3),简单推导时间复杂度,用常数1取代运行时间中的所有加法常数 在修改后的运行次数函数中，只保留最高阶项 如果最高阶存在且不是1，则去除它的系数 得到的结果就是大 O 阶 简单说就是最高阶的执行次数,常见的时间复杂度,以下算法的时间复杂度是？,以下算法的时间复杂度是？,以下实体在程序中如何存放？,线性表的特点,定义：零个或多个数据元素的有限序列 除首尾外，均只有一个直接前驱和直接后继 一个数组元素可以有若干数据项
6、组成 线性表有顺序存储和链式存储两种存储结构 堆栈、队列、串、数组等都是线性表,单链表,A,B,C,D,E,head,data ：数据域，存放结点的值。 next ：指针域，存放结点的直接后继的地址。,单链表,插入节点 : 头插/尾插 也叫前插/后插 ,其实就是head 所指向节点不一样,当然他们的时间复杂度也不一样 删除节点 : 先找到要删除的节点位置,将父节点的next 指向其子节点,然后删除该节点 查询节点 : 从head开始一级一级的往下找 编辑节点 : 从head开始一级一级的往下找,找到后编辑器内容 节点排序 :后面说排序算法 练习 : 用php实现单链表,双向链表,A,B,C,D
7、,E,head,data ：数据域，存放结点的值。 prev ：指针域，存放结点的直接前驱的地址。 next ：指针域，存放结点的直接后继的地址。,双向链表,与单链表操作很类似 插入节点 : 头插/尾插 也叫前插/后插 ,其实就是head 所指向节点不一样,当然他们的时间复杂度也不一样 删除节点 : 先找到要删除的节点位置,将父节点的next 指向其子节点,然后删除该节点 查询节点 : 从head开始一级一级的往下找 编辑节点 : 从head开始一级一级的往下找,找到后编辑器内容 节点排序 :后面说排序算法,循环单链表,循环单链表,循环单链表是在单链表发展而来, 与单链表不同的是,其末尾节点的
8、next域指向的是head,此时就形成了一个循环一个圈 其他操作方法也是同单链表类似 小练习 : 用php实现循环单链表,27,用循环链表解决“约瑟夫环”问题,一群猴子排成一圈，按1，2，.，n依次编号。然后从第1只开始数，数到第m只,把它踢出圈，从它后面再开始数，再数到第m只，在把它踢出去.，如此不停的进行下去，直到最后只剩下一只猴子为止，那只猴子就叫做大王。要求编程模拟此过程，输入m、n, 输出最后那个大王的编号。,队列,队列,队列（Queue）是只允许在一端进行插入，而在另一端进行删除的运算受限的线性表 （1）允许删除的一端称为队头（Front）。 （2）允许插入的一端称为队尾（Rear
9、）。 （3）当队列中没有元素时称为空队列。 （4）队列亦称作先进先出（First In First Out）的线性表，简称为FIFO表。 队列的修改是依先进先出的原则进行的。新来的成员总是加入队尾（即不允许“加塞“），每次离开的成员总是队列头上的（不允许中途离队），即当前“最老的“成员离队。,队列,一个基本的队列需要实现的操作有哪些? 1. 添加队列节点 (入队) 2. 删除队列节点(出队) 3. 查询队列 4. 队列排序(不需要!) 5. 队列修改 练习,用php实现队列系统,堆栈,堆栈,也可以叫作栈 , 与队列的先进先出相比 ,堆栈是先进后出, 堆栈只有一个口, 添加节点和删除节点都在这一
10、个口 小练习,用php实现堆栈,33,34,35,递归的要点,定义：递归( recursion)就是自调用 使用递归，必须有明确的递归结束条件 理论上递归都可以转为非递归方式 使用递归的必备条件： 可以通过递归调用来缩小问题规模，且新问题与原问题有着相同的形式 存在一种简单情境，可以使递归在简单情境下退出,36,练习：用递归完成下列问题,1+2+3+.+n。 求n个整数的平均值。 一般而言，兔子在出生两个月后，就有繁殖能力，一对兔子每个月能生出一对小兔子来。如果所有兔都不死，那么一年以后可以繁殖多少对兔子？,37,递归和循环对比,38,练习：不用递归完成下列问题,1+2+3+.+n。 求n个整
11、数的平均值。 一般而言，兔子在出生两个月后，就有繁殖能力，一对兔子每个月能生出一对小兔子来。如果所有兔都不死，那么一年以后可以繁殖多少对兔子？,树,F,G,R,A,B,C,D,E,树,它是由n（n=1）个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点： 1.每个节点有零个或多个子节点； 2.没有父节点的节点称为根节点； 3.每一个非根节点有且只有一个父节点； 4.除了根节点外，每个子节点可以分为多个不相交的子树； 无序树：树中任意节点的子节点之间没有顺序关系，这种树称为无序树，也称为自由树； 有序树：树中任意节点
12、的子节点之间有顺序关系，这种树称为有序树； 二叉树：每个节点最多含有两个子树的树称为二叉树； 完全二叉树：对于一颗二叉树，假设其深度为d（d1）。除了第d层外，其它各层的节点数目均已达最大值，且第d层所有节点从左向右连续地紧密排列，这样的二叉树被称为完全二叉树； 满二叉树：对于上述的完全二叉树，如果去掉其第d层的所有节点，那么剩下的部分就构成一个满二叉树（此时该满二叉树的深度为d-1）； 霍夫曼树：带权路径最短的二叉树称为哈夫曼树或最优二叉树； B树,特殊形态的二叉树,遍历二叉树,遍历二叉树,（1）前序遍历（DLR），首先访问根结点，然后遍历左子树，最后遍历右子树。简记根-左-右。 （2）中序
13、遍历（LDR），首先遍历左子树，然后访问根结点，最后遍历右子树。简记左-根-右。 （3）后序遍历（LRD），首先遍历左子树，然后遍历右子树，最后访问根结点。简记左-右-根。,练习：遍历二叉树,练习：推导二叉树,已知一颗二叉树的前序遍历序列为ABCDEF，中序遍历序列为CBAEDF，请问这颗二叉树的后序遍历的结果是什么？,练习：实现二叉树,用php实现二叉树,二叉查找树的应用,7,5,1,3,1,7,7,1,5,3,5,1,7,5,3,(a),(b),(c),(d),3,二叉查找树的应用,二叉排序树 二叉排序树（Binary Sort Tree）又称二叉查找树（Binary Search Tre
14、e），亦称二叉搜索树。 它或者是一棵空树；或者是具有下列性质的二叉树： （1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值； （2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值； （3）左、右子树也分别为二叉排序树； 练习: 用php实现二叉查找树,看下图找不同点,顺序表查找算法,“顺序查找”也叫线性查找，它从第一个记录开始，逐个进行比较，是最基本的查找技术。,折半查找(Binary Search),算法思想： 用Low、High和Mid表示待查找区间的下界、上界和中间位置 ； 取中间位置 Mid= (Low+High)/2 ； 比较中间位置记录的关键字与给定的K值：
15、相等：查找成功； 大于：待查记录在区间的前半段，修改上界： High=Mid-1，转1 ； 小于：待查记录在区间的后半段，修改下界：Low=Mid+1 ，转1 ； 直到越界(LowHigh)，查找失败。,折半查找优化-“插值查找”,Mid,查找的关键字和最大最小记录进行了比较 核心在于差值的计算公式 适用于关键字分布比较均匀的查找表 插值查找平均速度要优于折半查找,腾讯编程面试题,我们碰到了大麻烦，一个新来的传教士惹恼了上帝，上帝很愤怒，要求我们把圣经（bible.txt）背熟，直至他说哪个单词，我们就要飞快的回答出这个单词在第几行第几个单词位置。听说你是个优秀的程序员，那么帮助我们完成这个不
16、可能的任务吧。 要求： bible.txt，98版本英文圣经一本 输入部分要求如下：php search.php 输出部分如下：单词 1,2 2,4 5,6 表示：此单词在1行2列（第二个单词），2行4列. 说明： 此文本4MB之巨. 单词的含义：由英文字母（大小写），数字（0-9）组成的串 提供给你的机器内存只有1G，而且，很不幸的，其中700M用来做了别的 算法复杂度要求不能大于O（N2）（就是N的平方）,搜索引擎之基石“倒排索引”,1. Books and friends should be few but good. 2. A good book is a good friend.,排序的几个要点,什么叫做排序？ 内排序和外排序 什么是稳定的排序算法？ 正序和逆序比较次数是一样的 评价排序算法的标准有：执行时间和所需的辅助空间，其次是算法的稳定性,冒泡排序,例：设有关键字序列为：23, 38, 2
