《数据结构》知识点概括

数据结构知识点概括第一章 概 论数据就就是指能够被计算机识别、存储与加工处理得信息得载体。数据元素就是数据得基本单位,可以由若干个数据项组成。数据项就是具有独立含义得最小标识单位。数据结构得定义:·逻辑结构:从逻辑结构上描述数据，独立于计算机.·线性结构：一对一关系。·线性结构：多对多关系。 ·存储结构：就是逻辑结构用计算机语言得实现。·顺序存储结构:如数组。 ·链式存储结构:如链表。 ·索引存储结构：·稠密索引:每个结点都有索引项。 ·稀疏索引：每组结点都有索引项. ·散列存储结构:如散列表。·数据运算。·对数据得操作。定义在逻辑结构上，每种逻辑结构都有一个运算集合。 ·常用得有:检索、插入、删除、更新、排序。数据类型:就是一个值得集合以及在这些值上定义得一组操作得总称. ·结构类型:由用户借助于描述机制定义,就是导出类型。 抽象数据类型Ａ 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) ·查找:...