大学数据结构课件.ppt

1、北京市林业大学信息学院，02:04，Office:西侧楼218(数字媒体研究室)电子邮件3360，杨孟，数据结构，北京市林业大学信息学院，02:04，编程基础计算机和相关专业研究生考试课程计算机等级考试课程程序员考试课程北京市林业大学信息学院提前预习，努力上课，按时完成书面及机械工作2。课程知识准备离散数学，c语言3。渐进主义：基本概念、基本思想、基本阶段、算法设计4。培养算法设计需要注意的数据结构选择方法，有效的算法设计，课程特征：内容抽象，概念，内容灵活性，不易理解，北京市林业大学信息学院，02:04，平时成绩3360%作业，测验，实验教室规律无缘无故迟到：无故旷课：没有理由了解数据结构研

2、究的主要内容2。把握数据结构相关基本概念3。了解算法、算法时间复杂度和分析方法、教育目标、北京市林业大学信息学院、02336004、1.1数据结构研究内容1.2基本概念和术语1.3抽象数据类型表示和实现1.4算法和算法分析、教育内容、北京市林业大学信息学院、02336004、Wirth 瑞士苏黎世联邦产业大学)节目=算法数据结构电子计算机的主要用途：早期：主要用于数值计算后：处理逐渐扩展到非数值计算领域，1.1数据结构研究内容，北京市林业大学信息学院，02336004，书目自动检索系统，书目文件，北京市林业大学信息学院，02336004 连接的两个顶点不能具有相同的颜色。北京市林业大学信息学院

3、，02336004，非数字计算问题解决：适当的数据结构及其算法设计：首先，必须考虑如何表示、组织和存储相关相关信息。数据结构研究内容是在研究非数字计算的计算机编程问题上研究计算机的操作数和它们之间的关系和操作。北京市林业大学信息学院，02336004，数据结构课程形成与发展：形成阶段：60年代初，“数据结构”相关内容包括操作系统、编译原理、表格处理语言等课程1968年，“数据结构”被纳入美国部分大学计算机科学系的教育计划。发展阶段：数据结构概念不断扩展，包括网络、集合代数论、关系等“离散数学结构”的内容。20世纪70年代后期，我国高校相继开设了牙齿课程。，北京市林业大学信息学院，02:04，数

4、据结构位置：数学，电脑硬件，电脑软件三者之间的核心课程，核心课程之一，北京林业大学信息学院，02336004，课程目的，计算机加工对象特性分析，逻辑获取学一些常用算法复杂的计算机编程训练课程，编写的节目结构必须清晰易读。初步了解算法时间分析和空间分析技术、北京市林业大学信息学院、02:04，1、数据(数据)所有符号数字数据非数字数据(多媒体信息处理)2、数据元素(数据元素)数据的基本单位节点(node)或唱片(record) 数据对象：相同的特性数据元素集，数据的子集，北京市林业大学信息学院，02:04，5，数据结构(数据结构)是，数据结构是具有“结构”的数据元素集，“结构”是数据元素之间存在

5、的关系。北京市林业大学信息学院，02:04，数据结构两层：逻辑结构-数据元素之间的抽象相互关系，与数据存储无关，与计算机无关，在特定问题上的抽象数学模型。存储结构(物理结构)-数据元素及其关系在电脑存储中的存储方式。北京市林业大学信息学院，02:04，分割方法1 (1)线性结构示例，线性表、堆栈、队列、字符串(2)非线性结构-一个节点可以有多个直接向前和直接向后。例如：树、图、逻辑结构、北京市林业大学信息学院、02336004、一对线性结构、线性表、堆栈、队列、一对树结构(例如，树、集合数据元素之间的“同一集合”除外)，存储结构分为：顺序存储结构使用存储的元素相对位置表示数据元素之间的逻辑关系

6、。链存储结构使用指示元素存储地址的指针表示数据元素之间的逻辑关系。存储结构，北京市林业大学信息学院，02:04，北京市林业大学信息学院，02336004，1536，元素2，1346，元素3，元素4，北京市林业大学信息学院，02:04，逻辑结构和存储结构相同，但运算不同。例如，堆栈和队列包含数据结构、常规运算插入删除祖怀排序、数据运算、北京市林业大学信息学院、02336004、数据数据运算：插入、删除、修改、查找、排序、线性结构、非线性结构、顺序存储数据类型包括具有相同特性的值集和定义抽象数据类型(ADTs: Abstract Data Types)，高级数据抽象是由表示应用程序节目问题的数据模

7、型默认数据类型组成的自定义，包含相关集的操作取决于逻辑特性。 与内部结构无关、抽象数据类型、北京市林业大学信息学院、02336004抽象数据类型是ADT=(D，s，p)数据对象D的关系集D的工作集、ADT抽象数据类型名称数据对象：数据关系：基本任务：ADT抽象数据类型名称、ADT公用与北京市林业大学信息学院、0233666、C语言的结构(struct)类型类似，但是相关操作教材使用C类语言(医生代码与C语言之间)作为说明工具，在飞机上必须用C或C等特定语言实现。 北京市林业大学信息学院，02336004，(1)预定义常量和类型/函数结果状态代码# define ok1 # define err

8、or 0 # define infeasible-1 # define overflow，(3)算法说明采用以下函数格式：函数类型函数名称(函数表)语句序列；北京市林业大学信息学院，02:04，(4)动态分配和释放内存使用new和delete的动态分配和空闲内存空间分配空间指针变量=new数据类型空闲空间删除指针变量；(5)赋值语句= (6)语句 if 、 switch (7)循环语句 for 、 while 、 do-while 。北京市林业大学信息学院，02:04，(9)输入和输出语句格式：输入语句min (11scanf()输出语句cout (printf() (10)扩展函数示例：最大max查找Ij n；j)cij=AIJ bij；语句频率：重复计数：n * nT(n)=O (n 2)，即矩阵加运算量和问题的规模n的平方等于规模，北京市林业大学信息学院，02:04，变量数，x=0；y=0；for(int k=0)；k n；k)x；for(int I=0)；I n；I)for(int j=0；j n；j)y；t1 (n)=