大学数据结构《数据结构绪论》教学课件

COURSEINTRODUCTION数据结构绪论数据·结构·算法·效率时间2026年课程导览01认识数据结构学科定位与基本概念02数据的逻辑与存储逻辑结构与存储结构03算法及其效率度量算法定义与复杂度分析04课程学习路径学习目标与方法指引数据结构·课程章节01认识数据结构数据是信息的载体从数据出发，认识数据结构的研究对象数据结构课程为何重要计算机科学的核心问题：如何高效地表示并处理数据数据结构是操作系统、数据库、编译原理等后续课程的共同基础它是这些课程得以展开的共同基础。它直接影响程序的运行效率数据组织方式决定了程序的运行效率。它直接影响程序的存储开销数据组织方式同时决定了程序的存储开销。程序=数据结构+算法数据与信息的关系数据是信息的载体数据对客观事物的符号表示符号表示原始记录信息数据经加工处理后得到的有意义的结果加工结果有意义数据元素与数据项数据元素数据的基本单位，也称结点或记录数据项构成数据元素的、不可分割的最小单位数据对象性质相同的数据元素的集合，是数据的子集例：学生表中的一个学生记录是数据元素，学号、姓名则是数据项逐层拆解数据的组成单位数据结构的定义数据结构：相互之间存在一种或多种特定关系的数据元素的集合逻辑结构刻画数据元素之间的抽象关系存储结构刻画数据在计算机中的具体表示方式数据的运算定义在逻辑结构上的操作集合数据结构的三个层面“抽象关系定逻辑，具体表示定存储，操作定义定运算。”三个层面共同构成数据结构的完整刻画逻辑结构数据元素之间的抽象关系，与计算机无关存储结构数据及其关系在计算机中的具体表示数据的运算定义在逻辑结构上的操作，如插入、删除、查找学好数据结构的意义学好数据结构，收获三重成长算法设计提升算法设计能力学会为问题选择合适的数据结构抽象思维培养抽象思维学会从实际问题中提炼数据模型课程基础为后续核心专业课程打下坚实基础数据结构是算法与系统课程的共同底座数据结构·课程章节02数据的逻辑与存储结构决定关系逻辑结构与存储结构，构成数据的双重刻画逻辑结构决定数据关系逻辑结构是数据结构设计中第一步要确定的内容。逻辑结构是数据元素之间抽象关系的描述，独立于计算机。按元素间关系的不同，分为四类。集合元素间无特定关系线性元素间一对一关系树形元素间一对多关系图状元素间多对多关系线性结构：一对一元素之间是一对一的线性关系前驱后继特征直接前驱除第一个元素外，每个元素有且仅有一个直接前驱直接后继除最后一个元素外，每个元素有且仅有一个直接后继典型实例：线性表栈队列字符串树形结构：一对多树形结构的分层特征元素之间是一对多的层次关系：一个根元素无直接前驱，其余每个元素最多一个直接前驱一对多的层次关系根元素没有直接前驱其余元素最多一个直接前驱后继可有多个直接后继典型实例结构树结构二叉树结构堆图状结构与集合结构四类逻辑结构的关系复杂度由简到繁依次递增图状结构元素之间可有多对多的前驱与后继多对多：任意多个前驱与后继无向图：连接无方向有向图：连接带方向集合结构元素之间除同属一个集合外无其他关系同属一集：仅以集合归属相连无其他关系：成员之间彼此独立存储结构：从抽象到具体同一逻辑结构可以对应多种存储实现存储结构又称物理结构，是逻辑结构在计算机中的表示核心问题：如何用有限的存储单元表示元素及其关系常见四类存储结构顺序存储链式存储索引存储散列存储顺序存储与链式存储对比小结：顺序存储查询快，链式存储增删灵活顺序存储用连续单元依次存放逻辑相邻即物理相邻可随机存取链式存储用任意单元存放靠指针表示元素关系插入删除方便索引存储与散列存储存储结构的选择需要权衡

时间与空间

开销索引存储建立索引表记录关键字与地址检索快需额外空间散列存储由关键字直接计算存储地址查找效率高可能产生冲突数据结构·课程章节03算法及其效率度量算法是求解问题的步骤从算法定义到复杂度，度量效率的标尺算法是求解问题的步骤算法是求解问题的步骤。算法求解步骤对特定问题求解步骤的描述，是有限的指令序列。算法与程序的区别方法与实现算法是方法。程序是算法的具体实现。算法的核心目标目标导向正确且高效算法的五个重要特性算法必须具备以下五个特性有穷性执行有限步之后终止。确定性每条指令含义明确，无二义性。可行性每一步都能通过基本运算实现。输入有零个或多个输入。输出有一个或多个输出。算法设计的四项要求从设计角度看，衡量算法质量有四项基本要求。正确性基本标准能正确解决所要处理的问题可读性基本标准便于阅读、理解与交流健壮性基本标准对非法输入能做出合理反应高效性基本标准时间与空间开销尽可能低为什么需要效率度量“同一个问题可以有多种算法，需要客观比较其优劣。”“度量算法效率，需要从运行环境走向抽象分析。”1事后统计法依赖运行环境不具普适性依赖具体运行环境2事前分析估算法分析语句执行次数估计效率分析算法中语句的执行次数3抽象结果复杂度分析最终抽象估计被抽象为复杂度分析时间复杂度与大O表示法时间复杂度：算法执行时间随问题规模

n

增长的变化趋势大O表示法取最高阶项取执行次数的最高阶项作为复杂度忽略常数忽略常数与低阶项常见阶别（按增长快慢排列）常数阶O(1)对数阶O(logn)线性阶O(n)线性对数阶O(nlogn)平方阶O(n²)复杂度阶别增长差异显著当

n=100

时，各复杂度阶别的运算次数差距悬殊空间复杂度与复杂度权衡空间换时间，时间换空间空间复杂度算法所需存储空间随问题规模

n

增长的趋势。原地工作所需辅助空间为

常量，通常记为常数阶。时空权衡时间与空间常需折中，例如用

额外空间

换取更快速度。数据结构·课程章节04课程学习路径打好基础，方能行远明确学习目标，开启数据结构之旅课程知识体系概览四大知识板块，构建数据结构完整体系四大知识板块，构建数据结构完整体系线性结构线性表、栈、队列、串树形结构二叉树、树、堆图状结构图的存储与遍历查找与排序经典算法及其效率分析本课程的学习目标完成本课程学习后，你将具备三大核心能力：逻辑与存储掌握各类数据结构的逻辑结构与存储实现问题求解能针对实际问题选择合适的数据结构进行求解算法分析具备算法设计与复杂度分析的基本能力学习方法与建议概念理解理清逻辑结构与存储结构的对应关系动手实现结合编程实践加深对结构的理解效率分析养成主动分析复杂度的习惯理论学习与动手实践并重，是学好数据结构的关键后续课程与拓展方向数据结构是计算机专业能力成长的长期基石后续课程4项操作系统数据库原理编译原理算法设计与分析拓展方向3项高级数据结构算法竞赛机器学习中的数据