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

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

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

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