数据结构知识点汇总

1、在数据结构中，随机访问是指能够直接访问任一元素，而不需要从特定的起始位置开始，也不需要按顺序访问其他元素。这种访问方式通常不涉及遍历。例如，数组（array）支持随机访问，你可以直接通过索引访问任意元素，而无需从第一个元素开始一步步遍历。

2、对于链式存储的理解：可以把每个节点理解为仅存储两个元素的数组，第一个元素是这个节点存储的数据，第二个节点存储的是下一个节点的数组名，也就是下一个节点的首地址（假设这个数组可以存储不同的数据类型）。

3、链式存储无法进行随机访问的原因就是，每一个节点在计算机内存中的位置信息都保留在前驱节点中，而前驱节点的位置信息又保存在前驱节点的前驱节点中，就这样连锁反应到首个节点，所以若要进行访问只能从第一个节点进行遍历。

4、算法可以没有输入，但至少有一个输出，用时间复杂度和空间复杂度来衡量一个算法的效率。

5、时间复杂度里的O()是指同阶的意思。

6、时间复杂度就是在当问题规模n趋近于无穷大时，谁是高阶无穷大。

7、高阶无穷大的比较参考为：常对幂指阶


时间复杂度的最终结果会省略低阶项和高阶项的系数，所以最终的结果一定是以上高阶无穷大序列中的某一个。且由于以上的函数单调递增、无交点，所以当n趋近于0时，他们的高阶无穷小顺序是反过来的。

8、由于在计算时间复杂度时，是将n处于趋近于无穷大的情况下进行计算，所以算法中的会执行但与n无关的代码步骤会被视作常数而被忽略掉。且由于最终的结果会忽略低阶项，所以都是直接研究最深层的循环的循环次数，一般循环次数都是关于n的一元函数。

9、在某些情况下，计算最深循环次数的条件并不确定，需要讨论最好和最坏情况，则需要计算平均循环次数，从而得到一个代表平均次数的n的一元函数。实际使用的都是平均时间复杂度和最坏时间复杂度，最好时间复杂度不会使用。

10、空间复杂度的变化一般都是由n引起的变量大小的改变，例如n决定了数组的大小和结构体大小；或则n决定了函数的嵌套次数，例如递归函数的递归次数。

11、空间复杂度就是根据n所决定的空间大小的高阶无穷大。

12、时间复杂度和空间复杂度的计算就是去找n的一元函数。

13、数据元素和数据项可以分别理解为一个账户和这个账户的具体信息，在实际的代码中可理解为结构体和成员变量。

14、数据结构就是存在特定关系的数据元素的集合，这个概念包含了数据元素以及它们之间的关系，在具体的数据结构中，每个节点的数据域就是数据元素。

15、数据对象就是具有相同性质的数据元素的集合，可理解为由同一个结构体或者类产生的实例对象集合。数据对象这个概念不包含数据元素之间的关系，所以这个概念仅指一个数据元素集合，数据元素之间可以不存在关系。

16、逻辑结构使用不同的存储结构会影响存储空间分配的方便程度、影响对数据运算的速度。

17、数据的运算是通过算法来实现的。

18、抽象数据类型ADT就是逻辑结构和数据的运算这两点的总和，一般都是先定义ADT，也就是逻辑结构和在此之上的运算，再使用具体的存储结构去实现他。