image.png
数据结构定义
数据结构(data structure)是带有结构特性的数据元素的集合，它研究的是数据的逻辑结构和数据的物理结构以及它们之间的相互关系，并对这种结构定义相适应的运算，设计出相应的算法，并确保经过这些运算以后所得到的新结构仍保持原来的结构类型。简而言之，数据结构是相互之间存在一种或多种特定关系的数据元素的集合，即带“结构”的数据元素的集合。“结构”就是指数据元素之间存在的关系，分为逻辑结构和存储结构。
数据结构 = 逻辑结构+物理结构
时间复杂度
算法执行语句的次数（除非特指，否则说的都是最坏情况的运行时间，最坏运行时间是一种保证，是一种最重要的需求）
- 如一组随机数的数组中找到某个元素，最好的情况就是第一个元素就是要找的元素，那么算法时间复杂度是O(1),但是也有可能最后一个才找到，那么时间复杂度就是O(n).
时间复杂度的计算方式-大O表示法
用常数1取代所有运行时间中的常数
只保留最高阶
如果与最高阶项相乘的系数大于1，则为1
常用的时间复杂度所耗费的时间从小到大依次是：
O(1) < O(logn) < (n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)
空间复杂度
算法在执行过程中所用到的辅助空间大小的量度
逻辑结构
- 线性结构：表中各个结点具有线性关系。
- 集合结构：数据结构中的元素之间除了“同属一个集合” 的相互关系外，别无其他关系
- 树形结构-一对多
- 图形结构-多对多
常用的数据结构
数组：
是一种聚合数据类型
栈：
是一种特殊的线性表，在一个表的固定端进行数据结点的插入和删除操作。按照一种先进后出的原则来存储数据，即先插入的数据被压到栈底，后插入的数据在栈顶，读数据时，先从栈顶开始
堆:
堆是一种特殊的树形结构，一般讨论的都是二叉堆。堆的特点是根结点的值是所有结点中最小或者最大的，且根结点的两个子树也是一个堆结构
队列:
是一种特殊的线性表。遵循FIFO（先进先出原则），即允许在表的一端进行插入，在另一端进行删除。一般来说，进行插入的是队尾，进行删除的是队头。
链表
链表是一种数据元素按照链式存储结构进行存储的数据结构，这种存储结构具有在物理上存在非连续的特点。链表由一系列数据结点构成，每个数据结点包括数据域和指针域两部分。其中，指针域保存了数据结构中下一个元素存放的地址。链表结构中数据元素的逻辑顺序是通过链表中的指针链接次序来实现的。
树
树是典型的非线性结构，它是包括，2个结点的有穷集合K。在树结构中，有且仅有一个根结点，该结点没有前驱结点。在树结构中的其他结点都有且仅有一个前驱结点，而且可以有两个后继结点，m≥0。
图
图是另一种非线性数据结构。在图结构中，数据结点一般称为顶点，而边是顶点的有序偶对。如果两个顶点之间存在一条边，那么就表示这两个顶点具有相邻关系。
散列表
散列表源自于散列函数(Hash function)，其思想是如果在结构中存在关键字和T相等的记录，那么必定在F(T)的存储位置可以找到该记录，这样就可以不用进行比较操作而直接取得所查记录
线性表
对于非空的线性表和线性结构，有如下特点：
- 存在唯一的一个被称作“第一个”的元素
- 存在唯一的一个被称作“最后一个”的元素
- 除了第一个元素之外，结构中的每个数据元素都有一个前驱
- 除了最后一个元素之外，结构中的每个数据元素都有一个后继
- 单链表
- 双向链表
- 循环链表
网友评论