数据结构教程第1章绪论.ppt

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

例3多叉路口交通灯管理问题

图CEDABABACADBABCBDDADBDCEAEBECED1.1什么是数据结构是相互之间存在一种或多种特定关系的数据元素的集合，表示为：Data_Structure=（D,R）元素有限集关系有限集（数值或非数值）——是指同一数据元素类型中各元素之间存在的关系。12345数据(data)——所有能被计算机识别、存储和处理的符号的集合（包括数字、字符、声音、图像等信息）。数据元素(dataelement)——是数据的基本单位，具有完整确定的实际意义(又称元素、结点，顶点、记录等）。数据项(Dataitem)——构成数据元素的项目。是具有独立含义的最小标识单位（又称字段、域、属性等）。例：班级通讯录个人记录姓名、年龄……三者之间的关系：数据数据元素数据项数据、数据元素和数据项术语简介：1.2学习数据结构的意义01单击此处添加小标题计算机内的数值运算依靠方程式，而非数值运算（如表、树、图等）则要依靠数据结构。单击此处添加小标题数据结构是一门学科，针对非数值计算的程序设计问题，研究计算机的操作对象以及它们之间的关系和操作等等。单击此处添加小标题同样的数据对象，用不同的数据结构来表示，运算效率可能有明显的差异。0203程序设计＝好算法＋好结构1.3数据结构涵盖的内容解释1：什么叫数据的逻辑结构？01集合结构：仅同属一个集合单击此处添加正文，文字是您思想的提炼，为了演示发布的良好效果，请言简意赅地阐述您的观点。线性结构:一对一（1:1)树结构:一对多（1:n)图结构:多对多(m:n)逻辑结构可细分为4类：答：指数据元素之间的逻辑关系。即从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。0203非线性线性（1）S=(D,R)D={a,b,c,d,e,f}R={(a,e),(b,c),(c,a),(e,f),(f,d)}解：上述表达式可用图形表示为：bcaefd此结构为线性的。例：用图形表示下列数据结构，并指出它们是属于线性结构还是非线性结构。该结构是非线性的。D={di|1≤i≤5}

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