数据结构知识点_高校招聘数据库和数据结构知识点 - CSDN
精华内容
参与话题
  • 数据结构知识点大全

    2019-08-10 18:42:56
    数据结构知识点大全 本博文参考自【简书-龙猫小爷】如转载涉及版权问题,请联系博主删除! 作者:龙猫小爷 链接:https://www.jianshu.com/p/2469a4d9708e 数据结构绪论 数据结构的基本概念  数据结构...

    数据结构知识点大全


     本博文参考自【简书-龙猫小爷】如转载涉及版权问题,请联系博主删除!

    作者:龙猫小爷

    链接:https://www.jianshu.com/p/2469a4d9708e

     数据结构绪论

     数据结构的基本概念

      数据结构是一门研究非数值计算的程序设计问题中,计算机的操作对象以及它们之间的关系和操作的学科。

    数据元素是数据的基本单位,在计算机程序中通常作为一个整体进行考虑和处理。

    数据结构包含三个方面的含义:

      

    逻辑结构

      

    物理结构:数据的逻辑结构在计算机中的表示,称此为物理结构,或称存储结构。

      

      

    数据类型:一个值的集合以及定义在这个值集上的一组操作的总称。

      

    抽象数据类型:通常由用户定义,用以表示应用问题的数据模型以及定义在该模型上的一组操作。

      

    算法是描述计算机解决给定问题的操作过程,即为决解某一特定问题而由若干条指令组成的有穷序列。

      

    算法的效率分析:

    http://univasity.iteye.com/blog/1164707

    事后统计法:

    收集该算法实际的执行时间和实际占用空间的统计资料。

    事前分析估算法:

    在算法运行之前分析该算法的时间复杂度和空间复杂度,来判断算法的效率。

    时间复杂度分析:

      

      

      

    常见函数的时间复杂度按数量递增排列及增长率:

      


     

    线性表

    线性表的类型定义

      线性表是n(n>0)个相同类型数据元素构成的有限序列,其中n为线性表的长度。

    线性表的基本操作:   

      

      

     

    线性表的顺序表示和实现

    线性表的顺序存储结构:用一组地址连续的存储单元依次存储线性表的元素。

    线性表的顺序存储,也成为向量存储,又可以说是一维数组存储。线性表中结点存放的物理顺序与逻辑顺序完全一致,它叫向量存储。

    线性表顺序存储结构在插入或删除数据元素时比较繁琐,但是它比较适合存取数据元素。

     

    线性表的插入操作:

      在第i个元素之前插入一个元素时,需将第n至第i(共n-i+1)个元素向后移动一个位置。

       

    线性表的删除操作:

      删除第i个元素时需将从第i+1至第n(共n-i)个元素一次向前移动一个位置 

        

    线性表的链式表示和实现

    用一组任意的存储单元(可能不连续)存储线性表的数据元素。

    在链式存储结构中,每个存储结点不仅包含数据元素本身的信息,还必须包含每个元素之间逻辑关系的信息,即包含直接后继结点的地址信息(指针域)。

          

    逻辑顺序与物理顺序有可能不一致;属顺序存取的存储结构,即存取每个元素必须从第一个元素开始遍历,直到找到需要访问的元素,所以所花时间不一定相等。

      

     
        
     

    链表的创建方式:                                                                                                

      
     

    结点类的定义:                                                                                                  

      

    单链表的基本操作

    插入方式——头插法:                                                                                         

      

     插入方式——尾插法:                                                                                             

      

    查找运算——按序号查找:

      在链表中,即使知道被访问结点的序号i,也不能像顺序表中那么直接按序号i访问结点,而只能从链表的头指针除法,顺着链域next逐个结点往下搜索,直至搜索到第i个结点为止。链表不是随机存取结构,只能顺序存取 。

      

    查找运算——按数值查找:                                                                                      

      

    删除结点:

    将被删除结点的前驱指针连接被删除结点的后继指针

      

    循环链表

      表中尾结点的指针域指向头结点,形成一个环。从表中任意一个点出发都可以找到表中其他的结点。

      
     

      循环链表的操作和线性链表的操作基本一致,但循环链表中没有NULL指针,故遍历操作时,终止条件不再是判断p或p.next是否为空,而是判断他们是否等于某一指定指针,如头指针或尾指针。

    双向链表

      双向链表是在单链表的每个结点里再增加一个指向其直接前驱的指针域prior。这样就形成了链表中有两个方向不同的链,故称为双向链表。

       

    双线链表——头插法:                                                                                         

      

    双向链表——尾插法:                                                                                          

      
       
      

    插入操作

      
     

    栈和队列

    栈的概念

      栈是限制在表的一端进行插入和删除运算的线性表,通常称插入、删除的这一端为栈顶,另一端为栈底。当表中没有元素时成为空栈。 

      
     

    栈的进出顺序判断:

      
     

    栈的基本操作:

      

    顺序栈

      顺序栈利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素,同时由于栈的操作的特殊性,还必须附设一个位置指针top来动态地指示栈顶元素的顺序栈中的位置。通常以top=0表示空栈。                                                       

      
     
       

    顺序栈的基本运算:

      
     
      
     

    链栈:

      采用链表作为存储结构实现的栈。为便于操作,采用带头结点的单链表实现栈。因为栈的插入和删除操作仅限制在表头位置进行,所以链表的表头指针就作为栈顶指针。  

      

    顺序栈和链式栈的比较:

      实现链式栈和顺序栈的操作都是需要常数时间,即时间复杂度为O(1),主要从空间和时间两个方面考虑。初始时,顺序堆栈必须说明一个固定的长度,当堆栈不够满时,造成一些空间的浪费,而链式堆栈的长度可变则使长度不需要预先设定,相对比较节省空间,但是在每个节点中设置了一个指针域,从而产生了结构开销。

    队列的概念

      队列是一种先进先出的线性表,它只允许在表的一端进行插入,而在另一端删除元素。在队列中,允许插入数据一端成为队尾(rear),允许删除的那一端称为队头(front)。

           

     队列的基本操作:

       

      

    顺序队列

      顺序队列利用一组地址连续的存储单元依次存放自队首到队尾的数据元素,同时由于队的操作的特殊性,还必须附两个位置指针front和rear来动态地指示队首元素和队尾元素在顺序队列中的位置。通常front=rear表示空队列。

      

      队列同堆栈一样也有上溢和下溢现象。以外,队列中还存在“假溢出”现象。所谓“假溢出”是指在入队和出队操作中,头尾指针不断增加而不减小或只减小而不增加,致使被删除元素的空间无法重新利用,最后造成队列中有空闲空间,但是不能够插入元素,也不能够删除元素的现象。

    链式队列:

      采用链表作为存储结构实现的队列。为便于操作,采用带头结点的单链表实现队列。因为队列的插入和删除操作位置不同,所以链表需要设置表头指针和表尾指针分别指队首和队尾。

    循环队列:

      假设向量的空间是m,只要在入出队列时,将队首和队尾的指针对m做求模运算即可实现队首和队尾指针的循环,即队首和队尾指针的取值范围是0到m-1之间。

      

     
      
     

    判断队空和队满的方法  

     
     

    数组和广义表

    数组的定义

      数组是我们熟悉的数据类型,数组中各元素具有统一的类型,并且数组元素的下标一般具有固定的上界和下界,因此,数组的处理比其它复杂的结构更为简单。

      任何数组A都可以看作一个线性表。数组维数确定后,数据元素个数和元素之间的关系不再发生改变,适合顺序存储。

    数组的基本操作  

      

    数组的顺序表示和实现

    行优先顺序 

      

    列优先顺序

      

    矩阵的压缩存储

      有些特殊矩阵,非零元素呈某种规律分布或者矩阵中出现大量的零元素的情况下,会占用许多单元去存储重复的非零元素或零元素,这对高阶矩阵会造成极大的浪费,为了节省存储空间,对这类矩阵进行压缩存储——即为多个相同的非零元素只分配一个存储空间;对零元素不分配空间。

    特殊矩阵:

      所谓特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵,如对称矩阵、三角矩阵、对角矩阵等等。

      

    对称矩阵 

      

      对称矩阵中元素关于主对角线对称,故只要存储矩阵中上三角或下三角中的元素,让每两个对称的元素共享一个存储空间,这样能节约近一半的存储空间。

      n2 个元素可以压缩到 n(n+1)/2个空间中。

        

      

    三角矩阵

      以主对角线划分,三角矩阵有上三角和下三角两种。上三角矩阵它的下三角中的元素均为常数。下三角矩阵正好相反,它的主对角线上方均为常数。

      

      
     
      

    稀疏矩阵 

      

      除了记录非零元素的值之外,还必须同时几下它所在的行和列的位置。稀疏矩阵的存储方法一般有三种:三元组法、行逻辑连接顺序表和十字链表法。

      

    广义表

      是由零个或多个原子或子表组成的优先序列,是线性表的推广。

       

     
      
     
      
     
      
      
      
       
       

    广义表的存储结构

      广义表中的数据元素可以具有不同的结构,因此,难以用顺序存储结构表示,通常采用链式存储结构,每个数据元素可用一个节点表示。由于广义表中有两种数据元素,因此需要有两种结构的节点——一种是表结点,一种是原子结点。

    表结点由三个域组成:

    标志域、指示表头的指针的指针域和指示表尾的指针域;而原子域只需两个域:标志域和值域。

      

      

      
     

    表结点由三个域组成:

    标志域、指示表头的指针域和指向下一个元素的指针;原子结点的三个域为:标志域、值域和指向下一个元素的指针。

       

      
     

      树

    树的定义 

     

    树的逻辑表示:

      树形表示法、

      文氏图表示法、

      凹入表示法、

      括号表示法。

       

      
       
      

    结点:

      表示树中的元素,包括数据项及若干指向其子树的分支。

    结点的度:

      结点拥有的子树树;树的度:一棵树中最大的结点度数

      

    叶子结点:

      度为0的结点;

    分支结点:

      度不为0的结点;

    孩子:

      结点子树的根称为该结点的孩子;双亲:孩子结点的上层结点叫该结点的双亲;兄弟:同一双亲的孩子。

    深度:

      树中结点的最大层次数。                                                               

       

     

    有序树:

      树中各结点的子树从左至右是有次序的,不能互换。否则称为无序树。

    树的性质

      树中的结点数等于所有结点的度数加1。

        

      度为m的树中第i层上至多有mi-1 个结点(i>=1)。

      

       
      

    二叉树的概念

       
     

     满二叉树:

      定义—— 一棵深度为k且具有2k-1个结点的二叉树。特点——每一层上的结点数都是最大结点数。

    完全二叉树:

      定义—— 深度为k,有n个结点的二叉树当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时,称为完全二叉树。

    二叉树的性质 

      
     

    二叉树的第i层上至多有2i-1(i>=1)个结点。

    深度为K的二叉树至多有2k-1个结点。

    对任何一棵二叉树T,如果其叶子数为n0,度为2的结点数为n2,则n0=n2+1。

        

      
      
       
      一个有n个结点的完全二叉树,编号最大的分支结点的编号是 
       一个有n个结点的完全二叉树,n0的个数是不小于n/2的最小整数。

    二叉树的存储结构

      用一组连续的存储单元存储二叉树的数据元素。在存储之前对二叉树的所有结点安排一个适当的序列,使得结点在这个序列中的相互位置能反应出结点之间的逻辑关系。 

      

     特点:
      结点间关系蕴含在其存储位置中;浪费空间,适于存满二叉树和完全二叉树。

    二叉树的链式存储结构

      用一个链表来存储一棵二叉树,二叉树中每一个结点用链表中的一个链结点来存储。 

      
       
     
      
     

    遍历二叉树

    遍历方法:

       
     

    利用遍历结果确定二叉树: 

      
     

    先序遍历:

    //先序遍历递归算法
    
    void preorder(Tree t){
    
        if(t==null)
    
            return;
    
        visit(t);
    
        preorder(t.left());
    
        preorder(t.right());
    
    }
    
    
    //先序遍历非递归算法
    void PreOrderUnrec(Bitree t)
    {
        //创建栈来存放树的结点
        SqStack s;
        StackInit(s);
        p=t;
        
        while (p!=null || !StackEmpty(s))
        {
            while (p!=null)             //遍历左子树
            {
                visite(p->data);
                push(s,p);
                p=p->lchild;       
            }//endwhile
            
            if (!StackEmpty(s))         //通过下一次循环中的内嵌while实现右子树遍历
            {
                p=pop(s);
                p=p->rchild;        
            }//endif
                    
        }//endwhile 
        
    }//PreOrderUnrec

     

    中序遍历

    //中序遍历递归算法
    void inorder(Tree t){
        if(t==null)
            return;
        inorder(t.left());
        visit(t);
        inorder(t.right());
    }
    
    
    // 非递归
    
    void InOrderUnrec(Bitree t)
    {
        //创建栈来存放树的结点
        SqStack s;
        StackInit(s);
        p=t;
        
        while (p!=null || !StackEmpty(s))
        {
            while (p!=null)             //遍历左子树
            {
                push(s,p);
                p=p->lchild;       
            }//endwhile
            
            if (!StackEmpty(s))         //通过下一次循环中的内嵌while实现右子树遍历
            {
                p=pop(s);
                visite(p->data);        //访问根节点
                p=p->rchild;        
            }//endif
                    
        }//endwhile 
        
    }//InOrderUnrec

     后序遍历

    后序遍历递归算法
    void inorder(Tree t){
        if(t==null)
            return;
        inorder(t.left());
        inorder(t.right());
        visit(t);
    }
    
    //后序遍历非递归算法
    /*对于任一结点P,将其入栈,然后沿其左子树一直往下搜索,直到搜索到没有左孩子的结点,此时该结点出现在栈顶,但是此时不能将其出栈并访问,因此其右孩子还为被访问。所以接下来按照相同的规则对其右子树进行相同的处理,当访问完其右孩子时,该结点又出现在栈顶,此时可以将其出栈并访问。这样就保证了正确的访问顺序。可以看出,在这个过程中,每个结点都两次出现在栈顶,只有在第二次出现在栈顶时,才能访问它。因此需要多设置一个变量标识该结点是否是第一次出现在栈顶。*/
    void postOrder2(BinTree *root)    //非递归后序遍历
    {
        stack<BTNode*> s;
        BinTree *p=root;
        BTNode *temp;
        while(p!=NULL||!s.empty())
        {
            while(p!=NULL)              //沿左子树一直往下搜索,直至出现没有左子树的结点 
            {
                BTNode *btn=(BTNode *)malloc(sizeof(BTNode));
                btn->btnode=p;
                btn->isFirst=true;
                s.push(btn);
                p=p->lchild;
            }
            if(!s.empty())
            {
                temp=s.top();
                s.pop();
                if(temp->isFirst==true)     //表示是第一次出现在栈顶 
                 {
                    temp->isFirst=false;
                    s.push(temp);
                    p=temp->btnode->rchild;    
                }
                else                        //第二次出现在栈顶 
                 {
                    cout<<temp->btnode->data<<" ";
                    p=NULL;
                }
            }
        }    
    }

     

    线索二叉树

      利用二叉链表的空指针域,建立指向该结点的前驱/后继结点的指针,方便二叉树的线性化使用。 

       

       对二叉链表以某种次序遍历使其变为线索二叉树的过程叫做线索化。有先序线索二叉树、中序线索二叉树(更实用)和后序线索二叉树三种。
      

    建立中序线索二叉树      

      
     

       

      
         
     
      
       

    树的存储结构

    双亲表示法:

      用一组连续空间存储树的结点,每个节点包含两个域——数据域用来存放结点本身信息,双亲域用来指示本结点的双亲结点在数组中位置。

       

    孩子表示法:

      采用孩子链表,每个结点的孩子结点用单链表存储,再用含n个元素的结构数组指向每个孩子链表。

      

    带双亲的孩子链表

       

    孩子兄弟表示法:

      用二叉链表作为树的存储结构。链表中结点的两个链域分为指向该结点的第一个孩子结点和下一个兄弟结点。

      

     

    森林与二叉树的转换

    将树转换为二叉树 

      
     
      

    将二叉树转换为树:

      
     
      
     

    森林转换成二叉树: 

      
     
      

    二叉树转换成森林   

      
     
      

    哈夫曼树

      结点的权及带权路径长度:若将树中结点赋给一个有着某种含义的数值,则这个数值称为该结点的权。结点的带权路径长度为:从根节点到该结点之间的路径长度与该结点的权的乘积。

          

        
     

     在一棵二叉树中,若带权路径长度达到最小,称这样的二叉树为最优二叉树,也称哈夫曼树。

          

     

    图的概念

      图是一种较线性表和树更为复杂的数据结构,在图形结构中,结点之间关系可以是任意的,图中任意两个数据元素之间都可能相关。

      

    有向图和无向图 

      
     
      

      若无向图中的每两个顶点之间都存在着一条边,则称该无向图称作完全无向图;显然完全无向图中包含着e=n(n-1)/2条边。若有无向图中的每两个顶点之间都存在方向相反的两条边,则称该有向图称作完全有向图;显然完全有向图中包含有e=n(n-1)条边。

      
     

      与图的边或弧相关的数叫做权,带权的图称为网。

      

     
      
     
      
     

      对于有向图而言,度又分为出度和入度。顶点的出度——以顶点v为弧尾的弧的数目;顶点的入度——以顶点v为弧头的弧的数目;顶点的度为该顶点的出度和入度的和。

     
       
      
     

      在无向图G中,如果从顶点v到顶点w存在路径,则称v到w是连通的。若图G中任意两个顶点之间都有路径相通,则称为连通图。

      若无向图为非连通图,则图中各个极大连通子图称作此图的连通分量。任何连通图的连通分量只有一个,即本身,而非连通图则有多个连通分量。 

      

    在有向图中,若任意两个顶点之间都存在一条有向路径,则称此有向图为强连通图。

    若有向图为非强连通图,其各个强连通子图称为它的强连通分量。

      
     

    图的存储结构——邻接矩阵

    邻接矩阵是表示顶点之间相邻关系的矩阵。

      

    无向图的邻接矩阵:

      

    有向图的邻接矩阵:

      

    网的邻接矩阵:

           

        
     
      

    图的存储结构——邻接表

      邻接表存储方法是一种顺序分配与链式分配相结合的存储方法。它包括两部分:一部分是单链表,用来存放边的信息;另一部分是数组,主要用来存放顶点本身的数据信息。                                                                            

      

    无向图邻接表:

      

    有向图的邻接表:

      
      

    图的存储结构——十字链表

      十字链表是有向图的另一种链式存储结构。可以看成是将有向图的邻接表和逆邻接表结合起来得到的一种链表。在十字链表中,每条弧和每个顶点分别对应着一个结点。 

      
      
        

    图的存储结构——邻接多重表

      邻接多重表是无向图的另一种链式存储结构。邻接多重表和十字链表一样,每条边和每个顶点分别对应着一个结点。  

      
     
       
       

    图的遍历

      从图中某个顶点出发游历图,访遍图中其余顶点,并且使图中的每个顶点仅被访问一次的过程。

      根据搜索方法的不同,图的遍历有两种:深度优先搜索(DFS)和广度优先搜索(WFS)。

    深度优先搜索 

      
      
      
     
      
     

    连通图深度优先搜索的算法:  

      
     
      
      

    广度优先搜索 

      

      广度优先搜索是一种分层的搜索过程,每向前走一步可能访问一批顶点,不像深度优先搜索那样有回退的情况。因此,广度优先搜索不是一个递归的过程,其算法也不是递归的。                      

      

    连通图的广度优先搜索算法: 

       

    非连通图广度优先搜索:

      

    无向图的连通分量和生成树

    连通图生成树:

      一个连通图的生成树是一个极小连通子图,它含有图中全部顶点,但只有构成一棵树的n-1条边。 

      
     
      
     

      当无向图为非连通图时,从图中某一顶点除法,利用深度优先搜索算法或广度优先搜索算法不可能遍历到图中的所有顶点,只能访问到该顶点所在的极大连通子图的所有顶点,该极大连通子图称为无向图的一个连通分量。

      

    使用不同的遍历图的方法,可以得到不同的生成树;从不同的顶点出发,也可能得到不同的生成树。 

      

    最小生成树

      在连通网的众多生成树中,各边权值之和最小的生成树称为最小代价生成树,简称最小生成树。

      

    生成最小生成树算法——普里姆算法:  

      
      

    生成最小生成树算法——克鲁斯卡尔算法:

       
      

    有向无环图

      一个无环的有向图称为有向无环图,简称DAG图。

      

    拓扑排序

      在一个有向图中,若用顶点表示活动,有向边表示活动间的先后关系,称该有向图叫做顶点表示活动的网络,简称AOV网。

      
       按照有向图给出的次序关系,将图中顶点排成一个线性序列,对于有向图中没有限定次序关系的顶点,则可以人为加上任意的次序关系。由此所得顶点的线性序列成为拓扑有序序列。

    拓扑排序:

    由某个集合上的一个偏序(集合中仅有部分成员之间可以比较)得到该集合上的一个全序(集合中全体成员之间均可以比较)的操作称为拓扑排序。 

      

    拓扑排序的算法:    

      
       
     
       

    关键路径

      在一个有向图中,若用顶点表示事件,弧表示活动,权表示活动持续时间,称该有向图叫做边表示活动的网络,简称为AOE网。

      
     
     
     
     
      
     
     
     

     查找 

    概述

    查找表:

      由同一类型的数据元素(或记录)构成的集合。

       
      
     
      

    静态查找表

      静态查找是指在静态查找表上进行的查找操作,在查找表中满足条件的数据元素的存储位置或各种属性。

    静态查找表的查找算法主要有: 

      

    顺序查找:

      从表的一端开始,顺序扫描线性表,依次将扫描到的关键字和给定值k进行比较,若当前扫描到的关键字与k相等,则查找成功;若扫描结束后,仍未找到关键字等于k的记录,则查找失败。

      
     
      
     

    折半查找:

      对给定值k,逐步确定待查记录所在区间,每次将搜索空间减少一半,直到查找成功或失败为止。 

       
      
       
      

    分块查找

      
      
     

    动态查找表:

      表结构在查找过程中动态生成的这样一种查找表。实现动态查找方法:二叉排序树、平衡二叉树、B-树和B+树。

    二叉排序树 

      定义:左子树的所有结点均小于根的值;右子树的所有节点均大于根的值;它的左右子树也分别为二叉排序树。 

      
     

    二叉排序树插入新结点的过程:

      

    二叉排序树插入新节点递归算法:

      
       

    二叉排序树删除结点的算法: 

      
       

    二叉排序树查找算法分析:  

       

    平衡二叉树 

      平衡二叉树又称为AVL树,设二叉树中结点的左子树和右子树的深度分别为HL和HR。

     

       
      

      若在构造二叉排序树的同时,使其始终保持为AVL树,则此时的二叉排序树为平衡的二叉排序树。将一棵非平衡二叉排序树调整成平衡二叉排序树的“旋转”,分为:LL平衡旋转、RR平衡旋转、LR平衡旋转、RL平衡旋转。 

      
       
      
       
       
      

    B-树:

    http://haicang.blog.51cto.com/2590303/1134864

      B-树又称基本B树或多路平衡查找树。它是构造大型文件系统索引结构的一种数据结构类型,适合在磁盘等直接存取设备上组织动态的查找表。

         
       
        
         该公式包括没有任何关键字的叶子结点。

    B-树的查找算法思路:    

      
     
      

    B-树的查找效率取决于以下两个因素:包含k的结点在B-树种所在的层数h;结点中ki的个数n。 

      

    B-树的生成:

     
      
      
     
     B-树的删除:

     

     

      

    B+树

     

      B+树是B-树的变形,目的在于有效地组织文件的索引结构。

    1. m阶B+树与B-树的差异:                                                                                    
    2.  
    3. B+树种可以有两种查找方式:顺序查找——类似单链表的查找,直接在数据层进行查找。随机查找——类似B-树的查找,不同的是搜索到索引层的key与k相等时,还得继续搜索下去,直到数据层为止。
    4.  

    哈希表

    1.  
       

    2. 哈希表,根据设定的哈希函数H(key)和处理冲突的方法将一组关键字key映射到一个有限的连续的地址集上,并以关键字key在地址集中的“像”作为记录在表中的存储位置,这种表便称为哈希表,这一映射过程称为哈希造表或散列,所得存储位置称哈希地址或散列地址。 
    3. 将不同的关键码映射到同一个哈希地址上,该现象称为冲突。

    哈希函数的构造方法

    1. 常用的哈希函数构造方法有:直接定址法、除留余数法、乘余取整法、数字分析法、平方取中法、折叠法、随机数法。
    2. 直接定址法:
       
       
    3. 除留余数法:                                                                                              
       
       
    4. 乘余取整法:                                                                                                
       
       
    5. 数字分析法:                                                                                           
       
       
    6. 平方取中法:                                                                                            
       
       
    7. 叠加法:                                                                                                             
       
       
          
    8. 随机数法:                                                                                                    
       
       

    处理冲突的方法

    1. 开放定址法、链地址法、再哈希法、建立一个公共溢出区
    2. 开放定址法:                                                                                          
       
       
       
       
       
       
    3. 链地址法:                                                                                                        
       
       
       
    4. 再哈希法:                                                                                                 
       
       
    5. 建立一个公共溢出区:                                                                                           
       
       

    红黑树

    1. 红黑树,一种二叉查找树,但在每个结点上增加一个存储位表示结点颜色,可以是Red或Black。通过对任何一条从根到叶子的路径上各个结点着色方式的限制,红黑树确保没有一条路径会比其他路径长出两倍,因而是接近平衡的。
       
       
    2. 红黑树虽然本质上是一棵二叉查找树,但它在二叉查找树的基础上增加了着色和相关的性质使得红黑树相对平衡,从而保证了红黑树的查找、插入、删除的时间复杂度最坏为O(log n)。红黑树和AVL树的区别在于它使用颜色来标识结点的高度,它所追求的是局部平衡而不是AVL树中的非常严格的平衡。
    3. 红黑树的五个性质保证了红黑树的高度始终保持在logn:
       
       
       
       
    4. 红黑树的旋转操作:红黑树的旋转操作和AVL树一样,分为LL、RR、LR、RL四种旋转类型,差别在于旋转完成后改变的是结点的颜色,而不是平衡因子。
    5. 红黑树的插入和删除:http://blog.csdn.net/eric491179912/article/details/6179908 

    排序

    排序概述

    排序的分类:内部排序和外部排序(若待排序记录都在内存中,称为内部排序;若待排序记录一部分在内存,一部分在外存,则称为外部排序)。稳定排序和不稳定排序。 

     

      内部排序的算法:插入排序(希尔排序)、交换排序(快速排序)、选择排序(堆排序)、归并排序、基数排序。

    插入排序

    思想:每次将一个待排序的对象,按其关键码大小,插入到前面已经排好序的一组对象的适当位置上,直到对象全部插入为止。

    具体实现算法:直接插入排序、折半插入排序、希尔排序

    直接插入排序:

    void InsertSort(int a[]){
        int i,j;
        //按照有小到大的顺序排序
        for(i=2;i<a.length;i++){
            //找到无序表的第一个位置
            if(a[i]<a[i-1]){
                a[0]=a[i];
                //将无序表依次向后移动
                for(j=i-1;a[0]<a[j];j--){
                    a[j+1]=a[j];
                }
                //将数据插入相应位置
                a[j+1]=a[0];
            }
        }
    }

     

    该算法的时间复杂度是:O(n2)

     

    折半插入排序:                                                                                           

    void BInsertSort(int a[]){
        int i,j,high,low;
        for(i=2;i<a.length;i++){
            a[0]=a[i];        
            low=1;
            high=i-1;
            int min;
            while(low<=high){        //使用折半查找到插入的位置
                min=(high+low)/2;
                if(a[0]<a[min])
                    high=min-1;
                else
                    low=min+1;
            }
            for(j=i-1;j=>high+1;j++)    //插入的位置是在high位置之后
                a[j+1]=a[j];
            a[high+1]=a[0];
        }
    }

     

    希尔排序:                                                                                                

     
     
    从排序过程可以看出,希尔排序的一个特点是:子序列的构成不是简单地“逐段分割”,而是将相隔某个“增量”的记录组成一个子序列。
    void SheelSort(int a[],int dx){
        //这是对直接插入排序的修改
        //dx表示增量
        //当j<=0时,插入位置已经找到
        int i,j;
        for(i=dx+1;i<a.length;i++){
            if(a[i]<a[i-dx]){
                a[0]=a[i];
                for(j=i-dx;j>0&&a[0]<a[j];j-=dx)
                    a[j+dx]=a[j];
                a[j+dx]=a[0];
            }
        }
    }

    交换排序

    两两比较待排序记录的关键码,如果发生逆序(即排列顺序与排序后次序正好相反),则交换之,直到所有记录都排好序为止。

    冒泡排序:

    void bubbleSort(int a[]){
        int i,j;
        for(i=1;i<a.length-1;i++){
            for(j=1;j<a.length-i;j++){
                if(a[j]>a[j+1]){
                    a[0]=a[j];
                    a[j]=a[j+1];
                    a[j+1]=a[0];
                }
            }
        }
    }

    快速排序:

     
    void Partition(int a[],int low,int high){
        //这只是一趟快速排序的算法
        a[0]=a[low];
        while(low<high){
            //从高位往低位扫描,找到数值小于关键字的位置,与low位置交换
            while(low<high&&a[0]<=a[high])
                high--;
            a[low]=a[high];
            //从低位往高位扫描,找到数值大于关键字的位置,与high位置交换
            while(low<high&&a[low]<=a[0])
                low++;
            a[high]=a[low];
        }
        //最后将关键字放入数组中
        a[low]=a[0];
    }

    快速排序平均时间复杂度和最好时间复杂度为:O(log2n),最坏时间复杂度为O(n2)。

    选择排序

    不断从待排记录序列中选出关键字最小的记录插入已排序记录序列的后面,直到n个记录全部插入已排序记录序列中。

    简单选择排序

    堆排序:

      借助于完全二叉树结构进行的排序,是一种树形选择排序。其特点是——在排序过程中,将R[1...N]看成是一棵完全二叉树的顺序存储结构,利用完全二叉树双亲结点和孩子结点之间的内在关系,在当前无序区中选择关键字最大(或最小)的记录。

      
      
     

      堆的根节点是堆中元素值最小(或最大)的结点,称为堆顶顶点;从根节点到每个叶节点的路径上,元素的排序序列都是递减(或递增)有序的。

      

    建立一个堆排序的方法:                                                                               

      
      
      

    堆排序的过程:                                                                                       

      
      

    堆排序算法实现:

    void HeapAdjust(int *a,int i,int size)  //调整堆 
    {
        int lchild=2*i;       //i的左孩子节点序号 
        int rchild=2*i+1;     //i的右孩子节点序号 
        int max=i;            //临时变量 
        if(i<=size/2)          //如果i不是叶节点就不用进行调整 
        {
            if(lchild<=size&&a[lchild]>a[max])
            {
                max=lchild;
            }    
            if(rchild<=size&&a[rchild]>a[max])
            {
                max=rchild;
            }
            if(max!=i)
            {
                swap(a[i],a[max]);
            }
        }        
    }
    
    void BuildHeap(int *a,int size)    //建立堆 
    {
        int i;
        for(i=size/2;i>=1;i--)    //非叶节点最大序号值为size/2 
        {
            HeapAdjust(a,i,size);    
        }    
    } 
    
    void HeapSort(int *a,int size)    //堆排序 
    {
        int i;
        BuildHeap(a,size);
        for(i=size;i>=1;i--)
        {
            //cout<<a[1]<<" ";
            swap(a[1],a[i]);           //交换堆顶和最后一个元素,即每次将剩余元素中的最大者放到最后面 
              //BuildHeap(a,i-1);        //将余下元素重新建立为大顶堆 
              HeapAdjust(a,1,i-1);      //重新调整堆顶节点成为大顶堆
        }
    } 
      

    归并排序

      “归并”的含义是将两个或两个以上的有序表合并成一个新的有序表。

     

      
      

    两个有序表的合并算法Merge():              

                                             

      
      
      
     

    算法分析:                                                                                                 

      

    基数排序

      基数排序是一种借助多关键字排序的思想对单逻辑关键字进行排序的方法,即先将关键字分解成若干部分,然后通过对各部分关键字的分别排序,最终完成对全部记录的排序。

    多关键字的排序: 

      
      
     

    链式基数排序:                            

                                      

      
      
      

    排序算法总结  

      
     

     

    转载于:https://www.cnblogs.com/wjw1014/p/10181252.html

    展开全文
  • 数据结构--知识点总结(汇总)

    千次阅读 2018-07-15 22:48:18
    栈和队列 树 查找 图

    数据结构–知识点总结(汇总)

    概述
    线性表
    栈和队列
    数组、串、广义表
    集合与字典


    查找
    排序

    展开全文
  • 数据结构知识点整理

    2019-12-10 16:14:37
    数据结构 一、什么是数据结构 数据结构是一门研究非数值计算的程序设计问题中计算机的数据元素以及他们之间的关系和运算的学科。 数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种...

    数据结构

    一、什么是数据结构

    1. 数据结构是一门研究非数值计算的程序设计问题中计算机的数据元素以及他们之间的关系和运算的学科。

    2. 数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。

    3. 数据结构是一门研究非数值计算的程序设计问题的学科,主要研究数据的逻辑结构、存储结构和运算方法

    4. 数据结构被定义为(D,R)D是数据的有限集合,R是D上的逻辑关系的有限集合。

    二、数据的逻辑结构

    1、基本概念

    1. 数据 是描述客观事物的数字、字符以及所有能输入到计算机中并被计算机接受的各种符号集合的统称。
    2. 数据元素(节点) 一个事物的一组数据,是数据集合中的一个“个体”,是数据的**基本单位*
    3. 数据项(字段)数据不可分割、具有独立意义的最小数据单位,对数据元素属性的描述
    4. 数据结构 相互之间存在一种或多种特定关系的数据元素集合
    5. 数据对象 性质相同的数据元素的集合,是数据的一个子集
    6. 关键字 一个数据元素中,能够识别该元素的一个或多个数据项
    7. 主关键字 能够唯一识别数据元素的关键字

    2、逻辑结构分类

    • 集合 结构中的数据元素除了同属于一种类型外,别无其它关系。(不存在数据之间的关系)
    • 线性结构 数据元素之间一对一的关系
    • 非线性结构 数据元素之间存在多对多的关系
      • **树形结构 ** 数据元素之间一对多的关系
      • 图形结构 数据元素之间多对多的关系

    三、数据的存储结构

    1、基本概念

    数据元素及其关系在计算机中的存储表示或实现称为数据的存储结构,也称为物理结构

    2、存储结构形式

    • 顺序存储

      占用连续存储单元,借用元素在存储器中的相对位置来表示数据元素之间的逻辑关系 [最简单的实现:一维数组]

    • 链式存储

      借助知识元素存储地址的指针来表示数据元素之间的逻辑关系

      特点:数据元素不一定存在地址连续的存储单元,存储处理得灵活性较大

    • 索引存储

      原有存储数据结构的基础上,附加建立一个索引表,索引表的每一项都由关键字和地址组成(索引表反映了按某一个关键字递增或递减排列的逻辑次序)

      作用:提高数据的检索速度

    • 散列存储

      构造散列函数来确定数据存储地址或查找地址

      散列存储的内存存放形式称为散列表,也称为哈希表

    四、算法

    1、基本概念

    算法是对特定问题求解步骤的一种描述,是指令的有限序列。其中每一条指令表示一个或多个操作。

    2、算法的特性

    • 有穷性:一个算法必须在有限的步骤之后结束,并且每一步在有限时间内完成。
    • 稳定性:算法的每一条指令必须在有确切的定义,无二义性。
    • 可行性:算法所描述的操作可以通过有限次的运算来实现,并得到正确的结果。
    • 输入:一个算法具有零个或多个输入。
    • 输出:一个算法具有一个或多个输出。

    3、算法的目标

    • 正确性:算法的执行结果应当满足预先设定的功能和要求。
    • 可读性:一个算法应当思路清晰、层次分明、易读易懂。
    • 健壮性(鲁棒性):当发生误操作输入非法数据时,应能适当的反应和处理,不至于引起莫名其妙的后果
    • 高效性:对同一个问题,执行的时间越短,算法的效率就越高。
    • 低存储量:完成相同的功能,执行算法所占用附加存储空间尽可能的少。

    4、算法的效率的度量

    算法效率的度量可以分为事先估算法事后统计法

    5、算法效率 --时间复杂度

    算法中原操作重复执行的次数的规模n的某个函数f(n),算法的时间复杂度T(n)的数量级可记作: T(n) = 0(f(n))

    他表示随着问题规模的扩大,算法执行时间的增加率和f(n)的增长率相同,称为算法的渐进时间复杂度,简称时间复杂度。

    6、算法效率 --空间复杂度

    一个程序的空间复杂度是指程序运行从开始到结束所需要的存储空间。类似于算法的时间复杂度,吧算法所需存储空间的量度记作: S(n) = 0(f(n))

    五、线性表

    1、基本概念

    线性表的插入、删除操作不受限制。

    线性表是由n(n>=0)个类型相同的数据元素a0,a1,…an-1组成的有限序列,记作(a0,a1,…an-1),其中,元素ai的数据类型可以是整数、浮点数、字符或类;n是线性表的元素个数,称为线性表长度。若n=0,则为空表;若n>0,则ai<0<i<n-1)有且仅有一个前驱元素ai-1和后继元素ai+1a0没有前驱元素,an-1没有后继元素

    2、顺序表

    2.1 顺序表定义

    线性表的顺序存储是用一组地址连续的存储单元依次存储线性表的数据元素,我们把这种形式存储的线性表称为顺序表。顺序表中各个元素的物理顺序和逻辑顺序是一致的。 随机存取指访问时可以按下标随机访问,存储和存取是不一样的。如果是存储,则是指按顺序的,如果是存取,则是可以随机的,可以利用元素下标进行

    ​ 设a1的存储地址LOC(a1)为首地址B,每个元素占d个存储单元,则i个数据元素的地址为:

    ​ LOC(ai)=LOC(a1)+(i-1)x d 1<=i<=n

    ​ 即: LOC(ai)=B+(i-1)x d 1<=i<=n

    只要知道顺序表首地址和每个数据元素所占存储单元的个数,就可以求出第i个数据元素的存储地址。顺序表具有按数据元素的序号随机存取的特点

    2.2 顺序表的基本运算

    • 插入运算

      ​ 表长为n的表,在i (1<=i<=n+1)处插入新结点,之后结点需要后移动n-i+1个元素 平均时间复杂度 O(n)

      ​ 【1、检查表是否已满 2、插入的位置是否有效 3、必须从表的最后一结点开始移动】

    • 删除运算

      ​ 表长为n的表,在i (1<=i<=n)处删除结点,之后结点需要前移动n-i个元素 平均时间复杂度 O(n)

      ​ 【1、检查表是否为空 2、删除的位置是否有效】

    • 查找运算

      ​ 元素下标查找,速度最快 时间复杂度O(1)

      ​ 按值查找 需进行元素值的比较,查找整个表 时间复杂度O(n)

    3、线性链表

    3.1 线性链表定义

    (1)用一组任意的存储单元存储线性表的数据元素,存储单元可以是连续的,也可以不连续,因此,链表中结点的逻辑次序和物理次序不一定相同。

    (2) 为了能正确表示结点间的逻辑关系,在存储每个结点值的同时,还必须存储指示其后继结点的地址。data域是数据域,用来存放结点的值。next是指针域(亦称链域),用来存放结点的直接后继的地址(或位置)。不需要事先估计存储空间大小。

    3.2 单向链表

    每个结点的存储地址是存放在其前驱结点next域中,而开始结点无前驱,故应设头指针head指向开始结点(头结点)。同时,由于最后一个结点无后继,故结点的指针域为空,即NULL。头插法建表(逆序)、尾插法建表(顺序)。增加头结点的目的是算法实现上的方便,但增大了内存开销。

    • 单向链表的存取必须从头指针开始
    • 头指针:指向链表中第一个结点(头结点或无头结点时的开始结点)的指针。
    • 头结点:在开始结点之前附加一个结点。
    • 开始结点:在链表中,存储第一个数据元素(a1)的结点。
    • 判空:p->next = NULL;
    • 缺点:只能顺时针往后寻找其他结点,若要寻找结点的前驱,则需要从表头指针出发。
    3.21 单向链表的基本运算
    • 插入运算

      1. 头插法建表(逆序)

        从一个空表开始,重复读入数据,生成新结点,将读入数据存放在新结点的数据域中,然后将新结点插入到当前链表的表头结点之后,直至读入结束标志为止

        //伪代码
        LinkNode *head; //头指针
        var x = "数值"
        LinkNode s = new LinkNode()
        s->data = x;	//数值存到新结点的数据域中
        s->next = head;	//将头指针所指向的下一个结点的地址,赋给新创建结点的next 
        head = s;		//头指针指向s结点
        
        

      //2,3步颠倒导致新结点地址域指向自己

      
      2. **尾插法建表(顺序)[常用]** 
      
      将新结点插到当前单链表的表尾上。增加一个尾指针,使之指向当前单链表的表尾
      
      ```c
      //伪代码
      LinkNode *real; //尾指针
      var x = "数值"
      LinkNode s = new LinkNode()
      s->data = x;  //数值存到新结点的数据域中
      real.next = s; //尾指针指向下一个结点的地址
      real = s;     //当前新结点的地址赋予尾指针
      
      //2.3颠倒导致尾指针不移动
      
    • 删除结点

      ​ 删除p指向线性链表中某结点

      ​ (需要查找到p的前驱结点 [时间复杂度 O(n)] )

      // 伪代码
      LinkNode p; //假定p就是要删除的结点
      LinkNode q; //q是的p的前驱结点
      q-next = p-next;  //q的下一结点直接指向p的下一结点
      delete(p);   //回收删除结点p
      

      ​ 若要删除p的后继结点(假设存在),则可以直接完成

      s = p->next; //p的后继结点
      p->next = s-next;	//p的下一结点指向后两位置的结点
      delete(s);
      
    • 查找运算

      ​ 按序号查找 从链表的第一个元素开始判断当前结点是否是第i个,

      ​ 时间复杂度O(n)。

      ​ 按值查找 从链表的第一个元素开始判断当前结点的值是否等于x,

      ​ 时间复杂度O(n)。

    3.3 单循环链表

    一种头尾相接的链表。其特点是无须增加存储量,仅对表的链接方式稍作改变,即可使得表处理更加方便灵活。
    在单链表中,将终端结点的指针域NULL改为指向表头结点的或开始结点,就得到了单链形式的循环链表,并简单称为单循环链表。由于循环链表中没有NULL指针,故涉及遍历操作时,其终止条件就不再像非循环链表那样判断p或p—>next是否为空,而是判断它们是否等于某一指定指针,如头指针或尾指针等。

    3.4 双向链表

    在单链表的每个结点里再增加一个指向其直接前驱的指针域。这样就形成的链表中有两个方向不同的链。双向链表一般由头指针唯一确定的,将头结点和尾结点链接起来构成循环链表,并称之为双向链表。

    双向链表有一个数据域和两个指针域组成 结点(头指针,数据域,尾指针)

    3.41 双向链表的基本运算
    • 插入运算

      ​ 先搞定插入节点的前驱和后继,再搞定后结点的前驱,最后搞定前结点的后继。

      //伪代码
      linkNode p; //新结点
      linkNode q; //前驱结点
      
      p->front = q;       //p的头指针指向q
      p->rear = q->rear;  //p的尾指针指向q的尾指针(q的后继结点)
      q->rear->front = p; //q的后继结点的头指针指向p
      q->rear = p;		//q的后继结点指向p
      
    • 删除运算

      可以直接删除当前指针所指向的节点。而不需要像单向链表中,删除一个元素必须找到其前驱

    //伪代码
    linkNode p; //待删除的结点
    p->front->rear = p->rear;	//p的前驱结点尾指针指向p的后驱结点
    p->rear->front = p->front;  //p的后驱结点的头指针指向p的前驱结点
    delete p;  //删除p结点
    

    4、存储密度

    1. 存储密度是指结点数本身所占的存储空间大小和整个结点结构所占的存储空间之比,即

      存储密度 = 结点数据占的存储位 / 整个实际分配的存储位

      由此可见:顺序表的存储密度等于1,链表的存储密度小于1。

    2. 链式存储比顺序存储占用更多存储空间,原因是链式存储结构增加了存储其后继结点地址的指针域

    3. 存储空间完全被结点值占用的存储方式称为紧凑存储,否则称为非紧凑存储。

    4. 存储密度值越大,标识数据所占的存储空间越少。

    5、顺序表与链性表对比

    • 顺序表

      ​ 优点:随机存储,密度大(存储空间占用少)

      ​ 缺点:表的扩充困难,插入、删除要操作大量元素移动

    • 链性表

      ​ 优点:表扩充简单,插入、删除效率高。

      ​ 缺点:查找效率低,密度小(存储空间占用多)

    六、栈

    1、基本概念

    栈又称为堆栈,是一种特殊的,只能在表的一端进行插入、删除操作的线性表

    栈的逻辑结构和线性表相同,其特点是按”后进先出“的原则进行操作,而且栈的操作被限制在栈顶进行,是一种运算受限制的线性表,允许插入、删除的这一段称为栈顶,另一端称为栈底。

    2、顺序栈

    2.1 顺序栈定义

    利用顺序存储方式实现的栈称为顺序栈。顺序栈是利用地址连续的存储单元依次从栈底到栈顶的元素,同时附设栈顶指针来指示栈顶元素在栈中的位置

    2.2 顺序栈的基本算法

    顺序栈的空间分配及初始化,即给顺序栈分配内存空间,并设置好栈顶指针top的初始值-1,构造一个空栈的过程

    • 用一维数组实现顺序栈

      #define MAXLEN 10        //分配最大栈空间
      datatype data[MAXLEN]    //datatype 可根据用户需要定义类型
      int top;				//定义栈顶指针
      
    • 用结构体数组实现顺序栈

      #define MAXLEN 10        	//分配最大栈空间
      typedef stuct				//定义结构体
      {
          datatype data[MAXLEN]    //datatype 可根据用户需要定义类型
          int top;				//定义栈顶指针
      }SeqStack;
      
    • 进栈

      ​ 进栈运算是在栈顶位置插入一个新元素x,其算法步骤为:

      • 判断栈是否为满,若栈满,作溢出处理

      • 若栈未满,栈顶指针top加1。

      • 将新元素x送入栈顶

        //伪代码
        SeqStack s = new SeqStack();    
        s.top = -1					//定义栈且初始化栈顶指针
        datatype x = "某个引用";
        
        if(MAXLEN-1 = s.top){
            //栈满
        }else{
        	s.top++;
            s.data[s.top] = x;		//栈不满则进栈
        }
        
    • 出栈

      出栈运算是指去除栈顶元素,付给某一个指定变量x,其算法步骤为:

      • 判断栈是否为空,若栈空,做下溢处理

      • 若栈非空,将栈顶元素赋给变量x

      • 指针top减1

    //伪代码
    SeqStack s;    //栈
    datatype x;
    if(-1==s.top){
        //栈空
    }else{
        s.data[s.top] = x;		
        s.top--}
    

    3、链栈

    3.1 链栈定义

    链式存储结构。插入和删除操作仅限制在链头位置上进行。栈顶指针就是链表的头指针。通常不会出现栈满的情况。 不需要判断栈满但需要判断栈空。

    通常就用单向链表来实现,由于栈中的操作只能在栈顶进行,所以链表的头部做栈顶是最合适的。

    typedef struct stacknode
    {
        datatype data;		      //定义栈元素
        struct stacknode *next;    //定义指向下一个结点的指针
    }StackNode;
    
    typedef struct
    {
        StackNode *top;			  //定义栈顶指针top
    }LinkStack;					  //定义栈链类型
    

    3.2 链栈的基本算法

    链栈的空间分配及初始化,设置好栈顶指针top的初始值NULL,构造一个空栈的过程(不必分配内存)

    • 进栈

      //伪代码
      LinkStack s = new LinkStack();    
      s.top = null					//定义栈且初始化栈顶指针
      datatype x = "某个引用";
      StackNode *p = new StackNode();  //申请一个新结点空间
      p->data = x;					
      p->next = s.top;				 //将新结点插入到栈顶(p地址域指向上一个结点)
      s.top = p						 //修改栈顶指针(指针指向当前结点)
      
    • 出栈

    //伪代码
    SeqStack s;    //栈
    datatype x;
    if(null==s.top){
        //栈空
    }else{
        StackNode *p = s.top;   //定义临时指针p指向栈顶结点
       	s = p->data;			//获取结点值
        s.top = p->next;        //修改栈顶指针 (指向p的前驱结点)
        delete p;
    }
    

    4、顺序栈与链栈对比

    • 顺序栈

      ​ 优点:密度大,存储空间占用少

      ​ 缺点:扩容困难,容易出现栈满

    • 链栈

      ​ 优点:通常不出现栈满的情况

      ​ 缺点:密度小,存储空间占用多

    5、应用例子

    七、队列

    1、基本概念

    队列是一种运算受限的线性表,限制在两个端点进行插入和删除操作的线性表,允许删除的一端称为队头(front),允许插入的一端称为队尾(rear)。先进先出(FIFO)。

    2、顺序队列

    2.1 顺序队列定义

    ​ 顺序存储结构。当头尾指针相等时队列为空。在非空队列里,头指针始终指向队头前一个位置,而尾指针始终指向队尾元素的实际位置

    2.2 顺序队列的基本算法

    顺序队列的空间分配及初始化,即给顺序队列分配内存空间,并设置好队头指针与队尾的初始值为-1,构造一个空队列的过程

    #define MAXLEN 10	//队列的最大容量
    typedef struct
    {
        datatype Q[MAXLEN];
        int front;		//定义头指针
        int rear;		//定义尾指针
    }SeqQueue;
    SeqQueue *q;
    q = new SeqQueue(); 
    
    //初始化
    q.front = -1;
    q.rear = -1;
    
    • 入队

      if(MAXLEN == q.rear-q.front){
          //队满
      }else{
          q.rear++;			//先队尾指针加1
          q.Q[q.rear] = x;	//元素x进队
      }
      
    • 出队

      if(q.rear == q.front){
      	//队空
      }else{
          q.front++;			//先将队头指针加1
          x= q.Q[q.front];	//队头元素赋值给x,x在返回出去
      }
      

    3、循环顺序队列

    3.1 循环顺序队列定义

    随着入队出队,猪呢个队列会整体向上移动,这样就造成了队尾指针虽然已经移到最上面,而队列却未真满,这种

    现象叫 “假溢出”

    为了解决上诉队列的“假溢出”现象,一个方法是将队列的数据区Q[0…MAXLEN-1]看成是首尾相连的环,即将表示队首的Q[0]单元与表示队尾的Q[MAXLEN-1]单元从逻辑上连接起来,形成一个环形表,这就形成循环顺序队列

    如无特殊说明,一般情况下都直接将循环顺序队列简称为顺序队列

    3.2 循环顺序队列基本算法

    • 队空

      q.front == q.rear	//队空
      
    • 队满

      (q.rear+1) %MAXLEN == q.front	//队满
      
    • 入队

      q.rear = (q.rear+1)%MAXLEN;
      
    • 出队

      q.front = (q.front+1)%MAXLEN;
      

    4、链队列

    4.1 链队列定义

    链式存储结构。限制仅在表头删除和表尾插入的单链表。显然仅有单链表的头指针不便于在表尾做插入操作,为此再增加一个尾指针,指向链表的最后一个结点。

    4.2 链队列基本算法

    具有链式存储结构的队列称为链队列,实际上它是一个带有头指针和尾指针的单向链表,该链表一般没有头结点

    链队列的头指针和尾指针使两个独立的指针变量,由于他们分别指向同一个单链表中的首尾结点,所以链队列的整体结构考虑,一般将这两个指针封装在同一个结构体中。

    typedef struct linkqueuenode
    {
        datatype data;		// datatype 为链队列中元素的类型
        struct linkqueuenode *next;
    }LinkQueueNode;			// 链队列结点的类型为LinkQueueNode
    
    typedef struct
    {
        LinkQueueNode *front, *rear;	//队头队尾指针的定义
    }LinkQueue;							// 链队列的类型为LinkQueue
    
    • 初始化

      q.front =NULL;		//头指针为空
      q.rear =NULL//尾指针为空
      
    • 入队

      LinkQueueNode *p = new LinkQueueNode;	//开辟新的结点空间
      p->data = x;
      p->next = NULL;
      if(NULL == q.front){		//若队列为空,则队头直接指向新结点
          q.front = p;			
      }else{						//否则将新结点插入队尾
          q.rear->next = p;
      }
      q.rear = p;					//更改队尾指针
      
    • 出队

    LinkQueueNode *p = q.front;		//获取即将出队结点
    if(NULL == p){
        //空队列
    }else{
    	q.front = q->next;			//否则,将队头结点从队列中断开
            if(NULL == q.front){	//若出队是队列的最后一个结点,则将队尾为置空
                q.rear = NULL;
            }
        x = p-> data;
        delete p;
    }
    

    5、应用例子

    八、串

    1、串的概念

    串(String)是零个或多个字符组成的有限序列 。一般记作:

    ​ s = “a1a2…aian

    其中,s是串名,用引号括起来的字符序列为串值,ai(1<=i<=n)是一个任意字符,它称为串的元素,是构成元素的基本单位;i是它在整个串中的序号;n为串的长度,表示串中所包含的字符的字符个数。

    2、几个术语

    1. 长度:串中字符的个数,称为串的长度。
    2. 空串:长度为零的字符串称为空串。
    3. 空格串:有一个或朵儿连续空格组成的串称为空格串。
    4. 串相等:两个串是相等的,是指两个串的长度相等且对应的字符都相等。
    5. 子串:串中任意连续的字符组成的子序列称为该串的子串。
    6. 主串:包含子串的串称为该子串的主串。
    7. 模式匹配:子串的定位运算又称为串的模式匹配,是一种求子串的第一个字符在主串中序号的运算。被匹配的主串称为目标串,子串称为模式

    九、数组和广义表

    十、树和二叉树

    1、树的定义

    ​ 树【递归】是n(n>=0)个有限数据元素的集合。在任意一棵非空树T中:

    ​ 有且仅有一个特定的称为树根的结点(根结点无前驱结点)

    ​ 当n>=1时,出根结点之外的其余结点被分成m(m>0)个互不相交的集合T1,T2…,Tn,其中每一个集合Ti (1<=i<=m)本身又是一棵树,并且称为根的子树。

    2、基本术语

    1. 结点:树的结点包含一个数据及若干指向其子树的分支。
    2. 结点的度:结点所拥有的子树称为该结点的度。
    3. 树的度:树中各个结点度的最大值称为该树的度。
    4. 叶子(终端结点):度为零的结点称为叶子结点。
    5. 分支结点:度不为零的结点称为分支结点。
    6. 兄弟结点:同一父亲结点下的子结点称为兄弟结点。
    7. 层数:树的根结点的层数为1,其余结点的层数等于它双亲结点的层数加1。
    8. 树的深度:树中结点最大层数称为树的深度。
    9. 森林:零棵或有限棵互不相交的树的集合称为森林。
    10. 有序树:子树有序的树。
    11. 无序树:子树无序的树。

    3、二叉树

    3.1 二叉树定义

    二叉树可以为空,非空的二叉树中,每个结点至多只有两颗子树,分别称为左子树和右子树,且左、右子树的次序不能任意交换。

    3.2 二叉树的性质

    1. 非空二叉树的第i层上最多有**2i-1**个结点(i>=1)

    2. 深度为h的二叉树中,最多具有2h-1个结点(h>=1)

    3. 满二叉树:一棵深度为h,且有2h-1个结点的二叉树称为满二叉树

    4. 完全二叉树:深度为h、有n个结点的二叉树,当且仅当每一个结点都与深度为h的满二叉树中编号从1至n的结点一一对应时,称此二叉树为完全二叉树。

    5. 对于一棵有n个结点的完全二叉树,若按满二叉树的同样方法对结点进行编号,则对于任意序号为i的结点:

      1. 若i=1,则序号为i的结点为根节点。

        若i>1,则序号为i的结点的父结点的序号为**【i/2】**。

      2. 若2i<=n,则序号为i的结点的左孩子结点的序号为2i

        若2i>i,则序号为i的结点无左孩子。

      3. 若2i+1<=n,则序号为i的结点的右孩子结点的序号为2i+1。

        若2i+1>n,则序号为i的结点无右孩子。

    6. 具有·n(n>0)个结点的完全二叉树(包括满二叉树)的深度(h)为**[log2n]+1**

    7. 对于一棵非空的二叉树,设n0、n1、n2分别表示度为0、1、2的结点个数,则有n0=n2+1。

    3.3 二叉树的存储

    未完。。。

    展开全文
  • 数据结构知识点汇总

    万次阅读 多人点赞 2018-07-18 15:44:21
    4、栈通常采用的两种存储结构是(线性存储结构和链表存储结构) 5、队列具有(先进先出)的特征,栈具有(后进先出)的特征。 6、链表(插入和删除不需要移动元素,但是无法随机访问任一元素) 7、循环链表的主要...

    1、用链表表示线性表的优点是(便于插入和删除操作)

    2、单链表中,增加头结点的目的是(方便运算的实现)

    3、栈和队列的共同特点是(只允许在端点处插入和删除元素)

    4、栈通常采用的两种存储结构是(线性存储结构和链表存储结构)

    5、队列具有(先进先出)的特征,栈具有(后进先出)的特征。

    6、链表(插入和删除不需要移动元素,但是无法随机访问任一元素)

    7、循环链表的主要优点是(从表中任一结点出发都能访问到整个链表)

    8、线性表(除了第一个和最后一个元素外,其余每个元素都有一个直接前驱和直接后继)

    9、线性表的顺序存储结构和线性表的链式存储结构分别是(随机存取的存储结构、顺序存取的存储结构)

    10、深度为5的满二叉树中,叶子结点的个数为(16)。其共有(31)个结点。

           设一棵完全二叉树共有699个结点。则该二叉树的叶子结点数为(350)个。 

                 #完全二叉树总的结点数为N,若N为奇数,则叶子结点数为(N+1)/2;若N为偶数,则叶子结点数为N/2。

    11、具有3个结点的二叉树有(5)种形态。 #高度为2层的是:根-左-右。高度为3层的是:根-左-左、根-左-右、根-右-右、根-右-左。

    12、一棵二叉树中有3个叶子结点,有8个度为1的结点,则该二叉树中总的结点数为(13)个。

          #叶子结点数n0与度为2的结点数n2的关系是:n0=n2+1,所以度为2的结点个数为3-1=2。所以总的结点数为 n=n0+n1+n2, 8+2+3=13.

    13、已知二叉树的后序遍历序列是dabec,中序遍历序列是debac,它的前序遍历序列是(cedba)。#过程见文章:点击打开链接

    14、已知二叉树的前序遍历序列是abdgcefh,中序遍历序列是dgbaechf,它的前序遍历序列是(gdbehfca)。

    15、算法是指(解决方案的准确而完整的描述)。

    16、算法由(顺序、选择、循环)控制结构组合而成。

    17、算法的时间复杂度是指(算法执行过程中所需要的基本运算次数)。

    18、算法的空间复杂度是指(执行过程中所需要的存储空间)。

    19、算法分析的目的是(分析算法的效率以求改进)。

    20、数据的存储结构是指(数据的逻辑结构在计算机中的表示)。

    21、数据的逻辑结构是指(反映数据元素之间逻辑关系的数据结构)。

    22、根据数据结构中各元素之间前后件关系的复杂程度,可将数据结构分为(线性结构和非线性结构)。

    线性结构一般是首无前驱,尾无后继,中间元素有唯一的前驱和后继。主要有:列表、链表、队列、栈。

    非线性结构主要有1、没有对应关系的 集合。2、一对多关系的 树。3、多对多关系的 图。

    23、(队列,循环队列,顺序表)不具有记忆功能,(栈)具有记忆功能。

    24、递归算法一般需要用(栈)来实现。

    #在递归算法的运行过程中,需要利用栈来保存其运算结果、参数和返回地址等。

    25、算法的五个基本特征是:可行性,确定性,和拥有足够的情报

    有限性:算法在执行有限步后必须终止。

    确定性:算法的每个步骤都需要精确地定义,严格地、无歧义的运行。

    输入:算法在运行之前赋给它的量。

    输出:算法运行结束时的结果。

    可行性:算法原则上能够精准地运行,而且人们用纸和笔做有限次运算后即可完成。

    26、由两个栈共享一个存储空间的好处是(节省存储空间,降低上溢发生的概率)。

    为了不发生上溢错误,就必须给每个栈分配一个足够大的存储空间。但实际中,很难准确地估计,若每个栈都分配过大的存储空间,势必造成系统空间紧张;若让多个栈共用一个足够大的连续存储空间,则可利用栈的动态特性使它们的存储空间互补

    27、需要打印机输出数据时,一般将打印作业放在一个(队列)中。

    28、非空的循环单链表head的尾结点(由 p 所指向) ,满足(p->next=head )。

    29、与单链表相比,双向链表的优点是(更容易访问相邻结点)。

    30、

    31、N个顶点的连通图中边的条数至少为(N-1)条。#将所有顶点连成一条线即可

    32、N个顶点的强连通图中边的条数至少为(N)条。#将所有顶点连成一条圈

    33、对长度为n的线性表进行顺序查找,最坏情况下需要比较(N)次。

    34、最简单的交换排序是(冒泡排序)。

    35、对长度为n的线性表进行顺序冒泡排序,最坏情况下需要比较(n(n-1)/2)次。

            #一共比较n-1遍,第1遍需要比较n-1次,第1遍需要比较n-2次,........最后一遍需要比较1次。是一个等差序列,对其进行求和即可。

    36、在序列基本有序的情况下,效率最高的方法是(A) #如果将插入排序换为冒泡排序,则选冒泡排序

             A.插入排序   B.选择排序   C.快速排序   D.堆排序

            插入排序通过数据元素的交换来逐步消除线性表中的逆序,所以比较的次数与初始排列次序有关,在待排序的元素序列基本有序的前提下,效率最高。而选择排序和堆排序的比较次数与初始排列次序无关。快速排序虽然与初始排列次序有关,但在待排序的元素序列基本有序的前提下,效率低于插入排序。

    37、希尔排序属于(插入类排序),堆排序属于(选择类排序)。

    38、在下列几种排序方法中,要求内存量最大的是(D).
     

            A.插入排序  B.选择排序  C.快速排序  D.归并排序

            快速排序的基本思想是,通过一趟排序将待排序记录分割成独的两部分,其中一部分记录的关键字均比另一部分记录的关键字小,再分别对这两部分记录继续进行排序,以达到整个序列有序;插入排序的基本操作是指将无序序列中的各元素依次插入到已经有序的线性表中,从而得到一个新的序列;选择排序的基本思想是:扫描整个线性表,从中选出最小的元素,将它交换到表的最前面(这是它应有的位置),然后对剩下的子表采用同样的方法,直到表空为止;归并排序是将两个或两个以上的有序表组成合成一个新的序列表。

    39、已知数据表 A中每个元素距其最终位置不远,为节省时间, 应采用(直接插入排序)。

    40、数据结构是指相互有关联的( 数据元素 )的集合。

    41、数据元素之间的任何关系都可以用 (前驱和后继) 关系来描述。

    42、顺序存储方法是把逻辑上相邻的结点存储在 (物理位置) 相邻的存储单元中。

    43、栈的基本运算有三种:入栈、退栈与读栈顶元素。

    44、队列主要有两种基本运算:入队和退队。

    45、在实际应用中,带链的栈可以用来收集计算机存储空间中所有空闲的存储结点,这种带链的栈称为 (可利用栈) .

    46、栈和队列通常采用的存储结构分别是 链式存储和顺序存储。

    47、当循环队列非空且队尾指针等于对头指针时, 说明循环队列已满,不能进行入队运算。这种情况称为 (上溢) 

    48、当循环队列为空时, 不能进行退队运算, 这种情况称为 (下溢)。

    49、在一个容量为 25 的循环队列中, 若头指针 front=16 , 尾指针 rear=9 , 则该循环队列中共有 18 个元素。        注: 当 rear<front 时, 元素个数=总容量-( front -rear ); 当 rear>front 时,元素个数= rear -front 。

    50、判断一个链表是否存在环:点击打开链接

            单链表中元素的反转:点击打开链接

            判断两个数组中是否有相同的数字:点击打开链接

            从一个子序列中找出其最大子序列的和:点击打开链接

            按单词反转字符串:点击打开链接

            删除数组中重复的元素:点击打开链接

     

    1、数组和链表的区别

          数组不允许动态地定义其大小,只能够将其定义成足够大小,这样可能会造成空间的浪费。

          数组在内存中是顺序的存储,可以以O(1)时间查找元素,但是需要O(n)时间插入和删除元素(因为其后面的元素都需要跟着移动)。

          链表可以动态地定义其大小。其在内存中是链式的存储,访问元素是需要从头开始向后顺序访问,所以需要O(n)时间查找元素;如果在所需位置直接插入或删除元素,需要O(1)时间,如果在需要先找到所需位置再插入或删除元素,需要O(n)时间。

    2、链表的基本操作:反转,是否存在环,循环链表点击打开链接和双向链表点击打开链接的查找、插入、删除操作。

    3、栈的入栈和出栈:点击打开链接,队列的入队和出队:点击打开链接

    4、二叉树的基础知识:点击打开链接及其三种遍历(递归和非递归实现):点击打开链接

    5、图的基础知识:点击打开链接

    6、常用散列函数和冲突消解机制:点击打开链接

     

    7、排序算法中基本的冒泡排序、选择排序、插入排序需要很快地用代码实现。堆排序、归并排序、快速排序需要掌握其主要思想,并熟悉常用排序算法的时间和空间复杂度,及其应用范围:

        (1) 当数据规模较小时,直接采用直接插入排序或直接选择排序。

        (2) 当数据已经基本有序时,可以用直接插入排序或冒泡排序。

        (3) 当数据规模较大时,可以用快速排序。当记录随机分布时,快速排序的平均时间最短。当最坏情况时,其时间复杂度为O(n2),空间复杂度为O(n)。

         (4) 堆排序所需的辅助空间比快排少,但这两种方法都不稳定。

         (5) 归并排序既可以用于内部排序,也可以用于外部排序,是一种稳定的算法。

    8、能熟练写出二分查找的程序。

    9、熟悉算法的思想:贪心算法,动态规划,分治算法。

     

     

    参考:https://www.cnblogs.com/houjun/p/4896268.html

    展开全文
  • 超级详细,而又直白简单的讲述数据结构基础知识点的个人笔记(包含自己的解读),标记了重点,适合数据结构基础入门
  • 数据结构知识点复习

    千次阅读 2018-09-28 09:29:50
    1、数组和链表的区别: 数组的特点: 数组在内存中是连续的区域 数组的大小需要提前申请,即需要提前确定大小。不利于扩展,可能导致用不完而... 增加和删除数据很容易,只需要改变添加位置的前后两个数据单位的...
  • 数据结构知识点

    2019-06-03 17:29:00
    对数据结果概念与知识点进行小结 什么是数据结构? 简单说,数据结构就是一个容器,以某种特定的布局存储数据。这个“布局”使得数据结构在某些操作上非常高效,在另一些操作上则不那么高效。你的目标就是理解...
  • 数据结构知识点总结

    2019-12-15 15:03:57
    数据结构部分 队列 用数组表示循环队列: 为了区分队空和队满,入队时少用一个队列元素,约定以“队头指针在队尾指针的下一个位置作为队满的标志”,(也就是说如果队尾快要赶上队头了就认为满了)。也可以通过增加...
  • 数据结构与算法知识点总结—思维导图

    万次阅读 多人点赞 2020-04-20 22:50:54
    数据结构与算法是学习编程者的必修课,下面是我学习完之后的知识点梳理与总结。 本来用xmind做的时候把重要知识点都附了博客链接,但是xmind导出来后打不开了。 不用担心我把相关内容放在了数据结构专栏里。 ...
  • 数据结构知识点整理(思维导图版)

    万次阅读 多人点赞 2017-05-29 18:50:53
    Java图解数据结构思维导图内容整理
  • 写在前面: 恰逢期末复习,用了几天时间结合老师勾画的重点以及课件教材等,将全书重要内容做了个大整合。一方面便于自己复习记忆,另一方面po出来让更多需要的人也可以做个参考... 《数据结构》C语言版 (清华严...
  • 数据结构知识体系框架图

    千次阅读 2018-04-04 10:52:05
  • 数据结构》| 第一章 绪论 知识梳理

    万次阅读 多人点赞 2019-01-28 22:20:14
    绪论 目录 绪论 1.掌握数据、数据元素、抽象数据类型、数据结构、数据的逻辑结构与存储结构等...系列索引:《数据结构》C语言版 (清华严蔚敏考研版) 全书知识梳理       1.掌握数据、数据元素、抽象数...
  • 数据结构》(浙大版)笔记+题解目录

    万次阅读 多人点赞 2019-09-05 21:01:22
    中国大学MOOC上浙大的《数据结构》广受好评,原因有二,一是基础,简单易懂,老师讲得也清楚,另一大优点就是配套的每周相应知识点的编程题了,有难有易,容易的题帮助巩固知识点,难的题开阔视野。 现将笔记和题解...
  • 数据结构和算法视频教程

    万人学习 2019-06-25 10:51:39
    数据结构、算法视频培训课程,该教程主要是介绍在游戏开发中经常使用的数据结构,例如数组,链表,栈,队列,二叉树,递归等重要知识点讲解以及将它们里灵活的运用到算法里面。
  • 数据结构——树——知识点总结

    万次阅读 多人点赞 2017-05-13 10:02:17
    数据结构——树 定义:树是一个n(n>=0)个结点的有序合集 名词理解: 结点:指树中的一个元素; 结点的度:指结点拥有的子树的个数,二叉树的度不大于2; 数的度:指树中的最大结点度数; 叶子:度为0的结点,也...
  • 数据结构与算法思维导图
  • 数据结构课程是计算机类专业的专业基础课程,在IT人才培养中,起着重要的作用。课程按照大学计算机类专业课程大纲的要求,安排教学内容,满足需要系统学习数据结构的人。系列课程包含11个部分,本课为第1部分,介绍...
  • 数据结构基础系列(2):线性表

    万人学习 2018-10-22 21:38:03
    数据结构课程是计算机类专业的专业基础课程,在IT人才培养中,起着重要的作用。课程按照大学计算机类专业课程大纲的要求,安排教学内容,满足需要系统学习数据结构的人。系列课程包含11个部分,本课为第2部分,...
  • 数据结构基础系列(6):树和二叉树

    万人学习 2018-10-22 21:38:03
    数据结构课程是计算机类专业的专业基础课程,在IT人才培养中,起着重要的作用。课程按照大学计算机类专业课程大纲的要求,安排教学内容,满足需要系统学习数据结构的人。系列课程包含11个部分,本课为第6部分“树和...
1 2 3 4 5 ... 20
收藏数 480,043
精华内容 192,017
关键字:

数据结构知识点