文档介绍：数据结构
数据结构:数据间存在的相互关系称为结构。数据间抽象化的相互关系(如何表示)称为数据的逻辑结构。如何把这些数据按照一定的逻辑关系存储在计算机中的问题,即数据的存储方式——数据的物理结构或存储结构。数据的逻辑结构有线性结构和非线性结构两大类。
常用的存储表示方法有4种,顺序存储、链式存储、索引存储、散列存储。其中,顺序存储方法是把逻辑上相邻的结点存储在物理位置也相邻的存储单元中。
数据结构的主要内容:1)数据间的逻辑关系——逻辑结构——抽象的 2)数据的具体存储方式——存储结构——具体的 3)数据的运算——用算法实现——实现过程
数据的四种逻辑结构:
集合:数据之间只是“同属一个集合”(和数学中的集合概念一致)
线性结构(表):数据之间存在“一对一”的序列关系。即‘一个跟着一个’。
树型结构:数据之间存在着“一对多”的关系,即‘每个元素只能跟着一个元素,但可以有多个元素跟着它’。
图状结构(网):数据间是“多对多”的关系,即任意两个数据间都可能存在着关系。
算法是对待定问题求解步骤的一种描述,它是运算指令的有限序列,其中每一条指令表示一个或多个操作。算法有五个重要特性:1)有穷性——算法必须是在执行有穷步骤之后结束,即有始有终。2)确定性——算法的每一个步骤必须是确切地定义,不能产生二义。3)可行性(可操作性)——即任何一步都是切实可行的,所描述的操作都是基本的、可以通过有限次的运算来实现。4)数据的输入——有零个或多个数据输入5)数据的输出——有零个或多个数据输出
算法的复杂度包括算法的时间复杂度(指执行算法所需要的计算工作量,即算法中实现基本操作的语句重复执行的次数,算法中实现基本操作的语句(基本语句)重复执行的次数)和算法的空间复杂度(指执行这个算法所需要的内存空间)。
线性表:表是由N(N>=0)个同一类型的元素(结点)a1,a2,a3,…,an组成的有限序列。
其中,元素的个数N定义为表的长度。当N=0时称为空表。当N>=1时,称元素ai位于该表的第个i位置,或称ai是表中第i个元素,i=1,2,3,…,n。将ai称为 ai+1的直接前驱;ai+1为ai的直接后继。(四个一:唯一的首、尾、直接前驱、直接后继)
线性表的顺序表示:类似于数组,利用物理位置上的邻接关系来表示表中的元素之间的逻辑关系。有关系LOC(ai)=LOC(a1)+i×单个元素所占空间。优点:随机存取,缺点:插入删除需要移动大量元素。
线性表的链式表示:采用链表,结点空间动态申请和释放,数据元素之间的逻辑关系用指针来指示,不需移动数据。缺点:结点中的指针域占用额外空间,非随机存储结构(拓展:循环链表、双向链表)
栈:操作受限的线性表,只允许在栈顶对元素进行插入删除,是“后进先出/先进后出”的结构。
队列:操作受限的线性表,只允许在队列一端对元素进行插入,在另一端删除,是一种“先进先出/后进后出”的结构。
树是一个或多个结点组成的有限集合,其中一个特定的结点称为根,其余结点分为若干个不相交的集合。每个集合同时又是一棵树。树有且只有1个根结点。
结点(Node):树中的元素,包含数据项及若干指向其子树的分支。
结点的度(Degree):结点拥有的子树数。结点的层次:从根结点开始算起,根为第一层
叶子(Leaf):度为零的结点,也称端