DataStructure_Algorithm_ZJU

中国大学慕课上陈越老师和何钦铭老师主讲的数据结构课程课程链接，本项目整理课程相关内容，并利用Python将课程相关作业进行实现，相关视频内容视频链接，具体题目信息可以直接搜索题目名字进行查询。

To-do:

• 加入其他语言完成作业的branch，欢迎大家fork添加！
• 没有达到满分的作业，如果发现请在issue中添加，我会尽早解决。

第一讲 基本概念

通过研究很多例子去理解究竟什么是“数据结构”、为什么在教数据结构的时候要讲算法、以及相关的基本概念和常用术语。希望这次课的学习能让你明白为什么要学，并且在后面的学习中知道哪些术语是什么意思。

课件内容：

• 1.1 什么是数据结构
• 1.2 什么是算法
• 1.3 应用实例：最大子列和问题

题目内容：

• 01-复杂度1 最大子列和问题
• 01-复杂度2 Maximum Subsequence Sum
• 01-复杂度3 二分查找

第二讲 线形结构

介绍最基础的一种数据结构类型：线性结构，包括线性表、堆栈和队列。重点关注：如何用数组或者链表存储对象及关系、如何实现主要操作,以及有哪些典型的应用。

课件内容：

• 2.1 线性表及其实现
• 2.2 堆栈
• 2.3 队列
• 2.4 应用实例：多项式加法运算
• 小白专场：多项式乘法与加法运算- C实现（3小节共27:43）
• 线性结构之习题选讲[陈越]：Reversing Linked List

题目内容：

• 02-线性结构1 两个有序链表序列的合并
• 02-线性结构2 一元多项式的乘法与加法运算
• 02-线性结构3 Reversing Linked List
• 02-线性结构4 Pop Sequence

第三讲 树（上）

一般树的表示、二叉树及其存储、二叉树的遍历,当然最后还有详细讲解二叉树同构问题的"小白专场"。

课件内容：

• 3.1 树与树的表示
• 3.2 二叉树及存储结构
• 3.3 二叉树的遍历
• 小白专场：树的同构 - C语言实现
• 树之习题选讲-Tree Traversals Again

题目内容：

• 03-树1 树的同构
• 03-树2 List Leaves
• 03-树3 Tree Traversals Again

第四讲 树（中）

二叉搜索树，平衡二叉树。

课件内容：

• 4.1 二叉搜索树
• 4.2 平衡二叉树
• 小白专场：是否同一棵二叉搜索树- C实现
• 树之习题选讲-Complete Binary Search Tree

题目内容：

• 04-树4 是否同一棵二叉搜索树
• 04-树5 Root of AVL Tree
• 04-树6 Complete Binary Search Tree

第五讲 树（下）

"堆"：类似操作系统进程调度这样的场景中，我们需要管理一个带任务优先级的队列，经常要从优先队列中获取优先级最高的任务。堆结构将告诉你如何高效地解决这类问题。
"哈夫曼树和哈夫曼编码"：编码是通讯和数据传输中最基本的问题。如何针对不同的出现频率高效地编码以提高传输和存储的效率？哈夫曼树就是一种很好的方法。
"集合及运算":有许多貌似复杂的问题可以归结为等价类划分问题。以树形式表示的并查集方法就可以很方便、高效地解决等价类划分问题。

课件内容：

• 5.1 堆
• 5.2 哈夫曼树与哈夫曼编码
• 5.3 集合及运算
• 小白专场：堆中的路径 - C语言实现
• 小白专场[陈越]：File Transfer - C语言实现
• 树之习题选讲- Huffman Codes

题目内容：

• 05-树7 堆中的路径
• 05-树8 File Transfer
• 05-树9 Huffman Codes.py

第六讲 图（上）

了解什么是图，怎么存储、以及怎么遍历图。

课件内容：

• 6.1 什么是图
• 6.2 图的遍历
• 6.3 应用实例：拯救007
• 6.4 应用实例：六度空间
• 小白专场：如何建立图- C语言实现

题目内容：

• 06-图1 列出连通集
• 06-图2 Saving James Bond - Easy Version
• 06-图3 六度空间

第七讲 图（中）

最短路径问题。

课件内容：

• 7.1 最短路径问题
• 小白专场：哈利•波特的考试- C语言实现

题目内容：

• 07-图4 哈利·波特的考试
• 07-图5 Saving James Bond - Hard Version
• 07-图6 旅游规划.py

第八讲 图（下）

最小生成树问题，拓扑排序。

课件内容：

• 8.1 最小生成树问题
• 8.2 拓扑排序
• 图之习题选讲-旅游规划

题目内容：

• 08-图7 公路村村通
• 08-图8 How Long Does It Take
• 08-图9 关键活动

第九讲 排序（上）

简单排序，希尔排序，堆排序，归并排序。

课件内容：

• 9.1 简单排序（冒泡、插入）
• 9.2 希尔排序
• 9.3 堆排序
• 9.4 归并排序（3小节共28:22）
• 习题选讲-Insert or Merge

题目内容：

• 09-排序1 排序
• 09-排序2 Insert or Merge
• 09-排序3 Insertion or Heap Sort

第十讲 排序（下）

快速排序，表排序，基数排序，排序算法的比较。

课件内容：

• 10.1 快速排序
• 10.2 表排序
• 10.3 基数排序
• 10.4 排序算法的比较
• 习题选讲-Sort with Swap(0,*)

题目内容：

• 10-排序4 统计工龄
• 10-排序5 PAT Judge
• 10-排序6 Sort with Swap(0, i)

第十一讲 散列查找

散列查找的核心：“直接计算”的函数怎么设计？有冲突怎么办？

课件内容：

• 11.1 散列表
• 11.2 散列函数的构造方法
• 11.3 冲突处理方法
• 11.4 散列表的性能分析
• 11.5 应用实例:词频统计
• 小白专场[陈越]：电话聊天狂人- C语言实现
• 习题选讲-Hashing - Hard Version

题目内容：

• 11-散列1 电话聊天狂人
• 11-散列2 Hashing
• 11-散列3 QQ帐户的申请与登陆
• 11-散列4 Hashing - Hard Version

第十二讲 KMP算法

课件内容：

• 串的模式匹配（KMP算法）