数据结构教程第1章绪论

《数据结构教程第1章绪论》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构汪赫瑜电子与信息工程学院计算机系数据结构课程的地位——针对非数值计算的程序设计问题，研究计算机的操作对象以及它们之间的关系和操作。——是介于数学、计算机硬件和计算机软件三者之间的一门核心课程。关系对象关系操作数学软件硬件对象关系操作学时数：72(56+16)教材：严蔚敏等，数据结构（C语言版），清华大学出版社参考书：[1]李春葆等，数据结构教程（第3版），清华大学出版社[2]殷人昆等，数据结构C语言描述，机械工业出版社第1章　绪　论1.1什么是数据结构1.2学习数据结构的意义1.3数据结构涵盖的主要内容1.4什么是抽象数据类型1.5算法效率的度量数据结构产生的背景树……..

2、……..…...…...…...…...例2人机对奕问题例3多叉路口交通灯管理问题图CEDABABACADBABCBDDADBDCEAEBECED1.1什么是数据结构是相互之间存在一种或多种特定关系的数据元素的集合，表示为：（数值或非数值）Data_Structure=（D,R）——是指同一数据元素类型中各元素之间存在的关系。元素有限集关系有限集数据(data)——所有能被计算机识别、存储和处理的符号的集合（包括数字、字符、声音、图像等信息）。数据元素(dataelement)——是数据的基本单位，具有完整确定的实际意义(又称元素、结点，顶点、记录等）。数据项(Dataitem)—

3、—构成数据元素的项目。是具有独立含义的最小标识单位（又称字段、域、属性等）。三者之间的关系：数据>数据元素>数据项例：班级通讯录>个人记录>姓名、年龄……数据、数据元素和数据项术语简介：1.2学习数据结构的意义计算机内的数值运算依靠方程式，而非数值运算（如表、树、图等）则要依靠数据结构。数据结构是一门学科，针对非数值计算的程序设计问题，研究计算机的操作对象以及它们之间的关系和操作等等。程序设计＝好算法＋好结构同样的数据对象，用不同的数据结构来表示，运算效率可能有明显的差异。1.3数据结构涵盖的内容集合结构：仅同属一个集合线性结构:一对一（1:1)树结构:一对多（1:n)图结构:多对

4、多(m:n)非线性线性逻辑结构可细分为4类：答：指数据元素之间的逻辑关系。即从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。解释1：什么叫数据的逻辑结构？（1）S=(D,R)D={a,b,c,d,e,f}R={(a,e),(b,c),(c,a),(e,f),(f,d)}解：上述表达式可用图形表示为：bcaefd此结构为线性的。例：用图形表示下列数据结构，并指出它们是属于线性结构还是非线性结构。d1d5d2d4d3该结构是非线性的。解：上述表达式可用图形表示为：（2）S=(D,R)D={di

5、1≤i≤5}R={,i

6、逻辑结构在计算机存储器内的表示（或映像）。它依赖于计算机。存储结构可分为4大类：例：复数3.0－2.3i的两种存储方式：顺序、链式、索引、散列－2.303043.00300041503043.003000415－2.3法1：地址内容法2：地址内容4字节解释2：什么叫数据的物理结构？答：在数据的逻辑结构上定义的操作算法。它在数据的存储结构上实现。最常用的数据运算有5种：插入、删除、修改、查找、排序解释3：什么是数据的运算？1.4什么是抽象数据类型1.4.1数据类型与抽象数据类型的区别？1.4.2抽象数据类型如何定义？1.4.3抽象数据类型如何表示和实现？讨论：抽象数据类型和伪码是学习

7、数据结构的工具1.4.1数据类型与抽象数据类型的区别数据类型：是一个值的集合和定义在该值上的一组操作的总称。抽象数据类型：由用户定义，用以表示应用问题的数据模型。它由基本的数据类型构成，并包括一组相关的服务（或称操作）1.4.2抽象数据类型如何定义抽象数据类型可以用以下的三元组来表示：ADT=（D，R，P）ADT抽象数据类型名{数据对象：<数据对象的定义>数据关系：<数据关系的定义>基本操作：<基本操作的定义>}ADT抽象数据类型名ADT常用定义格式数据对象D上的关系集D上的操作集例：给出自然数(NaturalNumber)的抽象数据类型定义。ADTNatural_Number{o

8、bjects:一个整数的有序子集合，它开始于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返回MAXINT