数据结构高分笔记

本书讨论群:15945769                                         作者qq：39826407 立志于打造昀贴近考生实际的辅导书计算机考研之数据结构高分笔记率辉编著周伟张浩审核讨论群：15945769 本书讨论群:15945769                                         作者qq：39826407 前言在计算机统考的四门专业课中，昀难拿高分的就是数据结构。但是这门课本身的难度并不是考生昀大的障碍，真正的障碍在于考生不能独自把握复习的方向和考试范围。也许有同学要问了，我们不是有大纲吗？照着大纲去复习不就可以了吗？表面上看是这样，但是当你真正开始复习的时候你就会发现，其实大纲只给了考生一个大致范围，有很多地方是模糊的，这些模糊的地方就可能是你要纠结的地方。比如大纲里对于栈和队列的考查中有这么一条：“栈和队列的应用”。这个知识点就说的很模糊，因为只要涉及到栈和队列的地方，都是其应用的范畴，这时考生该怎么办呢？于是把所有的希望寄托于参考书，希望参考书能帮助我们理解大纲的意图。下边我们就来说说参考书吧。参考书分两种，一是课本，二是与课本配套的辅导书。对于课本，考生用的昀多的就是严版的《数据结构》，这里我也推荐大家把这本书选作考研辅导教材。因为这本书的内容非常丰富，如果能把这本书中考纲要求的章节理解透彻了，参加考研没有任何问题。但是这个过程是漫长的，除非本科阶段就学的非常好。计算机统考后，专业课四门加上公共课三门，一共是七门。绝大数考生复习的时间一般也就六个月，而数据结构的复习需要占用多少时间，我不算大家也清楚。要在这么短的时间内掌握严版数据结构上考纲要求的知识点，基本上是不可能的，这就需要一本辅导书来依照大纲从课本中总结出考纲要求的知识点，才能使得考生在短时间内达到研究生考试的要求。市面上的参考书有两种，一种是四合一的辅导书，比如大家熟悉的复旦版的，山东人民出版社出版的等等。另一种是分册的，比如网上流行的《1800题》以及其第二版，此书题目巨多，并且有很多老式的考研题，有些算法设计题的答案是Pascal语言写的。这本书中的题目一般考生全做基本上是不可能的，挑着做又会把时间浪费在选题上。不可否认，这本书确实是一本非常好的题库，但是考生直接拿来用做考研辅导书却不太合适。还有一本书叫《数据结构习题与解析》，作者是李春葆，上边总结了一些考研所需知识点，但是这本书同样出自统考以前，也不完全适应新大纲的要求。直到复试后，第一次见到周伟写的计算机网络高分笔记样稿，经过半天的研读，发现这个就是我想要的，如果这种写作风格用在数据结构我相信一定是昀畅销的书籍。辅导书就应该站在学生的角度去写，特别像数据结构这门比较难深入的课。所以我决定加入周伟的队伍一起来完成一本真正意义站在学生角度去写的数据结构辅导书。去更好的帮助考生在昀短的时间内去掌握这一门课。这也是我写这本辅导书昀主要的动机。接下来我详细讲解一下这本辅导书书的写作过程，请看下图：本书讨论群:15945769                                         作者qq：39826407 图中所涉及的书都是大家很熟悉的吧。当年这些书我都买了，花了很大心思才从中找出在考研战场上真正有用的东西。比如《1800题》，里边有好题，有废题，我当时多么渴望有人能在我复习之前就帮我从中去掉重复的题目，选出大纲要求的题目，并能把解答写的更通俗易懂点，可是当时没有人这么做，。而我们所做的工作就是从这1800题中选出了大纲要求的题目，并且修正了部分解答，使其更容易理解，我想这也是你们很想要的吧。其次是严版的《数据结构》写的过于严谨，语言表述过于专业，对于基础稍差的同学来说读起来十分费力，要很长时间才能适应这本书的写作风格。我当时就是在这本书中痛苦的挣扎了很久，看第三遍的时候才真正的可以说适应了，何苦这样呢？如果当时有一本辅导书帮我把那些复杂程序的执行过程，拗口的专业术语，令人头大的符号，翻译成容易理解的语言，我就可以节省很多时间，可惜当时也没有。而我们所做的就是根据自己复习的经验，以及对这本书的理解，把其中考试不需要的内容删掉，把需要的内容经过改造变成一般学生容易接受的形式。对于李版的《习题与解析》我也做了类似的处理。并且，我在本书中穿插讲解了一些考纲中没有明文规定但是很多算法题目中大量用到得算法设计课程中的思想，来帮助大家提高解算法设计题的能力，比如搜索（打印图中两节点之间的所有路径），分治法（二分法排序、求树的深度等等）等算法思想。因此我相信这本书会给你的考研复习带来很大的帮助。  本书讨论群:15945769                                         作者qq：39826407 本书特点：（1）精心挑选出适合考研的习题，并配上通俗易懂的答案供你自测和练习。（2）总结出考研必备知识点，并且帮你把其中过于专业过于严谨的表述翻译成通俗易懂的语言。（3）针对于近年数据结构大题的出题风格（比如算法设计题目中的三段式题目：1.表述算法思想。2.写出算法描述。3.计算算法的时间和空间复杂度），设计了独特的真题仿造部分，让你在复习的过程中逐渐养成适合解决考研类型题目的习惯。听我说了这么多之后，很多学生现在想问，我只看你这本书够不够？还需要自己准备其他书吗？对于这个问题，我用下图来回答。本书讨论群:15945769                                         作者qq：39826407 从图中可以看到，如果你只看本书，你能达到考研要求水平的95%左右，为什么是这样，因为今年大纲还没有公布，所以我不敢保证我的书涵盖大纲所有内容。但是数据结构中的经典内容本书已经全部包括，再加上对统考这两年大纲范围的解读，估计今年大纲变化不会太大，毕竟数据结构是一门经典科目，因此考研对这一门科的考察范围较为稳定。从图中同样可以看出，掌握了严版《数据结构》你可以至少掌握比考试范围多出30%的内容，但是这需要花很多时间，并不可行。因此在这里我建议大家先看本书，把重要知识点先拿到手，然后把严版数据结构当做字典来用，等正式大纲出来之后进行查缺补漏，这是一种较为高效的复习方法。这本书不仅涵盖了考纲绝大部分内容，更重要的是它会帮助你理解大纲，理解出题人的思路，这样你就会白哪一类的题目有可能考，哪一类的题目不会考，慢慢的，你复习的方向感会越来越明确，效率会越来越高。                                                                本书作者                  本书讨论群:15945769                                         作者qq：39826407 第一章绪论..................................11．1针对考研数据结构的代码书写规范以及C&C++语言基础............11．1．1考研综合应用题中算法设计部分的代码书写规范.............11．1．2考研中的C&C++语言基础杂谈......................31．2算法的时间复杂度与空间复杂度分析基础....................121．2．1考研中的算法时间复杂度杂谈.....................121．2．2例题选讲................................121．2．3考研中的算法空间复杂度分析....................141．3数据结构和算法的基本概念..........................141．3．1数据结构的基本概念.........................141．3．2算法的基本概念...........................15习题心选....................................16习题心讲....................................18第二章线性表................................212．1线性表的基本概念与实现........................212．2线性表的基本操作............................262．2．1线性表的定义............................262．2．2顺序表的算法操作..........................282．2．3单链表的算法操作..........................312．2．4双链表的算法操作......................352．2．5循环链表的算法操作.........................37▲真题仿造...................................37真题仿造答案与讲解..............................38习题心选....................................39习题心讲....................................43第三章栈、队列和数组.........................543．1栈和队列的基本概念...........................543．1．1栈的基本概念.............................543．1．2队列的基本概念...........................543．2栈和队列的存储结构、算法与应用........................553．2．1本章所涉及的数据结构定义.....................553．2．2顺序栈的基本算法操作........................563．2．3链栈的基本算法操作..........................583．2．4栈的应用...............................593．2．5顺序队的算法操作..........................633．2．6链队的算法操作...........................653．3特殊矩阵的压缩存储..........................67▲真题仿造.................................69真题仿造答案与讲解：.............................69习题心选.....................................72习题心讲.......................................76第四章树和二叉树...............................854．1树的基本概念................................85本书讨论群:15945769                                         作者qq：39826407 4．1．1树的定义...............................854．1．2树的基本术语............................854．1．3树的存储结构............................864．2二叉树.....................................874．2．1二叉树的定义............................874．2．2二叉树的主要性质..........................884．2．3二叉树的存储结构..........................894．2．3二叉