数据结构知识点总结
一、数据结构:相互之间存在一种或多种特定关系的数据元素的集合。
二、基本数据结构:集合、线性结构、树形结构、图状结构。
1、线性表:N个具有相同特性的数据元素的有限序列。
1)存储方式:顺序存储(使用连续的存储空间存储)、链式存储(一组任意的存储单元存储,可以是连续的也可以不是连续的,每个数据元素除了存储数据外,还要存储前驱、后继元素的地址)。
下面辨别一下数据长度与线性表长度:
数据长度指的是线性表中能保存的数据元素的最多个数,比如说数组的大小。
线性表长度指的是表中已经保存的数据元素的个数。
2)单链表
3)串
定义:有零个或多个字符组成的有限序列。
2、树
树的一些概念:
1)结点:包含数据元素及指向子树的指针;
2)结点的度:结点拥有的子树数量;例如下图树中,结点A的度为3,B为3,C为1,D为2。
3)树的度:树中所有结点度的最大值;例如下图树中,结点度数最大为3,所以树的度为3。
4)树的深度:树的层数。
4)结点的分类:
根结点:没有双亲的结点;
内部结点:有双亲,且结点的度不为0;
叶子结点:有双亲,但是度为0;
特殊的树:二叉树
定义:是n(n >= 0)个结点的有限集合。
当n > 1时,除根结点外的其余结点可分为左结点和右结点。
结点的度不能大于2。
二叉树存储:满二叉树用数组依次存储,其他二叉树根据满二叉树存储,不存在的结点都存为空。
问题:孩子结点没办法找到双亲结点
只是总结了知识点原理,没有写具体的代码实现,有时间的时候再补上。