数据结构导论笔记

发布于 2019-05-15  180 次阅读


数据结构导论笔记

一、基础知识

1.常见的逻辑结构有哪几种?常见的逻辑结构
2.常见的存储结构有哪几种?常见的存储结构
3.时间复杂度是研究什么的?时间复杂度研究的内容
4.空间复杂度是研究什么的?空间复杂度研究的内容
5.都有什么组成了空间复杂度?组成空间复杂度的要素
6.常见的时间复杂度排序?时间复杂度的排序
7.等差数列求和公式等差数列求和公式
8.log对数,对求幂的逆运算log定义

二、线性表

线性表(List):由零个或多个数据元素组成的有限序列。 注意: 1.线性表是一个序列。 2.0个元素构成的线性表是空表。 3.线性表中的第一个元素无前驱,最后一个元素无后继,其他元素有且只有一个前驱和后继。 4.线性表是有长度的,其长度就是元素个数,且线性表的元素个数是有限的,也就是说,线性表的长度是有限的。 如果用数学语言来进行定义,可如下: 若将线性表记为(a1,…,ai-1,ai,ai+1,…an),则表中ai-1领先于ai,ai领先于ai+1,称ai-1是ai的直接前驱元素,ai+1是ai的直接后继元素。[常见的逻辑结构]  集合,线性结构,树形结构,图结构[常见的存储结构]  顺序存储,链式存储,散列存储,索引存储[时间复杂度研究的内容]  在给定数据下的计算量[空间复杂度的研究内容]  辅助变量的所占用的空间[组成空间复杂度的要素]  程序代码,输入数据,辅助变量构成了算法所需要的存储空间[时间复杂度的排序]  常数O(1),对数O(log2n),线性阶O(n),线性对数阶O(nlog2n),平方阶O(n2),多项式O(nc),指数阶O(Cn)[等差数列求和公式]  ​[log定义]  如果a的x次方等于N(a>0,且a≠1)那么x叫做以a为底N的对数,记住x=logaN,其中a叫做对数的底数,N叫做真数。


把一切平凡的事做好即不平凡,把一切简单的事做好即不简单。