精华内容
下载资源
问答
  • 顺序存储
    千次阅读
    2021-02-05 10:01:58

    一、顺序存储结构

    二叉树的顺序存储结构是指用一组地址连续的存储单元依次自上而下、自左至右存储完全二叉树上的结点元素,即将完全二叉树上编号为 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) 掌握顺序存储线性表结构的定义 (2) 掌握顺序存储线性表结构的相关操作 (3) 掌握顺序表的特点
  • 线性表的顺序存储与实现。采用顺序存储的方式实现线性表,并实现了一些基本功能,包括创建、销毁、清空、插入等一些常规的操作。
  • 实现线性表的顺序存储结构、链式存储结构,以及定义在上述结构的基本操作,栈的顺序存储结构、链式存储结构,以及定义在上述结构的基本操作
  • 二叉树的顺序存储

    2015-11-17 21:11:08
    C语言实现二叉树的顺序存储
  • 本讲主要讲述二叉树的顺序存储结构思想,和类主要的顺序存储方法。
  • 线性表的顺序存储线性表的顺序存储线性表的顺序存储线性表的顺序存储线性表的顺序存储线性表的顺序存储线性表的顺序存储
  • 一,实验目的 1,掌握用Visual C++6.0上机调试顺序表的基本方法 ...[基本要求] 要求生成顺序表时,可以键盘上读取元素,用顺序存储结构实现存储. [实现提示] 要实现基本操作,可用实现的基本操作,也可设计简单的算法实现.
  • 数据结构之顺序存储与链式存储

    千次阅读 2020-11-25 19:27:43
    线性表,全名为线性存储结构。 线性表是n个数据特性相同的元素的组成有限序列,是最基本且常用的一种线性结构(线性表,栈,队列,串和数组都是线性结构),同时也是其他数据结构的基础。具有“一对一”逻辑关系的...

    定义

    线性表,全名为线性存储结构。

    线性表是n个数据特性相同的元素的组成有限序列,是最基本且常用的一种线性结构(线性表,栈,队列,串和数组都是线性结构),同时也是其他数据结构的基础。具有“一对一”逻辑关系的数据,最佳的存储方式是使用线性表。

    特点

    • 是一个有限的序列
    • 可以是有序的也可以是无序的。
    • 线性表的开始元素没有前驱元素只有后继元素,线性表的结束元素没有后继元素只有前驱元素,除了开头元素和结尾元素以外,每个元素都有且只有一个前驱元素和后继元素。

    前驱和后继

    数据结构中,一组数据中的每个个体被称为“数据元素”(简称“元素”)。

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

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

    存储结构

    线性表存储结构分为顺序存储结构链式存储结构,前者称为顺序表,后者称为链表。

    顺序存储结构

    定义

    顺序表就是把线性表中的所有元素按照某种逻辑顺序,依次存储到从指定位置开始的一块连续的存储空间。

    特点

    逻辑上相邻的数据元素,物理次序也是相邻的。

    只要确定好了存储线性表的起始位置,线性表中任一数据元素都可以随机存取,所以线性表的顺序存储结构是一种随机存取的储存结构,因为高级语言中的数组类型也是有随机存取的特性,所以通常我们都使用数组来描述数据结构中的顺序储存结构,用动态分配的一维数组表示线性表。

    **数组长度和线性表的长度区别:**数组长度是存放线性表的存储空间的长度,存储分配后这个量一般是不变的,线性表的长度是线性表中数据元素的个数,随着线性表插入和删除操作的进行,这个量是变化的。

    优缺点

    优点缺点
    无需为表示表中元素之间的逻辑关系而增加额外的存储空间插入和删除操作需要移动大量元素
    可快速的存取表中的任一位置元素当线性表长度变化比较大时,难以确定存储空间的容量
    容易造成存储空间碎片

    基本操作

    结构体定义

    顺序表可以分为静态分配和动态分配两种:

    • 静态分配
    #define MaxSize 50  / /顺序表的最大长度
    typedef struct{		// typedef类型重命名
        ElemType data[MaxSize]; // 顺序表的元素,ElemType是未明确的数据类型,使用时可以用typedef定义具体类型
        int length;				// 长度
    }SqList;
    

    静态分配方法需要预先分配一段固定大小的连续空间,但在运算过程中,进行插入,合并等操作时,容易超过预分配的空间长度,出现溢出问题。

    • 动态分配
    #define InitSize 50  // 顺序表的初始长度
    typedef struct{		// typedef类型重命名
        ElemType *data; // 指向动态分配数组的指针,基地址,*取内容
        int MaxSize;	// 数组的最大容量
        int length;	// 数组的当前个数
    }SeqList;
    // 定义SqList类型的变量
    SqList L;
    L.data = (ElemType*)malloc(sizeof(ElemType)*InitSize);
    

    初始化

    struct SqList{
    	int data[MaxSize]; // 存放顺序表的元素
    	int length; // 存放顺序表的长度
    	int last;
    };
    
    void Init(SqList *L){
    	L->data[0] = int(malloc(MaxSize * sizeof(int)));
    	int n, i = 0;
    	cin >> n;
    	L->length = n;
    	while (i < n)
    	{
    		cin >>(L->data[i++]);
    	}
    	L->last = i - 1;
    }
    

    插入

    bool InsertList(SqList &L, int i, int e)
    {
    	// 在顺序表中第i个位置(位序,不是下标)插入数值e
    	int j;
    	if (i<1 || i>L.length+1) // 是否越界
    		return false;
    	if (L.length == MaxSize)// 内存已满
    		return false;
    	L.length++;            // 长度++
    	for (j = L.length; j >= i; j--) // 将第i个起的数据后移
    		L.data[j] = L.data[j - 1];
    	L.data[j] = e;
    	return true;
    }
    

    删除

    bool DeleteList(SqList&L, int i)
    {
    	// 删除顺序表中第i个元素
    	int j;
    	if (i<1 || i>L.length)
    		return false;   // 判断越界
    	for (j = i; j < L.length; j++)
    		L.data[j - 1] = L.data[j];
    	L.length--;
    	return true;
    }
    

    查找

    bool LocateElem(SqList L, int e)
    {
    	int i;
        for(i = 0; i < L.length; i++){
            if(L.data[i] == e){
                return i+1;
            }
        }
        return 0;
    }
    

    链式存储结构

    又称为链表,用于存储逻辑关系为 “一对一” 的数据。

    用一组任意的存储单元存储线性表的数据元素(这组存储单元可以是连续的,也可以是不连续的),包括数据域和指针域,数据域存数据,指针域指示其后继的信息。

    1、单链表

    节点

    一个完整的链表需要由以下几部分构成:

    1. **头指针:**一个普通的指针,它的特点是永远指向链表第一个节点的位置。很明显,头指针用于指明链表的位置,便于后期找到链表并使用表中的数据;

    2. 节点:链表中的节点又细分为头节点、首元节点和其他节点:

      • **头节点:**其实就是一个不存任何数据的空节点,通常作为链表的第一个节点。对于链表来说,头节点不是必须的,它的作用只是为了方便解决某些实际问题;
      • **首元节点:**由于头节点(也就是空节点)的缘故,链表中称第一个存有数据的节点为首元节点。首元节点只是对链表中第一个存有数据节点的一个称谓,没有实际意义;
      • **其他节点:**链表中其他的节点;

    在这里插入图片描述

    链表中有头节点时,头指针指向头节点;反之,若链表中没有头节点,则头指针指向首元节点。

    基本操作

    结构体定义

    typedef struct Lnode{	
    	ElemType data; 
    	struct Lnode *next;
    }LNode,*LinkList
    

    初始化

    单链表的初始化是指构建一个空表。先创建一个空结点,不存放数据,然后令其指针域为空;

    bool InitList_L(LinkList &L){
    	L = new Lnode; 
    	if(!L) return false;
    	L -> next = NULL;
    	return true;
    }
    

    创建

    创建单链表分为头插法和尾插法两种。

    • 头插法:是指每次将新结点插入到头结点之后,其创建的单链表和数据输入的顺序正好相反,因此也称为逆序建表。
    void CreateList_H(LinkList &L){
    	int n;
    	LinkList s;
    	L = new LNode;
    	L -> next = NULL;
    	cin>>n;
    	while(n--){
    		s = new LNode;
    		cin>>s->data;
    		s->next = L->next;
    		L->next = s;
    	}
    }
    
    • 尾插法:是指每次把新结点链接到链表的尾部,其创建的单链表和数据输入顺序一致,因此也称为正序建表。
    void CreatList_R(LinkList &L){	
    	int n;
        LinkList s, r;
        L = new Lnode;
        L -> next = NULL;
        r = L;
        cin>>n;
        while(n--){
    		s = new LNode; 
            cin >> s->data;
            s -> next = NULL; 
            r -> next = s;
            r = s; 
        }
    }
    

    按序取值
    从单链表的第一个结点出发,顺指针逐个往下搜索,知道找到第i个结点为止,否则返回最后一个结点的指针NULL。

    LinkList GetElem(LinkList L, int i){
    	int j = 1; 
        LinkList p = L -> next;
        if(i == 0) return L;
        if(i < 1) return NULL;
        while(p && j<i){
            p = p->next;
            j++;
        }
        return p;
    }
    

    插入结点

    p = GetElem(L, i-1);
    s -> next = p -> next;
    p -> next = s;
    

    删除结点

    p = GetElem(L, i-1);
    q = p -> next;
    p -> next = q -> next;
    

    2、静态链表

    静态链表,兼顾了顺序表和链表的优点于一身。

    使用静态链表存储数据,数据全部存储在数组中(和顺序表一样),但存储位置是随机的,数据之间"一对一"的逻辑关系通过一个整形变量(称为"游标",和指针功能类似)维持(和链表类似)。

    3、双向链表

    在单链表的基础上,再在每个结点中设置一个指向其前驱结点的指针域,这样一个结点既可以指向它的前面又可以指向它的下一个,我们把这种链表称为双向链表。

    4、循环链表

    将单链表中终端结点的指针端由空指针改为指向头结点,就使整个单链表形成一个环,这种头尾相接的单链表称为单循环链表,简称循环链表。

    顺序存储和链式存储比较

    • 顺序表只需知道第一个元素的位置,就可以通过起始位置的偏移去获取顺序表中的任何元素(随机访问),而链表的存储结构是一个元素中包含下一个数据元素的位置信息,下一个包含下下一个,也就是每个数据元素之间都是单线联系的,你要想知道最后一个元素在哪里,你必须从头走到尾才可以,所以链表是不支持随机访问的。
    • 顺序表中的数据元素是存放在一段地址连续的空间中,且这个存储空间是提前分配的,一旦分配好了,在对其进行操作的过程中是不会更改的。而链表支持存储空间动态分配。
    • 顺序表在插入删除一个元素的时候需要移动大量元素。而链表在插入和删除一个元素时,不需要移动大量元素,只需要更改插入位置的指针指向就可以。

    本篇完

    展开全文
  • 线性表顺序存储demo

    2016-07-30 10:42:25
    线性表顺序存储demo,实现了线性表顺序存储的基本操作
  • C语言线性表顺序存储结构实例详解 1、 什么是顺序存储结构? 用一段地址连续的存储单元依次存储线性表的数据元素。 2、线性表的顺序存储结构 #include #include #define Max 80 //存储空间初始分配量 #define ...
  • 线性表的顺序存储结构

    千次阅读 2021-10-21 22:05:32
    顺序存储定义 说这么多的线性表,我们来看看线性表的两种物理结构的第一种——顺序存储结构。 线性表的顺序存储结构,指的是用一段地址连续的存储单元依次存储线性表的数据元素。线性表(a1,a2……,an)的顺序存储示意...

    顺序存储定义

    说这么多的线性表,我们来看看线性表的两种物理结构的第一种——顺序存储结构。
    线性表的顺序存储结构,指的是用一段地址连续的存储单元依次存储线性表的数据元素。线性表(a1,a2……,an)的顺序存储示意图如下:

    在这里插入图片描述

    顺序存储方式

    线性表的顺序存储结构,说白了,就是在内存中找了块地儿,通过占位的形式,把一定内存空间给占了,然后把相同数据类型的数据元素依次存放在这块空地中。既然线性表的每个数据元素的类型都相同,所以可以用C语言(其他语言也相同)的一维数组来实现顺序存储结构,即把第一个数据元素存到数组下标为0的位置中,接着把线性表相邻的元素存储在数组中相邻的位置。

    线性表中,我们估算这个线性表的最大存储容量,建立一个数组,数组的长度就是这个最大存储容量。但在实际使用中,我们并不是每个时刻都使用这最大的存储容量,我们希望能够更加高效的使用空间,因此我们使用malloc申请空间,realloc来调整空间大小,做到此点。可看空间分配与释放来具体了解函数作用。

    来看线性表的顺序存储的结构代码。

    #define INITSIZE 20  //初始化的大小
    #define EXPANDTIMES 2 //每次的扩容倍数
    typedef int ELemType; //用int来模拟数据项类型
    typedef struct
    {
    	ElemType* data; //存储数据的初始位置
    	int capacity; //容量(总共的:未使用的+已经使用的)
    	int size;//已经使用的
    }Sqlist;
    

    关于数组和指针我在这就不多讲了,想要了解的可以去看我的数组与指针

    Init_List(*L)

    bool Init_List(Sqlist *L)
    {
    	assert(L != NULL);//对输入也检测一下,使用空指针可能会导致程序奔溃,具体原因自己去搜,后续不解释
    	L->data = (int*)malloc(sizeof(ELemType) * INITSIZE);//申请一段堆空间来存储元素
    	//assert(L->data != NULL);//因为malloc可能会申请失败,判断一下
    	if (L->data == NULL)
    	{
    		return false;
    	}
    	else
    	{
    		L->capacity = INITSIZE;//初始容量通过宏定义设定
    		L->size = 0;//初始使用的大小当然是0喽
    		return true;
    	}
    }
    

    为了能够拥有动态空间大小,我们在这使用了堆空间作为存储空间,不用了记得free

    Change_List(*L, flag)

    bool Change_List(Sqlist* L,int flag)//改变容量
    {
    	assert(L != NULL);
    	ELemType* temp = L->data;
    	int newsize = flag == -1 ? L->capacity / EXPANDTIMES : L->capacity * EXPANDTIMES;//简单的判断,
    	temp = (ELemType*)realloc(temp,newsize * sizeof(ELemType));//扩容也可能会失败,这样做是防止旧数据丢失
    	if (temp == NULL)
    	{
    		return false;
    	}
    	else
    	{
    		L->data = temp;//将申请到的空间交给data
    		L->capacity = newsize;//更改容量
    		return true;
    	}
    }
    

    Is_Empty(*L)

    bool Is_Empty(Sqlist* L)
    {
    	assert(L != NULL);
    	return L->size == 0;//只用检测一下使用的大小为不为0,就ok
    }
    

    Clear_List(*L)

    bool Clear_List(Sqlist* L)
    {
    	assert(L != NULL);
    	free(L->data);//因为空间是malloc来的,不用就free掉
    	Init_List(L);//最简单的做法,重新给他初始化下,就消除了数据,也缩小了容量
    	//L->size = 0;//最最最简单的方法因为数据是否有效,我们说了算,容量没变
    	return true;
    }
    

    GetElem_List(*L,i)

    ELemType GetElem_List(Sqlist* L, int i)
    {
    	assert(L != NULL && i < L->size && i >= 0);//保证改下标必须为有效下标,后续不解释
    	return L->data[i];
    }
    

    LocateElem_List(*L,e)

    int LocateElem_List(Sqlist* L, ELemType e)
    {
    	assert(L != NULL);
    	int pos = -1;
    	for (int i = 0; i < L->size; i++)//遍历是必须的
    	{
    		if (e == L->data[i])
    		{
    			pos = i;
    			break;
    		}
    	}
    	return pos;
    }
    

    Insert_List(*L,i,e)

    在这里插入图片描述
    图来自大话数据结构

    bool Insert_List(Sqlist* L,int i,ELemType e)
    {
    	assert(L != NULL && i >= 0 && i <= L->size);//为满足线性表的定义,应对下标进行检测
    	if (L->capacity == L->size)//容量不足是需要进行扩容
    	{
    		if (!Change_List(L,1)) //扩容成功才能继续放数据
    		{
    			return false;
    		}
    	}
    	int pos = L->size;
    	while (L->size != i)//向后挪动一位
    	{
    		L->data[pos] = L->data[pos - 1];
    		pos--;
    	}
    	L->data[pos] = e;
    	L->size++;
    	return true;
    }
    

    尾插的话,i=L->size;头插i=0;

    Delect_List(*L, i)

    与插入反向操作

    bool Delect_List(Sqlist* L, int i)//
    {
    	assert(L != NULL && i < L->size && i >= 0);
    	while (i != L->size-1)//向前挪动一位
    	{
    		L->data[i] = L->data[i+1];
    		i++;
    	}
    	L->size--;
    	if (L->capacity > INITSIZE && L->size < L->capacity / EXPANDTIMES)
    		Change_List(L, -1);
    	return true;
    }
    

    Length_List(*L)

    int Length_List(Sqlist* L)
    {
    	assert(L != NULL);
    	return L->size;//我们有专门的数据项来记录长度,直接返回就行
    }
    

    Destory_List(*L)

    因为clear只会清除数据(存储空间有一部分清不掉),我们要专门free掉

    bool Destroy_List(Sqlist* L)
    {
    	L->capacity = 0;
    	L->size = 0;
    	free(L->data);//Destroy以后就彻底不能用了,因为0乘以任何数还是0
    	L->data = NULL;
    	return true;
    }
    

    线性表顺序存储结构的优缺点

    优点

    无须为表示表中元素之间的逻辑关系而增加额外的存储空间。
    可以快速地存取表中任位置的元素。(顺序读取快,O(1));

    缺点

    插入和删除操作需要移动大量元素 O(n)
    当线性表长度变化较大时,难以确定存储空间的容量 (用数组就是这样,所以我们有扩容/缩容)
    造成存储空间的“碎片”(绝大部分时间capacity > size,有一部分空间闲置)

    展开全文
  • 顺序存储二叉树

    千次阅读 2021-01-19 18:25:15
    一、顺序存储二叉树概述 从数据存储来看,数组存储方式和树的存储方式可以相互转换,即数组可以转换成树,树也可以转换成数组。顺序结构存储就是使用数组来储存,一般使用数组只适合表示完全二叉树,因为不完全...

    一、顺序存储二叉树概述

    从数据存储来看,数组存储方式和树的存储方式可以相互转换,即数组可以转换成树,树也可以转换成数组。顺序结构存储就是使用数组来储存,一般使用数组只适合表示完全二叉树,因为不完全二叉树会有空间的浪费。

    下图就是树和数组对应的关系图:

    在这里插入图片描述

    顺序二叉树有下面几个显著的特征(n 表示二叉树中的第几个元素,从 0 开始):

    1. 第 n 个元素的左子节点为第 2 * n + 1 个元素;
    2. 第 n 个元素的右子节点为第 2 * n + 2 个元素;
    3. 第 n 个元素的父节点为第 ( n - 1 ) / 2 个元素。

    我们随便选两个节点来验证其中一个特性。比如 元素2 是第 1 个元素,对应数组中的 arr[1],则根据公式 元素2 的左子节点应当为 2*1+1 = 3,也就是第 3 个元素,对应数组中的 arr[3],刚好与二叉树的第 3 个元素符合。

    二、顺序存储二叉树的操作

    【案例需求】

    已知一个数组为:

    arr = {1,2,3,4,5,6,7}
    

    要求以二叉树前序遍历的方式对数组进行遍历,前序遍历的结果应当为:

    1,2,4,5,3,6,7
    

    【思路分析】

    这个需求实际上是在考察顺序存储二叉树的重要特征:第 n 个元素的左子节点为 2n+1、右子节点为 2n+2。

    根据它的特征我们可以知道:第 0 个元素 arr[0] 的左子节点为 arr[1]、右子节点为 arr[2];第 1 个元素 arr[1] 的左子节点为 arr[3]、右子节点为 arr[4]

    【代码实现】

    利用顺序存储二叉树的公式,我们可以很容易写出对数组以二叉树形式的前序遍历:

    /**
     * 顺序存储二叉树
     */
    class ArrayBinaryTree{
        int[] arr;	// 数组
    
        public ArrayBinaryTree(int[] arr){
            this.arr = arr;
        }
    
        /**
         * 前序遍历:根->左->右
         * @param index 数组索引,也即第几个元素
         */
        public void preOrder(int index){
            System.out.println(arr[index]);  // 先打印根
            if ((index*2+1) < arr.length){	// 判断左子节点是否存在
                preOrder(index*2+1);	// 再打印左子树
            }
            if ((index*2+2) < arr.length){	// 判断右子节点是否存在
                preOrder(index*2+2);	// 最后打印右子树
            }
        }
    }
    

    运行结果如下:

    在这里插入图片描述

    展开全文
  • 数据结构:线性表的顺序存储与链式存储

    千次阅读 多人点赞 2020-02-23 11:27:37
    文章目录一、线性表的基本概念二、动态数组(顺序表)的实现与测试 一、线性表的基本概念 线性表:线性表是零个或者多个数据元素的有限序列,是最常用且最简单的一种数据结构。 特点: (1)存在惟一的一个被称做“第一...
  • 1.二叉树链式存储的定义 首先自己写了个队列类(其实也可以不用); 树节点模板类的定义:data-数据,left-左孩子指针,right-右孩子指针,含参构造函数; 创建结点的函数-GetBTNode()函数 创建一个树节点并分配内存,同时...
  • 线性表的顺序存储的c语言实现,带有注释,简洁明了,一看即懂
  • 二叉树的顺序存储是指用一组地址连续的存储单元依次自上而下、自左至右存储完全二叉树上的节点元素,即将完全二叉树上的编号为i的结点元素存储在一维数组下摆为i-1的分量中。 依据二叉树的性质,完全二叉树和满...
  • 二叉树的存储结构有两种,分别为顺序存储和链式存储
  • 实验一顺序存储线性表的基本运算实验目的掌握线性表的定义、顺序存储的方法及基本操作。实验一顺序存储线性表的基本运算实验目的掌握线性表的定义、顺序存储的方法及基本操作。2掌握将算法在VC++6.0语言环境下实现的...
  • 顺序存储结构小结

    千次阅读 2020-09-13 21:05:48
    线性结构的存储表示主要有两种:顺序存储和链式存储。其中: (1)如果只允许在序列末端进行操作(后进先出,LIFO),这种线性结构称为栈(Stack)。 (2)如果只允许在序列两端进行操作(先进先出,FIFO),这种线性结构称为...
  • 线性表的顺序存储,此程序主要实现线性表的顺序存储,有C++语言实现,还是比较轻易看得懂的!
  • 数据结构 基于顺序存储结构对学生成绩表的设计 课程设计 实验报告.docx数据结构 基于顺序存储结构对学生成绩表的设计 课程设计 实验报告.docx数据结构 基于顺序存储结构对学生成绩表的设计 课程设计 实验报告.docx...
  • 数据结构 基于顺序存储结构对学生成绩表的设计 课程设计 实验报告.pdf数据结构 基于顺序存储结构对学生成绩表的设计 课程设计 实验报告.pdf数据结构 基于顺序存储结构对学生成绩表的设计 课程设计 实验报告.pdf数据...
  • 一、顺序存储结构(也可称为顺序表) 顺序存储结构是存储结构类型中的一种,该结构是把逻辑上相邻的结点存储在物理位置上相邻的存储单元中,结点之间的逻辑关系由存储单元的邻接关系来体现。 顺序表的特点是逻辑上...
  • 顺序存储(顺序表)

    万次阅读 多人点赞 2018-08-25 11:56:23
    1.顺序存储方式 线性表的顺序存储结构,就是在内存中找到一块空间,通过占位的方式,把一定内存空间给占了,然后把相同数据类型的数据元素依次存放在这块空间中,既然线性表的每个数据元素的类型相同,所以C语言...
  • 顺序存储结构实现一元多项式的加法、减法和乘法
  • 简单的线性表顺序存储的示例,代码主要完成在顺序存储中的插入及删除元素的操作。 本程序在VS2008下编译通过
  • 直接插入排序(顺序存储、链式存储),折半插入排序(顺序存储),希尔排序(顺序存储) 插入排序 直接插入排序 将元素插入L[i]插入到已有序的子序列L[i-1]中。其基本思想是每次将一个待排序的记录按其关键字大小...
  • 线性表之顺序存储和链式存储结构

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

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,395,851
精华内容 558,340
关键字:

顺序存储