数据结构自我总结
一、数据结构的三要素：逻辑结构、存储结构、数据的运算。
逻辑结构分为线性结构和非线性结构，线性表是典型的线性结构；集合、树和图是典型的非线性结构。
存储结构主要有顺序存储、链式存储、索引存储、散列存储。
二、算法是对特定问题求解步骤的描述。
算法的五个重要特征：
1、有穷性 2、确定性 3、可行性 4、输入 5、输出
通常设计一个”好“的算法应考虑
1、正确性 2、可读性 3、健壮性 4、高效率与低存储量需求
三、复杂度
1、时间复杂度
总是考虑在最坏情况下的时间复杂度
a）加法法则
b）乘法法则
常见的渐近时间复杂度
O(1)<O(logn)<O(n)<O(nlogn)<O(n^2)<O(n^3)<O(2^n)<O(n!)<O(n^n)
2、空间复杂度
算法原地工作是指算法所需的辅助空间为常量，即O(1)。
三、线性表
1、线性表是具有相同数据类型的n个数据元素的有限序列。n=0时为空表
2、第一个数据元素为表头元素，除了表头元素外，每个元素都有一个直接前驱。最后一个数据元素为表尾元素，除表尾元素外，每一个元素都有直接后继。
表中元素的个数有限。
表中元素具有逻辑上的顺序性，表中元素有其先后次序。
表中元素都是数据元素，每个元素都是单个元素。
表中元素的数据类型相同，即每个元素占有相同大小的存储空间。
表中元素具有抽象性，即仅讨论元素间的逻辑关系，而不考虑元素究竟表示什么内容。
3、线性表是一种逻辑结构。顺序表和链表是指存储结构。
