数据组织方法和一些典型算法的实现

　　“数据结构”是计算机科学与技术专业、软件工程专业甚至于其它电气信息类专业的重要专业基础课程。它所讨论的知识内容和提倡的技术方法，无论对进一步学习计算机领域的其它课程，还是对从事大型信息工程的开发，都是重要而必备的基础。

　　程序设计解决问题往往有多种方法，且不同方法之间的效率可能相差甚远。程序的时间和空间效率，不仅跟数据的组织方式有关，也跟处理流程的巧妙程度有关。本课程将介绍并探讨有关数据组织、算法设计、时间和空间效率的概念和通用分析方法，帮助学员学会数据的组织方法和一些典型算法的实现，能够针对问题的应用背景分析，选择合适的数据结构，从而培养高级程序设计技能。

　　注意：本课程只涉及最基础的数据结构和与之关联的最基本的算法，更多更复杂的数据结构和经典的解决优化问题的算法，将在后续课程中介绍。

　　本课程的特点是，对每一种重要的经典数据结构，我们都会从实际应用问题出发，导出其定义、实现（存储）方法以及操作实现，并以更丰富的综合应用案例和练习题帮助学员增强对理论的感性认识，从而明白这些数据结构为什么存在以及在什么情况下可以最好地解决什么样的问题。为了兼顾起点不同的学员，课程中特意设计了“小白专场”系列，手把手教授如何将解决问题的抽象算法用具体的代码实现，从而引导初学者更好地入门。

　　坚持完成本课程学习、并按照要求完成所有练习的学员，应该具备了攀拓（PAT - Professional Ability Test）甲级需要的所有基础知识，辅以充分的英语阅读能力和熟练的编程能力，应可以取得优良成绩。

　　课程大纲

　　第一讲 基本概念（1:15:26）[陈越]

　　1.1 什么是数据结构（4节共32:43）

　　1.2 什么是算法（3节共22:41）

　　1.3 应用实例：最大子列和问题（3节共20:02）

　　第二讲 线性结构（2:19:00）[何钦铭]

　　2.1 线性表及其实现(6小节共45:04)

　　2.2 堆栈(4小节共39:51)

　　2.3 队列(2小节共15:45)

　　2.4 应用实例：多项式加法运算(1小节10:37)

　　小白专场：多项式乘法与加法运算- C实现（3小节共27:43）

　　第三讲 树(上) （1:50:08）[何钦铭]

　　3.1 树与树的表示(5小节共38:54)

　　3.2 二叉树及存储结构(2小节共16:43)

　　3.3 二叉树的遍历(4小节共37:02)

　　小白专场：树的同构 - C语言实现（2小节共17:29）

　　第四讲 树（中）（1:06:31）[何钦铭]

　　4.1 二叉搜索树(3小节共20:57)

　　4.2 平衡二叉树(2小节共22:53)

　　小白专场：是否同一棵二叉搜索树- C实现（3小节共22:41）

　　线性结构之习题选讲[陈越]：Reversing Linked List（3小节共13:08）

　　第五讲 树（下）（1:53:28）[何钦铭]

　　5.1 堆（4小节共30:05）

　　5.2 哈夫曼树与哈夫曼编码（3小节共19:52）

　　5.3 集合及运算（2小节共12:57）

　　小白专场：堆中的路径 - C语言实现（1小节共7:51）

　　小白专场[陈越]：File Transfer - C语言实现（4小节共42:43）

　　第六讲 图（上）（1:29:32）[陈越]

　　6.1 什么是图（3小节共24:02）

　　6.2 图的遍历（4小节共22:22）

　　6.3 应用实例：拯救007（1小节共14:40）

　　6.4 应用实例：六度空间（1小节共8:06）

　　小白专场：如何建立图- C语言实现（6小节共20:22）

　　第七讲 图（中）（2:11:35）[陈越]

　　树之习题选讲-Tree Traversals Again（2小节共12:16）

　　树之习题选讲-Complete Binary Search Tree（3小节共25:47）

　　树之习题选讲- Huffman Codes（3小节共18:11）

　　7.1 最短路径问题（6小节共56:38）

　　小白专场：哈利?波特的考试- C语言实现（4小节共18:43）

　　第八讲 图（下）（57:02）[陈越]

　　8.1 最小生成树问题（2小节共20:16）

　　8.2 拓扑排序（2小节共27:57）

　　图之习题选讲-旅游规划（2小节共8:49）

　　第九讲 排序（上）（1:11:44）[陈越]

　　9.1 简单排序（冒泡、插入）（4小节共23:26）

　　9.2 希尔排序（1小节共9:29）

　　9.3 堆排序（2小节共10:27）

　　9.4 归并排序（3小节共28:22）

　　第十讲 排序（下）（54:20）[陈越]

　　10.1 快速排序（4小节共25:25）

　　10.2 表排序（2小节共12:41）

　　10.3 基数排序（3小节共12:13）

　　10.4 排序算法的比较（1小节共4:01）

　　第十一讲 散列查找（1:43:39）[何钦铭]

　　11.1 散列表(2小节共13:43)

　　11.2 散列函数的构造方法(2小节共13:05)

　　11.3 冲突处理方法(6小节共36:26)

　　11.4 散列表的性能分析(1小节10:26)

　　11.5 应用实例:词频统计(1小节6:01)

　　小白专场[陈越]：电话聊天狂人- C语言实现（4小节共23:58）

　　第十二讲 综合习题选讲（1:14:41） [陈越]

　　习题选讲-Insert or Merge（2小节共11:51）

　　习题选讲-Sort with Swap(0,*)（2小节共11:06）

　　习题选讲-Hashing - Hard Version（1小节共7:15）

　　串的模式匹配（KMP算法）（5小节共44:29）