当前位置：文档之家 › 数据结构(严蔚敏)完整第1章PPT

数据结构(严蔚敏)完整第1章PPT

  • 格式：ppt
  • 大小：547.50 KB
  • 文档页数：77

下载文档原格式

  / 77

合集下载

教学课件 数据结构--严蔚敏

教学课件 数据结构--严蔚敏
1.1 数据结构讨论的范畴 1.2 基本概念 1.3 算法和算法的量度
1.1 数据结构讨论的范畴
Niklaus Wirth：
Algorithm + Data Structures = Programs
程序设计:
算法: 数据结构:
为计算机处理问题编制 一组指令集
处理问题的策略
问题的数学模型
例如: 数值计算的程序设计问题
结构静力分析计算 ─━ 线性代数方程组
全球天气预报 ─━ 环流模式方程 (球面坐标系)
非数值计算的程序设计问题
例一: 求一组(n个)整数中的最大值 算法: ? 基本操作是“比较两个数的大小” 模型：？ 取决于整数值的范围
例二：计算机对弈
算法：? 对弈的规则和策略 模型：? 棋盘及棋盘的格局
例三：足协的数据库管理
S 是 D上关系的有限集。
数据的存储结构
—— 逻辑结构在存储器中的映象
“数据元素”的映象 ？
“关系”的映象 ？
数据元素的映象方法：
用二进制位(bit)的位串表示数据元素 (321)10 = (501)8 = (101000001)2 A = (101)8 = (001000001)2
关系的映象方法：（表示x, y的方法）
抽象数据类型的表示和实现
抽象数据类型需要通过固有数据 类型(高级编程语言中已实现的数据 类型)来实现。
例如，对以上定义的复数。
// -----存储结构的定义
typedef struct { float realpart； float imagpart；
}complex；
// -----基本操作的函数原型说明
顺序映象
以相对的存储位置表示后继关系 例如:令 y 的存储位置和 x 的存储位置之间差一个常量 C

数据结构C语言版(严蔚敏) 教材讲义242页PPT

数据结构C语言版(严蔚敏) 教材讲义242页PPT
11、越是没有本领的就越加自命不凡。——邓拓 12、越是无能的人，越喜欢挑剔别人的错儿。——爱尔兰 13、知人者智，自知者明。胜人者有力，自胜者强。——老子 14、意志坚强的人能把世界放在手中像泥块一样任意揉捏。——歌德 15、最具挑战性的挑战莫过于提升自我。——迈讲义
36、如果我们国家的法律中只有某种 神灵， 而不是 殚精竭 虑将神 灵揉进 宪法， 总体上 来说， 法律就 会更好 。—— 马克·吐 温 37、纲纪废弃之日，便是暴政兴起之 时。— —威·皮 物特
38、若是没有公众舆论的支持，法律 是丝毫 没有力 量的。 ——菲 力普斯 39、一个判例造出另一个判例，它们 迅速累 聚，进 而变成 法律。 ——朱 尼厄斯
40、人类法律，事物有规律，这是不 容忽视 的。— —爱献 生
谢谢

数据结构第一章--绪论(严蔚敏版)

数据结构第一章--绪论(严蔚敏版)

解 T = (D, R ) D={A,B,a,b,c }
R是D上的关系的集合 是 上的关系的集合
A
B
a R={ P1,P2 } P1 ={<A,a>, <A,b>, <A,c>} P2 ={<B,a>, <B,b>, <B,c>}
b
c
写出一个复数的数据结构 例3 写出一个复数的数据结构 Complex= (C , R) 解 一个复数可以表示为 a+bi 一个复数可以表示为 复数 C={a,b}
也可以表示成一个有序对 <a, b>
∴这里存在一种关系 P ={<a,b>} (只有一个有序对 只有一个有序对) 只有一个有序对
而R是C上的关系的集合 R={ P } 是 上的关系的集合
写出一个复数的数据结构 例3 写出一个复数的数据结构 Complex= (C , R) 解 一个复数的数据结构为 Complex= (C , R) 其中， 其中， C={a,b} R={ P } P ={<a,b>}
a b c
解 其数据结构可描述为 d e T = (D, R ) D是数据元素的集合 D={a,b,c,d,e} 是数据元素的集合
R是D上的关系的集合 R={ P } 是 上的关系的集合
P ={<a,b>,<a,c>,<b,d>,<b,e>}
例2
一小组有a,b,c 三个学生，一个导师A 一小组有a,b,c 三个学生，一个导师A 和一个辅导员B 和一个辅导员B，此小组的数据结构如图：
48
ADT 抽象数据类型名 { 数据对象： 数据对象：〈数据对象的定义〉 数据关系： 数据关系：〈数据关系的定义〉 基本操作： 基本操作：〈基本操作的定义〉 } ADT 抽象数据类型名 其中基本操作的定义格式为: 基本操作名（参数表） 基本操作名 初始条件：〈初始条件描述〉 初始条件： 操作结果：〈操作结果描述〉 操作结果

数据结构(C语言版) 第1章 绪论

数据结构(C语言版) 第1章 绪论
数据结构
理论课教材： 数据结构（C语言版） 严蔚敏 吴伟民 编著
第一章 绪论
1.0 1.1 1.2 1.3 1.4 学习数据结构的主要意义和要求 数据结构讨论的范畴 基本概念 抽象数据类型的表示和实现 算法和算法的度量
学习数据结构的主要意义和要求
意义：

数据结构和算法是计算机学科的两大支柱 数据结构是程序设计的基础 程序=算法+数据结构
存储结构分为： 顺序存储结构——借助元素在存储器中的相对位置来表示 数据元素间的逻辑关系 链式存储结构——借助指示元素存储地址的指针表示数据 元素间的逻辑关系 数据的逻辑结构与存储结构密切相关 逻辑结构
线性表
物理结构
顺序存储结构
树
图
链式存储结构
复合存储结构
h
h
元素1 1400
1345 元素2
链式存储
数据结构的形式定义为: 数据结构是一个二元组 Data_Structures = (D, S) 其中: D 是数据元素的有限集， S 是 D上关系的有限集。
数据元素的映象方法： 例用二进制位(bit)的位串表示数据元素
(321)10 = (501)8 = (101000001)2 A = (101)8 = (001000001)2
算法设计的要求
2. 可读性 算法主要是为了人的阅读与交流，其次才是为计算机执行，因此算法 应该易于人的理解；另一方面，晦涩难读的程序易于隐藏较多错误而难以 调试。 3．健壮性 当输入的数据非法时，算法应当恰当地作出反映或进行相应处理，而
1536
元素3
1346
元素4
∧
存储地址 1345 1346
存储内容 元素1 元素4
指针 1400 ∧

数据结构(C)严蔚敏-(文件)PPT课件

数据结构(C)严蔚敏-(文件)PPT课件

2021/3/12
Page 2
单关键字文件
❖ 文件中的记录只有一个唯一标识记录的主关键字。
多关键字文件
❖ 文件中的记录除了含有一个主关键字外，还含有若干个次关键字。
记录的属性
❖ 记录中所有非关键字的数据项。
记录的逻辑结构
❖ 记录在用户或应用程序员面前呈现的方式，是用户对数据的表示和 存取方式。
文件的检索方式
❖ 顺序存取：存取下一个逻辑记录。 ❖ 直接存取；存取第i个逻辑记录。 ❖ 按关键字存取：
简单查询、区域查询、函数查询、布尔查询
Data Structure
2021/3/12
Page 4
文件的修改
❖ 记录的插入、删除、修改。
文件的物理结构
❖ 文件在外存上的组织方式。 ➢ 顺序组织 ➢ 随机组织 ➢ 链组织
记录的物理结构
❖ 数据在物理存储器上存储的方式，是数据的物理表示和组织。
Data Structure
2021/3/12
Page 3
物理记录
❖ 计算机用一条I/0命令进行读写的基本数据单位（物理块）。 ❖ 物理记录和逻辑记录之间可能存在下列三种关系：
➢ 一个物理记录存放一个逻辑记录； ➢ 一个物理记录包含多个逻辑记录； ➢ 多个物理记录表示一个逻辑记录。
项。索引项指出该记录的物理地址。最后，索引表按关键字排序。 ❖ 只能存储在磁盘存储设备上。
Data Structure
2021/3/12
Page 8
物理记录号 职工号 姓名 职务 其他
101
29 张珊 程序员
103
05 李四 维修员
104
02 王红 程序员
105
38 刘淇 穿孔员

数据结构第一章ppt课件

数据结构第一章ppt课件
一般地说，如果指针变量pointer已指向结 构变量var，则以下三种形式等价：
（1）var.成员 （2）pointer->成员 （3）(*pointer).成员
上机作业
• 定义一个结构体变量,其成员项包括工作 证号、姓名、工资，编程计算N名职工的 总工资和平均工资。
数据结构基本概念和术语
• 程序设计=算法+数据结构 程序设计的实质即为计算机处理问题编 制一组“指令”，首先需要解决两个问 题：即算法和数据结构。算法即处理问 题的策略，而数据结构即为问题的数学 模型。
• 结构类型定义
struct 结构类型名 /* struct是结构 类型关键字*/
{
数据类型 成员名1; 数据类型 成员名2;
……
……
数据类型 成员名ｎ;
};
结构体
• 结构体变量定义
– 先定义结构体类型、再定义结构体变量 struct date birthday; – 在定义结构类型的同时，定义结构变量
• 数据结构是一门讨论"描述现实世界实体 的数学模型(非数值计算)及其上的操作在 计算机中如何表示和实现"的学科。
基本概念
• 数据
是所有能被输入到计算机中，且能被计算机处理的符 号(数字、图像等)的集合
• 数据元素
是数据中的"个体"，在计算机中通常作为一个整体进 行考虑和处理，是数据结构中讨论的"基本单位"。
• free
– 释放内存 – void free( void *p) – free(p1);
循环程序设计
• for语句的一般格式
for([变量赋初值]；[循环继续条 件]；[循环变量增值]) { 循环体语句组； }
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
顺序映象(顺序存储方法)
以相对的存储位置表示后继关系
例如:令 y 的存储位置和 x 的存储位置之 间差一个常量 C
而 C 是一个隐含值，整个存储结构中只 含数据元素本身的信息
xy
24
2007年9月5日星期三
.
链式映象(链式存储方法)
称之为组合项
15
2007年9月5日星期三
.
数据结构：带结构的数据元素的集合
假设用三个 4 位的十进制数表示一个含 12 位 数的十进制数。
例如: 3214,6587,9345 ─ a1(3214),a2(6587),a3(9345)
则在数据元素 a1、a2 和 a3 之间存在着
“次序”关系 a1,a2、a2,a3
为计算机处理问题编制 一组指令集
处理问题的策略
问题的数学模型
6 .
例如: 数值计算的程序设计问题
结构静力分析计算 ─━ 线性代数方程组
全球天气预报 ─━ 环流模式方程 (球面坐标系)
7
2007年9月5日星期三
.
非数值计算的程序设计问题
例一: 求一组(n个)整数中的最大值 算法: ? 基本操作是“比较两个数的大小” 模型：？取决于整数值的范围
第一章 绪论
1
2007年9月5日星期三
.
【课前思考】
你过去是否听说过"数据结构"？你知 道数据结构是一门讨论什么内容的学科吗？
同学们见过《算法+数据结构=程序设 计》这本书吧，它正好说明数据结构的实 质是讨论程序设计的方法。通过这门课的 学习，同学们将掌握非数值计算程序设计 中用的基本方法和技巧。
8
2007年9月5日星期三
.
例二：计算机对弈
算法：? 对弈的规则和策略 模型：? 棋盘及棋盘的格局
9
2007年9月5日星期三
.
例三：足协的数据库管理
算法：? 需要管理的项目？ 如何管理？ 用户界面？
模型：? 各种表格
10
2007年9月5日星期三
.
概括地说：
数据结构是一门讨论“描述现实 世界实体的数学模型(非数值计算) 及其上的操作在计算机中如何表 示和实现”的学科。
19
2007年9月5日星期三
.
数据的逻辑结构可归结为以下四类:
线性结构 树形结构 图状结构 集合结构
20
2007年9月5日星期三
.
数据结构的形式定义为:
数据结构是一个二元组
Data_Structures = (D, S)
其中:D 是数据元素的有限集，
S 是 D上关系的有限集。
21
2007年9月5日星期三
row = {<a1,a2>,<a2,a3>,<a4,a5>,<a5,a6>}
列的次序关系:
col = {<a1,a4>,<a2,a5>,<a3,a6>}
a1 a3 a5
a1 a2 a3
a2 a4 a6
a4 a5 a6
17
2007年9月5日星期三
.
数据结构：带结构的数据元素的集合
再例，在一维数组 {a1, a2, a3, a4, a5, a6} 的数据元素之间存在如下的次序关系:
【知识点】
数据、数据元素、数据结构、数据类型、抽象数据类 型、算法及其设计原则、时间复杂度、空间复杂度。
3
2007年9月5日星期三
.
【学习指南】
1. 熟悉各名词、术语的含义，掌握基本概念， 特别是数据的逻辑结构和存储结构之间的关系。分 清哪些是逻辑结构的性质，哪些是存储结构的性质。
2. 了解抽象数据类型的定义、表示和实现方法。 3. 熟悉类C语言的书写规范，特别要注意值调 用和引用调用的区别，输入、输出的方式以及错误 处理方式。 4. 理解算法五个要素的确切含义和对算法正确 性的理解。 5. 掌握计算语句频度和估算算法时间复杂度的 方法。
4
2007年9月5日星期三
.
1.1 数据结构讨论的范畴 1.2 基本概念 1.3 算法和算法的量度
5
2007年9月5日星期三
.
1.1 数据结构讨论的范畴
Niklaus Wirth：
Algorithm + Data Structures = Programs
程序设计:
算法: 数据结构:
2007年9月5日星期三
{<ai, ai+1>| i=1, 2, 3, 4, 5}
可见，不同的“关系”构成不同的“结构”
或者说，数据结构是相互之间存在着某
种关系的数据元素的集合。
பைடு நூலகம்
18
2007年9月5日星期三
.
数据结构包括以下几个方面：
数据元素之间的逻辑关系，即逻辑结构 数据元素及其关系在计算机存储器中的 存储方式，即数据的存储结构 施加在该数据上的操作，即数据的运算
3214，6587，9345 ≠ 6587，3214，9345
a1 a2
2007年9月5日星期三
a3 . a2
a1
a163
数据结构：带结构的数据元素的集合
又例，在2行3列的二维数组{a1, a2, a3, a4, a5, a6}
中六个元素之间 存在两个关系:
a1 a2 a3 a4 a5 a6
行的次序关系:
.
数据元素:
是数据（集合）中的一个“个体”
是数据结构中讨论的基本单位
数据对象是性质相同的数据元素的集合
是数据的子集
14
2007年9月5日星期三
.
数据项：是数据结构中讨论的最小单位
数据元素可以是数据项的集合 例如：描述一个运动员的数据元素可以是
姓名 俱乐部名称 出生日期 参加日期 职务 业绩
年月日
11
2007年9月5日星期三
.
1.2 基本概念
一、数据与数据结构 二、数据类型 三、抽象数据类型
12
2007年9月5日星期三
.
一、数据与数据结构
数据:
所有能被输入到计算机中，且能被 计算机处理的符号的集合。
是计算机操作的对象的总称。
是计算机处理的信息的某种特定的
符号表示形式。
13
2007年9月5日星期三
.
数据的存储结构(物理结构)
—— 逻辑结构在存储器中的映象
“数据元素”的映象 ？ “关系”的映象 ？
22
2007年9月5日星期三
.
数据元素的映象方法：
用二进制位(bit)的位串表示数据元素 (321)10 = (501)8 = (101000001)2
23
2007年9月5日星期三
.
关系的映象方法：（表示x, y的方法）
2
2007年9月5日星期三
.
【学习目标】
熟悉各名词、术语的含义，掌握基本概念。理解算法 五个要素的确切含义。掌握计算语句频度和估算算法时 间复杂度的方法。
【重点和难点】
本章讨论的都是一些基本概念，因此没有难点，重点 在于了解有关数据结构的各个名词和术语的含义，以及语 句频度和时间复杂度、空间复杂度的估算 。