数据结构数据结构

数据结构数据结构第1页，共26页，2023年，2月20日，星期六2第2页，共26页，2023年，2月20日，星期六数据结构课程的地位

它是计算机专业及相关专业的核心课程之一，是计算机及相关专业的重要骨干基础课程。它针对非数值计算的程序设计问题，研究计算机的操作对象以及它们之间的关系和操作。即其研究目的是研究有效地组织和处理非数值类型数据的理论、技术和方法。3第3页，共26页，2023年，2月20日，星期六数据结构的核心研究内容数据的逻辑结构、存储结构及它们之间的关系和相应的基本操作运算的定义和实现。本书围绕数据结构的三种基本结构：线性结构、树形结构和图形结构展开讨论，研究解决如下问题：一个具体问题的逻辑数据结构是什么？适宜选用什么样的存储结构？采用什么样的操作实现算法效率更高？4第4页，共26页，2023年，2月20日，星期六1、上课认真听讲，适当做好笔记，按时交作业。2、考试成绩分两部分：平时成绩（包括出勤和上机实验）占40%，期末成绩占60%。3、课后需要多读课文和参考书，上网查看相关内容，在理解基本内容的基础上，多看、多做习题。4、上机实验十分重要，一定要在上机前做好充分准备，多采用不同的数据存储结构和不同的实现算法解决一个问题。对学生的几点要求5第5页，共26页，2023年，2月20日，星期六第1章绪论讨论5个问题：1.1数据结构的基本概念1.2学习数据结构的意义1.3数据结构涵盖的主要内容1.4算法效率的度量6第6页，共26页，2023年，2月20日，星期六1.1数据结构的基本概念1、举例

建立一个学生档案。学生表包括学号、姓名、性别、籍贯。要求：查找“王红”是否存在。解决的方法步骤：如何记录所有学生记录（及选择何种逻辑数据结构）？选择何种存储结构？若把所有记录依次存储在一个数组中——采用顺序存储结构若采用指针链表——采用链式存储结构7第7页，共26页，2023年，2月20日，星期六2、基本术语(1)数据：所有能被计算机识别、存储和处理的符号的集合（包括数字、字符、声音、图像等信息）。(2)数据元素:是数据的基本单位，具有完整确定的实际意义。在计算机程序中通常作为一个整体进行考虑和处理。一个数据元素可由若干个数据项组成。(3)数据项:构成数据元素的项目。它是数据不可分割的最小单位。(4)数据类型：指一个类型和定义在这个类型上的操作集合。例：C语言（基本类型：整型、浮点型、字符型等构造类型：数组、结构、联合、指针、枚举等）(5)抽象数据元素：抽象定义的、没有实际含义的数据元素。(6)抽象数据类型：用户自己定义的数据类型。8第8页，共26页，2023年，2月20日，星期六2、基本术语(续）(7)数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。或按照一定逻辑关系组织，并按一定存储方法存储的数据的集合，且需要定义一系列运算。逻辑结构、存储结构和运算合称为三要素。表示为：

Data_Structure=（D,R）

其中，D—元素有限集，R—关系有限集

9第9页，共26页，2023年，2月20日，星期六程序设计＝好算法＋好结构

同样的数据对象，用不同的数据结构来表示，运算效率可能有明显的差异。1.2学习数据结构的意义计算机内的数值运算依靠方程式，而非数值运算（如表、树、图等）则要依靠数据结构。

数据结构是一门学科，针对非数值计算的程序设计问题，研究计算机的操作对象以及它们之间的关系和操作等等。10第10页，共26页，2023年，2月20日，星期六1.3数据结构涵盖的内容11第11页，共26页，2023年，2月20日，星期六集合结构：仅同属一个集合线性结构:一对一（1:1)

树结构:一对多（1:n)

图结构:多对多(m:n)非线性线性逻辑结构可细分为4类：

指数据元素之间的逻辑关系。即从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。解释1：什么叫数据的逻辑结构？12第12页，共26页，2023年，2月20日，星期六（1）S=(D,R)D={a,b,c,d,e,f}R={(a,e),(b,c),(c,a),(e,f),(f,d)}解：上述表达式可用图形表示为：bcaefd此结构为线性的。例：用图形表示下列数据结构，并指出它们是属于线性结构还是非线性结构。13第13页，共26页，2023年，2月20日，星期六

d1d5d2d4d3该结构是非线性的。解：上述表达式可用图形表示为：（2）S=(D,R)

D={di|1≤i≤5}

R={(di,dj),i<j}14第14页，共26页，2023年，2月20日，星期六

物理结构亦称存储结构，是数据的逻辑结构在计算机存储器内的表示（或映像）。它依赖于计算机。存储结构可分为4大类：例：复数3.0－2.3i的两种存储方式：顺序、链式、索引、散列－2.303023.00300041503023.003000415－2.3法1：地址内容法2：地址内容2字节解释2：什么叫数据的物理结构？15第15页，共26页，2023年，2月20日，星期六在数据的逻辑结构上定义的操作算法。它在数据的存储结构上实现。最常用的数据运算有5种：插入、删除、修改、查找、排序解释3：什么是数据的运算？16第16页，共26页，2023年，2月20日，星期六1.4算法效率的度量1什么是算法？如何评判算法的好坏？2时间复杂度和空间复杂度如何表示？3计算举例讨论：17第17页，共26页，2023年，2月20日，星期六1什么是算法？如何评判一个算法的好坏？常用时间复杂度来衡量算法的基本特性：算法评价指标：有穷性、确定性、可行性、必有输出正确性、可读性、健壮性、高效率与低存储量需求常用空间复杂度来衡量好的程序设计：好算法＋好结构

算法：是对特定问题求解步骤的一种描述，它是指令的有限序列，是一系列输入转换为输出的计算步骤。18第18页，共26页，2023年，2月20日，星期六注：1）O（）为渐近符号。2）空间复杂度S(n)按数量级递增顺序也与上表类似。复杂度高复杂度低时间复杂度T(n)按数量级递增顺序为：2时间复杂度和空间复杂度如何表示？多项式阶19第19页，共26页，2023年，2月20日，星期六3n+2=O(n)因为3n+24n

forn26*2n+n2=O(2n)

因为6*2n+n27*2n

forn4例：渐进符号（O）的定义：当且仅当存在一个正的常数C，使得对所有的

nn0

，有f(n)Cg(n)，则：f(n)=O(g(n))20第20页，共26页，2023年，2月20日，星期六该算法的运行时间由程序中所有语句的频度（即该语句重复执行的次数）之和构成。解：分析：显然，语句①的频度是1。设语句2的频度是f(n)，则有：算法的时间复杂度由嵌套最深层语句的频度决定例：分析以下程序段的时间复杂度。i=1;①while(i<=n)i=i*2;②即f(n)≤log2n，取最大值f(n)=log2n所以该程序段的时间复杂度T(n)=1+f(n)=1+log2n=O(log2n)3计算举例21第21页，共26页，2023年，2月20日，星期六该算法的运行时间由程序中所有语句的频度（即该语句重复执行的次数）之和构成。解：例：分析以下程序段的时间复杂度。i=1;k=0;①while(i<n)

{k=k+10*i;i++;}

②即f(n)≤log2n，取最大值f(n)=log2n所以该程序段的时间复杂度T(n)=1+f(n)=1+log2n=O(log2n)3计算举例22第22页，共26页，2023年，2月20日，星期六T(n)=1+1+n+(n-1)+(n-1)=3n可表示为T(n)=O(n)3分析i=1;//1k=0;//1

while(i<n)//n{k=k+10*i;//n-1i++;//n-1}

23第23页，共26页，2023年，2月20日，星期六本章小结数据结构课程——数据结构＋算法＝程序，涉及数学、计算机硬件和软件。数据结构定义——指互相有关联的数据元素的集合，可用data_Structure=(D,R)表示。数据结构内