算法与数据结构—课程总结
AlgorithmsandDataStructures
课程重点
算法与数据结构绝对是计算机专业的专业基石，是专业水平的一种体现。所以很有必要学好这门课程。
本门课程较为全面地介绍算法与数据结构的基本内容，包括：算法与数据结构概论、线性表、栈、队列、字符串、二叉树、堆、优先队列、树、森林、图、内排序、检索等内容。
主要知识点有：
概论：
1、算法与数据结构的初步认识
注意初步培养专业意识，逐步建立对算法数据结构专业概念的理解，如：“逻辑结构，物理结构，结点，算法的特性，算法复杂度”等等。
2、算法复杂度的计算
注：重点掌握算法的大O表示法，熟练表示各种程序结构的大O表示法的复杂度计算，熟悉算法最好、最坏、平均情况下考试必考一个或两个这样的题。
线性表：
1、顺序表
就是我们平常说的数组。简单理解定义和结构即可。
2、链表
链表是很重要也很常用的数据结构，一定要认真理解到精髓并十分熟练的运用。练习的时候仔细对照书和PPT的图解码C代码，并认真通过自己的调试检测。注意链表的指针操作，一般会在这里遇到许多bug，改的时候细心细心。其实，无论是C/C++，还是其他编程语言如Java，Python等，这些关键的数据结构已经在标准类库中实现了，我们只需要调用即可，不需要每次都自己实现。如C/C++的STL库，Java的集合框架，Python众多的数据结构模块等等。我们在自己实现成功后，更重要的是自己去了解和使用标准的、官方的库，去读官方文档、API，并在以后使用标准实现。这样自己的程序就不会在数据结构方面出问题，还能锻炼自己的英文文档和API阅读和使用能力。
3、栈
也是很重要的数据结构，掌握栈的运行方式，并且认真理解PPT和书上的几个有关栈的应用，如：数制转换、计算前中后缀表达式的值（稍微有点难度，但是非常值得深究，收获会很大）、栈与递归等等。争取利用空余时间自己动手码代码实现一个或两个，这是对自己编程能力的很好的锻炼。
4、队列
比较重要的数据结构，注意与栈的对比。栈-先进后出，队列-先进先出。掌握C代码的队列操作。
5、每种数据结构的操作，优缺点
明白在什么情况下应该使用什么样的数据结构。
字符串：
1、字符串的抽象数据类型
2、字符串的存储结构和类定义
注：这部分PPT的内容不推荐，建议去查询C/C++或java的有关字符串的类库。PPT中这部分写的比较混乱，不太好。
3、字符串运算的算法实现
简单地阅读书和PPT上的代码，自己手动码字实现即可。
4、字符串的模式匹配-朴素模式匹配，KMP算法
字符串模式匹配，特别是KMP算法是重点和难点。考试一定会有一道题考察KMP算法，多半是画出算法图解。个人认为KMP算法“巧夺天工”，非常地巧妙非常地神奇。当然KMP算法很抽象，短时间内很难理解（学霸除外）。首先建议阅读理解能力比较强的同学自习阅读思考书中相关内容，一遍没看懂，再看一遍，总之多看几遍。如果还是没太懂，到网上查查资料，找详细解释。最后结合PPT上的动图，辅以自己手动画过程图，相信你们应该就理解的差不多了。理解能力不强的同学不要灰心，先看PPT上的动图，先“死记”KMP算法的过程，然后一定要找已经理解的差不多的同学请教，让学霸们在你面前画一画，相信你们会开窍的。最后，你们都会不得不服K、M、P这三个人。
二叉树：
1、概念性质
注：二叉树也是很重要的数据结构，前序概念有些是离散数学里的（后面的树、图也是），回忆一下。
2、二叉树的抽象数据类型
理解类的结构。
3、周游二叉树算法-深度优先周游二叉树（前序、中序、后序），非递归深度优先周游二叉树，广度优先周游二叉树
周游二叉树算法也是重点和难点。书上给的周游算法的C代码比较有代表性，可以仔细去看。一般看这种代码的方法是：先通读代码，了解大概。然后以一次循环为单位，为每次循环过程画图，手动保留中间过程。这样自己的脑袋里跑完这些代码后你就可以得到运行过程的所有中间结果，连起来看非常好理解了。此外，还可以使用VisualStudio等先进的IDE进行单步调试，在debug界面下观察变量的变化。
4、完全二叉树二叉搜索树穿线二叉树堆优先队列哈夫曼编码树
注意各种特殊二叉树之间的联系和区别。其实这些特殊的二叉树才是应用的重点，每一个都需要认真掌握用法，并且都要手动画图过一遍。这几个二叉树你们应该还会在这门课程以后的学习中再见到，所以切不可马虎了事。
树：
1、概念
2、树与二叉树的相互转换算法
3、树和森林的周游算法
注：这一章就显得不太重要（对考试而言），考试会考第二点的画图和第三点的简单叙述和画图。
图：
1、概念
注：前序概念有些是离散数学中的，有些是新的。其中关键的部分贯穿整个这一章，如：出度、入读、顶点等等。课上认真跟着老师走就好了。
2、图的抽象数据类型
熟悉书上的类
3、图的存储结构-相邻矩阵，邻接表
本章的重点之一，但是不难理解。跟着书上的代码跑一遍，好好完成作业就能很好地理解了。
4、图的周游算法-深度优先周游，广度优先周游，拓扑排序
重要程度不及二叉树的周游，但是要会过程，会画图。认真完成书上老师给的题就好。
5、最短路径问题-Dijstra算法，Floyd算法
6、最小支撑树-Prim算法，Kruskal算法
以上几个算法是本章的重点，理解起来稍微有点难度。仔细理解书中的算法介绍和图表，手动跑一遍流程图。学有余力的同学争取码代码实现这几个算法。
内排序：
1、概念
2、三种O（n2）的简单排序-插入排序，冒泡排序，选择排序
这三种基本的排序要做到闭眼就会。
3、Shell排序
看懂过程即可
4、基于分治法的排序-快速排序，归并排序
快速排序比较重要，需要会画图理解过程。考试在这里出题的几率也较大。
5、堆排序
堆排序稍有点抽象，需要前面学好堆。堆排序比较精妙，一定要多画图才能理解书上给出的C代码。
6、各种排序算法的理论和实验时间代价
7、排序问题的下限
检索：
1、概念
2、线性表的检索-顺序检索，二分检索，分块检索
看懂书上和PPT的过程即可。
3、散列方法
散列方法是本章的重点，涉及到的概念比较多。书上的内容都要过一遍，重点还是看PPT的讲解。散列方法在今后用处比较多。
学习方法
想要学好这门课，仅仅依靠课堂上认真听讲是远远不够的。前面的线性表部分难度还不大，但是到了后面，比如字符串模式匹配KMP算法，二叉树周游等等，算法的难度就开始慢慢加大了。所以往往上课有不少内容没听懂，没理解，这其实是很正常的现象，不用担心。我们要做的就是在课下一定要找时间弄懂这些“神奇”的算法，千万不要落下，到最后想补起来简直会比登天还难。
所以说，这门课有一些难度，但是绝不会难倒大家。我们需要锻炼一下自己的逻辑思维，学会以计算机的方式思考算法。无论是课上还是课下，一定要勤动笔，把抽象的算法过程一步一步地画出来，这样对理解算法非常有帮助。比如说，书上的算法、例子有些是用C代码给出的，光看代码有些是很难理解的，但是我们如果能在脑子里运行代码，或者干脆在电脑上使用先进的IDE进行单步调试，把中间过程一步一步地画出来，自然地就理解了。
老生常谈，一定要上课听讲，一定要自己按时完成作业。老师上课讲的，课下留的作业，基本上都是考点。特别是像算法数据结构这门课程，做作业的意义就更大了，只有亲自过手，才能真正理解算法的妙处。
学有余力的同学，不妨自己亲自码代码实现书中的算法。这种过程才是学算法的最好方法，如果自己去踩过算法数据结构的坑，自己从坑里面爬出来，这种成就感，保证是对算法精髓的最好理解。
另外，不要局限与教材。算法与数据结构是计算机的基础，这门课程国内国外都有不少优秀的著作和帖子，大佬们可以尽情地去探索，把自己的专业水平提升到更高层次。
注意事项
1、工欲善其事必先利其器，相信大家已经对编程环境有了些了解，还没有先进IDE的同学可以请教周围的同学安装学习一下先进IDE的使用，这对后面编程有极大的帮助。
2、一定要亲自动手码代码，亲自思考并解决bug。最好把自己犯的bug记录下来，供自己以后参考。推荐大名鼎鼎的github网站，或者使用各种笔记软件如：Onenote、印象笔记等。另外推荐技术博客：国内CSDN，国外StackOverflow（学会翻墙，推荐VPN：蓝灯、赛风，学会阅读英文网站英文资料）。
3、一定要勤动笔，画图，把算法的每一步、每一个中间过程都画出来加深理解！
4、不会的一定要请教老师同学，尽快搞懂。
学习建议
参考资料：《算法导论》，《算法竞赛入门经典》，MIT在线课程，慕课网
点击“阅读原文”下载电子文档↓
赞赏