php数据结构

主要内容

数据结构定义

注：数据结构是指在一个数据集合中，描述数据与数据之间关系的一种结构；通过该关系可以确定一种数据的排列方式，该排列方式则决定了数据集合的各种性质，性质举例：1）查询，即通过集合的一个数据去寻找集合中的另一个数据；2）新增，即要在该数据集合中插入一个数据时，结构要怎么改变；

数据的逻辑结构和存储结构

注：逻辑结构即表、树和图；

注：数据的物理存储结构中，顺序结构在物理空间，如内存中是连续的，如100个字节存储在内存中编号为0-100的空间内；链式、索引和哈希则是在物理空间中不连续的；

运算效率的度量------时间复杂度

时间复杂度示例：

注：时间复杂度的计算有两个前提条件：

1）每一条语句算一次；

2）常数项通常可以忽略不计，不参数比较，如上图中，左边的常数项为N为3，即第4，5，9行代码，右边的常数项N为2，即第4，6行代码；

时间复杂度计算示例： 

注：上图中，设字符串变量$string的长度为n，上图中总的执行次数4n + 8，for循环中，$i=0，算一次，在常数项里，$i<$strLent和$i++，分别为N次，再加上循环体里的两个语句，一共4n，加上其它的为4n + 8，T(n) = 4n +8，同量级的函数为f(n) = n，T(n) / f(n) =4 + 8/n，求极限后为常数4，因此总的时间复杂度为O(f(n)) = O(n)； 

线性表

注：循环单链表是为解决约瑟夫环的问题而产生的；

树

php查找和排序算法

注：二分查找的数据必须是已经排好序的数据，二分查找循环的次数f(n) = log₂n,（是以2为底，n的对数），所以时间复杂度可以表示O()=O(logn)

算法题示例：

注：循环文本的每一行每一个单词，将每个单词哈希到一个内存地址上，然后在哈希到的地址上存入一个单链表的首地址，并将当前的行列值存入该链表中，后面有相同的单词则将行列数追加到单链表的后面，查找时，通过哈希算法找到单链接表，然后循环单链表，输出里面的每个值；

注：给每个收录的文章编一个号，然后将每篇文单里出现的单词追加到索引里，查找时就可以通过单词长到相应的文章； 

排序

注：内排序是指在内存中进行排序，外排是指在内存外进行排序；

注：php的系统排序函数就是采用的快速排序；

分解法和剥洋葱法的思想