Houfeng Wang, ICL of PKU 1 ¸ª ¤º˚ Æ £"˝ı"æ ˜£"¸ª ¤º˚ Æ ——CˆŁ˚£¤¯˜¸—¢£' ¨ ˛£" (1) ˚ Æ £¤—¿¨"£' (2) ˚ Æ º¸ª ¤ ˛£¤ C++£' ¯ˆœ£ `ıˇ ¨º Houfeng Wang, ICL of PKU 2 1. »ø– ¯˜ ˛˚˙ ˚ Æ ¸ª ¤ Øˇ˚—˝ Houfeng Wang, ICL of PKU 3 1. »ø– ¯˜ ¾˛˚˙ ˚ Æ ¸ª ¤ Øˇ˚—˝ Houfeng Wang, ICL of PKU 4 ˛˚˙ ¶¤£"ˆ…˘¸ª»œ ˚…˚˛˚£" – ¨"˛–˚"·ƒ˜˚£¤˚ Æ ˛˚£'£» – ¨"˛·ƒ˚˚£¤¸ª ¤˛˚£'£» ˛˚˙ Ł£" – ˛£"ˆ¨ ˛˚˜˜ ˇ£» – Ł…˘£"Ł…˘˚ Æ º¸ª ¤£¤–¿˛˜¨£' – –´º£"¡æ˚˚–˜ —Ł…˘–—· — – ˚ +˛ » £"¡»¶¤˜˚¨º£ ˚˚˙ æ¨ Houfeng Wang, ICL of PKU 5 »˝¤˛˚ Houfeng Wang, ICL of
《算法与数据结构》是一门深入探讨计算机科学核心概念的课程，由北京大学信息科学技术学院的王厚峰教授讲授。课程内容重点介绍了算法和数据结构的基本概念、理论及其在实际应用中的重要性。王教授的课程不仅深入浅出地讲述了理论知识，而且还注重实践应用，帮助学生掌握如何将复杂问题转化为计算机可处理的形式，并通过合理设计数据结构和算法来高效解决问题。
在课程的学习过程中，学生首先会接触到数据的表示和处理方法，这是理解数据结构和算法的基础。数据结构是指数据元素之间的逻辑关系以及数据的存储表示和相关运算，它的好坏直接影响着算法的效率。常见的数据结构如线性表、树、图和文件等，它们各自的特点决定了在特定场景下的适用性。例如，线性表适用于元素间关系简单、顺序性强的情况；树结构适用于表示层次关系，如组织结构图；图结构则能够表示复杂的网络关系，如社交网络。每一种数据结构都有其特有的运算方式，如树的遍历、图的搜索等。
数据结构的选择与设计必须基于对问题的深刻理解。在这个过程中，抽象数据类型（ADT）的概念起到了桥梁的作用。抽象数据类型将数据的表示与操作封装起来，只暴露出必要的接口给外部使用，从而提高了代码的可重用性和模块化。通过使用ADT，开发者能够在不了解数据内部细节的情况下，对其加以操作，这对于构建大型系统尤为重要。
与数据结构紧密相连的是算法。算法是解决问题的一系列操作步骤，它是程序的核心。一个有效的算法必须具备几个基本特性：有限性（算法必须在有限步骤后完成），确定性（算法的每一步都必须明确无误），输入（算法至少需要零个输入），输出（算法至少产生一个输出），以及可行性（算法必须能在有限资源下执行）。在设计算法时，我们通常会采用贪心法、分治法、回溯法、动态规划法和分支界限法等策略，这些都是解决特定问题时的常见方法。
算法的性能分析是判断一个算法好坏的重要手段。性能分析主要关注算法的空间复杂性和时间复杂性，即算法对存储空间和运行时间的需求。在评估时，大O表示法经常被用来描述算法复杂性的上限，它有助于我们了解随着输入规模的增长，算法性能的变化趋势。例如，对于排序算法而言，冒泡排序的时间复杂度是O(n^2)，而快速排序在最坏的情况下也是O(n^2)，但在平均情况下可以达到O(nlogn)，这就说明了在处理大量数据时，快速排序往往更有效率。
王厚峰教授在课程中推荐了两本参考书籍，一本是《数据结构》（许卓群），另一本是《数据结构与算法分析（C++版）》。这两本书籍是学习算法与数据结构的宝贵资源，它们涵盖了从基础概念到复杂应用的各个方面，并且通过丰富的实例和习题来加深学生对知识点的理解。
总体而言，《算法与数据结构》这门课程是计算机科学与技术专业学生不可或缺的基础课程之一。它不仅为学生打下了坚实的理论基础，而且还培养了学生解决实际问题的能力。正如计算机科学领域的著名学者N. Wirth所言：“算法+数据结构=程序”，这句话精辟地概括了算法和数据结构在计算机程序开发中的重要性。通过本课程的学习，学生将能够掌握将复杂问题转化为计算机程序的技能，并在未来的工作中更加得心应手地设计和实现高效、优雅的程序。
