数据结构-从概念到C++实现（第4版）课件 1-1引言

1-1引言v第一章绪论课程概述两个例子讲什么？课程性质课程目标学习方法考核方案Whystudy?Whattostudy？Whataretheoutcomes?Howtostudy?Howto

pass?课程概述v第一章绪论专业基础课，在教学计划中处于核心地位——承上启下考研——必考，面试——必考（算法与数据结构是专业人士的基本功）数据结构程序设计基础数学基础电子技术基础操作系统编译原理人工智能图像处理数据库原理Web信息处理算法设计与分析计算复杂性理论计算机网络图、最短路径、散列表、生成树栈、队列、散列、索引检索、排序广义表、树、图、矩阵、搜索树栈、队列、图、矩阵、索引检索线性表、树、排序、索引、检索表、栈、队列、树、散列、排序表、栈、队列、语法树、散列课程性质属于武术中的“练功”科目课程性质为什么是核心课程？为什么必考？为什么是基本功？What1——数据结构课程研究什么？各种数据模型在内存中的存储方法及实现方法What2——通过学习数据结构课程获得什么？VonNeumann体系结构只要是程序，无不是以数据结构为基础经典数据结构和经典算法，思想、方法、技术学习过程就像思维体操，在潜移默化中提高程序设计和计算思维能力课程性质描述基本数据模型的逻辑特征，分析和评价数据模型的不同存储方法，进行存储结构定义；针对计算机领域的工程问题，构建数据模型、设计存储结构、描述存储示意图（毕业要求1.4）。描述数据结构的基本操作、经典算法、经典查找技术和排序技术的执行过程，对重要的算法进行复现；针对计算机领域的工程问题，进行算法设计并运用大O记号进行算法性能分析（毕业要求2.3）。针对计算机领域具有时空性能约束的复杂工程问题，应用数据结构的基本原则和方法，通过比较、选择、优化等过程，设计合理的存储结构和解决方案，进行数据表示、算法描述和程序实现（毕业要求2.4）。教学目标理解并掌握基本的数据结构和经典的算法思想、方法、技术，工具箱

复用、修改、重组、创新培养算法设计和分析能力算法——程序的灵魂，设计算法、评价算法、改进算法培养数据结构和算法的运用能力运用程序设计语言解决实际问题的能力，设计优美的程序培养计算思维能力计算思维——模型化、形式化、逻辑思维、抽象思维教学目标编程境界会写程序（程序设计基础的教学目标之一）会高效地写程序（代码量与编程的速度成正比）会写高效的程序（数据结构的教学目标之一）会设计算法（我们一直在努力）发明（发现）算法（计算机学者的最高境界）Page06先修知识编程基础——C++语言的基本语法数据表示：常量、变量、数组、结构体、指针数据处理：表达式、语句、三种基本程序结构数据传递：自定义函数面向对象：类、对象、构造函数与析构函数、友元函数、模板、异常处理离散数学集合、关系、递推、级数求和、数列求和、数学归纳法、图（基本概念、算法思想）概率论基础随机分布、概率分布、数学期望学习方法循序渐进，切忌心浮气躁——练功正确对待考试，学习是一个积累的过程；提高课外学习的时间和质量作习题——不做习题等于入宝山而空返知识需要通过练习来加深理解，通过学知识促进能力的提高作实验——计算机学科的特征：理论与实践紧密结合纸上得来总觉浅，绝知此事要躬行；程序设计与算法类竞赛读、仿、练、思——理解

掌握

应用读：理解科学而不是背诵科学，让知识活起来仿：在模仿中掌握套路和应用场景，让学习动起来练：蓝桥杯、POJ、杭电ACM、leetcode、CSP，让实践跃起来主讲教材教育部高等教育精品教材、“十一五”和“十二五”国家级规划教材，国家级一流课程配套教材。累计销量35万册，2020-2024年清华大学出版社畅销图书，国内超过500所高校用作主讲教材[1]ThomasH.Corman等.算法导论（第4版）.机械工业出版社.2022[2]MarkA.Weiss.数据结构与算法分析：C语言描述（第4版）.机械工业出版社.2016[3]SartajSahni.数据结构、算法与应用：C++语言描述（第2版）.机械工业出版社.2015[4]Bentley.黄倩译.编程珠玑（第2版）.人民邮电出版社.2019参考教材[1]严蔚敏等.数据结构（C语言版）.清华大学出版社.2010[2]邓俊辉.数据结构（C++语言版）第3版.清华大学出版社.2013[3]程杰.大话数据结构.清华大学出版社.2020[4]余勇.数据结构（101教材）.高等教育出版社.2024参考教材考核方案过程化考核！

过程化考核！

过程化考核！平时测验：10%，10次，在雨课堂上进行（1）考查刚学过的知识及运用；（2）自学概念性知识，通过做题考查完成情况作业：10%，5次，在雨课堂上进行（1）阶段测试：近期学过的知识及运用；（2）算法设计：满足一定的时间和空间约束实验：10%，5次，在实验中心进行期中考试：10%，第1~5章，在雨课堂或线下进行期末考试：60%，线下进行，进入大考1-1引言v第一章绪论美妙的节奏【例1-1】美妙的节奏。给定m个强音节DUM和n个弱音节da，如何将强弱音节均匀分布，得到美妙的节奏？【想法】设三角符△表示强音节DUM，圆点符●表示弱音节da，假设有5个三角符和7个圆点符，把三角符均匀散落到圆点符中的操作步骤如下：第1步把三角符和圆点符放在一行；第2步把右侧5个圆点符放在三角符的下面，得到余数是两列；第3步把右侧2个圆点符放在最左侧的两列下面，得到余数是三列；第4步把最右侧两列放在最左侧的两列下面，得到余数是一列。△△△△△●●●●●●●△△△△△●●●●●●●△△△△△●●●●●●●△△△●●●●●△△●●美妙的节奏至此，只有一列余数，停止操作，从左至右将符号连接起来，得到排列：用DUM代替三角符，用da代替圆点符，该模式变为：这个节奏是南非歌曲的拍手声。如果再进行旋转，从第三、第四个重音节开始，则形成了其他节奏。如果将该模式进行旋转，从第二个重音节开始，即：这个节奏是肯尼亚的鼓点模式。△●●△●△●●△●△●DUM-da-da-DUM-da-DUM-da-da-DUM-da-DUM-daDUM-da-DUM-da-da-DUM-da-DUM-da-DUM-da-da用不同的节拍数和弱音节数，可以得到大约40种节奏模式，这些节奏存在于世界各地的音乐之中。这是一个简单的算法（辗转相除法），却能生成如此多样的有趣结果！△△△●●●●●△△●●还原DNA序列【例1-2】近几十年最重要的科学成就之一就是人类基因组的解码。基因组被编码在DNA序列中，DNA是一种双螺旋结构，由四种碱基组成：胞嘧啶（Cytosine）、鸟嘌呤（Guanine）、腺嘌呤（Adenine）和胸腺嘧啶（Thymine）。为确定未知DNA序列的组成，可以先将DNA序列分割成若干含有三个碱基的小片段，如何将这些小片段拼接成DNA序列呢？还原DNA序列【例1-2】还原DNA序列。如何将这些小片段拼接成DNA序列？【想法】假设有以下DNA小片段：GTG、TGG、ATG、GGC、GCG、CGT、GCA、TGC、CAA和AAT，将所有小片段构建一个有向图。其中，边是长度为3的碱基小片段，取该小片段中前两个和后两个高分子，得到边依附的两个顶点。找出经过所有边一次且仅一次的回路AT-TG-GC-CG-GT-TG-GG-GC-CA-AA-AT，即欧拉回路，就得到了DNA序列ATGCGTGGCAAT。很多问题抽象的数据模型是图结构，欧拉回路算法