数据结构

数据结构汪赫瑜电子与信息工程学院计算机系2020/7/152数据结构课程的地位——针对非数值计算的程序设计问题，研究计算机的操作对象以及它们之间的关系和操作。——是介于数学、计算机硬件和计算机软件三者之间的一门核心课程。关系对象关系操作数学软件硬件对象关系操作Data_Structure=（D,R）2020/7/153学时数：80教材：严蔚敏等，数据结构（C语言版），清华大学出版社，1997年4月第1版（配题集）参考书：[1]殷人昆等，数据结构（用面向对象方法与C++描述），清华大学出版社，1999年7月（2002年配习题集）[2]资讯教育小组，数据结构C语言版，中国铁道出版社。2020/7/154第1章绪论1.1什么是数据结构1.2学习数据结构的意义1.3数据结构涵盖的主要内容1.4什么是抽象数据类型1.5算法效率的度量2020/7/1552020/7/156数据结构产生的背景树……..……..…...…...…...…...–例2人机对奕问题2020/7/157例3多叉路口交通灯管理问题图CEDABABACADBABCBDDADBDCEAEBECED2020/7/1581.1什么是数据结构是相互之间存在一种或多种特定关系的数据元素的集合，表示为：（数值或非数值）Data_Structure=（D,R）——是指同一数据元素类型中各元素之间存在的关系。元素有限集关系有限集2020/7/159数据(data)——所有能被计算机识别、存储和处理的符号的集合（包括数字、字符、声音、图像等信息）。数据元素(dataelement)——是数据的基本单位，具有完整确定的实际意义(又称元素、结点，顶点、记录等）。数据项(Dataitem)——构成数据元素的项目。是具有独立含义的最小标识单位（又称字段、域、属性等）。三者之间的关系：数据数据元素数据项例：班级通讯录个人记录姓名、年龄……数据、数据元素和数据项术语简介：2020/7/15102020/7/15111.2学习数据结构的意义计算机内的数值运算依靠方程式，而非数值运算（如表、树、图等）则要依靠数据结构。数据结构是一门学科，针对非数值计算的程序设计问题，研究计算机的操作对象以及它们之间的关系和操作等等。程序设计＝好算法＋好结构同样的数据对象，用不同的数据结构来表示，运算效率可能有明显的差异。2020/7/15121.3数据结构涵盖的内容2020/7/1513集合结构：仅同属一个集合线性结构:一对一（1:1)树结构:一对多（1:n)图结构:多对多(m:n)非线性线性逻辑结构可细分为4类：答：指数据元素之间的逻辑关系。即从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。解释1：什么叫数据的逻辑结构？2020/7/1514（1）S=(D,R)D={a,b,c,d,e,f}R={(a,e),(b,c),(c,a),(e,f),(f,d)}解：上述表达式可用图形表示为：bcaefd此结构为线性的。例：用图形表示下列数据结构，并指出它们是属于线性结构还是非线性结构。2020/7/1515d1d5d2d4d3该结构是非线性的。解：上述表达式可用图形表示为：（2）S=(D,R)D={di|1≤i≤5}R={(di,dj),ij}2020/7/1516答：物理结构亦称存储结构，是数据的逻辑结构在计算机存储器内的表示（或映像）。它依赖于计算机。存储结构可分为4大类：例：复数3.0－2.3i的两种存储方式：顺序、链式、索引、散列－2.303023.00300041503023.003000415－2.3法1：地址内容法2：地址内容2字节解释2：什么叫数据的物理结构？2020/7/1517答：在数据的逻辑结构上定义的操作算法。它在数据的存储结构上实现。最常用的数据运算有5种：插入、删除、修改、查找、排序解释3：什么是数据的运算？2020/7/15181.4什么是抽象数据类型1.4.1数据类型与抽象数据类型的区别？1.4.2抽象数据类型如何定义？1.4.3抽象数据类型如何表示和实现？讨论：抽象数据类型和伪码是学习数据结构的工具2020/7/15191.4.1数据类型与抽象数据类型的区别数据类型：是一个值的集合和定义在该值上的一组操作的总称。抽象数据类型：由用户定义，用以表示应用问题的数据模型。它由基本的数据类型构成，并包括一组相关的服务（或称操作）它与数据类型实质上是一个概念，但其特征是使用与实现分离，实行封装和信息隐蔽（独立于计算机）2020/7/15201.4.2抽象数据类型如何定义抽象数据类型可以用以下的三元组来表示：ADT=（D，R，P）ADT抽象数据类型名{数据对象：数据对象的定义数据关系：数据关系的定义基本操作：基本操作的定义}ADT抽象数据类型名ADT常用定义格式数据对象D上的关系集D上的操作集2020/7/1521例：给出自然数(NaturalNumber)的抽象数据类型定义。ADTNatural_Numberisobjects:一个整数的有序子集合，它开始于0，结束于机器能表示的最大整数(MAXINT)functions:对于所有的x,yNatural_Number；TRUE,FALSEBoolean；+,-,,==,=等都是可用的服务。Zero()：NaturalNumber返回0IsZero(x)：Booleanif(x==0)返回TRUEelse返回FALSEAdd(x,y)：NaturalNumberif(x+y=MAXINT)返回x+yelse返回MAXINTSubtract(x,y):NaturalNumberif(xy)返回0else返回x-yEqual(x,y):Booleanif(x==y)返回TRUEelse返回FALSESuccessor(x):NaturalNumberif(x==MAXINT)返回xelse返回x+1endNatural_Number2020/7/15221.4.3抽象数据类型如何表示和实现抽象数据类型可以通过固有的数据类型（如整型、实型、字符型等）来表示和实现。注1：它有些类似C语言中的结构（struct)类型，但增加了相关的服务。注2：教材中用类C语言（介于伪码和C语言之间）作为描述工具。其描述语法汇总在教材P10-11上。但上机时要用具体语言实现，如C或C++等2020/7/1523提示：教材中例1-6和例1-7分别给出了抽象数据类型“三元组”的定义、表示和实现，请自己先试读一遍。当课程内容学习到50%以后，你再回头看这个例子，会发现自己已能完全看懂了！2020/7/15241.5算法效率的度量1.5.1什么是算法？如何评判算法的好坏？1.5.2时间复杂度和空间复杂度如何表示？1.5.3计算举例2020/7/15251.5.1什么是算法？如何评判一个算法的好坏？常用时间复杂度来衡量算法的基本特性：算法评价指标：有穷性、确定性、可行性、必有输出正确性、可读性、健壮性、效率与低存储量需求常用空间复杂度来衡量程序设计的实质：好算法＋好结构算法是对特定问题求解步骤的一种描述，它是指令的有限序列，是一系列输入转换为输出的计算步骤。4个层次2020/7/1526算法中实现基本操作的语句（基本语句）重复执行的次数，称为算法的频度。记作：T(n)=O(f(n))随问题规模n的增大，算法的频度T(n)和f(n)的增长率同阶。例1：x+=5;单个语句的频度为1，则程序段的时间复杂度为T(n)=O(1)。2020/7/15271.5.3计算举例该算法的运行时间由程序中所有语句的频度（即该语句重复执行的次数）之和构成。解：分析：T(n)=2n2+2n+1当n充分大时，T(n)与n2是同阶的。该算法时间复杂度为：T(n)=O(n2)算法的时间复杂度由嵌套最深层语句的频度决定例：分析以下程序段的时间复杂度。for(i=1;i=n;++i)/*n+1*/for(j=1;j=n;++j)/*n(n+1)*/c[i][j]=0;/*n2*/2020/7/1528例题s=0/*1*/for(i=0;in;i++)/*n+1*/for(j=0;jm;j++)/*n(m+1)*/s+=B[i][j];/*n*m*/sum=s/*1*/时间复杂度:T(n)=O(2(n*m)+2n+3)=O(n*m)2020/7/1529注：1）O（）为渐近符号。2）空间复杂度S(n)按数量级递增顺序也与上表类似。复杂度高复杂度低时间复杂度T(n)按数量级递增顺序为：1.5.2时间复杂度和空间复杂度如何表示？多项式阶2020/7/1530本章小结数据结构课程——数据结构＋算法＝程序，涉及数学、计算机硬件和软件。数据结构定义——指互相有关联的数据元素的集合，可用data_Structure=(D,R)表示。数据结构内容——数据的逻辑结构、存储结构和基本运算数据结构学习工具——抽象数据类型和伪码（类C）算法效率指标——时间效率和空间效率第1章结束2020/7/1531练习：①复习C语言，重点是结构体和递归概念，链表操作。有下列几种用二元组表示的数据结构，画出它们分别对应的图形表示，并指出它们分别属于何种结构1）A=(K,R),其中：K={a,b,c,d,e,f,g,h}R={r}r={a,b,b,c,c,d,d,e,e,f,f,g,g,h}2)B=(K,R),其中：K＝{a,b,c,d,e,f,g,h}R={r}r={d,b,d,g,d,a,b,c,g,e,g,h,e,f}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)}2020/7/1532练习计算下列程序段的时间复杂度：1)i=s=0while(sn){i++;S+=i;}2）i=1；while(i=n)i=i*2;2020/7/1533数据结构课程的起点：2020/7/1534线性结构的定义：若结构是非空有限集，则有且仅有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。可表示为：（a1,a2,……,an）简言之，线性结构反映结点间的逻辑关系是的。特点①只有一个首结点和尾结点；特点②除首尾结点外，其他结点只有一个直接前驱和一个直接后继。线性结构包括：线性表、堆栈、队列、字符串、数组等，其中最典型、最常用的是------线性表一对一(1:1)2020/7/1535第2章线性表2.1线性表的逻辑结构2.2线性表的顺序表示和实现2.3线性表的链式表示和实现2.4应用举例2020/7/1536（a1,a2,…ai-1，ai,ai＋1，…,an）2.1线性表的逻辑结构线性表的定义：用数据元素的有限序列表示n=0时称为数据元素线性起点ai的直接前趋ai的直接后继下标，是元素的序号，表示元素在表中的位置n为元素总个数，即表长。n≥0空表线性终点2020/7/1537（A,B,C,D,……,Z）学号姓名性别年龄班级0406010402陈杰2004级计软04-1班0406010405邓博2004级计软04-1班0406010406管杰2004级计软04-1班0406010410黄腾达2004级计软04-1班0406010413李荣智2004级计软04-1班：：：：：例2分析学生情况登记表是什么结构。分析：数据元素都是同类型（记录），元素间关系是线性的。分析：数据元素都是同类型（字母），元素间关系是线性的。注意：同一线性表中的元素必定具有相同特性！例1分析26个英文字母组成的英文表是什么结构。2020/7/1538“同一数据逻辑结构中的所有数据元素都具有相同的特性”是指数据元素所包含的数据项的个数都相等。×是指各元素具有相同的数据类型试判断下列叙述的正误：2020/7/15392.2线性表的顺序表示和实现2.2.1顺序表的表示2.2.2顺序表的实现2.2.3顺序表的运算效率分析2020/7/154