数据结构第一章笔记,数据结构第四章知识点总结
从《数据结构基础知识(1)》收到的内容。
链表的分类
单向链表
单链表是一种链式访问结构。为了找到第I个数据元素,我们必须首先找到第I个数据元素。图中阴影区域代表数据字段,空白区域代表指针字段。并且最后一个指针字段为空。
循环链表
循环链表是链式存储结构的另一种形式。其特点是表中最后一个节点的指针字段指向头节点,整个链表形成一个环。循环链表分为单循环链表和多链循环链表。
双向链表
双向链表,也称双链表,是链表的一种。它的每个数据节点都有两个指针,分别指向直接后继和直接前任。因此,从双向链表中的任何节点开始,都可以很容易地访问它的前一个和后一个节点。双链表的灵活性比单链表好,但代价更大(有两个指针)。
顺序表和链表的比较
一种数据结构,其中顺序表存储位置是连续的,可以立即访问。顺序表的长度必须在使用前指定,内存一旦分配,就不能在使用过程中动态改变。它的优点是存取数据方便,可以立即存取表中的任何数据。
链表是一种通过指针描述元素关系的数据结构。它可以是具有不连续物理地址的物理空间。您不能立即访问链接列表元素。您必须从头开始,一步一步地搜索元素。它的优点是:对于数组,可以动态改变数据的长度,分配物理空间。
使用中:如果一个数组在使用中,查询比较多,但是插入和删除的数据比较少,数组长度不变,那么选择序列表比较合理。如果你插入或删除一个不定长的数组,你可以选择链表。
树(树)
树是有n(n ^ 0)个节点的有限集k,关系n定义在k中,满足以下条件:
(1)只有一个节点K0,它没有关系N的前身,K0称为树的根节点。简称root。
(2)除了K0之外,K中的每个节点对于关系n只有一个前体。
(3)k中的每个节点可以有关系n的m个后继(m=0)
树木具有以下特征:
(1)每个节点有零个或多个子节点。
(2)每个子节点只有一个父节点。
(3)没有父节点的节点称为根节点。
关于树的一些术语
节点的度:一个节点所包含的子树的个数称为该节点的度;
叶节点或终端节点:度数为零的节点称为叶节点;
非末端节点或分支节点:度数不为零的节点;
父节点或父节点:如果一个节点包含子节点,则该节点称为其子节点的父节点;
子节点或子节点:一个节点中包含的子树的根节点称为该节点的子节点;
兄弟节点:具有相同父节点的节点称为兄弟节点;
树的高度或深度:树的根节点级别定义为1,其他节点的级别为父节点级别加1。树中所有节点的最高级别称为树的深度。节点的层次结构:从根开始,根是第一级,其子节点是第二级,以此类推;
树的度:一棵树中最大节点的度称为树的度;
节点的祖先:从根到节点的分支上的所有节点;
后代:子树中以某个节点为根的任何节点都称为该节点的后代。
森林:m(m=0)棵不相交的树的集合称为森林;
树的遍历
树的遍历分为:前序遍历、后序遍历和层次遍历。预遍历的遍历顺序是先访问根节点,再访问叶节点;后遍历的遍历顺序是先访问叶节点,再访问根节点;层次遍历就是按照层次进行遍历。
二叉树
二叉树是一种有序树,每个节点最多有两个子树。子树一般称为“左子树”和“右子树”。二叉树分为完全二叉树、完全二叉树和不完全二叉树。
图
一个图由有限的一组V个节点和一组E条边组成。其中,为了与树形结构相区别,节点常被称为顶点,边是有序的顶点对。如果两个顶点之间有边,说明这两个顶点相邻。其中,图分为无向图和有向图。
图的遍历
图的遍历分为深度优先遍历和广度优先遍历。深度优先遍历的思想类似于树的一阶遍历。遍历过程可以描述为:从图中的一个顶点V开始,访问该顶点,然后依次从V的未访问过的相邻点开始继续深入遍历图中的其余顶点,直到图中所有有路径连接到V的顶点都被访问过。
广度优先遍历方法描述为:从图中的一个顶点V开始,访问完该顶点V后,依次访问V的所有未访问的相邻点,然后访问每个相邻点的相邻点,访问顺序应保持首先访问的顶点及其相邻点也被优先访问,直到图中的所有顶点都被访问。