文档介绍：数据结构指的是数据之间的关系,一般包括三个方面的内容:数据的逻辑结构、数据的存储结构、数据的运算或操作。
数据的存储结构有四种基本方式:顺序结构、链接结构、索引结构、散列结构。
算法效率的度量分为:事后测量和事前估计。
物理结构:指数据在计算机中存放的方式,即数据逻辑结构的物理存储方式。主要有顺序存储和链式存储。
数据的操作指利用计算机对数据进行插入、删除、修改、查找、排序等操作。
数据类型:一个数据的集合,以及定义于这个数据集合上的一组操作的总称。
算法是对特定问题求解步骤的一种描述。算法是一个有穷的指令集,这些指令为解决某一特定任务规定了一个运算序列。
算法特性:输入、输出、确定性、有穷性、可行性。
算法评价:正确性、可读性、稳建性、时间复杂度、空间复杂度
线性表是 n(n>=0) 个相同类型数据元素a1, a2, …, an 构成的有限序列。是一种线性结构,允许在任意位置进行插入和删除操作。
一般表示为: L = ( a1, a2, …, an )
形式化定义: Linear_list = (D, R)
线性表的顺序存储结构:
用一组地址连续的存储单元依次存储线性表的各个数据元素。逻辑上相邻的元素在物理存储上也相邻。
顺序表的优点:空间单元利用率高、可以方便的随机存取表中的任一元素、算法简单
顺序表的缺点: 插入和删除运算需移动数据元素
线性表的链式存储结构特点:1、不要求逻辑上相邻的元素在物理位置上也相邻。可以用任意的存储单元存储数据元素。 2、线性表元素之间的逻辑关系由指针指示。顺序存取机制。
循环单链表与单链表的区别在于:循环链表的最后一个结点的指针指向头结点,整个链表形成一个环。优势在于:从表中任意一个结点出发都可找到表中其他结点。
“指针”的程序设计语言
单链表的优点:插入和删除操作时不需要移动数据元素
单链表的缺点:①每个结点要有一个指针域,空间单元利用率不高②算法相对复杂些
栈又称堆栈,是一种操作受限制的线性表,只允许在表的固定一端(表尾)进行插入或删除。
递归:一个算法直接或间接地调用自身,称该算法为递归算法。这个函数就称递归函数。
递归算法与栈的关系:
调用递归函数时,自动使用栈保存下述两类信息:调用后的返回地址;调用函数的局部变量值(包括实参)调用结束时,自动执行出栈操作,按返回地址返回。
队列也是一种操作受限的线性表,只允许在表的一端进行插入(表尾),在表的另一端进行删除(表头)。
树是n(n≥0)个结点的有限集。n=0的树称为空树。
任意一棵非空树,满足:
①有且只有一个称为根的结点(root):②当n>1时,除根结点外的结点可分为 m(m>0)个互不相交的有限集T1 , T2 ,…, Tm。且每一集合本身又是一棵树,称其为根的子树。每棵子树的根结点是整棵树根结点的后继,整棵树的根结点是每棵子树根结点的前驱。
树的形式化定义
Tree = ( K , R )
K = { ki | 1≤i≤n , n≥0, ki∈ElemType}
R= { r }
当 n > 0(非空树)时,关系 r 满足下列条件:
①有且仅有一个结点没有前驱,此结点称为根。
②除根以外,其余结点有且仅有一个前驱结