数据结构第1章ppt课件.ppt

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

1、数据结构佛山科学技术学院环建学院课程简介内容简介数据结构+算法=程序数据结构：问题的数学模型线性结构：线性表、栈、队列、串、…非线性结构：树…算法：求解问题的策略学时：56其中理论课46实验课10计算机专业的内功：数据结构、算法、离散数学、操作系统、数据库原理、计算机原理、编译原理、…——打基础是苦功夫，不愿吃苦是不能修成正果的！计算机的外功：语言、技术、平台、标准和工具计算机专业=编程专业?第一章绪论重点：数据结构的基本概念难点：ADT、算法复杂度基础：C语言的基本知识第一章绪论1.1什么是数据结构1

2、.2基本概念和术语1.3抽象数据类型的表示与实现1.4算法和算法分析1.4.1算法1.4.2算法设计的要求1.4.3算法效率的度量1.4.4算法的存储空间的需求1.1什么是数据结构【例1】学生成绩单要求：给定学生的学号或姓名，要求打印出其成绩；若学生不存在，则报告没有该学生的信息。学号姓名成绩PB01001张平80PB01002王晴85………1.1什么是数据结构【例1】学生成绩单计算机处理该问题时，应考虑：1)数据及其存储：学生(学号,姓名,成绩)structstudent{charsNo[8];cha

3、rsName[9];intnScore;}astStudent[200];2)基本运算的实现1.1什么是数据结构【例】图书馆的书目检索系统自动化问题【例】计算机和人对弈问题【例】多叉路口交通灯的管理问题【例】计算机辅助设计（CAD）问题【例】计算机辅助制造（CAM）问题【例】产品质量在线检测与故障诊断问题【例】智能设备控制问题【例】企业资源规划（ERP）问题【例】客户关系信息管理（CRM）问题【例】企业发展规划决策与分析问题。。。。。。1.1什么是数据结构1）描述这类非数值计算问题的数学模型不是数学方程

4、，而是树、表等之类的数据结构2）数据结构描述现实世界实体的数学模型及其上的操作在计算机中的表示和实现结论第一章绪论1.1什么是数据结构1.2基本概念和术语1.3抽象数据类型的表示与实现1.4算法和算法分析1.4.1算法1.4.2算法设计的要求1.4.3算法效率的度量1.4.4算法的存储空间的需求1.2基本概念和术语1）客观事物的符号表示2）能输入到计算机中被计算机程序处理的符号集数据(Data)1.2基本概念和术语1）数据的基本单位2）在计算机程序中作为一个整体进行考虑和处理3）一个数据元素可以由若干数

5、据项(DataItem)组成4）数据项是具有独立含义的最小标识单位数据元素(DataElement)1.2基本概念和术语性质相同的数据元素的集合e.g.C={‘A’,‘B’,…,‘Z’}数据对象(DataObject)形式定义：Data_Structure=(D,S)其中：D—数据对象,数据元素的有限集S—是D上关系的有限集数据结构(DataStructure)1.2基本概念和术语关系集合是空集，顶点元素间无任何关系。四个基本数据结构－－集合1.2基本概念和术语1)元素间的关系是1:12)一个结点（

6、除头结点外）有且仅有一个直接前驱3)一个结点（除尾结点外）有且仅有一个直接后继四个基本数据结构－－线性结构1.2基本概念和术语一个结点可以有多个直接后继（除叶子结点外），但只有一个直接前驱（除根结点外）。四个基本数据结构－－树型结构1.2基本概念和术语元素间的关系是m:n，一个结点可以有多个直接后继，也可以有多个直接前驱四个基本数据结构－－图型结构1.2基本概念和术语1.2基本概念和术语-逻辑结构数据的逻辑结构特征从逻辑关系上描述数据，与数据的存储无关从具体问题抽象出来的数据模型与数据元素本身的形式、

7、内容无关与数据元素的相对位置无关分类线性结构：线性表非线性结构：树、图1.2基本概念和术语-存储结构数据的存储结构(物理结构)数据结构在计算机中的表示(又称映像)数据元素之间的关系的表示顺序映像（顺序存储结构）向量或数组（表格存储结构）非顺序映像（链式存储结构）单链表、双链表、多重链表、循环链表索引存储结构散列(hash)存储结构借用程序语言中的“数据类型”描述存储结构算法的设计取决于选定的数据（逻辑）结构，算法的实现取决于采用的存储结构1.2基本概念和术语-数据类型数据类型—最早出现在高级程序语言中一

8、个值的集合和定义在该值集上的一组操作按“值”的不同特性，数据类型可分为：原子类型：值不可分解。如C语言中的基本类型(整型、实型、字符型和枚举型)、指针类型和空类型。结构类型：值由若干成分按某种结构组成。如C语言中的数组、结构体类型应用：计算机硬件系统、操作系统、高级语言、数据库等计算机硬件系统：位、字节、字…1.2基本概念和术语-抽象数据类型抽象数据类型(AbstractDataType,ADT)一个数学模型及定义在该模型上的一组操作。【例