文档介绍：数据的存储结构有四种基本方式:顺序结构、链接结构、索引结构、散列结构。算法效率的度量分为:事后测量和事前估计。物理结构:指数据在计算机中存放的方式,即数据逻辑结构的物理存储方式。主要有顺序存储和链式存储。数据的操作指利用计算机对数据进行插入、删除、修改、查找、排序等操作。数据类型:一个数据的集合,以及定义于这个数据集合上的一组操作的总称。算法是对特定问题求解步骤的一种描述。算法是一个有穷的指令集,这些指令为解决某一特定任务规定了一个运算序列。算法特性:输入、输出、确定性、有穷性、可行性。算法评价:正确性、可读性、稳建性、时间复杂度、空间复杂度线性表是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满足下列条件:①有且仅有一个结点没有前驱,此结点称为根。②除根以外,其余结点有且仅有一个前驱结点。③所有结点可以有任意多个(含0个)后继。结点:包含一个数据值和若干指向其子树的分支。结点的度:结点拥有的子树个数。(degree)树的度:树内各结点的度的最大值。分支结点:度不为0的结点(也称非终端结点)。分单、双、三分支结点等。叶子结点:度为0的结点(也称终端结点)。孩子(后继)、双亲(前驱)、兄弟结点:一个结点的子树的根结点称为该结点的孩子结点。该