数 据 结 构 主讲人:文 军.

Slides:



Advertisements
Similar presentations
一、 一阶线性微分方程及其解法 二、 一阶线性微分方程的简单应用 三、 小结及作业 §6.2 一阶线性微分方程.
Advertisements

数据结构的引入. 通讯录管理 社团机构管理 校园导航管理 通讯录管理 社团机构管理 校园导航管理.
练一练: 在数轴上画出表示下列各数的点, 并指出这些点相互间的关系: -6 , 6 , -3 , 3 , -1.5, 1.5.
第1章 绪论 数据结构(C++描述).
数据结构 DATA STRUCTURE.
《解析几何》 乐山师范学院 0 引言 §1 二次曲线与直线的相关位置.
§1 二阶与三阶行列式 ★二元线性方程组与二阶行列式 ★三阶行列式
数据结构 第一章 绪论.
数据结构 张秀虹
数据结构(C语言版) Data Structure
实用操作系统概念 张惠娟 副教授 1.
《高等数学》(理学) 常数项级数的概念 袁安锋
第一章 行列式 第五节 Cramer定理 设含有n 个未知量的n个方程构成的线性方程组为 (Ⅰ) 由未知数的系数组成的n阶行列式
第 1 章 课 程 概 论 1.1 课程的初步认识 1.2 数据结构的基本概念 1.3 算法及算法分析 1.4 实习一: 常用算法.
2-7、函数的微分 教学要求 教学要点.
第1章 绪论 本章主要内容 1.1 什么是数据结构 1.2 基本概念和术语 1.3 数据类型和抽象数据类型 1.4 算法描述与算法评价.
全国计算机等级考试 二级基础知识 第二章 程序设计基础.
《数据结构》课程简介 李武军 南京大学计算机科学与技术系 2016年秋季.
《数据库原理及应用》课程介绍 信息工程学院 孙俊国
任课教师:赵玉艳 电话: 邮箱: 数据结构 第1章 绪论(一) 任课教师:赵玉艳 电话: 邮箱: 1/
数据结构 袁平波
Computer Graphics 计算机图形学基础 张 赐 Mail: CSDN博客地址:
第一章 绪论 早期:数值计算 —— 运算对象是简单的整型、实型或布尔类型数据 中后期:非数值计算 ——
管理信息结构SMI.
全国高校数学微课程教学设计竞赛 知识点名称: 导数的定义.
辅导课程六.
第2讲 绪论(二).
数 据 结 构 计 算 机 学 院 肖明军
第一单元 初识C程序与C程序开发平台搭建 ---观其大略
§2 求导法则 2.1 求导数的四则运算法则 下面分三部分加以证明, 并同时给出相应的推论和例题 .
第一章 函数 函数 — 研究对象—第一章 分析基础 极限 — 研究方法—第二章 连续 — 研究桥梁—第二章.
动态规划(Dynamic Programming)
《数据结构》 (计科、电信专业).
《编译原理与技术》 期末复习 计算机科学与技术学院 郑启龙 李 诚 25/12/2018.
宁波市高校慕课联盟课程 与 进行交互 Linux 系统管理.
第一章 函数与极限.
C++语言程序设计 C++语言程序设计 第七章 类与对象 第十一组 C++语言程序设计.
数列.
C语言程序设计 主讲教师:陆幼利.
EBNF与操作语义 请用扩展的 BNF 描述 javascript语言里语句的结构;并用操作语义的方法描述对应的语义规则
简单介绍 用C++实现简单的模板数据结构 ArrayList(数组, 类似std::vector)
1 School of Computing and Information Engineering.
顺序表的删除.
( data structures, Algorithms and Applications in C++)
线 性 代 数 厦门大学线性代数教学组 2019年4月24日6时8分 / 45.
cn/~dongeliu/dsa.html 刘 东 信息学院6系 中国科学技术大学
用计算器开方.
<编程达人入门课程> 本节内容 内存的使用 视频提供:昆山爱达人信息技术有限公司 官网地址: 联系QQ: QQ交流群: ,
成绩是怎么算出来的? 16级第一学期半期考试成绩 班级 姓名 语文 数学 英语 政治 历史 地理 物理 化学 生物 总分 1 张三1 115
第4章 Excel电子表格制作软件 4.4 函数(一).
3.16 枚举算法及其程序实现 ——数组的作用.
多层循环 Private Sub Command1_Click() Dim i As Integer, j As Integer
第一章 绪论 1.1 引言 1.2 逻辑结构和存储结构 1.3 算法.
海报题目 简介: 介绍此项仿真工作的目标和需要解决的问题。 可以添加合适的图片。
线 性 代 数 厦门大学线性代数教学组 2019年5月12日4时19分 / 45.
GIS基本功能 数据存储 与管理 数据采集 数据处理 与编辑 空间查询 空间查询 GIS能做什么? 与分析 叠加分析 缓冲区分析 网络分析
2019/5/20 第三节 高阶导数 1.
第二节 函数的极限 一、函数极限的定义 二、函数极限的性质 三、小结 思考题.
实验目的:掌握数据的顺序存储结构及它们在计算机中的操作。 实验内容:
基于列存储的RDF数据管理 朱敏
C++语言程序设计 C++语言程序设计 第一章 C++语言概述 第十一组 C++语言程序设计.
我们能够了解数学在现实生活中的用途非常广泛
西安交通大学计教中心 ctec.xjtu.edu.cn
第十七讲 密码执行(1).
插入排序的正确性证明 以及各种改进方法.
学习数据结构的意义 (C语言版) 《数据结构》在线开放课程 主讲人:李刚
高等学校计算机专业教材 数据结构 袁平波
任课教师:戴开宇 TA:时均帅、谭肖、王安华 程序设计B班 :20-16:50(90分钟)
§2 自由代数 定义19.7:设X是集合,G是一个T-代数,为X到G的函数,若对每个T-代数A和X到A的函数,都存在唯一的G到A的同态映射,使得=,则称G(更严格的说是(G,))是生成集X上的自由T-代数。X中的元素称为生成元。 A变, 变 变, 也变 对给定的 和A,是唯一的.
海报题目 简介: 介绍此项仿真工作的目标和需要解决的问题。 可以添加合适的图片。
Presentation transcript:

数 据 结 构 主讲人:文 军

课程安排 总学时:64 讲课学时:54 实验学时:10 教材: 《数据结构C语言版》严蔚敏、吴伟民 教学参考书: -----清华大学出版社 教学参考书: (1)《数据结构C语言篇》习题与解析 李春葆 (2)《数据结构》黄杨铭 科学出版社 (3)《数据结构自学考试指导》丁宝康等 清华大学出版社,

内 容 安 排 1 2 7 10 6 8 略 3 4 9 5 11 12 章 内 容 学时 绪 论 图 线性表 动态存储管理 栈和队列 查找 内 容 学时 1 绪 论 2 7 图 10 线性表 6 8 动态存储管理 略 3 栈和队列 4 9 查找 串 内部排序 5 数组和广义表 11 外部排序 树和二叉树 12 文件

考核: 平时成绩(10%)+实验(20%)+考试(70%)

第一章 绪论 一、教学内容: 1、数据结构基本概念 数据、数据元素、数据对象、数据结构和数据类型等概念 2、算法及算法分析 性能分析与度量:算法的性能标准;空间复杂度度量;时间复杂度度量 二、教学要求: 1、了解数据、数据对象、数据元素、数据类型、数据结构、数据的逻辑结构与物理结构概念及逻辑结构与物理结构间的关系 2、了解算法的定义、算法的特性、算法的时间代价、算法的空间代价 3、掌握计算语句频度和估算算法时间复杂度的方法

什么是数据结构 基本概念和术语  抽象数据类型的概念 算法和算法分析 第一章 绪论 什么是数据结构 基本概念和术语  抽象数据类型的概念 算法和算法分析

1.1 什么是数据结构 一、了解计算机的主要用途: 处理逐渐扩大到非数值计算领域(能处理多种复杂的具有一定结构关系的数据)。 早期: 主要用于数值计算。 后来: 处理逐渐扩大到非数值计算领域(能处理多种复杂的具有一定结构关系的数据)。

数值计算与非数值计算的区别? 数值计算的特点是: 数值计算的关键是: 如何得出数学模型(方程)? 程序设计人员比较关注程序设计的技巧。 数据元素之间的相互关系一般无法用数学方程加以描述,程序设计人员主要关心的是如何设计出能恰当表达问题本质的数据模型,并在该模型上建立一组相应的服务(操作).

非数值计算问题举例: 例1.1 电话号码查询问题: (1)按顺序存储方式:须遍历表 (2)按姓氏索引方式:索引 例1.1 电话号码查询问题: (1)按顺序存储方式:须遍历表 (2)按姓氏索引方式:索引 要写出好的查找算法,取决于这张表的结构及存储方式。 电话号码表的结构和存储方式决定了查找(算法)的效率。

例1.2 田径赛的时间安排问题(无向图的着色问题) : 例1.2 田径赛的时间安排问题(无向图的着色问题) : 设有六个比赛项目,规定每个选手至多可参加三个项目,有五人报名参加比赛(如下表所示)设计比赛日程表,使得在尽可能短的时间内完成比赛。

(1)设用如下六个不同的代号代表不同的项目: 跳高 跳远 标枪 铅球 100米 200米 A B C D E F (2)用顶点代表比赛项目 不能同时进行比赛的项目之间连上一条边。 (3)某选手比赛的项目必定有边相连(不能同时比赛)。

只需安排四个单位时间进行比赛 1 A,C 2 B,D 3 E 4 F 比赛时间 比赛项目 姓名 项目1 项目2 项目3 丁一 A B E 马二 C D 张三 F 李四 王五 只需安排四个单位时间进行比赛 比赛时间 比赛项目 1 A,C 2 B,D 3 E 4 F A B F E C D

求解非数值计算问题主要考虑的是: 设计出合适的数据结构及相应的算法。即先要考虑对相关的各种信息如何表示、组织和存储.

二、学习数据结构有什么用? 程序设计的实质是对实际问题选择一个好的数据结构,加之设计一个好的算法。而好的算法在很大程度上取决于描述实际问题的数据结构。 计算机内的数值运算依靠方程式,而非数值运算(如表、树、图等)则要依靠数据结构。

三、数据结构课程的形成和发展: 形成阶段: 60年代初期,“数据结构”有关的内容散见于操作系统、编译原理和表处理语言等课程。1968年,“数据结构”被列入美国一些大学计算机科学系的教学计划。 发展阶段: 数据结构的概念不断扩充,包括了网络、集合代数论、关系等“离散数学结构”的内容。 70年代后期,我国高校陆续开设该课程。

四、《数据结构课程》所处的地位:

1.2 基本概念和术语 一、几个概念: 1、数据(Data): 是对信息的一种符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。 2、数据元素(Data Element): 是数据的基本单位,在计算机程序中通常作为一个整体进行考虑和处理。一个数据元素可由若干个数据项组成。数据项是数据的不可分割的最小单位。

例如:学生卡片记录表 3、数据对象(Data Object): 是性质相同的数据元素的集合。是数据的一个子集。例如,整数数据对象的集合可表示为N={0,±1,±2…….},字母字符数据对象的集合可表示为C={‘A’,’B’,…’Z’}。

4、数据结构 是相互之间存在一种或多种特定关系的数据元素的集合。 形式化定义:数据结构是一个二元组 Data_Structure = (D,R) 其中,D是数据元素的有限集合,R是D上关系的集合

更具体的说明数据结构定义: 按某种逻辑关系组织起来的一批数据(或称带结构的数据元素的集合)应用计算机语言并按一定的存储表示 方式把它们存储在计算机的存储器中,并在其上定义了一个运算的集合。具体来说,数据结构包含三个方面的内容,即数据的逻辑结构,数据的存贮结构和对数据所施加的运算(操作)。

这三个方面的关系为: (1)数据的逻辑结构独立于计算机,是数据本身所固有的。 (2)存贮结构是逻辑结构在计算机存贮器中的映像,必须依赖于计算机。 (3)运算是指所施加的一组操作总称。运算的定义直接依赖于逻辑结构,但运算的实现必须依赖于存贮结构。

(1)、集合: 结构中的数据元素除了同属于一种类型外,别无其它关系。 5、逻辑结构的分类: (1)、集合: 结构中的数据元素除了同属于一种类型外,别无其它关系。 (2)、线性结构:结构中的数据元素之间存在一对一的关系。 (3)、树型结构:结构中的数据元素之间存在一对多的关系。 a1 a2 a3 a4

(4)、图状结构或网状结构 结构中的数据元素之间存在多对多的关系。

6、存储方法的分类: (1)顺序存储方法(顺序存储结构) (2)链接存储方法(链式存储结构) (3)索引存储方法 (4)散列存储方法 同一种逻辑结构可采用不同的存储方法(以上四种之一或组合),这主要考虑的是运算方便及算法的时空要求。

顺序存储结构: 用数据元素在存储器中的相对位置来表示数据元素之间的逻辑关系。 链式存储结构: 在每一个数据元素中增加一个存放地址的指针,用此指针来表示数据元素之间的逻辑关系。

数据的运算:检索、排序、插入、删除、修改等 线性表 数据结构的三个方面: 栈 队列 线性结构 串及数组 数据的逻辑结构 树形结构 非线性结构 图形结构 顺序存储 链式存储 数据的存储结构 索引存储 散列存储 数据的运算:检索、排序、插入、删除、修改等

例2.1:用图形表示下列数据结构,并指出它 们是属于线性结构还是非线性结构。 例2.1:用图形表示下列数据结构,并指出它 们是属于线性结构还是非线性结构。 (1) S=(D, R) D={ a, b, c, d, e, f } R={(a,e), (b,c), (c,a), (e,f), (f,d)} 解: 上述表达式可用图形表示为: b c a e f d 此结构为线性的。

(2) S=(D, R) D={di | 1≤i≤5} R={(di , dj ), i<j} 解:上述表达式可用图形表示为: d1 d5 d2 d4 d3 该结构是非线性的。

1.3 抽象数据类型的表示与实现 思考: 1、数据类型与抽象数据类型的区别? 2、 抽象数据类型如何定义? 3、抽象数据类型如何表示和实现? 提示:教材中例1-6和例1-7分别给出了抽象数据类型“三元组”的定义、表示和实现,试请阅读。

一、数据类型与抽象数据类型的概念 1、数据类型:数据类型是一个值的集合和定义在这个值集上的一组操作的总称 2、抽象数据类型:是指一个数学模型以及定义在该模型上的一组操作。抽象数据类型的定义取决于它的一组逻辑特性,而与其在计算机内部如何表示和实现无关。

二、抽象数据类型如何定义 抽象数据类型可以用以下的三元组来表示: ADT = (D,R,P) 数据对象 D上的关系集 D上的操作集 数据对象:<数据对象的定义> 数据关系:<数据关系的定义> 基本操作 :<基本操作的定义> } ADT抽象数据类型名 ADT常用定义格式

三、抽象数据类型如何表示和实现 抽象数据类型可以通过固有的数据类型(如整型、实型、字符型等)来表示和实现。 注1 :它有些类似C语言中的结构(struct)类型,但增加了相关的服务。 注2 :教材中用的是类C语言(介于伪码和C语言之间)作为描述工具。其描述语法见P10-11。 但上机时要用具体语言实现,我们用C语言

1.4 算法和算法分析 一、算法的概念和描述: 1、什么是算法? 是对特定问题求解步骤的一种描述,算法是指令的有限序列,其中每一条指令表示一个或多个操作。

2、 算法具有以下五个特性: (1)有穷性 一个算法必须总是在执行有穷步之后结束,且每一步都在有穷时间内完成。 (2)确定性 算法中每一条指令必须有确切的含义。不存在二义性。且算法只有一个入口和一个出口。 (3)可行性 一个算法是可行的。即算法描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。 (4)输入 一个算法有零个或多个输入,这些输入取自于某个特定的对象集合。 (5)输出 一个算法有一个或多个输出,这些输出是同输入有着某些特定关系的量。

3、算法设计的要求: 评价一个好的算法有以下几个标准: (1) 正确性(Correctness ) 算法应满足具体问题的需求。 (2)可读性(Readability) 算法应该好读。以有利于阅读者对程序的理解,便于调试和修改。 (3)健状性(Robustness) 算法应具有容错处理。当输入非法数据时,算法应对其作出反应,而不是产生莫名其妙的输出结果。

(4)效率与存储量需求 效率指的是算法执行的时间;存储量需求指算法执行过程中所需要的最大存储空间。一般,这两者与问题的规模有关。 注意:算法和程序的关系 算法的含义与程序十分相似,但二者是有区别的。一个程序不一定满足有穷性(死循环),另外,程序中的指令必须是机器可执行的,而算法中的指令则无此限制。一个算法若用计算机语言来书写,则它就可以是一个程序。

二、算法的描述和实现 描述---可采用自然语言、数学语言或约定的符号语言。 实现---必须借助程序设计语言提供的数据类型及其运算。 本课的描述---采用类C语言。

三、算法分析 同一问题可用不同算法解决,而一个算法的质量优劣将影响到算法乃至程序的效率。算法分析的目的在于选择合适算法和改进算法。一个算法的评价主要从时间复杂度和空间复杂度来考虑。

1、时间频度 一个算法执行所耗费的时间,从理论上是不能算出来的,必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试,只需知道哪个算法花费的时间多,哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例,哪个算法中语句执行次数多,它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为f(n)。

例1 求下列算法段的语句频度   for(i=1; i<=n; i++) for(j =1; j <=i ; j++) x=x+1; 分析:该算法为一个二重循环,执行次数为内、外循环次数相乘,但内循环次数不固定,与外循环有关,因些,时间频度f(n)=1+2+3+…+n=

2、时间复杂度 在刚才提到的时间频度中,n称为问题的规模,当n不断变化时,时间频度f(n)也会不断变化。但有时我们想知道它变化时呈现什么规律。为此,我们引入时间复杂度概念。 一般情况下,算法中基本操作重复执行的次数是问题规模n的某个函数,用T(n)表示,若有某个辅助函数f(n),使得当n趋近于无穷大时,T(n)/f(n)的极限值为不等于零的常数,则称f(n)是T(n)的同数量级函数(。记作T(n)=O(f(n)),称O(f(n)) 为算法的渐近时间复杂度,简称时间复杂度。

例如,若T(n)=n(n+1)/2,则有 1/4≤T(n)/n2≤1 故它的时间复杂度为O(n2), 即T(n)与n2 数量级相同。

例1.3 分析以下程序段的时间复杂度 i=1; while (i<=n) /* 1 * / 语句1的频度是:1 例1.3 分析以下程序段的时间复杂度 i=1; while (i<=n) i=i*2 语句1的频度是:1 设语句2的频度是f(n),则有: 即 ,取最大值 则该程序段的时间复杂度为: /* 1 * / /* 2 * /

常见函数的时间复杂度按数量递增排列及增长率。 常数阶O(1) 对数阶O(log2n) 线性阶O(n) 线性对数阶O(nlog2n) 平方阶O(n2) 立方阶O(n3) …… k次方阶O(nk) 指数阶O(2n)

3、空间复杂度 与时间复杂度类似,空间复杂度是指算法在计算机内执行时所需存储空间的度量。记作: S(n)=O(f(n)) 我们一般所讨论的是除正常占用内存开销外的辅助存储单元规模。讨论方法与时间复杂度类似,不再赘述。

本章小结 数据、数据结构等基本概念 数据结构的三个方面的内容 抽象数据类型的概念 线性和非线性结构的逻辑特征 数据存储的四种基本方法 算法、算法的时间复杂度及其分析的简易方法

作业: