精华内容
下载资源
问答
  • 数据结构算法

    千次阅读 2016-05-03 11:36:37
    数据结构算法

    数据结构和算法中包含了太多的内容,根据我看到的大概有以下的内容:

    简单的说,是“3+2”:3种数据结构:线性结构、树、图;2种算法:查找、排序。其中线性结构又可以分为:顺序表、链表、队列、栈它们在平时有着更加广泛的应用。而树、图则在解决一些特定的算法时更加管用。

    其次,数据结构并不是死的:你可以根据自己的需要定制数据结构的成员。而这些成员又决定了对应于这种结构的算法。因此,数据结构跟算法之间并不是孤立的,而是紧密联系的一体:对于有的算法,比如返回树中一个节点的父节点,如果你在树结构中添加一个parent指针,就很好办,如果没有这个指针,做起来就会很纠结。

     

    1、程序设计=数据结构+算法

    我的理解:算法,就是解决一个问题所用到的思路和方法。

    对于特定的问题,我们需要使用不同的算法,有时候是一个算法,有时候是几个算法的结合,甚至有时候需要我们根据实际问题设计与之最匹配的算法。

    算法一般具有下列5个重要特性:

    (1)输入: 一个算法应该有一个或多个输入:

    (2)有穷性:一个算法必须在执行有穷步骤之后正常结束,而不能形成无穷循环:

    (3)确定性:算法中的每一条指令必须有确切的含义,不能产生多义性:

    (4)可行性:算法中的每一条指令必须是切实可执行的,即原则上可以通过已经实现的基本运算执行有限次来实现:

    (5)输出:一个算法应有零个或多个输出,这些输出是同输入有某个特定关系的量。

     

    2、什么是数据结构?

    数据结构是一门研究非数值计算的程序设计问题中的操作对象,以及它们之间的关系和操作等相关问题的学科(带结构的数据元素的集合。)。简单来说,数据结构就是关系,没错,就是数据元素相互之间存在的一种或多种特定关系的集合。

    程序设计=数据结构+算法

    一般的,我们把数据结构分为逻辑结构和物理结构。

    逻辑结构:是指数据对象中数据元素之间的相互关系,也是我们今后最需要关注和讨论的问题。

    物理结构:是指数据的逻辑结构在计算机中的存储形式。

    四大逻辑结构:

    1>线性结构:数据元素之间是一对一的关系;

    2>树形结构:数据元素之间存在一种一对多的层次关系;

    3>图形结构:数据元素是多对多的关系;

    4>集合结构:其中的数据元素除了同属于一个集合外,它们之间没有其他不三不四的关系。

     

    数据的逻辑结构有4种基本类型:集合结构、线性结构、树形结构和图形结构。线性表和树是最常用的两种高效数据结构,许多高效的算法都能用这两种数据结构来设计实现。偶尔也会使用到图形结构,集合结构使用甚少。

     

    根据物理结构的定义,我们实际上研究的的就是如何把数据元素存储到计算机的存储器中。

    存储器主要是针对内存而言的,像硬盘、软盘、光盘等外部存储器的数据组织通常用文件结构来描述。

     

    3、时间复杂度和空间复杂度

    1>用常数1取代运行时间中的所有加法常数;

    2>在修改后的运行次数函数中,只保留最高阶项;

    3>如果最高阶项存在且不是1,则去除与这个项相乘的常数;

    这样,得到的最后结果就是大O阶。

     

    一般情况下,当一个算法包含两个(或多个)独立的过程我们在计算完各自的时间复杂度后,只选择较大的那个。例如:N和NlogN,那么这个算法的时间复杂度就是NlogN。

     

     


    展开全文
  • 数据结构算法习题库

    万次阅读 多人点赞 2018-12-26 21:24:55
    第一章 绪论 一.选择题 1.数据结构被形式地定义为(K,R),其中K是①_B_的有限集合,R是K上的②_D_的有限集合。...2.算法分析的目的是①C,算法分析的两个主要方面是②A。  ①A.找出数据结构的合理性 ...

    第一章  绪论

    一.选择题

    1.数据结构被形式地定义为(KR),其中K是①_B_的有限集合,RK上的②_D_的有限集合。

      A.算法      B.数据元素    C.数据操作     D.逻辑结构

      A.操作      B.映象        C.存储         D.关系

    2.算法分析的目的是①C,算法分析的两个主要方面是②A

        A.找出数据结构的合理性

          B.研究算法中的输入和输出的关系

          C.分析算法的效率以求改进

          D.分析算法的易懂性和文档性

        A.空间复杂性和时间复杂性

          B.正确性和简明性

          C.可读性和文档性

          D.数据复杂性和程序复杂性

    3 在计算机存储器内表示时,物理地址和逻辑地址相同并且是连续的,称之为(B)

    A.逻辑结构      B.顺序存储结构

    C.链表存储结构    D.以上都不对

    4.数据结构中,在逻辑上可以把数据结构分成:(  C )。

    A.动态结构和静态结构                       B.紧凑结构和非紧凑结构 

    C.线性结构和非线性结构                     D.内部结构和外部结构

    5.以下属于顺序存储结构优点的是( A )。

    A.存储密度大         B.插入运算方便       

    C.删除运算方便    D.可方便地用于各种逻辑结构的存储表示

    6.数据结构研究的内容是( D )。

    A.数据的逻辑结构                            B.数据的存储结构    

    C.建立在相应逻辑结构和存储结构上的算法      D.包括以上三个方面

    7.链式存储的存储结构所占存储空间()。

    A.分两部分,一部分存放结点值,另一部分存放表示结点间关系的指针

    B.只有一部分,存放结点值

    C.只有一部分,存储表示结点间关系的指针

    D.分两部分,一部分存放结点值,另一部分存放结点所占单元数

    8.一个正确的算法应该具有 5 个特性,除输入、输出特性外,另外 3 个特性是( A )。

    A.确定性、可行性、有穷性                   B.易读性、确定性、有效性

    C.有穷性、稳定性、确定性                   D.可行性、易读性、有穷性

    9.以下关于数据的逻辑结构的叙述中正确的是(  A)。

    A.数据的逻辑结构是数据间关系的描述

    B.数据的逻辑结构反映了数据在计算机中的存储方式

    C.数据的逻辑结构分为顺序结构和链式结构

    D.数据的逻辑结构分为静态结构和动态结构

    10.算法分析的主要任务是( C )。

    A.探讨算法的正确性和可读性               B.探讨数据组织方式的合理性

    C.为给定问题寻找一种性能良好的解决方案   D.研究数据之间的逻辑关系

    二.解答

    设有一数据的逻辑结构为:B=(D, S),其中:

    D={d1, d2, , d9}

    S={<d1,d3>, <d1, d8>, <d2, d3>, <d2, d4>, <d2, d5>, <d3, d9>, <d4, d7>, <d4, d6>, <d5, d6>, <d8, d9>, <d9, d7> }画出这个逻辑结构示意图

     

    d1

    d8

    d3

    d2

    d4

    d5

    d9

    d7

    d6

     

    第二章 线性表

    一、选择题

    1.下述哪一条是顺序存储结构的优点?( A)

    A.存储密度大 B.插入运算方便 C.删除运算方便 D.可方便地用于各种逻辑结构的存储表示

    2.下面关于线性表的叙述中,错误的是哪一个?( B)

    A.线性表采用顺序存储,必须占用一片连续的存储单元。

    B.线性表采用顺序存储,便于进行插入和删除操作。

    C.线性表采用链接存储,不必占用一片连续的存储单元。

    D.线性表采用链接存储,便于插入和删除操作。

    3.若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算,则利用(A )存储方式最节省时间。

    A.顺序表 B.双链表 C.带头结点的双循环链表 D.单循环链表

    4.某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素,则采用( D)存储方式最节省运算时间。

    A.单链表 B.仅有头指针的单循环链表 C.双链表 D.仅有尾指针的单循环链表

    5.在一个长度为n的顺序表中删除第i个元素(0<=i<=n)时,需向前移动(A)个元素

    A.n-i           B.n-i+l        C.n-i-1        D.i

    6.从一个具有n个结点的单链表中查找其值等于x的结点时,在查找成功的情况下,需平均比较(C)个元素结点

    A.n/2               B.n                     C.(n+1)/2         D.(n-1)/2

    7.设单链表中指针p指向结点m,若要删除m之后的结点(若存在),则需修改指针的操作为(A)

    A.p->next=p->next->next;         B.p=p->next;

    C.p=p->next->next;                     D.p->next=p;

    8.在一个单链表中,已知q结点是p结点的前趋结点,若在q和p之间插入s结点,则须执行(B)

    A.s->next=p->next;  p->next=s

    B.q->next=s;  s->next=p

    C.p->next=s->next;  s->next=p

    D.p->next=s;  s->next=q

    9.线性表的顺序存储结构是一种(A)的存储结构。

    A.随机存取        B.顺序存取        C.索引存取        D.散列存取

    二、填空

    1.在线性表的顺序存储中,元素之间的逻辑关系是通过  物理位置相邻    决定的;在线性表的链接存储中,元素之间的逻辑关系是通过  指针    决定的。

    2.在双向链表中,每个结点含有两个指针域,一个指向   .直接前驱    结点,另一个指向   直接后继    结点。

    3.当对一个线性表经常进行存取操作,而很少进行插入和删除操作时,则采用_顺序     存储结构为宜。相反,当经常进行的是插入和删除操作时,则采用   链式     存储结构为宜。

    三、算法设计

    1.设有一个正整数序列组成的有序单链表(按递增次序有序,且允许有相等的整数存在),试编写能实现下列功能的算法(要求用最少的时间和最小的空间)

    确定在序列中比正整数x大的数有几个(相同的数只计算一次)

    将单链表中比正整数x小的偶数从单链表中删除

    int count(Linklist h,int x)

    {

      int num=0;

      Linknode *p;

      p=h->next;

      while(p&&p->data<=x)//p指针向后移动,直至p指向第一个值大于x的结点

        p=p->next;

      while(p)

    if(p->next&&p->data==p->next->data) 

    //若p没有指向链表中同一数值的最后一个结点,则向后移动

          p=p->next;

        else

    //若p指向数值相同的结点中的最后一个,则num加1,p指针后移,继续执行while循环

        {

          num++;

          p=p->next;

        }

       return num;

    }

    void delevenl(Linklist &h,int x)

    {

      Linknode *p,*r;

      p=h->next;r=h;

      while(p&&p->data<x)

      {

        if(p->data%2==0)

        {

          r->next=p->next;

          free(p);

          p=r->next;

        }

        else

        {

          r=p;

          p=p->next;

        }

      }

    }

     

    2.设有一个表头指针为h的单链表。试设计一个算法,通过遍历一趟链表,将链表中所有结点的链接方向逆转,如下图所示。要求逆转结果链表的表头指针h指向原链表的最后一个结点。

     

    p

    h

    h

    Λ

    Λ

    Λ

     

     

     

     

     

     

     

    2.void converse(Linklist &h)

    {

           Linknode *p,*q;

           p=h->next;

           h->next=NULL;

        q=p->next;

           while(q)

           {

                  p->next=h;

                   h=p;

                   p=q;

            q=q->next;           

           }

    p->next=h;

    h=p;

    }

     

    3.设计算法将一个带头结点的单链表A分解为两个具有相同结构的链表B、C,其中B表的结点为A表中值小于零的结点,而C表的结点为A表中值大于零的结点(链表A的元素类型为整型,要求B、C表利用A表的结点)。

    3.void decompose(Linklist La,Linklist &Lb,Linklist &Lc)

    {

           Linknode *p;

           Lc=(Linknode *)malloc(sizeof(Linknode));

           Lc->next=NULL;

           p=La->next;

           Lb=La;

           Lb->next=NULL;

           while(p)

           {

                  La=p->next;

                  if(p->data>0)

                  {

                         p->next=Lc->next;

                         Lc->next=p;

                  }

                  else

                  {

                  p->next=Lb->next;

                         Lb->next=p;

                  }

                  p=La;

           }

    }

    4. 假设链表A、B分别表示一个集合,试设计算法以判断集合A是否是集合B的子集,若是,则返回1,否则返回0,并分析算法的时间复杂度。

    4.int subset(LinkList la, LinkList lb)

    {  LinkNode * pa,*pb;

      pa=la->next;

      while(pa)

      {  pb=lb->next;

         while(pb&&(pb->data!=pa->data)) pb=pb->next;

            if(!pb) return 0;

            pa=pa->next;

           }

      return 1;

    }算法时间复杂度O(A.Length*B.Length)

    5.设有一单循环链表la,其结点有三个域:prior、data与next,其中data为数据域,,next域指向直接后继,prior域应指向直接前驱,但目前空着。试写一算法将此单循环链表改造为双向循环链表。

    5.void priorset(DuLinkList &la)

    { p=la;q=la->next;

      while(q!=la){q->prior=p; p=q;q=q->next;}

       q->prior=p;

    }

     

    第三章 栈和队列

    一、选择题

    1.设有一个栈,元素的进栈次序为A, B, C, D, E,下列是不可能的出栈序列(C )

    A.A, B, C, D, E         B.B, C, D, E, A

    C.E, A, B, C, D         D.E, D, C, B, A

    2.在一个具有n个单元的顺序栈中,假定以地址低端(即0单元)作为栈底,以top作为栈顶指针,当做出栈处理时,top变化为(C )

    A.top不变        B.top=0      C.top--      D.top++

    3.在具有n个单元的顺序存储的循环队列中,假定front和rear分别为队头指针和队尾指针,则判断队满的条件为( D)

    A.rear%n= = front         B.(front+l)%n= = rear

    C.rear%n -1= = front    D.(rear+l)%n= = front

    4.在具有n个单元的顺序存储的循环队列中,假定front和rear分别为队头指针和队尾指针,则判断队空的条件为( C)

    A.rear%n= = front         B.front+l= rear

    C.rear= = front         D.(rear+l)%n= front

    5.在一个链队列中,假定front和rear分别为队首和队尾指针,则删除一个结点的操作为( A)

    A.front=front->next     B.rear=rear->next

    C.rear=front->next      D.front=rear->next

    6.某堆栈的输入序列为1,2,3,…,n,输出序列的第一个元素是n,则第i个输出元素为( C)

    A.i     B.n-i     C.n-i+1   D.哪个元素无所谓

     

    二、解答题

    1.一个双向栈S是在同一向量空间内实现的两个栈,它们的栈底分别设在向量空间的两端。 试为此双向栈设计初始化InitStack ( S ) 、入栈Push( S , i , x) 和出栈Pop( S , i )等算法, 其中i为0 或1, 用以表示栈号。

    1.双向栈

     

    栈底1

    ……….

     

    ………

     

    栈底2

    //双向栈类型定义

    #define STACK_SIZE 100;

    Typedef struct {

            SElemType  * base_one, * base_two;//栈底指针

            SElemType  * top_one, * top_two;//栈顶指针

            int stacksize;

                } SqStack;

     

    Status InitStack ( SqStack &S) {

    //初始化双向栈

    S.base_one=S.top_one=( SElemType *)malloc(STACK_SIZE * sizeof(SElemType));//第一个栈底和栈顶指向数组起点

    S.base_two=S.top_two=S.base_one +STACK_SIZE-1;// 第二个栈底和栈顶指向数组终点

    S.stacksize= STACK_SIZE ;

    return OK;

    }//InitStack

     

    Status Push ( SqStack &S, int i, SElemType e){  

    //入栈操作,i=0时将e存入前栈,i=1时将e存入后栈

    if( S.top_two < S.top_one)   return OVERFLOW;//栈满,不考虑追加空间

    if( i = = 0 )

    *S.top_one++ = e;

    else

    *S.top_two-- = e;

    return OK;

    }//Push

     

    SElemType  Pop ( SqStack &S, int i){   

    //出栈操作,i=0出前栈,i=1出后栈

    if( i==0 ) {

           if ( S.top_one==S.base_one) return ERROR;

           S.top_one--; e=*S.top_one;

            }

    else {

          if ( S.top_two==S.base_two) return ERROR;

           S.top_two++; e=*S.top_two;

            }

    return e;

    }//Pop

     

    2.利用两个栈S1、S2模拟一个队列时,如何使用栈的运输实现队列的插入、删除运算。

    2.#define M 3

    struct Stack{

           Qelemtype data[M];

           int top;

    };

    struct Queue{

           Stack s1;

           Stack s2;

    };

    void InitQueue(Queue &Q)//初始化队列

    {

           Q.s1.top=0;

           Q.s2.top=0;

    }

    int IsEmpty(Queue &Q)//判断队列是否为空

    {

           if(Q.s1.top==0&&Q.s2.top==0)

                  return 1;

           if(Q.s2.top==0&&Q.s1.top!=0)

           {

                  while(Q.s1.top!=0)

                         Q.s2.data[Q.s2.top++]=Q.s1.data[--Q.s1.top];

           }

           return 0;

    }

     

    int IsFull(Queue &Q)

    {

           if(Q.s1.top==M&&Q.s2.top!=0)

                  return 1;

           if(Q.s1.top==M&&Q.s2.top==0)

           {

                  while(Q.s1.top!=0)

                         Q.s2.data[Q.s2.top++]=Q.s1.data[--Q.s1.top];

                  return 0;

           }

           if(Q.s1.top!=M)

                  return 0;

    }

     

    void InQueue(Queue &Q,Qelemtype e)

    {

           if(IsFull(Q))

           {

                  cout<<"OVERFLOW"<<endl;

                  return;

           }

           Q.s1.data[Q.s1.top++]=e;

    }

     

    void DeQueue(Queue &Q,Qelemtype &e)

    {

           if(IsEmpty(Q))

           {

                  cout<<"UNDERFLOW"<<endl;

                  return;

           }

           e=Q.s2.data[--Q.s2.top];

    }

     

    3.已知一个栈S的输入序列为abcd,下面两个序列能否通过栈的push和pop操作输出?如果能,请写出操作序列;如果不能,请写明原因。

    (1)dbca    (2)cbda

    3.(1)不能 (2)可以 原因略

    4.假设以带头结点的循环链表表示队列,并且只设一个指针指向队尾元素结点(注意不设头指针) ,试编写相应的置空队、判队空 、入队和出队等算法。

    4.struct QueueNode

    {

           Qelemtype data;

           QueueNode *next;

    };

     

    struct LinkQueue

    {

           QueueNode *rear;

    };

     

    void InitQueue(LinkQueue &Q)  //置空队

    {

           Q.rear=new QueueNode;

           Q.rear->next=Q.rear;

    }

     

    int EmptyQueue(LinkQueue Q)  //判队空

    {

           return Q.rear==Q.rear->next;

    }

    void EnQueue(LinkQueue &Q, Qelemtype e)//元素入队

    {

           QueueNode *p;

    //新建一个结点,并置其值为e

           p=new QueueNode;

           p->data=e;

    //将结点插入队列末尾

           p->next=Q.rear->next;

           Q.rear->next=p;

    //修改队尾指针

           Q.rear=p;

    }

    void DeQueue(LinkQueue &Q,Qelemtype &e)  //元素出队

    {

           QueueNode *p;

           if (EmptyQueue(Q))  //若队中无元素,则无法执行出队操作

           {

                  cout<<"error"<<endl;

                  return;

           }

           p=Q.rear->next->next;  //让p指向队头元素

           e=p->data;

      if(p==Q.rear)//如队中只有一个元素,则要rear指向头结点,头结点的next指针指向自身

      {

                  Q.rear=Q.rear->next;

         Q.rear->next=Q.rear;

       }

         else    //若队中不只一个元素,则删除p所指向的结点。

                   Q.rear->next->next=p->next;

           delete p;//释放被删除结点的存储空间

    }

     

    5.假设以I和O表示入栈和出栈操作,栈的初态和终态均为空,入栈和出栈的操作序列可表示为仅由I和O组成的序列。称可以操作的序列为合法序列,否则称为非法序列。

    (1)下面所示的序列中哪些是合法的?

    A.IOIIOIOO      B.IOOIOIIO      C.IIIOIOIO      D.IIIOOIOO

    (2)通过对问题⑴的分析,写出一个算法判定所给的操作序列是否合法。若合法返回TRUE,否则返回FALSE。(假定被判定的操作序列已经存入一维数组中)

    5.typedef struct

    {

     char data[10];

     int top;

    }stack;

     

    int descion(char *str)

    {

     stack s;

     int i;

     s.top=0;

     for(i=0;str[i];i++)

     {

      switch(str[i])

      {

        case 'I':s.data[s.top++]=str[i];break;//若为I,则如栈

        case 'O':if(s.top==0) return 0;s.top--;//若为O,则从栈中弹出一个I

       }

      }

     if(s.top==0) return 1;

     else return 0;

    }

    第四章 

    一.选择题

    1. 设有两个串 p和q,求q在p中首次出现的位置的运算称作(B )

    A.连接   B.模式匹配   C.求串长   D .求子串

    2.设字符串 S1=“ABCDEFG”,S2=“PQRST”,则运算:

    S=CONCAT(SUBSTR(S1,2,LEN(S2));SUBSTR(S1,LEN(S2),2));后的串值为 ( D)

    A.A BCDEF    B.BCDEFG    C.BCDPQRST     D. BCDEFEF

    3. 下面的说法中,只有(A  )是正确的

    A.串是一种特殊的线性表    B. 串的长度必须大于零

    C.串中元素只能是字母      D. 空串就是空白串

    5. 两个字符串相等的条件是(D  )

    A.两串的长度相等

    B.两串包含的字符相同

    C.两串的长度相等,并且两串包含的字符相同

    D.两串的长度相等,并且对应位置上的字符相同

    二、填空题

    1. 令t1=“aaab”, t2=“abcabaa”, t3=“abcaabbabcabaacba”,试分别求出他们的nex函数值   0123   ,  0111232   ,    01112231234532211  

    2.空格串的长度为  .空格数    ,空串的长度为   0   。

    3.设串S=’How are you’,则串的长度为    11     。 

    三、问答题

    回文是指正读反读均相同的字符序列,如"abba""abdba"均是回文,但"good"不是回文。试写一个算法判定给定的字符变量是否为回文。

    Status IsHuiwen( char *S)

    { i=0;

      while(s[i]!=’\0’) i++;

    i=i-1; j=0;

    while(j<i)

    if(s[j]!=s[i]) return 0;

    else {j++;i--;}

    return 1;

    }

    第五章 数组和广义表

    一.选择题

    1. 设有数组A[i,j],数组的每个元素长度为3字节,i的值为1 到8 ,j的值为1 到10,数组从内存首地址BA开始顺序存放,当用以列为主存放时,元素A[5,8]的存储首地址为(  B  )

    A. BA+141       B. BA+180          C. BA+222           D. BA+225

    2. 假设以行序为主序存储二维数组A=array[1..100,1..100],设每个数据元素占2个存储单元,基地址为10,则LOC[5,5]=(  B  )

    A. 808              B. 818              C. 1010             D. 1020

    3 对稀疏矩阵进行压缩存储目的是( C   )

    A.便于进行矩阵运算  B.便于输入和输出   C.节省存储空间   D.降低运算的时间复杂度

    4. 广义表A=(a,b,(c,d),(e,(f,g))),则下面式子的值为( D  )。

    Head(Tail(Head(Tail(Tail(A)))))

    A. (g)            B. (d)               C. c              D. d

    5.设广义表L=((a,b,c)),则L的长度和深度分别为(  B  )。

    A. 1和1         B. 1和3            C. 1和2         D. 2和3

    6. 假设以三元组表表示稀疏矩阵,则与如图所示三元组表对应的4×5的稀疏矩阵是(注:矩阵的行列下标均从1开始)( B )

    A.                            B.

     

     

    C.                                D.

    7. 一个非空的广义表的表尾( B)

    A.不能是子表    B.只能是子表   C.只能是原子   D.是原子或子表

    8. 如果将矩阵An×n的每一列看成一个子表,整个矩阵看成是一个广义表L,即L=((a11,a21,…,an1),( a12,a22,…,an2),…,(a1n,a2n,…,ann)),并且可以通过求表头head和求表尾tail的运算求取矩阵中的每一个元素,则求得a21的运算是(   A )

    A. head (tail (head (L)))   B. head (head(head(L)))

    C. tail (head (tail (L)))   D. head (head (tail (L)))

    二.填空题

    1.己知三对角矩阵A[1..9,1..9]的每个元素占2个单元,现将其三条对角线上的元素逐行存储在起始地址为1000的连续的内存单元中,则元素A[7,8]的地址为__1038____

    2.设广义表L=((),()), head(L)_()tail(L)(())_L的长度是2_;深度是2_

    3. 广义表A=(((ab),(cde))),试用求表头和表尾的操作Head( )Tail( )取出A中的原子e的操作是: _ Head(Tail(Tail(Head(Tail(Head(A))))))__.

    三.解答下列各题

    1.已知一个65列的稀疏矩阵中非零元的值分别为:-9041-7628-5465-8,它们在矩阵中的列号依次为:1451245。当以带行表的三元组表作存储结构时,其行表中的值依次为002235(行列下标均从1开始),写出该稀疏矩阵。

     

    0   0   0   0   0

    -90  0   0  41   0

    0   0   0   0   0

    0   0   0   0   -76

    28  -54  0   0   0

    0   0   0  65   -8

     

     

    2.写出广义表B=(a,b),C=(a,(b,c,(d,e))),D=(a,B,C),E=((a,b),E)的存储结构(任一种存储方法均可)

     

    1

    0   a

    1    ∧

    0  b

    B

    1

    0   a

    1    ∧

    C

    1

    1   

    0  b

    0  c

    1    ∧

    1

    0   d

    1    ∧

    0  e

    1

    1   

    0  a

    1    ∧

    D

    1

    1    ∧

    1     ∧

    0  b

    E

    1

    0   a

     

    第六章 树和二叉树

    一.选择题{CDDAC  ADDED  BCCBB  CACCC}

    1.如果在数据结构中每个数据元素只可能有一个直接前驱,但可以有多个直接后继,则该结构是( C )

    A. 栈           B. 队列       C. 树          D. 图

    2.设树T的度为4,其中度为1,2,3和4的结点个数分别为4,2,1,1  则T中的叶子数为(  D)

    A.5            B.6          C.7           D.8

    4.树的先根序列等同于与该树对应的二叉树的( A )

    A.先序序列     B.中序序列   C.后序序列   D.层序序列

    5. 用二叉链表表示具有n个结点的二叉树时,值为空的指针域的个数为(C

    A.n-1          B.n          C.n+l         D.2n

    6. 设森林F对应的二叉树为B,它有m个结点,B的根为p,p的右子树结点个数为n,森林F中第一棵树的结点个数是(A  )

    A.m-n          B.m-n-1      C.n+1         D.条件不足,无法确定

    7. 设树T的度为4,其中度为1,2,3和4的结点个数分别为4,2,1,1,则T中的叶子数为( D )

    A.5            B.6          C.7           D.8

    8.设森林F中有三棵树,第一,第二,第三棵树的结点个数分别为M1,M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是(D  )

    A.M1           B.M1+M2       C.M3         D.M2+M3

    9.一棵完全二叉树上有1001个结点,其中叶子结点的个数是( E)

    A. 250         B. 500        C.254        D.505      E.以上答案都不对   

    10.有n个叶子的哈夫曼树的结点总数为(D  )

    A.不确定       B.2n          C.2n+1       D.2n-1

    11.一棵二叉树高度为h,所有结点的度或为0,或为2,则这棵二叉树最少有( B )结点

    A.2h           B.2h-1        C.2h+1       D.h+1

    12.将有关二叉树的概念推广到三叉树,则一棵有244个结点的完全三叉树的高度( C )

    A.4            B.5           C.6          D.7

    13.若度为m的哈夫曼树中,其叶结点个数为n,则非叶结点的个数为( C )

    A.n-1     B.ën/mû-1       C.é(n-1)/(m-1)ù     D. én/(m-1)ù-1   E.é(n+1)/(m+1)ù-1

    14.若下面几个符号串编码集合中,不是前缀编码的是(B  )。

    A.{0,10,110,1111}             B.{11,10,001,101,0001}   

    C.{00,010,0110,1000}          D.{b,c,aa,ac,aba,abb,abc}

    15.一棵二叉树的前序遍历序列为ABCDEFG,它的中序遍历序列可能是( B )

    A.CABDEFG      B.ABCDEFG     C.DACEFBG    D.ADCFEG

    16.线索二叉树是一种( C )结构。

    A. 逻辑    B. 逻辑和存储   C. 物理     D.线性

    17.引入二叉线索树的目的是( A )

    A.加快查找结点的前驱或后继的速度   B.为了能在二叉树中方便的进行插入与删除

    C.为了能方便的找到双亲             D.使二叉树的遍历结果唯一

    18.n个结点的线索二叉树上含有的线索数为( C )

    A.2n      B.n-l       C.n+l         D.n

    19.若X是二叉中序线索树中一个有左孩子的结点,且X不为根,则x的前驱为( C )

    A.X的双亲                   B.X的右子树中最左的结点 

    C.X的左子树中最右结点       D.X的左子树中最右叶结点

    20.某二叉树的前序序列和后序序列正好相反,则该二叉树一定是( C )的二叉树

    A.空或只有一个结点          B.任一结点无左子树   

    C.高度等于其结点数          D.任一结点无右子树

    二.填空题

    1. 假定一棵树的嵌套括号表示法为 A ( B ( E ), C ( F ( H , I , J ), G ), D ),则该树的度为______,树的深度为_____,终端点的个数为____,但分支结点的个数为_____,双分支结点为_____,三分支结点的个数为______, C 结点的双亲结点为_________,其孩子结点为__________和为_________结点。

    2.  一棵深度为 K 的满二叉树结点总数为___________ ,一棵深度为 K 的完全二叉树的结点总数的最小值为________,最大值为____________。

    3. 由三个结点构成的二叉树,共有_____________种不同的形态。

    4. 具有100个叶子结点的完全二叉树的深度为   

    5. 高为h(h>0)的满二叉树对应森林的由    棵树构成。

     

    三.已知一个二叉树的中序序列为CBEDAHGIJF,后序序列为CEDBHJIGFA。

    1.画出该二叉树。

    2.画出该二叉树的先序线索二叉树。

    四.试找出分别满足下列条件的所有二叉树:

    1.先序序列和中序序列相同。

    2.中序序列和后序序列相同。

    3.先序序列和后序序列相同。

    五、设二叉树用二叉链表表示,设计算法求二叉树的高度

    int Depth(BiTree t)(后序遍历)

    {   if(!t)

          d=0

        else

       {dl=Depth(t->lchild);

        dr=Depth(t->rchild);

        d=1+(dl>dr?dl:dr); }

       return d;

    }

    六、设T是一棵具有n个结点的二叉树,若给定二叉树T的先序序列和中序序列,并假设T的先序序列和中序序列分别放在数组PreOrder[1..n]和InIrder[1..n]中,设计一个构造二叉树T的二叉链表存储结构的算法。

    六 //根据二叉树的先序序列和中序序列创建二叉链表

    void createBiTree(char pre[],char in[],int start,int end,int &count,BiTree &T)

    //按先序次序创建二叉链表,pre为存放先序序列的字符数组,in为存放中序序列的字符数组,

    //count为二叉树的根结点在先序序列中的序号

    //start和end为以pre[count]为根的二叉树在中序序列中的起始位置和结束位置

    //T为二叉链表的根指针,

    {

        if(start > end) T=0;

        else

        {  T=(BiTNode*) malloc(sizeof(BiTNode)); //新建根结点

           if(!T) exit(0);

           T->data=pre[count];T->lchild=T->rchild=0;

     

    for(int i=0;in[i]!='\0';i++) //查找根结点在中序序列in[ ]中的下标

       if(in[i]==pre[count]) break;

    count++;  

    if(in[i]=='\0') cout<<"input error"<<endl;

    else {

    createBiTree(pre,in,start,i-1,count,T->lchild);//根据先序序列和中序序列创建左子树

    createBiTree(pre,in,i+1,end,count,T->rchild); //根据先序序列和中序序列创建右子树

     }

    七、设用于通信的电文由字符集{a,b,c,d,e,f,g}中的字母构成,它们在电文中出现的频率分别为{0.31,0.16,0.10,0.08,0.11,0.20,0.04},回答下列问题:

    ⑴为这7个字母设计哈夫曼编码

    ⑵若对这7个字母进行等长编码,至少需要几位二进制数?

    哈夫曼树

    a: 10  b: 110   c: 010   d: 1110   e: 011   f:: 00  g:1111

    等长编码至少需要3位二进制位。

    八.设计算法以输出二叉树中先序序列的前kk>0)个结点的值。

    void  preintraverse(BiTree T, int &n)

    {  if(T)

    { n++;

    if(n<=k) {cout<<T->data;

    intraverse(T->lchild,n);

    intraverse(T->rchild ,n);}

    }

    }

    九.编写算法,对一棵二叉树统计叶子的个数

    void CountLeaf(BiTree t,int &count)(先序遍历)

    {   if(t)

       { if((t->lchild==NULL)&&(t->rchild==NULL))

             count++;

          CountLeaf(t->lchild,&count);

          CountLeaf(t->rchild,&count);

       }

    第七章

    一.选择题

    1.n个顶点,e条边的有向图的邻接矩阵中非零元素有  C    个。

    A.n            B.2e            C.e             D.n+e

    2.用邻接表存储图所用的空间大小(A)

    A.与图的顶点数和边数都有关

    B.只与图的边数有关

    C.只与图的顶点数有关

    D.与边数的平方有关

    3.有 n 条边的无向图的邻接表存储法中,链边中结点的个数是(B )个。

    A.n       B.2n        C.n/2       D.n*n

    4.一个带权无向连通图的最小生成树(A )。

    A.有一棵或多棵 .    B.只有一棵    C.一定有多棵    D.可能不存在

    二.如下所示有向图:

    1.请给出每个顶点的度,入度和出度。

     

    A

    B

    C

    D

    入度

    1

    1

    2

    1

    出度

    2

    1

    1

    1

    3

    2

    3

    2

     

    2.请画出其邻接矩阵、邻接表、逆邻接表、十字链表。

     

     

    0101

    0010

    1000

    0010

     

    邻接矩阵

    A

     

    B

     

    C

     

    D

    1       3  ∧

    2  ∧

    0  ∧

    2  ∧

    邻接表       3

    A

     

    B

     

    C

     

    D

    2  ∧

    0  ∧

    0

    逆邻接表       3

    1       3  ∧

     

     

    A

     

    B

     

    C

     

    D

    0  1   ∧

    0  3  ∧   ∧

    1  2       ∧

    2  0  ∧   ∧

    3  2  ∧   ∧

    十字链表

     

    三.试对下图所示的AOE网络,解答下列问题。

    1.求每个事件的最早发生时间ve [i]和最迟发生时间vl[i]。

    2.求每个活动的最早开始时间ee(s)和最迟开始时间el(s)。

    3.指出哪些活动加速可使整个工程提前完成。

    事件

    A

    B

    C

    D

    E

    F

    最早发生时间ve[i]

    0

    3

    2

    6

    6

    8

    最迟发生时间vl[i]

    0

    4

    2

    6

    7

    8

     

    活动

    a1

    a2

    a3

    a4

    a5

    a6

    a7

    a8

    最早开始时间

    0

    0

    3

    3

    2

    2

    6

    6

    最迟开始时间

    1

    0

    4

    4

    2

    5

    6

    7

    关键活动为a2  a5  a7,加速这些关键活动可使整个工程提前完成。

    四.写出下图所示的AOV网的所有拓扑有序序列。

    四、拓扑有序序列

    ABCDEF

    ABCEDF

    ACBDEF

    ACBEDF

    ACEBDF

     

    第九章   查找

    一.填空题

    1.采用二分法进行查找的查找表,应选择___顺序_________方式的存储结构

    2.设在有序表A[0……9]中进行二分查找,比较一次查找成功的结点数为_1____,比较二次查找成功的结点数为__2____,比较三次查找成功的结点数为__4___,比较四次查找成功的结点数为__3___,比较五次查找成功的结点数为__0___,平均查找长度为___(1+2*2+3*4+4*3)/10=2.9___。

    (3)设在线性表R[0……59]中进行分块查找,共分10块,每块长度为6,若利用顺序查找法对索引表和子块进行查找,则查找每个元素的平均查找长度为___9_______。

    二.选择题

    1.对线性表进行二分查找时,要求线性表必须( B )

    A.键值有序的链接表        B.键值有序的顺序表

    C.链接表但键值不一定有序     D.顺序但键值不一定有序

    2.有一个有序表{1,4,6,10,18,35,42,53,67,71,78,84,92,99},当用二分查找法查找键值为84的结点时,经( C )比较后查找成功。

    A.2       B. 3       C.4      D.12

    3.顺序检索一个具有n个数据元素的线性表,其时间复杂度为_____,二分检索一个具有n个数据元素的线性表,其时间复杂度为( AB )

    A. O(n)     B.O(log2n)    C.O(n2)     D.O(nlog2n)

    4.设散列表长度为m,散列函数为H(key)=key%p,为了减少发生冲突的可能性,p应取( B )

    A.小于m的最大奇数        B.小于m的最大素数

    C.小于m的最大偶数        D.小于m的最大合数

    三.解答题

    1.给定表{19,14,22,01,66,21,83,27,56,13,10}

    ①试按元素在表中的顺序构造一棵二叉排序树;

    ②判断该二叉排序树是否平衡,若不平衡,调整其为平衡二叉树。

    1、二叉排序树如下:

     

    19

     

    14

    22

    01

    66

    21

    83

    27

    56

    13

    10

    二叉排序树

     

     

     

    19

     

    14

    27

    01

    66

    22

    83

    21

    56

    13

    10

    平衡二叉树

     

    2.现有线性表的关键字集合{33,41,20,24,30,13,01,67}共8个数据元素,已知散列函数为H(k)=(3k)%11,用开放定址法解决冲突,且d1=h(k),di=(di-1+(7k)%10+1)%11(i=2,3,……),

    ①试在0~10的散列地址空间中构造散列表,并计算出等概率情况下查找成功和查找失败的平均查找长度。

    2H(33)=0   H(41)=2  H(20)=5   H(24)=6  

    H(30)=2 冲突  d1=2 H1=(H(K)+d1)%11=4

    H(13)=6冲突 d1=6 H1=(H(K)+d1)%11=1

    H(01)=3 H(63)=2 冲突   d1=2 H1=(H(K)+d1)%11=4  冲突

           d2=(2+(7*63)%10+1)%11=4    H2=(H(K)+d2)%11=(2+4) %11=6  冲突

    d3=(4+(7*63)%10+1)%11=6  H3=(H(K)+d3)%11=(2+6) %11=8

     

    33

    13

    41

    01

    30

    20

    24

     

    63

     

     

    0      1       2      3      4       5       6      7      8       9     10

    等概率情况下查找成功的平均查找长度=(1*5+2*2+1*4)/8=13/8

    第十章  排序

    一. 填空题

    1.排序是将一组任意排列的数据元素按__ ___的值从小到大或从大到小重新排列成有序的序列。

    2.在排序前,关键字值相等的不同记录间的前后相对位置保持___ 的排序方法称为稳定的排序方法。

    3.在排序前,关键字值相等的不同记录间的前后相对位置_______________的排序方法称为不稳定的排序方法。

    4.外部排序是指在排序前被排序的全部数据都存储在计算机的_____________储器中。

    5.下列程序是按关键字的值从大到小进行直接选择排序的算法,将算法补充完整。

    Select(list r,int n)

    {for(i=1;______________;i++)

    { k=i;

    for(j=i+1;_______________;j++)

    if(r[k].key<r[j].key) ______________________;

    if(_____________________)

    swap(r[k],r[i]);      /*r[k]与r[i]交换*/

    }

    }

    6.将下列按关键字值从小到大进行冒泡排序的算法补充完整。

    Bubblesort(int n,list r)

    { flag=_____________________;

    m=n-1;

    while(m>0 && flag)

    {flag=0;

    for(i=1;i<=m;i++)

    if(r[i].key____________r[i+1].key)

    {flag=_________________;

    swap(r[i],r[i+1]);   }

    m--; }}

    7.若快速排序算法中完成一趟快速排序的算法是Quickpass(SqList &r,int low,int high),将完整的快速排序递归算法补充完整。

    Quicksort(SqList &r,int s,int t)

    {if(s<t)

    {  i=Quickpass(L,s,t);

    Quicksort(r,______  ,______);

    Quicksort(r,____________);  }

    二.选择题

    1.直接插入排序的方法是从第__________个元素开始,插入前边适当位置的排序方法。

    A.1         B.2        C.3        D.n

    2.冒泡排序的方法是______________的排序方法。

    A.稳定     B.不稳定     C.外部      D.选择

     

    展开全文
  • 基础数据结构算法概念

    千次阅读 2017-10-10 16:56:39
    基本数据结构和查找算法本文主要是基础的数据结构算法概念,可能部分地方会涉及更高级的算法算法,具体内容以后会单独写的。此外一些性质还会不断补充,也希望可以得到您的指点,谢谢。数据结构 程序 = 数据...

    本文涉及更多的是概念,代码部分请参考之前写过的 2 篇博客

    排序算法 基于Javascript
    基本数据结构和查找算法

    本文主要是基础的数据结构和算法概念,可能部分地方会涉及更高级的算法和算法,具体内容以后会单独写的。此外一些性质还会不断补充,也希望可以得到您的指点,谢谢。

    数据结构

    程序 = 数据结构 + 算法

    数据结构基本概念

    1. 数据的逻辑结构:反映数据元素之间的关系的数据元素集合的表示。数据的逻辑结构包括集合、线形结构、树形结构和图形结构四种。
    2. 数据的存储结构:数据的逻辑结构在计算机存储空间种的存放形式称为数据的存储结构。常用的存储结构有顺序、链接、索引等存储结构。

    在数据结构中,没有前件的结点称为根结点,没有后件的结点成为终端结点

    数据结构的基本操作

    插入和删除是对数据结构的两种基本操作。此外还有查找、分类、合并、分解、复制和修改等。

    线性结构和非线性结构

    根据数据结构中各数据元素之间前后件关系的复杂程度,一般将数据结构分为两大类型:线性结构和非线性结构。

    • 线性结构:有且只有一个根结点;每个结点最多有一个前件,最多只有一个后件。
    • 非线性结构: 如果一个数据结构不是线性结构,称之为非线性结构。

    本文涉及一下内容:

    • 四种线性结构的存储结构:顺序表、链表、索引、散列
    • 两种常见的线性逻辑结构:队列、栈
    • 非线性逻辑结构:循环队列、双向队列、双向循环队列、树、图

    存储结构

    顺序表

    顺序表是线性表的顺序存储结构,指的是用一组地址连续的存储单元依次存储线性表的数据元素。
    顺序表具备如下两个基本特征:

    1. 顺序表中的所有元素所占的存储空间是连续的;
    2. 顺序表中各数据元素在存储空间中是按逻辑顺序依次存放的。

    假设顺序表的每个元素需占用 K 个存储单元,并以所占的第一个单元的存储地址作为数据元素的存储位置。则顺序表中第 i+1 个数据元素的存储位置 LOC(ai+1) 和第 i 个数据元素的存储位置 LOC(ai) 之间满足下列关系为:

    LOC(ai+1)=LOC(ai)+K

    LOC(ai)=LOC(a1)+(i1)K

    其中,LOC(a1)是顺序表的第一个数据元素 a1 的存储位置,通常称做顺序表的起始位置或基地址。顺序存储结构也称随机存取结构。

    顺序表常见操作(括号中为算法平均时间复杂度,没有写明的具体复杂度依赖不同算法和运算规则):

    插入(O(n))、删除(O(n))、查找、排序、分解、合并、复制(O(n))、逆转(O(n))

    链表

    链表指线性表的链式存储结构。一组任意的存储单元存储线性表的数据元素,因此,为了表示每个数据元素 ai 与其直接后继数据元素 ai+1 之间的逻辑关系,对数据元素 ai 来说,除了存储其本身的信息(数据域)之外,还需存储一个变量指示其直接后继的信息(指针域)。这两部分信息组成数据元素 ai 的存储映象,称为结点。N 个结点链结成一个链表。该链表就是传统的单向链表。

    有时,我们在单链表的第一个结点之前附设一个结点,称之为头结点,它指向表中第一个结点。头结点的数据域可 以不存储任何信息,也可存储如线性表的长度等类的附加信息,头结点的指针域存储指向第一个结点的指针。在单链表中,取得第 I 个数据元素必须从头指针出发寻找,因此,链表是非随机存取的存储结构。

    以上提到的链表指针域只包括一个指针,指向下一个数据的地址,如果我们将链表最后一个结点指针域的指针指向链表的头结点地址,就构成了一个环状的存储结构,我们称作循环链表。

    当然我们可以给每个结点的指针域再添加一个指针,使其指向前一个数据结点的地址,这样就构成了双向链表,而将头结点的前一个结点指向尾结点,同时将尾结点的下一个结点指向头结点就构成了双向循环链表。

    如果链表的尾结点的指针域指向了该链表之前的任意一个结点,我们称该链表为有环链表。环形链表就是其中一个特例

    顺序表常见操作(括号中为算法平均时间复杂度,没有写明的具体复杂度依赖不同算法和运算规则):

    插入(O(n))、删除(O(n))、查找、排序、分解、合并、复制(O(n))、逆转(O(n))

    索引

    索引存储除建立存储结点信息外,还建立附加的索引表来标识结点的地址。索引表由若干索引项组成。

    对于索引的理解最好的例子就是《新华字典》,它建立的2套索引表(拼音、部首)。字典的正文就是从“啊”到“做”的每个字的解释,有上千页,就是是数据。而前面的拼音/部首就是索引表,索引表告诉你某个读音/部首在第几页,这就好比是指向数据地址的指针。而索引表可以有一级的也可以是多级的,比如字典中的部首索引就是两级的。

    索引存储结构是用结点的索引号来确定结点存储地址,其优点是检索速度快,缺点是增加了附加的索引表,会占用较多的存储空间。

    散列

    散列存储,又称哈希(hash)存储,是一种力图将数据元素的存储位置(预留连续存储区域)与关键码之间建立确定对应关系的查找技术。散列法存储的基本思想是由结点的关键码值决定结点的存储地址。散列技术除了可以用于存储外,还可以用于查找。

    散列以数据中每个元素的关键字 K 为自变量,通过散列函数 H(k) 计算出函数值,以该函数值作为一块连续存储空间的的单元地址,将该元素存储到函数值对应的单元中。由于该函数值唯一,所以查找时间复杂度为 O(1)

    线性逻辑结构

    线性表

    线性表满足以下特征:

    1. 有且只有一个根结点 a1,它无前件;
    2. 有且只有一个终端结点 an,它无后件;
    3. 除根结点与终端结点外,其他所有结点有且只有一个前件,也有且只有一个后件。线性表中结点的个数 n 称 为线性表的长度。当 n=0 时称为空表。

    栈实际上也是一个线性表,只不过是一种特殊的线性表。栈是只能在表的一端进行插入和删除运算的线性表,通常称插入、删除这一端为栈顶(TOP),另一端为栈底(BOTTOM)。当表中没有元素时称为栈空。 栈顶元素总是后被插入(入栈)的元素,从而也是最先被移除(出栈)的元素;栈底元素总是最先被插入的元素,从而也是最后才能被移除的元素。所以栈是个 后进先出(LIFO) 的数据结构

    栈的基本运算有三种:入栈、出栈与读栈顶,时间复杂度都是O(1)

    队列

    队列是只允许在一端删除,在另一端插入的顺序表,允许删除的一端叫做队头,用对头指针 front 指向对头元素的下一个元素,允许插入的一端叫做队尾,用队尾指针 rear 指向队列中的队尾元素,因此,从排头指针 front 指向的下一个位置直到队尾指针 rear 指向的位置之间所有的元素均为队列中的元素。

    队列的修改是 先进先出(FIFO) 。往队尾插入一个元素称为入队运算。从对头删除一个元素称为退队运算。

    队列主要有两种基本运算:入队运算和退队运算,复杂度都是O(1)

    循环队列

    在实际应用中,队列的顺序存储结构一般采用循环队列的形式。所谓循环队列,就是将队列存储空间的最后一个 位置绕到第一个位置,形成逻辑上的环状空间。在实际使用循环队列时,为了能区分队满还是队列空,通常需要增加一个标志 S

    循环队列主要有两种基本运算:入队运算和退队运算,复杂度都是O(1)

    • 入队运算
      指在循环队列的队尾加入一个新元素,首先 rear=rear+1, 当 rear=m+1 时,置 rear=1,然后将新元素插入到队尾指针 指向的位置。当 S=1,rear=front,说明队列已满,不能进行入队运算,称为“上溢”。
    • 退队运算
      指在循环队列的排头位置退出一个元素并赋给指定的变量。首先 front=front+1, 并当 front=m+1 时,置 front=1, 然后 将排头指针指向的元素赋给指定的变量。当循环队列为空 S=0,不能进行退队运算,这种情况成为“下溢”。

    非线性逻辑结构

    树是一种简单的非线性结构。树型结构具有以下特点:

    1. 每个结点只有一个前件,称为父结点,没有前件的结点只有一个,称为树的根结点。
    2. 每一个结点可以有多个后件结点,称为该结点的子结点。没有后件的结点称为叶子结点
    3. 一个结点所拥有的后件个数称为结点的度
    4. 树的最大层次称为树的深度。

    二叉树

    二叉树是一种树型结构,通常采用链式存储结构,满足以下特性:

    1. 它的特点是每个结点至多只有二棵子树(即二叉树中不存在度大于 2 的结点);
    2. 二叉树的子树有左右之分,其次序不能任意颠倒。

    二叉树的基本性质

    • 在二叉树的第 i 层上至多有 2i1 个结点
    • 深度为 k 的二叉树至多有 2k1 个结点(k1)
    • 在任意一个二叉树中,度为 0 的结点总是比度为 2 的结点多一个
    • 具有 N 个结点的二叉树,其深度至少为 log2N+1
    • 霍夫曼树的带权路径长度 len=2n+1; n 为所以叶子权重和。

    二叉树的遍历

    就是遵从某种次序,访问二叉树中的所有结点,使得每个结点仅被访问一次。分为以下几种:

    1. 前序遍历(DLR): 首先访问根结点,然后遍历左子树,最后遍历右子树。
    2. 中序遍历(LDR): 首先遍历左子树,然后根结点,最后右子树
    3. 后序遍历(LRD): 首先遍历左子树,然后遍历右子树,最后访问根结点。

    此外图的遍历也可以用在树上,包括:

    1. 广度优先遍历(层序遍历): 从根结点开开始逐层向下,从左到右遍历。
    2. 深度优先遍历: 从根结点出发沿左子树遍历到叶子结点再逐层向上向遍历右子树。

    除此之外还有很多有特点的特殊二叉树:

    • 满二叉树:除最后一层以外,每一层上的所有结点都有两个子结点。
      1. 在满二叉树的第 K 层上有 2K1 个结点,且深度为 M 的满二叉树有 2M1 个结点
      2. 完全二叉树:除最后一层以外,每一层上的结点数均达到最大值;在最后一层上只缺少右边的若干结点。
      3. 具有 N 个结点的完全二叉树的深度为 log2N+1
      4. 完全二叉树总结点数为 N,则叶子结点数为N/2

    最常见的完全二叉树就是 **堆** 了。堆满足以下条件
    • 堆中某个结点的值总是不大于或不小于其父结点的值
    • 堆总是一棵完全二叉树

    将根结点最大的堆叫做 最大堆大根堆 ,根结点最小的堆叫做 最小堆小根堆

    堆具有以下基本操作:

    • 插入: 向堆中插入一个新元素
    • 获取: 获取当前堆顶元素的值
    • 删除: 删除堆顶元素
    • 包含: 判断堆中是否存在某个元素

    哈希表

    常用的哈希函数

    1. 直接寻址法: H(k) 是一个线性函数,如果该位置已经有值就向下寻找到第一个空的地方作为散列地址
    2. 平方取中法: 取 k 平方以后值的中间几位作为散列地址
    3. 数字分析法: 对于比较规律的 k 值,找出其差异较大的部分作为散列地址
    4. 折叠法: 将 k 分成很多部分,然后做模二和作为散列地址
    5. 留余数法: H(k)=k,其中 p 为素数,m 为表的长度
    6. 随机数法: 取键字的随机值作为散列地址,关键字长度时使用

    实现映射的函数是哈希函数,简单的 hash 可能会发生碰撞(不同输入得到相同输出),为了防止碰撞,考虑以下方法:

    • 链地址法(拉链法): 当发生碰撞时,将发生碰撞的数据元素连接到同一个单链表中,而新元素插入到链表的前端
    • 线性探针法: 线性探针法地址增量 dD1={1,2,3,...,m1}, i 为探测次数,m 为表的长度,该方法遇到冲突地址会依次探测下一个地址(d=di+1)直到有空的地址,若找不到空地址,则溢出。

    平均查找长度

    • 线性探针法平均长度推算(其中 m 为表中数据长度,n 为表长度):


      ASLs=i=1mdim,查找成功

      ASLu=i=1ndin,查找不成功


    注:线性探针法查找成功时 di 为每次放入元素时的地址增量,不成功时 di 为在表长度内依次查找每个元素到下一个空地址的地址增量(索引在表长度内循环)
    • 链地址法平均长度推算(其中 k 为最长链长度,其中 m 为表中数据长度,n 为表长度):


      ASLs=i=1k(×)m,查找成功

      ASLu=i=1nn,查找不成功


    哈希表相关特性
    • 线性探针法容易“聚集”,影响查找效率,而链地址法不会
    • 链地址法适应表长不确定情况
    • (α)=

    图有两种定义:

    • 二元组的定义:图 G 是一个有序二元组 (V,E),其中 V 称为顶集(Vertices Set),E 称为边集(Edges set),EV 不相交。它们亦可写成 V(G)E(G)E 的元素都是二元组,用 (x,y) 表示,其中 x,yV
    • 三元组的定义: 图 G 是指一个三元组(V,E,I),其中 V 称为顶集,E 称为边集,EV 不相交;I 称为关联函数,IE 中的每一个元素映射到V×V。如果 e 被映射到 (u,v),那么称边 e 连接顶点 u,v,而 u,v 则称作 e 的端点,u,v 此时关于 e 相邻。同时,若两条边 i,j 有一个公共顶点 u,则称 i,j 关于 u 相邻。

    图的分类

    图有不同的分类规则,具体如下:

    分类1
    - 有向图: 如果图中顶点之间关系不仅仅是连通与不连通,而且区分两边的顶点的出入(存在出边和入边),则为有向图。
    - 无向图: 如果图中顶点之间关系仅仅是连通与不连通,而不区分两边顶点的出入(不存在出边和入边),则为无向图。
    单图

    分类2
    - 有环图: 单向遍历回可以到已遍历的点,比如有环链表
    - 无环图: 单向遍历不能回到已遍历的点,比如树

    分类3
    - 带权图: 图的具有边带有关于该边信息的权值,比如地图中两点间距离
    - 无权图: 图的每个边都不具有有关于该边信息的权值,其仅表示是否连通

    其他
    - 单图: 一个图如果任意两顶点之间只有一条边且边集中不含环,则称为单图

    图的表示采用邻接矩阵和类似树的形式(顶点指针域是个指针数组)的形式,其具有以下特点:

    • 无向图的邻接矩阵是对称矩阵
    • 带权图的矩阵中元素为全职,无权图中用0/1分别表示不连通/连通
    • 主对角线有不为零元素,该图一定有环

    图的遍历

    • 广度优先遍历: 广度优先遍历是连通图的一种遍历策略。因为它的思想是从一个顶点 V0 开始,辐射状地优先遍历其周围较广的区域。
    • 深度优先遍历:

    图的相关性质:

    • N 个顶点的连通图中边的条数至少为 N1
    • N 个顶点的强连通图的边数至少有 N
    • 广度优先遍历用来找无权图最短路径(有权图其实也行,多点东西呗)

    简单数据结构的增删改查

    操作 添加 删除 查找 使用条件
    数组 O(n) O(n) O(n) 数定下标
    链表 O(1) O(n) O(n) 两端修改
    变长数组 O(1) O(n) O(n) 数不定下标
    O(1) O(1) - LIFO
    队列 O(1) O(1) - FIFO
    哈希表 O(1) O(1) O(1) key操作,无序
    树字典 O(log2n) O(log2n) O(log2n) key操作,有序
    哈希集合 O(1) O(1) O(1) 唯一值,无序
    树集合 O(log2n) O(log2n) O(log2n) 唯一值,有序

    算法

    算法基本概念

    1. 算法的基本特征:可行性,确定性,有穷性
    2. 算法的基本要素:算法中对数据的运算和操作、算法的控制结构。
    3. 算法设计的基本方法:穷举法、动态规划、贪心法、回溯法、递推法、递归法、分治法、散列法,分支限界法。
    4. 算法设计的要求:正确性、可读性、健壮性、效率与低存储量需求
    5. 算法的基本结构:顺序、循环、选择

    算法复杂度

    1. 算法的时间复杂度:指执行算法所需要的计算工作量(不代表算法实际需要时间)
    2. 算法的空间复杂度:执行这个算法所需要的额外内存空间(代表算法实际需要的空间)

    复杂度表示方法: 使用大写 O 表示:O(n)表示时间复杂度时指 n 个数据处理完成使用 n 个单位的时间;表示空间复杂度时指 n 个数据处理完成使用了 n 个单位的辅助空间。

    字符串算法

    字符串算法除了增删改查以外,还有很多匹配算法,比如最耳熟能详的 KMP 算法(不属于基础部分),这里整理一些相关算法的性质:

    • 一个长为 n 的字符串有 n(n+1)/2+1 个子串
    • n的字符串,其中的字符各不相同,则S中的互异的非平凡子串有 12n2+12n1

    排序算法

    排序算法实际上可以分为内排序和外排序:

    • 内排序:在排序过程中,所有元素调到内存中进行的排序,称为内排序。内排序是排序的基础。内排序效率用比较次数来衡量。按所用策略不同,内排序又可分为插入排序、选择排序、堆排序、归并排序、冒泡排序、快速排序、希尔排序及基数排序等等。
    • 外排序:在数据量大的情况下,只能分块排序,但块与块间不能保证有序。外排序用读/写外存的次数来衡量其效率。

    排序算法时间复杂度

    排序算法分为以下几类:

    1. 插入类排序:插入排序、希尔排序
    2. 交换类排序:冒泡排序、快速排序
    3. 选择类排序:选择排序、堆排序
    4. 归并排序
    5. 基数排序
    算法 时间复杂度(最好) 时间复杂度(最好) 时间复杂度(最坏) 空间复杂度 稳定性
    插入排序 O(n2) O(n) O(n2) O(1) 稳定
    希尔排序 O(n1.3) O(n) O(n2) O(1) 不稳定
    选择排序 O(n2) O(n2) O(n2) O(1) 不稳定
    堆排序 O(nlog2n) O(nlog2n) O(nlog2n) O(1) 不稳定
    冒泡排序 O(n2) O(n) O(n2) O(1) 稳定
    快速排序 O(nlog2n) O(nlog2n) O(n2) O(nlog2n) 不稳定
    归并排序 O(nlog2n) O(nlog2n) O(nlog2n) O(n) 稳定
    基数排序 O(d(r+n)) O(d(n+rd)) O(d(r+n)) O(n+rd) 稳定

    注:
    1. 基数排序的复杂度中,r 代表关键字基数,d 代表长度,n 代表关键字个数
    2. 排序算法的稳定性指在原序列中,ri=rj,且 rirj 之前,而在排序后的序列中,ri 仍在 rj 之前,则称这种排序算法是稳定的;否则称为不稳定的。

    查找算法

    查找算法时间复杂度

    算法 查找(最坏) 插入(最坏) 删除(最坏) 查找(最好) 插入(最好) 删除(最好) 是否要求有序
    顺序结构 N N N N2 N N2 No
    二分算法 logN N N logN N2 N2 Yes
    二叉查找树(BST) N N N 1.39logN 1.39logN N Yes
    2-3树 clogN clogN clogN clogN clogN clogN Yes
    红黑树 2logN 2logN 2logN logN logN logN Yes
    哈希散列查找 logN logN logN 3~5 3~5 3~5 No
    哈希探针查找 logN logN logN 3~5 3~5 3~5 No

    平均查找长度(ASL) = 查找表中第 i 个元素概率(Pi) × 找到第 i 个元素时已经比较的次数(Ci)

    展开全文
  • 数据结构–七大查找算法总结

    万次阅读 多人点赞 2018-08-06 17:13:43
    转 数据结构–七大查找算法总结 2017年08月15日 21:06:17 阅读数:10610 ...

      查找定义:根据给定的某个值,在查找表中确定一个其关键字等于给定值的数据元素(或记录)。

      查找算法分类:
      1)静态查找和动态查找;
        注:静态或者动态都是针对查找表而言的。动态表指查找表中有删除和插入操作的表。
      2)无序查找和有序查找。
        无序查找:被查找数列有序无序均可;
        有序查找:被查找数列必须为有序数列。
      平均查找长度(Average Search Length,ASL):需和指定key进行比较的关键字的个数的期望值,称为查找算法在查找成功时的平均查找长度。
      对于含有n个数据元素的查找表,查找成功的平均查找长度为:ASL = Pi*Ci的和。
      Pi:查找表中第i个数据元素的概率。
      Ci:找到第i个数据元素时已经比较过的次数。

    1. 顺序查找

      说明:顺序查找适合于存储结构为顺序存储或链接存储的线性表。
      基本思想:顺序查找也称为线形查找,属于无序查找算法。从数据结构线形表的一端开始,顺序扫描,依次将扫描到的结点关键字与给定值k相比较,若相等则表示查找成功;若扫描结束仍没有找到关键字等于k的结点,表示查找失败。
      复杂度分析: 
      查找成功时的平均查找长度为:(假设每个数据元素的概率相等) ASL = 1/n(1+2+3+…+n) = (n+1)/2 ;
      当查找不成功时,需要n+1次比较,时间复杂度为O(n);
      所以,顺序查找的时间复杂度为O(n)。
      C++实现源码:
    //顺序查找
    int SequenceSearch(int a[], int value, int n)
    {
        int i;
        for(i=0; i<n; i++)
            if(a[i]==value)
                return i;
        return -1;
    }
    

    2. 二分查找

      说明:元素必须是有序的,如果是无序的则要先进行排序操作。

      基本思想:也称为是折半查找,属于有序查找算法。用给定值k先与中间结点的关键字比较,中间结点把线形表分成两个子表,若相等则查找成功;若不相等,再根据k与该中间结点关键字的比较结果确定下一步查找哪个子表,这样递归进行,直到查找到或查找结束发现表中没有这样的结点。

      复杂度分析:最坏情况下,关键词比较次数为log2(n+1),且期望时间复杂度为O(log2n)

      注:折半查找的前提条件是需要有序表顺序存储,对于静态查找表,一次排序后不再变化,折半查找能得到不错的效率。但对于需要频繁执行插入或删除操作的数据集来说,维护有序的排序会带来不小的工作量,那就不建议使用。——《大话数据结构

      C++实现源码:

    //二分查找(折半查找),版本1
    int BinarySearch1(int a[], int value, int n)
    {
        int low, high, mid;
        low = 0;
        high = n-1;
        while(low<=high)
        {
            mid = (low+high)/2;
            if(a[mid]==value)
                return mid;
            if(a[mid]>value)
                high = mid-1;
            if(a[mid]<value)
                low = mid+1;
        }
        return -1;
    }
    
    //二分查找,递归版本
    int BinarySearch2(int a[], int value, int low, int high)
    {
        int mid = low+(high-low)/2;
        if(a[mid]==value)
            return mid;
        if(a[mid]>value)
            return BinarySearch2(a, value, low, mid-1);
        if(a[mid]<value)
            return BinarySearch2(a, value, mid+1, high);
    }
    

    3. 插值查找

      在介绍插值查找之前,首先考虑一个新问题,为什么上述算法一定要是折半,而不是折四分之一或者折更多呢?
      打个比方,在英文字典里面查“apple”,你下意识翻开字典是翻前面的书页还是后面的书页呢?如果再让你查“zoo”,你又怎么查?很显然,这里你绝对不会是从中间开始查起,而是有一定目的的往前或往后翻。
      同样的,比如要在取值范围1 ~ 10000 之间 100 个元素从小到大均匀分布的数组中查找5, 我们自然会考虑从数组下标较小的开始查找。
      经过以上分析,折半查找这种查找方式,不是自适应的(也就是说是傻瓜式的)。二分查找中查找点计算如下:
      mid=(low+high)/2, 即mid=low+1/2*(high-low);
      通过类比,我们可以将查找的点改进为如下:
      mid=low+(key-a[low])/(a[high]-a[low])*(high-low),
      也就是将上述的比例参数1/2改进为自适应的,根据关键字在整个有序表中所处的位置,让mid值的变化更靠近关键字key,这样也就间接地减少了比较次数。
      基本思想:基于二分查找算法,将查找点的选择改进为自适应选择,可以提高查找效率。当然,差值查找也属于有序查找。
      注:对于表长较大,而关键字分布又比较均匀的查找表来说,插值查找算法的平均性能比折半查找要好的多。反之,数组中如果分布非常不均匀,那么插值查找未必是很合适的选择。
      复杂度分析:查找成功或者失败的时间复杂度均为O(log2(log2n))。
      C++实现源码:
    //插值查找
    int InsertionSearch(int a[], int value, int low, int high)
    {
        int mid = low+(value-a[low])/(a[high]-a[low])*(high-low);
        if(a[mid]==value)
            return mid;
        if(a[mid]>value)
            return InsertionSearch(a, value, low, mid-1);
        if(a[mid]<value)
            return InsertionSearch(a, value, mid+1, high);
    }
    

    4. 斐波那契查找

      在介绍斐波那契查找算法之前,我们先介绍一下很它紧密相连并且大家都熟知的一个概念——黄金分割。

      黄金比例又称黄金分割,是指事物各部分间一定的数学比例关系,即将整体一分为二,较大部分与较小部分之比等于整体与较大部分之比,其比值约为1:0.618或1.618:1。

      0.618被公认为最具有审美意义的比例数字,这个数值的作用不仅仅体现在诸如绘画、雕塑、音乐、建筑等艺术领域,而且在管理、工程设计等方面也有着不可忽视的作用。因此被称为黄金分割。

      大家记不记得斐波那契数列:1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89…….(从第三个数开始,后边每一个数都是前两个数的和)。然后我们会发现,随着斐波那契数列的递增,前后两个数的比值会越来越接近0.618,利用这个特性,我们就可以将黄金比例运用到查找技术中。

      基本思想:也是二分查找的一种提升算法,通过运用黄金比例的概念在数列中选择查找点进行查找,提高查找效率。同样地,斐波那契查找也属于一种有序查找算法。
      相对于折半查找,一般将待比较的key值与第mid=(low+high)/2位置的元素比较,比较结果分三种情况:

      1)相等,mid位置的元素即为所求

      2)>,low=mid+1;

         3)<,high=mid-1。

      斐波那契查找与折半查找很相似,他是根据斐波那契序列的特点对有序表进行分割的。他要求开始表中记录的个数为某个斐波那契数小1,及n=F(k)-1;

     开始将k值与第F(k-1)位置的记录进行比较(及mid=low+F(k-1)-1),比较结果也分为三种

      1)相等,mid位置的元素即为所求

      2)>,low=mid+1,k-=2;

      说明:low=mid+1说明待查找的元素在[mid+1,high]范围内,k-=2 说明范围[mid+1,high]内的元素个数为n-(F(k-1))= Fk-1-F(k-1)=Fk-F(k-1)-1=F(k-2)-1个,所以可以递归的应用斐波那契查找。

      3)<,high=mid-1,k-=1。

      说明:low=mid+1说明待查找的元素在[low,mid-1]范围内,k-=1 说明范围[low,mid-1]内的元素个数为F(k-1)-1个,所以可以递归 的应用斐波那契查找。

      复杂度分析:最坏情况下,时间复杂度为O(log2n),且其期望复杂度也为O(log2n)。

      C++实现源码:

    // 斐波那契查找.cpp 
    #include "stdafx.h"
    #include <memory>;
    #include  <iostream>;
    using namespace std;
    
    const int max_size=20;//斐波那契数组的长度
    
    /*构造一个斐波那契数组*/ 
    void Fibonacci(int * F)
    {
        F[0]=0;
        F[1]=1;
        for(int i=2;i<max_size;++i)
            F[i]=F[i-1]+F[i-2];
    }
    
    /*定义斐波那契查找法*/  
    int FibonacciSearch(int *a, int n, int key)  //a为要查找的数组,n为要查找的数组长度,key为要查找的关键字
    {
      int low=0;
      int high=n-1;
      
      int F[max_size];
      Fibonacci(F);//构造一个斐波那契数组F 
    
      int k=0;
      while(n>F[k]-1)//计算n位于斐波那契数列的位置
          ++k;
    
      int  * temp;//将数组a扩展到F[k]-1的长度
      temp=new int [F[k]-1];
      memcpy(temp,a,n*sizeof(int));
    
      for(int i=n;i<F[k]-1;++i)
         temp[i]=a[n-1];
      
      while(low<=high)
      {
        int mid=low+F[k-1]-1;
        if(key<temp[mid])
        {
          high=mid-1;
          k-=1;
        }
        else if(key>temp[mid])
        {
         low=mid+1;
         k-=2;
        }
        else
        {
           if(mid<n)
               return mid; //若相等则说明mid即为查找到的位置
           else
               return n-1; //若mid&gt;=n则说明是扩展的数值,返回n-1
        }
      }  
      delete [] temp;
      return -1;
    }
    
    int main()
    {
        int a[] = {0,16,24,35,47,59,62,73,88,99};
        int key=100;
        int index=FibonacciSearch(a,sizeof(a)/sizeof(int),key);
        cout<<key<<" is located at:"<<index;
        return 0;
    }
    

    5. 树表查找

      5.1 最简单的树表查找算法——二叉树查找算法。

      基本思想:二叉查找树是先对待查找的数据进行生成树,确保树的左分支的值小于右分支的值,然后在就行和每个节点的父节点比较大小,查找最适合的范围。 这个算法的查找效率很高,但是如果使用这种查找方法要首先创建树。 

      二叉查找树(BinarySearch Tree,也叫二叉搜索树,或称二叉排序树Binary Sort Tree)或者是一棵空树,或者是具有下列性质的二叉树:

      1)若任意节点的左子树不空,则左子树上所有结点的值均小于它的根结点的值;

      2)若任意节点的右子树不空,则右子树上所有结点的值均大于它的根结点的值;

      3)任意节点的左、右子树也分别为二叉查找树。

      二叉查找树性质对二叉查找树进行中序遍历,即可得到有序的数列。

      不同形态的二叉查找树如下图所示:

       有关二叉查找树的查找、插入、删除等操作的详细讲解,请移步浅谈算法和数据结构: 七 二叉查找树

      复杂度分析:它和二分查找一样,插入和查找的时间复杂度均为O(logn),但是在最坏的情况下仍然会有O(n)的时间复杂度。原因在于插入和删除元素的时候,树没有保持平衡(比如,我们查找上图(b)中的“93”,我们需要进行n次查找操作)。我们追求的是在最坏的情况下仍然有较好的时间复杂度,这就是平衡查找树设计的初衷。

      下图为二叉树查找和顺序查找以及二分查找性能的对比图:

     

      基于二叉查找树进行优化,进而可以得到其他的树表查找算法,如平衡树、红黑树等高效算法。

      5.2 平衡查找树之2-3查找树(2-3 Tree)

      2-3查找树定义:和二叉树不一样,2-3树运行每个节点保存1个或者两个的值。对于普通的2节点(2-node),他保存1个key和左右两个自己点。对应3节点(3-node),保存两个Key,2-3查找树的定义如下:

      1)要么为空,要么:

      2)对于2节点,该节点保存一个key及对应value,以及两个指向左右节点的节点,左节点也是一个2-3节点,所有的值都比key要小,右节点也是一个2-3节点,所有的值比key要大。

      3)对于3节点,该节点保存两个key及对应value,以及三个指向左中右的节点。左节点也是一个2-3节点,所有的值均比两个key中的最小的key还要小;中间节点也是一个2-3节点,中间节点的key值在两个跟节点key值之间;右节点也是一个2-3节点,节点的所有key值比两个key中的最大的key还要大。

    Definition of 2-3 tree

      2-3查找树的性质:

      1)如果中序遍历2-3查找树,就可以得到排好序的序列;

      2)在一个完全平衡的2-3查找树中,根节点到每一个为空节点的距离都相同。(这也是平衡树中“平衡”一词的概念,根节点到叶节点的最长距离对应于查找算法的最坏情况,而平衡树中根节点到叶节点的距离都一样,最坏情况也具有对数复杂度。)

      性质2)如下图所示:

     

      复杂度分析:

      2-3树的查找效率与树的高度是息息相关的。

    • 在最坏的情况下,也就是所有的节点都是2-node节点,查找效率为lgN
    • 在最好的情况下,所有的节点都是3-node节点,查找效率为log3N约等于0.631lgN

      距离来说,对于1百万个节点的2-3树,树的高度为12-20之间,对于10亿个节点的2-3树,树的高度为18-30之间。

      对于插入来说,只需要常数次操作即可完成,因为他只需要修改与该节点关联的节点即可,不需要检查其他节点,所以效率和查找类似。下面是2-3查找树的效率:

    analysis of 2-3 tree

     

      5.3 平衡查找树之红黑树(Red-Black Tree)

      2-3查找树能保证在插入元素之后能保持树的平衡状态,最坏情况下即所有的子节点都是2-node,树的高度为lgn,从而保证了最坏情况下的时间复杂度。但是2-3树实现起来比较复杂,于是就有了一种简单实现2-3树的数据结构,即红黑树(Red-Black Tree)。

      基本思想:红黑树的思想就是对2-3查找树进行编码,尤其是对2-3查找树中的3-nodes节点添加额外的信息。红黑树中将节点之间的链接分为两种不同类型,红色链接,他用来链接两个2-nodes节点来表示一个3-nodes节点。黑色链接用来链接普通的2-3节点。特别的,使用红色链接的两个2-nodes来表示一个3-nodes节点,并且向左倾斜,即一个2-node是另一个2-node的左子节点。这种做法的好处是查找的时候不用做任何修改,和普通的二叉查找树相同。

    Red black tree

      红黑树的定义:

      红黑树是一种具有红色和黑色链接的平衡查找树,同时满足:

    • 红色节点向左倾斜
    • 一个节点不可能有两个红色链接
    • 整个树完全黑色平衡,即从根节点到所以叶子结点的路径上,黑色链接的个数都相同。

      下图可以看到红黑树其实是2-3树的另外一种表现形式:如果我们将红色的连线水平绘制,那么他链接的两个2-node节点就是2-3树中的一个3-node节点了。

    1-1 correspondence between 2-3 and LLRB

      红黑树的性质整个树完全黑色平衡,即从根节点到所以叶子结点的路径上,黑色链接的个数都相同(2-3树的第2)性质,从根节点到叶子节点的距离都相等)。

      复杂度分析:最坏的情况就是,红黑树中除了最左侧路径全部是由3-node节点组成,即红黑相间的路径长度是全黑路径长度的2倍。

      下图是一个典型的红黑树,从中可以看到最长的路径(红黑相间的路径)是最短路径的2倍:

    a typic red black tree

      红黑树的平均高度大约为logn。

      下图是红黑树在各种情况下的时间复杂度,可以看出红黑树是2-3查找树的一种实现,它能保证最坏情况下仍然具有对数的时间复杂度。

      红黑树这种数据结构应用十分广泛,在多种编程语言中被用作符号表的实现,如:

    • Java中的java.util.TreeMap,java.util.TreeSet;
    • C++ STL中的:map,multimap,multiset;
    • .NET中的:SortedDictionary,SortedSet 等。

      5.4 B树和B+树(B Tree/B+ Tree)

      平衡查找树中的2-3树以及其实现红黑树。2-3树种,一个节点最多有2个key,而红黑树则使用染色的方式来标识这两个key。

      维基百科对B树的定义为“在计算机科学中,B树(B-tree)是一种树状数据结构,它能够存储数据、对其进行排序并允许以O(log n)的时间复杂度运行进行查找、顺序读取、插入和删除的数据结构。B树,概括来说是一个节点可以拥有多于2个子节点的二叉查找树。与自平衡二叉查找树不同,B树为系统最优化大块数据的读和写操作。B-tree算法减少定位记录时所经历的中间过程,从而加快存取速度。普遍运用在数据库文件系统

      B树定义:

      B树可以看作是对2-3查找树的一种扩展,即他允许每个节点有M-1个子节点。

    • 根节点至少有两个子节点

    • 每个节点有M-1个key,并且以升序排列

    • 位于M-1和M key的子节点的值位于M-1 和M key对应的Value之间

    • 其它节点至少有M/2个子节点

      下图是一个M=4 阶的B树:

      可以看到B树是2-3树的一种扩展,他允许一个节点有多于2个的元素。B树的插入及平衡化操作和2-3树很相似,这里就不介绍了。下面是往B树中依次插入

    6 10 4 14 5 11 15 3 2 12 1 7 8 8 6 3 6 21 5 15 15 6 32 23 45 65 7 8 6 5 4

    的演示动画:

      B+树定义:

      B+树是对B树的一种变形树,它与B树的差异在于:

    • 有k个子结点的结点必然有k个关键码;
    • 非叶结点仅具有索引作用,跟记录有关的信息均存放在叶结点中。
    • 树的所有叶结点构成一个有序链表,可以按照关键码排序的次序遍历全部记录。

      如下图,是一个B+树:

    B Plus tree

     

      下图是B+树的插入动画:

     

      B和B+树的区别在于,B+树的非叶子结点只包含导航信息,不包含实际的值,所有的叶子结点和相连的节点使用链表相连,便于区间查找和遍历。

      B+ 树的优点在于:

    • 由于B+树在内部节点上不好含数据信息,因此在内存页中能够存放更多的key。 数据存放的更加紧密,具有更好的空间局部性。因此访问叶子几点上关联的数据也具有更好的缓存命中率。
    • B+树的叶子结点都是相链的,因此对整棵树的便利只需要一次线性遍历叶子结点即可。而且由于数据顺序排列并且相连,所以便于区间查找和搜索。而B树则需要进行每一层的递归遍历。相邻的元素可能在内存中不相邻,所以缓存命中性没有B+树好。

      但是B树也有优点,其优点在于,由于B树的每一个节点都包含key和value,因此经常访问的元素可能离根节点更近,因此访问也更迅速。

      下面是B 树和B+树的区别图:

    Different between B tree and B plus tree

      B/B+树常用于文件系统和数据库系统中,它通过对每个节点存储个数的扩展,使得对连续的数据能够进行较快的定位和访问,能够有效减少查找时间,提高存储的空间局部性从而减少IO操作。它广泛用于文件系统及数据库中,如:

    • Windows:HPFS文件系统;
    • Mac:HFS,HFS+文件系统;
    • Linux:ResiserFS,XFS,Ext3FS,JFS文件系统;
    • 数据库:ORACLE,MYSQL,SQLSERVER等中。

      有关B/B+树在数据库索引中的应用,请看张洋的MySQL索引背后的数据结构及算法原理这篇文章,这篇文章对MySQL中的如何使用B+树进行索引有比较详细的介绍,推荐阅读。

      树表查找总结:

      二叉查找树平均查找性能不错,为O(logn),但是最坏情况会退化为O(n)。在二叉查找树的基础上进行优化,我们可以使用平衡查找树。平衡查找树中的2-3查找树,这种数据结构在插入之后能够进行自平衡操作,从而保证了树的高度在一定的范围内进而能够保证最坏情况下的时间复杂度。但是2-3查找树实现起来比较困难,红黑树是2-3树的一种简单高效的实现,他巧妙地使用颜色标记来替代2-3树中比较难处理的3-node节点问题。红黑树是一种比较高效的平衡查找树,应用非常广泛,很多编程语言的内部实现都或多或少的采用了红黑树。

      除此之外,2-3查找树的另一个扩展——B/B+平衡树,在文件系统和数据库系统中有着广泛的应用。


    6. 分块查找

      分块查找又称索引顺序查找,它是顺序查找的一种改进方法。
      算法思想:将n个数据元素"按块有序"划分为m块(m ≤ n)。每一块中的结点不必有序,但块与块之间必须"按块有序";即第1块中任一元素的关键字都必须小于第2块中任一元素的关键字;而第2块中任一元素又都必须小于第3块中的任一元素,……
      算法流程:
      step1 先选取各块中的最大关键字构成一个索引表;
      step2 查找分两个部分:先对索引表进行二分查找或顺序查找,以确定待查记录在哪一块中;然后,在已确定的块中用顺序法进行查找。


    7. 哈希查找

      什么是哈希表(Hash)?

      我们使用一个下标范围比较大的数组来存储元素。可以设计一个函数(哈希函数, 也叫做散列函数),使得每个元素的关键字都与一个函数值(即数组下标)相对应,于是用这个数组单元来存储这个元素;也可以简单的理解为,按照关键字为每一个元素"分类",然后将这个元素存储在相应"类"所对应的地方。但是,不能够保证每个元素的关键字与函数值是一一对应的,因此极有可能出现对于不同的元素,却计算出了相同的函数值,这样就产生了"冲突",换句话说,就是把不同的元素分在了相同的"类"之中。后面我们将看到一种解决"冲突"的简便做法。
      总的来说,"直接定址"与"解决冲突"是哈希表的两大特点。

      什么是哈希函数?

      哈希函数的规则是:通过某种转换关系,使关键字适度的分散到指定大小的的顺序结构中,越分散,则以后查找的时间复杂度越小,空间复杂度越高。

      算法思想:哈希的思路很简单,如果所有的键都是整数,那么就可以使用一个简单的无序数组来实现:将键作为索引,值即为其对应的值,这样就可以快速访问任意键的值。这是对于简单的键的情况,我们将其扩展到可以处理更加复杂的类型的键。

      算法流程:

      1)用给定的哈希函数构造哈希表;
      2)根据选择的冲突处理方法解决地址冲突;
        常见的解决冲突的方法:拉链法和线性探测法。详细的介绍可以参见:浅谈算法和数据结构: 十一 哈希表
      3)在哈希表的基础上执行哈希查找。
      哈希表是一个在时间和空间上做出权衡的经典例子。如果没有内存限制,那么可以直接将键作为数组的索引。那么所有的查找时间复杂度为O(1);如果没有时间限制,那么我们可以使用无序数组并进行顺序查找,这样只需要很少的内存。哈希表使用了适度的时间和空间来在这两个极端之间找到了平衡。只需要调整哈希函数算法即可在时间和空间上做出取舍。

      复杂度分析

      单纯论查找复杂度:对于无冲突的Hash表而言,查找复杂度为O(1)(注意,在查找之前我们需要构建相应的Hash表)。

      使用Hash,我们付出了什么?
      我们在实际编程中存储一个大规模的数据,最先想到的存储结构可能就是map,也就是我们常说的KV pair,经常使用Python的博友可能更有这种体会。使用map的好处就是,我们在后续处理数据处理时,可以根据数据的key快速的查找到对应的value值。map的本质就是Hash表,那我们在获取了超高查找效率的基础上,我们付出了什么?

      Hash是一种典型以空间换时间的算法,比如原来一个长度为100的数组,对其查找,只需要遍历且匹配相应记录即可,从空间复杂度上来看,假如数组存储的是byte类型数据,那么该数组占用100byte空间。现在我们采用Hash算法,我们前面说的Hash必须有一个规则,约束键与存储位置的关系,那么就需要一个固定长度的hash表,此时,仍然是100byte的数组,假设我们需要的100byte用来记录键与位置的关系,那么总的空间为200byte,而且用于记录规则的表大小会根据规则,大小可能是不定的。

      Hash算法和其他查找算法的性能对比:

    search method efficient conclusion

    展开全文
  • 数据结构算法常见笔试题

    万次阅读 多人点赞 2017-09-10 11:03:57
    1.数据结构算法常见笔试题   第一章 数据结构算法 一.算法的基本概念 计算机解题的过程实际上是在实施某种算法,这种算法称为计算机算法。 1.算法的基本特征:可行性,确定性,有穷性,拥有足够的情报。 2....
  • 数据结构之排序算法

    2018-07-07 21:13:10
    数据结构之排序算法   稳定排序:冒泡、插入、归并、基数 稳定排序:选择、快速、希尔、堆   口诀就是:快(快速)些(希尔)选(选择)一堆(堆)好朋友来玩吧!   1.冒泡排序 冒泡排序(Bubble Sort...
  • 数据结构-查找算法总结

    千次阅读 2017-09-07 18:45:18
    本文将对数据结构中各种查找算法进行总结。
  • 一、绪论 什么是数据结构? 数据结构是一门研究非数值的程序设计问题中的操作对象,以及它们之间的关系和操作等相关问题的学科。...集合结构:结合结构的数据元素除了同属于一个集合外,他们之间没有其他
  • 数据结构算法面试总结

    千次阅读 2012-03-15 09:44:48
    2.算法的基本要素:算法中对数据的运算和操作、算法的控制结构。 3.算法设计的基本方法:列举法、归纳法、递推、递归、减半递推技术、回溯法。 4.算法设计的要求:正确性、可读性、健壮性、效率与低存储量需求 二...
  • 数据结构算法 试题

    千次阅读 2012-04-13 18:01:01
    部分 数据结构算法 1. 假设执行语句S的时间为O(1),则执行下列程序短的时间为() for(i=1;i  for(j=I;j  S; A. O(n) B. O(n2) C. O(n*i) D. O(n+1)   2.  二位数组A[10…20,5…1
  • 数据结构算法题汇总

    千次阅读 2019-04-13 19:40:07
    3. 算法一般都可以用哪几种控制结构组合而成? 答案:顺序、选择、循环。 4. 算法的时间复杂度是指? 答案:算法执行过程中所需要的基本运算次数。 5. 算法的空间复杂度是指? 答案:执行过程中所需要的存储空间。...
  • 数据结构算法总结

    千次阅读 2018-03-26 18:44:56
    数据结构算法总结 https://blog.csdn.net/u010273362/article/details/77920891 标签:数据结构 /算法 1.数据结构算法...
  • 归并排序(MERGE-SORT)是利用归并的思想实现的排序方法,该算法采用经典的分治(divide-and-conquer)策略(分治法将问题分(divide)成一些小的问题然后递归求解,而治(conquer)的阶段则将分的阶段得到的各答案"修补...
  • 来自coursera的课程:普林斯顿大学的算法。 通俗地讲,在一堆item上进行两种操作,一是合并,即将某两个item所在的集合合并为一个大集合;二是查询,即给定的两个item是否属于同一个集合。 高效快速地支持这种...
  • MySQL索引背后的数据结构算法原理
  • 数据结构算法的描述和分析

    千次阅读 2018-08-17 19:25:49
    数据结构概论 高级语言程序设计在解决某一实际问题的一般步骤是:分析实际问题、确定数学模型、设计或选择一个求解此数学模型的算法、编写程序进行调试和测试解决问题等几个步骤。 例1:已知:游泳池的长length和...
  • 下列不属于线性结构的是: 串 队列 栈 二叉树 Question 2 以下哪种结构是逻辑结构,而与存储和运算无关: 单链表 散列表 线性表 顺序表 Question 3 计算运行下列程序段后m的值: n = 10; m = 0; for (i...
  • MySQL索引的数据结构以及算法原理

    万次阅读 多人点赞 2018-04-19 22:13:28
    写在前面的话 在编程领域有一句人尽皆知的法则“程序 = 数据结构 + 算法”,我个人是太赞同这句话(因为我觉得程序仅仅是数据结构算法),但是在日常的学习和工作中我确认深深感受到数据结构算法的重要性,...
  • 复习 - 算法与数据结构

    千次阅读 2012-01-12 09:45:42
    最近有个考试,是关于算法和数据结构的。很久没有看了,赶快补一下。 这个地方有个连接,比较简洁,关于遍历二叉树,还有动态演示,可以看看。 ... ...目
  • 数据结构算法总论

    千次阅读 2004-09-03 01:32:00
    关键字 数据结构 算法 泛型设计 (一)何谓数据结构 数据结构是在整个计算机科学与技术领域上广泛被使用的术语。它用来反映一个数据的内部构成,即一个数据由那些成分数据构成,以什么方式构成,呈什么结构。数据...
  • Mysql数据结构算法原理

    万次阅读 2018-04-06 21:01:42
    特别需要说明的是,MySQL支持诸多存储引擎,而各种存储引擎对索引的支持也各相同,因此MySQL数据库支持多种索引类型,如BTree索引,哈希索引,全文索引等等。为了避免混乱,本文将只关注于BTree索引,因为这是平常...
  • 数据结构算法知识总结(一)

    千次阅读 2020-04-24 17:15:07
    下面是对学习数据结构与算法一些基础知识总结,主要讲解...数据结构是指相互之间存在一种或者多种特定关系的数据元素的集合。通常情况下,精心选择的数据结构可以带来更高的运行或者存储效果。数据结构往往同高效的...
  • 算法和数据结构学习笔记

    千次阅读 2016-03-24 19:48:07
    算法和数据结构就是编程的一个重要部分,你若失掉了算法和数据结构,你就把一切都失掉了。 一、数据结构和算法绪论 ...其中的逻辑结构是指数据对象中数据元素之间的相互关系,也是我们最需要关注和讨论的问
  • 数据结构算法这门计算机必修课对于技术人员来说是必须的并且对于编程能力的提高很重要。我最近正在复习数据结和算法,在这里将看的视频中的精华总结出来,争取每日一更。总结一下对于我自己来说也是一种提高。  ...
  • 常用查找数据结构算法(Python实现)
  • 数据结构基础与常见算法

    千次阅读 2017-07-16 15:17:01
    链表,在内存上可以连续,每个链表节点包括数据可其他节点的地址信息。 数组优点: 内存空间占有少,因为链表节点保存其他节点的信息。 数组内的数据是随机访问的,数据查找速度快 链表优点: 数组需要连续内存...
  • C++ 数据结构算法

    千次阅读 2018-02-05 06:47:43
    集合结构,集合结构中的数据元素除了同属于一个集合外,他们之间没有其他不三不四的关系。 线性结构,线性结构中的数据元素之间是一对一的关系。 树形结构,树形结构中,数据元素之间存在一种一对多的层次关系。 ...
  • 为了与大家取得“共同的语言”,下面对一些概念和术语赋予确定的含义。 1、数据(data):对客观事物的符号...一个数据元素可以由若干个数据项(data item)组成,数据项是数据可分割的最小单位。 3、数据对

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 32,914
精华内容 13,165
关键字:

下列不属于算法结构的是