一、数据结构
1.1 数据结构定义
数据结构是计算机存储、组织数据的方式。数据结构是相互之间存在一种或者多种特定关系的数据元素的集合。数据结构=物理结构+逻辑结构
1.2 数据结构的基本数据单位
1、数据：是描述客观事物的符号，是计算机中可以操作的对象，是能被计算机识别，并输入给计算机处理的符号集合。数据不仅仅包括整型、实型等数值类型，还包括字符及声音、图像、视频等非数值类型。
2、数据对象：是性质相同的数据元素的组合、是数据的子集。
3、数据元素：组成数据的，且有一定意义的基本单位，在计算机中通常作为整体处理。
4、数据项：一个数据元素有多个数据项组成。
关系图如下：
数据结构基本数据单位
1.3 数据结构
数据结构分为逻辑结构和物理结构。
1.3.1逻辑结构
逻辑结构：数据对象中的数据元素之间的相互关系。逻辑结构分为四种，分别是集合结构、线性结构、树形结构、图形结构。
集合结构
集合结构
集合结构中数据元素之间并没有什么联系，只是多个数据元素集合了在一起。
线性结构
线性结构
线性结构中数据元素存在着先后顺序的关系，一对一。常用的线性结构有：线性表，栈，队列，双队列，数组，串。
树形结构
树形结构
树形结构中数据元素之间一对多，常见的树形结构: 二叉树,B树,哈夫曼树,红黑树等.
图形结构
图形结构
图形结构中数据元素之间的关系多对多。常见的图形结构: 邻近矩阵,邻接表.
1.3.2物理结构
物理结构：数据的逻辑结构在计算机的存储形式.
物理结构有顺序存储结构和链式存储结构。
二、数据结构与算法
2.1.1算法
算法就是解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每个指令表示一个或者多个操作。
2.1.2算法特性
有输入和输出、有穷性、确定性、可行性
2.1.3算法的设计要求
正确性、可读性、健壮性、时间效率高和存储量低
2.1.4常见的时间复杂度
时间复杂度
2.1.5算法空间复杂度
算法设计有一个重要原则，即空间/时间权衡原则（space/time tradeoff）。
算法的空间复杂度通过计算算法所需的存储空间实现,算法空间复杂度的计算公式记做: S(n) = n(f(n)),其中,n为问题的规模,f(n)为语句关于n所占存储空间的函数.
一般情况下, 一个程序在机器上执行时,除了需要寄存本身所用的指令,常数,变量和输入数据外,还需要一些对数据进行操作的辅助存储空间. 其中,对于输入数据所占的具体存储量取决于问题本身,与算法无关. 这样**==只需要分析该算法在实现时所需要的辅助空间就可以了==**.
如果算法执行时所需要的辅助空间相对于输入数据量是一个常数,则成这个算法原地工作,辅助空间为O(1).
网友评论