数据结构和算法的基础常识

- 日理万妓 2022-08-07 13:48 200阅读 0赞

1.基本的概念  
    1.数据            是客观描述事物的符号,是计算机中操作的对象,是能被计算机识别.并输入给计算机处理的集合  
    2.数据元素        是组成数据的,有一定意义的基本单位.在计算机中通常作为整体处理.也被称为记录  
    3.数据项        一个数据元素可以由若干个项组成,是数据不可分割的最小单位  
    4.数据对象        是性质相同的数据元素的集合,是数据的子集  
    5.结构            各个组成部分相互搭配和排列的方式  
    6.数据结构        是相互之间存在一种或多种特定关系的数据元素的集合  
        1.逻辑结构        是指数据对象中数据元素之间的相互关系  
            1.集合结构        集合结构中的元素同属于一个集合  
            2.线性结构        线性集合中的元素之间是一对一的关系  
            3.树形结构        树形结构中的元素之间存在一对多的层次关系  
            4.图形结构        图形结构中的元素之间存在多对多的关系  
        2.物理结构        是指数据的逻辑结构在计算机中的存储形式。  
            1.线性存储        是把数据元素存放在地址连续的单元里,其数据见的物理关系和逻辑关系是一致的  
            2.链式存储        是把数据元素存放在任意的存储单元里,这些存储单元可以是连续的,也可以是不连续的  
    7.数据类型        是指一组性质相同的值的集合及定义在此集合上的一些操作的总称  
    8.算法            是解决特定问题求解步骤的描述,在计算机中表现为指令有限序列,并且每条指令表示一个或多个操作  
        1.算法具有的五个特性  
            1.输入  
            2.输出  
            3.有穷性  
            4.确定性  
            5.可行性  
        2.好的算法应该具有的特性  
            1.正确性        能正确反应问题的需求,你能得到问题的正确答案  
            2.可读性        便于理解和交流  
            3.健壮性          
            4.高效率  
            5.低存储  
        3.算法的时间复杂度    公式:语句的总执行次数:T(n)=O(f(n));    f(n)为问题规模n的某个函数      
            大O记法的推导步骤  
                    1.用常数1取代运行时间中的所有加法常数  
                    2.在修改后的运行次数函数中,只保留最高阶项  
                    3.如果最高阶项存在且不是1,咋去除与这个项相乘的常数      
                1.O(1)            常数阶  
                2.O(log2n)/O(lbn)    对数阶  
                3.O(n)            线性阶  
                4.O(n\*log2n)        线性对数阶  
                5.O(n^2)        平方阶  
                6.O(n^3)        立方阶  
                7.O(n^k)        k次方阶  
                8.O(2^n)        指数阶      
        4.算法的空间复杂度    公式:    S(n)=O(f(n));            f(n)为语句关于n所占存储空间的函数  
    9.线性表(List)            零个或多个数据元素的有限序列.最前面的元素没有前驱.最后面的元素没有后继.其它元素有且只有一个前驱和后继  
    10.树        树(Tree)是n(n>=0)个节点的有限集合.n=0是称为空树  
        1.树的定义  
            1.根节点是唯一的,不能存在多个根节点  
            2.子树的个数不限制,但是他们节点是互不相交的  
        2.节点的定义  
            1.树的节点包含一个数据元素和若干指向子树的分支      
            2.节点拥有的子树的个数称为节点的度.度为0的节点称为叶子节点.度不为0的节点称为非终端节点或分支节点,树的度是树内各节点度的最大值  
            3.树中节点的最大层次称为树的深度或高度  
        3.树结构和线性结构的区别  
            1.线性结构的第一个数据元素没有前驱.树结构的根节点:无双亲,唯一  
            2.线性表中间元素只有也仅有一个前驱和一个后继.中间节点...有一个双亲或着多个孩子  
            3.线性表的最后一个数据元素.没有后继    ,叶节点.无孩子  
    11.二叉树的特点  
            1.每个节点最多有两棵子树  
            2.左子树和右子树是有顺序的  
            3.即使节点只有一棵子树,也要区分他为左子树还是右子树  
        1.斜树  
            1.所有节点都只有左子树的二叉树叫做左斜树  
            2.所有节点都只有右子树的二叉树叫做右斜树  
        2.满二叉树        在一棵二叉树中,如果所有分支节点都存在左子树和右子树.并且所有叶子都在同一个层上.这样的二叉树称为满二叉树  
  
            特点:1.叶子只能出现在最下一层  
                2.非叶子节点的度一定是2  
                3.在同样深度的二叉树中.满二叉树的节点和叶子是最多的  
        3.完全二叉树        对一棵具有N个节点的二叉树按层次编号,如果编号为i(1<=i<=N)的节点与同样深度的的满二叉树中编号为i的节点的位置完全相同.即为完全二叉树          
            特点1.叶子节点只能出现在最下面的两层  
                2.最下层的叶子一定集中在左部的连续部位  
                3.倒数第二层若为叶子节点.一定在右连续位置  
                4.如果节点度为1.那么该节点只有左子树,不可能有右子树  
                5.同样节点树的二叉树,完全二叉树的深度是最小的  
        4.二叉树的性质  
            1.在二叉树的第i层上最多2^i个节点  
            2.深度为i的二叉树,最多有2^(i+1)-1个节点  
            3.对任何一棵二叉树T,如果其叶子节点数为n0,度为2的节点数n2,则n0=n2+1;  
            4.具有n个节点的完全二叉树的深度为logn;  
        5.二叉树的先,中,后序遍历  
            1.先序遍历        先访问根节点.在先序遍历左树.在先序遍历右树  
            2.中序遍历        中序遍历左子树,在访问根节点,在中序遍历右子树  
            3.后序遍历        后序遍历左子树,在后序遍历右子树,在访问根节点