精华内容
下载资源
问答
  • 数据结构知识整理

    万次阅读 多人点赞 2018-07-30 18:50:47
    基于严蔚敏及吴伟民编著的清华大学C语言版教材并结合网上相关资料整理(http://www.docin.com/p-2027739005.html) ...数据:对客观事物的符号表示,在计算机科学是指所有能输入到计算机并被计算...

    基于严蔚敏及吴伟民编著的清华大学C语言版教材并结合网上相关资料整理(http://www.docin.com/p-2027739005.html)

    第一章:绪论

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

    2.数据结构涵盖的内容:

    3.基本概念和术语:

    数据:对客观事物的符号表示,在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。

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

    数据对象:性质相同的数据元素的集合,是数据的一个子集。

    数据结构:相互之间存在一种或多种特定关系的数据元素的集合。

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

    4.算法和算法分析

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

    算法五个特性:有穷性,确定性,可行性,输入,输出。

    2)算法设计要求:正确性,可读性,健壮性,效率与低存储量需求。

    3)算法分析:时间复杂度,空间复杂度,稳定性

     

    第二章:线性表

    1.线性结构特点:在数据元素的非空有限集合中,(1)存在唯一的一个被称做“第一个”的数据元素;(2)存在唯一的一个被称做“最后一个”的数据元素;(3)除第一个之外,集合中的每个数据元素均只有一个前驱;(4)除最后一个之外,集合中每个数据元素均只有一个后继。

    2.线性表定义:有限个性质相同的数据元素组成的序列。

    3.线性表的存储结构:顺序存储结构和链式存储结构

    顺序存储定义:把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构。

    通常用数组来描述数据结构中的顺序存储结构。

    链式存储结构: 其结点在存储器中的位置是随意的,即逻辑上相邻的数据元素在物理上不一定相邻。通过指针来实现。

    数据结构的基本运算:修改、插入、删除、查找、排序

    4.线性表的顺序表示和实现

    1)修改:通过数组的下标便可访问某个特定元素并修改。

    时间复杂度O(1)

    2) 插入:在线性表的第i个位置前插入一个元素

    实现步骤:

       ①将第n至第i 位的元素逐一向后移动一个位置;

       ②将要插入的元素写到第i个位置;

       ③表长加1。

       注意:事先应判断: 插入位置i 是否合法?表是否已满?

       应当符合条件: 1≤i≤n+1  或  i=[1, n+1]

       核心语句:

    for (j=n; j>=i; j--)

    a[j+1]=a[ j ]; 

    a[ i ]=x;   

    n++;

      插入时的平均移动次数为:n(n+1)/2÷(n+1)=n/2≈O(n)

    3)删除:删除线性表的第i个位置上的元素

      实现步骤:

      ①将第i+1 至第n 位的元素向前移动一个位置;

      ②表长减1。

      注意:事先需要判断,删除位置i 是否合法?

      应当符合条件:1≤i≤n  或  i=[1, n]

      核心语句:

    {

        for ( j=i+1; j<=n; j++ )

        a[j-1]=a[j]; 

        n--;

    }

      顺序表删除一元素的时间效率为:T(n)=(n-1)/2 O(n)

      顺序表插入、删除算法的平均空间复杂度为O(1)

    5.线性表的链式表示和实现

    线性链表:用一组任意的存储单元存储线性表的数据元素(这组存储单元可以是连续的,也可以是不连续的)。

    一个数据元素称为一个结点,包括两个域:存储数据元素信息的域称为数据域;存储直接后继存储位置的域称为指针域。指针域中存储的信息称作指针或链。

    由于链表的每个结点中只包含一个指针域,故线性链表又称为单链表。

    1)单链表的修改(或读取)

    思路:要修改第i个数据元素,必须从头指针起一直找到该结点的指针preturn p;  

    然后才能:p->data=new_value

    读取第i个数据元素的核心语句是:

    Linklist *find(Linklist *head ,int i)

    { 

       int j=1;

       Linklist *p;

       P=head->next;

       While((p!=NULL)&&(j<i))

       {

           p=p->next;

           j++;

        }

    }

    2)单链表的插入

    链表插入的核心语句:

    Step 1:s->next=p->next;

    Step 2:p->next=s;

    3)单链表的删除

    删除动作的核心语句(要借助辅助指针变量q):

    q = p->next;           //首先保存b的指针,靠它才能找到c;

    p->next=q->next;  //将a、c两结点相连,淘汰b结点;

    free(q) ;               //彻底释放b结点空间

    4)双向链表的插入操作

    设p已指向第i 元素,请在第 i 元素前插入元素 x:

    ① ai-1的后继从 ai ( 指针是p)变为 x(指针是s) :

                    s->next = p  ;   p->prior->next = s ;

    ② ai  的前驱从ai-1 ( 指针是p->prior)变为 x ( 指针是s);

                    s->prior = p ->prior ; p->prior = s ;

    5)双向链表的删除操作

    设p指向第i 个元素,删除第 i 个 元素

    后继方向:ai-1的后继由ai ( 指针p)变为ai+1(指针 p ->next );

                       p ->prior->next =  p->next  ;

    前驱方向:ai+1的前驱由ai ( 指针p)变为ai-1 (指针 p -> prior );

                     p->next->prior = p ->prior ;

    6.循环链表

    循环链表是另一种形式的链式存储结构。它的特点是表中最后一个结点的指针域指向头结点,整个链表形成一个环。

    循环链表的操作和线性链表基本一致,差别仅在于算法中的循环条件不是p或p->next是否为空,而是它们是否等于头指针。

    学习重点:

    • 线性表的逻辑结构,指线性表的数据元素间存在着线性关系。在顺序存储结构中,元素存储的先后位置反映出这种线性关系,而在链式存储结构中,是靠指针来反映这种关系的。

    • 顺序存储结构用一维数组表示,给定下标,可以存取相应元素,属于随机存取的存储结构。

    • 链表操作中应注意不要使链意外“断开”。因此,若在某结点前插入一个元素,或删除某元素,必须知道该元素的前驱结点的指针。

    • 掌握通过画出结点图来进行链表(单链表、循环链表等)的生成、插入、删除、遍历等操作。

    • 数组(主要是二维)在以行序/列序为主的存储中的地址计算方法。

    补充重点:

    • 每个存储结点都包含两部分:数据域和指针域(链域)

    • 在单链表中,除了首元结点外,任一结点的存储位置由 其直接前驱结点的链域的值 指示。

    • 在链表中设置头结点有什么好处?

        头结点即在链表的首元结点之前附设的一个结点,该结点的数据域可以为空,也可存放表长度等附加信息,其作用是为了对链表进行操作时,可以对空表、非空表的情况以及对首元结点进行统一处理,编程更方便。

    • 如何表示空表?

    (1)无头结点时,当头指针的值为空时表示空表;

    (2)有头结点时,当头结点的指针域为空时表示空表。

    • 链表的数据元素有两个域,不再是简单数据类型,编程时该如何表示?

     因每个结点至少有两个分量,且数据类型通常不一致,所以要采用结构数据类型。

    • sizeof(x)——  计算变量x的长度(字节数);

              malloc(m) —  开辟m字节长度的地址空间,并返回这段空间的首地址;

              free(p)   —— 释放指针p所指变量的存储空间,即彻底删除一个变量。

    • 链表的运算效率分析:

    (1)查找 

    因线性链表只能顺序存取,即在查找时要从头指针找起,查找的时间复杂度为 O(n)。

    (2) 插入和删除 

    因线性链表不需要移动元素,只要修改指针,一般情况下时间复杂度为 O(1)。

    但是,如果要在单链表中进行前插或删除操作,因为要从头查找前驱结点,所耗时间复杂度将是 O(n)。

    例:在n个结点的单链表中要删除已知结点*P,需找到它的前驱结点的地址,其时间复杂度为 O(n)

    • 顺序存储和链式存储的区别和优缺点?

        顺序存储时,逻辑上相邻的数据元素,其物理存放地址也相邻。顺序存储的优点是存储密度大,存储空间利用率高;缺点是插入或删除元素时不方便。

      链式存储时,相邻数据元素可随意存放,但所占存储空间分两部分,一部分存放结点值,另一部分存放表示结点间关系的指针。链式存储的优点是插入或删除元素时很方便,使用灵活。缺点是存储密度小,存储空间利用率低。

    • 顺序表适宜于做查找这样的静态操作;

    • 链表宜于做插入、删除这样的动态操作。

    • 若线性表的长度变化不大,且其主要操作是查找,则采用顺序表;

    • 若线性表的长度变化较大,且其主要操作是插入、删除操作,则采用链表。

    ① 数组中各元素具有统一的类型;

    ② 数组元素的下标一般具有固定的上界和下界,即数组一旦被定义,它的维数和维界就不再改变。

    ③数组的基本操作比较简单,除了结构的初始化和销毁之外,只有存取元素和修改元素值的操作。

    • 三元素组表中的每个结点对应于稀疏矩阵的一个非零元素,它包含有三个数据项,分别表示该元素的 行下标  、列下标 和 元素值 。

    第三章:栈和队列

    1.栈:限定仅在表尾进行插入或删除操作的线性表。

    栈的基本操作:在栈顶进行插入或删除,栈的初始化、判空及取栈顶元素等。

    入栈口诀:堆栈指针top “先压后加”

    出栈口诀:堆栈指针top “先减后弹”

    top=0表示空栈。

     

    2.栈的表示和实现

         1)构造一个空栈S

        Status InitStack(SqStack &S)

        {

            S.base = (SElemType *) malloc(STACK_INIT_SIZE * sizeof(SElemType));

            if(!S.base) exit (OVERFLOW); //存储分配失败

                S.top = S.base;

                S.stacksize = STACK_INIT_SIZE;

                return OK;

        }

     

        2)返回栈顶元素

           Status GetTop(SqStack S, SElemType e) 

            {//若栈不空,则用e返回S的栈顶元素,并返回OK,否则返回ERROR

                if(S.top == S.base) return ERROR;

                e = *(S.top-1);

                return OK; 

            }//GetTop

     

        3)顺序栈入栈函数PUSH()

    Status Push(SqStack &S, SElemType e)

    { //插入元素e为新的栈顶元素

        if(S.top-S.base>=S.stacksize)//栈满,追加存储空间

       {

        s.base = (SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType));

        if(!S.base) exit(OVERFLOW);//存储分配失败

        S.top = S.base + S.stacksize;

        S.stacksize += STACKINCREMENT;

        }

        *S.top++ =e;

        return OK:

    }//PUSH

    4)顺序栈出栈函数POP()

    status Pop( SqStack &S,SElemType &e)

    { //若栈不空,则删除S的栈顶元素,用e返回其值,并返回OK,否则返回ERROR

        if(S.top == S.base) return ERROR; 

        e=* —S.top;

        return OK;

            }

    3.栈的应用

    数制转换,括号匹配的检验,行编辑程序,迷宫求解,表达式求值,递归实现。

    4.队列:是一种先进先出的线性表,它只允许在表的一端进行插入,而在另一端删除元素。

    允许插入的一端叫做队尾,允许删除的一端叫做队头。

    除了栈和队列外,还有一种限定性数据结构是双端队列。双端队列是限定插入和删除操作在表的两端进行的线性表。

    5.链队列结点类型定义:

     typedef Struct QNode{

         QElemType        data;     //元素

         Struct   QNode   *next;  //指向下一结点的指针

       }Qnode , * QueuePtr ;

    链队列类型定义:

     typedef  struct {

      QueuePtr     front ; //队首指针

      QueuePtr     rear ; //队尾指针

      }  LinkQueue;

    链队示意图:

    ①  空链队的特征:front=rear

    ②  链队会满吗?一般不会,因为删除时有free动作。除非内存不足!

    ③  入队(尾部插入):rear->next=S; rear=S;

        出队(头部删除):front->next=p->next;

    6.顺序队

    顺序队类型定义:

    #define    QUEUE-MAXSIZE  100  //最大队列长度

         typedef    struct {

                QElemType     *base;    //队列的基址

                 int                    front;     //队首指针

                 int                     rear;    //队尾指针

           }SqQueue

    建队核心语句:

    q.base=(QElemType *)malloc(sizeof (QElemType)* QUEUE_MAXSIZE);       //分配空间

    顺序队示意图:

    7.循环队列:

    队空条件 :  front = rear       (初始化时:front = rear )

    队满条件: front = (rear+1) % N         (N=maxsize)

    队列长度(即数据元素个数):L=(N+rear-front)% N

    1)初始化一个空队列

    Status   InitQueue ( SqQueue  &q ) //初始化空循环队列 q

    {   

    q.base=(QElemType *)malloc(sizeof(QElemType)* QUEUE_MAXSIZE);   //分配空间

    if (!q.base)  exit(OVERFLOW);//内存分配失败,退出程序

       q.front =q.rear=0; //置空队列

        return OK;

     } //InitQueue;

     

    2)入队操作

    Status   EnQueue(SqQueue  &q,  QElemType e)

    {//向循环队列 q 的队尾加入一个元素 e

       if ( (q.rear+1) %  QUEUE_MAXSIZE ==  q.front)

                        return  ERROR ; //队满则上溢,无法再入队

            q.rear = ( q.rear + 1 ) %  QUEUE_MAXSIZE;

            q.base [q.rear] = e;    //新元素e入队

            return  OK;

     }// EnQueue;

     

    3)出队操作

    Status     DeQueue ( SqQueue  &q,    QElemType &e)

     {//若队列不空,删除循环队列q的队头元素,

            //由 e 返回其值,并返回OK

          if ( q.front = = q.rear )   return ERROR;//队列空

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

          e = q.base [ q.front ] ;

         return OK;

        }// DeQueue

    • 链队列空的条件是首尾指针相等,而循环队列满的条件的判定,则有队尾加1等于队头和设标记两种方法。

    补充重点:

    1. 为什么要设计堆栈?它有什么独特用途?

    2. 什么叫“假溢出” ?如何解决?

     调用函数或子程序非它莫属;

     递归运算的有力工具;

     用于保护现场和恢复现场;

     简化了程序设计的问题。                         

    2.为什么要设计队列?它有什么独特用途?

     离散事件的模拟(模拟事件发生的先后顺序,例如 CPU芯片中的指令译码队列);

     操作系统中的作业调度(一个CPU执行多个作业);

     简化程序设计。

    答:在顺序队中,当尾指针已经到了数组的上界,不能再有入队操作,但其实数组中还有空位置,这就叫“假溢出”。解决假溢出的途径———采用循环队列。

    4.在一个循环队列中,若约定队首指针指向队首元素的前一个位置。那么,从循环队列中删除一个元素时,其操作是先 移动队首位置 ,后 取出元素

    5.线性表、栈、队的异同点:

    相同点:逻辑结构相同,都是线性的;都可以用顺序存储或链表存储;栈和队列是两种特殊的线性表,即受限的线性表(只是对插入、删除运算加以限制)。

    不同点:① 运算规则不同:

    线性表为随机存取;

    而栈是只允许在一端进行插入和删除运算,因而是后进先出表LIFO

    队列是只允许在一端进行插入、另一端进行删除运算,因而是先进先出表FIFO

     用途不同,线性表比较通用;堆栈用于函数调用、递归和简化设计等;队列用于离散事件模拟、OS作业调度和简化设计等。

     

    第四章:串

    1.串是数据元素为字符的线性表,串的定义及操作。

    串即字符串,是由零个或多个字符组成的有限序列,是数据元素为单个字符的特殊线性表。

    串比较:int strcmp(char *s1,char *s2);            

    求串长:int strlen(char *s);                          

    串连接:char  strcat(char *to,char *from)   

    子串T定位:char strchr(char *s,char *c);

    2.串的存储结构,因串是数据元素为字符的线性表,所以存在“结点大小”的问题。

    模式匹配算法 

    串有三种机内表示方法:

     

    3.模式匹配算法 :

    算法目的:确定主串中所含子串第一次出现的位置(定位)

    定位问题称为串的模式匹配,典型函数为Index(S,T,pos)

    BF算法的实现—即编写Index(S, T, pos)函数

    BF算法设计思想:

    将主串S的第pos个字符和模式T的第1个字符比较,

    若相等,继续逐个比较后续字符;

    若不等,从主串S的下一字符(pos+1)起,重新与T第一个字符比较。 

    直到主串S的一个连续子串字符序列与模式T相等。返回值为S中与T匹配的子序列第一个字符的序号,即匹配成功。

    否则,匹配失败,返回值 0。

    Int Index_BP(SString S, SString T, int pos)

    { //返回子串T在主串S中第pos个字符之后的位置。若不存在,则函数值为0.

     // 其中,T非空,1≤pos≤StrLength(S)

        i=pos;      j=1;

       while ( i<=S[0] && j<=T[0] ) //如果i,j二指针在正常长度范围,

         {  

           if (S[i] = = T[j] ) {++i, ++j; }   //则继续比较后续字符

           else {i=i-j+2; j=1;} //若不相等,指针后退重新开始匹配

          }

      if(j>T[0]) return i-T[0];  //T子串指针j正常到尾,说明匹配成功,  else return 0;        //否则属于i>S[0]情况,i先到尾就不正常

    } //Index_BP

    补充重点:

    1.空串和空白串有无区别?

    答:有区别。

    空串(Null String)是指长度为零的串;

    而空白串(Blank  String),是指包含一个或多个空白字符‘  ’(空格键)的字符串.

    2.“空串是任意串的子串;任意串S都是S本身的子串,除S本身外,S的其他子串称为S的真子串。”

     

    第五章:数组和广义表

    重点:二维数组的位置计算。

    矩阵的压缩存储:特殊矩阵(三角矩阵,对称矩阵),稀疏矩阵,

     

    第六章:树和二叉树

    1.树:是n(n≥0)个结点的有限集。(1)有且仅有一个特定的称为根(root)的结点;(2)当n>1时,其余的结点分为m(m≥0)个互不相交的有限集合T1,T2,…,Tm。每个集合本身又是棵树,被称作这个根的子树 。

    2.二叉树:是n(n≥0)个结点的有限集合,由一个根结点以及两棵互不相交的、分别称为左子树和右子树的二叉树组成。

    二叉树的性质,存储结构。

    性质1: 在二叉树的第i层上至多有2^(i-1)个结点(i>0)。

    性质2: 深度为k的二叉树至多有2^k-1个结点(k>0)。

    性质3: 对于任何一棵二叉树,如果其终端结点数为n0,度为2的结点数有n2个,则叶子数n0=n2+1

    性质4: 具有n个结点的完全二叉树的深度必为 [log2n]+1

    性质5: 对完全二叉树,若从上至下、从左至右编号,则编号为i 的结点,其左孩子编号必为2i,其右孩子编号为2i+1;其双亲的编号必为i/2(i=1 时为根,除外)。

    二叉树的存储结构:

    1).顺序存储结构

    按二叉树的结点“自上而下、从左至右”编号,用一组连续的存储单元存储。

    若是完全/满二叉树则可以做到唯一复原。

    不是完全二叉树:一律转为完全二叉树!

    方法很简单,将各层空缺处统统补上“虚结点”,其内容为空。

    缺点:①浪费空间;②插入、删除不便 

    2).链式存储结构

    用二叉链表即可方便表示。一般从根结点开始存储。

    lchild

    data

    rchild

    优点:①不浪费空间;②插入、删除方便

    3.二叉树的遍历。

    指按照某种次序访问二叉树的所有结点,并且每个结点仅访问一次,得到一个线性序列。

    遍历规则:二叉树由根、左子树、右子树构成,定义为D、 L、R

    若限定先左后右,则有三种实现方案:

      DLR               LDR                   LRD

    先序遍历           中序遍历          后序遍历

    4.线索二叉树

    1)线索二叉树可以加快查找前驱与后继结点,实质就是将二叉链表中的空指针改为指向前驱或后继的线索,线索化就是在遍历中修改空指针。

    通常规定:对某一结点,若无左子树,将lchild指向前驱结点;若无右子树,将rchild指向后继结点。

    还需要设置左右两个tag,用来标记当前结点是否有子树。

    若ltag==1,lchild指向结点前驱;若rtag==1,rchild指向结点后继。

    2)线索二叉树的存储结构如下:

    typedef struct ThreadNode{

    ElemType data;

    struct ThreadNode *lchild, *rchild;

    int ltag, rtag;

    }ThreadNode, *ThreadTree;

    5.树和森林

    1)树有三种常用存储方式:

    ①双亲表示法     ②孩子表示法    ③孩子—兄弟表示法

    2)森林、树、二叉树的转换

    (1)将树转换为二叉树

    树中每个结点最多只有一个最左边的孩子(长子)和一个右邻的兄弟。按照这种关系很自然地就能将树转换成相应的二叉树:a.在所有兄弟结点之间加一连线

    b.对每个结点,除了保留与其长子的连线外,去掉该结点与其它孩子的连线。

    (2)将一个森林转换为二叉树:

    具体方法是:a.将森林中的每棵树变为二叉树;

    b.因为转换所得的二叉树的根结点的右子树均为空,故可将各二叉树的根结点视为兄弟从左至右连在一起,就形成了一棵二叉树。

    (3)二叉树转换为树

    是树转换为二叉树的逆过程。

    a.加线。若某结点X的左孩子结点存在,则将这个左孩子的右孩子结点、右孩子的右孩子结点、右孩子的右孩子的右孩子结点,都作为结点X的孩子。将结点X与这些右孩子结点用线连接起来。

    b.去线。删除原二叉树中所有结点与其右孩子结点的连线。

     

    (4)二叉树转换为森林:

    假如一棵二叉树的根节点有右孩子,则这棵二叉树能够转换为森林,否则将转换为一棵树。

    a.从根节点开始,若右孩子存在,则把与右孩子结点的连线删除。再查看分离后的二叉树,若其根节点的右孩子存在,则连线删除。直到所有这些根节点与右孩子的连线都删除为止。

    b.将每棵分离后的二叉树转换为树。

    6.树和森林的遍历

    • 树的遍历

    ① 先根遍历:访问根结点;依次先根遍历根结点的每棵子树。

    ② 后根遍历:依次后根遍历根结点的每棵子树;访问根结点。

     

    • 森林的遍历

    ① 先序遍历

    若森林为空,返回;

    访问森林中第一棵树的根结点;

    先根遍历第一棵树的根结点的子树森林;

    先根遍历除去第一棵树之后剩余的树构成的森林。

    ② 中序遍历

    若森林为空,返回;

    中根遍历森林中第一棵树的根结点的子树森林;

    访问第一棵树的根结点;

    中根遍历除去第一棵树之后剩余的树构成的森林。

     

    7.哈夫曼树及其应用

    Huffman树:最优二叉树(带权路径长度最短的树)

    Huffman编码:不等长编码。

    树的带权路径长度:(树中所有叶子结点的带权路径长度之和)

    构造Huffman树的基本思想:权值大的结点用短路径,权值小的结点用长路径。

    构造Huffman树的步骤(即Huffman算法):

    (1) 由给定的 n 个权值{ w1, w2, …, wn }构成n棵二叉树的集合F = { T1, T2, …, Tn } (即森林) ,其中每棵二叉树 Ti 中只有一个带权为 wi 的根结点,其左右子树均空。

    (2) 在F 中选取两棵根结点权值最小的树 做为左右子树构造一棵新的二叉树,且让新二叉树根结点的权值等于其左右子树的根结点权值之和。

    (3) 在F 中删去这两棵树,同时将新得到的二叉树加入 F中。

    (4) 重复(2) 和(3) , 直到 F 只含一棵树为止。这棵树便是Huffman树。

    具体操作步骤:

    应用:用于通信编码

      在通信及数据传输中多采用二进制编码。为了使电文尽可能的缩短,可以对电文中每个字符出现的次数进行统计。设法让出现次数多的字符的二进制码短些,而让那些很少出现的字符的二进制码长一些。假设有一段电文,其中用到 4 个不同字符A,C,S,T,它们在电文中出现的次数分别为 7 , 2 , 4 , 5 。把 7 , 2 , 4 , 5 当做 4 个叶子的权值构造哈夫曼树如图(a) 所示。在树中令所有左分支取编码为 0 ,令所有右分支取编码为1。将从根结点起到某个叶子结点路径上的各左、右分支的编码顺序排列,就得这个叶子结点所代表的字符的二进制编码,如图(b) 所示。这些编码拼成的电文不会混淆,因为每个字符的编码均不是其他编码的前缀,这种编码称做前缀编码。

     

    第七章 图

    1.图的定义,概念、术语及基本操作(https://blog.csdn.net/eyishion/article/details/53234255)

    1)图的定义

    图(Graph)是由顶点的有穷非空集合和顶点之间边的集合组成;

    通常表示为:G(V,E),G表示一个图,V是图G中顶点的集合,E是图G中边的集合;

    注意:在图中数据元素称之为顶点(Vertex),而且顶点集合有穷非空;在图中任意两个顶点之间都可能有关系,顶点之间的逻辑关系用边来表示。

    2)图的分类

    • 按照有无方向,分为无向图有向图

    无向图:如果图中任意两个顶点之间的边都是无向边,则称该图为无向图。

    无向边:若顶点M到顶点N的边没有方向,称这条边为无向边,用无序偶对(M,N)或(N,M)表示。

    无向图是有顶点构成。如下图所示就是一个无向图G1:

    无向图G1= (V1,{E1}),其中顶点集合 V1={A,B,C,D};边集合E1={(A,B),(B,C),(C,D),(D,A)}

    有向图:如果图中任意两个顶点之间的边都是有向边,则称该图为有向图。

    有向边:若顶点M到顶点N的边有方向,称这条边为有向边,也称为弧,用偶序对 < M, N >表示;M表示弧尾,N表示弧头

    有向图是有顶点构成,如下图所示是一个有向图G2:

    有向图G2=(V2,{E2}),其中顶点集合 V2={A,B,C,D};弧集合E2={< A,D>,< B,A>,< C,A>,< B,C>}

    对于弧< A,D>来说, A是弧尾,D是弧头

    注意:无向边用 小括号 “()”表示,有向边用“<>”表示。

    无向完全图:在无向图中,如果任意两个顶点之间都存在边,则称该图为无向完全图。

    含有n个顶点的无向完全图有n * (n-1)/2条边。下面是一个无向完全图

    4个顶点,6条无向边,每个顶点对应3条边 ,一共4个顶点 总共 4*3,每个顶点对应的边都重复计算了一次,所以整体要除以2。

    对于n各 顶点和e条边的无向图满足:0<=e <= n(n-1)/2

    有向完全图:在有向图中,如果任意两个顶点之间都存在方向互为相反的两条弧,则称该图为有向完全图。

    含有n个顶点的无向完全图有n * (n-1)条边。下面是一个有向完全图

    4个顶点,12条弧,一共4个顶点 总共 4*3。

    2,按照弧或边的多少,分为稀疏图稠密图

    若边或弧的个数e<=NlogN(N是顶点的个数),称为系数图,否则称为稠密图;

    3,按照边或弧是否带权,其中带权的图统称为

    有些图的边或弧具有与它相关的数字,这种与图的边或弧相关的数叫做权。

    有向网中弧带权的图叫做有向网;

    无向网中边带权的图叫做无向网;

    比如下图就是一个无向图

     

    图的顶点和边间关系

    邻接点 度 入度 出度

    对于无向图,假若顶点v和顶点w之间存在一条边,则称顶点v和顶点w互为邻接点,边(v,w)和顶点v和w相关联。

    顶点v的是和v相关联的边的数目,记为TD(v);

    上面这个无向图G1,A和B互为邻接点,A和D互为邻接点,B和C互为邻接点,C和D互为邻接点;

    A的度是2,B的度是2,C的度是2,D的度是2;所有顶点度的和为8,而边的数目是4;

    图中边的数目e = 各个顶点度数和的一半。

    对于有向图来说,与某个顶点相关联的弧的数目称为度(TD);以某个顶点v为弧尾的弧的数目定义为顶点v的出度(OD);以顶点v为弧头的弧的数目定义为顶点的入度(ID)

    度(TD) = 出度(OD) + 入度(ID);

    比如上面有向图,

    A的度为3 ,A的入度 2,A的出度是1

    B的度为2 ,B的入度 0,B的出度是2

    C的度为2 ,C的入度 1,C的出度是1

    D的度为1 ,D的入度 1,D的出度是0

    所有顶点的入度和是4,出度和也是4,而这个图有4个弧

    所以 有向图的弧 e = 所有顶点入度的和 = 所有顶点出度的和

    路径 路径长度 简单路径 回路 (环) 简单回路(简单环)

    设图G=(V,{E})中的一个顶点序列{u=Fi0,Fi1,Fi2,….Fim=w}中,(Fi,j-1,Fi,j)∈E 1 ≤j ≤m,则称从顶点u到顶点w之间存在一条路径,路径上边或弧的数目称作路径长度

    若路径中的顶点不重复出现的路径称为简单路径

    若路径中第一个顶点到最后一个顶点相同的路径称为回路或环

    若路径中第一个顶点和最后一个顶点之外,其余顶点不重复出现的回路,称为简单回路或简单环

    比如下图 :

    从B 到 D 中顶点没有重复出现 ,所以是简单路径 ,边的数目是2,所以路径长度为 2。

    图1和图2都是一个回路(环),图1中出了第一个顶点和最后一个顶点相同之外,其余顶点不相同,所以是简单环(简单回路),图2,有与顶点C重复就不是一个简单环了;

    连通图相关术语

    连通图

    在无向图G(V,{E})中,如果从顶点V到顶点W有路径,则称V和W是连通的。如果对于图中任意两个顶点Vi、Vj∈V,Vi和Vj都是连通的,则称G是连通图。

    如下图所示:

    图1,顶点A到顶点E就无法连通,所以图1不是连通;图2,图3,图4属于连通图;

    连通分量

    若无向图为非连通图,则图中各个极大连通子图称作此图的连通分量;

    图1是无向非连通图,由两个连通分量,分别是图2和图3。图4尽管也是图1的子图,但是它不满足极大连通,也就说极大连通应当是包含ABCD四个顶点,比如图2那样;

    强连通图

    在有向图G(V,{E})中,如果对于每一对Vi ,Vj∈V,Vi≠Vj,从Vi到Vj和从Vj到Vi都存在有向路径,则称G是强连通图。

    图1不是强连通图因为D到A不存在路径,图2属于强连通图。

    强连通分量

    若有向图不是强连通图,则图中各个极大强连通子图称作此图的强连通分量;

    图1不是强连通图,但是图2是图1的强连通子图,也就是强连通分量;

    生成树和生成森林

    生成树

    假设一个连通图有n个顶点和e条边,其中n-1条边和n个顶点构成一个极小连通子图,称该极小连通子图为此连通图的生成树;

    图1是一个连通图含有4个顶点和4条边,图2,图3,图4含有3条边和4个顶点,构成了一个极小连通图子图,也称为生成树,为什么是极小连通子图,因为图2,图3,图4中少一条边都构不成一个连通图,多一条边就变成一个回路(环),所以是3条边和4个顶点构成的极小连通子图。图5尽管也是3个边4个顶点,但不是连通图。

    生成森林

    如果一个有向图恰有一个顶点的入度为0,其余顶点的入度为1,则是一颗有向树

    入度为0,相当于根节点,入度为1,相当于分支节点;,比如下面的有向图就是一个有向树

    顶点B的入度是0,其余顶点的入度是1;

    一个有向图的生成森林由若干颗有向树组成,含有图中全部顶点,但有足以构成若干颗不相交的有向树的弧;

    有向图1去掉一些弧后分解成2颗有向树,图2和图3,这两颗树就是有向图图1的生成森林;

    2.图的存储结构

    1).邻接矩阵(数组)表示法

    ① 建立一个顶点表和一个邻接矩阵

    ② 设图 A = (V, E) 有 n 个顶点,则图的邻接矩阵是一个二维数组 A.Edge[n][n]。

    注:在有向图的邻接矩阵中,

       第i行含义:以结点vi为尾的弧(即出度边);

       第i列含义:以结点vi为头的弧(即入度边)。

    邻接矩阵法优点:容易实现图的操作,如:求某顶点的度、判断顶点之间是否有边(弧)、找顶点的邻接点等等。

    邻接矩阵法缺点:n个顶点需要n*n个单元存储边(弧);空间效率为O(n^2)。

    2).邻接表(链式)表示法

    ① 对每个顶点vi 建立一个单链表,把与vi有关联的边的信息(即度或出度边)链接起来,表中每个结点都设为3个域:

    ② 每个单链表还应当附设一个头结点(设为2个域),存vi信息;

    ③ 每个单链表的头结点另外用顺序存储结构存储。

    邻接表的优点:空间效率高;容易寻找顶点的邻接点;

    邻接表的缺点:判断两顶点间是否有边或弧,需搜索两结点对应的单链表,没有邻接矩阵方便。

    3.图的遍历

    遍历定义:从已给的连通图中某一顶点出发,沿着一些边,访遍图中所有的顶点,且使每个顶点仅被访问一次,就叫做图的遍历,它是图的基本运算。

    图的遍历算法求解图的连通性问题、拓扑排序和求关键路径等算法的基础。

    图常用的遍历:一、深度优先搜索;二、广度优先搜索 

    深度优先搜索(遍历)步骤:(如下图)

    ① 访问起始点 v;

    ② 若v的第1个邻接点没访问过,深度遍历此邻接点;

    ③ 若当前邻接点已访问过,再找v的第2个邻接点重新遍历。

    基本思想:——仿树的先序遍历过程。

    遍历结果:v1->v2->v4->v8->v5-v3->v6->v7

    广度优先搜索(遍历)步骤:

    ① 在访问了起始点v之后,依次访问 v的邻接点;

    ② 然后再依次(顺序)访问这些点(下一层)中未被访问过的邻接点;

    ③ 直到所有顶点都被访问过为止。

    遍历结果:v1->v2->v3->v4->v5-v6->v7->v8

    4.图的连通性问题

    1)对无向图进行遍历时,对于连通图,仅需从图中任一顶点出发,进行深度优先搜索或广度优先搜索,便可访问到图中所有顶点。

    2)最小生成树:在连通网的所有生成树中,所有边的代价和最小的生成树。

    构造最小生成树有很多算法,但是他们都是利用了最小生成树的同一种性质:MST性质(假设N=(V,{E})是一个连通网,U是顶点集V的一个非空子集,如果(u,v)是一条具有最小权值的边,其中u属于U,v属于V-U,则必定存在一颗包含边(u,v)的最小生成树),下面就介绍两种使用MST性质生成最小生成树的算法:普里姆算法和克鲁斯卡尔算法。

    Kruskal算法特点:将边归并,适于求稀疏网的最小生成树。

    Prime算法特点: 将顶点归并,与边数无关,适于稠密网。

    Prime算法构造最小生成树过程如下图:

    Kruskal算法构造最小生成树过程如下图:

    5.有向无环图及其应用

    有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序,是将G中所有顶点排成一个线性序列,使得图中任意一对顶点u和v,若边(u,v)∈E(G),则u在线性序列中出现在v之前。

    1)拓扑排序

    拓扑排序对应施工的流程图具有特别重要的作用,它可以决定哪些子工程必须要先执行,哪些子工程要在某些工程执行后才可以执行。

    我们把顶点表示活动、边表示活动间先后关系的有向图称做顶点活动网(Activity On Vertex network),简称AOV网。

    一个AOV网应该是一个有向无环图,即不应该带有回路,因为若带有回路,则回路上的所有活动都无法进行(对于数据流来说就是死循环)。在AOV网中,若不存在回路,则所有活动可排列成一个线性序列,使得每个活动的所有前驱活动都排在该活动的前面,我们把此序列叫做拓扑序列(Topological order),由AOV网构造拓扑序列的过程叫做拓扑排序(Topological sort)。AOV网的拓扑序列不是唯一的,满足上述定义的任一线性序列都称作它的拓扑序列。

    拓扑排序的实现:

    a.在有向图中选一个没有前驱的顶点并且输出

    b.从图中删除该顶点和所有以它为尾的弧(白话就是:删除所有和它有关的边)

    c.重复上述两步,直至所有顶点输出,或者当前图中不存在无前驱的顶点为止,后者代表我们的有向图是有环的,因此,也可以通过拓扑排序来判断一个图是否有环。

    2)关键路径

    AOE-网是一个带权的有向无环图,其中,顶点表示事件,弧表示活动,权表示活动持续的时间。通常,AOE-网可用来估算工程的完成时间。

    关键路径:在AOE网中,从始点到终点具有最大路径长度(该路径上的各个活动所持续的时间之和)的路径称为关键路径。

    关键活动:关键路径上的活动称为关键活动。关键活动:e[i]=l[i]的活动

    由于AOE网中的某些活动能够同时进行,故完成整个工程所必须花费的时间应该为始点到终点的最大路径长度。关键路径长度是整个工程所需的最短工期。

    与关键活动有关的量

    (1)事件的最早发生时间ve[k]:ve[k]是指从始点开始到顶点vk的最大路径长度。这个长度决定了所有从顶点vk发出的活动能够开工的最早时间。 

    (2)事件的最迟发生时间vl[k]:vl[k]是指在不推迟整个工期的前提下,事件vk允许的最晚发生时间。

    (3)活动的最早开始时间e[i]:若活动ai是由弧<vk vj>表示,则活动ai的最早开始时间应等于事件vk的最早发生时间。因此,有:e[i]=ve[k]

    (4)活动的最晚开始时间l[i]:活动ai的最晚开始时间是指,在不推迟整个工期的前提下, ai必须开始的最晚时间。若ai由弧<vkvj>表示,则ai的最晚开始时间要保证事件vj的最迟发生时间不拖后。因此,有:l[i]=vl[j]-len<vk,vj

    示例如下:

    6.最短路径

    从某顶点出发,沿图的边到达另一顶点所经过的路径中,各边上权值之和最小的一条路径叫做最短路径。

    1)迪杰斯塔拉算法--单源最短路径

     

    所有顶点间的最短路径—用Floyd(弗洛伊德)算法

    第八章:查找

    查找表是称为集合的数据结构。是元素间约束力最差的数据结构:元素间的关系是元素仅共在同一个集合中。(同一类型的数据元素构成的集合)

    1.静态查找表

      1)顺序查找(线性查找)

      技巧:把待查关键字key存入表头或表尾(俗称“哨兵”),这样可以加快执行速度。

    int Search_Seq( SSTable  ST , KeyType  key ){

    ST.elem[0].key =key;

    for( i=ST.length; ST.elem[ i ].key!=key;  - - i  );

          return i;

    } // Search_Seq

    //ASL=(1+n)/2,时间效率为 O(n),这是查找成功的情况:

    顺序查找的特点:

    优点:算法简单,且对顺序结构或链表结构均适用。

           缺点: ASL 太大,时间效率太低。

      2)折半查找(二分查找)——只适用于有序表,且限于顺序存储结构。

      若关键字不在表中,怎样得知并及时停止查找?

      典型标志是:当查找范围的上界≤下界时停止查找。

      ASL的含义是“平均每个数据的查找时间”,而前式是n个数据查找时间的总和,所以:

     

    3)分块查找(索引顺序查找)

    思路:先让数据分块有序,即分成若干子表,要求每个子表中的数据元素值都比后一块中的数值小(但子表内部未必有序)。然后将各子表中的最大关键字构成一个索引表,表中还要包含每个子表的起始地址(即头指针)。

    特点:块间有序,块内无序。

    查找:块间折半,块内线性

    查找步骤分两步进行:

    ① 对索引表使用折半查找法(因为索引表是有序表);

    ② 确定了待查关键字所在的子表后,在子表内采用顺序查找法(因为各子表内部是无序表);

    查找效率ASL分析:

    2.动态查找表

    1)二叉排序树和平衡二叉树

    • 二叉排序树的定义----或是一棵空树;或者是具有如下性质的非空二叉树:

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

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

     (3)它的左右子树也分别为二叉排序树。

    二叉排序树又称二叉查找树。

    二叉排序树的查找过程:

    BiTree SearchBST(BiTree T, KeyType key)

    {

            //在根指针T所指二叉排序树中递归地查找某关键字等于key的数据元素,

            //若查找成功,则返回指向该数据元素结点的指针,否则返回空指针

            if ((!T)||EQ(key, T->data.key))  return(T); //查找结束

            else if LT(key, T->data.key) return (SearchBST(T->lchild, key)); //在左子树中继续查找

            else return (SearchBST(T->rchild,key)); //在右子树中继续查找

    }

    • 二叉排序树的插入

            思路:查找不成功,生成一个新结点s,插入到二叉排序树中;查找成功则返回。

       SearchBST (K,  &t) { //K为待查关键字,t为根结点指针

       p=t;       //p为查找过程中进行扫描的指针

       while(p!=NULL)

    {

       case {

                   K= p->data:  {查找成功,return true;}

                   K< p->data :  {q=p;p=p->lchild }  //继续向左搜索

                   K> p->data :  {q=p;p=p->rchild } //继续向右搜索

                }

      }  //查找不成功则插入到二叉排序树中

    s =(BiTree)malloc(sizeof(BiTNode)); 

    s->data=K; s ->lchild=NULL; s ->rchild=NULL;

          //查找不成功,生成一个新结点s,插入到二叉排序树叶子处

    case {

                t=NULL:   t=s;   //若t为空,则插入的结点s作为根结点

                K < q->data: q->lchild=s;  //若K比叶子小,挂左边

                K > q->data: q->rchild=s; //若K比叶子大,挂右边

            }

    return OK;

    }

    • 二叉排序树的删除

    假设:*p表示被删结点的指针; PL和PR 分别表示*P的左、右孩子指针;

    *f表示*p的双亲结点指针;并假定*p是*f的左孩子;则可能有三种情况:

    *p有两颗子树,有两种解决方法:

    法1:令*p的左子树为 *f的左子树,*p的右子树接为*s的右子树;如下图(c)所示  //即 fL=PL  ;   SR=PR   ;

    法2:直接令*p的直接前驱(或直接后继)替代*p,然后再从二叉排序树中删去它的直接前驱(或直接后继) 。如图(d),当以直接前驱*s替代*p时,由于*s只有左子树SL,则在删去*s之后,只要令SL为*s的双亲*q的右子树即可。 // *s为*p左子树最右下方的结点

    删除算法如下:

    Status Delete(BiTree &p)

    {

        //从二叉排序树种删除结点p,并重接它的左或右子树

        if(!p->rchild) //右子树空,只需重接它的左子树

        {

            q=p;

            p=p->lchild;

            free(q);

        }

        else if(!p->lchild) //左子树空,只需重接它的右子树

        {

            q=p;

            p=p->rchild;

            free(q);

        }

        else //左右子树都不空

        {

            q=p; 

            s=p->lchild;

            while(s->rchild)  //转左,然后向右到尽头(找p的直接前驱) 图(b)

            {

                q=s;

                s=s->rchild;

            }

            p->data = s->data; //s指向被删结点的“前驱”

            if(q!=p)  //重接*q的右子树

            {

                q->rchild=s->lchild;

            }

            else  //q=p,说明s->rchild为空(即:p->lchild->rchild为空),重接*q的左子树

            {

                q->lchild=s->lchild;

            }

             delete s;

        }//end else 左右子树都不空

        return TRUE;

    }

    二叉排序树查找分析:和折半查找类似,与给定值比较的关键字个数不超过树的深度。然而,折半查找长度为n的表的判定树是惟一的,而含有n个结点的二叉排序树却不惟一。

    含有n个结点的二叉排序树的平均查找长度和树的形态有关。当先后插入的关键字有序时,构成的二叉排序树蜕变为单支树。树的深度为n,其平均查找长度为(n+1)/2(和顺序查找相同),这是最差的情况。最好的情况是二叉排序树的形态和折半查找的判定树相同,其平均查找长度和log2n成正比。

    (n>=2)

     

    • 平衡二叉树

    又称AVL树,即它或者是一颗空树,或者具有如下性质:它的左子树和右子树都是平衡二叉树,且左子树与右子树的深度之差的绝对值不超过1。

    平衡因子:该结点的左子树的深度减去它的右子树的深度。

    平衡二叉树的特点:任一结点的平衡因子只能取:-1、0 或 1。

    如果在一棵AVL树中插入一个新结点,就有可能造成失衡,此时必须重新调整树的结构,使之恢复平衡。我们称调整平衡过程为平衡旋转

    平衡旋转可以归纳为四类:单向右顺时针旋转(LL);单向左逆时针旋转(RR);双向旋转先左逆时针后右顺时针(LR);双向旋转先右顺时针后左逆时针(RL)

    平衡二叉树查找分析:

    时间复杂度为O(logn)

    3.B-树和B+树

    B+树是应文件系统所需而出的一种B树的变型树。一棵m阶的B+树和m阶的B-树的差异在于:

    1.有n棵子树的结点中含有n个关键字,每个关键字不保存数据,只用来索引,所有数据都保存在叶子节点。

    2.所有的叶子结点中包含了全部关键字的信息,及指向含这些关键字记录的指针,且叶子结点本身依关键字的大小自小而大顺序链接。

    3.所有的非终端结点可以看成是索引部分,结点中仅含其子树(根结点)中的最大(或最小)关键字。

    通常在B+树上有两个头指针,一个指向根结点,一个指向关键字最小的叶子结点。

    B-树:一棵m阶的B-树或者是一棵空树,或者是满足下列要求的m叉树:

    • 树中的每个结点至多有m棵子树;

    • 若根结点不是叶子结点,则至少有两棵子树;

    • 除根结点外,所有非终端结点至少有[ m/2 ] ( 向上取整 )棵子树。

    • 所有的非终端结点中包括如下信息的数据(n,A0,K1,A1,K2,A2,….,Kn,An)

    其中:Ki(i=1,2,…,n)为关键码,且Ki < K(i+1),

    Ai 为指向子树根结点的指针(i=0,1,…,n),且指针A(i-1) 所指子树中所有结点的关键码均小于Ki (i=1,2,…,n),An 所指子树中所有结点的关键码均大于Kn。n 为关键码的个数。

    • 所有的叶子结点都出现在同一层次上,并且不带信息(可以看作是外部结点或查找失败的结点,实际上这些结点不存在,指向这些结点的指针为空)。

     

    4.哈希表

    哈希表(Hash table,也叫散列表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组叫做散列表

     

    1)哈希函数构造方法

    • 直接定址法

    取关键字或关键字的某个线性函数值为散列地址。

    即 H(key) = key 或 H(key) = a*key + b,其中a和b为常数。

    • 除留余数法

    取关键字被某个不大于散列表长度 m 的数 p 求余,得到的作为散列地址。

    即 H(key) = key % p, p < m。

    • 数字分析法

    当关键字的位数大于地址的位数,对关键字的各位分布进行分析,选出分布均匀的任意几位作为散列地址。

    仅适用于所有关键字都已知的情况下,根据实际应用确定要选取的部分,尽量避免发生冲突。

    • 平方取中法

    先计算出关键字值的平方,然后取平方值中间几位作为散列地址。

    随机分布的关键字,得到的散列地址也是随机分布的。

    • 折叠法(叠加法)

    将关键字分为位数相同的几部分,然后取这几部分的叠加和(舍去进位)作为散列地址。

    用于关键字位数较多,并且关键字中每一位上数字分布大致均匀。

    • 随机数法

    选择一个随机函数,把关键字的随机函数值作为它的哈希值。

    通常当关键字的长度不等时用这种方法。

    构造哈希函数的方法很多,实际工作中要根据不同的情况选择合适的方法,总的原则是尽可能少的产生冲突

    通常考虑的因素有关键字的长度分布情况哈希值的范围等。

    如:当关键字是整数类型时就可以用除留余数法;如果关键字是小数类型,选择随机数法会比较好。

     

    2)哈希冲突的解决方法

     

    • 开放定址法

    Hi=(H(key) + di) MOD m i=1,2,…,k (k<=m)

    当冲突发生时,使用某种探测技术在散列表中形成一个探测序列。沿此序列逐个单元地查找,直到找到给定的关键字,或者碰到一个开放的地址(即该地址单元为空)为止(若要插入,在探查到开放的地址,则可将待插入的新结点存人该地址单元)。查找时探测到开放的地址则表明表中无待查的关键字,即查找失败。

    当冲突发生时,使用某种探查(亦称探测)技术在散列表中寻找下一个空的散列地址,只要散列表足够大,空的散列地址总能找到

    按照形成探查序列的方法不同,可将开放定址法区分为线性探查法、二次探查法、双重散列法等。

    a.线性探查法

    hi=(h(key)+i) % m ,0 ≤ i ≤ m-1

    基本思想是:探查时从地址 d 开始,首先探查 T[d],然后依次探查 T[d+1],…,直到 T[m-1],此后又循环到 T[0],T[1],…,直到探查到 有空余地址 或者到 T[d-1]为止。

    b.二次探查法

    hi=(h(key)+i*i) % m,0 ≤ i ≤ m-1

    基本思想是:探查时从地址 d 开始,首先探查 T[d],然后依次探查 T[d+1^2],T[d+2^2],T[d+3^2],…,等,直到探查到 有空余地址 或者到 T[d-1]为止。缺点是无法探查到整个散列空间。

    c.双重散列法

    hi=(h(key)+i*h1(key)) % m,0 ≤ i ≤ m-1

    基本思想是:探查时从地址 d 开始,首先探查 T[d],然后依次探查 T[d+h1(d)], T[d + 2*h1(d)],…,等。

    该方法使用了两个散列函数 h(key) 和 h1(key),故也称为双散列函数探查法。

    定义 h1(key) 的方法较多,但无论采用什么方法定义,都必须使 h1(key) 的值和 m 互素,才能使发生冲突的同义词地址均匀地分布在整个表中,否则可能造成同义词地址的循环计算。

    该方法是开放定址法中最好的方法之一。

    • 链接法(拉链法)

    将所有关键字为同义词的结点链接在同一个单链表中。若选定的散列表长度为 m,则可将散列表定义为一个由 m 个头指针组成的指针数组 T[0..m-1] 。

    凡是散列地址为 i 的结点,均插入到以 T[i] 为头指针的单链表中。

    T 中各分量的初值均应为空指针。

    在拉链法中,装填因子 α 可以大于 1,但一般均取 α ≤ 1。

    3.哈希表的查找及其分析

    哈希表是实现关联数组(associative array)的一种数据结构,广泛应用于实现数据的快速查找。

    查找过程中,关键字的比较次数,取决于产生冲突的多少,产生的冲突少,查找效率就高,产生的冲突多,查找效率就低。因此,影响产生冲突多少的因素,也就是影响查找效率的因素。

    影响产生冲突多少有以下三个因素:

    1)哈希函数是否均匀;

    2)处理冲突的方法;

    3)哈希表的加载因子。

     

    第九章:内部排序

    排序:将一个数据元素(或记录)的任意序列,重新排列成一个按关键字有序的序列。

    稳定性——若两个记录A和B的关键字值相等,且排序后A、B的先后次序保持不变,则称这种排序算法是稳定的。

    1.插入排序

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

    简言之,边插入边排序,保证子序列中随时都是排好序的。

    1)  直接插入排序

        在已形成的有序表中线性查找,并在适当位置插入,把原来位置上的元素向后顺移。

    时间效率: 因为在最坏情况下,所有元素的比较次数总和为(0+1+…+n-1)→O(n^2)。

    其他情况下也要考虑移动元素的次数。 故时间复杂度为O(n^2)

    空间效率:仅占用1个缓冲单元——O(1)

    算法的稳定性:稳定

    直接插入排序算法的实现:

    void InsertSort ( SqList &L ) 

    { //对顺序表L作直接插入排序

     for ( i = 2;  i <=L.length; i++) //假定第一个记录有序

    {

         L.r[0]= L.r[i];

           j=i-1 ;                      //先将待插入的元素放入“哨兵”位置

         while(L[0] .key<L[j].key)

        {  

            L.r[j+1]= L.r[j];

            j--  ;                    

        }      //只要子表元素比哨兵大就不断后移

        L.r[j+1]= L.r[0];      //直到子表元素小于哨兵,将哨兵值送入

                                     //当前要插入的位置(包括插入到表首)

    }

    }

    2)折半插入排序

    子表有序且为顺序存储结构,则插入时采用折半查找定可加速。

    优点:比较次数大大减少,全部元素比较次数仅为O(nlog2n)。

    时间效率:虽然比较次数大大减少,可惜移动次数并未减少, 所以排序效率仍为O(n^2) 。

    空间效率:仍为 O(1)

    稳 定  性: 稳定

     

    3)希尔排序—不稳定

    基本思想:先将整个待排记录序列分割成若干子序列,分别进行直接插入排序,待整个序列中的记录“基本有序”时,再对全体记录进行一次直接插入排序。

    优点:让关键字值小的元素能很快前移,且序列若基本有序时,再用直接插入排序处理,时间效率会高很多。

    时间效率:当n在某个特定范围内,希尔排序所需的比较和移动次数约为n^1.3,当n->无穷,可减少到n(log2n)^2

    空间效率:O(1)

    4)快速排序

    基本思想:从待排序列中任取一个元素 (例如取第一个) 作为中心,所有比它小的元素一律前放,所有比它大的元素一律后放,形成左右两个子表;然后再对各子表重新选择中心元素并依此规则调整,直到每个子表的元素只剩一个。此时便为有序序列了。

    优点:因为每趟可以确定不止一个元素的位置,而且呈指数增加,所以特别快!

    前提:顺序存储结构

    时间效率:O(nlog2n) —因为每趟确定的元素呈指数增加

    空间效率:O(log2n)—因为递归要用栈(存每层low,high和pivot)

    稳 定 性: 不 稳 定 — —因为有跳跃式交换。

    算法:

    int partition(SqList &L,int low,int high)

    {

      L.r[0] = L.r[low];

      pivot key = L.r[low].key;

        while(low < high)

        {

         while(low<high&&L.r[high]>=pivot) high--;

         L.r[low] = L.r[high];

         while(low<high&&L.r[low]<=pivot) low++;

         L.r[high] = L.r[low];

        }

        L.r[low] = pivot;

        return low;

    }

     

    5)冒泡排序

    基本思路:每趟不断将记录两两比较,并按“前小后大”(或“前大后小”)规则交换。

    优点:每趟结束时,不仅能挤出一个最大值到最后面位置,还能同时部分理顺其他元素;一旦下趟没有交换发生,还可以提前结束排序。

    前提:顺序存储结构

    冒泡排序的算法分析:

    时间效率:O(n^2) —因为要考虑最坏情况

    空间效率:O(1) —只在交换时用到一个缓冲单元

    稳 定 性: 稳定  —25和25*在排序前后的次序未改变

    冒泡排序的优点:每一趟整理元素时,不仅可以完全确定一个元素的位置(挤出一个泡到表尾),还可以对前面的元素作一些整理,所以比一般的排序要快。

    选择排序:选择排序的基本思想是:每一趟在后面n-i 个待排记录中选取关键字最小的记录作为有序序列中的第i  个记录。

    6)简单选择排序

    思路异常简单:每经过一趟比较就找出一个最小值,与待排序列最前面的位置互换即可。

    ——首先,在n个记录中选择最小者放到r[1]位置;然后,从剩余的n-1个记录中选择最小者放到r[2]位置;…如此进行下去,直到全部有序为止。

    优点:实现简单

    缺点:每趟只能确定一个元素,表长为n时需要n-1趟

    前提:顺序存储结构

    时间效率:O(n^2)——虽移动次数较少,但比较次数较多

    空间效率:O(1)

    算法稳定性——不稳定

    Void SelectSort(SqList  &L ) 

    {

    for (i=1;  i<L.length; ++i)

    {

         j = SelectMinKey(L,i);  //在L.r[i..L.length]中选择key最小的记录

         if( i!=j )   r[i] <--> r[j]; //与第i个记录交换

          } //for

      }  //SelectSort

     

    7)堆排序

    设有n个元素的序列 k1,k2,…,kn,当且仅当满足下述关系之一时,称之为堆。

    如果让满足以上条件的元素序列 (k1,k2,…,kn)顺次排成一棵完全二叉树,则此树的特点是:树中所有结点的值均大于(或小于)其左右孩子,此树的根结点(即堆顶)必最大(或最小)。

    堆排序算法分析:

    时间效率:O(nlog2n)。因为整个排序过程中需要调用n-1次HeapAdjust( )算法,而算法本身耗时为log2n;

    空间效率:O(1)。仅在第二个for循环中交换记录时用到一个临时变量temp。

    稳定性: 不稳定。

    优点:对小文件效果不明显,但对大文件有效。

     

    8)归并排序----稳定

    将两个或两个以上有序表组合成一个新的有序表。

    时间复杂度:O(nlogn)

    空间复杂度:和待排记录等数量的辅助空间。

     

    9)基数排序

    时间复杂度:对于n各记录(每个记录含d个关键字,每个关键字取值范围为rd个值)进行链式基数排序的时间复杂度为O(d(n+rd)),其中每一趟分配的时间复杂度为O(n),每一趟收集的时间复杂度为O(rd)

    10)各种内部排序方法的比较讨论

    (1) 从平均时间性能看,快速排序最佳,其所需时间最省,但快速排序的最坏情况下的时间性能不如堆排序和快速排序。后两者相比较,在n较大时,归并排序所需时间较堆排序省,但它所需的辅助存储量最多。

    (2)基数排序的时间复杂度可写成O(dn)。因此,它最适用于n值很大而关键字较小的序列。

    (3)从方法的稳定性来比较,基数排序是稳定的内排方法,所需时间复杂度为O(n^2)的简单排序方法也是稳定的,然而,快速排序、堆排序和希尔排序等时间性能较好的排序方法是不稳定的。

    展开全文
  • 八问数据中台:关于数据中知道的都在这里! 原创: 筱愚她爸 凯哥讲故事系列 1周前 数据中台最近特别火,各个企业都在关注如何构建自己的数据中台,利用数据中台打造数据驱动的经营能力。数据中台的概念漫天...

    八问数据中台:关于数据中台你想知道的都在这里!
    原创: 筱愚她爸 凯哥讲故事系列 1周前

    数据中台最近特别火,各个企业都在关注如何构建自己的数据中台,利用数据中台打造数据驱动的经营能力。数据中台的概念漫天飞,作为最早为企业提供数据中台构建服务的实践者,我们希望将一些落地的经验和教训给到那些正在考虑建设数据中台的企业。

    1.数据中台是什么

    数据中台需求的出现,是企业数字化转型的一个标志性的转折,数据中台成为热点,标志着,“在企业信息化或者数字化的历史上,数据从来没有距离业务这么近,数字化转型正从流程优先走向数据优先”。要想从根本上理解数据中台是什么,要认识到数据和软件的关系。

    信息化和数字化的本质区别是:

    “信息化是用软件工程技术局部支撑和改良业务,数字化是用数字化技术重塑和转型业务本身”,而数据则是构成数字化业务世界的原子材料。

    数据从应用诞生的那一天开始就存在,但是,数据并不是第一天就被存储和利用的,应用和数据的发展是不同步的,数据的地位是不断演进,越来越重要的,经历了以下五个阶段:
    在这里插入图片描述
    阶段1:数据没有被存储

    早期的应用,是为了解决某一个单点的问题,比如计算器,计算过程的数据是不被存储的,但是计算的过程中,数据是客观存在的。这个阶段,数据是应用的过程产物,产生即丢弃,并不被存储。

    阶段2:只有少量结果数据被存储和查询

    当应用的功能丰富后,软件从解决单点问题的工具演进到处理一类业务问题,从而有了多个功能模块。典型的例子是办公自动化系统、进销存系统,这个时候少量的结果数据被存储起来,并且也有了对数据的查询、统计的需求。这个时候,数据是关键业务的记录。

    阶段3:数据仓库出现,数据被大量存储

    接着,企业级管理系统比如ERP、MES、CRM的出现,企业管理层需要跨条线,跨职能了解和掌握整体的经营情况,从而根据这些数据来帮助企业做决策。这个时候商务智能,传统数据仓库系统应运而生的出现了,数据在企业管理中的作用开始显现。但是这个时候的数据距离业务很远,为业务提供支持的速度很慢,往往是先有了业务想法和需求,先有“领导要看什么”,然后在去采集和处理对应的数据做出什么报表给到领导

    阶段4:数据的深入价值开始被挖掘

    传统数据仓库还是基于流程的,原因是数据仓库的需求还是来自于预先的设计,来自于固有流程数据的整合。而这个时候,企业的业务已经有了一定的复杂度,企业管理人员希望从数据当中发现一些隐藏的未知的价值和规律。而这个时候预定义的查询条件,预定义的业务主题已经不能满足这样的需求,所以在数据仓库基础上,产生了数据挖掘的技术,业务从数据中发现市场的规律,洞察客户的兴趣,产生一些人们不知道的信息。这个阶段在市场营销、生产调度等影响因子较多,动态性较大的业务领域,数据的重要性愈加凸显。

    以上四个阶段,基本上都处于“业务数据化”的阶段

    阶段5:业务数据化,数据成为企业核心资产

    到了数字化时代,所有的一切都被数字化的技术所重构,而数据是构成数字化世界的基础。数据如同石油一样,成为新时代的资源,从数据当中挖掘价值,从数据当中去产生创新已经成为了所有企业的共识。这个时候,数据成为了企业的核心资产,所有的业务都被数据化。

    总结一下,我们会发现在信息化时代,数据是流程的副产品,流程是预先设计好的,然后在设计好的流程中产生了数据;

    在数字化时代,业务流程应用软件(业务流程的显形载体)会随着市场的变化快速而不断动态迭代甚至消亡,而数据成为了物理世界映射到数字化世界的原子,数据思维(”Data First” )成为战略核心之一。

    “数据是构建物理世界对等的数字化世界的原子”,数据中蕴含着业务的本质,蕴含着创新的源泉,谁能掌握数据的能力谁就能在数字化竞争中拔得头筹。

    最近两年,数据在数字化转型的重要性被提上了前所未有的高度,数据驱动的决策,调度,运营给企业插上了智能的大脑,带来了巨大的业务价值。

    UPS的首席信息官Juan Perez在2017年启动了网络规划工具的试点,利用算法和数据来优化路由,2018年这个项目为UPS节约了三千九百万加仑的能源消耗,缩短了3.64亿公里的路程。现在利用算法,机器学习,深度学习的技术来加工数据,通过数据来驱动企业的运营已经成为了UPS的核心竞争力。

    [https://erpinnews.com/big-data-case-study-ups-using-analytics-improve-performance

    https://bigdata-madesimple.com/10-big-data-case-studies-big-results-2018/

    ]

    招商银行将“数据化”作为金融科技战略的核心举措,通过数据驱动来全方位进行渠道优化和服务升级革命,打造了一批数据和智能驱动的新产品和服务。

    [

    https://www.wdzj.com/hjzs/ptsj/20180724/707374-1.html

    http://www.cfc365.com/technology/bigdata/2018-07-25/14785.shtml

    ]

    ThoughtWorks在2018年初就提出,数字化转型已经从流程驱动进入数据驱动的时代,数据已经成为了企业的核心生产资料。

    [https://mp.weixin.qq.com/s/Y2Q_NUKzHWTOyX99kXO5BQ]

    2018年10月,阿里云栖大会上提出”数字外场“的概念,而数字外场的核心就是数据,每一个企业都在努力的成为数据驱动的企业,所以构建数据中台之前,企业需要在企业推行数据思维,建立自己的数据战略。

    [https://www.yidianzixun.com/article/0KBGxr4g]

    数据本身在企业数字化转型的历程中,成为了最核心,最重要的生产资料,成为了企业重塑业务,自我转型的决定性因子,在这个背景下,企业需要一个源源不断的输出数据服务,数据洞察的能力源泉,数据中台的出现就成了顺理成章的事情。

    在2017年,我们就观察到到数据中台将会成为今年的风口,那个时候我们提的最多的是“精益数据资产创新”(有兴趣的同学可以自行百度搜索“精益数据资产创新”)。

    那么,数据中台到底是什么呢?

    用一句话来简单的介绍,“数据中台是数据服务(Data API)工厂”,数据中台的核心是Data API。
    在这里插入图片描述

    Data API是数据中台的核心,它是连接前台和后台的桥梁,通过API的方式提供数据服务,而不是直接把数据库给前台、让前台开发自行使用数据。至于产生DataAPI的过程,怎么样让DataAPI产生得更快,怎么样让DATA API更加清晰,怎么样让DATA API的数据质量更好,这些是要围绕数据中台去构建的能力。

    某多产业现代物流集团,在2017年就通过构建企业级数据中台,为业务人员提供了数据资产创新服务,将数据以API的形式提供给前台,从而将新产品从想法到上线的时间,提高了数倍。

    在金融领域,所有的产品、服务、交易本身就是数据化的。我们看到最复杂的业务领域,电信行业现在的网络建设,网络优化,大部分工作都是在电脑上,利用各种工具软件来处理基站和网络的数据,将网络洞察数据转换成网络扩容需求数据,将扩容需求数据设计成网络架构数据,在讲网络架构数据处理成各种不同设备型号的配置数据,同步的产生财务、物流、服务数据等。整个过程90%的工作量在处理各类数据,最后把结果数据传递到现实世界,安排发货,安装,验收等行为。而现在所提倡的工业4.0,智能制造本身也是将生产过程数据化,在数字化世界里用数据来重构工厂本身,从而利用数字化的强大的计算能力,快速的搜索能力,数据的预测能力来增强和优化业务本身。

    未来企业的业务运营,从操作本质上来讲就是加工和处理数据。数据中台就是企业的数据服务工厂,完成从数据到价值的加工过程。
    在这里插入图片描述

    对比与之前的所有的数据相关的应用和系统来讲,

    数据中台对于业务的价值是“加速从数据到价值的过程,提高企业的响应能力“。

    传统的信息化建设过程中,数据对业务的贡献是靠人看报表,从数据中理解和发现了新的思想后,通过传统的沟通方式(开会,新需求)来对业务产生影响和指导的。

    数字化时代,数据中台对于企业的价值,是加速从数据到价值的过程,提高企业的响应力。

    原来从数据报表的产生到改变业务行为是以周为单位去计算的,而数据中台的价值是通过抽象和生产数据服务,更快的影响和改变业务行为本身,这就是有的企业将数据服务直接嵌入到交易系统中,实时通过数据洞察来改变业务流程和应用本身。

    某金融科技企业,构建自己的实时风控数据中台,将原来的报表系统变成实时的智能预警平台,将合规评估从事后的模式,直接改变成事前的模式,就像在业务的高速公路上建设了一个个的风控检查站,检查站通过高速的建模,实时数据分析,能够在不影响业务速度的情况下,实时对来往的车辆做风控评估,如果有的车辆有风险,则实时预警。

    将传统的数据服务,从事后管控的模式提高到事前评估的模式,打造高数据响应力的企业是数据中台对于业务的核心价值。

    数据中台还能够为企业解决数据开发和应用开发不同步的问题。

    我们要接受并认可一个现实问题,那就是,企业的数据开发是跟不上应用的开发速度,更是跟不上业务的变化速度的。这是一个不可调和解决的问题,从市场变化到业务需求,到应用开发到沉淀成数据,这三者的速度是天生不一致的,这样的不一致会带来很多的问题,包括有开发效率的问题,有团队协作的问题,有技术能力的问题。比如,为什么开发一个报表需要十几个人天,并且大部分时间都是花在找数据,对数据,算数据上。为什么同样的一个数据需求,不同的项目就要开发两边,不能共用,不能做到一个数据出口?为什么一般的Java开发人员不能掌握数据处理,ETL的能力?

    数据中台就是要将这些能力都沉淀到一个体系中,变成数据开发的能力,变成可以复用,二次加工的数据服务工厂,加快数据开发和协作的速度。

    我们可以广义上来给数据中台一个企业级的定义:“聚合和治理跨域数据,将数据抽象封装成服务,提供给前台以业务价值的逻辑概念”。

    从T+N到T+0,数据中台将融合OLTP和OLAP,为前台业务提供更快的数据类业务服务

    十几年前,数据处理的流程分成两类,联机交易处理类(OLTP)和联机分析处理类(OLAP),分别对应两类业务需求:“T+0”和”T+N”,这是因为软件的计算能力有限,生产系统无法容纳历史数据的查询统计功能,否则就会导致海量数据的查询,拖垮生产系统的正常交易。所以不得已一个业务系统分成了两个:交易型系统和分析型系统,前者用来处理最新的交易业务,后者用来对历史的、集成的、多维的数据进行分析,支撑业务。

    我们举一个常见的电商价格策略调整的场景,原来的电商系统的价格是提前设置好的录入到电商系统数据库的,电商系统是OLTP也就是在线交易系统。电商系统对于实时性能要求很高,处理的并发交易量很大,为了提高数据库的处理速度,电商系统只保存一段时间内的交易数据,而把历史数据都归档到数据仓库系统也就是OLAP系统里。电商的运营部门定期会在OLAP系统里挖掘历史数据来分析不同的商品的交易数据和价格的关系,然后决定电商系统的价格是不是需要调整。所以传统电商系统,产品价格的变化需要一个比较长的周期的。到了今天,价格本身受影响的维度越来越多,市场需要电商系统的价格能够实时的根据历史数据进行变化,这样一来,传统的OLTP和OLAP分离的架构就不能够满足业务需求了。

    随着大容量高速存储技术的发展、计算能力的提升、微服务、大数据架构的出现,OLTP和OLAP在逐渐融合:应用系统能够实时的基于多维、多渠道、历史数据的分析来定制化交易流程和和行为。OLTP和OLAP从平行的关系,变成垂直的关系。

    刚才举的电商的例子是互联网时代的典型场景,而对于比较传统的金融保险行业来说,目前也正面临着这样的挑战。很多保险产品的报价需要进行信息搜集,评估,审核,而这个过程就是数据的采集,建模,评估,模拟的过程,过去这样的业务都是”T+N”,就是从接到交易申请到给出结果,需要N天,而现在市场的竞争愈加激烈,更快,更准确的给出报价,所以业务要就能够尽量做到”T+0”,实时响应市场的需求。

    这就意味着要把原来的OLAP的历史数据分析,建模,评估的过程和OLTP系统里的交易数据进行融合分析才能够做到。

    我们观察到,从金融保险到电信制造,原来传统的”T+N”的需求都在朝”T+0”演进,大家都在寻找高响应力,快速反馈的实时分析型数据数据处理架构,将数据从原来传统的经营分析领域演进到直接参与业务交易。

    所以我们认为未来的交易型系统,都会变成分析型交易系统(Analytic Transcation Processing),具有跨域、全量数据分析的支持能力,用数据分析来支持交易的动态敏捷变化,高速响应市场和用户的需求,而OLTP和OLAP也会在云计算,微服务,大数据等技术支撑下逐渐融合。

    2.数据中台和数据仓库,数据平台的关系是什么?

    下面这张图说明了企业对于数据处理需求的变化和演进:
    在这里插入图片描述
    早期,企业的数据是少量的,利用Excel等数据文件处理工具来进行统计和手工分析。

    然后,企业希望能够更快的处理比较多的数据,就有了数据仓库的出现,也希望利用数据来支撑运营和分析。接下来不仅有了结构化数据,还出现了非结构化数据,并且运营对于数据的需求越来越多,数据量也越来越大,这就出现了大数据平台,去处理各种不同格式,不同领域的数据,这个过程都是业务数据化的过程。

    到数字化的今天,企业不仅希望事后的运营能够靠数据支撑,更希望构建数据驱动的业务本身,所以,企业需要将这些数据变成一个个业务服务应用到业务本身,参与到业务流程,业务应用的过程中,去改变和驱动业务行为,这也就是”数据业务化“,我把”数据业务化“理解成是”数据业务服务化“的简称。

    这个过程,就能很清晰的解答数据中台和数据仓库,数据平台的关系。

    第一,他们不是一个维度的东西,数据仓库和数据平台是提供数据的系统,而数据中台是提供业务服务的系统,数据中台是能够直接为业务提供数据服务的。但是数据中台是需要构建在数据之上的,所以,数据中台是可以构建在数据仓库、数据平台之上的。

    第二、数据中台能够以提供数据服务的方式直接驱动和改变业务行为本身,而不需要人的介入,数据中台距离业务更近,为业务产生价值的速度更快。

    一句话来总结,数据仓库,数据平台提供的是数据本身,而数据中台提供的是有直接业务价值的数据服务,数据中台距离业务更近。

    3.数据中台建设的最大的挑战是什么

    数据中台建设的最大挑战,是如何找到有价值的业务场景。

    数据中台是一个能力平台,是将企业的数据能力封装到一个平台中,快速提供给业务前台使用的工作。那么企业需要什么样的数据能力,哪些业务需要这些能力,这些数据能力之间的关系是什么?这是一个体系化的工作,是需要进行整体规划和顶层设计的。

    数据中台从出生那一天起就承担着为业务提供更快的数据服务的使命,所以它是和业务价值紧密绑定的,不能提供业务价值的数据服务就是一种浪费。所以如何能够找到,识别出有价值的业务场景是数据中台建设的最大,也是最紧迫的挑战。但是这里就有一个矛盾,业务场景是不断被挖掘和演进的,是快速变化的,而作为能力平台是要支撑全场景的,是要相对稳定的,如何平衡这两者之间的关系呢?

    我们总结了数据中台建设的三大策略:围绕业务价值,演进式架构,要有战略耐心。

    业务价值策略:

    数据中台建设应该以"业务价值为纲,生于业务场景,高于业务场景,始于业务场景。"

    数据中台的建设需求,要围绕业务价值产生。所以所有的功能设计要有对应的业务场景需求为根源,但是数据服务是要抽象, 建模,复用的,所以数据中台在业务场景的基础上要高于业务场景,完成总体的架构设计。

    最终建设的时候,我们不建议那种传统的分层的方式,而是在总的架构设计为目标,要从某一个业务场景出发建设,从业务价值,平台能力和数据治理三个方面同步建设。

    演进式架构策略:

    数据中台的建设应该”快规划,重场景,轻标准“。

    我们所说的规划,不是那种传统意义上的很重,很细致的流程层面的IT规划,而是比较快,比较轻的,围绕业务价值的场景探索式的规划。要轻标准,不要试图去做一个放之四海皆准的企业级数据中台标准,并且定制的很细致,要充分理解市场的动态性,标准一定要轻量,越重实施起来就是枷锁,很难落地。

    战略耐心策略:

    投资方和建设方都要有战略耐心。

    投资方要清晰的认识到数据中台是一个赋能平台,是一个体系化的工作,融合了技术、组织、能力、机制等多个因素,不是一蹴而就的,所以要有一定的耐心给到数据中台的价值露出。

    建设方也要清晰地认识到数据中台是一个复杂工程,是一个演进迭代式的建设工程,是不能毕其功于一役的,要有策略,有步骤的去建设,不要试图做一个大而全,大一统的平台。要服务于业务,高于业务,要深入到业务场景当中去才能获得业务的支持,获得持续的生命力。

    在以上三个策略的基础上,我们在过去的实践中,设计和总结了一套精益数据探索方法(LDD),通过四个阶段来产出数据中台的建设路线。

    在这里插入图片描述

    5.数据中台里的数据质量应该如何保障?

    过去这么多年的经验教训告诉我们,数据质量的问题是不可能百分之百解决掉的,因为业务变化的速度快于数据变化的速度,这是一个客观存在的而且短期内不可能改变的事实。我们最应该关心的应该是数据如何能够给业务产生价值,即使只有50%的数据准确度,在治理数据质量的同时,依然要找到这些数据可以为业务产生价值的方法和场景。

    这个问题应该改成,如何治理好现有的数据为业务产生价值。

    数据治理是要服务于业务场景的,而传统的数据治理方法,更多的将数据和业务独立了出来,最后数据治理项目的成果基本上可以归纳为创造了”三个一“工程:

    一堆新岗位:传统的数据治理项目一般会产生一堆新职位,比如主数据管理员,物料管理员,数据治理委员会等。

    一摞新流程:一批新的流程和标准会发布出来,告诉所有的业务项目组,应该遵循这个流程来管理数据。

    一批新系统:会上线一批数据管理系统,将流程和规则固化到系统中。

    但是,很少有数据治理项目能根本上解决数据质量的问题,并且有些项目导致业务的速度变慢了,最后都流于形式和标准。

    这是因为传统的数据治理都是管控式治理,而不是服务式治理。他们的目标是把数据标准定出来,然后让业务服从于这个数据标准,却忽视了,数据标准是为了业务服务的。

    所以,在精益数据创新体系中,我们提倡和实践新的治理方法:精益数据治理(Lean Data Governance):服务式治理,重场景轻标准,元数据驱动

    在这里插入图片描述

    服务式原则:

    我们实践服务式的治理,轻管控,以解决业务问题为目标,而不以数据质量为唯一目标

    场景核心原则:

    数据标准越轻越好,强调与业务场景的融合,能够服务好业务场景,产生业务价值的数据标准就是好标准

    元数据驱动原则:

    原来的数据治理很多都是事前进行管控,让业务服从于数据管理,比如主数据的管理,需要有事前审批。而我们现在更多的在实践利用元数据驱动的数据管理的方式,将审批流程弱化,通过自动化数据技术,让业务无感,从事前管控变成事后归因。不影响业务交易的速度,将复杂的事情坐在后端。

    6.数据中台的典型架构是怎样的?

    数据中台是直接服务于业务系统的数据服务工厂,狭义上讲,数据中台就是可复用的数据API。

    站在企业架构的角度,从广义上来讲,数据中台(包含数据平台,数据仓库)应该提供的服务如下图所示:
    在这里插入图片描述
    1.数据资产的规划和治理

    做中台之前,首先需要知道业务价值是什么,从业务角度去思考企业的数据资产是什么。数据资产不等同于数据,数据资产是唯一的,能为业务产生价值的数据。对于同一堆数据,不同业务部门所关注的数据指标可能完全不同,怎么让各个跨域的业务变成统一的标准,就需要规划企业的数据全景图,将所有有可能用上的、所有对企业有可能有价值的数据都规划出来,最终梳理出企业的数据资产目录。在这个时候不需要考虑有没有系统、有没有数据,只需要关注哪些数据是对企业业务有价值的。这一层不建议做得太细,太细就难以形成标准,不能适用于多个场景了。数据治理是数据中台很重要的一个领域,ThoughtWorks认为在现在业务边界消失、需求快速变化的情况下,企业需要具备精益数据治理的能力——Lean Data Governance。传统的中心化、事前控制式的数据治理方式,要改变为去中心化、事后服务式的治理方式。

    2.数据资产的获取和存储

    从广义上来讲,数据中台要为企业提供强大的数据资产的获取和存储的能力。但是这个能力不是数据中台的核心功能,很多企业可以基于原来的数据平台,数据仓库等已有的工具来提供数据采集和存储的能力。

    3.数据的共享和协作

    企业的数据中台一定是跨域的,需要让所有的人都知道数据资产目录在哪里。不能因为数据安全,就不让大家知道企业有什么数据。没有共享和开放,数据没有办法流动起来,没有流动的话数据的价值产生的速度就会非常慢。所以在数据安全的基础上,企业的数据资产目录要对利益相关者、价值创造者开放,要让业务人员能够做到“Self-Service”。

    数据资产目录是数据中台很核心的一个基础能力,但是往往目前很多的企业都尚未建立这个能力,这也是导致数据在企业内部不开放,不共享,不被利用的很重要的一个原因。

    4.业务价值的探索和分析

    数据中台不仅要建立到源数据的通路,还需要提供分析数据的工具和能力,帮助业务人员去探索和发现数据的业务价值。一个好的数据中台解决方案中需要针对不同业务岗位的用户提供个性化的数据探索和分析的工具,并且在此基础上一键生成数据API,以多样化的方式提供给前台系统。

    5.数据服务的构建和治理

    数据中台需要保证数据服务的性能和稳定性,以及数据质量和准确性,还需要具备强大的服务治理能力。数据服务要在一开始就有整体的顶层设计,从而能够将数据服务做分类,打标签,能够更方便的被搜索被调用,让好的服务浮现出来,让质量不高的服务自动的退市被销毁。

    数据中台是一个生态平台,在数据中台上面会不断生长各种数据服务,所以从一开始就构建好数据服务的治理结构是非常重要的,就想经营一个市场一样。

    6.数据服务的度量和运营

    如果数据中台最终只是做到把数据给到业务人员,那它就只是一个搬运工的角色,数据中台的核心是为业务应用提供有业务价值的数据服务。所以度量和运营数据服务的能力是数据中台的业务能力。

    数据中台应该能够对提供的数据服务及相关行为做持续跟踪和记录,包括哪些数据服务被哪个部门使用、用了多少次等,通过这些去度量每一个数据服务的业务价值。

    数据中台是一个需要用互联网思维去经营的利润中心平台,数据中台的经营分析人员需要分·析务,了解为什么今天上午这个财务部门的人用了数据中台、调用了十次,下午他不用了,原因是什么,调用了这些数据服务的人通常还会调用哪些其他的数据服务。这些都需要相应地做记录、做日志、做分析,要把数据当做像电商平台一样去经营,然后实时地根据这些业务行为数据去提醒数据服务提供方,调整、改变、优化数据服务,这才是可经营的数据中台,也只有这样业务部门才能得到最快的支持和响应。

    在这样的一个功能愿景下,我们初步定义了一个数据中台的典型逻辑功能架构:

    在这里插入图片描述

    这个架构中,把数据中台比喻为数据工厂,具备数据工厂的典型功能架构。

    7.数据中台和业务中台服务有什么区别

    应该如何去界定和划分?

    在目前,与数据中台齐名的还有业务中台,但是业务中台和数据中台有什么区别呢?

    数据中台和业务中台都是为业务系统提供服务的中台层,他们的区别在于提供的服务不一样。

    我们举几个例子:

    多个电商渠道使用一个下单服务,一个订单接口同时为多个前台系统提供服务,这是业务中台提供的能力。

    多个前台系统,根据一个用户的手机号,获取对应的画像,用户的标签,这是数据中台提供的服务。

    将多个支付通道,抽象建立成一个支付API,暴露给前台业务系统,这是业务中台提供的能力。

    通过一个订单编号,来获取可能的商品推荐清单,从而做到交叉销售,这是数据中台提供的服务。

    所以,我们可以总结一下:
    在这里插入图片描述

    业务中台提供的是可复用的流程类,交易类服务,是为了让业务交易同口径,让前台系统更标准,更规范,迭代速度更快,解决效率和产生数据不一致的问题。对应到API,是业务命令式API。

    数据中台提供的是基于跨域数据的分析,洞察,训练产生的数据服务,是给前台系统提供实时决策数据。对应到API是,计算类的智能API和查询类的数据API。

    一句话总结:业务中台让前台系统更敏捷,数据中台让前台业务系统更智慧。

    8.企业数据中台的团队如何构建?绩效如何评价?

    数据中台是距离业务更近的能力平台,数据中台是一个需要持续运营的数据服务业务平台,所以数据中台的团队不仅仅是一个技术团队,应该将数据中台当做一个产品团队来构建,整体的结构如下:

    数据中台提供两类服务:

    一类是数据资产目录,数据探索,数据分析等服务,让业务和应用部门的人员能够在数据中台上协作的玩数据。

    一类是数据服务,让各个业务系统能够调用这些服务,包括决策分析类的非实时服务和实时的嵌入式交易规则服务。

    对应到这两类服务,数据中台的团队应该包括以下三组:

    中台运营团队:

    将整个数据中台的服务和功能作为产品来运营,对应的绩效是用户满意度,用户存留,这些用户相关的指标。

    中台开发团队:

    负责数据中台的功能层开发,包括平中台本身的架构,中台上的应用(客户服务,业务监控等)功能的开发,对应的绩效是功能的稳定性和客户的满意度。

    数据服务开发团队:

    负责数据中台之上的数据服务的开发,包括数据处理链的开发,服务的开发等,对应的绩效是数据服务的稳定性, 性能和客户的满意度等。

    参考这样的三个团队组成, 分别应该包括如下角色:

    数据中台架构师:进行整体数据中台的技术架构设计,保证数据中台架构的可持续性,稳定性和扩容弹性。

    DataOps工程师:从基础能力上保障数据中台的运行的稳定性和持续演进。

    数据工程师:数据处理工程师,负责数据的获取,处理,建立数据处理链。

    数据服务产品团队:数据服务的产品团队,包括产品经理(PO),业务分析师,体验设计师,还有算法工程师,和数据工程师和数据运营分析师一起协作,创新、设计、生产数据服务。

    数据运营分析师:将数据服务作为产品来运营的数据运营分析师,通过对数据服务上线后被调用的情况的分析来运营数据服务,像经营一个互联网产品一样来经营数据服务。

    数据中台某种角度上,上是一个数据服务的创新、生产、交易的数据服务市场,那么企

    业对于数据中台整体的绩效评价方法也就出来了,那就是:

    企业评价数据中台的标准:数据中台服务的客户,也就是业务系统的满意度。

    那么如何度量业务系统的满意度呢?我们认为,标准很简单,也很清晰,那就是数据中台提供的的数据服务被业务系统,被业务人员使用的频率。业务人员和业务系统调用多的服务,一定是对业务更有帮助的数据服务。

    最后,我们在回顾一下这八个重要的问题及解读:

    1.数据中台是什么,数据中台对于业务的价值是什么?

    数据中台是数据服务(Data API)工厂,打造高数据响应力的企业

    2.数据中台和数据仓库,数据平台的关系是什么?

    数据仓库,数据平台提供的是数据本身,而数据中台提供的是有直接业务价值的数据服务。

    3.数据中台建设的最大挑战是什么,应该遵循什么策略?

    数据中台建设的最大挑战,是如何找到有价值的业务场景。

    数据中台建设的三大策略:围绕业务价值,演进式架构,要有战略耐心。

    4.数据中台的数据质量应该如何保障?

    正视数据质量的问题是客观存在的,采用提倡和实践新的治理方法:精益数据治理(Lean Data Governance):服务式治理,重场景,元数据驱动

    5.数据中台的典型功能架构是怎样的?

    广义的讲数据中台是直接服务于业务系统的数据服务工厂

    6.数据中台和业务中台服务有什么区别,应该如何去界定和划分?

    业务中台让前台系统更敏捷,数据中台让前台业务系统更智慧。业务中台提供交易API,数据中台提供数据和智能API

    7.企业数据中台的团队如何构建?

    要按照运营一个互联网平台式产品的方式来组织数据中台的团队。

    8.数据中台的绩效如何评价?

    数据中台服务的用户和业务系统的满意度是数据中台的绩效

    展开全文
  • 目标检测数据整理

    万次阅读 多人点赞 2018-06-02 22:13:28
    本篇博客主要整理基于深度学习的目标检测所用的数据集, 评价指标见上一篇博客。 参考链接: 1、链接1 2、链接2 3、链接3 1、Pascal VOC 2、COCO

    本篇博客主要整理基于深度学习的目标检测所用的数据集,

    评价指标见上一篇博客


    参考链接:

    1、链接1

    2、链接2

    3、链接3

    1、Pascal VOC

    VOC综述

    VOC数据集是目标检测经常用的一个数据集,从05年到12年都会举办比赛(比赛有task: Classification 、Detection(将图片中所有的目标用bounding box框出来) 、 Segmentation(将图片中所有的目标分割出来)、Person Layout),

    然后本篇博客主要整理了VOC2007和VOC2012两个数据集。

    然后先介绍一下VOC数据集,以2007版为例。

    一共包含了20类。

    • person
    • bird, cat, cow, dog, horse, sheep
    • aeroplane, bicycle, boat, bus, car, motorbike, train
    • bottle, chair, dining table, potted plant, sofa, tv/monitor

    关于数据集:
    - 所有的标注图片都有Detection需要的label, 但只有部分数据有Segmentation Label。
    - VOC2007中包含9963张标注过的图片, 由train/val/test三部分组成, 共标注出24,640个物体。
    - VOC2007的test数据label已经公布, 之后的没有公布(只有图片,没有label)
    - 对于检测任务,VOC2012的trainval/test包含08-11年的所有对应图片。 trainval有11540张图片共27450个物体。

    数据集下载完后会有5个文件夹。Annotations、ImageSets、JPEGImages、SegmentationClass、SegmentationObject。

    JPRGImages

    包含了所有的图片信息,包含训练集和验证集。

    以年份和编号命名,尺寸大约为500*375或者是375*500,训练或者验证时会统一resize。

    这里写图片描述

    Annotations

    存放的是xml格式的标签文件,每一个xml文件都对应于JPEGImages文件夹中的一张图片

    这里写图片描述

    <annotation>
        <folder>VOC2007</folder>
        <filename>000005.jpg</filename>#文件名
        <source>#文件来源
            <database>The VOC2007 Database</database>
            <annotation>PASCAL VOC2007</annotation>
            <image>flickr</image>
            <flickrid>325991873</flickrid>
        </source>
        <owner>
            <flickrid>archintent louisville</flickrid>
            <name>?</name>
        </owner>
        <size>#文件尺寸,包括长、宽、通道数
            <width>500</width>
            <height>375</height>
            <depth>3</depth>
        </size>
        <segmented>0</segmented>#是否用于分割
        <object>#检测目标
            <name>chair</name>#目标类别
            <pose>Rear</pose>#摄像头角度
            <truncated>0</truncated>#是否被截断,0表示完整
            <difficult>0</difficult>#目标是否难以识别,0表示容易识别
            <bndbox>#bounding-box
                <xmin>263</xmin>
                <ymin>211</ymin>
                <xmax>324</xmax>
                <ymax>339</ymax>
            </bndbox>
        </object>
        <object>#检测到的多个物体, 可以看到上图中,图片000005中有多个椅子
            <name>chair</name>
            <pose>Unspecified</pose>
            <truncated>0</truncated>
            <difficult>0</difficult>
            <bndbox>
                <xmin>165</xmin>
                <ymin>264</ymin>
                <xmax>253</xmax>
                <ymax>372</ymax>
            </bndbox>
        </object>
        <object>#检测到的多个物体
            <name>chair</name>
            <pose>Unspecified</pose>
            <truncated>1</truncated>
            <difficult>1</difficult>
            <bndbox>
                <xmin>5</xmin>
                <ymin>244</ymin>
                <xmax>67</xmax>
                <ymax>374</ymax>
            </bndbox>
        </object>
        <object>
            <name>chair</name>
            <pose>Unspecified</pose>
            <truncated>0</truncated>
            <difficult>0</difficult>
            <bndbox>
                <xmin>241</xmin>
                <ymin>194</ymin>
                <xmax>295</xmax>
                <ymax>299</ymax>
            </bndbox>
        </object>
        <object>#检测到的多个物体
            <name>chair</name>
            <pose>Unspecified</pose>
            <truncated>1</truncated>
            <difficult>1</difficult>
            <bndbox>
                <xmin>277</xmin>
                <ymin>186</ymin>
                <xmax>312</xmax>
                <ymax>220</ymax>
            </bndbox>
        </object>
    </annotation>
    

    对应图片为:

    这里写图片描述

    ImageSets

    ImageSets中是每一种类型的challenge对应的图像数据。

    一共四个文件夹,不知道为什么,win7下载后只有3个文件夹。

    这里写图片描述

    • Action下存放的是人的动作(例如running、jumping等等,这也是VOC challenge的一部分)
    • Layout下存放的是具有人体部位的数据(人的head、hand、feet等等,这也是VOC challenge的一部分)
    • Main下存放的是图像物体识别的数据,总共分为20类。
    • Segmentation下存放的是可用于分割的数据。

    然后我们主要关注于main文件夹。里面放了20个类的train、val、trainval的txt。

    这里写图片描述

    • _train中存放的是训练使用的数据,每一个class的train数据都有5717个。
    • _val中存放的是验证结果使用的数据,每一个class的val数据都有5823个。
    • _trainval将上面两个进行了合并,每一个class有11540个。

    这里写图片描述

    上图中前面代表图片编号,后面-1代表负样本,1代表正样本。

    SegmentationClass

    这里面包含了2913张图片,每一张图片都对应JPEGImages里面的相应编号的图片。这里面的图片的像素颜色共有20种,对应20类物体。比如所有飞机都会被标为红色。

    这里写图片描述

    SegmentationObject

    这里面同样包含了2913张图片,图片编号都与Class里面的图片编号相同。这里面的图片和Class里面图片的区别在于,这是针对Object的。在Class里面,一张图片里如果有多架飞机,那么会全部标注为红色。而在Object里面,同一张图片里面的飞机会被不同颜色标注出来。

    这里写图片描述

    VOC 2007

    Train/Validation Data (439 MB)
    Test Data With Annotations (431 MB)
    Development Kit
    PDF Documentation

    VOC 2012

    Train/Validation Data (1.9 GB)
    Test Data (1.8 GB)
    Development Kit
    PDF Documentation

    2、COCO

    参考链接1

    参考链接2

    和VOC相比,coco数据集,小目标多、单幅图片目标多、物体大多非中心分布、更符合日常环境,所以coco检测难度更大。

    1)Object segmentation(2)Recognition in Context(3)Multiple objects per image(4)More than 300,000 images(5)More than 2 Million instances(6)80 object categories(7)5 captions per image(8)Keypoints on 100,000 people

    coco数据集以场景理解为目标,从复杂的日常场景中截取,图像中的目标通过精确的Segmentation进行位置的标定,包含91类目标.

    展开全文
  • 今天我们分享一个小案例,获取天气数据,进行可视化分析,带直观了解天气情况! 一、核心功能设计 总体来说,我们需要先对天气网的天气数据进行爬取,保存为csv文件,并将这些数据进行可视化分析展示。 拆解需求...

    前言

    今天我们分享一个小案例,获取天气数据,进行可视化分析,带你直观了解天气情况!

    一、核心功能设计

    总体来说,我们需要先对中国天气网中的天气数据进行爬取,保存为csv文件,并将这些数据进行可视化分析展示。

    拆解需求,大致可以整理出我们需要分为以下几步完成:

    1. 通过爬虫获取中国天气网7.20-7.21的降雨数据,包括城市,风力方向,风级,降水量,相对湿度,空气质量
    2. 对获取的天气数据进行预处理,分析河南的风力等级和风向,绘制风向风级雷达图
    3. 根据获取的温度和湿度绘制温湿度相关性分析图,进行温度、湿度对比分析。
    4. 根据获取的各城市的降雨量,可视化近24小时的每小时时段降水情况
    5. 绘制各城市24小时的累计降雨量

    二、实现步骤

    1. 爬取数据

    首先我们需要获取各个城市的降雨数据,通过对中国天气网网址分析发现,城市的天气网址为:http://www.weather.com.cn/weather/101180101.shtml。

    在这里插入图片描述

    根据对数据分析,返回的json格式数据,不难发现:

    • 101180101就是代表城市编号
    • 7天的天气预报数据信息在div标签中并且id=“7d”
    • 日期、天气、温度、风级等信息都在ul和li标签

    网页结构我们上面已经分析好了,那么我们就可以来动手爬取所需要的数据了。获取到所有的数据资源之后,可以把这些数据保存下来。

    请求网站:

    天气网的网址:http://www.weather.com.cn/weather/101180101.shtml。如果想爬取不同的地区只需修改最后的101180101地区编号,前面的weather代表是7天的网页。

    def getHTMLtext(url):
    	"""请求获得网页内容"""
    	try:
    		r = requests.get(url, timeout = 30)
    		r.raise_for_status()
    		r.encoding = r.apparent_encoding
    		print("Success")
    		return r.text
    	except:
    		print("Fail")
    		return" "
    

    在这里插入图片描述

    处理数据:

    采用BeautifulSoup库对刚刚获取的字符串进行数据提取。获取我们需要的风力方向,风级,降水量,相对湿度,空气质量等。

    def get_content(html,cityname):
    	"""处理得到有用信息保存数据文件"""
    	final = []  							 # 初始化一个列表保存数据
    	bs = BeautifulSoup(html, "html.parser")  # 创建BeautifulSoup对象
    	body = bs.body
    	data = body.find('div', {'id': '7d'})    # 找到div标签且id = 7d
    	# 下面爬取当天的数据
    	data2 = body.find_all('div',{'class':'left-div'})
    	text = data2[2].find('script').string
    	text = text[text.index('=')+1 :-2]		 # 移除改var data=将其变为json数据
    	jd = json.loads(text)
    	dayone = jd['od']['od2']				 # 找到当天的数据
    	final_day = []						     # 存放当天的数据
    	count = 0
    	for i in dayone:
    		temp = []
    		if count <=23:
    			temp.append(i['od21'])				 # 添加时间
    			temp.append(cityname+'市')			# 添加城市
    			temp.append(i['od22'])				 # 添加当前时刻温度
    			temp.append(i['od24'])				 # 添加当前时刻风力方向
    			temp.append(i['od25'])				 # 添加当前时刻风级
    			temp.append(i['od26'])				 # 添加当前时刻降水量
    			temp.append(i['od27'])				 # 添加当前时刻相对湿度
    			temp.append(i['od28'])				 # 添加当前时刻控制质量
    # 			print(temp)
    			final_day.append(temp)
    			data_all.append(temp)
    		count = count +1
    	# 下面爬取24h的数据
    	ul = data.find('ul')                     # 找到所有的ul标签
    	li = ul.find_all('li')                   # 找到左右的li标签
    	i = 0                                    # 控制爬取的天数
    	for day in li:                          # 遍历找到的每一个li
    	    if i < 7 and i > 0:
    	        temp = []                        # 临时存放每天的数据
    	        date = day.find('h1').string     # 得到日期
    	        date = date[0:date.index('日')]  # 取出日期号
    	        temp.append(date)
    	        inf = day.find_all('p')          # 找出li下面的p标签,提取第一个p标签的值,即天气
    	        temp.append(inf[0].string)
    
    	        tem_low = inf[1].find('i').string  	# 找到最低气温
    
    	        if inf[1].find('span') is None:  	# 天气预报可能没有最高气温
    	            tem_high = None
    	        else:
    	            tem_high = inf[1].find('span').string  # 找到最高气温
    	        temp.append(tem_low[:-1])
    	        if tem_high[-1] == '℃':
    	        	temp.append(tem_high[:-1])
    	        else:
    	        	temp.append(tem_high)
    
    	        wind = inf[2].find_all('span')		# 找到风向
    	        for j in wind:
    	        	temp.append(j['title'])
    
    	        wind_scale = inf[2].find('i').string # 找到风级
    	        index1 = wind_scale.index('级')
    	       	temp.append(int(wind_scale[index1-1:index1]))
    	        final.append(temp)
    	    i = i + 1
    	return final_day,final
    

    城市的天气数据拿到了,同理我们可以根据不同的地区编号获取河南省各个地级市的天气数据。

    Citycode = { "郑州": "101180101",
                 "新乡": "101180301",
                 "许昌": "101180401",
                 "平顶山": "101180501",
                 "信阳": "101180601",
                 "南阳": "101180701",
                 "开封": "101180801",
                 "洛阳": "101180901",
                 "商丘": "101181001",
                 "焦作": "101181101",
                 "鹤壁": "101181201",
                 "濮阳": "101181301",
                 "周口": "101181401",
                 "漯河": "101181501",
                 "驻马店": "101181601",
                 "三门峡": "101181701",
                 "济源": "101181801",
                 "安阳": "101180201"}
    citycode_lists = list(Citycode.items())
    for city_code in citycode_lists:
        city_code = list(city_code)
        print(city_code)
        citycode = city_code[1]
        cityname = city_code[0]
        url1 = 'http://www.weather.com.cn/weather/'+citycode+ '.shtml'    # 24h天气中国天气网
    	html1 = getHTMLtext(url1)
    	data1, data1_7 = get_content(html1,cityname)		# 获得1-7天和当天的数据
    

    存储数据:

    def write_to_csv(file_name, data, day=14):
    	"""保存为csv文件"""
    	with open(file_name, 'a', errors='ignore', newline='') as f:
    		if day == 14:
    			header = ['日期','城市','天气','最低气温','最高气温','风向1','风向2','风级']
    		else:
    			header = ['小时','城市','温度','风力方向','风级','降水量','相对湿度','空气质量']
    		f_csv = csv.writer(f)
    		f_csv.writerow(header)
    		f_csv.writerows(data)
    write_to_csv('河南天气.csv',data_all,1)
    
    

    这样我们就可以把全省的各个地级市天气数据保存下来了。

    在这里插入图片描述

    2. 风向风级雷达图

    统计全省的风力和风向,因为风力风向使用极坐标的方式展现比较清晰,所以我们采用极坐标的方式展现一天的风力风向图,将圆分为8份,每一份代表一个风向,半径代表平均风力,并且随着风级增高,蓝色加深。

    def wind_radar(data):
    	"""风向雷达图"""
    	wind = list(data['风力方向'])
    	wind_speed = list(data['风级'])
    	for i in range(0,24):
    		if wind[i] == "北风":
    			wind[i] = 90
    		elif wind[i] == "南风":
    			wind[i] = 270
    		elif wind[i] == "西风":
    			wind[i] = 180
    		elif wind[i] == "东风":
    			wind[i] = 360
    		elif wind[i] == "东北风":
    			wind[i] = 45
    		elif wind[i] == "西北风":
    			wind[i] = 135
    		elif wind[i] == "西南风":
    			wind[i] = 225
    		elif wind[i] == "东南风":
    			wind[i] = 315
    	degs = np.arange(45,361,45)
    	temp = []
    	for deg in degs:
    		speed = []
    		# 获取 wind_deg 在指定范围的风速平均值数据
    		for i in range(0,24):
    			if wind[i] == deg:
    				speed.append(wind_speed[i])
    		if len(speed) == 0:
    			temp.append(0)
    		else:
    			temp.append(sum(speed)/len(speed))
    	print(temp)
    	N = 8
    	theta = np.arange(0.+np.pi/8,2*np.pi+np.pi/8,2*np.pi/8)
    	# 数据极径
    	radii = np.array(temp)
    	# 绘制极区图坐标系
    	plt.axes(polar=True)
    	# 定义每个扇区的RGB值(R,G,B),x越大,对应的颜色越接近蓝色
    	colors = [(1-x/max(temp), 1-x/max(temp),0.6) for x in radii]
    	plt.bar(theta,radii,width=(2*np.pi/N),bottom=0.0,color=colors)
    	plt.title('河南风级图--Dragon少年',x=0.2,fontsize=16)
    	plt.show()
    

    结果如下:
    在这里插入图片描述

    观察可以发现,当天的东北风最多,平均风级达到了1.75级。

    3. 温湿度相关性分析

    我们可以分析温度和湿度之间是否存在关系,为了更加清楚直观地验证,可以使用离散点plt.scatter()方法将温度为横坐标、湿度为纵坐标,每个时刻的点在图中点出来,并且计算相关系数。

    def calc_corr(a, b):
    	"""计算相关系数"""
    	a_avg = sum(a)/len(a)
    	b_avg = sum(b)/len(b)
    	cov_ab = sum([(x - a_avg)*(y - b_avg) for x,y in zip(a, b)])
    	sq = math.sqrt(sum([(x - a_avg)**2 for x in a])*sum([(x - b_avg)**2 for x in b]))
    	corr_factor = cov_ab/sq
    	return corr_factor
    
    
    def corr_tem_hum(data):
    	"""温湿度相关性分析"""
    	tem = data['温度']
    	hum = data['相对湿度']
    	plt.scatter(tem,hum,color='blue')
    	plt.title("温湿度相关性分析图--Dragon少年")
    	plt.xlabel("温度/℃")
    	plt.ylabel("相对湿度/%")
    	# plt.text(20,40,"相关系数为:"+str(calc_corr(tem,hum)),fontdict={'size':'10','color':'red'})
    	plt.show()
    	print("相关系数为:"+str(calc_corr(tem,hum)))
    

    结果如下:

    在这里插入图片描述
    观察可以发现,一天的温度和湿度具有强烈的相关性,呈负相关。当温度较低时,空气中水分含量较多,湿度自然较高,而温度较高时,水分蒸发,空气就比较干燥,湿度较低。

    4. 24小时内每小时时段降水

    from pyecharts import options as opts
    from pyecharts.charts import Map,Timeline
    #定义一个timeline和map的组合图
    def timeline_map(data):
        tl = Timeline().add_schema(play_interval =300,height=40,is_rewind_play=False,orient = "horizontal",is_loop_play = True,is_auto_play=False)#设置播放速度、是否循环播放等参数
        for h in time_line_final:
            x =data[data["小时"]==h]['城市'].values.tolist() #选取指定城市
            y=data[data["小时"]==h]['降水量'].values.tolist() #选取时间的降水量
            map_shape = (
                Map()
                .add("{}h时降水量(mm)".format(h),[list(z) for z in zip(x, y)],"河南") #打包输入地区及对应降水量数据
                .set_series_opts(label_opts=opts.LabelOpts("{b}")) #配置系列参数,{b}为显示地区数据
                .set_global_opts(
                    title_opts=opts.TitleOpts(title="河南省降雨分布--Dragon少年"), #全局参数中设置标题
                    visualmap_opts=opts.VisualMapOpts(max_=300,  #设置映射配置项的最大值
                                                      is_piecewise=True, #设置是否为分段显示
                                                      pos_top = "60%", #映射配置项距图片上部的距离
                                                      pieces=[
                                                            {"min": 101, "label": '>100ml', "color": "#FF0000"},  # 分段指定颜色及名称
                                                            {"min": 11, "max": 50, "label": '11-50ml', "color": "#FF3333"},
                                                            {"min": 6, "max": 10, "label": '6-10ml', "color": "#FF9999"},
                                                            {"min": 0.1, "max": 5, "label": '0.1-5ml', "color": "#FFCCCC"}])
            ))
            tl.add(map_shape, "{}h".format(h)) #将不同日期的数据加入到timeline中
        return tl
    timeline_map(data).render("rainfall.html")
    

    效果如下:

    在这里插入图片描述

    观察可以发现,7.20当天大部分地区均有雨,7月20日17时-18时一小时的降水量达到了201.9mm。

    4. 24小时累计降雨量

    from pyecharts import options as opts
    from pyecharts.charts import Map,Timeline
    #定义一个timeline和map的组合图
    time_line_final = list(data1['小时'].iloc[0:24])
    def timeline_map(data1):
        tl = Timeline().add_schema(play_interval =200,height=40,is_rewind_play=False,orient = "horizontal",is_loop_play = True,is_auto_play=True)#设置播放速度、是否循环播放等参数
        for h in time_line_final:
            x =data1[data1["小时"]==h]['城市'].values.tolist() #选取指定城市
            y=data1[data1["小时"]==h]['降水量'].values.tolist() #选取时间的降水量
            map_shape1 = (
                Map()
                .add("{}h时累计降水量(mm)".format(h),[list(z) for z in zip(x, y)],"河南") #打包输入地区及对应降水量数据
                .set_series_opts(label_opts=opts.LabelOpts("{b}")) #配置系列参数,{b}为显示地区数据
                .set_global_opts(
                    title_opts=opts.TitleOpts(title="河南省累计降雨分布--Dragon少年"), #全局参数中设置标题
                    visualmap_opts=opts.VisualMapOpts(max_=300,  #设置映射配置项的最大值
                                                      is_piecewise=True, #设置是否为分段显示
                                                      pos_top = "60%", #映射配置项距图片上部的距离
                                                      pieces=[
                                                            {"min": 251, "label": '特大暴雨', "color": "#800000"},  # 分段指定颜色及名称
                                                            {"min": 101, "max": 250, "label": '暴雨', "color": "#FF4500"},
                                                            {"min": 51, "max": 100, "label": '暴雨', "color": "#FF7F50"},
                                                            {"min": 25, "max": 50, "label": '大雨', "color": "#FFFF00"},
                                                            {"min": 10, "max": 25, "label": '中雨', "color": "#1E90FF"},
                                                            {"min": 0.1, "max": 9.9, "label": '小雨', "color": "#87CEFA"}])
            ))
            tl.add(map_shape1, "{}h".format(h)) #将不同日期的数据加入到timeline中
        return tl
    timeline_map(data1).render("rainfalltoall_1.html")
    

    效果如下:

    在这里插入图片描述

    至此,天气数据分析可视化就完成啦~

    今天我们就到这里,明天继续努力!
    在这里插入图片描述
    若本篇内容对您有所帮助,请三连点赞,关注,收藏支持下。

    创作不易,白嫖不好,各位的支持和认可,就是我创作的最大动力,我们下篇文章见!

    Dragon少年 | 文

    如果本篇博客有任何错误,请批评指教,不胜感激 !

    展开全文
  • 用Python进行数据整理

    千次阅读 2018-01-14 13:39:24
    数据整理是在分析,可视化和在使用机器学习建立预测模型之前,进行数据收集,数据评估和数据整理的过程 【数据收集】 方法:1、网上直接下载数据源;2、用编程方法下载数据源;3、使用手头的文件 【数据评估】 ...
  • Excel教程:如何快速整理数据

    千次阅读 2019-07-02 14:53:59
    知道大家平时整理数据是使用什么样的方法,我经常需要整理一些网络数据,网络数据整理一直是个难题,导出的网络数据要不是单列的,要不就是有一些特殊符号,都需要整理后才能使用,这不,领导让小红把后套导出的...
  • 数据采集流程整理

    千次阅读 热门讨论 2014-01-01 21:31:35
    数据采集流程与反思。
  • 摘要:本文对机器学习的UCI数据集进行介绍,带你从UCI数据集官网出发一步步深入认识数据集,并就下载的原始数据详细讲解了不同类型的数据整理如何通过程序进行整理。为了方便使用,博文附上了包括数据整理及...
  • R语言中数据清洗、整理的方法

    万次阅读 多人点赞 2015-10-08 19:59:22
    用R语言做数据清理(详细教程) 数据的清理 如同列夫托尔斯泰所说的那样:“幸福的家庭都是相似的,不幸的家庭各有各的不幸”,糟糕的恶心的数据各有各的糟糕之处,好的数据集都是相似的。一...
  • 数据的都知道,阿里发明了数据中台,然后“台”这个概念就马上成为了国内大多数企业趋之若鹜的风口,真正实施后却发现台与数据平台、数据湖等项目大差不差,又有好多机构开始忙着拆台了,台虽然还没到人见...
  • 怎么做到ERP基础数据整理

    千次阅读 2014-10-31 14:32:16
    可见,ERP系统基础数据整理的重要性。  参与过ERP项目实施的人都应该知道,ERP项目实施能够成功,关键在于细节。有人这样说,ERP不难,只是很繁。这里所说的繁,指的就是整理ERP基础数据的过程。整理ERP基础数据...
  • 数据挖掘常用算法整理

    万次阅读 多人点赞 2016-08-21 08:22:12
     找工作时(IT行业),除了常见的软件开发以外,机器学习岗位也可以当作是一个选择,不少计算机方向的研究生都会接触这个,如果的研究方向是机器学习/数据挖掘之类,且又对其非常感兴趣的话,可以考虑考虑该岗位...
  • 数据分析与可视化内容整理

    千次阅读 2020-01-21 18:37:17
    数据分析是基于商业目的,有目的的进行收集、整理、加工和分析数据,提炼有价信息的一个过程。其过程概括起来主要包括:明确分析目的与框架、数据收集、数据处理、数据分析、数据展现和撰写报告等6个阶段。 1、明确...
  • 全网最全python爬虫+数据分析资源整理

    千次阅读 多人点赞 2021-04-29 14:08:36
    什么需要数据分析能力? 第一模块:数据分析基础篇 (16讲) 01丨数据分析全景图及修炼指南 02丨学习数据挖掘的最佳路径是什么? 03丨Python基础语法:开始的Python之旅 04丨Python科学计算:用NumPy快速处理...
  • Java基础问题整理

    万次阅读 多人点赞 2020-04-07 11:44:14
    备注:针对基本问题做一些基本的总结,不是详细解答!...4.HashMap1.7与HashMap1.8的区别,从数据结构上、Hash值的计算上、链表数据的插入方法、内部Entry类的实现上分析? 5.Hash1.7是基于数组...
  • 6、多线程编程中你知道哪些都是保证线程安全的 7、Volatile的底层实现是什么 8、线程池了解吗,说说工作原理 9、内存溢出说一下 10、栈溢出说一下 11、要实现一个OOM和栈溢出,怎么实现 12、说一下常用的垃圾回收...
  • 前言 数据源:腾讯新闻肺炎疫情 ...可以直接通过分析URL得到数据网址,并将这些数据存储为json文件。但是同样的过程,并不能在其他门户新闻网站上进行。因此,腾讯新闻是最容易抓取疫情数据的网站...
  • 你知道MySQL是如何处理千万级数据的吗?

    万次阅读 多人点赞 2020-08-10 21:10:11
    mysql 分表思路 一张一亿的订单表,...**主表插入之后返回一个 id,根据这个 id 和表的数量进行取模,余数是几就往哪张表插入数据。 **注意:**子表的 id 要与主表的 id 保持一致 以后只有插入操作会用到主表,
  • 大多数AI实验室、初创型AI公司在发展初期如果雇佣大量的人力进行数据标注,就不得不面临下面两种处境: 首先对公司的管理方面就是巨大的挑战,在研发产品的同时还得把大量精力放在如何管理大量标注人员身上。 其次...
  • 数据仓库项目管理面试题整理

    千次阅读 2011-08-20 18:37:09
    数据仓库项目管理面试题整理   搜了一下网络上都是一个主题一个网页,自己看了觉得不方便,所以整理到一起放上来方便自己看。 原文出自Jerome的BI博客,网址是...
  • 从数据中台到全链路数据生产力

    万次阅读 2020-11-12 18:15:35
    有必要再阐释一下什么叫全链路数据生产力平台,它跟其他的很多数据领域的技术如数据中台、BI等是什么关系。 一、全链路数据生产力 1979年,老邓画了一个圈,造就的一个信奉生产力的时代。虽然不排除某些企业逼格高...
  • 精心整理了7种常用数据分析方法(建议收藏)

    万次阅读 多人点赞 2019-11-08 08:30:00
    其实,这位朋友与很多小伙伴一样,做数据分析时,拿着手里的数据知道怎么分析、从什么维度分析。今天DataHunter数猎哥就来给大家分享7种最常用的数据分析方法,让轻松运用数据分析解决实际工作问题,提升核心...
  • 2019已经到来,是否在满意的公司?拿着理想的薪水? 目前全国正处于招聘的高峰期,如果有面试题能提示一下,可以提前做个准备,也可以看出自己的不足之处,面试能拿到offer的机会就大的多,下面就是一些常见的...
  • 海量数据面试题整理

    万次阅读 多人点赞 2012-06-01 11:41:23
    1、给定a、b两个文件,各存放50亿个url,每个url各占64字节,内存限制是4G,让找出a、b文件共同的url? 方案1:可以估计每个文件安的大小为50G×64=320G,远远大于内存限制的4G。所以不可能将其完全加载到内存...
  • 前言 2010年左右,还是在上学的时候,学过一门...如今,十年风云际会,大数据早已成了行业绕不开的话题,这其中我们或多或少会接触到很多新兴的概念,例如数据湖、数据中台等,通过一些碎片化的学习,也是大概知...
  • MySQL相关问题整理

    万次阅读 多人点赞 2020-04-07 11:47:29
    备注:针对基本问题做一些基本的总结,不是详细解答! 1.事务的基本要素 2.事务隔离级别(必考) ...7.查询在什么时候不走(预期的)索引(必考) 8.sql如何优化 9.explain是如何解析sql的 ...
  • 什么数据仓库?

    万次阅读 多人点赞 2019-04-24 19:44:14
    传统的数据库,存放的数据都是一些定制性数据较多,表是二维的,一张表可以有很多字段,字段一字排开,对应的数据就一行一行写入表,特点就是利用二维表表现多维关系。 但这种表现关系的上限和下限就定死了,...
  • 微服务系统数据一致性,都会了吗

    万次阅读 多人点赞 2021-09-17 23:11:34
    单体架构到分布式架构,巨石架构到微服务架构。系统之间的交互越来越复杂,系统间的数据交互量级也是指数级增长。作为一个系统,我们要保证逻辑的自洽和数据的自洽。 数据自洽有两方面要求: 抛开代码,数据...
  • mysql异常宕机故障数据恢复思路整理

    千次阅读 2016-03-31 16:37:36
    遇到问题不能慌,尤其是线上的环境,更不能紧张,心理素质对DBA来说也是一项挑战,可能的手一抖就会导致多少人无法正常使用业务,如果没有把握,请先把现场环境备份后再进行操作,避免数据的二次损坏,下面说...
  • 数字化革命,第四次科技革命,因计算机和电子数据的普及和推广而在各行各业发生的机械和模拟电路到... 通常第一步我们拿到数据,很多人非常着急的马上开始研究如何建模分析,实际上,一开始整理数据非常重要。数...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 311,687
精华内容 124,674
关键字:

从整理的数据中你知道了什么