精华内容
下载资源
问答
  • 线性表的两种存储结构 1.顺序结构 (1)结点中只有自身的信息域,没有关联信息域。因此,顺序存储结构的存储密度大度、存储空间利用率高。 (2)通过计算地址直接访问任何数据元素,即可以随机访问。 (3)插入和...

    线性表的两种存储结构

    1.顺序结构

    (1)结点中只有自身的信息域,没有关联信息域。因此,顺序存储结构的存储密度大度、存储空间利用率高。
    (2)通过计算地址直接访问任何数据元素,即可以随机访问。 (3)插入和删除操作会引起大量元素的移动。

    2.链式结构

    (1)结点除自身的信息域外,还有表示关联信息的指针域。因此,链式存储结构的存储密度小、存储空间利用率低。
    (2)在逻辑上相邻的结点在物理上不必相邻,因此,不可以随机存取,只能顺序存取。
    (3)插入和删除操作方便灵活,不必移动结点只需修改结点中的指针域即可。

    使用场合的选择

    1、基于存储空间
    顺序表的存储空间是静态分配的,在程序执行之前必须明确规定它的存储规模。链表不用事先估计存储规模,但链表的存储密度较低。顺序存储结构的存储密度是1,而链式存储结构的存储密度小于1。
    2、基于运算
    在顺序表中按序号访问的时间复杂度为O(1),而链表中按序号访问的时间复杂度为O(n)。
    3、基于环境
    顺序表容易实现,在任何高级语言中都有数组类型,链表的操作是基于指针的,相对来讲顺序表简单些。

    总之,两种存储结构各有优势,选择哪一种结构依据实际问题而定。一般来讲,较稳定的线性表选择顺序存储,而频繁的做插入、删除操作的动态性较强的线性表选择链式存储更为合适。

    展开全文
  • 常用数据结构之图的两种存储方式

    千次阅读 2019-04-20 10:09:58
    图通常有两种存储方式,即邻接矩阵和邻接表。 下面介绍一下邻接矩阵。设G=(V,E)是具有n个结点的图,顶点序号依次为0,1,2,3、、、n-1。G的邻接矩阵是具有如下定义的方阵A: A[i][j]=1表示顶点i与顶点j邻接...

    图由结点的有穷结合V和边的集合E组成。为了与树形结构进行区别,在图结构中常常将结点称为顶点,边是顶点的有序偶对。若两个顶点之间存在一条边,则表示这两个顶点具有相邻的关系。

    图通常有两种存储方式,即邻接矩阵和邻接表。

    下面介绍一下邻接矩阵。设G=(V,E)是具有n个结点的图,顶点序号依次为0,1,2,3、、、n-1。G的邻接矩阵是具有如下定义的方阵A:

    A[i][j]=1表示顶点i与顶点j邻接,即i与j之间有一条边或者弧。

    A[i][j]=0表示顶点i与顶点j不邻接

    邻接矩阵是图的顺序存储结构。

    邻接矩阵的结构型定义如下:

    struct VerType{
    	
    	int no;//顶点的编号 
    	char info;//顶点的其他信息 
    	
    };
    struct MGraph{
    	
    	int n,e;//结点数目与边数
    	int edges[maxn][maxn];//邻接矩阵的定义 
    	int VerType[maxn]; //存放结点的信息
    	
    };

    关于邻接表的形式: 

    struct ArcNode{
    	int adjvex;//这条边所指向的结点信息
    	struct ArcNode *nextarc;//该顶点指向下一条边的指针
    	int info;//这条边的相关信息如权值 
    }; 
    struct VNode {
    	char data;//顶点信息 
    	ArcNode *firstarc;//指向第一条边的指针 
    };
    struct Agraph{
    	
    	VNode adjlist[maxn];//邻接表 
    	int n,e;//顶点数目和边数 
    };
    
    

     

    展开全文
  • 常用的逻辑线性结构和逻辑非线性结构: 堆栈、队列、线性表、数组、链表、普通的树、二叉树、哈夫曼树。 下面分别介绍这些数据结构的初始化。 堆栈 堆栈又称为“栈”,是一线性结构;其最大的特点是:记忆性、...

    常用的逻辑线性结构和逻辑非线性结构:
    堆栈、队列、线性表、数组、链表、普通的树、二叉树、哈夫曼树。
    下面分别介绍这些数据结构的初始化。
    //具体源代码看github:https://github.com/xiami-maker/aboutInitialization/tree/master

    堆栈

    堆栈又称为“栈”,是一种线性结构;其最大的特点是:记忆性、先进后出控制堆栈存取数据需要一个“栈顶指针”,通常堆栈还涉及”栈底指针“。
    int top; //栈顶指针,下标
    int bottom; //栈底指针,下标
    top和bottom的初始值都是0,这表示栈为“空”。
    入栈的过程,即,push的过程:stack[top++] = data;这就是data入stack栈的过程。
    数据出栈的过程,即,pop的过程:data = stack[–top];
    堆栈相对于一般的存储结构,最大的不同点是:其中的数据,不能“遍历”!只能直接访问栈顶元素的值,不能访问栈顶元素下面的元素的值!也就是说,堆栈不支持“随机访问(就是通过下标进行访问!)”。
    堆栈的实现:
    由于堆栈有空间、栈顶指针等众多要素,因此,先设计其“控制头”;

    typedef struct MEC_STACK {
    	void **data;
    	int capacity;
    	int top;
    	}MEC_STACK;
    

    画图来表示为:
    在这里插入图片描述
    具体源代码看最上方的github;

    队列

    线性逻辑结构,一对一;
    基本点:一个入口(队尾)和一个出口(队首)
    特点:先进先出
    画图表示如下
    在这里插入图片描述队列不仅仅是直线的,也可以是环形的。
    如下图所示:
    在这里插入图片描述那么,环形队列的表示用刚才的结构体就无法表示了。这时,我们就要增加结构体里的内容。

    typedef struct QUEUE {
    	USER_TYPE *queue;
    	int capacity;
    	int head;
    	int tail;
    	boolean lastAction;
    }QUEUE;
    #define IN		1
    #define OUT		0
    

    其中head表示队首,tail表示队尾,lastAction表示上一次操作。
    队列满时,heda == tail;队列空时,head == tail;
    单独从head == tail,无法判断队列的空与满!但是,可以根据上一次队列的操作(入队列或出队列)来综合判断。
    队列中有效元素个数的计算公式:
    (tail - head + capacity ) % capacity;

    具体源代码看最上方的github;

    链表

    链表是一个物理非线性结构。是由一个一个的节点链接而成,每个节点对应一块内存空间,两个节点之间并不是像数组一样连续。
    节点的定义如下:

    typedef struct NODE {
    	void data;
    	struct NODE *next;
    }NODE;
    

    链表形成的链式结构如下图:
    在这里插入图片描述
    具体源代码看最上方的github;

    树、二叉树与哈夫曼树

    树的性质:
    1.一棵树最多有一个节点,该节点无前驱节点,即,无父节点,称为:根节点;空树:没有任何节点的树。
    2.树中的任意一个节点,有且仅有一个前驱节点,可以有n(n >= 0)个后继节点。
    3.若一个节点没有后继节点(子节点),则,这个节点称为“叶子节点”。
    树的基本术语:
    根节点:如上,不再赘述。
    节点的度(degree):一个节点的子节点个数,称为这个节点的度。
    树的度:一棵树中,度最大的节点的度,称为该树的度。
    树的深度(高度):树的节点的层次数。
    叶子节点:度为0的节点。

    树的遍历:
    在这里插入图片描述
    二叉树:
    在这里插入图片描述
    满二叉树:
    在这里插入图片描述
    完全二叉树:
    在这里插入图片描述
    在这里插入图片描述
    具体源代码看最上方的github;

    哈夫曼树:
    由于哈夫曼树涉及到一个非常具有实际意义的问题:哈夫曼压缩与解压缩技术,所以单独写了一篇博文,这里提供博文链接:https://blog.csdn.net/weixin_44836233/article/details/102837718

    数组

    int arr[10];
    

    数组是一个线性结构,其特点:
    1.数组通常由capaci的限制;
    2.数组中的元素,类型都是一样的;即,数组元素长度相同。
    在学习数组时,需要解决的问题是:地址映射。

    double ar[10] = {.....};
    

    ar[3] 在c编译器的工作下,将转换成:ar + sizeof(double) * 3;这个结果直接在c程序执行时体现,在c语言源代码角度根本看不到这个“地址映射“过程!!!
    现在要求编写一个通用二维数组。

    typedef struct MATRIX {
    	USER_TYPE *data;
    	int maxRow;
    	int maxCol;
    }MATRIX;
    

    在这个MATRIX所提供的算子(函数)中,最重要的基础函数是:行、列值与一维数组下标的相互转换。
    在这里插入图片描述

    线性表

    线性表是一个逻辑线性结构,即,一对一结构。
    在讨论线性表的实现(存储结构),可以用物理线性结构(数组)实现,也可以用物理非线性结构(链表)实现。
    假设用数组实现:
    一个简单而目光短浅的做法是:直接用数组就好了(代码如下)!!!

    typedef struct POINT {
    	int row;
    	int col;
    }POINT;
    
    POINT *pointLinear = NULL;
    int pointCount = 0;
    int capacity = 30;
    
    pointLinear = (POINT *) calloc(sizeof(POINT),capacity);
    

    对于线性表的思考:线性表处理需要必须的“存储空间”(就是线性表的主体部分)之外,还需要对线性表进行诸多方面的运算:插入、删除、查找、清空等等,或者说:控制!
    “控制头是基于数据(信息)的”,因此,为了更好地控制线性表,也为了能为“用户”(使用我们所编写的线性表工具,完成自己的APP的那些程序员,就是我们的用户!)提供一个我完善的编程工具,需要先定义一个“控制头”!
    控制头部分至少有如下三种内容:
    1。存储用户数据的线性表空间;
    2.线性表的容量;
    3.用户数据的数量;
    最后一个难题,用户的数据类型!!
    因为工具需要具有普适性。工具不能因为用户的数据类型不一致,而不能使用!!!以前曾经用过USER_TYPE的方式解决用户类型的问题,但是,这是需要用户事先定义USER_TYPE类型,且,这个类型只能是一种;这些约束都使得USER_TYPE方式应该慎重使用。
    这里将使用void **的方案解决用户数据类型普适化的问题!
    假设用户数据类型是:POINT,用数组直接表达的方案,应该如下:POINT data[N];事实上,上述数组的每一个元素的类型是POINT;
    如果用动态存储分配的方案实现:
    POINT *data;
    data = (POINT *) calloc(sizeof(POINT),capacity);
    事实上,上述动态申请的每一个元素类型是POINT;

    对于下面的定义,该如何理解?
    POINT *data[N];
    data是一个(拥有N个POINT *类型的元素)数组;所以,data是一个指针数组(由指针组成的数组)!
    如果用动态存储分配方案,则写成:
    POINT **data;
    data = (POINT **) calloc(sizeof(POINT *),capacity);
    这里最关键的问题是:sizeof(POINT *)的结果是4B,而且,无论是否是POINT,任意类型的指针类型,长度都为4B;那么就定义为:
    void **data;
    data = (void **) calloc(sizeof(void *),capacity);
    当然的,在data[i]中,必须存储而且也只能存储用户数据类型的变量的首地址(指针)! data[i]的类型是void *,是一个指针类型;
    综上所述,MEC_LINEAR类型的定义是:

    typedef struct MEC_LINEAR {
    	void **data;	//真正的线性表空间
    	int capacity;	//线性表容量
    	int count;	//有效的用户数据个数
    }MEC_LINEAR;
    

    线性表的结构图如图所示:
    在这里插入图片描述

    展开全文
  • 图的两种存储结构各有什么有缺点

    千次阅读 2020-04-30 20:23:43
    图的两种存储结构各有什么有缺点 邻接矩阵 优点:容易确定两个顶点之前是否存在边,容易确定顶点的度 缺点:占用空间大(当顶点多边少的时候) 空间复杂度:n平方 邻接表: 优点:无向图邻接表容易求得顶点的度 ,节省空间 有...

    图的两种存储结构各有什么有缺点

    邻接矩阵
    优点:容易确定两个顶点之前是否存在边,容易确定顶点的度
    缺点:占用空间大(当顶点多边少的时候)
    空间复杂度:n平方
    邻接表:
    优点:无向图邻接表容易求得顶点的度 ,节省空间
    有向图邻接表容易得到顶点的出度,节省空间
    缺点:不容易得到某个顶点的入度
    空间复杂度O(边数+顶点数)

    展开全文
  • 和线性表类似,堆栈也有两种基本的存储结构:顺序存储结构和链式存储结构。 顺序栈是使用顺序存储结构实现的堆栈,即利用一组地址连续的存储单元依次存放堆栈中的数据元素。 由于堆栈是一种特殊的线性表,因此在...
  • 广义表的两种存储方法
  • 顺序存储结构和链接存储结构
  • 比较顺序存储和链接存储两种存储结构的有缺点。 1. 分别用顺序存储和链接存储实现线性表的基本操作; 2. 比较两者的优缺点,并说明两者的适用场合。
  • 队列的两种存储结构

    千次阅读 2016-05-15 17:37:59
    从数据的存储结构来划分,队列结构可以分成类: 顺序队列结构:即使用一组地址连续的内存单元依次保存队列中的数据。在程序中,可以定义一个指定大小的结构数组来作为队列。 struct DATA{ int x; int y; }; ...
  • 数据结构之图的两种存储方式

    千次阅读 2017-03-05 16:36:47
    第一:邻接矩阵 邻接矩阵可以表示顶点之间的相邻关系的矩阵,是一个n阶方阵,可以用一个一维数组来表示顶点信息,用一个二维数组来表示顶点之间的边的联系以及权重 具体的代码如下:#include #include ...
  • 1、存储空间分配不同 顺序栈——顺序分配 (1)在申明顺序栈类型时,就已经确定顺序栈所占空间,此处空间为一块连续的存储单元; (2)而确定空间之后,经过后续不断有元素进栈,栈中的元素位置会发生变化,同时可能...
  • 图的两种存储结构及其互相转换

    千次阅读 2017-11-11 10:36:17
    图的存储结构除了要存储 图中各个顶点本身的信息,还要存储边的信息。 常见的图的存储结构有邻接矩阵和邻接表。 邻接矩阵是表示顶点之间相邻关系的矩阵。 图的邻接矩阵是唯一的,适于存储边的数目较多的稠密图。...
  • 广义表的存储结构(2)详解

    千次阅读 多人点赞 2019-03-17 19:49:21
    由于广义表中既可存储原子(不可再分的数据元素),也可以存储子表,因此很难使用顺序存储结构表示,通常情况下广义表结构采用链表...由于广义表中可同时存储原子和子表两种形式的数据,因此链表节点的结构也有两种...
  • 数据结构大致包含以下几种存储结构: 线性表,还可细分为顺序表、链表、栈和队列; 树结构,包括普通树,二叉树,线索二叉树等; 图存储结构; 线性表 线性表结构存储的数据往往是可以依次排列的,就像小朋友手拉手...
  • 树的三种存储结构

    万次阅读 多人点赞 2017-03-19 19:46:38
    之前我们一直在谈的是一对一的线性结构,可现实中,还有很多一对多的情况需要处理,所以我们需要研究这种一对多的数据结构----"树",考虑它的各种特性,来解决我们在编程中碰到的相关问题。 树(Tree)是n(n>=0)个...
  • 1.线性表是最简单也是最常用的一数据结构。线性表的例子不胜枚举,例如,英文字母表就是一个线性表,表中的英文字母是一个数据元素。 2.线性表的定义:线性表是具有相同特性的数据元素的一个有限序列。 3.线性表...
  • 二叉树的存储结构

    千次阅读 2020-09-21 10:53:33
    二叉树的存储结构可以分为顺序存储和链式存储两种存储结构。 二 顺序存储结构 二叉树的顺序存储结构是指用一组地址连续的存储单元依次自上而下,自左至右存储完全完全二叉树上的结点元素,即将完全二叉树上编号为i...
  • 数据结构方面的储存结构分类 顺序存储方法它是把逻辑上相邻的结点存储在物理位置相邻的存储单元里,结点间的逻辑关系由存储单元的邻接关系来体现,由此得到的存储表示称为顺序存储结构。顺序存储结构是一最基本的...
  • 队列分为顺序存储结构和链式存储结构,链式存储结构其实就是线性表的单链表,只是只能在对头出元素,队尾进元素而已。从之前实现的队列的顺序存储结构中 我们可以看到他的缺点,我们为了避免“假溢出”就实现循环...
  • 树的三种存储结构(详细基础)

    万次阅读 多人点赞 2019-06-21 10:53:14
    之前我们一直在谈的是一对一的线性结构,可现实中,还有很多一对多的情况需要处理,所以我们需要研究这种一对多的数据结构----"树",考虑它的各种特性,来解决我们在编程中碰到的相关问题。 树(Tree)是n(n>=0)个...
  • 什么是数据结构

    千次阅读 2019-06-19 20:25:39
    数据结构是指相互之间存在一或多种特定关系的数据元素的集合。通常情况下,精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。 定义 名词定义 数据结构是指...
  • 数据结构之树的三种存储结构

    万次阅读 2014-04-28 23:36:21
    说道存储结构,我们就会
  • 队列的两种存储方式的介绍与实现

    千次阅读 2017-07-31 14:38:03
    简介 队列是一特殊的线性表,它的特殊之处在于它必须在队列的头部进行...队列的存储的数据称为队列元素,因为只能在对头进行删除的操作,队尾进行插入,先插入的先出队,所以我们可以称队列为一先进先出(FIFO:first
  • 数据库的存储结构

    千次阅读 2021-01-06 21:52:44
    数据库中数据的储存主要有两种方式,一种是行存储,一种是列存储。 行存储,就是数据库中的一行数据存储在一段连续的磁盘块上。同理,列存储,就是一列数据存储在一起。 行存储的优点就是,单挑记录集中,适合事务...
  • 串的3种存储结构

    千次阅读 2015-05-28 13:05:13
    第一种存储结构:顺序存储 这种存储结构里没有包含指针,比如说: String S[101];//其中S[0]存储S的长度 第二种存储结构:堆存储结构 这种存储结构一般包含一个头结点,比如说: typedef struct{ Node *head; ...
  • 树和森林6.7 树和森林的实现6.7.1 树的存储结构1.双亲表示法2.孩子表示法3.双亲-孩子表示法4. 孩子-兄弟表示法总结6.7.2 树、森林和二叉树的转换1. 树转化为二叉树2. 森林转化为二叉树3. 二叉树转化为森林6.7.3 树的...
  • 广义表存储结构|数据结构

    千次阅读 2019-10-27 10:19:24
    由于广义表的数据元素可以分为原子和广义表,由此需要两种结构的结点,一种是表结点(广义表),一种是原子结点(原子)。 非空广义表可以分解为表头和表尾。 1、表头和表尾 表头:非空广义表的第一个元素,可以...
  • 顺序存储在计算机中用一组地址连续的存储单元依次存储线性表的各个数据元素,称作线性表的顺序存储结构。特点:随机存取表中元素。插入和删除操作需要移动元素。链接存储在计算机中用一组任意的存储单元存储线性表的...
  • 线性表之顺序存储和链式存储结构

    千次阅读 2020-11-27 11:36:34
    线性表有两种物理存储结构:顺序存储结构和链式存储结构 线性表插入操作 插入算法的思路: 1、如果插入位置不合理,抛出异常 2、如果线性表长度大于等于数组长度,则抛出异常或动态增加数组容量 3、从最后一个元素...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,316,449
精华内容 526,579
关键字:

常用的两种存储结构