数据结构第一章笔记,数据结构第四章知识点总结

　　从《数据结构基础知识(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的所有未访问的相邻点，然后访问每个相邻点的相邻点，访问顺序应保持首先访问的顶点及其相邻点也被优先访问，直到图中的所有顶点都被访问。