数据结构基础理论

ゞ浴缸里的玫瑰 2021-09-17 23:54 361阅读 0赞

# 数据结构基础理论点 #

#### 概念 ####

> 数据与数据之间的关系

#### 可分为逻辑结构和存储结构 ####

##### 逻辑结构： #####

*  线性结构
    
     *  数据与数据之间的关系为 1： 1
     *  栈
     *  队列
 *  非线性结构
    
     *  数据与数据之间的关系为 1：n ,n ： m
     *  树 1 ： n
     *  图 n : m

##### 存储结构 ： #####

*  顺序存储
    
     *  各元素按照逻辑顺序存放在一段连续的地址空间中
     *  查询效率高
     *  插入，删除的效率低
     *  查找 元素 >>>>>> 元素物理地址 + （n-1)\* 内存空间大小
 *  链式存储
    
     *  保存元素的同时保存下一个或者上一个元素的地址
     *  查询效率低
     *  插入和删除的效率高
 *  索引存储
    
     *  在保存原始数据的同时，还需要建立一个索引表
     *  建议原始数据必须遵循一定的规律
 *  哈希存储
    
     *  利用一个哈希函数，把原始数据映射成一个唯一地址。
     *  在下次查找时，把要查找的内容，通过同样的哈希函数，得到一个结果，比较这个结果，看对应地址上是否存在这个内容。
     *  时间消耗主要在哈希的计算

#### 算法： ####

##### 评估方案的准则： #####

时间复杂度  
 O(n) : 线性增长，随着n的增大，消耗的时间呈线性增加  
 O(n^2): 二次方增长，随着n的增大，消耗的时间呈平方的级数增长  
 O(2^n)： 指数级增长  
 O(logn): 对数级增长，随着n的增大，消耗时间比较平缓  
 数量n 查找次数  
 31 5  
 127 7  
 255 8  
 511 9  
 1023 10  
 假设我有800个数字，请问使用二分法查找，最大查找次数：10次  
 O©： 常数级增长，不管n多大，消耗的时间都是一个固定的值  
 空间复杂度  
 T(n^2) 需要解决这个问题，输入n个元素，开辟n^2个元素来解决

顺序存储的特点：

元素大小统一，空间利用率是最高的
    空间不可以扩容

python list 增加新的需求：  
 顺序空间中，可以存储任意类型的数据  
 把数据的地址用顺序结构来保存，数据的地址是线性关系保存，数据的地址是随意的元素外置式

空间如何扩容
    	采用外置式的结构
    		表信息  表内容 分离
    		表信息中 含有该表的基本属性 和 表内容的地址
    		
    		当空间不够时，表内容以2倍关系进行扩充
    		扩充的新空间地址赋值给表信息中的地址