第2章-数据结构与算法-第1节-概述概要PPT课件

• 有时一个数据元素可以由若干数据项 （data item）组成。数据项是具有独 立含义的最小标识单位。
第 13 页
数据对象 (data object)
• 具有相同性质的数据成员（数据 元素）的集合，数据的子集 。例： 整数数据对象
N = { 0, 1, 2, … } 学生数据对象 • 有穷集和无穷集
数据是信息的载体，是描述客观 事物的数、字符以及所有能输入 到计算机中、被计算机程序识别 和处理的符号的集合。 数值性数据 非数值性数据
第 12 页
数据元素 (data element)和 数据项（data item）
• 数据元素是数据的基本单位。在计算 机程序中常作为一个整体进行考虑和 处理。数据元素又可称为元素、结点、 记录。
第 10 页
若干名词术语
• 数据（data） • 数据元素（data element） • 数据项（data item） • 数据对象（data object） • 数据结构（data structure） • 数据类型（data type） • 抽象数据类型（ADT）
第 11 页
数据（data）
学号 课程编号 成绩 时间
学生选课系统中“学生”和“课程”这两个
实体构成了网状（图状）关系（即“选课”关
系）。
学生 (学号,姓名,性别,籍贯)
课程 (课程号,课程名,学分)
选课 (学号,课程号,成绩)
第8页
UNIX文件系统的系统结构图
/ (root)
bin
lib
user
etc
math ds sw
lin tao xie
第2页
Data Structures + Algorithms = Programs ——Nicklaus Wirth
程 序: 利用计算机语言编制的一组 具有确定功能的指令集合。
数据结构: 问题或对象的数学模型(如 何描述数据的外部表现形式 和内部存储结构)。
算 法: 处理问题的策略。
第3页
一、数据结构 研究和讨论的范畴
第2章 数据结构与算法
第1节 概述
一、数据结构讨论与研究的范畴 二、算法
学习内容与要求
• 学习和了解数据结构所研究的内容；掌握 数据的逻辑结构和存储结构的定义和基本 分类；
• 学习和掌握与数据结构有关的名词术语 （如数据、数据元素、数据对象、数据类 型、抽象数据类型ADT等等）；
• 学习和了解算法的概念、特点以及算法的 评价标准。
数据的运算，即对数据元素施加的操 作。
第 16 页
数据的逻辑结构
数据的逻辑结构从数据的逻辑关系 上描述数据，与数据的存储无关， 与数据元素本身的具体形式、内容 无关。 数据的逻辑结构可以看作是从具体 问题抽象出来的数据模型。
第 17 页
数据的逻辑结构可归结为以下四类：
集合结构：简单隶属关系 线性结构：一对一关系 树形结构：一对多关系 图状结构：多对多关系
Queue.cpp Stack.cpp Tree.cpp
第9页
数据结构的研究内容
综合上述例子可见，描述这类非数值 计算问题的数学模型不再是数学方程，而 是诸如表、树和图之类的数据结构。
简单地说，作为一门学科，数据结构 主要研究非数值计算的程序设计问题当中 计算机的操作对象（数据）以及它们之间 的关系（逻辑结构和物理结构）和操作 （算法实现）。
第5页
“课程”数据
课程编号 课 程 名
学时
024002 程序设计基础
64
024010 汇编语言
ห้องสมุดไป่ตู้48
024016 计算机原理
64
024020 数据结构
64
024021 微机技术
64
024024 操作系统
48
024026 数据库原理
48
第6页
“选课”数据
学号 98164 98164 98165 98165 98165
第 14 页
什么是数据结构
定义: 由某一数据对象及该对象中所有数据成
员之间的关系组成。 与“数据对象”这一概念的区别？ 作为术语名词和作为学科名词的区别？
第 15 页
➢作为学科，数据结构研究数据的组织 形式，包括以下内容：
数据元素间的逻辑关系，即数据的逻 辑结构。
数据元素及其关系在计算机存储内的 表示，即数据的存储表示（物理结构、 物理表示）。
第 18 页
数据逻辑结构的描述方式
Data_Structure = {D, R}
其中，D 是某一数据对象，R 是该对象中 所有数据成员之间的关系的有限集合。一般表 现形式如下：
D={d1,d2,…,dn}
R={r1,r2,…,rm}
关键字：数据元素中可用于标识该数据元素的
某个分量（数据项）。通常用关键字区别不同
的数据元素。
第 19 页
D＝{01,02,03,04,05,06,07,08,09,10}
R1={<08,05>,<05,02>,<02,01>,<01,03>,<03,09>,<09,04>,<04,06>,<06,10>, <10,07>}
R2={<01,02>,<01,05>,<01,08>,<02,03>,<02,04>,<05,06,>,<05,07>,<08,09>, <08,10>}
课程编号 024002 024016 024002 024016 024024
成绩 82 90 85 76 89
时间 06.6.10 06.6.15 06.6.10 06.6.15 06.6.13
学生
98164 98165
024002 024016 024024
课程
第7页
“选课”数据包含如下信息:
第4页
学号
1 98131 2 98164 3 98165 4 98182 5 98224 6 98236 7 98297 8 98310 9 98318
“学生”数据
姓名 刘激扬 衣春生 卢声凯 袁秋慧 洪伟 熊南燕 宫力 蔡晓莉 陈健
性别 籍 贯 出生年月 男 北 京 1979.12 男 青 岛 1979.07 男 天 津 1981.02 女 广 州 1980.10 男 太 原 1981.01 女 苏 州 1980.03 男 北 京 1981.01 女 昆 明 1981.02 男 杭 州 1979.12
R3={<01,04>,<04,01>,<01,05>,<05,01>,<01,08>,<08,01>,<04,07>,<07,04>, <05,06>,<06,05>,<06,04>,<04,06>,<05,08>,<08,05>,<06,09>,<09,06>,<0 9,02>,<02,09>,<08,10>,<10,08>,<04,03>,<03,04>}