严蔚敏最新版《数据结构》电子教案.ppt
《严蔚敏最新版《数据结构》电子教案.ppt》由会员分享,可在线阅读,更多相关《严蔚敏最新版《数据结构》电子教案.ppt(55页珍藏版)》请在三一文库上搜索。
1、北京林业大学信息学院,03:30,李冬梅,数据结构,北京林业大学信息学院,03:30,编程基础 计算机及相关专业考研考博课程 计算机等级考试课程 程序员考试课程,为什么要学习数据结构,北京林业大学信息学院,03:30,课程学习指导,1.提前预习、认真听课、按时完成书面及上机作业 2.注意先修课程的知识准备 离散数学、C语言 3.注意循序渐进: 基本概念、基本思想、基本步骤、算法设计 4.注意培养算法设计的能力 理解所讲算法、对此多做思考:若问题要求不同,应如何选择数据结构,设计有效的算法,课程特点:内容抽象、概念性强、内容灵活、不易掌握,北京林业大学信息学院,03:30,平时成绩 : 30%
2、作业、小测验、实验 课堂纪律 无故迟到: 无故旷课: 上机:玩游戏、上网聊天 期末成绩 : 70%(闭卷笔试),考核方式,北京林业大学信息学院,03:30,教材和参考书 教材: 数据结构978-7-115-23490 严蔚敏,李冬梅,人民邮电出版社出版 参考书: 数据结构C语言版,严蔚敏,清华大学出版社 数据结构用面向对象方法与C+描述,殷人昆等,清华大学出版社,03:30,第1章 绪论,1. 了解数据结构研究的主要内容 2.掌握数据结构中涉及的基本概念 3. 掌握算法、算法的时间复杂度及其分析的简易方法,教学目标,北京林业大学信息学院,03:30,1.1 数据结构的研究内容 1.2 基本概念
3、和术语 1.3 抽象数据类型的表示与实现 1.4 算法与算法分析,教学内容,北京林业大学信息学院,03:30,N.沃思(Niklaus Wirth)教授提出: 程序=算法+数据结构 电子计算机的主要用途: 早期: 主要用于数值计算。 后来: 处理逐渐扩大到非数值计算领域,能处理多种复杂的具有一定结构关系的数据,1.1 数据结构的研究内容,北京林业大学信息学院,03:30,书目自动检索系统,书目文件,北京林业大学信息学院,03:30,人机对奕问题,北京林业大学信息学院,03:30,/ (root),bin,lib,user,etc,math,ds,sw,yin,tao,xie,Stack.cpp
4、,Queue.cpp,Tree.cpp,文件系统的系统结构图,北京林业大学信息学院,03:30,多叉路口交通灯管理问题,顶点:一条通路 连线:不能同时通行 染色:有连线的两个顶点不能具有相同颜色,北京林业大学信息学院,03:30,求解非数值计算的问题: 设计出合适的数据结构及相应的算法 即:首先要考虑对相关的各种信息如何表示、组织和存储? 数据结构的研究内容为: 研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作。,北京林业大学信息学院,03:30,数据结构课程的形成和发展: 形成阶段: 60年代初期,“数据结构”有关的内容散见于操作系统、编译原理和表处理语言等课程。196
5、8年,“数据结构”被列入美国一些大学计算机科学系的教学计划。 发展阶段: 数据结构的概念不断扩充,包括了网络、集合代数论、关系等“离散数学结构”的内容。 70年代后期,我国高校陆续开设该课程。,北京林业大学信息学院,03:30,数据结构所处的地位:,介于数学、计算机硬件和计算机软件三者之间的一门核心课程,北京林业大学信息学院,03:30,数据结构在计算机学科中的地位,北京林业大学信息学院,03:30,课程目的,能够分析研究计算机加工的对象的特性,获得其逻辑结构,根据需求,选择合适存贮结构及其相应的算法; 学习一些常用的算法; 复杂程序设计的训练过程,要求编写的程序结构清楚和正确易读; 初步掌握
6、算法的时间分析和空间分析技术,北京林业大学信息学院,03:30,1、数据(data)所有能输入到计算机中去的描述客观事物的符号 数值性数据 非数值性数据(多媒体信息处理) 2、数据元素(data element)数据的基本单位,也称结点(node)或记录(record) 3、数据项(data item)有独立含义的数据最小单位,也称域(field),三者之间的关系:数据 数据元素 数据项,例:学生表 个人记录 学号、姓名,1.2 基本概念和术语,北京林业大学信息学院,03:30,整数数据对象 N = 0, 1, 2, 学生数据对象 学生记录的集合,4、数据对象(Data Object):相同特
7、性数据元素的集合,是数据的一个子集,北京林业大学信息学院,03:30,5、数据结构(Data Structure)是相互之间存在一种或多种特定关系的数据元素的集合。,数据结构是带“结构”的数据元素的集合,“结构”就是指数据元素之间存在的关系。,北京林业大学信息学院,03:30,数据结构的两个层次: 逻辑结构- 数据元素间抽象化的相互关系,与数据的存储无关,独立于计算机,它是从具体问题抽象出来的数学模型。 存储结构(物理结构)- 数据元素及其关系在计算机存储器中的存储方式。,北京林业大学信息学院,03:30,划分方法一 (1)线性结构- 有且仅有一个开始和一个终端结点,并且所有结点都最多只有一个
8、直接前趋和一个后继。 例如:线性表、栈、队列、串 (2)非线性结构- 一个结点可能有多个直接前趋和直接后继。 例如:树、图,逻辑结构,北京林业大学信息学院,03:30,线性结构一个对一个,如线性表、栈、队列,树形结构一个对多个,如树,集合数据元素间除“同属于一个集合”外,无其它关系,图形结构多个对多个,如图,逻辑结构,划分方法二,北京林业大学信息学院,03:30,存储结构分为: 顺序存储结构借助元素在存储器中的相对位置来表示 数据元素间的逻辑关系 链式存储结构借助指示元素存储地址的指针表示数据 元素间的逻辑关系,存储结构,北京林业大学信息学院,03:30,北京林业大学信息学院,03:30,15
9、36,元素2,1400,元素1,1346,元素3,元素4,1345,h,链式存储,h,北京林业大学信息学院,03:30,逻辑结构和存储结构都相同, 但运算不同, 则数据结构不同. 例如, 栈与队列 对于一种数据结构, 常见的运算 插入 删除 修改 查找 排序,数据的运算,北京林业大学信息学院,03:30,数据的逻辑结构,数据的存储结构,数据的运算:插入、删除、修改、查找、排序,线性结构,非线性结构,顺序存储,链式存储,线性表,栈、队列,串、数组,树形结构,图形结构,逻辑结构 唯一 存储结构 不唯一 运算的实现 依赖于 存储结构,北京林业大学信息学院,03:30,定义:在一种程序设计语言中,变量
10、所具有的数据种类,数据类型,FORTRAN语言:整型、实型、和复数型 C语言: 基本数据类型: char int float double void 构造数据类型:数组、结构体、共用体、文件,数据类型是一组性质相同的值的集合, 以及定义于这个集合上的一组运算的总称,北京林业大学信息学院,03:30,抽象数据类型 (ADTs: Abstract Data Types),更高层次的数据抽象 由用户定义,用以表示应用问题的数据模型 由基本的数据类型组成, 并包括一组相关的操作,抽象数据类型,北京林业大学信息学院,03:30,抽象数据类型可以用以下的三元组来表示: ADT = (D,S,P) 数据对象
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 严蔚敏 最新版 电子 教案
链接地址:https://www.31doc.com/p-2160252.html