PHP数据结构笔记录
时间：2010-10-15 来源：HuSuMiao
数据结构：
1.数据结构中对象的定义,存储的表示及操作的实现.
2.线性:线性表、栈、队列、数组、字符串（广义表不考）
树：二叉树
集合：查找，排序
图。 排序知识：选择、希尔、堆、快速排序是不稳定的；直接插入、冒泡、合并排序是稳定的，其选择与冒泡思想类似选择效率更高。
排序分类：交换排序（冒泡排序、快速排序）、选择排序（直接选择排序、 堆排序）、分配排序（箱排序、基数排序）。
各种内部排序方法的比较和选择：
（1）按平均时间复杂度分为：
1) 平方阶排序：直接插入、直接选择、冒泡排序；
2) 线性对数阶：快速排序、堆排序、归并排序；
3) 指数阶：希尔排序；
4) 线性阶：箱排序、基数排序。
（2）选择合适排序方法的因素：
1)待排序的记录数；
2)记录的大小；
3)关键字的结构和初始状态；
4)对稳定性的要求；
5)语言工具的条件；
6)存储结构；
7)时间和辅助空间复杂度。
（3）结论：
1) 若规模较小可采用直接插入或直接选择排序；
2) 若文件初始状态基本有序可采用直接插入、冒泡或随机快速排序；
3) 若规模较大可采用快速排序、堆排序或归并排序；
4) 任何借助于比较的排序，至少需要O(nlog2n)的时间，箱排序和基数排序只适用于有明显结构特征的关键字；
5) 有的语言没有提供指针及递归，使归并、快速、基数排序算法复杂；
6) 记录规模较大时为避免大量移动记录可用链表作为存储结构，如插入、归并、基数排序，但快速、堆排序在链表上难以实现，可提取关键字建立索引表，然后对索引表排序。 查找知识：
线性表上进行查找的方法主要有三种：顺序查找、二分查找和分块查找，查找方法的比较如下：
查找算法 存储结构 优点 缺点 适用于 顺序查找 顺序结构 链表结构 算法简单且对表的结构无任何要求 查找效率低 n较小的表的查找和查找较少但改动较多的表(用链表作存储结构)
二分查找 顺序结构 查找效率高 关键字要有序且只能用顺序存储结构实现 特别适用于一经建立就很少改动又经常需要查找的线性表
分块查找 顺序结构 链表 在表中插入或删除记录时就只要在该记录所属块内操作，因为块内记录的存放是随意的，所以插入和删除比较容易 要增加一个辅助数组的存储空间，并要进行将初始表分块排序运算 适用于有分块特点的记录，如一个学校的学生登记表可按系号或班号分块。 根据排序元素所在位置的不同,排序分: 内排序和外排序。
内排序：在排序过程中，所有元素调到内存中进行的排序，称为内排序。内排序是排序的基础。内排序效率用比较次数来衡量。按所用策略不同，内排序又可分为插入排序、选择排序、交换排序、归并排序及基数排序等几大类。
外排序：在数据量大的情况下，只能分块排序，但块与块间不能保证有序。外排序用读/写外存的次数来衡量其效率。
排序算法的稳定性：若待排序的序列中，存在多个具有相同关键字的记录，经过排序，这些记录的相对次序保持不变，则称该算法是稳定的；若经排序后，记录的相对次序发生了改变，则称该算法是不稳定的。 排序算法的存储结构通常有三种：一维数组；链表；辅助表（如索引表）。
按策略划分内部排序方法，可以分为五类：插入排序、选择排序、交换排序、归并排序和分配排序。
评价排序算法好坏的标准主要有两条：执行时间和所需的辅助空间、算法本身的复杂程度。 算法知识：
移动一个数组可以使用 while 实现。
找出一个数组中的最大值和最小值可以用for() if($array[$i]>$max) $max=$array[$i]; 实现。 进制转换知识：
十进制转任意进制的方法一般有两种
1.试减法
2.短除法
总的来说，方法1适合笔算，方法2适合计算机算 下面分别说
1.试减法
通过估算反复减去不大于目标数字的权重的n次方来得到每一位的数字
说起来十分拗口，做起来其实不难
比如将十进制的 1234 转为 5 进制
首先寻找不大于1234的5的整数次方
5^4 = 625 < 1234
5^5 = 3125 > 1234
所以 625 符合条件
625 * 2 = 1250 >1234
625 * 1 = 625 <1234 所以第5位上的数字为1
1234(十进制) = 1???? 用1234 - 1 * 5^4 = 609作为目标数，再重复刚才的操作
因为刚才得出了最高位是第5位，所以现在接着往下算就可以了
5^3 = 125
125 * 4 = 500 <609
第4位上的数字为4
1234(十进制) = 14??? 609 - 4 * 5^3 = 109
5^2 = 25
25 * 4 = 100 <109
第三位上的数字为4
1234(十进制) = 144?? 109 - 4 * 5^2 = 9
5^1 = 5
5 * 1 = 5 <9
5 * 2 = 10 >9
第二位上的数字为1
1234(十进制) = 1441? 9 - 1 * 5^1 = 4
最低位上的数字为4
1234(十进制) = 14414 可以看出这个方法需要多次估计与试算，所以不适合计算机算 2.短除法
通过反复短除目标数求余来得到每一位上的数字
比如 1234 转 5 进制
1234 / 5 = 246
余 4
246 / 5 = 49
余 1
49 / 5 = 9
余 4
9 / 5 = 1 余 4
1 / 5 = 0 余 1
可以看出，所有的余数就构成了转化的结果 14414
最低位在最上
这样的方法计算量比较大，适合计算机算 最后，对于有乘方关系的两个进制转换有简洁的算法
比如3进制和9进制互转
因为 9 是3的2次方，所以 3 进制数每两位就对应 9 进制数的1位
9进制
比如9进制1234转3进制就有如下对应关系
0----00
1----01
2----02
3----10
4----11
5----12
6----20
7----21
8----22
所以 9 进制 3781 转化为 3 进制就可以简单地查表计算为
3 7 8 1 = 10 21 22 01 = 10212201 归纳一下：
A进制转10进制：
k(n) * 10^(n-1) + k(n-1) * 10^(n-2) + ... + k(2) * 10^1 + k(1) * 10 ^0
其中n代表数字所在的位数，k(n)代表第n位上的数字值 10进制转A进制：试减法或者短除法
地址：http://www.xinqdian.com/index.php/archives/107/
php 进制转换函数：http://www.blags.org/php-jinzhi/
1.数据结构中对象的定义,存储的表示及操作的实现.
2.线性:线性表、栈、队列、数组、字符串（广义表不考）
树：二叉树
集合：查找，排序
图。 排序知识：选择、希尔、堆、快速排序是不稳定的；直接插入、冒泡、合并排序是稳定的，其选择与冒泡思想类似选择效率更高。
排序分类：交换排序（冒泡排序、快速排序）、选择排序（直接选择排序、 堆排序）、分配排序（箱排序、基数排序）。
各种内部排序方法的比较和选择：
（1）按平均时间复杂度分为：
1) 平方阶排序：直接插入、直接选择、冒泡排序；
2) 线性对数阶：快速排序、堆排序、归并排序；
3) 指数阶：希尔排序；
4) 线性阶：箱排序、基数排序。
（2）选择合适排序方法的因素：
1)待排序的记录数；
2)记录的大小；
3)关键字的结构和初始状态；
4)对稳定性的要求；
5)语言工具的条件；
6)存储结构；
7)时间和辅助空间复杂度。
（3）结论：
1) 若规模较小可采用直接插入或直接选择排序；
2) 若文件初始状态基本有序可采用直接插入、冒泡或随机快速排序；
3) 若规模较大可采用快速排序、堆排序或归并排序；
4) 任何借助于比较的排序，至少需要O(nlog2n)的时间，箱排序和基数排序只适用于有明显结构特征的关键字；
5) 有的语言没有提供指针及递归，使归并、快速、基数排序算法复杂；
6) 记录规模较大时为避免大量移动记录可用链表作为存储结构，如插入、归并、基数排序，但快速、堆排序在链表上难以实现，可提取关键字建立索引表，然后对索引表排序。 查找知识：
线性表上进行查找的方法主要有三种：顺序查找、二分查找和分块查找，查找方法的比较如下：
查找算法 存储结构 优点 缺点 适用于 顺序查找 顺序结构 链表结构 算法简单且对表的结构无任何要求 查找效率低 n较小的表的查找和查找较少但改动较多的表(用链表作存储结构)
二分查找 顺序结构 查找效率高 关键字要有序且只能用顺序存储结构实现 特别适用于一经建立就很少改动又经常需要查找的线性表
分块查找 顺序结构 链表 在表中插入或删除记录时就只要在该记录所属块内操作，因为块内记录的存放是随意的，所以插入和删除比较容易 要增加一个辅助数组的存储空间，并要进行将初始表分块排序运算 适用于有分块特点的记录，如一个学校的学生登记表可按系号或班号分块。 根据排序元素所在位置的不同,排序分: 内排序和外排序。
内排序：在排序过程中，所有元素调到内存中进行的排序，称为内排序。内排序是排序的基础。内排序效率用比较次数来衡量。按所用策略不同，内排序又可分为插入排序、选择排序、交换排序、归并排序及基数排序等几大类。
外排序：在数据量大的情况下，只能分块排序，但块与块间不能保证有序。外排序用读/写外存的次数来衡量其效率。
排序算法的稳定性：若待排序的序列中，存在多个具有相同关键字的记录，经过排序，这些记录的相对次序保持不变，则称该算法是稳定的；若经排序后，记录的相对次序发生了改变，则称该算法是不稳定的。 排序算法的存储结构通常有三种：一维数组；链表；辅助表（如索引表）。
按策略划分内部排序方法，可以分为五类：插入排序、选择排序、交换排序、归并排序和分配排序。
评价排序算法好坏的标准主要有两条：执行时间和所需的辅助空间、算法本身的复杂程度。 算法知识：
移动一个数组可以使用 while 实现。
找出一个数组中的最大值和最小值可以用for() if($array[$i]>$max) $max=$array[$i]; 实现。 进制转换知识：
十进制转任意进制的方法一般有两种
1.试减法
2.短除法
总的来说，方法1适合笔算，方法2适合计算机算 下面分别说
1.试减法
通过估算反复减去不大于目标数字的权重的n次方来得到每一位的数字
说起来十分拗口，做起来其实不难
比如将十进制的 1234 转为 5 进制
首先寻找不大于1234的5的整数次方
5^4 = 625 < 1234
5^5 = 3125 > 1234
所以 625 符合条件
625 * 2 = 1250 >1234
625 * 1 = 625 <1234 所以第5位上的数字为1
1234(十进制) = 1???? 用1234 - 1 * 5^4 = 609作为目标数，再重复刚才的操作
因为刚才得出了最高位是第5位，所以现在接着往下算就可以了
5^3 = 125
125 * 4 = 500 <609
第4位上的数字为4
1234(十进制) = 14??? 609 - 4 * 5^3 = 109
5^2 = 25
25 * 4 = 100 <109
第三位上的数字为4
1234(十进制) = 144?? 109 - 4 * 5^2 = 9
5^1 = 5
5 * 1 = 5 <9
5 * 2 = 10 >9
第二位上的数字为1
1234(十进制) = 1441? 9 - 1 * 5^1 = 4
最低位上的数字为4
1234(十进制) = 14414 可以看出这个方法需要多次估计与试算，所以不适合计算机算 2.短除法
通过反复短除目标数求余来得到每一位上的数字
比如 1234 转 5 进制
1234 / 5 = 246
余 4
246 / 5 = 49
余 1
49 / 5 = 9
余 4
9 / 5 = 1 余 4
1 / 5 = 0 余 1
可以看出，所有的余数就构成了转化的结果 14414
最低位在最上
这样的方法计算量比较大，适合计算机算 最后，对于有乘方关系的两个进制转换有简洁的算法
比如3进制和9进制互转
因为 9 是3的2次方，所以 3 进制数每两位就对应 9 进制数的1位
9进制
比如9进制1234转3进制就有如下对应关系
0----00
1----01
2----02
3----10
4----11
5----12
6----20
7----21
8----22
所以 9 进制 3781 转化为 3 进制就可以简单地查表计算为
3 7 8 1 = 10 21 22 01 = 10212201 归纳一下：
A进制转10进制：
k(n) * 10^(n-1) + k(n-1) * 10^(n-2) + ... + k(2) * 10^1 + k(1) * 10 ^0
其中n代表数字所在的位数，k(n)代表第n位上的数字值 10进制转A进制：试减法或者短除法
地址：http://www.xinqdian.com/index.php/archives/107/
php 进制转换函数：http://www.blags.org/php-jinzhi/
相关阅读 更多 +
