北京师范大学数据结构教学资料 第1章-绪论

Chapter01·Introduction数据结构第1章绪论|北京师范大学计算机科学与技术专业课程Contents目录北京师范大学·数据结构教学资料第1章绪论01课程概述与学习意义02数据结构基本概念03算法与算法分析04学习方法与课程要求Chapter01课程概述与学习意义理解数据结构的学科定位、核心价值与课程体系中的基础性作用CHAPTER01·绪论什么是数据结构数据结构是计算机存储和组织数据的方式，研究数据元素之间的逻辑关系及其在计算机中的表示。高校计算机专业课堂教学场景01研究相互之间存在特定关系的数据元素集合，以及这些元素之间的逻辑关系和存储方式02精心选择的数据结构可以带来更高的运行效率和存储效率，直接影响程序的性能表现03与高效的检索算法和索引技术密切相关，是软件设计和系统开发的核心基础04计算机学科中综合性的专业基础课，为操作系统、数据库、编译原理等后续课程奠定理论基础CHAPTER01·绪论计算机发展与数据结构的诞生计算机从数值计算向非数值处理的扩展，催生了对复杂数据组织方式的研究需求。数据结构正是在应对数据量爆炸式增长和应用场景多元化的挑战中应运而生，成为计算机科学的核心研究领域。数值计算时代早期计算机主要用于科学和工程计算，处理对象是简单的数值数据，程序设计关注数学算法。PHASE01非数值数据扩展随着应用扩展，计算机开始处理文字、图像、声音等非数值数据，数据组织方式变得复杂多样。PHASE02效率核心挑战数据量的爆炸式增长使得程序效率成为关键问题，如何有效存储和组织数据成为核心挑战。PHASE03学科正式确立数据结构作为独立学科在20世纪60年代末正式确立，成为计算机专业必修的核心基础课程。1960sChapter01·绪论数据结构在课程体系中的地位数据结构是计算机专业课程体系的枢纽课程，上承编程语言与离散数学，下启操作系统、数据库、编译原理等核心课程。前置基础课程C/C++程序设计提供实现数据结构的编程工具和语法基础，包括指针操作、内存管理等核心概念离散数学为数据结构的理论分析提供数学工具和逻辑推理方法，奠定算法正确性证明基础后续核心课程操作系统文件系统、内存管理大量运用树形结构和链表数据库系统索引技术、查询优化依赖B树、哈希表等结构编译原理语法分析树的构建与遍历是编译器的核心技术人工智能搜索算法、知识表示离不开图和树的应用LEARNINGOBJECTIVES课程学习目标与能力要求数据结构课程旨在构建层次化的认知结构，从基础知识掌握到算法设计能力，再到计算思维素养，形成完整的培养目标体系。知识目标掌握线性表、栈、队列、树、图等基本数据结构的定义与特性理解顺序存储和链式存储两种基本存储方式的原理与适用场景熟悉查找、排序等基本算法的设计方法与实现技术基础认知能力目标能够针对具体问题选择合适的数据结构并设计相应算法掌握算法时间复杂度和空间复杂度的分析方法与评估技巧具备将实际问题抽象为数据模型并用程序实现的综合能力实践应用素养目标培养抽象思维能力，学会从具体问题中提取数据结构本质形成严谨的逻辑推理习惯，提升问题分析和解决能力建立计算思维意识，理解算法效率对系统性能的决定性影响思维养成CHAPTER02数据结构基本概念从数据、数据元素到数据结构，系统掌握核心术语与分类体系CHAPTER01·绪论数据的层次结构数据具有清晰的层次结构：数据项是最小单位，数据元素是基本单位，数据对象是同类元素的集合。理解这种层次关系是掌握数据结构概念的前提。数据信息的载体，包括数值、字符、声音、图像等，需经编码才能被计算机识别和处理信息载体数据元素数据的基本单位，在程序中通常作为一个整体考虑，由若干数据项组成基本单位数据项数据结构中讨论的最小单位，分为原子项（不可再分）和组合项（可再分）最小单位数据对象性质相同的数据元素的集合，可以是有限集合也可以是无限集合元素集合Definition数据结构的定义数据结构由数据元素集合D和元素间关系集合R组成，记为Data_Structure=(D,R)。不同学者从逻辑关系、物理实现、设计层次等不同视角给出了各自的定义，共同构成了对数据结构的完整理解。数学定义数据结构=(D,R)，其中D是数据元素的有限集合，R是D上关系的有限集合。这是最形式化的数学表述，揭示了数据结构的本质构成。(D,R)Sahni定义数据结构是数据对象及其实例和数据元素之间的各种联系，可通过函数定义。这一定义强调数据结构的动态行为特征。函数定义视角Shaffer定义数据结构是抽象数据类型(ADT)的物理实现，强调从抽象到具体的映射过程。该定义连接了理论与实践两个层面。ADT→物理实现Kruse三层次抽象层讨论逻辑结构与运算，数据结构层和实现层分别讨论存储细节与运算的具体实现。三层次模型提供了系统化的设计框架。抽象·结构·实现Chapter1·Fundamentals数据的逻辑结构分类数据的逻辑结构反映数据元素之间的固有关系，与计算机存储无关。根据元素间关系的不同特征，可分为集合、线性、树形和图形四种基本类型，从简单到复杂构成完整的数据组织体系。集合结构元素之间除"同属一个集合"外无其他关系，是最简单的逻辑结构，如整数集合、字符集合。最简单结构线性结构元素之间存在一对一的前后关系，每个元素最多有一个前驱和一个后继，典型应用包括数组、链表、栈、队列。数组·链表·栈·队列树形结构元素之间存在一对多的层次关系，每个元素最多有一个前驱但可有多个后继，适用于文件系统、组织架构等场景。文件系统·组织架构图形结构元素之间存在多对多的复杂关系，每个元素可有多个前驱和多个后继，典型应用于社交网络、交通网络与任务依赖图。社交网络·交通网络CHAPTER01·绪论数据的物理结构（存储结构）物理结构是逻辑结构在计算机存储空间中的具体实现形式。主要包括顺序存储和链式存储两种基本方式，前者通过物理位置相邻表示逻辑关系，后者通过指针链接分散的存储单元，各有适用场景。顺序存储结构将数据元素存放在连续的存储单元中，逻辑相邻的元素物理位置也相邻优点是支持随机访问，可通过下标直接定位元素，访问效率高缺点是插入删除操作需要移动大量元素，存储空间需要预先分配连续·随机访问链式存储结构数据元素可存放在任意存储单元中，通过指针链接表示逻辑关系优点是插入删除操作灵活，不需要移动元素，存储空间动态分配缺点是只能顺序访问，需要额外空间存储指针，存储密度较低分散·指针链接DATASTRUCTURE·CHAPTER01逻辑结构与物理结构的关系同一逻辑结构可对应多种物理实现方式，选择何种存储结构取决于具体应用场景。逻辑结构与物理结构对照表逻辑结构物理实现方式典型应用线性结构顺序存储（数组）、链式存储（链表）线性表、栈、队列树形结构顺序存储（完全二叉树）、链式存储（一般树）二叉树、B树、堆图形结构邻接矩阵、邻接表网络图、状态图集合结构哈希表、位图集合运算、快速查找同一逻辑结构可有多种物理实现，需根据应用场景选择最优存储方式DataStructure·Chapter01抽象数据类型（ADT）抽象数据类型是从使用者角度对数据结构的封装，由数据对象、数据关系和基本操作三部分组成。ADT强调接口与实现分离，是软件工程中模块化设计思想的理论基础，对大型程序开发具有重要意义。ADT定义数学模型+定义在此模型上的一组操作，使用者只关心功能而不关心实现细节数学模型ADT三要素数据对象（是什么）、数据关系（有何联系）、基本操作（能做什么）对象·关系·操作封装与抽象将数据结构的实现细节隐藏，只对外提供统一的操作接口，降低模块间耦合接口隔离工程意义支持团队协作开发，不同开发者可独立实现同一ADT，提高代码复用性和可维护性代码复用ADTEXAMPLEADT的形式化定义示例：线性表以线性表为例展示ADT的完整定义方式：明确数据对象的特征、描述元素间的逻辑关系、规范基本操作的接口。这种形式化定义为数据结构的实现提供了清晰的蓝图，是程序设计规范化的重要手段。数据对象定义01线性表是n（n≥0）个同类型数据元素的有限序列02n=0时称为空表，n>0时元素具有确定的先后顺序D={ai}数据关系定义01除第一个元素外，每个元素有且仅有一个直接前驱02除最后一个元素外，每个元素有且仅有一个直接后继<ai-1,ai>基本操作定义01InitList()初始化空表；DestroyList()销毁线性表02ListInsert(i,e)在第i个位置插入元素e03ListDelete(i)删除第i个位置的元素04GetElem(i)获取第i个元素值；ListLength()返回表长6OperationsCHAPTER03算法与算法分析掌握算法的定义与特性，学会用时间复杂度和空间复杂度评价算法效率CHAPTER01·绪论算法的定义与基本特性算法是为解决特定问题而设计的有限步骤的指令序列，必须具备输入、输出、有穷性、确定性和可行性五个基本特性。算法与程序的区别在于算法必须保证在有限步骤内终止，这是算法正确性的基本前提。01算法定义：对特定问题求解步骤的一种描述，是指令的有限序列，每条指令表示一个或多个操作02输入输出：算法有零个或多个输入，有一个或多个输出，输出与输入之间存在确定的关系03有穷性：算法必须在执行有限步骤后终止，且每一步都在有限时间内完成，区别于可能无限循环的程序04确定性：算法中每条指令必须有确切的含义，无二义性，相同输入必须产生相同输出05可行性：算法中描述的操作都可以通过已经实现的基本运算执行有限次来实现EvaluationCriteria算法设计的评价标准优秀算法应同时满足正确性、可读性、健壮性和高效率四个标准。这些标准之间存在权衡关系：追求极致效率可能牺牲可读性，增强健壮性可能增加时间开销。算法设计是一个多目标优化过程。正确性算法应能正确实现预期功能，在各种合法输入下都能产生正确输出，这是算法最基本的要求Correctness可读性算法应易于理解和交流，便于调试和维护，清晰的命名、注释和模块化结构是关键Readability健壮性对非法输入能做出适当处理，不会导致系统崩溃或产生错误结果，具备良好的容错能力Robustness效率包括时间效率（执行速度）和空间效率（内存占用），通常用时间复杂度和空间复杂度衡量EfficiencyAlgorithmAnalysis时间复杂度分析时间复杂度用大O表示法描述算法执行时间随输入规模增长的渐进趋势，是评价算法效率的核心指标。通过忽略常数因子和低阶项，聚焦于增长量级，为算法性能比较提供了统一的理论框架。大O表示法T(n)=O(f(n))，表示算法执行时间的增长率与f(n)相同，忽略常数系数和低阶项O(f(n))分析方法找出算法中基本操作的执行次数，确定其与输入规模n的函数关系，取最高阶项最高阶项常见复杂度级别O(1)<O(logn)<O(n)<O(nlogn)<O(n²)<O(n³)<O(2ⁿ)<O(n!)8Levels实际意义帮助开发者预估算法在大规模数据下的性能表现，指导算法选择与优化性能预估AlgorithmComplexity常见时间复杂度增长趋势对比不同时间复杂度随输入规模增长呈现截然不同的增长趋势。对数阶和线性阶算法在大规模数据下仍能保持较好性能，而平方阶和指数阶算法的效率会急剧下降，应尽量避免在大规模数据处理中使用。操作次数随输入规模增长数据来源：北京师范大学数据结构教学资料O(logn)对数阶：增长极为缓慢，n=1000时仅需10次操作。适用于二分查找、平衡树等分治算法。O(n)线性阶：操作次数与输入规模等比增长，n=1000时为1000次。遍历类算法的典型复杂度，效率可接受。O(nlogn)线性对数阶：归并排序、快速排序等高效排序算法的典型复杂度，n=1000时约9966次操作。O(n²)平方阶：n=1000时操作次数达100万，效率急剧下降。冒泡排序、嵌套遍历的典型复杂度，大规模场景应避免。AlgorithmAnalysis时间复杂度计算示例计算时间复杂度的关键是确定基本操作的执行次数与输入规模n的函数关系。通过分析循环结构和递归调用的执行次数，可以准确推导出算法的时间复杂度，为算法优化提供量化依据。O(n)线性复杂度单层循环执行n次，基本操作次数与n成正比随输入规模线性增长for(i=0;i<n;i++)O(n²)平方复杂度双层嵌套循环，外层n次内层n次共n²次冒泡排序、选择排序等典型场景冒泡排序·选择排序O(logn)对数复杂度循环变量每次翻倍，执行log₂n次二分查找、快速幂等分治算法二分查找·快速幂CHAPTER01·绪论空间复杂度分析空间复杂度衡量算法运行过程中额外需要的存储空间，使用大O表示法描述其随输入规模增长的趋势。时间复杂度与空间复杂度往往存在权衡关系，算法设计需要根据实际场景在两者之间做出合理取舍。01DEFINITION空间复杂度定义算法在运行过程中临时占用存储空间大小的度量，记为S(n)=O(f(n))02SCOPE计算范围只统计算法额外申请的空间，不包括输入数据本身占用的存储空间03LEVELS常见级别O(1)原地算法、O(n)线性额外空间、O(n²)二维辅助空间、O(logn)递归栈空间O(1)·O(n)·O(n²)04TRADE-OFF时空权衡哈希表用O(n)空间换取O(1)查找时间，归并排序用O(n)空间实现O(nlogn)时间Space↔Time算法分析基础最好、最坏与平均时间复杂度同一算法在不同输入下可能呈现不同的时间复杂度。最好情况给出性能上界，最坏情况给出性能下界保证，平均情况反映期望性能。实际分析中通常关注最坏情况，因为它提供了可靠的性能承诺。三种情况分析最好情况：对算法最有利的输入，执行时间最短，如顺序查找目标在首位时O(1)最坏情况：对算法最不利的输入，执行时间最长，如顺序查找目标在末位时O(n)平均情况：考虑所有可能输入的加权平均，需知道各输入出现的概率分布分析方法选择最坏情况分析最常用，提供性能的下界保证，确保算法不会更差平均情况分析更有实际意义，但计算复杂，需假设输入的概率分布摊还分析用于评估一系列操作的平均性能，如动态数组的扩容策略AlgorithmDesign常用算法设计策略算法设计是创造性工作，但有成熟的方法论可遵循。分治、贪心、动态规划和回溯是四种基本策略，分别适用于不同特征的问题。实际开发中往往需要综合运用多种策略，并配合合适的数据结构实现高效算法。分治法将问题分解为规模更小的同类子问题，递归求解后合并，如归并排序、快速排序归并排序贪心法每步选择当前最优解，期望达到全局最优，如Huffman编码、最小生成树Huffman编码动态规划通过记忆化存储子问题解避免重复计算，适用于最优子结构问题，如背包问题背包问题回溯法系统地搜索解空间，通过剪枝减少无效搜索，如N皇后问题、数独求解N皇后问题CHAPTER04学习方法与课程要求掌握高效学习方法，明确课程考核标准，为后续学习做好充分准备学习方法论数据结构课程学习方法数据结构课程理论性与实践性并重，需要采用针对性的学习方法。重视概念理解而非死记硬背，坚持编程实践巩固理论，善用图形辅助理解抽象概念，培养分析比较能力以应对不同场景。概念理解优先先理解数据结构的逻辑本质和适用场景，再记忆具体实现细节，避免本末倒置逻辑本质编程实践巩固每学一种数据结构都要动手实现，通过调试代码加深理解，纸上谈兵难以掌握精髓动手实现图形辅助思考善用图示理解抽象概念，画出数据结构和算法执行过程的示意图，建立直观认知直观认知比较分析能力对比不同数据结构和算法的优劣，理解各自的适用场景，培养技术选型的判断力技术选型学习策略课程学习难点与应对策略数据结构课程的主要难点在于概念抽象、算法复杂和编程要求高。针对这些困难，应采用案例驱动理解、手动模拟执行、模仿优秀代码等策略，循序渐进地突破学习瓶颈。概念抽象难理解难点指针、递归、树图等概念较为抽象，初学者难以建立直观认知策略结合实际案例理解概念本质，多用图形化方式展示数据结构资源参考可视化教学工具，如AlgorithmVisualizer等在线平台指针·递归·树图算法复杂难掌握难点递归算法、图算法等逻辑复杂，不易理解和调试，需要深入理解其执行机制和状态变化规律策略手动模拟算法执行过程，画出每步的状态变化图，跟踪变量取值和递归调用栈资源阅读经典教材中的详细推导，观看算法动画演示视频，使用调试工具逐步跟踪手动模拟·状态图编程实现有困难难点从理论到代码的转化需要较强的编程能力策略从模仿开始，先读懂再改写再独立写，循序渐进资源参考GitHub上的优质代码库，参与编程练习平台模仿→改写→独立ASSESSMENT课程考核方式与成绩构成数据结构课程采用多元化考核方式，平时表现、实验能力和期末考试三者并重。这种设计既考察理论学习成果，又强调编程实践能力，鼓励学生在学习过程中持续投入而非临时突击。平时成绩30%：涵盖课堂出勤、课后作业与课堂互动讨论，考察学生日常学习态度与知识理解的持续性。实验成绩30%：通过编程实践与实验报告，评估学生对数据结构算法的实现能力与问题分析能力。期末考试40%：闭卷笔试形式，综合考察数据结构理论知识的系统掌握与分析设计能力。课程成绩构成比例实验成绩与平时成绩各占30%，期末考试占40%，强调过程性评价RESOURCES推荐教材与学习资源丰富的学习资源是学好数据结构的重要保障。主教材提供系统知识框架，辅助教材补充不同视角，在线平台提供实践机会，视频资源辅助理解抽象概念。教材资源主教材《数据结构》北京师范大学出版社，李强编著，概念清晰、习题丰富辅助教材《数据结构（C语言版）》严蔚敏著，清华大学出版社，经典权威进阶阅读《算法导论》MIT出版社，适合深入理解算法设计原理在线资源编程练习LeetCode·牛客网提供大量数据结构相关题目，支持在线评测视频课程B站·中国大学MOOC多所高校的优质公开课资源可视化工具AlgorithmVisualizer直观展示算法执行过程，辅助理解抽象概念SUMMARY本章小结绪论建立了数据结构的整体认知