资源描述：
《数据结构课件(清华版)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、数据结构DataStructure河南大学计算机与信息工程学院２００8．31学分： 5教材：严蔚敏等，数据结构（C语言版），清华大学出版社，1997年4月参考书：[1]殷人昆等，数据结构（用面向对象方法与C++描述），清华大学出版社，1999年7月。￥26[2]殷人昆等，数据结构习题解析，清华大学出版社，2002年4月。￥26[3]李春葆，数据结构习题与解析（C语言篇），清华大学出版社，2001年1月。￥28[4]严蔚敏等，数据结构题集(C语言版)，清华大学出版社，1997年4月。￥162内容安排章内容学时章内容学时1序论27图1
2、22线性表88动态存储管理略3栈和队列89查找124串610内部排序125数组和广义表811外部排序略6树和二叉树１212文件略注：本学期共85学时，机动5学时。3第1章序论1.1什么是数据结构1.2基本概念和术语1.3抽象数据类型的表示和实现1.4算法和算法分析作业4§1.1什么是数据结构Q1如何采用计算机解决问题？Q2数据结构解决什么样的问题？Q3《数据结构》课程介绍5Q1：如何采用计算机解决问题？答：寻求数学模型的实质：分析问题，从中提取操作的对象，并找出这些操作对象之间含有的关系，然后用数学的语言加以描述。(2)设计解此数
3、学模型的算法；(1)从具体问题抽象出一个适当的数学模型；(3)编程，测试、调整直至得到最终解答。6Q2：数据结构解决什么样的问题？答：数据结构研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科。7介于数学、计算机硬件和计算机软件三者之间的一门核心课程关系对象关系操作数学软件硬件对象关系操作Q3：《数据结构》课程介绍8§1.2基本概念和术语Q1什么是数据结构？Q2学习数据结构有什么用？Q3数据结构涵盖的主要内容？讨论：9Q1：什么是数据结构？答:(见教材P5)是相互之间存在一种或多种特定关系的数据元素的集
4、合，表示为：（数值或非数值）Data_Structure=（D,S）或：是指同一数据元素类中各元素之间存在的关系。亦可表示为：S＝（D,R）或B=（K,R）元素有限集关系有限集10术语：数据、数据元素和数据项（见教材P4定义）：数据(data)——所有能被计算机识别、存储和处理的符号的集合（包括数字、字符、声音、图像等信息）。数据元素(dataelement)——是数据的基本单位，具有完整确定的实际意义(又称元素、结点，顶点、记录等）。数据项(Dataitem)——构成数据元素的项目。是具有独立含义的最小标识单位（又称字段、域、属
5、性等）。三者之间的关系：数据>数据元素>数据项例：班级通讯录>个人记录>姓名、年龄……11Q2：学习数据结构有什么用？答：计算机内的数值运算依靠方程式，而非数值运算（如表、树、图等）则要依靠数据结构。这是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等等的学科。程序设计实质＝好算法＋好结构同样的数据对象，用不同的数据结构来表示，运算效率可能有明显的差异。12Q3：数据结构涵盖的内容？13解释1：什么叫数据的逻辑结构？答：指数据元素之间的逻辑关系。即从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机
6、的。逻辑结构可细分为4类：集合结构：仅同属一个集合线性结构:一对一（1:1)树结构:一对多（1:n)图结构:多对多(m:n)非线性线性14例：用图形表示下列数据结构，并指出它们是属于线性结构还是非线性结构。（1）S=(D,R)D={a,b,c,d,e,f}R={(a,e),(b,c),(c,a),(e,f),(f,d)}解：上述表达式可用图形表示为：bcaefd此结构为线性的。15（2）S=(D,R) D={di
7、1≤i≤5} R={(di,dj),i8、释2：什么叫数据的物理结构？答：物理结构亦称存储结构，是数据的逻辑结构在计算机存储器内的表示（或映像）。它依赖于计算机。存储结构可分为4大类：例：（见教材P6）复数3.0－2.3i的两种存储方式：顺序、链式、索引、散列－2.303023.00300041503023.003000415－2.3法1：地址内容法2：地址内容2字节17解释3：什么是数据的运算？答：在数据的逻辑结构上定义的操作算法。它在数据的存储结构上实现。最常用的数据运算有5种：插入、删除、修改、查找、排序18§1.3抽象数据类型的表示和实现Q1数据类型与抽象数据类型
9、的区别？Q2抽象数据类型如何定义？Q3抽象数据类型如何表示和实现？讨论：提示：教材中例1-6和例1-7分别给出了抽象数据类型“三元组”的定义、表示和实现，请试阅读。19Q1数据类型与抽象数据类型的区别？数据类型：是一个值的集合和定义在该值上的一组操
