尧图网站建设 
数据结构的三要素逻辑结构线性结构每一个元素除了第一个和最后一个都有唯一前驱和唯一后继例如排队前后是有逻辑关系的。树形结构一对多比如从我们电脑的磁盘D盘到下面的各级目录图形结构例如人际关系多对多集合数据在其中无特殊联系只是在同一个集合内。物理结构存储结构顺序存储把逻辑上相邻的元素存储在一段连续的存储单元里链式存储把逻辑上相邻的元素存储在任意的一组存储单元里数据域用于存储本身的数据。指针域保存下一个节点的内存地址。索引存储存储元素信息的同时还建立了索引表索引表中的每项称为索引项索引项的一般形式为关键字地址例如书的目录散列存储也叫哈希存储物理结构是利用哈希函数将数据元素通过关键字算出数组下标然后将元素放在下标位置哈希存储不支持顺序遍历、排序。存放位置由哈希函数决定。数据运算及实现对数据元素可以施加的操作以及这些操作在相应的存储结构上的实现小结数据结构概念导图数据结构和数据对象以及两结构的关系另逻辑结构可以看作是蓝图设计图纸等。而物理结构可以看作是实操也就是真的建的房子算法效率分析算法效率分析包括时间效率时间复杂度和空间效率空间复杂度。时间复杂度是衡量算法的运行速度空间复杂度是衡量算法需要的额外空间。关于时间复杂度并不是程序运行的实际时间1s1min而是算法中基本操作的执行次数因为计算机的硬件不同先进的处理器在实际操作时会比老旧的处理器快时间复杂度的计算是在准确表达式中对整个表达式的结果影响最大的一个比如上图中的N*N。上图中时间复杂度为ON*N又或者准确表示式为2*n10时间复杂度就是On又或者是MN次当mn时时间复杂度就是OM抓大头m和n差不多时就是OM或ON如果是常数比如100、1000、10000他们的时间复杂度都为O1也就是上图的第一条当运行时间中只有加法常数时用常数1代替。常数次执行次数时间是固定的另有些算法的时间复杂度存在最好、平均、最坏的情况最坏的情况也就是此程序运行次数的上界最大运行次数N次平均情况也就是期望运行次数N\2次最好的情况也就是此程序运行次数的下界最小运行次数1次当程序出现这三种情况时我们计算时间复杂度取最坏的情况也就是此程序运行次数的上界N因此时间复杂度为ON冒泡排序第一次要进行N次排序第二次是N-1以此类推准确次数就是N*N-1/2那么时间复杂度也就是ON*N二分查找二分查找需要先进行排序通过多次折半的方式来查找所需要的数据假设我们折半了x次整个数据有N个元素那么我们查找时最好的情况就是第一次就直接找到O1最坏的情况也就是我们折半了x次每一次折半都有至少一半的元素被查完那么也就是2的x次方等于N算出查找次数xlog2Nlog2底N时间复杂度也就等于Olog2底N将2省略OlogN阶乘的时间复杂度使用递归来完成阶乘运算执行了N次因此时间复杂度为On。时间复杂度中里面的数值越小n取无穷大代表此程序的运行时间越短程序越精妙。空间复杂度因设计思路所需要开辟的额外空间不包括数据本身所占用的空间。示例while的循环条件是k--k不等于0时为真继续循环内层循环次数不变外乘内计算就是k*nOk*n时间复杂度而空间上几乎没有额外空间开辟空间复杂度为O1原地算法开辟了k个新空间将后面的k个元素先放到临时空间tmp中再将前面的n-k个元素后置再把tmp中存储的k个元素放到nums的前面一共进行了kn-kk次因此时间复杂度为On而我们开辟了k个新空间所以空间复杂度为OK三次逆置先将所有数据逆置一次再将前k项逆置然后后n-k项逆置。逆置时所有数据逆置实际执行次数为n/2前k项逆置为k/2后n-k项同理所以完整的实际执行次数正好是n时间复杂度为On而我们在此算法中并没有开辟任何的额外空间只是在原有数据上进行操作故也属于原地算法空间复杂度为O1数据类型和抽象数据类型数据类型是一个值的集合和定义在这个值集上的一组操作的总称数据类型一般可分为原子类型和结构类型原子类型原子类型的值是不可以再分解的例如c语言中的int、char等结构类型由若干成分按某种结构组成是可以分解的。如c语言中定义的一个结构体类型。抽象数据类型是一种数学模型加上在该模型上定义的一组操作的集合它定义了数据对象、数据关系以及对数据的操作但隐藏了具体实现细节算法的基本概念算法是解决特定问题的求解步骤的一种描述它描述了如何将输入的数据转换成我们期望的输出数据的操作算法表示用系统的方法来描述解决问题的策略机制。精心设计的算法可以大大提高程序的运行效率算法和数据结构算法数据结构程序一个好的程序需要选择精妙的算法和更加适合的数据结构。算法的特性有穷性算法必须在有限的步骤内结束不能无限制的循环或永远不终止确定性算法的每一步骤必须有确切的没有歧义、二义性的定义。对于相同的输入必须得到相同的输出可行性算法是可执行的算法中描述的操作都是通过已经实现的基本运算执行有限次来实现输入算法有零个或多个输入这些输入取自特定的对象集合输出算法有一个或多个输出。输出是算法处理输入后得到的结果与输入有特定关系算法设计的要求正确性可读性健壮性高效率与低存储要求 数据结构之开端
数据结构的三要素逻辑结构线性结构每一个元素除了第一个和最后一个都有唯一前驱和唯一后继例如排队前后是有逻辑关系的。树形结构一对多比如从我们电脑的磁盘D盘到下面的各级目录图形结构例如人际关系多对多集合数据在其中无特殊联系只是在同一个集合内。物理结构存储结构顺序存储把逻辑上相邻的元素存储在一段连续的存储单元里链式存储把逻辑上相邻的元素存储在任意的一组存储单元里数据域用于存储本身的数据。指针域保存下一个节点的内存地址。索引存储存储元素信息的同时还建立了索引表索引表中的每项称为索引项索引项的一般形式为关键字地址例如书的目录散列存储也叫哈希存储物理结构是利用哈希函数将数据元素通过关键字算出数组下标然后将元素放在下标位置哈希存储不支持顺序遍历、排序。存放位置由哈希函数决定。数据运算及实现对数据元素可以施加的操作以及这些操作在相应的存储结构上的实现小结数据结构概念导图数据结构和数据对象以及两结构的关系另逻辑结构可以看作是蓝图设计图纸等。而物理结构可以看作是实操也就是真的建的房子算法效率分析算法效率分析包括时间效率时间复杂度和空间效率空间复杂度。时间复杂度是衡量算法的运行速度空间复杂度是衡量算法需要的额外空间。关于时间复杂度并不是程序运行的实际时间1s1min而是算法中基本操作的执行次数因为计算机的硬件不同先进的处理器在实际操作时会比老旧的处理器快时间复杂度的计算是在准确表达式中对整个表达式的结果影响最大的一个比如上图中的N*N。上图中时间复杂度为ON*N又或者准确表示式为2*n10时间复杂度就是On又或者是MN次当mn时时间复杂度就是OM抓大头m和n差不多时就是OM或ON如果是常数比如100、1000、10000他们的时间复杂度都为O1也就是上图的第一条当运行时间中只有加法常数时用常数1代替。常数次执行次数时间是固定的另有些算法的时间复杂度存在最好、平均、最坏的情况最坏的情况也就是此程序运行次数的上界最大运行次数N次平均情况也就是期望运行次数N\2次最好的情况也就是此程序运行次数的下界最小运行次数1次当程序出现这三种情况时我们计算时间复杂度取最坏的情况也就是此程序运行次数的上界N因此时间复杂度为ON冒泡排序第一次要进行N次排序第二次是N-1以此类推准确次数就是N*N-1/2那么时间复杂度也就是ON*N二分查找二分查找需要先进行排序通过多次折半的方式来查找所需要的数据假设我们折半了x次整个数据有N个元素那么我们查找时最好的情况就是第一次就直接找到O1最坏的情况也就是我们折半了x次每一次折半都有至少一半的元素被查完那么也就是2的x次方等于N算出查找次数xlog2Nlog2底N时间复杂度也就等于Olog2底N将2省略OlogN阶乘的时间复杂度使用递归来完成阶乘运算执行了N次因此时间复杂度为On。时间复杂度中里面的数值越小n取无穷大代表此程序的运行时间越短程序越精妙。空间复杂度因设计思路所需要开辟的额外空间不包括数据本身所占用的空间。示例while的循环条件是k--k不等于0时为真继续循环内层循环次数不变外乘内计算就是k*nOk*n时间复杂度而空间上几乎没有额外空间开辟空间复杂度为O1原地算法开辟了k个新空间将后面的k个元素先放到临时空间tmp中再将前面的n-k个元素后置再把tmp中存储的k个元素放到nums的前面一共进行了kn-kk次因此时间复杂度为On而我们开辟了k个新空间所以空间复杂度为OK三次逆置先将所有数据逆置一次再将前k项逆置然后后n-k项逆置。逆置时所有数据逆置实际执行次数为n/2前k项逆置为k/2后n-k项同理所以完整的实际执行次数正好是n时间复杂度为On而我们在此算法中并没有开辟任何的额外空间只是在原有数据上进行操作故也属于原地算法空间复杂度为O1数据类型和抽象数据类型数据类型是一个值的集合和定义在这个值集上的一组操作的总称数据类型一般可分为原子类型和结构类型原子类型原子类型的值是不可以再分解的例如c语言中的int、char等结构类型由若干成分按某种结构组成是可以分解的。如c语言中定义的一个结构体类型。抽象数据类型是一种数学模型加上在该模型上定义的一组操作的集合它定义了数据对象、数据关系以及对数据的操作但隐藏了具体实现细节算法的基本概念算法是解决特定问题的求解步骤的一种描述它描述了如何将输入的数据转换成我们期望的输出数据的操作算法表示用系统的方法来描述解决问题的策略机制。精心设计的算法可以大大提高程序的运行效率算法和数据结构算法数据结构程序一个好的程序需要选择精妙的算法和更加适合的数据结构。算法的特性有穷性算法必须在有限的步骤内结束不能无限制的循环或永远不终止确定性算法的每一步骤必须有确切的没有歧义、二义性的定义。对于相同的输入必须得到相同的输出可行性算法是可执行的算法中描述的操作都是通过已经实现的基本运算执行有限次来实现输入算法有零个或多个输入这些输入取自特定的对象集合输出算法有一个或多个输出。输出是算法处理输入后得到的结果与输入有特定关系算法设计的要求正确性可读性健壮性高效率与低存储要求