精华内容
下载资源
问答
  • 的储存方式 图是一个好东西,能够使用图来模拟或解决很多生活问题,同时在各大比赛上都少不了关于图的问题.图是关系与顶点与边的,那么我们该如何来存入图的信息呢? 1. 直接存边 我们开一个数组,数组里每个元素是...

    title: 图的几种储存方式
    author: BbiHH
    tags:

    • ACM_汇总
    • ‘’
      categories:
    • 图的存储方式
      toc: true
      date: 2019-08-07 17:15:00

    (原创)

    图的储存方式

    图是一个好东西,能够使用图来模拟或解决很多生活问题,同时在各大比赛上都少不了有关于图的问题.图是关系与顶点与边的,那么我们该如何来存入图的信息呢?

    1. 直接存边

    我们开一个数组,数组里每个元素是图的一条边。其中存的每一条边都包含这些信息:顶点 v 与 u , 边的权值 .
    这就用到结构体数组 . 对于无向图 , 只需要存两个 顶点 , 有向图的话需要区分 起点 终点 .

    // 直接存边 
    struct edge{
        int start; // 起点
        int to;    // 终点
        int cost;  // 花费(权值)
    }G[MAXN];
    

    这样做有个缺点 , 每次想要知道两个点之间是否有连边(或者说一条边是否存在),都需要遍历整个数组进行查找.而且如果没有进行排序的话 , 还不能使用二分查找( O(log n) ) , 只能顺序查找 ( O(n) ) , 对于需要多次查找的情况 , 显然是不合适的 . 但在使用 Kruskal 算法求 最小生成树 的时候能用到这种方法 .

    2.邻接矩阵

    邻接矩阵的英文名是 adjacency matrix。它的形式是bool adj[n][n] , 这里需要存 n 个节点 , adj[x][y] 表示 节点x节点y 之间是否有边.如果边有权值的话 , 用 int adj[n][n] 直接吧边权存进去 .
    无向图需要 xy 有边则需要存 adj[x][y]adj[y][x] 表示有双向导通 , 有向图则 x -> y 则存 adj[x][y] 就行了 .

    #include<bits/stdc++.h>
    
    using namespace std;
    
    int adj[MAXN][MAXN],n,m;  // n 为节点数 , m 为边数
    
    int main()
    {
        scanf("%d %d",&n,&m);
        for(int i=1;i<=m;i++)
        {
            int x,y,v;
            scanf("%d %d %d",&x,&y,&v);
            adj[x][y]=adj[y][x]=v;//向x,y间添加一个权值为v的边(无向)
            //有向图为adj[x][y]=v;
        }
        return 0;
    }
    

    它的优点是 , 在查询两点间是否有边时 , 时间复杂度为 O(1) , 但是缺点是它存边却是极占内存, 它的空间(内存)复杂度是 O(n^2) . 对于一个稀疏的图(边相对于点数的平方比较少)来说,用邻接矩阵来存的话,成本偏高 .
    如果n*m超过3×1e7,内存就超过128MB了,所以当看到类似的 n,m=<1e4时 就不要用邻接矩阵 , 需要考虑其他的存储方式 .

    邻接表

    邻接表英文名是 adjacency list . 邻接表是链状的 ,它实际上是一个离散化的邻接矩阵. edge[i] 代表第 i 号节点 , .to[] 表示到与别的节点联通的路径 ,.v[ ]是i到 edge[i].to[j] 号节点的权值 , .len 用来标记一共有几个联通 i 号节点的边 (也称节点i出度)

    #include<bits/stdc++.h>
    using namespace std;
    
    struct node
    {
        int to[1010];  //存储与当前节点相接的节点
        int v[1010];   //两节点间的边的权值
        int olen;      //出度
        //int ilen;      //入度 
    }edge[1010];
    int n,m;
    int main()
    {
        scanf("%d %d",&n,&m);
        for(int i=1;i<=m;i++)
        {
            int x,y,v1;
            scanf("%d %d %d",&x,&y,&v1);
            edge[x].len++;edge[y].len++;
            edge[x].to[edge[x].len]=y;edge[y].to[edge[x].len]=x;
            edge[x].v[edge[x].len]=edge[y].to[edge[x].len]=v1;//向x,y间添加一个权值为v的边(无向)
            /*有向图为
            edge[x].len++;
            edge[x].to[edge[x].len]=y;
            edge[x].v[edge[x].len]=v1;
            */
        }
        return 0;
    }
    
    展开全文
  • 常量池在java用于保存在编译期已确定的,已编译的class文件中的一份数据。它包括了关于类,方法,接口等中的常量,也包括字符串常量,如...在java中创建并初始化一个String对象,最常见的有两种方式 (1)String st

    常量池在java用于保存在编译期已确定的,已编译的class文件中的一份数据。它包括了关于类,方法,接口等中的常量,也包括字符串常量,如String s = "java"这种申明方式;当然也可扩充,执行器产生的常量也会放入常量池,故认为常量池是JVM的一块特殊的内存空间。

    一、字符串的创建与初始化

    java中创建并初始化一个String对象,最常见的有两种方式

    (1)String str 1= “hello”

    JVM会先去字符串池中找有没有"hello",有的话就把str1指向常量池中的"hello"(也就是获取对hello的引用没有就会先在创建一个字符串对象并将其放入到字符串常量池,再让str1指向常量池中的"hello" 

    hello放在常量区中,在编译时产生

    String str 1= “hello”创建了几个对象?

    创建时常量池中没有相同字符串则1个否则0个。

    (2)String str1 = new String(“hello”)

          new String(“hello”)此语句等价于“abc”和new String()两个操作。

    如果在字符串常量池中不存在“hello”字符串,创建一个字符串常量“hello,并将其添加到字符串常量池中;若存在,则不创建;

    new String()会在堆里创建一个新的对象。

    str1指向堆中创建的对象

    String str1 = new String(“hello”)创建了几个对象?

    创建时常量池中没有相同字符串则2个否则1


     常见面试题:

    (1)字符串的创建与存储问题

    	      public static void main(String[] args)
    <span style="white-space:pre">	</span>    {
    		String s1 = "abc";//常量池中没有"abc",创建字符串常量"abc"biang放入常量池,让s1指向常量池中的"abc"
    		String s2 = "abc";//常量池中已经存在"abc",直接让s2指向常量池中的"abc",s1和s2指向常量池中的同一个对象
    		System.out.println(s1 == s2);//true  “==“对你是否指向同一个对象,输出true
    		System.out.println(s1.equals(s2));//true  equals方法对比的是指向的对象中的字符串内容是否相同
    		
    		String s3 = new String("abc");//常量池中已经存在"abc",运行时在堆中生成一个字符串对象,s3指向堆中的对象
    		String s4 =  new String("abc");//常量池中已经存在"abc",运行时在堆中新生成生成一个字符串对象,s4指向堆中的对象
    		System.out.println(s3 == s4);//false  s3、s4指向对堆中不同的字符串对象
    		System.out.println(s3.equals(s4));//true 指向的对象中的字符串内容相同
    		
    		System.out.println(s1 == s3);// false s1是指向字符串常量区 s3指向的是堆区
    		System.out.println(s1.equals(s3));//true 指向的对象中的字符串内容相同
    		
    	  }


    内存空间如下:



    (2)字符串的拼接

      1)

    	        String str1 = "aaa";  
    		String str2 = "bbb";  
    		String str3 = "aaabbb";  
    		  
    		String str4 = "aaa" + "bbb";//两个字面字符串常量直接相加在编译时就str4确定为aaabbb,不会产生新的字符串对象  
    		System.out.println(str3 == str4);//true  str4与str3都是指向aaabbb
    		  
    		str4 = str1 + "bbb";//会产生新的字符串对象  
    		System.out.println(str3 == str4);//false  
    		  
    		str4 = str1 + str2;//会产生新的字符串对象  
    		System.out.println(str3 == str4);//false 
    		 
    		/*
    		 * 使用“+”连接的两个字符串本身就是字面常量字符串时,如果池中存在这样连接后的字符串,
    		 * 则是不会重新创建对象,而是直接引用池中的字符串对象;如果“+”连接的两字符串中只要
    		 * 有一个不是字面常量串(即定义过的),是会产生新的字符串对象。
    		 */

    2)若在定义字符串变量时加final关键字修饰并且在声明时就赋予初始值

    final String str1 = "aaa";  
    final String str2 = "bbb";  
    String str3 = "aaabbb";  
    String str4 = str1 + str2;  
    System.out.println(str3 == str4);//true
    解析:
      因为str1与str2都定义成了常量,在编译时就能确定,编译时就会将常量替换,等同于 
      str4 = "aaa"+"bbb",因此不产生新对象 
       

    3)

    final static String str1;    
        final static String str2;  <span style="font-family: Arial, Helvetica, sans-serif;"> </span>
        static {    
            str1 ="aaa";    
            str2 ="bbb";    //此时str1与str2相当于变量,而不是常,因为块是在运行时才能确定,在编译时不能确定 
        }  
        public static void main(String[] args){    
            String str3 = str1 + str2;  
            String str4 ="aaabbb";    
            System.out.println(str3==str4);   //输出为false  
        } 

    
    

    
    


    展开全文
  • 的储存结构

    2017-08-08 12:22:14
    要将图的信息存到计算机中,需要使用专门设计的数据结构,比较常见的是邻接矩阵,向前星,邻接表,链式向前星这四种方式。另外还有十字链表的方式,由于其建立比较复杂,故在ACM/ICPC竞赛中很少用到,这里不再赘述。...

            

            要将图的信息存到计算机中,需要使用专门设计的数据结构,比较常见的是邻接矩阵,向前星,邻接表,链式向前星这四种方式。另外还有十字链表的方式,由于其建立比较复杂,故在ACM/ICPC竞赛中很少用到,这里不再赘述。下文只需要考虑输入的信息为有向边的信息,如果输入为无向边请读者自行拆成两条有向边处理

                                                                                        

    一  邻接矩阵 

           逻辑结构分为两部分:V和E集合。因此,用一个一维数组存放图中所有顶点数据;用一个二维数组存放顶点间关系(边或弧)的数据,这个二维数组

    称为邻接矩阵。邻接矩阵又分为有向图邻接矩阵和无向图邻接矩阵。(下面三张图片转自点击打开链接

            1.无向图。

                                


             2.有向图 




               3.有向网图

                             

    优点:实现简单直观。

               可以直接查询点Vi与Vj间是否有边,如果有,边的权值是多少。

    缺点:遍历效率低,并且不能储存重边。

               大图的空间开销大,特别当n比较大的时候,建一个n*n的数组是不现实的。

               对于稀疏图邻接矩阵的空间利用效率也不高

     

    二 向前星

           向前星是一种通过储存边信息的方式储存图的数据结构。它的构造方式非常简单,读入每条边的信息,将边存放在数组中,把数组中的边按照起点顺序排序,向前星就构造完了,为了查询方便,经常会有一个数组储存七点为Vi的第一条边的位置。

    数据结构如下

    int head[maxsize];   //储存起点为Vi的第一条边的位置
    struct node
    {
        int from;    //起点
        int to;    //终点
        int w;    //权值
    }edge[maxsize];


            将所有边的信息读入,按照边的起点排序,如果起点相同,对于相同起点的边按终点排序,如果依然相同,按权值排序。在下面的样例中,使用的C++STL的排序函数

    比较函数

    bool cmp(node x,node y)
    {
        if(x.from!=y.from)
            return x.from<y.from;
        if(x.to!=y.to)
            return x.to<y.to;
        return x.w<y.w;
    }

    读入数据

             cin>>n>>m
            for(int i=1;i<=m;i++)
                cin>>edge[i].from>>edge[i].to>>edge[i].w;
            sort(edge+1,edge+1+m,cmp);   //排序
            memset(head,-1,sizeof(head));
            head[edge[0].from]=0;
            for(int i=2;i<=m;i++)
            {
                if(edge[i].from!=edge[i-1].from)
                    head[edge[i].from]=i;  //确实起点为Vi的第一条边的位置
            }

    遍历代码

    for(int i=1;i<=n;i++)
            {
                for(int j=head[i];edge[j].from==i&&j<=m;j++)
                {
                    cout<<edge[j].from<<" "<<edge[j].to<<" "<<edge[j].w<<endl;
                }
            }


    完整代码

    #include<iostream>
    #include<algorithm>
    #include<string.h>
    const int maxsize=1000;
    using namespace std;
    int n,m;
    int head[maxsize];
    struct node
    {
        int from;
        int to;
        int w;
    }edge[maxsize];
    bool cmp(node x,node y)
    {
        if(x.from!=y.from)
            return x.from<y.from;
        if(x.to!=y.to)
            return x.to<y.to;
        return x.w<y.w;
    }
    int main()
    {
        while(cin>>n>>m)
        {
            for(int i=1;i<=m;i++)
                cin>>edge[i].from>>edge[i].to>>edge[i].w;
            sort(edge+1,edge+1+m,cmp);
            memset(head,-1,sizeof(head));
            head[edge[1].from]=1;
            for(int i=2;i<=m;i++)
            {
                if(edge[i].from!=edge[i-1].from)
                    head[edge[i].from]=i;
            }
            for(int i=1;i<=n;i++)
            {
                for(int j=head[i];edge[j].from==i&&j<=m;j++)
                {
                    cout<<edge[j].from<<" "<<edge[j].to<<" "<<edge[j].w<<endl;
                }
            }
        }
        return 0;
    }


    样例测试

    测试数据
    
    8 12
    1 2 4
    8 7 7
    1 6 9
    6 1 12
    3 1 22
    4 3 17
    5 8 29
    6 5 9
    7 4 25
    6 7 4
    8 3 11
    3 2 19
    
    输出
    
    1 2 4
    1 6 9
    3 1 22
    3 2 19
    4 3 17
    5 8 29
    6 1 12
    6 5 9
    6 7 4
    7 4 25
    8 3 11
    8 7 7
    
    head数组的值
    1 -1 3 5 6 7 10 11


    优点:可以对应点非常多的情况,可以储存重边。

    缺点 :但是不能直接判断任意两个顶点之间是否具有边,而且排序需要浪费一些时间


    三 邻接表

    邻接表的是图的一种链式储存结构。对于图G中每个顶点Vi,把所有邻接于Vi的顶点Vj链成一个单链表,这个单链表称为顶点Vi的邻接表。

    邻接表有三种实现方法,分别为动态建表实现,使用STL中的vector模拟链表实现和静态建表实现。

                                     

    1动态建表

    动态建表的数据结构:

    struct EdgeNode   //邻接表节点
    {
        int to;     //终点
        int w;      //权值
        EdgeNode *next;      //指向下一条边的指针
    };
    struct VNode      //起点表节点
    {
        int from;       //起点
        EdgeNode *first;    //邻接表头指针
    }; 
    VNode Adjlist[maxsize];   //整个图的邻接表

    信息储存的主要代码

    cin>>i>>j>>w;
    EdgeNode *p=new EdgeNode();
    p->to=j;
    p->w=w;
    p->next=Adjlist[i].first;
    Adjlist[i].first=p;
    //将新节点指向起点表节点,并且将起点表节点更新为该新节点
    
    

    遍历代码

    for(int i=1;i<=n;i++)
    {
        for(EdgeNode *k=Adjlist[i].first;k!=NULL;k=k->next)
        {
            cout<<i<<" "<<k->to>>" "<<k->w<<endl;
        }
    }

    2 STL 中的vector模拟链表实现

    所需的数据结构

    struct node   //表边节点的类型
    {
        int to;   //节点序号
        int w;     //权值
    };
    vector<node> map[maxsize];   
    

    信息储存的主要代码

    node e;
    cin>>i>>j>>w;
    e.to=j;
    e.w=w;
    map[i].push_back(e);

    遍历代码

    for(int i=1;i<=n;i++)
    {
        for(vector<node>::iterator k=map[i].begin();k!=map[i].end();k++)
        {
            node t=*p;
            cout<<i<<" "<<t.to<<" "<<t.w<<endl;
            /*或者写成 
            cout<<i<<" "<<k->to<<" "<<k->w<<endl;*/
        }
    }
    

    3静态建表

    静态建表也就是采用数组模拟链表的方式实现邻接表的功能。

    我以前的博客有将过,附上链接点击打开链接,在此不再赘述。


    优点:效率高,所在空间小

    缺点 :  不能迅速找到任意两点的关系

    展开全文
  • mysql储存引擎 MySQL的存储引擎是MySQL体系架构中的重要组成部分, 也是MySQL体系结构的核心,插件式的存储引擎更是它区别于其它数据库的重要特征。...常见的MySQL存储引擎InnoDB、MyISAM、...

    mysql储存引擎

    MySQL的存储引擎是MySQL体系架构中的重要组成部分,

    也是MySQL体系结构的核心,插件式的存储引擎更是它区别于其它数据库的重要特征。

    它处于MySQL体系架构中Server端底层,是底层物理结构的实现,用于将数据以各种不同的技术方式存储到文件或者内存中,

    不同的存储引擎具备不同的存储机制、索引技巧和锁定水平。常见的MySQL存储引擎有InnoDB、MyISAM、Memory、Archive等等,

    它们具备各自的特征,我们可以根据不同的具体应用来建立对应的存储引擎表。

     

    myisam和innodb的区别

    MyISAM:

    1. 不支持事务,但是每次查询都是原子的;
    2. 支持表级锁,即每次操作是对整个表加锁;
    3. 存储表的总行数;
    4. 一个MYISAM表有三个文件:索引文件、表结构文件、数据文件;
    5. 采用菲聚集索引,索引文件的数据域存储指向数据文件的指针。辅索引与主索引基本一致,但是辅索引不用保证唯一性。

    InnoDb:

    1. 支持ACID的事务,支持事务的四种隔离级别;
    2. 支持行级锁及外键约束:因此可以支持写并发;
    3. 不存储总行数;
    4. 一个InnoDb引擎存储在一个文件空间(共享表空间,表大小不受操作系统控制,一个表可能分布在多个文件里),也有可能为多个(设置为独立表空,表大小受操作系统文件大小限制,一般为2G),受操作系统文件大小的限制;
    5. 主键索引采用聚集索引(索引的数据域存储数据文件本身),辅索引的数据域存储主键的值;因此从辅索引查找数据,需要先通过辅索引找到主键值,再访问辅索引;最好使用自增主键,防止插入数据时,为维持B+树结构,文件的大调整。
    展开全文
  • 而当大家租用服务器时,挑选配置却又发现raid还有很多种类,其中常见的有RAID0、RAID0+1、RAID1、RAID5这四种。那么它们四者之间的区别又是什么呢?  通过下面这张形象的图片,生动的展现出它们之间的区别! ...
  • MySQL的存储引擎是MySQL体系架构中的重要组成部分,也是MySQL体系结构的核心,插件式的存储引擎更是它区别于其它数据库的重要特征。  它处于MySQL体系架构中Server端底层,是底层... 常见的MySQL存储引擎InnoD...
  • 数据库是以一定方式储存在一起、能与多个用户共享、具有尽可能小冗余度、与应用程序彼此独立数据集合,可视为电子化文件柜——存储电子文件处所,用户可以对文件中数据进行新增、查询、更新、删除等操作。...
  • 稀疏矩阵存储方式

    千次阅读 2019-02-24 23:13:11
    稀疏矩阵就是指一个矩阵中的大部分元素都是0...我们只讲一般情况下的稀疏矩阵的储存方式。 存储方式常见的有两大类,大家也都知道,分别是顺序存储结构和链式存储结构。 对于稀疏矩阵,顺序存储结构中常用的方式有...
  • 数据库是以一定方式储存在一起、能与多个用户共享、具有尽可能小冗余度、与应用程序彼此独立数据集合,可视为电子化文件柜——存储电子文件处所,用户可以对文件中数据进行新增、查询、更新、删除等操作。...
  • 一些常见问题

    2019-07-18 07:18:54
    ArrayList ,Vector,与LiskedList的储存性能和特性 Array List 和Vector都使用的是数组的方式储存数据,此数组的元素数大于实际储存的数据以便添加和插入元素。它们都允许直接按照序号索引元素,但是插入元素都要涉及...
  • 关于vuex使用

    2020-04-05 13:49:22
    例子:登录成功后,显示’‘欢迎xxx用户登录’’ ,常见的储存方式有sessionStorage和localStorage(博客里面有详详细使用方法) 使用Vuex管理数据的好处: 1、能够在vuex中集中管理共享的数据,易于开发和后...
  • 常见的储存方式 - plist 格式文件存储 - NSUserDefaults 沙盒存储(个人偏好设置) - 文件读写存储 - 解归档存储 - 数据库存储 了解缓存,先要了解iOS中沙盒机制这个概念 沙盒其实质就是在iOS系统...
  • 常见的储存方式 文件读写存储(plist,NSUserDefaults) 解归档存储(NSKeyedArchiver) 数据库存储(SQLite、FMDB、CoreData、Keychain) 了解缓存,先要了解iOS中沙盒机制这个概念 沙盒其实质就是在iOS系统下,...
  • 项目中需要上传图片可谓是经常遇到的需求,本文将介绍 3 种不同的...常见的 七牛云,OSS(阿里云)等,这些云平台提供API接口,调用相应的接口,文件上传后会返回图片存储在服务器上的路径,前端获得这个路径保存下来
  • Vue实现图片上传三种方式

    千次阅读 2020-11-02 11:36:29
    项目中需要上传图片可谓是经常遇到的需求,本文将介绍 3 种不同的图片上传方式,在这总结分享一下,什么建议或者意见,请大家踊跃提出来。 没有业务场景的功能都是...常见的 七牛云,OSS(阿里云)等,这些云平台提
  • XML也许是我们储存数据和通讯数据中最常见的一种简易方式,当我们来到XML的海洋时,我们会发现当我们用iPhone程序解析XML时,我们是如此多的选项,让人眼花缭乱。iOS SDK本身就带两种不同的解析库可以使用,除此...
  • 什么是锂电池保护板?锂电池保护板是对串联锂电池组的充放电保护;在充满电时能保证各单体电池之间的电压差异小于设定值,实现电池组各单体电池...锂电池正确的储存环境 怎样保存锂电池|蒲迅技术锂电池保护板原理锂...
  • 17.3. 下面是一些常见的索引限制问题 45 17.3.1. 使用不等于操作符(, !=) 45 17.3.2. 使用 is null 或 is not null 45 17.3.3. 使用函数 45 17.3.4. 比较不匹配的数据类型 46 17.4. 关于索引的排序 46 18. 数据库...
  •  异常表示程序运行过程中可能出现非正常状态,运行时异常表示虚拟机通常操作中可能遇到异常,是一种常见运行错误。java编译器要求方法必须声明抛出可能发生非运行时异常,但是并不要求必须声明抛出未被捕获...
  • 没有业务场景的功能都是耍流氓,那么我们先来模拟一个需要实现的业务场景。假设我们要做一个后台系统添加商品的页面,一些商品名称、信息等字段,还有...常见的 七牛云,OSS(阿里云)等,这些云平台提供API接口...
  • 没有业务场景的功能都是耍流氓,那么我们先来模拟一个需要实现的业务场景。假设我们要做一个后台系统添加商品的页面,...1.云储存常见的 七牛云,OSS(阿里云)等,这些云平台提供API接口,调用相应的接口,文件上传...
  • 前端中三种常见的本地储存方式,它们分别是 cookie localStorage sessionStorage 本地储存的数据量都不会太大,所以不能代替传统的SQL数据库储存,但轻量化的优点在于相应会比SQL快很多,节省了服务端的资源。 ...
  • 链表简单入门

    2021-02-04 18:25:54
    链表简单入门 寒假刚刚把链表题目刷完,感觉对链表了...所以就希望一种储存方式,其元素个数不受限定当添加新元素时,储存个数也会随之改变,这种存储方式就是链表。 下图为结构体示意图 链表
  • 比如有的储存图片,有的储存程序,有的储存文字信息。每一类信息,都可以一种或多种文件格式保存在电脑存储中。每一种文件格式通常会一种或多种扩展名可以用来识别,扩但也可能没有扩展名。展名可以帮助应用程序...
  •  DAS(Direct Attach Storage):是直接连接于主机服务器的一种储存方式,每一台主机服务器独立的储存设备,每台主机服务器的储存设备无法互通,需要跨主机存取资料时,必须经过相对复杂的设定,若主机服务器分属...

空空如也

空空如也

1 2 3 4 5 ... 7
收藏数 140
精华内容 56
关键字:

常见的储存方式有