Redis有哪几种数据结构？
 
● String——字符串
 String数据结构是简单的key-value类型，value不仅可以是String，也可以是数字（当数字类型用Long可以表示的时候encoding就是整型，其他都存储在sdshdr当做字符串）。
 
● Hash——字典
 在Memcached中，我们经常将一些结构化的信息打包成hashmap，在客户端序列化后存储为一个字符串的值（一般是JSON格式），比如用户的昵称、年龄、性别、积分等。
 
● List——列表
 List说白了就是链表（redis使用双端链表实现的List）
 
● Set——集合
 Set就是一个集合，集合的概念就是一堆不重复值的组合。利用Redis提供的Set数据结构，可以存储一些集合性的数据。
 
● Sorted Set——有序集合
 和Set相比，Sorted Set是将Set中的元素增加了一个权重参数score，使得集合中的元素能够按score进行有序排列，
 
● 带有权重的元素，比如一个游戏的用户得分排行榜
 
● 比较复杂的数据结构，一般用到的场景不算太多

分享一下我老师大神的人工智能教程！零基础，通俗易懂！http://blog.csdn.net/jiangjunshow

也欢迎大家转载本篇文章。分享知识，造福人民，实现我们中华民族伟大复兴！


                 
 

  影响空间规模的几种数据存储结构

  

   

   正文
   
            
   所谓数据存储结构，就是数据的元素与元素之间在计算机中的一种表示，它的目的是为了解决空间规模问题，或者是通过空间规模问题从而间接地解决时间规模问题。我们知道，随着输入的数据量越来越大，在有限的内存里，不能把这些数据完全的存下来，这就对数据存储结构和设计存储的算法提出了更高的要求。
   

   

          本文将介绍几种存储结构，分别为链式结构、树形结构、图结构以及矩阵结构。
   

   

   第一节 链式存储结构
   

   

          所谓链式存储结构，一般就是用一个头指针指向链表的第一个节点，如果你要增加新的存储元素时，只需在已有节点的后面插入新结点即可。
   

   

          链表通常有单链表、双链表、循环链表。在这，我只介绍单链表，双链表和循环链表只是单链表的拓展罢了。下图就是一个简单的单链表图示。
   

   

    
    

    

     单链表的类型描述如下代码：
     

     

      

       

        [cpp] 
        view plain
        copy
        print
        ?
       
      
      
typedef char DataType;  /***假设结点的数据域类型为字符***/  
typedef struct node{    /***结点类型定义***/  
    DataType data;      /***结点的数据域***/  
    struct node *next;  /***结点的指针域***/  
    }ListNode;  
    typedef ListNode *LinkList;  
    ListNode *p;  
    LinkList head;  
附注：   
    ① LinkList和ListNode *是不同名字的同一个指针类型（命名的不同是为了概念上更明确）  
    ② LinkList类型的指针变量head表示它是单链表的头指针  
    ③ ListNode *类型的指针变量p表示它是指向某一节点的指针  
     
     

      

       

        [cpp] 
        view plain
         copy
         print
        ?
       
      
      
typedef char DataType;  /***假设结点的数据域类型为字符***/  
typedef struct node{    /***结点类型定义***/  
    DataType data;      /***结点的数据域***/  
    struct node *next;  /***结点的指针域***/  
    }ListNode;  
    typedef ListNode *LinkList;  
    ListNode *p;  
    LinkList head;  
附注：   
    ① LinkList和ListNode *是不同名字的同一个指针类型（命名的不同是为了概念上更明确）  
    ② LinkList类型的指针变量head表示它是单链表的头指针  
    ③ ListNode *类型的指针变量p表示它是指向某一节点的指针  
     
typedef char DataType; /***假设结点的数据域类型为字符***/typedef struct node{ /***结点类型定义***/ DataType data;  /***结点的数据域***/ struct node *next; /***结点的指针域***/ }ListNode; typedef ListNode *LinkList; ListNode *p; LinkList head;附注：  ① LinkList和ListNode *是不同名字的同一个指针类型（命名的不同是为了概念上更明确） ② LinkList类型的指针变量head表示它是单链表的头指针 ③ ListNode *类型的指针变量p表示它是指向某一节点的指针
     

     下面我们来看单链表的操作：创建节点、增加节点、删除节点、查询、修改。
     

     

     1.创建节点：声明一个节点并为其申请一段内存空间，此节点有数据域和指针域。
     

     

      

       

        [cpp] 
        view plain
        copy
        print
        ?
       
      
      
node = (struct List *)malloc(sizeof(struct List));  
     
     

      

       

        [cpp] 
        view plain
         copy
         print
        ?
       
      
      
node = (struct List *)malloc(sizeof(struct List));  
     
node = (struct List *)malloc(sizeof(struct List));
     

     2.增加节点：插入节点，分为头插入、尾插入和非头尾插入。
     
    
     ①. 在表头插入节点，
     如图
     

     

      
      

      

       插入头节点的代码如下：
       

      
     
     

      

       

        [cpp] 
        view plain
        copy
        print
        ?
       
      
      
if(p == head)   /***其中p为链表中的某一节点***/  
{  
    struct list *s = NULL;  
    s = (struct list *)malloc(sizeof(struct list)); /***申请空间***/  
    s->DataNumber = data;    /***为节点s的数据域赋值***/  
  
    /***将节点s插入表头***/  
    s->next = p;  
    head = s;  
}  
     
     

      

       

        [cpp] 
        view plain
         copy
         print
        ?
       
      
      
if(p == head)   /***其中p为链表中的某一节点***/  
{  
    struct list *s = NULL;  
    s = (struct list *)malloc(sizeof(struct list)); /***申请空间***/  
    s->DataNumber = data;    /***为节点s的数据域赋值***/  
  
    /***将节点s插入表头***/  
    s->next = p;  
    head = s;  
}  
     
if(p == head) /***其中p为链表中的某一节点***/{ struct list *s = NULL; s = (struct list *)malloc(sizeof(struct list)); /***申请空间***/ s->DataNumber = data; /***为节点s的数据域赋值***/ /***将节点s插入表头***/ s->next = p; head = s;}
     

       ②. 在表尾插入节点，
     如图
     

     

      
      

      

       插入尾节点的代码如下：
       

       

        

         

          [cpp] 
          view plain
          copy
          print
          ?
         
        
        
if(p->next == NULL)  /***其中p为链表中的某一节点***/  
{  
    struct list *s = NULL;  
    s = (struct list *)malloc(sizeof(struct list)); /***申请空间***/  
    s->DataNumber = data;    /***为节点s的数据域赋值***/  
      
    /***将节点s插入表尾***/  
    p->next = s;  
    s->next = NULL;  
}  
       
       

        

         

          [cpp] 
          view plain
           copy
           print
          ?
         
        
        
if(p->next == NULL)  /***其中p为链表中的某一节点***/  
{  
    struct list *s = NULL;  
    s = (struct list *)malloc(sizeof(struct list)); /***申请空间***/  
    s->DataNumber = data;    /***为节点s的数据域赋值***/  
      
    /***将节点s插入表尾***/  
    p->next = s;  
    s->next = NULL;  
}  
       
if(p->next == NULL) /***其中p为链表中的某一节点***/{ struct list *s = NULL; s = (struct list *)malloc(sizeof(struct list)); /***申请空间***/ s->DataNumber = data; /***为节点s的数据域赋值***/  /***将节点s插入表尾***/ p->next = s; s->next = NULL;}
       
 
        ③. 在表中插入非头尾节点，
       如图
       

       

        
        

        

         插入非头尾节点的代码如下：
         

         

          

           

            [cpp] 
            view plain
            copy
            print
            ?
           
          
          
struct list *s = NULL;  
s = (struct list *)malloc(sizeof(struct list)); /***申请空间***/  
s->DataNumber = data;    /***为节点s的数据域赋值***/  
  
/***将节点s插入表中***/  
s->next = p; /***其中p为链表中的某一节点***/  
q->next = s; /***其中q为链表中p节点的前一个节点***/  
         
         

          

           

            [cpp] 
            view plain
             copy
             print
            ?
           
          
          
struct list *s = NULL;  
s = (struct list *)malloc(sizeof(struct list)); /***申请空间***/  
s->DataNumber = data;    /***为节点s的数据域赋值***/  
  
/***将节点s插入表中***/  
s->next = p; /***其中p为链表中的某一节点***/  
q->next = s; /***其中q为链表中p节点的前一个节点***/  
         
struct list *s = NULL;s = (struct list *)malloc(sizeof(struct list)); /***申请空间***/s->DataNumber = data; /***为节点s的数据域赋值***//***将节点s插入表中***/s->next = p; /***其中p为链表中的某一节点***/q->next = s; /***其中q为链表中p节点的前一个节点***/
         
3.删除节点：分为删除头结点，删除尾节点，删除头尾节点。
         

         

         ①. 删除表头结点，
         如图
         

         

          
          

          

           删除头结点的代码如下：
           

           

            

             

              [cpp] 
              view plain
              copy
              print
              ?
             
            
            
if(p == head)   /***p指向链表中的某一节点***/  
{  
    head = p->next;  
}  
           
           

            

             

              [cpp] 
              view plain
               copy
               print
              ?
             
            
            
if(p == head)   /***p指向链表中的某一节点***/  
{  
    head = p->next;  
}  
           
if(p == head) /***p指向链表中的某一节点***/{ head = p->next;}
           

           ②. 删除表尾节点，如图
           

           

            
            

            

             
附注说明：上图中删完尾节点之后，新链表的尾节点下标应为n-1。不过由于作图时只做了尾节点，故用图中的n2节点代替。

             
删除尾节点的代码如下：
             

             

              

               

                [cpp] 
                view plain
                copy
                print
                ?
               
              
              
if(p->next == NULL)  /***p指向链表中的某一节点***/  
{  
    q->next = NULL;  /***q指向链表中的p节点的前一节点**/  
}  
             
             

              

               

                [cpp] 
                view plain
                 copy
                 print
                ?
               
              
              
if(p->next == NULL)  /***p指向链表中的某一节点***/  
{  
    q->next = NULL;  /***q指向链表中的p节点的前一节点**/  
}  
             
if(p->next == NULL) /***p指向链表中的某一节点***/{ q->next = NULL; /***q指向链表中的p节点的前一节点**/}
             

             ③. 删除非头尾节点，如图
             

             

             
删除非头尾节点的代码如下：
             

             

              

               

                [cpp] 
                view plain
                copy
                print
                ?
               
              
              
q->next = p->next;    /***p指向链表中的某一节点，q指向链表中的p节点的前一节点***/  
             
             

              

               

                [cpp] 
                view plain
                 copy
                 print
                ?
               
              
              
q->next = p->next;    /***p指向链表中的某一节点，q指向链表中的p节点的前一节点***/  
             
q->next = p->next; /***p指向链表中的某一节点，q指向链表中的p节点的前一节点***/
             

             4.查询节点：在链表中找到你想要找的那个节点。此操作是根据数据域的内容来完成的。查询只能从表头开始，当要找的节点的数据域内容与当前不相符时，只需让当前节点指向下一结点即可，如此这样，直到找到那个节点。
             

             
附注：此操作就不在这用图和代码说明了。

             


             
5.修改节点：修改某个节点数据域的内容。首先查询到这个节点，然后对这个节点数据域的内容进行修改。
附注：同上
             


             
       ok，链表的几种操作介绍完了，接下来我们来总结一下链表的几个特点。
             
       链式存储结构的特点：
              1.易插入，易删除。不用移动节点，只需改变节点中指针的指向。
              2.查询速度慢：每进行一次查询，都要从表头开始，速度慢，效率低。
             
扩展阅读
链表：http://public.whut.edu.cn/comptsci/web/data/512.htm
             


             
第二节 树形存储结构
             
       所谓树形存储结构，就是数据元素与元素之间存在着一对多关系的数据结构。在树形存储结构中，树的根节点没有前驱结点，其余的每个节点有且只有一个前驱结点，除叶子结点没有后续节点外，其他节点的后续节点可以有一个或者多个。
             
如下图就是一棵简单的树形结构：
             

             
       说到树形结构，我们最先想到的就是二叉树。我们常常利用二叉树这种结构来解决一些算法方面的问题，比如堆排序、二分检索等。所以在树形结构这节我只重点详解二叉树结构。那么二叉树到底是怎样的呢？如下图就是一颗简单的二叉树：
             

             
附注：有关树的概念以及一些性质在此不做解释，有意者请到百科一览。
             


             
二叉树的类型描述如下：
             

             

              

               

                [cpp] 
                view plain
                copy
                print
                ?
               
              
              
typedef struct tree  
{  
    char data;  
    struct tree * lchild, * rchild; /***左右孩子指针***/  
}tree;  
             
             

              

               

                [cpp] 
                view plain
                 copy
                 print
                ?
               
              
              
typedef struct tree  
{  
    char data;  
    struct tree * lchild, * rchild; /***左右孩子指针***/  
}tree;  
             
typedef struct tree{ char data; struct tree * lchild, * rchild; /***左右孩子指针***/}tree;
             

             二叉树的操作：创建节二叉树，创建节点，遍历二叉树，求二叉树的深度。
             

             
1.创建二叉树：声明一棵树并为其申请存储空间。
             

             

              

               

                [cpp] 
                view plain
                copy
                print
                ?
               
              
              
struct tree * T = NULL;  
T = (struct tree *)malloc(sizeof(struct tree));  
             
             

              

               

                [cpp] 
                view plain
                 copy
                 print
                ?
               
              
              
struct tree * T = NULL;  
T = (struct tree *)malloc(sizeof(struct tree));  
             
struct tree * T = NULL;T = (struct tree *)malloc(sizeof(struct tree));
             

             2.创建节点：除根节点之外，二叉树的节点有左右节点之分。
             

             

             
创建节点的代码如下：
             

             

              

               

                [cpp] 
                view plain
                copy
                print
                ?
               
              
              
struct tree * createTree()  
{  
    char NodeData;  
    scanf(" %c", &NodeData);  
    if(NodeData == '#')  
        return NULL;  
    else  
    {  
        struct tree * T = NULL;  
        T = (struct tree *)malloc(sizeof(struct tree));  
        T->data = NodeData;  
        T->lchild = createTree();  
        T->rchild = createTree();  
        return T;  
    }  
}  
             
             

              

               

                [cpp] 
                view plain
                 copy
                 print
                ?
               
              
              
struct tree * createTree()  
{  
    char NodeData;  
    scanf(" %c", &NodeData);  
    if(NodeData == '#')  
        return NULL;  
    else  
    {  
        struct tree * T = NULL;  
        T = (struct tree *)malloc(sizeof(struct tree));  
        T->data = NodeData;  
        T->lchild = createTree();  
        T->rchild = createTree();  
        return T;  
    }  
}  
             
struct tree * createTree(){ char NodeData; scanf(" %c", &NodeData); if(NodeData == '#')  return NULL; else {  struct tree * T = NULL;  T = (struct tree *)malloc(sizeof(struct tree));  T->data = NodeData;  T->lchild = createTree();  T->rchild = createTree();  return T; }}
             

             3.遍历二叉树：分为先序遍历、中序遍历、后续遍历。
             

             
    ①.先序遍历：若二叉树非空，则依次执行如下操作：
                    (1) 访问根结点；
                    (2) 遍历左子树；
                    (3) 遍历右子树。
             
如图：

             

             
先序遍历的代码如下：
             

             

              

               

                [cpp] 
                view plain
                copy
                print
                ?
               
              
              
void PreTravser(struct tree * T)  
{  
    if(T == NULL)  
        return;  
    else  
    {  
        printf("%c",T->data);  
        PreTravser(T->lchild);  
        PreTravser(T->rchild);  
    }  
}  
             
             

              

               

                [cpp] 
                view plain
                 copy
                 print
                ?
               
              
              
void PreTravser(struct tree * T)  
{  
    if(T == NULL)  
        return;  
    else  
    {  
        printf("%c",T->data);  
        PreTravser(T->lchild);  
        PreTravser(T->rchild);  
    }  
}  
             
void PreTravser(struct tree * T){ if(T == NULL)  return; else {  printf("%c",T->data);  PreTravser(T->lchild);  PreTravser(T->rchild); }}
             

             ②.中序遍历：若二叉树非空，则依次执行如下操作：
                 (1)遍历左子树；
                 (2)访问根结点；
                 (3)遍历右子树。
如图：

             

             

             
中序遍历的代码如下：
             

             

              

               

                [cpp] 
                view plain
                copy
                print
                ?
               
              
              
void MidTravser(struct tree * T)  
{  
    if(!T)  
    {  
        return;  
    }  
    else  
    {  
        MidTravser(T->lchild);  
        printf("%c",T->data);  
        MidTravser(T->rchild);  
    }  
}  
             
             

              

               

                [cpp] 
                view plain
                 copy
                 print
                ?
               
              
              
void MidTravser(struct tree * T)  
{  
    if(!T)  
    {  
        return;  
    }  
    else  
    {  
        MidTravser(T->lchild);  
        printf("%c",T->data);  
        MidTravser(T->rchild);  
    }  
}  
             
void MidTravser(struct tree * T){ if(!T) {  return; } else {  MidTravser(T->lchild);  printf("%c",T->data);  MidTravser(T->rchild); }}
             

             ③.后续遍历：若二叉树非空，则依次执行如下操作：
                 (1)遍历左子树；
                 (2)遍历右子树；
                 (3)访问根结点。
             

             如图：
             

             

              

               
               

               

                后续遍历的代码如下：
                

                

                 

                  

                   [cpp] 
                   view plain
                   copy
                   print
                   ?
                  
                 
                 
void PostTravser(struct tree * T)  
{  
    if(!T)  
        return;  
    else  
    {  
        PostTravser(T->lchild);  
        PostTravser(T->rchild);  
        printf("%c->",T->data);  
    }  
}  
                
                

                 

                  

                   [cpp] 
                   view plain
                    copy
                    print
                   ?
                  
                 
                 
void PostTravser(struct tree * T)  
{  
    if(!T)  
        return;  
    else  
    {  
        PostTravser(T->lchild);  
        PostTravser(T->rchild);  
        printf("%c->",T->data);  
    }  
}  
                
void PostTravser(struct tree * T){ if(!T)  return; else {  PostTravser(T->lchild);  PostTravser(T->rchild);  printf("%c->",T->data); }}
                

                4.求二叉树的深度：树中所有结点层次的最大值，也称高度。
                

                二叉树的深度表示如下图：
                

                

                 
                 

                 

                  求二叉树深度的代码如下：
                  

                  

                   

                    

                     [cpp] 
                     view plain
                     copy
                     print
                     ?
                    
                   
                   
int treeDeepth(struct tree * T)  
{  
    int i, j;  
    if(!T)  
        return 0;  
    else  
    {  
        if(T->lchild)  
            i = treeDeepth(T->lchild);  
        else  
            i = 0;  
          
        if(T->rchild)  
            j = treeDeepth(T->rchild);  
        else  
            j = 0;  
    }  
    return i > j? i+1:j+1;   
}  
                  
                  

                   

                    

                     [cpp] 
                     view plain
                      copy
                      print
                     ?
                    
                   
                   
int treeDeepth(struct tree * T)  
{  
    int i, j;  
    if(!T)  
        return 0;  
    else  
    {  
        if(T->lchild)  
            i = treeDeepth(T->lchild);  
        else  
            i = 0;  
          
        if(T->rchild)  
            j = treeDeepth(T->rchild);  
        else  
            j = 0;  
    }  
    return i > j? i+1:j+1;   
}  
                  
int treeDeepth(struct tree * T){ int i, j; if(!T)  return 0; else {  if(T->lchild)   i = treeDeepth(T->lchild);  else   i = 0;    if(T->rchild)   j = treeDeepth(T->rchild);  else   j = 0; } return i > j? i+1:j+1; }
                  

                  好了，二叉树的几种操作介绍完了。

拓展阅读
二叉树：http://student.zjzk.cn/course_ware/data_structure/web/DOWNLOAD/%CA%FD%BE%DD%BD%E1%B9%B9%D3%EB%CB%E3%B7%A82.htm
赫夫曼编码：http://blog.csdn.net/fengchaokobe/article/details/6969217

第三节 图型存储结构
       所谓图形结构，就是数据元素与元素之间的关系是任意的，任意两个元素之间均可相关，即每个节点可能有多个前驱结点和多个后继结点，因此图形结构的存储一般是采用链接的方式。图分为有向图和无向图两种结构，如下图

                  

                   
                   

                   
                   

                   

                           通过图，我们可以判断两个点之间是不是具有连通性；通过图，我们还可以计算两个点之间的最小距离是多少；通过图，我们还可以根据不同的要求，寻找不同的合适路径。

1.图的结构有好几种，在实际应用中需根据具体的情况选择合适的结点结构和表结构。常用的有数组结构、邻接表。
   ①.数组结构
   数组结构的类型描述如下：

                    

                     

                      

                       [cpp] 
                       view plain
                       copy
                       print
                       ?
                      
                     
                     
typedef char VertexType;    /***顶点类型***/  
typedef int EdgeType;   /***边权值类型***/  
#define maxvex 100  /***顶点的最大个数***/  
  
typedef struct  
{  
    VertexType vexs[maxvex];    /***顶点个数***/  
    EdgeType arc[maxvex][maxvex];   /***两顶点构成边的权值***/  
}Mgraph;  
                    
                    

                     

                      

                       [cpp] 
                       view plain
                        copy
                        print
                       ?
                      
                     
                     
typedef char VertexType;    /***顶点类型***/  
typedef int EdgeType;   /***边权值类型***/  
#define maxvex 100  /***顶点的最大个数***/  
  
typedef struct  
{  
    VertexType vexs[maxvex];    /***顶点个数***/  
    EdgeType arc[maxvex][maxvex];   /***两顶点构成边的权值***/  
}Mgraph;  
                    
typedef char VertexType; /***顶点类型***/typedef int EdgeType; /***边权值类型***/#define maxvex 100 /***顶点的最大个数***/typedef struct{ VertexType vexs[maxvex]; /***顶点个数***/ EdgeType arc[maxvex][maxvex]; /***两顶点构成边的权值***/}Mgraph;附注：当前图为无向图时，图中某两个顶点VA和VB构成一条边时，其权值可表示为EdgeType arc[VA][VB]；当前图为有向图时，图中某两个顶点VA和VB构成一条边时，并且是由VA指向VB，其权值可表示为EdgeType arc[VA][VB]，如果是由VB指向VA，其权值可表示为EdgeType arc[VB][VA]。
                    

                    
   ②.邻接表
                    
   邻接表的类型描述如下：
                    

                    

                     

                      

                       [cpp] 
                       view plain
                       copy
                       print
                       ?
                      
                     
                     
typedef char VertexType;   // 顶点类型  
typedef int EdgeType;     //边权值类型  
  
typedef struct EdgeNode  //边表节点  
{  
   int adjvex;              //邻接点域，存储该顶点对应的下标  
   EdgeType weight;         //用于存储权值  
   struct EdgeNode *next;   //链域,指向下一个邻接点  
}EdgeNode;  
  
typedef struct VertexNode   //顶点表节点  
{  
   VertexType data;       //顶点域，存储顶点信息  
   EdgeNode * firstedge;  //边表头指针   
}VertexNode,AdjList[MAXVEX];  
  
typedef struct  
{  
    AdjList adjList;  
    int numVertexes,numEdges;   //图当前顶点数和边数  
}GraphAdjList;  
                    
                    

                     

                      

                       [cpp] 
                       view plain
                        copy
                        print
                       ?
                      
                     
                     
typedef char VertexType;   // 顶点类型  
typedef int EdgeType;     //边权值类型  
  
typedef struct EdgeNode  //边表节点  
{  
   int adjvex;              //邻接点域，存储该顶点对应的下标  
   EdgeType weight;         //用于存储权值  
   struct EdgeNode *next;   //链域,指向下一个邻接点  
}EdgeNode;  
  
typedef struct VertexNode   //顶点表节点  
{  
   VertexType data;       //顶点域，存储顶点信息  
   EdgeNode * firstedge;  //边表头指针  
}VertexNode,AdjList[MAXVEX];  
  
typedef struct  
{  
    AdjList adjList;  
    int numVertexes,numEdges;   //图当前顶点数和边数  
}GraphAdjList;  
                    
typedef char VertexType;   // 顶点类型typedef int EdgeType;     //边权值类型typedef struct EdgeNode  //边表节点{   int adjvex;              //邻接点域，存储该顶点对应的下标   EdgeType weight;         //用于存储权值   struct EdgeNode *next;   //链域,指向下一个邻接点}EdgeNode;typedef struct VertexNode   //顶点表节点{   VertexType data;       //顶点域，存储顶点信息   EdgeNode * firstedge;  //边表头指针}VertexNode,AdjList[MAXVEX];typedef struct{    AdjList adjList;    int numVertexes,numEdges;   //图当前顶点数和边数}GraphAdjList;
                    
2.图的遍历：从图中的某一节点出发访问图中的其余节点，且使每一节点仅被访问一次。图的遍历算法是求解图的连通性问题、拓扑排序和求路径等算法的基础。图的遍历分为深度优先遍历和广度优先遍历，且它们对无向图和有向图均适用。
                    

                    
   ①. 深度优先遍历
                    
   定义说明：假设给定图G的初态是所有顶点均未曾访问过。在G中任选一顶点V为初始出发点，则深度优先遍历可定义如下：首先访问出发点V，并将其标记为已访问过；然后依次从V出发搜索v的每个邻接点W。若W未曾访问过，则以W为新的出发点继续进行深度优先遍历，直至图中所有和源点V有路径相通的顶点(亦称为从源点可达的顶点)均已被访问为止。若此时图中仍有未访问的顶点，则另选一个尚未访问的顶点作为新的源点重复上述过程，直至图中所有顶点均已被访问为止。
                    

                    
深度遍历过程如下图：
                    

                    

                     
                     

                     

                      

                      ②. 广度优先遍历
   定义说明：假设从图中某顶点V出发，在访问了V之后一次访问V的各个未曾访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问，直至图中所有已被访问的顶点的邻接点都被访问到。若此时图中还有顶点未被访问，则另选图中一个未曾被访问的顶点作为起始点，重复上述过程，直至图中所有顶点都被访问到为止。换句话说，广度优先遍历图的过程是以V为起点，由近至远，依次访问和V有路径相同且路径长度为1,2，...的顶点。
                      

                      

                      广度遍历过程如下图：
                      

                      

                       
                       

                       

                        

                        扩展阅读
最小生成树：Prim算法，Kruskal算法
最短路径：Dijkstra算法，Floyd算法
                        

                        

                        第四节 结束语
                        

                               想想，写写，画画......
                        
原文地址：
                        http://blog.csdn.net/fengchaokobe/article/details/7416547
                        

                        
                       
                      
                     
                    
                   
                  
                 
                
               
              
             
            
           
          
         
        
       
      
     
    
   
  
 
            



给我老师的人工智能教程打call！http://blog.csdn.net/jiangjunshow

 

数据结构大致包含以下几种存储结构：
 线性表，还可细分为顺序表、链表、栈和队列；
 树结构，包括普通树，二叉树，线索二叉树等；
 图存储结构；
 线性表
 线性表结构存储的数据往往是可以依次排列的，就像小朋友手拉手，每位学生的前面和后面都仅有一个小朋友和他拉手，具备这种“一对一”关系的数据就可以使用线性表来存储。
 
例如，存储类似 {1,3,5,7,9} 这样的数据时，各元素依次排列，每个元素的前面和后边有且仅有一个元素与之相邻（除首元素和尾元素），因此可以使用线性表存储。
 
线性表并不是一种具体的存储结构，它包含顺序存储结构和链式存储结构，是顺序表和链表的统称。
 顺序表
 顺序表，简单地理解，就是常用的数组，只是换了个名字而已，例如使用顺序表存储 {1,3,5,7,9}，如图 1 所示：
 
顺序表结构
 图 1 顺序表结构
 由于顺序表结构的底层实现借助的就是数组，因此对于初学者来说，可以把顺序表完全等价为数组，但实则不是这样。数据结构是研究数据存储方式的一门学科，它囊括的都是各种存储结构，而数组只是各种编程语言中的基本数据类型，并不属于数据结构的范畴。
 
 顺序表结构
 链表
 我们知道，使用顺序表（底层实现靠数组）时，需要提前申请一定大小的存储空间，这块存储空间的物理地址是连续的，如图 1 所示。
 
链表则完全不同，使用链表存储数据时，是随用随申请，因此数据的存储位置是相互分离的，换句话说，数据的存储位置是随机的。
 
为了给各个数据块建立“依次排列”的关系，链表给各数据块增设一个指针，每个数据块的指针都指向下一个数据块（最后一个数据块的指针指向 NULL），就如同一个个小学生都伸手去拉住下一个小学生的手，这样，看似毫无关系的数据块就建立了“依次排列”的关系，也就形成了链表，如图 2 所示：
 
链表结构
 图 2 链表结构
 
 
栈和队列
 栈和队列隶属于线性表，是特殊的线性表，因为它们对线性表中元素的进出做了明确的要求。
 
栈中的元素只能从线性表的一端进出（另一端封死），且要遵循“先入后出”的原则，即先进栈的元素后出栈。
 
栈结构示意图
 图 3 栈结构示意图
 
 
栈结构如图 3 所示，像一个木桶，栈中含有 3 个元素，分别是 A、B 和 C，从在栈中的状态可以看出 A 最先进的栈，然后 B 进栈，最后 C 进栈。根据“先进后出”的原则，3 个元素出栈的顺序应该是：C 最先出栈，然后 B 出栈，最后才是 A 出栈。
 
队列中的元素只能从线性表的一端进，从另一端出，且要遵循“先入先出”的特点，即先进队列的元素也要先出队列。
 
队列结构示意图
 图 4 队列结构示意图
 
队列结构如图 4 所示，队列中有 3 个元素，分别是 A、B 和 C，从在队列中的状态可以看出是 A 先进队列，然后 B 进，最后 C 进。根据“先进先出”的原则，3 个元素出队列的顺序应该是 A 最先出队列，然后 B 出，最后 C 出。
 树存储结构
 树存储结构适合存储具有“一对多”关系的数据。
 
树存储结构示意图
 图 5 树存储结构示意图
 
 
如图 5 所示，其中张平只有一个父亲，但他却有两（多）个孩子，这就是“一对多”的关系，满足这种关系的数据可以使用树存储结构。
 图存储结构
 图存储结构适合存储具有“多对多”关系的数据。
 
图存储结构示意图
 图 6 图存储结构示意图
 
如图 6 所示，从 V1 可以到达 V2、V3、V4，同样，从 V2、V3、V4 也可以到达 V1，这就是“多对多”的关系，满足这种关系的数据可以使用图存储结构。

今天参加一个小考试，就是考的这一题，我竟然忘得很干净，拿出来数据结构书，再看一下。
 
数据结构----书上给的概念是：相互之间存在一种或多种特定关系的数据元素的集合。简单的就是：数据及数据之间的关系。
 
那么，到底有哪几种基本结构呢？
 
1，集合：集合中的每一个数据元素都是相互独立的，这跟数学里的集合是一致的。（还记得数学里集合的三要素呢，无序性，互异性，确定性）
 
2，线性结构：数据之间是一对一的关系，我感觉就像是有一条线把数据元素穿了起来。不知道这样子理解对不对·····
 
3，树形结构：数据之间存在一对多的关系。是不是像一个大家庭，我们都有一个祖宗，然后生啊生啊，就有了很多下一代，下一代又生啊生，就又有很多下下一代······
 
4，图状结构或者网状结构：数据元素间是多对多的关系。这像什么呢？同学之间的关系，大家都是互相交织的感觉。怎么感觉网状结构这么纠结呢？？
 
第一次写博客呢？觉得总结得不自然····看来以后要常写啊！