6. 数据结构 磨耳朵
数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。
研究数据结构就是研究数据的逻辑结构、存储结构及其基本运算。
数据结构一般包括数据的逻辑结构、数据的存储结构、数据运算。
与所使用的计算机无关的是数据的逻辑结构。
逻辑结构可分成线性结构与非线性结构。
非线性结构有集合、树、图。
计算机算法是对解题方法的步骤描述。
是有穷步骤的集合,这些步骤确定了解决某类问题的有限长的操作序列。
算法具有的性质包括输入、输出、有效性、正确性、有穷性。
算法的有穷性是指一个算法必须在执行有限步骤后终止。
数据结构和算法的描述可以使用多种方式,包括自然语言、伪代码、流程图以及具体的编程语言。这些描述方式并不局限于面向对象的编程语言。
伪代码通常采用自然语言和程序设计语言的混合形式来描述算法。
流程图是最早出现的用图形表示算法的工具,具有的特点包括准确、直观、可读性好
算法分析的目的就是分析算法的效率以求改进。
算法的复杂度一般与算法所解决问题的规模有关。
在评价算法时,时间复杂度和空间复杂度较低的算法是较优的算法。
数据在计算机内存储时,物理地址与逻辑地址相同并且是连续的,称之为顺序存储结构。
数据的存储结构又叫数据的物理结构。
在线性结构中,假设存储了 N 个元素,顺序查找最多执行 N 次就能知道查找结果。
顺序表的缺点主要有插入删除元素操作复杂、对于长度变化较大的线性表,要一次性地分配足够的存储空间,但这些空间常常又得不到充分的利用、线性表的容量难以扩充。
线性表若采用链式存储结构时,要求内存中可用的存储单元的地址连续不连续都可以。
属于线性结构的有线性表(数组和链表)、二维数组,队列和栈也是线性表
线性结构是指数据元素之间存在一对一关系
在线性表中,逻辑上相邻的元素,其物理位置不一定相邻。
顺序存储的线性表可以随机存取。
链式存储的线性表不可以随机存取。
栈和队列都是顺序存取的线性表,但它们对存取位置的限制不同。
链表的插入、删除不需要移动元素。
栈不具有的特点就是可随机访问任意元素。
栈内存储的元素先进后出。
树形结构是数据元素之间存在一对多关系。
树形结构中,各个数据元素之间是有联系的,这种联系是通过父子节点关系来体现。
树的度是指树中所有结点的度的最大值。
树的深度是指所有结点层次的最大值。
树的叶子结点没有子树。
树最适合用来存储元素之间具有分支层次关系的数据
在树结构中,结点的度可以用该结点拥有的子树数来衡量、叶子结点是指度为 0 的结点、结点子树的根称为这个结点的孩子、树的度指所有结点的度的最大值。
二叉树属于非线性结构。
二叉树所有非叶节点的度不大于 2。
二叉树的左右子树不能交换。
二叉树叶子结点的个数是度为零的节点的个数。
二叉树的度是树中所有节点度的最大值。
二叉树所有非叶节点的度不大于 2。二叉树的左右子树不能交换。
二叉树可以为空二叉树。
二叉树结点的度可以是 0、1 或 2。
图形结构是指数据元素之间存在多对多关系。
排序是把一个无序的数据元素序列重新整理成按关键字递增(或递减)排列的过程。
进行二分查找的表必须是顺序存储的有序表。