精华内容
下载资源
问答
  • (一) 什么是图存储结构

    千次阅读 2019-03-18 11:36:52
    阅读:1,220 作者:解学武 (数据结构)存储结构完全攻略 什么是连通 我们知道,数据之间的关系有 3 种,分别... 1 图存储结构示意 1 所示为存储 V1、V2、V3、V4 的结构,从中可以清楚的看...

    阅读:1,220       作者:解学武

    (数据结构)图的存储结构完全攻略

     什么是连通图 

    我们知道,数据之间的关系有 3 种,分别是 "一对一"、"一对多" 和 "多对多",前两种关系的数据可分别用线性表结构存储,本节学习存储具有"多对多"逻辑关系数据的结构——图存储结构。



    图 1 图存储结构示意图


    图 1 所示为存储 V1、V2、V3、V4 的图结构,从图中可以清楚的看出数据之间具有的"多对多"关系。例如,V1 与 V4 和 V2 建立着联系,V4 与 V1 和 V3 建立着联系,以此类推。

    链表不同,图中存储的各个数据元素被称为顶点(而不是节点)。拿图 1 来说,该图中含有 4 个顶点,分别为顶点 V1、V2、V3 和 V4。

    图存储结构中,习惯上用 Vi 表示图中的顶点,且所有顶点构成的集合通常用 V 表示,如图 1 中顶点的集合为 V={V1,V2,V3,V4}。


    注意,图 1 中的图仅是图存储结构的其中一种,数据之间 "多对多" 的关系还可能用如图 2 所示的图结构表示:



    图 2 有向图示意图


    可以看到,各个顶点之间的关系并不是"双向"的。比如,V4 只与 V1 存在联系(从 V4 可直接找到 V1),而与 V3 没有直接联系;同样,V3 只与 V4 存在联系(从 V3 可直接找到 V4),而与 V1 没有直接联系,以此类推。

    因此,图存储结构可细分两种表现类型,分别为无向图(图 1)和有向图(图 2)。

    图的基本常识

    弧头和弧尾

    有向图中,无箭头一端的顶点通常被称为"初始点"或"弧尾",箭头直线的顶点被称为"终端点"或"弧头"。

    入度和出度

    对于有向图中的一个顶点 V 来说,箭头指向 V 的弧的数量为 V 的入度(InDegree,记为 ID(V));箭头远离 V 的弧的数量为 V 的出度(OutDegree,记为OD(V))。拿图 2 中的顶点 V1来说,该顶点的入度为 1,出度为 2(该顶点的度为 3)。

    (V1,V2) 和 <V1,V2> 的区别

    无向图中描述两顶点(V1 和 V2)之间的关系可以用 (V1,V2) 来表示,而有向图中描述从 V1 到 V2 的"单向"关系用 <V1,V2> 来表示。

    由于图存储结构中顶点之间的关系是用线来表示的,因此 (V1,V2) 还可以用来表示无向图中连接 V1 和 V2 的线,又称为边;同样,<V1,V2> 也可用来表示有向图中从 V1 到 V2 带方向的线,又称为弧。

    集合 VR 的含义

    并且,图中习惯用 VR 表示图中所有顶点之间关系的集合。例如,图 1 中无向图的集合 VR={(v1,v2),(v1,v4),(v1,v3),(v3,v4)},图 2 中有向图的集合 VR={<v1,v2>,<v1,v3>,<v3,v4>,<v4,v1>}。

    路径和回路

    无论是无向图还是有向图,从一个顶点到另一顶点途径的所有顶点组成的序列(包含这两个顶点),称为一条路径。如果路径中第一个顶点和最后一个顶点相同,则此路径称为"回路"(或"环")。

    并且,若路径中各顶点都不重复,此路径又被称为"简单路径";同样,若回路中的顶点互不重复,此回路被称为"简单回路"(或简单环)。

    拿图 1 来说,从 V1 存在一条路径还可以回到 V1,此路径为 {V1,V3,V4,V1},这是一个回路(环),而且还是一个简单回路(简单环)。

    在有向图中,每条路径或回路都是有方向的。

    权和网的含义

    在某些实际场景中,图中的每条边(或弧)会赋予一个实数来表示一定的含义,这种与边(或弧)相匹配的实数被称为"权",而带权的图通常称为网。如图 3 所示,就是一个网结构:



    图 3 带权的图存储结构


    子图:指的是由图中一部分顶点和边构成的图,称为原图的子图。

    图存储结构的分类

    根据不同的特征,图又可分为完全图,连通图、稀疏图和稠密图:

    • 完全图:若图中各个顶点都与除自身外的其他顶点有关系,这样的无向图称为完全图(如图 4a))。同时,满足此条件的有向图则称为有向完全图(图 4b))。



      图 4 完全图示意图

      具有 n 个顶点的完全图,图中边的数量为 n(n-1)/2;而对于具有 n 个顶点的有向完全图,图中弧的数量为 n(n-1)。

    • 稀疏图和稠密图:这两种图是相对存在的,即如果图中具有很少的边(或弧),此图就称为"稀疏图";反之,则称此图为"稠密图"。

      稀疏和稠密的判断条件是:e<nlogn,其中 e 表示图中边(或弧)的数量,n 表示图中顶点的数量。如果式子成立,则为稀疏图;反之为稠密图。

    展开全文
  • 存储结构

    万次阅读 2016-07-14 14:50:57
    然后重点介绍了存储结构,主要是五种:邻接矩阵、邻接表、十字链表、邻接多重表和边集数组。邻接矩阵用一维数组存储顶点信息,用二维数组来存储边的信息;邻接表使用数组加链表的方式,一维数组存储顶点,链表...

    图的抽象数据类型

    ADT 图(Graph)
    Data
       顶点的有穷非空集合和边的集合。多对多结构。
    Operation
       CreateGraph(*G,V,VR):按照顶点集V和边弧集VR的定义构造图G。
       DestoryGraph(*G):图G存在便销毁。
       LocateVex(G,u):若图G中存在顶点u,则返回图中的位置。
       GetVex(G,v):返回图G中顶点v的值。
       PutVex(G,v,value):将图G中顶点v赋值value。
       FirstAdjvex(G,*v):返回顶点v的一个邻接顶点,若顶点在G中无邻接顶点返回空。
       NextAdjvex(G,v,*w):返回顶点v相对应顶点w的下一个邻接顶点,若w是v的最后一个邻接点则返回“空”。
       InsertVex(*G,v):在图G中增添新顶点v。
       DeleteVex(*G,v):删除图G中顶点v及其相关的弧。
       InsertArc(*G,v,w):在图G中增添弧<v,w>,若G是无向图,还需要增添对称弧<w,v>。
       DeleteArc(*G,v,w):在图G中删除弧<v,w>,若G是无向图,则还删除对称弧<w,v>。
       DFSTraverse(G):对图G中进行深度优先遍历,在遍历过程对每个顶点调用。
       HFSTraverse(G):对图G中进行广度优先遍历,在遍历过程对每个顶点调用。
    endADT

    图的存储结构

    不能用简单的顺序存储结构表示,也不能用多重链表结构,因为有空间的浪费。下面介绍5种不同的存储结构:

    邻接矩阵

    图的邻接矩阵(Adjacency Matrix)存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息,一个二维数组(称为邻接矩阵)存储图中的边或弧的信息。

    假设图G有n个顶点,则邻接矩阵式一个 nn 方阵,定义为:arc[i][j]=1,(vi,vj)E<vi,vj>E,反之arc[i][j]=0 。而无向图的边数组是一个对称矩阵。

    图反映的信息方便:判定任意两结点是否有边;知道某结点的度,其实就是这个顶点 vi 在邻接矩阵中第i行/列的元素之和;求顶点的所有邻接点就是将矩阵中第i行元素扫描一遍,arc[i][j]为1的就是该顶点的邻接点。

    注意:有向图中顶点的入度是该顶点列各数之和,出度是该顶点行各数之和

    图的邻接矩阵

    设图G是个网图,有n个结点,则邻接矩阵是一个 nn 方阵,定义为:arc[i][j]=Wij,若 (vi,vj)E<vi,vj>Earc[i][j]=0,若 i=jarc[i][j]=,反之。这里的 Wij 表示 (vi,vj)(vi,vj) 的权值。还有 是指计算机用一个不可能的值来代替不存在

    这里写图片描述

    首先来看邻接矩阵存储的结构,代码如下:

    typedef char VertexType;  //顶点类型
    typedef int EdgeType;  //边上的权值类型
    #define MAXVER 100;  //最大顶点数
    #define INFINITY 65535;  //用该数来代替无穷大
    type struct{
       VertexType vexs[MAXVER];  //顶点表
       EdgeType arc[MAXVER][MAXVER];  //邻接矩阵,边表
       int numVertexes,numEdges; //图中当前顶点数和边数
    }MGraph;

    有了这个结构,如何构造一个图呢?其实就是给顶点表和边表输入数据的过程,下面是构建无向网图的创建代码:

    /*构建无向网图的邻接矩阵表示*/
    void CreateMGraph(MGraph *G){
       int i,j,k,w;
       printf("输入顶点数和边数:\n");
       scanf("%d,%d",&G->numVertexes,&G->numEdges); //输入顶点数和边数
       for(i=0;i<G->numVertexes;i++)  
          scanf(&G->vexs[i]);  //读入顶点信息,建立顶点表
       for(i=0;i<G->numVertexes;i++)
          for(j=0;j<G->numVertexes;j++)
             G->arc[i][j]=INFINITY;  //邻接矩阵初始化
       for(k=0;k<G->numEdges;k++){ //给边表赋值
          printf("输入边(vi,vj)上的下标i,下标j和权值w:\n");
          scanf("%d,%d,%d",&i,&j,&w);  //输入边(vi,vj)上的权值w
          G->arc[i][j]=w;
          G->arc[j][i]=G->arc[i][j];  //无向图,矩阵对称
       }
    }

    n个顶点和e条边的无向网图创建的时间复杂度为 O(n+n2+e) ,其中,对邻接矩阵的初始化耗费了 O(n2) 的时间。

    邻接表

    对于边数相对顶点较少的图,邻接矩阵这种结构存在对存储空间的极大浪费。考虑另一种存储结构,可考虑对边或弧使用链式存储的方式来避免空间浪费问题。

    数组于链表相结合的存储方法称为邻接表(Adjacency List)。

    具体的处理方法为:

    1.图中顶点用一个一维数组存储,当然顶点也可用链表存储,不过数组更方便读取顶点信息。另外,对于顶点数组,每个数据元素还要存储指向第一个邻接点的指针,以便查找顶点的边信息。

    2。图中每个顶点 vi 的所有邻接点构成一个线性表,由于邻接点个数不定,所以用单链表存储,无向图称为顶点 vi边表,有向图则成为顶点 vi 作为弧尾的出边表

    这里写图片描述

    根据图获得信息:某顶点的度为该顶点边表中结点的个数;判断两顶点是否有边,只需测试顶点的边表中是否有该顶点的下标即可;求顶点的邻接点,只需对该顶点的边表进行遍历。

    注意:若是有向图,以顶点为弧尾来存储边表,这样就能得到该顶点的出度。有时也为了能方便确定顶点入度以顶点为弧头的弧,建立一个有向图的逆邻接表,及对每个顶点都建立一个链接为顶点为弧头的表。

    对于带权的网图,也可在边表结点定义中再增加一个weight的数据域,存储权值信息。

    下面详细介绍邻接表的结点定义的代码:

    typedef char VertexType;  //顶点类型
    typedef int EdgeType;  //边上的权值类型
    
    type struct EdgeNode{  //边表结点
       int adjvex; //邻接点域,存储该顶点对应的下标
       EdgeType weight;  //存储权值,非网图不需要
       struct EdgeNode *next;
    }EdgeNode;
    
    type struct VertexNode{  //顶点表结点
       VertexType data; //顶点信息
       EdgeNode *firstedge;  //边表头指针
    }VertexNode,AdjList[MAXSIZE];
    
    type struct{
       AdjList adjList;  
       int numVertexes,numEdges; //图中当前顶点数和边数
    }GraphAdjList;
    
    /*建立无向图图的邻接表结构,算法的复杂度为O(n+e)*/
    void CreateGraphAL(GraphAdjList *G){
       int i, j, k;
       EdgeNode *e;
       printf("请输入顶点数和边数(输入格式为:顶点数,边数):\n");
       // 读入顶点数和边数 
       scanf("%d,%d", &(G->numVertexes), &(G->numEdges));
       for (i = 0; i < G->numVertexes; i++){// 读入顶点信息,建立顶点表   
          scanf("\n%c", &(G->adjList[i].data)); // 读入顶点信息   
          G->adjList[i].firstedge = NULL; // 边表头指针设为空   
       }
       for (k = 0; k < G->numEdges; k++){ // 建立边表
          printf("请输入边的信息(输入格式为:i,j):\n"); 
          scanf("%d,%d", &i, &j); // 读入边(Vi,Vj)的顶点对应序号
          /*相当于将j的结点头插法插入到顶点i的边表链中*/
          e=(EdgeNode *)malloc(sizeof(EdgeNode));  //生成新边表结点 
          e->adjvex = j; // 邻接点序号为j
          // 将新边表结点s插入到顶点Vi的边表头部
          e->next = G->adjList[i].firstedge; 
          G->adjList[i].firstedge = e;
          /*相当于将i的结点头插法插入到顶点j的边表链中*/
          e=(EdgeNode *)malloc(sizeof(EdgeNode));
          e->adjvex = i;
          e->next = G->adjList[j].firstedge;
          G->adjList[j].firstedge = e;
         }
     }

    十字链表

    在有向图中,邻接表是有缺陷的,关心了出度问题,要想知道入度,就必须遍历整个图,反之逆邻接表解决了入度却不能解决出度,那能否将邻接表与逆邻接表结合起来呢,答案是肯定的,于是就有了一种新的有向图的存储方法:十字链表法

    重新定义顶点表结构:firstin 表示入边表头指针,指向该顶点的入边表中的第一个结点;firstout表示出边表头指针,指向该顶点的出边表中的第一个结点。


    重新定义边表结构:tailvex是指弧起点在顶点表的下标;headvex是指弧终点在顶点表中的下标;headlink是指入边表指针域,指向终点相同的下一条边;taillink是指出边表指针域,指向起点相同的下一条边。若是网,还可增加权值域来保存权值。

    有向图的十字链表法

    红线箭头表示该图的逆邻接表的表示,蓝色箭头表示该图的邻接表。对于 v0 来说,有两个顶点 v1v2 的入边,所以,v0 的firstin指向顶点v1 的边界点中headvex为0的结点,接着,由入边节点的headlink指向下一个入边顶点 v2

    十字链表的好处是将邻接表和逆邻接表整合在一起,既能找到以 vi 为尾的弧,又能找到以 vi 为头的弧,很容易求得顶点的出度和入度。除了结构复杂些,创建图算法的时间复杂度和邻接表相同,所以在有向图应用中,十字链表是个不错的数据结构模型。

    邻接多重表

    十字链表法师有向图的优化存储结构,对于无向图而言呢?若在无向图应用中,关注的重点是顶点,那邻接表不错,但是若更关注边的操作,例如对已访问的边做标记,删除一条边等操作,这就是说要找到这条边的两个边表结点进行操作,还是比较麻烦的。

    因此,仿照十字链表方法,对边表结点的结构进行改造,可避免边操作要找到两个结点的问题。

    重新定义边表结点结构:ivex 和 jvex 是与某条边依附的两个顶点在顶点表中的下标;ilink 指向依附顶点 ivex 的下一条边,jlink指向依附顶点 jvex 的下一条边

    无向图的多重链表结构

    其实,首先,由于顶点 v0 的 ( v0, v1) 边的邻边为 ( v0, v3) 和 ( v0, v2) ,所以第一行的0后面的ilink指向第四行的0,同理第四行0后面的jlink指向第五行的0。注意ilink指向的结点的jvex一定要和它本身的ivex的值相等,同理,其他的连线也可相继得出。

    邻接多重链表与邻接表的区别仅在于同一条边在邻接表中用两个结点表示,而邻接多重链表中只有一个结点,这样对边的操作就简单很多了。例如,若要删除上图的 ( v0, v2) ,只需要将第二行2后的指针和第四行0后面的指针设为空即可。基本操作和邻接链表相似。

    边集数组

    边集数组是由两个一维数组构成。一个是存储顶点的信息;另一个是存储边的信息,这个边数组每个数据元素有一条边的起点下标(begin)、终点下标(end)和权(weight)组成。

    边集数组更关注边的集合,查找一丁点的度需要扫描整个边数组,效率不高,因此,其更适合对边依次进行处理的操作。

    边集数组

    展开全文
  • 数据结构:存储结构之邻接表

    万次阅读 多人点赞 2013-04-30 00:05:05
    对于来说,邻接矩阵是不错的一种图存储结构,但是我们也发现,对于边数相对顶点较少的,这种结构是存在对存储空间的极大浪费的。因此我们考虑另外一种存储结构方式:邻接表(Adjacency List),即数组与链表相...

    对于图来说,邻接矩阵是不错的一种图存储结构,但是我们也发现,对于边数相对顶点较少的图,这种结构是存在对存储空间的极大浪费的。因此我们考虑另外一种存储结构方式:邻接表(Adjacency List),即数组与链表相结合的存储方法。

    邻接表的处理方法是这样的。

    1、图中顶点用一个一维数组存储,另外,对于顶点数组中,每个数据元素还需要存储指向第一个邻接点的指针,以便于查找该顶点的边信息。

    2、图中每个顶点vi的所有邻接点构成一个线性表,由于邻接点的个数不定,所以用单链表存储,无向图称为顶点vi的边表,有向图称为顶点vi作为弧尾的出边表。

    例如图7-4-6就是一个无向图的邻接表结构。


    若是有向图,邻接表的结构是类似的,如图7-4-7,以顶点作为弧尾来存储边表容易得到每个顶点的出度,而以顶点为弧头的表容易得到顶点的入度,即逆邻接表。


    对于带权值的网图,可以在边表结点定义中再增加一个weight的数据域,存储权值信息即可,如图7-4-8所示。


    下面示例无向图的邻接表创建:(改编自《大话数据结构》)

     C++ Code 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67

    #include<iostream>
    using namespace std;

    #define MAXVEX 100 /* 最大顶点数,应由用户定义 */
    typedef char VertexType; /* 顶点类型应由用户定义 */
    typedef int EdgeType; /* 边上的权值类型应由用户定义 */

    typedef struct EdgeNode/* 边表结点  */
    {
        int adjvex;/* 邻接点域,存储该顶点对应的下标 */
        EdgeType weight;/* 用于存储权值,对于非网图可以不需要 */
        struct EdgeNode *next; /* 链域,指向下一个邻接点 */
    } EdgeNode;

    typedef struct VextexNode/* 顶点表结点 */
    {
        VertexType data;/* 顶点域,存储顶点信息 */
        EdgeNode *firstedge;/* 边表头指针 */
    } VextexNode, AdjList[MAXVEX];

    typedef struct
    {
        AdjList adjList;
        int numNodes, numEdges; /* 图中当前顶点数和边数 */
    } GraphAdjList;


    void CreateALGraph(GraphAdjList *Gp)
    {
        int i, j, k;
        EdgeNode *pe;
        cout << "输入顶点数和边数(空格分隔):" << endl;
        cin >> Gp->numNodes >> Gp->numEdges;

        for (i = 0 ; i < Gp->numNodes; i++)
        {
            cout << "输入顶点信息:" << endl;
            cin >> Gp->adjList[i].data;
            Gp->adjList[i].firstedge = NULL;/* 将边表置为空表 */
        }

        for (k = 0; k <  Gp->numEdges; k++)/* 建立边表 */
        {
            cout << "输入边(vi,vj)的顶点序号i,j(空格分隔):" << endl;
            cin >> i >> j;
            pe = (EdgeNode *)malloc(sizeof(EdgeNode));
            pe->adjvex = j;/* 邻接序号为j */
            /* 将pe的指针指向当前顶点上指向的结点 */
            pe->next = Gp->adjList[i].firstedge;
            Gp->adjList[i].firstedge = pe;/* 将当前顶点的指针指向pe */

            pe = (EdgeNode *)malloc(sizeof(EdgeNode));
            pe->adjvex = i;
            pe->next = Gp->adjList[j].firstedge;
            Gp->adjList[j].firstedge = pe;

        }
    }

    int main(void)
    {
        GraphAdjList GL;
        CreateALGraph(&GL);

        return 0;
    }
    这里的邻接点插入使用了单链表创建中的头插法,对于无向图来说,一条边对应都是两个顶点,所以在循环中,一次就针对i和j分别进行了插入。

    展开全文
  • 顺序存储结构和链式存储结构的优缺点比较

    万次阅读 多人点赞 2018-10-09 17:45:34
    顺序存储结构和链式存储结构的比较 优缺点 顺序存储时,相邻数据元素的存放地址也相邻(逻辑与物理统一);要求内存中可用存储单元的地址必须是连续的。 优点:存储密度大(=1),存储空间利用率高。 缺点:...

    顺序存储结构和链式存储结构的比较

    优缺点

    1. 顺序存储时,相邻数据元素的存放地址也相邻(逻辑与物理统一);要求内存中可用存储单元的地址必须是连续的。
      • 优点:存储密度大(=1),存储空间利用率高。
      • 缺点:插入或删除元素时不方便。
    2. 链式存储时,相邻数据元素可随意存放,但所占存储空间分两部分,一部分存放结点值,另一部分存放表示结点间关系的指针
      • 优点:插入或删除元素时很方便,使用灵活。
      • 缺点:存储密度小(<1),存储空间利用率低。

    使用情况

    • 顺序表适宜于做查找这样的静态操作;
    • 链表宜于做插入、删除这样的动态操作。
    • 若线性表的长度变化不大,且其主要操作是查找,则采用顺序表;
    • 若线性表的长度变化较大,且其主要操作是插入、删除操作,则采用链表。

    比较

    顺序表与链表的比较

    • 基于空间的比较

      • 存储分配的方式
        • 顺序表的存储空间是静态分配的
        • 链表的存储空间是动态分配的
      • 存储密度 = 结点数据本身所占的存储量/结点结构所占的存储总量
        • 顺序表的存储密度 = 1
        • 链表的存储密度 < 1
    • 基于时间的比较

      • 存取方式
        • 顺序表可以随机存取,也可以顺序存取
        • 链表是顺序存取的
      • 插入/删除时移动元素个数
        • 顺序表平均需要移动近一半元素
        • 链表不需要移动元素,只需要修改指针

     

    内容转载自:https://blog.csdn.net/VonSdite/article/details/78240594?locationNum=9&fps=1

    展开全文
  • 图解存储结构

    千次阅读 2017-10-19 23:14:26
    刚开始接触图形结构的时候,觉得它很烧脑子,因为像线性表它仅有线性关系,树形结构有清晰...要清楚地理解存储结构,首先要明白存储结构里要存储些什么东西。要存储图形结构的信息,无非就是存储的顶点(vec
  • 【数据结构】存储结构

    千次阅读 2017-05-01 13:51:08
    是否可以采用顺序存储结构存储?的特点:顶点之间的关系是m:n,即任何两个顶点之间都可能存在关系(边),无法通过存储位置表示这种任意的逻辑关系,所以,无法采用顺序存储结构。如何存储?考虑的定义,...
  • 数据结构-存储结构

    千次阅读 2017-12-17 10:29:39
    数据结构-存储结构
  • 算法设计的要求时间效率高存储量低顺序存储结构和链式存储结构的区别链表存储结构的内存地址不一定是连续的,但顺序存储结构的内存地址一定是连续的;链式存储适用于在较频繁地插入、删除、更新元素时,而顺序存储...
  • 数据结构 - 顺序存储结构和链式存储结构 顺序存储结构 顺序存储中,相邻数据元素的存放地址也相邻,内存中存储单元的地址必须是连续的,存储密度 = 1。 优点: 不用为表示节点间的逻辑关系而...
  • 线性表之顺序存储结构和链式存储结构

    万次阅读 多人点赞 2018-09-28 14:17:06
    顺序存储结构和链式存储结构有所不同,具体区别如下表所示: 通过上面的对比,可以得出一些经验性的结论: 若线性表需要频繁查找,很少进行插入和删除操作时,宜采用顺序存储结构。若需要频繁插入和删除时,宜...
  • 存储结构

    2014-02-14 15:20:20
    存储结构 编辑 数据元素之间的关系有两种不同的表示方法:顺序映象和非顺序映象,并由此得到两种不同的存储结构:顺序存储结构和链式存储结构。数据的存储结构是指数据的逻辑结构在计算机中的表示。 ...
  • 顺序存储结构和随机存储结构

    千次阅读 2013-08-07 14:40:04
    顺序存储结构:   在计算机中用一组地址连续的存储单元依次存储线性表的各个数据元素,称作线性表的顺序存储结构.  顺序存储结构存储结构类型中的一种,该结构是把逻辑上相邻的节点存储在物理位置上相邻的存储...
  • [size=16px]]刚开始学数据结构,对于静态链表的存储结构书上也没有明确给出。以下是个人理解: 既然静态链表就是结构体数组,那数组肯定是顺序存储结构,所以静态链表整体上应该是顺序存储结构。但静态链表存储的...
  • 队列、队列的顺序存储结构、链式存储结构
  • 【数据结构——存储结构

    千次阅读 多人点赞 2020-11-10 15:29:27
    目录一、的定义和基本术语(一)的定义(二)的基本术语三级目录一、存储结构(一)邻接矩阵三级目录(二)邻接表三级目录(三)十字链表三级目录(四)邻接多重表三级目录 一、的定义和基本术语 (一)...
  • 存储结构类型

    2017-05-18 22:19:06
    1、数据结构:指所有数据元素以及数据元素之间的关系,其中包括数据元素之间的逻辑关系(数据的逻辑结构)、数据元素及其关系在计算机存储系统中的存储方式(数据的存储结构)、施加在数据上的操作(数据的运算) ...
  • 存储结构的遍历。

    千次阅读 2019-06-07 18:27:10
    定义存储结构类型 建立的邻接矩阵存储 邻接表存储法 定义结构类型 建立有向的邻接表存储 遍历 深度优先搜索DFS 广度优先搜索BFS 的存储方法 邻接矩阵存储法 定义存储结构类型 #define Max ...
  • 线性表有顺序存储结构与链式存储结构两种表示方式,本章主要介绍线性表的顺序存储结构的表示方式。 线性表的顺序表示是指用一组地址连续的存储单元依次存储线性表的数据元素。其原理大致如下所示: ![这里写图片...
  • 链式存储结构

    千次阅读 2019-09-20 16:27:14
    线性表的链式存储结构: 为什么采用链式存储结构这种数据结构? –》因为顺序存储结构插入或删除元素时候会涉及大量元素移动,非常影响效率。 因此引入了链式存储结构为了弥补顺序存储结构效率上的问题。 链式存储...
  • 一:线性表的顺序存储结构 1.定义 2.顺序存储示意如下所示: 3.编号地址 4.存储位置公式 5.存取操作时间性能 6.随机存储结构 7.时间复杂度 (1)对于存取操作 (2)对于插入和删除操作 8. 使用场景 二...
  • Oracle存储结构简介

    千次阅读 2018-01-18 11:12:53
    Oracle存储结构 Oracle存储结构分物理存储...Oracle存储结构示意 Oracle物理存储结构 1. 数据文件 每一个ORACLE数据库有一个或多个物理的数据文件(data file)。一个数据库的数据文件包含全部数据库数据。
  • 数据结构 - 存储结构

    千次阅读 2015-05-01 07:21:34
    的抽象数据类型定义是一种数据结构,加上一组基本操作就构成了的抽象数据类型。 的抽象数据类型定义如下: ADT Graph{ 数据对象V:具有相同特性的数据元素的集合,称为顶点集。 数据关系R:R={VR} VR={,w>|,...
  • 顺序存储结构

    2019-08-26 20:36:04
    线性表有两种存储结构:顺序存储结构和链式存储结构。 线性表的顺序存储结构,指的是用一段地址连续的存储单元依次存储线性表的数据元素。例如:C语言的数组。 线性表的顺序存储的结构代码: #define MAXSIZE 20 ...
  • 索引存储结构

    千次阅读 2019-07-26 20:13:23
    四种数据存储结构---顺序存储 链接存储 索引存储 散列存储 转自:https://www.cnblogs.com/fengty90/p/3768826.html 存储结构分四类:顺序存储、链接存储、索引存储 和 散列存储。 顺序结构和链接结构适用在内存...
  • 顺序存储结构和链式存储结构的优缺点

    万次阅读 多人点赞 2017-10-08 09:21:35
    顺序存储结构和链式存储结构的优缺点 数据在计算机内有链式和顺序两种存储方式,在存储空间使用的灵活性上, 链式存储比顺序存储要高。 (一)顺序存储结构和链式存储结构的优缺点比较,以及使用情况。 ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 2,094,904
精华内容 837,961
关键字:

图的存储结构