数据结构第一章教学.ppt
数 据 结 构,李 鑫电信学院,2023/11/14,数据结构,3,学时数：72（48+24）教 材：严蔚敏等，数据结构（C语言版）清华大学出版 社，1997年4月第1版参考书：1 数据结构教程 李春葆，清华大学出版社，2 数据结构（用面向对象方法与C+描述），殷人昆等，清华大学出版社，1999年7月 3 苏光奎等，数据结构导学，清华大学出版社，2002年2月上课班级：计软11-1、2答疑时间：周三下午静远418,2023/11/14,数据结构,4,目录,绪论,1,线性表,2,栈和队列,3,串,4,数组和广义表,5,树和二叉树,6,2023/11/14,数据结构,5,目录,7,9,图,10,查找,11,内部排序,外部排序,2023/11/14,数据结构,6,内 容 安 排,上机地点：耘慧楼210机房,2023/11/14,数据结构,7,数据结构课程的地位,针对非数值计算的程序设计问题，研究计算机的操作对象以及它们之间的关系和操作。是介于数学、计算机硬件和计算机软件三者之间的一门核心课程。,关系,对象关系操作,对象关系操作,Data_Structure=（D,R）,2023/11/14,数据结构,8,第1章绪论,讨论4个问题：,1.1 什么是数据结构1.2 基本概念和术语1.3 抽象数据类型的表示与实现1.4 算法和算法分析,2023/11/14,数据结构,9,例1学生表,数据结构产生的背景,2023/11/14,数据结构,10,例2 人机对奕问题,2023/11/14,数据结构,11,例3多叉路口交通灯管理问题,2023/11/14,数据结构,12,1.1 什么是数据结构,是相互之间存在一种或多种特定关系的数据元素的集合，表示为：,（数值或非数值）,Data_Structure=（D,R）,是指同一数据元素类型中各元素之间存在的关系。,元素有限集,关系有限集,2023/11/14,数据结构,13,数据结构是一门学科，针对非数值计算的程序设计问题，研究计算机的操作对象以及它们之间的关系和操作等等。,程序设计好算法好结构,同样的数据对象，用不同的数据结构来表示，运算效率可能有明显的差异。,1.1 数据结构的定义,2023/11/14,数据结构,14,数据结构涵盖的内容,1.1 数据结构的定义,2023/11/14,数据结构,15,数据(data)所有能被计算机识别、存储和处理的符号的集合（包括数字、字符、声音、图像等信息）。数据元素(data element)是数据的基本单位，具有完整确定的实际意义(又称元素、结点，顶点、记录等）。数据项(Data item)构成数据元素的项目。是具有独立含义的最小标识单位（又称字段、域、属性 等）。,三者之间的关系：数据 数据元素 数据项,例：班级通讯录 个人记录 姓名、年龄,数据、数据元素和数据项,术语简介：,1.2 基本概念和术语,2023/11/14,数据结构,16,1.1 数据结构的定义,2023/11/14,数据结构,17,集合结构：仅同属一个集合线性结构:一对一（1:1)树 结 构:一对多（1:n)图 结 构:多对多(m:n),非线性,线 性,逻辑结构可细分为4类：,答：指数据元素之间的逻辑关系。即从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。,解释1：什么叫数据的逻辑结构？,1.2 基本概念和术语,2023/11/14,数据结构,18,（1）S=(D,R)D=a,b,c,d,e,f R=(a,e),(b,c),(c,a),(e,f),(f,d),解：上述表达式可用图形表示为：,b c a e f d,此结构为线性的。,例：用图形表示下列数据结构，并指出它们是属于线性结构还是非线性结构。,1.2 基本概念和术语,2023/11/14,数据结构,19,d1 d5 d2 d4 d3,该结构是非线性的。,解：上述表达式可用图形表示为：,（2）S=(D,R)D=di|1i5 R=(di,dj),ij,1.2 基本概念和术语,2023/11/14,数据结构,20,答：物理结构亦称存储结构，是数据的逻辑结构在计算机存储器内的表示（或映像）。它依赖于计算机。,存储结构可分为4大类：,例：复数3.02.3i 的两种存储方式：,顺序、链式、索引、散列,法1：地址 内容,法2：地址 内容,2字节,解释2：什么叫数据的物理结构？,1.2 基本概念和术语,2023/11/14,数据结构,21,答：在数据的逻辑结构上定义的操作算法。它在数据的存储结构上实现。,最常用的数据运算有 5 种：,插入、删除、修改、查找、排序,解释3：什么是数据的运算？,1.2 基本概念和术语,2023/11/14,数据结构,22,1 数据类型与抽象数据类型的区别？2 抽象数据类型如何定义？3 抽象数据类型如何表示和实现？,讨论：,抽象数据类型和伪码是学习数据结构的工具,1.3抽象数据类型的表示与实现,2023/11/14,数据结构,23,1 数据类型与抽象数据类型的区别,数据类型：是一个值的集合和定义在该值上的一组操作的总称。,抽象数据类型：由用户定义，用以表示应用问题的数据模型。它由基本的数据类型构成，并包括一组相关的服务（或称操作）,它与数据类型实质上是一个概念，但其特征是使用与实现分离，实行封装和信息隐蔽（独立于计算机）,1.3抽象数据类型的表示与实现,2023/11/14,数据结构,24,2 抽象数据类型如何定义,抽象数据类型可以用以下的三元组来表示：ADT=（D，R，P）,ADT抽象数据类型名 数据对象：数据关系：基本操作：ADT抽象数据类型名,ADT常用定义格式,数据对象,D上的关系集,D上的操作集,1.3抽象数据类型的表示与实现,2023/11/14,数据结构,25,3 抽象数据类型如何表示和实现,抽象数据类型可以通过固有的数据类型（如整型、实型、字符型等）来表示和实现。,注1：它有些类似C语言中的结构（struct)类型，但增加了相关的服务。注2：教材中用类C语言（介于伪码和C语言之间）作为描述工具。,但上机时要用具体语言实现，如C或C+等,1.3抽象数据类型的表示与实现,2023/11/14,数据结构,26,1.4.1 什么是算法？如何评判一个算法的好坏？,常用时间复杂度来衡量,算法的基本特性：,算法评价指标：,有穷性、确定性、可行性、有输入、必有输出,正确性、可读性、健壮性、效率与低存储量需求,常用空间复杂度来衡量,程序设计的实质：好算法好结构,算法是对特定问题求解步骤的一种描述，它是指令的有限序列，是一系列输入转换为输出的计算步骤。,4个层次,1.4 算法和算法分析,2023/11/14,数据结构,27,1.4.2算法描述,1.4 算法和算法分析,算法描述可以有多种方式，语言方式、图形方式和表格方式等本书采用C/C+语言描述,2023/11/14,数据结构,28,1.4.1算法设计的目标,1.4 算法和算法分析,正确性可使用性（用户友好性）可读性健壮性高效率与低存储量需求,2023/11/14,数据结构,29,1.3.2算法效率与分析,1.4 算法和算法分析,一个算法是由控制结构（顺序、分支和循环）和原操作（指固有数据类型的操作）,算法执行时间大致为基本运算所需的时间与其运算次数的乘积,2023/11/14,数据结构,30,算法中实现基本操作的语句（基本语句）重复执行的次数，称为算法的频度。记作：T(n)=O(f(n)随问题规模n的增大，算法的频度T(n)和f(n)的增长率同阶。例1：x+=5;单个语句的频度为1，则 程序段的时间复杂度为T(n)=O(1)。,1.4 算法和算法分析,2023/11/14,数据结构,31,该算法的运行时间由程序中所有语句的频度（即该语句重复执行的次数）之和构成。,解：,分析：T(n)=2n2+2n+1 当n充分大时，T(n)与n2是同阶的。该算法时间复杂度为：T(n)=O(n2),算法的时间复杂度由嵌套最深层语句的频度决定,1.4 算法和算法分析,2023/11/14,数据结构,32,例题s=0/*1*/for(i=0;in;i+)/*n+1*/for(j=0;jm;j+)/*n(m+1)*/s+=B ij;/*n*m*/sum=s/*1*/时间复杂度:,T(n)=O(2(n*m)+2n+3)=O(n*m),1.4 算法和算法分析,2023/11/14,数据结构,33,分析以下算法的时间复杂度,Void fun(int a,int n,int k)int i;i=0;while(in&ai!=K)i+return(i),算法时间复杂度O(n),1.4 算法和算法分析,2023/11/14,数据结构,34,1.4 算法和算法分析,算法的空间分析,算法的存储量包括输入数据所占空间、程序本身所占空间和辅助变量所占空间空间复杂度是对一个算法在运行过程中临时占用的存储空间大小的量度记作：S(n)=O(g(n),2023/11/14,数据结构,35,注：1）O（）为渐近符号。2）空间复杂度S(n)按数量级递增顺序也与上表类似。,复杂度高,复杂度低,时间复杂度T(n)按数量级递增顺序为：,时间复杂度和空间复杂度如何表示？,多项式阶,1.4 算法和算法分析,2023/11/14,数据结构,36,本章小结,数据结构课程 数据结构算法程序，涉及数学、计算机硬件和软件。数据结构定义指互相有关联的数据元素的集合，可用data_Structure=(D,R)表示。数据结构内容数据的逻辑结构、存储结构和基本运算 数据结构学习工具抽象数据类型和伪码（类C）算法效率指标时间效率和空间效率,第1章结束,2023/11/14,数据结构,37,作业,有下列几种用二元组表示的数据结构，画出它们分别对应的图形表示，并指出它们分别属于何种结构1）A=(K,R),其中：K=a,b,c,d,e,f,g,h R=r r=,2)B=(K,R),其中：Ka,b,c,d,e,f,g,h R=r r=,3)C=(K,R)K=1,2,3,4,5,6 R=r r(1,2),(2,3),(2,4),(3,4),(3,5),(3,6),(4,5),(4,6),2023/11/14,数据结构,38,课后复习,复习C语言，重点是结构类型和链表操作，递归概念。,1、用循环嵌套的方法输出下面图形*,3、已知一个链表中存储了若干名学生的信息，学生的信息包括：学号、英语成绩、数学成绩、计算机成绩。现编写一个函数search（），要求根据输入的学生学号，输出他的各科成绩。,2023/11/14,数据结构,39,3、设有两个链表，每个链表中的结点包括学号、成绩。要求把两个链表合并，按学号升序排列。,课后复习,2023/11/14,数据结构,40,作业,计算下列程序段的时间复杂度：1)i=s=0 while(sn)i+;S+=i;2）i=1；while(i=n)i=i*2;,谢谢！,
