精华内容
下载资源
问答
  • 二叉树的顺序存储结构

    千次阅读 2021-02-05 10:01:58
    一、顺序存储结构 二叉树的顺序存储结构是指用一组地址连续的存储单元依次自上而下、自左至右存储完全二叉树上的结点元素,即将完全二叉树上编号为 i 的结点元素存储在一维数组下标为 i-1 的分量中。 依据二叉树的...

    一、顺序存储结构

    二叉树的顺序存储结构是指用一组地址连续的存储单元依次自上而下、自左至右存储完全二叉树上的结点元素,即将完全二叉树上编号为 i 的结点元素存储在一维数组下标为 i-1 的分量中。

    依据二叉树的性质,完全二叉树和满二叉树采用顺序存储比较合适,树中结点的序号可以唯一地反映结点之间的逻辑关系,这样既能最大地节省存储了空间,又能利用数组元素的下标值确定结点在二叉树中的位置,以及结点之间的关系。

    从数据存储来看,数组存储方式和树的存储方式可以相互转换,即数组可以转换成树,树可以转换成数组。

    二、顺序存储二叉树的特点

    1、顺序二叉树通常只考虑完全二叉树和满二叉树
    2、 第n个元素的左子结点为 2 * n + 1
    3、第n个元素的右子结点为 2 * n + 2
    4、 第n个元素的父结点为 (n-1) / 2
    n表示二叉树中的第几个元素,按0开始编号

    在这里插入图片描述
    例如,第一个元素2的左子结点为 21+1=3,即为第三个元素4;右子结点为 21+2=4,即为第四个元素5;父结点为(1-1) / 2=0,即为第零个元素1。

    三、遍历顺序存储二叉树

    package Tree;
    
    public class ArrayBinaryTree {
    
    	public static void main(String[] args) {
    		int[] arr= {1,2,3,4,5,6,7};
    		ArrBinaryTree arrBinaryTree=new ArrBinaryTree(arr);
    		System.out.println("顺序存储二叉树的前序遍历");
    		arrBinaryTree.preOrder(0);
    		System.out.println();
    		System.out.println("顺序存储二叉树的中序遍历");
    		arrBinaryTree.inOrder(0);
    		System.out.println();
    		System.out.println("顺序存储二叉树的后序遍历");
    		arrBinaryTree.postOrder(0);
    		System.out.println();
    
    	}
    }
    
    class ArrBinaryTree{
    	int[] arr;//用于存储数据结点的数组
    	
    	public ArrBinaryTree(int[] arr) {//ArrBinaryTree构造函数
    		this.arr=arr;
    	}
    	
    	//顺序存储二叉树的前序遍历(根->左->右)
    	public void preOrder(int index) {
    		if(arr==null||arr.length==0) {//如果数组为空,或者数组长度为零无法遍历
    			System.out.println("数组为空,不能执行二叉树的前序遍历");
    		}
    		
    		System.out.printf(arr[index]+" ");//打印当前结点
    		if((index*2+1)<arr.length) {//当前结点的左子结点没有越界则向左递归前序遍历
    			preOrder(index*2+1);
    		}
    		if((index*2+2<arr.length)) {//当前结点的右子结点没有越界则向右递归前序遍历
    			preOrder(index*2+2);
    		}
    	}
    	//顺序存储二叉树的中序遍历(左->根->右)
    	public void inOrder(int index) {
    		if(arr==null||arr.length==0) {//如果数组为空,或者数组长度为零无法遍历
    			System.out.println("数组为空,不能执行二叉树的中序遍历");
    		}
    		
    		if((index*2+1)<arr.length) {//当前结点的左子结点没有越界则向左递归前序遍历
    			preOrder(index*2+1);
    		}
    		System.out.printf(arr[index]+" ");//打印当前结点
    		if((index*2+2<arr.length)) {//当前结点的右子结点没有越界则向右递归前序遍历
    			preOrder(index*2+2);
    		}
    	}
    	
    	// 顺序存储二叉树的后序遍历(左->右->根)
    	public void postOrder(int index) {
    		if(arr==null||arr.length==0) {//如果数组为空,或者数组长度为零无法遍历
    			System.out.println("数组为空,不能执行二叉树的中序遍历");
    		}
    		
    		if((index*2+1)<arr.length) {//当前结点的左子结点没有越界则向左递归前序遍历
    			preOrder(index*2+1);
    		}
    		if((index*2+2<arr.length)) {//当前结点的右子结点没有越界则向右递归前序遍历
    			preOrder(index*2+2);
    		}
    		System.out.printf(arr[index]+" ");//打印当前结点
    	}
    }
    

    运行结果:

    顺序存储二叉树的前序遍历
    1 2 4 5 3 6 7 
    顺序存储二叉树的中序遍历
    2 4 5 1 3 6 7 
    顺序存储二叉树的后序遍历
    2 4 5 3 6 7 1 
    
    展开全文
  • 顺序存储结构定义与特点 定义 把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构。 基地址(首地址,起始位置):线性表的第1个数据元素a1a_1a1​的存储位置。 特点 地址连续 例如, ...

    顺序存储结构定义与特点

    • 定义
      把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构。
      在这里插入图片描述
      基地址(首地址,起始位置):线性表的第1个数据元素 a 1 a_1 a1的存储位置。

    • 特点

    地址连续
    例如,
    在这里插入图片描述
    线性表顺序存储结构占用一片连续的存储空间,知道某个元素的存储位置就可以计算其他元素的存储位置。

    假设线性表的每个元素需占 l l l个存储单元,则有如下两个公式:
    L O C ( a i + 1 ) = L O C ( a i ) + l LOC(a_{i+1})=LOC(a_i)+l LOC(ai+1)=LOC(ai)+l
    L O C ( a i ) = L O C ( a 1 ) + ( i − 1 ) ∗ l LOC(a_i)=LOC(a_1)+(i-1)*l LOC(ai)=LOC(a1)+(i1)l
    上述计算存储结构的时间复杂度为 O ( 1 ) O(1) O(1)
    在这里插入图片描述
    两大特点:

    • 以物理位置相邻表示逻辑关系
    • 任一元素均可随机存取
    C语言描述—数组

    顺 序 表 ( 元 素 ) { 地 址 连 续 依 次 存 放 随 机 存 取 类 型 相 同 ⇒ 用 一 维 数 组 表 示 顺 序 表 顺序表(元素)\begin{cases} 地址连续\\ 依次存放 \\ 随机存取\\ 类型相同\\ \end{cases} \Rightarrow 用一维数组表示顺序表 ()
    但在C语言中数组的长度不可动态定义,而线性表的表长是可变的(插入、删除等操作)。
    在这里插入图片描述
    所以,用一变量表示顺序表的长度属性
    在这里插入图片描述
    这里用一个数组和一个长度值定义一个顺序表。
    例子,

    • 多项式
      在这里插入图片描述
    • 图书表
      在这里插入图片描述
    展开全文
  • 线性表(线性存储结构)线性表是最基本、最简单、也是最常用的一种数据结构。它是数据结构与算法的基础之一。例如26个英文字母表:(A,B,C,D,···,Z)或者学生基本信息表又或者十二星座的排序等等,它们都是...

    线性表(线性存储结构)线性表是最基本最简单、也是最常用的一种数据结构。它是数据结构与算法的基础之一。例如26个英文字母表:(A,B,C,D,···,Z)或者学生基本信息表又或者十二星座的排序等等,它们都是线性表。

    一.线性表的定义和特点

    线性表(linear
    list):是n个具有相同特性的数据元素的有限序列。数据元素是一个抽象的符号,其具体含义在不同的情况下一般不同。
    n的个数代表线性表的长度,当n = 0时,称为空表

    对于非空的线性表或线性结构,其特点是:

    • 存在唯一的一个被称作“第一个”的数据元素;
    • 存在唯一的一个被称作“最后一个”的数据元素;
    • 除第一个之外,结构中的每个数据元素均只有一个前驱;
    • 除最后一个之外,结构中的每个元素均只有一个后继;
    对于前驱和后继

    某一元素的左侧相邻元素称为“直接前驱”,位于此元素左侧的所有元素都统称为“前驱元素”;
    某一元素的右侧相邻元素称为“直接后继”,位于此元素右侧的所有元素都统称为“后继元素”;

    以图数据中的元素 3 来说,它的直接前驱是 2 ,此元素的前驱元素有 2 个,分别是 1 和 2;同理,此元素的直接后继是 4 ,后继元素也有 2 个,分别是 4 和 5。如图所示:
    在这里插入图片描述

    二.线性表的基本操作

    1. InitList(&L):构造一个空的线性表L。
    2. DestroyList(&L):销毁线性表L。
    3. ClearList(&L):将线性表L重置为空表。
    4. ListEmpty(&L):若L为空表,则返回true,否则返回false。
    5. ListLength(&L):返回L中的数据元素的个数。
    6. GetElem(L,i,&e):用e返回L中第i个数据元素的值。
    7. LocateElem(L,e):返回L中第一个值与e相同的元素在L中的位置。若此数据元素不存在,则返回值为0。
    8. PrioElem(L,cur_e,&pre_e):若cur_e是L的数据元素,且不是第一个,则用pre_e返回其前驱,否则操作失败,pre_e无定义。
    9. NextElem(L,cur_e,&next_e):若cur_e是L的数据元素,且不是最后一个,则用next_e返回其后继,否则操作失败,next_e无定义。
    10. ListInsert(&L,i,e):在L中第i个位置之前 插入新的元素e,L的长度加1。
    11. ListDelet(&L,I):删除L的第i个数据元素,L的长度减1。
    12. TraverseList(L):对线性表L进行遍历,在遍历过程中对L的每一个结点访问一次。

    线性表根据在计算机的储存方式可以分为两种:

    • 顺序线性表
    • 链式线性表

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

    1.顺序表的定义

    • 所谓顺序表就是顺序存储的线性表。顺序存储是用一组地址连续的存储单元依次存放线性表中各个元素的存储结构。

    2.顺序表的特点

    • 在线性表中逻辑上相邻的数据元素,在物理存储上也是相邻的。
    • 存储密度高,但要预先分配“足够应用”的存储空间,这可能会造成存储空间的浪费。
    • 便于随机存储。
    • 不便于插入和删除操作,这是因为在顺序表上进行的插入和删除操作会引起大量数据元素的移动。

    例如,使用顺序表存储集合 {1,2,3,4,5}数据最终的存储状态如图所示

    在这里插入图片描述
    线性表的顺序存储的结构代码:

    #define MAXSIZE 20 //存储空间初始分配量
     typedef int ElemType;//ElemType根据实际情况而定,这里假设为int
     typedef struct
     {
         ElemType data[MAXSIZE];//数组存储数据元素,最大值为MAXSIZE
         int length;//线性表当前长度
     }SqList;
    

    描述顺序存储结构需要三个属性:

    • 存储空间的起始位置:数组data,它的存储位置就是存储空间的存储位置。
    • 线性表的最大存储容量:数组长度MaxSize。
    • 线性表的当前长度:length。

    线性表长度和数组长度的区别:

    数组长度是存放线性表的存储空间的长度,存储空间分配完一般是不变的。

    线性表长度是线性表中元素数据的个数,随着线性表插入和删除操作的进行,这个量是变化的。

    在任意时刻,线性表的长度应该小于等于数组的长度。

    3.顺序表中基本操作的实现

    3.1 初始化

    顺序表的初始化操作就是构造一个空的顺序表

    算法:顺序表的初始化

    status InitList(SqList &L)
    {//构造一个空的顺序表L
       L.elem = new ElemType[MAXSIZE];  //为顺序表分配一个大小为MAXSIZE的数组空间
       if(!L.elem) exit(OVERFLOW);    //存储分配失败退出
       L.lengh = 0;         //空表长度为0;
       return OK;
    

    3.2 取值

    取值操作是根据指定的位置序号i,获取顺序表中的第i个数据元素的值。

    算法:顺序表的取值

    Status GetElem(SqList L,int i, ElemType &e)
    {
    	if (i<1||i>L.length) return ERROR; //判断i值是否合理,若不合理,则返回ERROR 
    	
    	e = L.elem[i-1];   //elem[i-1]单元存储第i个数组元素 
    	
    	return OK;
    }
    

    该算法的时间复杂度为O(1)。

    3.3 查找

    查找顺序表中第一个值与e相同的元素在L中的位置。若此数据元素不存在,则返回值为0;存在即返回位置序号。

    算法:顺序表的查找

    int LocateElem(SqList L, ElemType e) 
    {
    	//在顺序表L中查找值为e的数据元素,返回其序号
    	for(i = 0; i < L.length; i++)
    	  if(L.elem[i] == e) {
    	  	return i+1;      // 查找成功,返回序号+1 
    	  }
    	  return 0;         //查找失败,返回0 
    }
    

    3.4 顺序表的插入
    顺序表中插入数据元素,无非三种情况:

    • 在表头插入;
    • 在表的中间某个位置插入;
    • 直接尾随顺序表,作为表的最后一个元素;

    无论在顺序表的什么位置插入数据元素,解决办法都是:找到要插入的位置,将后续数据元素整体向后移动一个位置,最后直接在腾出来的位置上插入指定的数据元素。

    Status ListInsert(SqList &L, int i ,ElemType e)
    {
    	// 在顺序表L中第i个位置插入新的元素e,i的合法范围是1<=i<=L.length+1
    	if((i<1)||(i>L.length+1)) return ERROR;  //i的值不合法
    	if(L.length == MAXSIZE) return ERROR;   //当前存储空间已满
    	for(j = L.length-1; j >= i-1; j--){
    		L.elem[j+1] = L.elem[j];    //插入新位置及之后的元素后移
    		L.elem[i-1] = e;      //将新元素e放入第i个位置
    		++L.length;    //表长加1
    		return OK;
    	} 
     } 
    

    该算法时间复杂度为O(n)。

    3.5 顺序表的删除

    从顺序表中删除指定元素,实现起来非常简单,只需找到目标元素,并将其后续所有元素整体前移 1 个位置,表长减1。

    后续元素整体前移一个位置,会直接将目标元素删除,可间接实现删除元素的目的。

    Status ListDelete(SqList &L,int i)
    {
    	//在顺序表L中删除第i个元素,i值的合法范围是1<=i<=L.length 
    	if((i<1)||(i>L.length)) return ERROR;
    	for(j = i; j <= L.length-1; j ++)
    	{
    		L.elem[j-1] = L.elem[j]; //被删除元素之后的元素前移 
    		--L.length;     //表长减1 
    		return OK;
    	}
     } 
    

    接下篇
    数据结构基础(二)——线性表之链式存储结构

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

    万次阅读 多人点赞 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

    展开全文
  • 线性表(List):由零个或多个数据元素组成的有序结构。 若线性表记为(a1,……,ai-1,ai,ai+1,……an),则表中ai-1领先于ai领先于ai+1,称ai-1是ai的直接前驱元素,ai+1是ai的后继元素。 例子: 请问公司的组织...
  • 顺序存储结构

    万次阅读 2018-02-01 18:41:59
    2. 顺序存储结构 答:线性表的顺序存储结构,指的是用一段地址连续的存储单元依次存储线性表的数据元素。     3. 顺序存储结构需要三个属性: ■ 存储空间的起始位置:数组data,它的存储位置就是存储空间...
  • 线性表之顺序存储结构和链式存储结构

    万次阅读 多人点赞 2018-09-28 14:17:06
    顺序存储结构和链式存储结构有所不同,具体区别如下表所示: 通过上面的对比,可以得出一些经验性的结论: 若线性表需要频繁查找,很少进行插入和删除操作时,宜采用顺序存储结构。若需要频繁插入和删除时,宜...
  • 全书链接: 408笔记——数据结构(C语言版)(将书上例题用C语言列出来,可以直接在IDE(Xcode)上运行)
  • 线性表--顺序存储结构

    千次阅读 2018-03-08 14:05:00
    一、线性表的顺序存储结构 线性表有两种物理存储结构:顺序存储结构和链式存储结构。 顺序存储结构 ①定义: 用一段地址连续的存储单元依次存储线性表的数据元素。 ②线性表(a1,a2,…,an)的顺序存储如下: ...
  • 1、基本概念 数据:是描述客观事物的符号,是计算机中可以操作的对象,是能被计算机识别,并输入给计算机处理的符号集合。 包含有整型、实型等数值类型;...数据结构:是相互之间存在一种或多种特定关系的数...
  • 顺序表的特点是逻辑上相邻的数据元素,物理存储位置也相邻,并且,顺序表的存储空间需要预先分配。 它的优点:  (1)方法简单,各种高级语言中都有数组,容易实现。  (2)不用为表示节点间的逻辑关系而增加...
  • 线性表的顺序存储结构及实现

    千次阅读 2020-11-21 01:21:21
    线性表的顺序存储结构定义 线性表的介绍 线性表的顺序存储称为顺序表(sequential list),其基本思zhunc想是用一段地址连续存储单元的存循单元依次存储线性表的数据元素,则第,如图1所示。设顺序表的每个元素占用c...
  • 一:线性表的顺序存储结构 1.定义 2.顺序存储示意图如下所示: 3.编号地址 4.存储位置公式 5.存取操作时间性能 6.随机存储结构 7.时间复杂度 (1)对于存取操作 (2)对于插入和删除操作 8. 使用场景 二...
  • 数据结构(16)队列的顺序存储结构

    千次阅读 2020-05-27 14:07:47
    1、队列的顺序存储 队列的顺序实现是指分配一块连续的存储单元存放队列中的元素,并附设两个指针:队头指针front指向队头元素。队尾指针rear指向队尾元素的下一个位置(其实和单链表有无头结点是一样的,队尾指针你...
  • 链表的组成部分以及和顺序存储结构的区别线性表顺序存储结构链式存储结构链表内存存储结构链表的组成结点头节点,头指针和首元节点两种存储结构的特点 线性表 线性表是最基本、最简单、也是最常用的一种数据结构。...
  • 队列的顺序存储结构

    千次阅读 2018-05-05 16:11:55
    队列的顺序存储结构:要预先分配内存,知道队列的最大长度。初始化队列时Q.rear=Q.front=0;对尾插入队列元素rear+1,对头删除队列元素front+1,假设当前为队列分配的最大空间为6,则当队列处于图(d)时,再插入元素...
  • 1.顺序存储结构特点: 线性表的逻辑结构与存储结构一致。用数据元素的存储位置标示相邻数据元素之间的前后关系。 可以对数据元素进行随机储存。访问线性表时,可以利用上述给出的数学公式,快速地计算出任何一个...
  • 数据结构 - 顺序存储结构和链式存储结构 顺序存储结构 顺序存储中,相邻数据元素的存放地址也相邻,内存中存储单元的地址必须是连续的,存储密度 = 1。 优点: 不用为表示节点间的逻辑关系而...
  • 算法设计的要求时间效率高存储量低顺序存储结构和链式存储结构的区别链表存储结构的内存地址不一定是连续的,但顺序存储结构的内存地址一定是连续的;链式存储适用于在较频繁地插入、删除、更新元素时,而顺序存储...
  • 本节先介绍二叉树的顺序存储结构。 二叉树的顺序存储,指的是使用顺序表(数组)存储二叉树。需要注意的是,顺序存储只适用于完全二叉树。换句话说,只有完全二叉树才可以使用顺序表存储。因此,如果我们想顺序存储...
  • 单链表结构和顺序存储结构的优缺点 存储的分配方式 顺序存储结构:需要用一串连续的空间存储,对内存比较要求比较苛刻 链式存储结构:存储的空间不连续,十分灵活 时间性能 查找: 顺序存储结构查找的时间复杂度为O...
  • 数据结构—二叉树的顺序存储结构

    千次阅读 2019-11-24 22:15:27
    二叉树的顺序存储结构 二叉树的顺序存储结构就是用一维数组存储二叉树中的节点,并且节点的存储位置(下标)应能体现节点之间的逻辑关系——父子关系。 普通二叉树需按照完全二叉树的编号方式编号,然后以完全二叉树...
  • 线性表之顺序存储和链式存储结构

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

    千次阅读 2018-12-13 20:01:48
    线性表的顺序存储结构称为顺序表。 顺序表是用一段地址连续的存储单元依次存储线性表的数据元素,因为线性表中每个元素的类型相同,通常用一维数组来实现线性表,也就是把线性表中相邻的元素存在数组中相邻的位置...
  • 线性结构又分为顺序存储和链式存储,顺序存储:各个元素存储的地址空间连续,逻辑相邻的元素在物理内存中也相邻,如数组; 链式存储:各个元素存储在任意的地址空间,逻辑相邻的元素在物理内存中没有联系,如链表。...
  • 顺序存储结构和链式存储结构的优缺点

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

    千次阅读 2020-03-23 11:59:57
    与前面所讲的线性表的顺序存储结构类似,可用一组地址连续的存储单元存储串的字符序列。 定长顺序串存储结构 #include <stdio.h> #define MAXLEN 40 /*MAXLEN 表示串的最大长度*/ typedef struct { char ch...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 303,678
精华内容 121,471
关键字:

顺序存储结构的特点

友情链接: ADO Data.rar