抱歉,您的浏览器无法访问本站

本页面需要浏览器支持(启用)JavaScript


了解详情 >

树(二)

树的遍历

上一节记录了树的递归遍历,递归是函数自身调用自身,大量压栈出栈,时间和空间开销较大,而这操作都是在栈上,如果数据规模较大很容易溢出。

以下是树的非递归遍历方法:

树(一)

树是n个结点的有限集,可以是空树(n == 0)也可以是非空树。

对于非空树:

1.有且仅有一个称之为根的结点。

2.除根结点以外的其余结点可分为m个互不相交的有限集,其中每个集合本身也是一棵树,成为根的子树。

栈和队列

引入

栈是一种重要的线性结构,是线性表(顺序表,链表)的一种具体形式,也就是说其可以通过顺序表或链表实现。

顺序表或者链表可以像之前一样独立存在、处理数据,同时它们也可以是一些特殊的数据结构(栈、队列)的实现基础。

单链表

链表是线性表的链式存储方式,逻辑上相邻的数据在计算机内的存储位置不一定相邻,可以给每个元素附加一个指针域,指向下一个元素的存储位置。

顺序表

概念

具有 一对一 逻辑关系的数据按照次序连续存储到一整块物理空间上”的存储结构就是顺序存储结构(顺序表)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define MAXSIZE 100
#define OK 1
#define ERROR 0
typedef int Status;
typedef int elem;


typedef struct Sqlist{
elem *e;//存储空间的及地址
int length;//长度
}Sqlist;

数据结构概括

数据

所有能够输入到计算机中的去的描述客观事物的符号

数据元素

数据的基本单位,也称结点或记录

数据结构

相互之间存在一种或多种特定关系的数据元素的集合