数据结构（Python版）课件 第1章 绪论

编程基础为什么要学习数据结构计算机及相关专业考研考博课程计算机等级考试课程程序员考试课程课程学习指导提前预习、认真听课、按时完成书面及上机作业课程特点：内容抽象、概念性强、内容灵活、不易掌握01020304先修课程的知识准备离散数学、Python语言注意循序渐进：基本概念、基本思想、基本步骤、算法设计注意培养算法设计的能力理解所讲算法、对此多做思考：若问题要求不同，应如何选择数据结构，设计有效的算法考核方式1期末成绩:60%（闭卷笔试）2平时成绩:40%课堂表现作业单元测验实验教材

[1]李冬梅,刘芳,颜荣恩．数据结构(Python版)(第2版)．人民邮电出版社,2026.（/book/details/56195）

[2]李冬梅,崔金满．数据结构习题解析与实验指导——Python版.人民邮电出版社,2023．（/book/details/48013）参考书

target目标了解数据结构研究的主要内容掌握算法的时间、空间复杂度及其分析的简易方法01OPTION02OPTION03OPTION掌握数据结构中涉及的基本概念目录导航1.11.21.3数据结构的研究内容基本概念和术语算法和算法分析

Contents

N.沃思（NiklausWirth)教授提出：程序=算法+数据结构

电子计算机的主要用途：早期：主要用于数值计算后来：非数值计算，复杂的具有一定结构关系的数据数据结构的研究内容用计算机求解问题现实世界

计算机

世界需求模型程序数学模型分析设计编程调试和维护数据结构＋算法数据结构的研究内容书目自动检索系统登录号：书名：作者名：分类号：出版单位：出版时间：价格：书目卡片书目文件按书名按作者名按分类号索引表线性表人机对弈问题树……..……..…...…...…...….../(root)binlibuseretcmathdsswyintaoxieStack.cppQueue.cppTree.cpp文件系统的系统结构图树多叉路口交通灯管理问题CEDABABACADBABCBDDADBDCEAEBECED图顶点：一条通路连线：不能同时通行染色：有连线的两个顶点不能具有相同颜色六度空间理论你和任何一个陌生人之间所间隔的人不会超过6个，也就是说，最多通过6个中间人你就能够认识任何一个陌生人。图描述非数值计算问题的数学模型不再是数学方程，而是诸如表、树、图之类的数据结构。设计出合适的数据结构及相应的算法。即：首先要考虑对相关的各种信息如何表示、组织和存储？求解非数值计算的问题数据结构的研究内容研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作。形成阶段：60年代初期，“数据结构”有关的内容散见于操作系统、编译原理和表处理语言等课程。1968年，“数据结构”被列入美国一些大学计算机科学系的教学计划。数据结构课程的形成和发展

发展阶段：数据结构的概念不断扩充，包括了网络、集合代数论、关系等“离散数学结构”的内容。70年代后期，我国高校陆续开设该课程。数据结构创始人--高德纳(DonaldErvinKnuth)程序设计是一门艺术如音乐和文学作品。BillGates“如果你学会了这本书，就直接给微软发个简历！”1968年，第一卷《基本算法》1969年，第二卷《半数字化算法》1973年，第三卷《排序与搜索》2011年，第四卷A《组合算法》……计划七卷双向链表字符串模式匹配算法KMP编译器LR……TeX，LaTeX数据结构创始人--高德纳(DonaldErvinKnuth)1938年出生，斯坦福大学计算机系教授--36岁图灵奖经典著作Knuth撰写了多部具有里程碑意义的经典著作，如《计算机程序设计艺术》，成为计算机科学领域的必读之作。创立新理论推广新技术他在算法分析、数据结构等领域创立了新理论，如算法的时间复杂度和空间复杂度分析，为后来的研究提供了重要指导。Knuth积极推广新技术和新方法，如TeX排版系统和METAFONT字体设计系统，对出版印刷领域产生了深远影响。数据结构创始人--高德纳(DonaldErvinKnuth)数据结构创始人--高德纳(DonaldErvinKnuth)Knuth在研究过程中遇到许多困难和挫折，但他始终坚定信念，持之以恒地解决问题。坚持不懈他对自己的研究成果要求极高，不断追求精益求精，力求做到最好。精益求精Knuth在数据结构领域的研究投入了大量的时间和精力，长期坚持不懈，最终取得了显著的成果。长期投入练内功不要只花功夫学习各种流行的编程语言和工具，以及一些公司招聘广告上要求的科目。学好基础课程离散数学、数据结构、计算机组成原理、操作系统、计算机网络、编译原理、数据库等。试试Knuth的TheArtofComputerProgramming的题目。多实战通过编程的实战，积累经验、内化知识。建议大家争取在大学四年中积累编写十万行代码的经验。李开复建议（专研+潜力+创新）介于数学、计算机硬件和计算机软件三者之间的一门核心课程数据结构所处的地位数据结构在计算机学科中的地位能够分析研究计算机加工的对象的特性，获得其逻辑结构，根据需求，选择合适存贮结构及其相应的算法；课程目的学习一些常用的算法；复杂程序设计的训练过程，要求编写的程序结构清楚和正确易读；初步掌握算法的时间分析和空间分析技术。目录导航1.11.21.3数据结构的研究内容基本概念和术语算法与算法分析

Contents所有能输入到计算机中去的描述客观事物的符号。数值性数据：整数、实数等；非数值性数据：字符、文本、声音、图像、视频等；数据是计算机程序加工的原料，是信息的编码表示。数据的基本单位，在计算机程序中通常作为一个逻辑整体进行处理。不同场合下，也常被称为元素、结点、顶点和记录等。1.数据（Data)2.数据元素

（DataElement）基本概念和术语三者之间的关系：数据>数据元素>数据项例：学生表

>学生记录>学号、姓名、性别……当一个数据元素包含多个部分信息时，其中每个部分信息为一个数据项。如一个学生记录可能包含学号、姓名、性别等多个数据项。数据项是构成数据元素的不可分割的最小单位，也称为字段、域或属性。3.数据项（DataItem）基本概念和术语三者之间的关系：数据>数据元素>数据项例：学生表

>学生记录>学号、姓名、性别……学号姓名分数2018001王华902018010刘丽622018006陈明542018009张强952018007许兵762018012李萍882018005李英82数据数据项数据元素基本概念和术语4.数据对象(DataObject)相同特性数据元素的集合，是数据的一个子集。整数的数据对象是集合{0,±1,±2,…}。英文字母的数据对象是集合{'a','A','b','B',…}。学生数据对象是学生记录的集合。在具体应用中，一个数据对象中的元素通常相互之间存在某种关系。基本概念和术语数据结构是带“结构”的数据元素的集合，“结构”就是指数据元素之间存在的关系。5.数据结构（DataStructure）相互之间存在一种或多种特定关系的数据元素的集合。数据结构＝数据对象＋结构数据元素之间的关系相同性质的数据元素的集合基本概念和术语数据元素之间的关系

结构现实世界的结构是纷繁复杂的

微观世界―DNA结构

宏观世界―建筑物的结构基本概念和术语数据结构的两个层次逻辑结构存储结构（物理结构）从具体问题抽象出来的数学模型数据元素间抽象化的逻辑关系与数据存储无关，独立于计算机数据元素及其关系在计算机存储器中的存储方式逻辑结构在计算机中的存储实现逻辑结构与存储结构的关系存储结构是逻辑结构在计算机中的映射。存储所有元素；存储数据元素间的关系。

逻辑结构存储结构映射逻辑结构是数据关系的抽象描述，存储结构是这些关系的具体实现。同一逻辑结构可以有不同的存储结构（顺序存储、链式存储）实现。存储结构的选择影响操作效率。划分方法一逻辑结构

线性结构有且仅有一个开始和一个终端结点，并且

所有结点都最多只有一个直接前趋和一个后继。例如：线性表、栈、队列、串非线性结构

一个结点可能有多个直接前趋和直接后继。例如：树、图02OPTION01OPTION线性结构一个对一个，如线性表、栈、队列。树形结构一个对多个，如树。集合数据元素间除“同属于一个集合”外，无其它关系。图形结构多个对多个，如图。逻辑结构划分方法二存储结构顺序存储结构借助元素在存储器中的相对位置来表示数据元素间的逻辑关系。1链式存储结构借助指示元素存储地址的指针表示数据元素间的逻辑关系。2元素n……..元素i……..元素2元素1LoLo+mLo+(i-1)*mLo+（n-1)*m存储地址存储内容顺序存储Loc(元素i)=Lo+（i-1)*m1536元素21400元素11346元素3∧元素41345h

链式存储h存储地址存储内容指针1345

元素114001346

元素4∧…….……..…….

1400

元素2

1536…….……..…….1536

元素31346逻辑结构和存储结构都相同，但运算不同，

则数据结构不同。例如，栈与队列。数据的运算1234插入查找删除修改排序5对于一种数据结构,常见的运算：小结

数据

数据元素

数据对象个体性质相同的元素加上数据元素之间的关系数据结构逻辑模型逻辑结构种类集合结构线性结构树结构图结构映射到存储器存储结构顺序存储结构链式存储结构构成的集合小结

数据的逻辑结构

数据的存储结构数据的运算：插入、删除、修改、查找、排序

线性结构

非线性结构

顺序存储

链式存储线性表树形结构图形结构逻辑结构唯一存储结构不唯一运算的实现依赖存储结构栈、队列串、数组以下说法正确的是（

）A、数据元素是数据的最小单位B、数据项是数据的基本单位C、数据结构是带有结构的各数据项的集合D、一些表面上很不相同的数据可以有相同的逻辑结构练习

D数据元素是数据的基本单位数据项是数据的最小单位数据结构是带有结构的各数据元素的集合目录导航1.11.21.3数据结构的研究内容基本概念和术语算法与算法分析

Contents算法和算法分析0102一个有穷的指令集，对解决特定问题求解步骤的一种描述。算法定义算法的描述

自然语言流程图程序设计语言伪码算法的特性：算法和算法分析12345输入

有0个或多个输入输出有一个或多个输出(处理结果)确定性每步定义都是确切、无歧义的有穷性算法应在执行有穷步后结束有效性每一条运算应足够基本算法的描述---流程图算法定义优点：直观、形象，描述顺序结构、选择结构和循环结构基本结构。缺点：灵活性不如自然语言，严密性不如伪代码或程序设计语言。问题：求解最大公约数①输入数字m和n。②m除以n，获得余数i。③如果i等于0，则n就是最大公约数。④如果i不等于0，则将n赋值给m，将i赋值给n，然后返回第②步继续执行直到i等于0。⑤返回n。算法的描述---自然语言优点：通俗易懂。缺点：描述过程则较为冗长和烦琐。算法的描述---伪代码算法定义采用某一程序语言的基本语法，具体的操作指令可结合自然语言来设计。输入：数字m、数字n，其中m和n都大于0。输出：m和n的最大公约数。 i←m%n whilei!=0： m←n n←i i←m%n优点：比自然语言更精确，更简洁，容易转换成计算机程序。缺点：不够直观、不容易排查错误。算法的描述---程序设计语言 defgreatest_common_divisor(m,n): #求m和n的最大公约数，其中m>0、n>0 i=m%n whilei!=0: m=n n=i i=m%n returnn优点：能由计算机直接执行。缺点：抽象性差，在描述过程中拘泥于算法的具体实现细节。算法的评价:正确性算法和算法分析可读性健壮性高效性（时间代价和空间代价）正确性不含语法错误；对于若干组输入数据，能够得出满足要求的结果；对于精心选择的典型、苛刻而带有刁难性的输入数据，能够得出满足要求的结果（通常以此层意义的正确性作为衡量程序是否合格的标准）；对于一切合法的输入数据，都能够得出满足要求的结果。算法的评价一个好的算法，首先应便于人们理解和相互交流，其次才是机器可执行性。可读性强的算法有助于人们对算法的理解，而难懂的算法容易隐藏错误，且难于调试和修改。可读性算法的评价

注释：给算法添加注释，以方便阅读和查错。命名：对函数、变量等对象进行合理命名。算法应具有容错处理的功能，当输入的数据不合法或运行环境改变时，算法都能恰当地做出反应或进行处理，而不是产生莫名其妙的输出结果。处理出错的方法，不应是中断程序的执行，而应是返回一个表示错误或错误性质的值，以便在更高的抽象层次上进行处理。健壮性（鲁棒性）算法的评价高效性（时间代价和空间代价）算法的效率分为时间效率和空间效率；时间效率高：运行速度快的算法；空间效率高：算法执行过程中占用内存空间少；时间效率和空间效率常不能同时兼顾，时间效率较高的算法可能是牺牲了部分空间效率而获得，通常更关注时间效率。算法的评价算法与程序算法：解决问题的一种方法或一个过程，考虑如何将输入转换成输出，一个问题可以有多种算法。程序：用某种程序设计语言对算法的具体实现。算法和算法分析数据结构通过算法实现操作算法根据数据结构设计程序程序=数据结构+算法算法的效率的度量

算法效率：用依据该算法编制的程序在计算机上执行所消耗

的时间来度量 算法和算法分析事后统计事前分析估计算法和算法分析1.事后统计：利用计算机内的计时功能，不同算法的程序可以用一组或多组相同的统计数据区分缺点必须先运行依据算法编制的程序所得时间统计量依赖于硬件、软件等环境因素，掩盖算法本身的优劣2.事前分析估计一个高级语言程序在计算机上运行所消耗的时间取决于：依据的算法选用何种策略问题的规模程序语言编译程序产生机器代码质量机器执行指令速度同一个算法用不同的语言、不同的编译程序、在不同的计算机上运行，效率均不同———使用绝对时间单位衡量算法效率不合适。算法和算法分析一个算法的执行时间大致上等于其所有语句执行时间的总和。语句的执行时间为该条语句的重复执行次数和执行一次所需时间的乘积。一条语句的重复执行次数称作语句频度（frequencycount）。算法时间效率的度量设每条语句执行一次所需的时间均是单位时间，则一个算法的执行时间可用该算法中所有语句频度之和来度量。foriinrange(n):#频度为n+1forjinrange(n):#频度为n*(n+1)c[i][j]=0#频度为n2forkinrange(n):#频度为n2*(n+1)c[i][j]=c[i][j]+a[i][k]*b[k][j]#频度为n3算法时间效率的度量n阶方阵的乘积算法：该算法中所有语句频度之和，是矩阵阶数n的函数，用f(n)表示。f(n)=2n3+3n2+2n+1基本语句重复执行的次数

时间复杂度的渐进表示法算法中重复执行次数和算法的执行时间成正比的语句对算法运行时间的贡献最大问题规模n排序：n为记录数矩阵：n为矩阵的阶数多项式：n为多项式的项数集合：n为元素个数树：n为树的结点个数图：n为图的顶点数或边数n越大算法的执行时间越长算法中基本语句重复执行的次数是问题规模n的某个函数f(n)，算法的时间量度记作：T(n)=O(f(n))。时间复杂度的渐进表示法数学符号“O”的定义为：若T(n)和f(n)是定义在正整数集合上的两个函数，则T(n)

=

O(f(n))表示存在正的常数C和n0，使得当n≥n0时都满足0≤T(n)≤Cf(n)。表示随着n的增大，算法执行的时间的增长率和f(n)的增长率相同，称渐近时间复杂度。n*n阶矩阵加法：foriinrange(n): forjinrange(n): c[i][j]=a[i][j]+b[i][j];

语句的频度（frequencycount):重复执行的次数：n*n; T(n)=O(n2)即：矩阵加法的运算量和问题的规模n的平方是同一个量级时间复杂度的渐进表示法（1）找出所有语句中语句频度最大的那条语句作为基本语句；（2）计算基本语句的频度，得到问题规模n的某个函数f(n)；（3）f(n)数量级用符号“O”表示即可。分析算法时间复杂度的基本方法f(n)=n2T(n)=O(n2)例1：N×N矩阵相乘foriinrange(n):forjinrange(n):c[i][j]=0; forkinrange(n):c[i][j]=c[i][j]+a[i][k]*b[k][j] 算法中的基本操作语句为c[i][j]=c[i][j]+a[i][k]*b[k][j];时间复杂度是由嵌套最深层语句的频度决定的

例2：for

i

in

range(n):forjinrange(i):forkinrange(j):

x=x+1语句频度=定理1.1若f(n)=amnm+am-1nm-1++a1n+a0是m次多项式，则T(n)=O(nm)。忽略所有低次幂项和最高次幂系数，体现出增长率的含义时间复杂度是由嵌套最深层语句的频度决定的例3：分析以下程序段的时间复杂度

i=1①whilei<=n:

i=i*2②即f(n)≤log2n，取最大值f(n)=log2n所以该程序段的时间复杂度T(n)=O(log2n)时间复杂度是由嵌套最深层语句的频度决定的算法的特性：总结：时间复杂度的计算过程1确定输入规模n：通常是数据的大小（如数组长度、矩阵维度等）。2确定基本语句：算法中执行次数最多的语句，最内层的循环体或递归调用。3计算基本语句频度：分析基本语句的执行次数与规模

n

的关系，得到函数

f(n)。4简化频度函数：忽略低次幂项和最高次幂系数，只留对增长率影响最大的项。5使用大O符号：取

f(n)

的数量级用大O符号表示，描述算法执行时间的上界。例4：顺序查找，在数组a[i]中查找值等于e的元素，返回其所在位置。foriinrange(n):ifa[i]==e:returni+1return0有的情况下，算法中基本操作重复执行的次数还随问题的输入数据集不同而不同。最好情况：