数据构造知识点概括第一章 概 论数据就就是指可以被计算机识别、存储与加工处理得信息得载体。数据元素就是数据得基本单位,可以由若干个数据项构成。数据项就是具有独立含义得最小标识单位。数据构造得定义:·逻辑构造:从逻辑构造上描述数据，独立于计算机.·线性构造：一对一关系。·线性构造：多对多关系。 ·存储构造：就是逻辑构造用计算机语言得实现。·次序存储构造:如数组。 ·链式存储构造:如链表。 ·索引存储构造：·稠密索引:每个结点均有索引项。 ·稀疏索引：每组结点均有索引项. ·散列存储构造:如散列表。·数据运算。·对数据得操作。定义在逻辑构造上，每种逻辑构造均有一种运算集合。 ·常用得有:检索、插入、删除、更新、排序。数据类型:就是一种值得集合以及在这些值上定义得一组操作得总称. ·构造类型:由顾客借助于描述机制定义,就是导出类型。 抽象数据类型Ａ D Ｔ:·就是抽象数据得组织与与之得操作。相称于在概念层上描述问题. ·长处就是将数据与操作封装在一起实现了信息隐藏.程序设计得实质就是对实际问题选择一种好得数据构造，设计一种好得算法 .算法取决于数据构造。算法就是一种良定义得计算过程，以一种或多种值输入,并以一种或多种值输出． 评价算法得好坏得原因：·算法就是对的得; ·执行算法得时间;·执行算法得存储空间(重要就是辅助存储空间);·算法易于理解、编码、调试。 时间复杂度：就是某个算法得时间花费，它就是该算法所求解问题规模ｎ得函数. 渐近时间复杂度:就是指当问题规模趋向无穷大时,该算法时间复杂度得数量级。 评价一种算法得时间性能时，重要原则就就是算法得渐近时间复杂度。 算法中语句得频度不仅与问题规模有关,还与输入实例中各元素得取值有关。 时间复杂度按数量级递增排列依次为:常数阶Ｏ（1)、对数阶 O（l ｏ g2n）、线性阶 O（n)、线性对数阶 O(n ｌ og2n)、平方阶 O(ｎ＾2)、立方阶Ｏ(n^3）、……ｋ次方阶 O(ｎ＾k)、指数阶 O(2^n)。 空间复杂度:就是某个算法得空间花费，它就是该算法所求解问题规模 n 得函数。 算法得时间复杂度与空间复杂度合称算法复杂度。第二章 线性表线性表就是由 n≥0 个数据元素构成得有限序列.ｎ=0 就是空表；非空表,只能有一种开始结点，有且只能有一种终端结点。 线性表上定义得基本运算: ·构造空表:Init ｌ ist(Ｌ) ·求表长：Ｌ i ｓ tleng ｔ h(L) ·取结点:G ｅ tNod ｅ(Ｌ，i) ·查找:...
