四川大学考研网 首页 文彦攻略计算机学院
20川大计算机 | 数据结构围观大讲堂(下篇)!
====================================================================
咨询QQ:2100097017  川大考研在线咨询
2020四川大学考研:2020四川大学考研
咨询热线: 400-0860-400

微信咨询

====================================================================
 


文 彦 考 研

让丨梦想丨有迹可循




这是20届川大计算机 第 篇文章


导师简介


零师姐,2017届以初试353分,复试第2的成绩考入四川大学计算机科学与技术专业。现于文彦考研担任专业课导师,辅导川大874计算机综合考研专业课。多次参与与IT公司的合作项目中,熟悉计算机专业的考研动态与就业形势。

数据结构围观大讲堂(下篇):

5

树:

  树是一种数据结构,它是由n(n>=1)个有限节点组成一个具有层次关系的集合。把它叫做 “树” 是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。它具有以下的特点:

1、每个节点有零个或多个子节点;

2、没有父节点的节点称为根节点;

3、每一个非根节点有且只有一个父节点;

4、除了根节点外,每个子节点可以分为多个不相交的子树;

   在日常的应用中,我们讨论和用的更多的是树的其中一种结构,就是二叉树。

    二叉树是树的特殊一种,具有如下特点:

1、每个结点最多有两颗子树,结点的度最大为2。

2、左子树和右子树是有顺序的,次序不能颠倒。

3、即使某结点只有一个子树,也要区分左右子树。

   二叉树是一种比较有用的折中方案,它添加,删除元素都很快,并且在查找方面也有很多的算法优化,所以,二叉树既有链表的好处,也有数组的好处,是两者的优化方案,在处理大批量的动态数据方面非常有用。

   对于树这部分是考试的重中之重,在选择题和大题中都有较多的考察。比如选择题中,多考察树的六大性质,编程题中考察,树的深度优先遍历(递归、非递归形式)、广度优先遍历。

扩展:

二叉树有很多扩展的数据结构,包括平衡二叉树、红黑树、B+树,B-树,这些数据结构二叉树的基础上衍生了很多的功能,在实际应用中广泛用到。在考试中平衡二叉树、B+树、B-树经常会以选择题的形式出现。

6

图:

  图是由结点的有穷集合V和边的集合E组成。其中,为了与树形结构加以区别,在图结构中常常将结点称为顶点,边是顶点的有序偶对,若两个顶点之间存在一条边,就表示这两个顶点具有相邻关系。这里对比树和图法向,树会有唯一的前驱,可能有多个后继,而图会有多个前驱,多个后继。

其存储通常可以有邻接表、邻接矩阵两种方式。


                                           一、邻接矩阵

邻接矩阵存储使用2个数组存储图的信息:1个以为数组存储顶点,一个二维数组存储边的信息

(1)二维数组中的对角线为0,以为不存在顶点到自身的边

(2)要知道某个点的出度,就是顶点vi在第i行的元素之和,入度就是该顶点所在列的元素之和

(3)顶点vi的所有邻接点就是吧矩阵中第i行元素扫描一遍


二、邻接表

邻接矩阵对于顶点多而边数少的稀疏图造成存储空间的大量浪费。正如线性表的预先分配可能造成存储空间浪费,因此引入链式存储结构。同样可以考虑用链表存储边或弧。


邻接表:数组 + 链表

(1)用的数组存储每个节点

(2)数组中的每个节点的所有邻接点组成一个链表(因为邻接点的个数不确定)。这个邻接表就是顶点的出度表

(3)邻接表的图形表示



推荐阅读

20届川大计算机 | 欢迎来到数据结构围观大讲堂!

扫码入群~

获取更多干货~



加小彦微信

 一对一咨询~

我是文彦考研




注:图片来源于网络,版权归原作者所有,侵删。



用户您好,您的访问过于频繁,为确认本次访问为正常用户行为,需要您协助验证。

验证码:

换一张 验证码错误,请重新输入

提交后没解决问题?欢迎反馈

 
(责任编辑:四川大学考研网)

关于我们

联系我们

成都文彦教育咨询有限公司
联系地址:成都市武侯区一环路南一段20号普利大厦B座601
热线电话: 400-0860-400
在线Q  Q:2100097017  川大考研在线咨询
联系邮箱:scdxky@qq.com

微信咨询

Copyright:2007-2017  Powered by  四川大学考研网  ICP备案证书号:蜀ICP备10208733号-13