《数据结构》半期内容梳理

1. 数据类型和算法
   • 抽象数据类型的概念
   • 算法复杂度（时间、空间）
   • 大O符号表示法
2. 线性表及其实现
   • 顺序存储（数组，操作：查插删）
   • 链式存储（链表，操作：查插删）
   • 广义表与链式表
3. 堆栈及其实现（顺序存储、链式存储）
4. 队列及其实现（顺序存储、链式存储）
5. 树及其实现
   • 二分查找的实现
   • 二叉树与完全二叉树（相关性质）
   • 树的四种遍历（递归、非递归实现）
   • 二叉搜索树的建立（操作：查插删）
   • 平衡二叉树的建立与调整（四种旋转）
   • 堆的建立、删除、插入与堆排序
   • 哈夫曼树与哈夫曼编码、前缀码与最优编码
   • 并查集的操作（并、查、大小集合并、路径压缩）
6. 图的表示及操作
   • 图的相关概念（入出度、连通图、稀疏图等）
   • 图的两种表示方式（邻接表、邻接矩阵）
   • 图的两种遍历方式DFS与BFS的实现
   • 最短路径问题（迪杰斯特拉、Floyd算法、无权/有权、单源/多源）

     关于课程：神课？神课！

     大三下闲来无事，正好看见神仙舍友在准备字节跳动和阿里巴巴的实习岗面试在刷Leetcode和牛客网，于是自己也想学习下算法与数据结构。也许自己将来会选择转码，从大三就开始努力准备未尝不是一件坏事；即使将来不转码，也算是锻炼了码力，对于通信工程中一些通信算法的设计也大有裨益。于是乎，早有听闻ZJU的数据结构闻名全国，陈越姥姥的功力法力无边，于是毅然决然地选择跟着这门课学习算法与数据结构。
     
     这门课程的话我个人觉得安排得特别好，算是达到了理想中的“理论与实践相结合”。理论的话我建议每周跟着浙江大学的《数据结构》MOOC进行更近，倍速食用更佳；实践的话那必然是课程配套的PTA刷题了，还可以去看看PAT、CCF甚至是ACM（这是对于打代码基础的人来说啊。如果是直接找工的话，刷Leetcode和背八股文就行了）。

     关于刷题：简单？思考！

     关于刷题，我个人本科截至目前为止其实接触算法不多，但也算是在大一的程序设计课上写过一些代码。但是这次的PTA刷题是第一次正规刷题的，第一次知道什么是AC，什么是Checkpoint还有测试样例等等。下面是我总结的几点我从这七周学习中学习到的点：

• 数据结构只是一种思维，不是特定的数据类型。所以我们看到的这些所谓的“数据结构”都有很多种实现方式，例如树，我们既可以使用链表来实现二叉树，也可以使用结构体数组来实现（只需要在结构体里定义左右子节点即可），所以学习数据结构的本质是希望我们打破这些固有数据类型实现的束缚。
• 三思而后行。学过这门课的小童鞋应该知道，你要如何解决这个问题，是与我们如何存储数据，如何定义ADT密切相关的，所以建议想清楚自己在解决问题过程中需要哪些操作集，来反推自己需要什么样的数据结构作为基础，通过一定的算法解决问题。
• 刷题需要集中精力。我个人不是特别推荐那种不是All-in的刷题状态，也就是一道题放到好几个时间段里完成，我个人比较推荐做题时就完全集中精力，就跟高考一样，脑子里唯一想的就是怎么用最快的时间AC面前的这道题，这样子比较有益于思维的养成（当然还有手速的提升doge）。
• AC之后也不要忘记把注释补上。我个人现在非常重视注释，觉得代码真的非常需要注释，不然过几天连自己都不知道自己写了个啥玩意。
• Debug和审题很重要。我自己总共做了二十来道题目，很多题目一直没AC后来发现是审题的问题，也就是——不是我做错了，而是我的答案与题目想让我输出的答案不一样（可能是格式不一啊等等），Debug能力也很重要，迅速发现结果不对的原因是在中间哪个函数哪个循环不对，这个能力需要通过刷题来培养（就像我现在题目做多了之后，一旦出现段错误就直接把数组开大一点，有时候段错误一下就被解决了。
• 边界测试是很多程序员的“落凤坡”。个人比较建议把一些边界的地方单独拿出来考虑，比如说输入的N很小的话那我就直接输出结果，然后return 0等等，总之很多特殊情况一定要慎重。PTA最大的好处和坏处就是：不告诉你测试样例，只靠诉你对了几个测试点，这就需要你自己要能够对自己的代码进行“自我反省”。
• 不断尝试新方法是锻炼代码能力的好方法。我之前也是固步自封，一旦碰到排序类问题，都是直接冒泡暴力干起来，直到最近的一道题目靠冒泡会超出时间限制，我不得不第一次编写并使用了堆排序，最后时间复杂度是OK的，这个例子就是告诉我们平时多提前准备一些代码，多去尝试新的方法，对于提升自己的代码很有帮助，不然学了《算法与数据结构》，却不去使用它们，最终只能是纸上谈兵，练就一身屠龙之术。
• 注意观察，发现本质。我在PTA上碰到一道两数相除的题目，我最后写的那个程序就是教电脑如何跟我们一样一步步用笔计算除法，所以看清本质和掌握规律很重要，毕竟编程的本质就是用一套规则教会电脑做事嘛。
• 掌握刷题套路，熟能生巧。当你刷题多了之后你就会发现，题干中有很多提示性的话语，比如“如果什么什么，那什么什么也是这样的”，这就是提醒你可以用递归，还有那种扫描或者比对一个字符串的事情，经常会用到双指针，这些都是在日常做题过后需要总结的。

其他还有很多其他需要注意的点，这里就不一一列举了，我之前也写过几篇关于C++编程和浙大《数据结构》的一些相关文章，这里也把链接放在这里，感兴趣的朋友可以康康。

• C++（一）：C++程设-文本分析
• C++（二）：C++程设-矩阵计算
• 数据结构（一）：数据结构C++实现
• 数据结构（二）：浙大数据结构刷题（一）
• 数据结构（三）：浙大数据结构刷题（二）
• 数据结构（四）：浙大数据结构刷题（三）
• 数据结构（五）：浙大数据结构刷题（四）

  课程之外：PTA其他练习

  PTA上面还有一些其他浙江大学计算机系老师准备好的题集，例如C++程序设计题库啊还有PAT基础到高级都有，感兴趣的也可以平时做下这些题目练练手，个人感觉无论是对于逻辑思维的构建还是代码工程的能力都大有裨益，当然更重要的是——在有一定的刷题后及时总结及时反思，方能不断进步。
  PAT（base level）我现在做了25题了，个人感觉这个base level更像是编程思维的训练，感觉涉及到所谓的算法与数据结构的部分并不多，所以我推荐大家可以刷个25题左右，主要考察：编程基本功、在线处理、排序算法、哈希表、双指针和Debug能力，大多数题目用这几个方法就可以AC，培养下自己的编程思维和一些Debug的能力即可，而且还是有一些题目值得大家多去思考思考的，下面列举了我目前做到的部分有点难度的题目：

总结：编程之美尽在不言中

纸上得来终觉浅，绝知此事要躬行。我现在越来越觉得编程是一件很美好的事情，也越来越能体会到编程的魅力。在接下来的一段时间也会继续更新浙大《数据结构》方面的文章。欢迎对ECE/CS/AI感兴趣的小伙伴关注我，如果你对我的内容有什么建议的话，或者你也对算法和数据结构感兴趣的话，可以单独找我讨论，也欢迎在评论区留下你的声音。