清华大学数据结构详解教程

教程网首页 > 电脑 > 数据库类》清华大学数据结构详解教程

内容简介

清华大学数据结构详解教程视频简介：

　　数据结构是计算机科学与技术专业最重要的一门专业基础课。通过学习这门课程，大家可以掌握数据结构和算法的基本概念和技术，并设计相应的操作算法。掌握线性表、栈和队列、串、广义表、树和二叉树、图等典型数据结构及相关算法，以及排序、查找等重要技术。想学好数据结构这门课程的朋友可以来第一视频教程观看一下这部由清华大学名师主讲的数据结构教程。

　　数据结构是一门研
关注公众号:diyijc_com 问题反馈

教程内容

清华大学数据结构详解教程视频简介：

　　数据结构是计算机科学与技术专业最重要的一门专业基础课。通过学习这门课程，大家可以掌握数据结构和算法的基本概念和技术，并设计相应的操作算法。掌握线性表、栈和队列、串、广义表、树和二叉树、图等典型数据结构及相关算法，以及排序、查找等重要技术。想学好数据结构这门课程的朋友可以来第一视频教程观看一下这部由清华大学名师主讲的数据结构教程。

　　数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象及其关系和操作算法的学科。它主要内容包括： ①数据的逻辑结构--数据关系之间的逻辑关系;②数据的存储结构--数据的逻辑结构在计算机中的表示; ③操作算法--插入、删除、修改、查询、排序等。该课程主要学习数据结构和算法的基本概念和技术，算法的评价标准以及算法的分析方法;学习线性表、栈、队列、串、数组、广义表、树和二叉树、图等典型数据结构的顺序存储结构和链式存储结构;学习在上述数据结构中进行数据插入、删除、遍历以及其他相关应用算法;学习各种查找、排序算法并进行性能分析比较。

　　学习数据结构这门课程至少要经历三个过程，方可真正的掌握这门课程，得到一个满意的成绩。这个过程简单来说就是三个字：活→死→活。

　　首先，是一个学“活”的过程，就要要求我们对书中的每一个算法，能够在脑海中建立起相应的模型，而不是死板的算法。比如树的遍历非递归算法，在入栈与出栈的过程中，我们就要在脑海中形成访问树每个结点的过程，真正掌握住这个算法。这样，全书复习下来，你的脑海中就有了整个数据结构的模型概念，对任何一个陌生的算法，将不感到生疏和害怕。

　　有些同学到了此处就觉得数据结构已经学好，可以万事大吉了，其实这还远远不够，如果参加考试，往往会拿不到高分，甚至还会纳闷，为何自己数据结构学的这样好，成绩却不尽如人意，因此产生了批卷老师判错的想法。所以，第二个过程，就是一个学“死”的过程，这个过程要求，要记住书中的算法(功利一点就是要背诵会所报考学校的考试要求的算法)。

　　有的学校有别的特殊要求，也一并背会。如上海交通大学喜欢考平均复杂度的分析这样的题目，我们在书上可以找到这样的分析一共十一个，全部背会，就免去了在考场上分析的麻烦，如果连答案都能记住，那么，也不会因为粗心失分了。这一过程也许有些枯燥，但却是最重要的过程，比如说背会了树的后序遍历非递归，遇到了像求某个结点的所有祖先，两个结点的共同祖先这样的题，不用想，直接套用。这样才是考试的高分的关键：在考场上，遇到考题，不用思考，直接从脑海中找匹配的算法，直接引用。

　　有了第二个过程的辛苦，我们就可以得到一个比较高的分数了，如果还想提高，就要进行第三个过程，再学“活”的过程。这一个过程中就要要求我们，在第二步的基础上，多进行思考，看看有哪些算法有共性，比如说：树的前序非递归遍历算法和图的深度优先遍历算法是不是类似啊，有些什么不同，有些什么相同，为什么会相同;森林转化为二叉树和图的生成树的算法也是这样，等等。总结出这种共性，这样就能正确有效的记忆算法，同时，遇到难题不至于慌乱，能够从容下手解题。

　　对于总结共性问题上，这里举一小个例子，(呵呵，我当初总结出这个，并且和kaoyan.com斑竹一具讨论确定后三天，就在2002年交大第一题考出类似东东)比如树的遍历，不管是递归还是非递归，也不管是线索树，还是头结点有父母信息的树，它的遍历其实就是一个寻找到遍历的第一个结点，然后再寻找它的后继结点的过程，我们归纳到此处，就可以试着总结一下三种遍历的后继结点是哪个，有几种情况：

　　对于前序遍历，它的后继如下：(1)若有左孩子，则后继是左孩子;(2)若无左孩子，有右孩子，则后继是右孩子;(3)若既无左孩子，又无右孩子，则是一片叶子;再讨论：(a)若是其父母的左孩子，且父母有右孩子，则后继是父母的右孩子。(b)若是其父母的左孩子，且父母无右孩子;(c)若是其父母的右孩子。b，c都表示这是某个节点的左子树前序遍历的最后一个节点，则需要找第一个有右子树的“左祖先”(定义“左祖先”，即找第一个使得当前节点在这个祖先的左子树上)，然后后继就是这个祖先的右孩子。

　　对于中序遍历，它的后继如下：(1)如有右孩子，后继是右孩子的最左下节点;(2)若无右孩子，且是父母的左孩子，则后继就是父母;(3)若无右孩子，且是父母的右孩子，则一直上溯到第一个“左祖先”(定义如前)则后继就是这个祖先。若无这样的祖先，说明已经遍历完毕。

　　对于后序遍历，它的后继如下：(1)若是父母的右孩子，则后继是父母;(2)若是父母的左孩子，且父母无右子树，则后继是父母;(3)若是父母的左孩子，父母有右子树，则后继是父母右子树的最先访问到的节点(指向父母的右子树后，一直往左，若不行的话，往右一步，一直到叶子)

　　总结完了，想一想，我们还能得到哪些提示?经常有一类型题目，要求求某个结点的直接前驱。其实求前序遍历的前驱和求后序遍历的后继是一样的，只不过把左换成右而已，前序遍历的求后继和后序遍历的求前驱、中序遍历的求前驱和中序遍历求后继都有这样的对称关系。因此，总结出共性的东西，许多题目就可以迎刃而解了。问一问读到这里的读者，你现在能够自己在脑子里面，非常轻松地像上面那样，把这个例子里面的情况都条理清楚地分析总结出来吗?如果现在还不行，到考试之前，你必须掌握到这种程度，才能得到一个自己很满意的分数。

　　经过以上的三个过程复习，相信读者对数据结构的掌握就可以到达比较高的水平了，如果参加考试，获得一个比较满意的成绩也很有希望了。当然，达到这一步并不容易，大量的练习是真正掌握的必由之路。因此，我们建议大家能够下功夫把本书中的题目完整地做一遍，然后在希赛教育远程测试平台中做模拟试题。能够真正把这些题都掌握，就意味着对数据结构这门课程的理解，以及对问题的分析能力都有很大的提高，这样在考场上即使遇到未曾见过的题目，也就可以从容应对了。

更新时间：2013-08-06 22:03