数据结构 DATA STRUCTURE.

Slides:



Advertisements
Similar presentations
数据结构的引入. 通讯录管理 社团机构管理 校园导航管理 通讯录管理 社团机构管理 校园导航管理.
Advertisements

第一章 绪论 学习提要 1.1 什么是数据结构 1.2 基本概念 1.3 抽象数据类型 1.4 算法及其分析.
——Windows98与Office2000(第二版) 林卓然编著 中山大学出版社
余莉 1236 首页 > 课程总览 > 信息技术学院 > 数据结构
数据结构 张秀虹
数据结构(C语言版) Data Structure
《高等数学》(理学) 常数项级数的概念 袁安锋
§1 线性空间的定义与性质 ★线性空间的定义 ★线性空间的性质 ★线性空间的子空间 线性空间是线性代数的高等部分,是代数学
数 据 结 构 主讲人:文 军.
小学生游戏.
第1章 绪论 本章主要内容 1.1 什么是数据结构 1.2 基本概念和术语 1.3 数据类型和抽象数据类型 1.4 算法描述与算法评价.
数据结构 主讲:庄越.
C++中的声音处理 在传统Turbo C环境中,如果想用C语言控制电脑发声,可以用Sound函数。在VC6.6环境中如果想控制电脑发声则采用Beep函数。原型为: Beep(频率,持续时间) , 单位毫秒 暂停程序执行使用Sleep函数 Sleep(持续时间), 单位毫秒 引用这两个函数时,必须包含头文件
全国计算机等级考试 二级基础知识 第二章 程序设计基础.
数据结构 袁平波
Hadoop I/O By ShiChaojie.
第一章 绪论 早期:数值计算 —— 运算对象是简单的整型、实型或布尔类型数据 中后期:非数值计算 ——
SOA – Experiment 3: Web Services Composition Challenge
管理信息结构SMI.
走进编程 程序的顺序结构(二).
第2讲 绪论(二).
数 据 结 构 计 算 机 学 院 肖明军
第一单元 初识C程序与C程序开发平台搭建 ---观其大略
第五讲 四则运算计算器(一) 精品教程《C#程序设计与应用(第2版)清华大学出版社 谭恒松 主编
§2 求导法则 2.1 求导数的四则运算法则 下面分三部分加以证明, 并同时给出相应的推论和例题 .
动态规划(Dynamic Programming)
CPU结构和功能.
宁波市高校慕课联盟课程 与 进行交互 Linux 系统管理.
第一章 函数与极限.
C++语言程序设计 C++语言程序设计 第七章 类与对象 第十一组 C++语言程序设计.
数列.
C语言程序设计 主讲教师:陆幼利.
简单介绍 用C++实现简单的模板数据结构 ArrayList(数组, 类似std::vector)
学习目标 1、什么是字符集 2、字符集四个级别 3、如何选择字符集.
顺序表的删除.
( data structures, Algorithms and Applications in C++)
线 性 代 数 厦门大学线性代数教学组 2019年4月24日6时8分 / 45.
VisComposer 2019/4/17.
cn/~dongeliu/dsa.html 刘 东 信息学院6系 中国科学技术大学
用计算器开方.
<编程达人入门课程> 本节内容 内存的使用 视频提供:昆山爱达人信息技术有限公司 官网地址: 联系QQ: QQ交流群: ,
C语言程序设计 第一章 数据类型, 运算符与表达式 第二章 顺序程序设计 第三章 选择结构程序设计 第四章 循环控制 第五章 数组.
第1章 绪论(二) 教学目标 理解算法的特性及评价标准 掌握算法时间复杂度和空间复杂度的分析方法 1/
成绩是怎么算出来的? 16级第一学期半期考试成绩 班级 姓名 语文 数学 英语 政治 历史 地理 物理 化学 生物 总分 1 张三1 115
第4章 Excel电子表格制作软件 4.4 函数(一).
用穷举法设计程序 南京师范大学 教育技术系 倪佳慧
数据集的抽取式摘要 程龚, 徐丹云.
多层循环 Private Sub Command1_Click() Dim i As Integer, j As Integer
魏新宇 MATLAB/Simulink 与控制系统仿真 魏新宇
第一章 绪论 1.1 引言 1.2 逻辑结构和存储结构 1.3 算法.
第七、八次实验要求.
2.2矩阵的代数运算.
第15讲 特征值与特征向量的性质 主要内容:特征值与特征向量的性质.
线 性 代 数 厦门大学线性代数教学组 2019年5月12日4时19分 / 45.
GIS基本功能 数据存储 与管理 数据采集 数据处理 与编辑 空间查询 空间查询 GIS能做什么? 与分析 叠加分析 缓冲区分析 网络分析
本节内容 C语言的汇编表示 视频提供:昆山爱达人信息技术有限公司 官网地址: 联系QQ: QQ交流群 : 联系电话:
第二节 函数的极限 一、函数极限的定义 二、函数极限的性质 三、小结 思考题.
第二节 C语言的特点.
实验目的:掌握数据的顺序存储结构及它们在计算机中的操作。 实验内容:
基于列存储的RDF数据管理 朱敏
C++语言程序设计 C++语言程序设计 第一章 C++语言概述 第十一组 C++语言程序设计.
第四节 向量的乘积 一、两向量的数量积 二、两向量的向量积.
第十七讲 密码执行(1).
插入排序的正确性证明 以及各种改进方法.
《偏微分方程》第一章 绪论 第一章 绪论 1.1.
学习数据结构的意义 (C语言版) 《数据结构》在线开放课程 主讲人:李刚
高等学校计算机专业教材 数据结构 袁平波
任课教师:戴开宇 TA:时均帅、谭肖、王安华 程序设计B班 :20-16:50(90分钟)
编译原理实践 6.程序设计语言PL/0.
§2 自由代数 定义19.7:设X是集合,G是一个T-代数,为X到G的函数,若对每个T-代数A和X到A的函数,都存在唯一的G到A的同态映射,使得=,则称G(更严格的说是(G,))是生成集X上的自由T-代数。X中的元素称为生成元。 A变, 变 变, 也变 对给定的 和A,是唯一的.
Presentation transcript:

数据结构 DATA STRUCTURE

课程基本情况与要求 课程属性:必修; 学时:总学时64,讲课46,上机18; 上机:双周二晚7:00~9:00,实验楼, 数学101,信计102; 三人一组,每组完成一份实验报告; 实验报告:上机时交电子版和打印版; 成绩组成:平时上机30分,上机考试20分, 期末笔试50分; 课堂纪律:人所共知 研究作业:分组查文献,写综述。

第一章 绪论 1 数据结构讨论的范畴 2 数据结构的基本概念 3 数据类型和抽象数据类型 4 C语言的数据类型 5 第一章 绪论 1 数据结构讨论的范畴 2 数据结构的基本概念 3 数据类型和抽象数据类型 4 C语言的数据类型 5 算法设计目标和算法效率度量

数据结构也称信息结构,是一门随着计算机科学的发展而逐渐形成的学科,目前也成为计算机类各专业的基础课、核心课之一。 40年代,计算机所能处理的数据非常简单,只有0、1组成的二进制数; 50年代到60年代中期,各种高级语言纷纷出现,所能描述的数据类型也逐渐繁多; 如FORTRAN语言中允许复数类型的量,用两个有序的实数<x,y>表示一个复数,这已有点“结构”的雏形了;BASIC等语言中出现了数组;当计算机应用领域有数值计算扩充到非数值计算后,各种新的结构因运而生,其中最重要的是COBOL等语言出现的记录类型,

60年代中期以后,在数据结构发展史上发生了几个重要的事件。首先,美国计算机界出现了信息结构这一名称;1968年,美国计算机协会颁发了建设性的计算机教学计划,其中规定《数据结构》作为独立的一门课,这在世界上还是第一次;同年,世界著名的计算机科学家D.E.Knuth教授的巨著《计算机程序设计的技巧》,第一卷《基本算法》出版,系统地论述了数据的逻辑结构和存储结构,并且给出了各种典型的算法。它把许多不同类型的数据组合起来构成一个新的类型。

从60年代到70年代初,出现了大型的程序和大规模的文件系统,结构程序设计成为程序设计方法学的主要内容。 人们对数据结构越来越重视,认为程序设计的实质就是要对处理的问题选择一种好的数据结构,同时在此结构上施加一种好的算法;著名计算机科学家N.Wirth写的 《算法+数据结构=程序》 一书正是体现了这种观点。

1.1 数据结构讨论的范畴 Niklaus Wirth: 程序设计:为计算机处理问题编制一组指令集 1.1 数据结构讨论的范畴 概括地说: 数据结构是一门讨论“描述现实世界实体的数学模型(非数值计算)及其上的操作在计算机中如何表示和实现”的学科。 Niklaus Wirth: Algorithm + Data Structures = Programs 程序设计:为计算机处理问题编制一组指令集 算 法:处理问题的策略 数据结构:问题的数学模型

数据结构研究的主要内容: 研究数据结构目的: 1、数据的逻辑结构 2、数据的存储结构 3、对各种数据结构进行的运算 研究数据结构目的: 1、提高数据处理的速度 2、尽量节省在数据处理过程中所 占用的计算机存储空间

第一章 绪论 1 数据结构讨论的范畴 2 数据结构的基本概念 3 数据类型和抽象数据类型 4 C语言的数据类型 5 第一章 绪论 1 数据结构讨论的范畴 2 数据结构的基本概念 3 数据类型和抽象数据类型 4 C语言的数据类型 5 算法设计目标和算法效率度量

1.2 数据结构的基本概念 数据:数据是信息的载体,是描述客观事物的数、字符、以及所有能输入到计算机中,被计算机程序识别和处理的符号的集合。 1.2 数据结构的基本概念 数据:数据是信息的载体,是描述客观事物的数、字符、以及所有能输入到计算机中,被计算机程序识别和处理的符号的集合。 数值性数据 非数值性数据 数据对象:数据的子集。具有相同性质的数据成员(数据元素)的集合。 整数数据对象 N = { 0, 1, 2, … } 学生数据对象:初等项(不可分割)、组合项(可再划分)

数据元素:是数据的最小单位,有时一个数据元素由数据项组成(具有独立含义的最小标识单位) 数据类型:具有相同性质的计算机数据集合及在这个集合上的一组操作。 数据结构:由某一数据对象及该对象中所有数据成员之间的关系组成。记为: Data_Structure = {D, R} 其中,D是某一数据对象,R是该对象中所有数据成员之间的关系的有限集合。

数据的逻辑结构: 对数据元素之间的逻辑关系的描述 只抽象地反映数据元素之间的逻辑关系, 与计算机中的存储无关 分为线性结构和非线性结构 两个要素: 数据元素的集合,通常记为D; 数据关系的集合,通常记为R

数据的存储结构或物理结构 数据的逻辑结构在计算机存储空间中的存放形式 常用的存储结构: 顺序存储 链式存储 索引存储 散列存储 一种数据结构可根据需要采用不同的存储结构。采用不同的存储结构,其数据处理的效率是不同

“学生”表格

“课程”表格

线性结构中各数据成员之间的线性关系: 有直接前驱和直接后继(除最前、最后一个元素) 例:电话号码查询问题 方法1:顺序存储,顺序查找

方法2:有序顺序存储,二分查找 姓名 地址 李1 李2 …… 张1 张2 王1 王2

方法3:部分有序,建立索引表 姓名 地址 李1 李2 …… 张1 张2 王1 王2 姓 地址 李 张 ……

非线性结构中各数据成员之间的没有线性关系: 前驱和后继可能多于一个 非线性结构中各数据成员之间的没有线性关系: 前驱和后继可能多于一个 选课单包含如下信息 学 号 课程编号 成 绩 时 间 学生选课系统中实体构成的网状关系

文件系统的系统结构图

树形结构 树 二叉树 二叉搜索树

堆结构 “最大”堆 “最小”堆

图结构 网络结构

1、任一选手所选中的项目中应该两两有边相连; 2、任一两个有边相连的顶点颜色(时间)不能相同。 例:田径赛的时间安排问题 跳高 跳远 姓名 项目1 项目2 项目3 丁1 跳高 跳远 100M 马2 标枪 铅球 张3 200M 李4 王5 100M 200M 铅球 标枪 1、任一选手所选中的项目中应该两两有边相连; 2、任一两个有边相连的顶点颜色(时间)不能相同。

第一章 绪论 1 数据结构讨论的范畴 2 数据结构的基本概念 3 数据类型和抽象数据类型 4 C语言的数据类型 5 第一章 绪论 1 数据结构讨论的范畴 2 数据结构的基本概念 3 数据类型和抽象数据类型 4 C语言的数据类型 5 算法设计目标和算法效率度量

1.3 数据类型和抽象数据类型 数据类型 定义:一个数据的集合, 以及定义于这个数据集合上的一组操作的总称。 C语言中的数据类型 1.3 数据类型和抽象数据类型 数据类型 定义:一个数据的集合, 以及定义于这个数据集合上的一组操作的总称。 C语言中的数据类型 基本数据类型、指针类型、数组类型、结构体类型、公用体类型、枚举类型

抽象数据和抽象数据类型 (ADTs: Abstract Data Types) 由用户定义,用以表示应用问题的数据模型 由基本的数据类型组成, 并包括一组相关的服务(或称操作) 信息隐蔽和数据封装,使用与实现相分离(物理实现封装)

ADT: 抽象数据类型名 数据对象:数据对象的定义 数据关系:数据逻辑关系的定义 基本操作:基本操作的定义 抽象数据类型的定义: ADT: 抽象数据类型名 数据对象:数据对象的定义 数据关系:数据逻辑关系的定义 基本操作:基本操作的定义 基本操作的定义: 操作名(参数表) 操作结果:操作结果描述

抽象数据类型

第一章 绪论 1 数据结构讨论的范畴 2 数据结构的基本概念 3 数据类型和抽象数据类型 4 C语言的数据类型 5 第一章 绪论 1 数据结构讨论的范畴 2 数据结构的基本概念 3 数据类型和抽象数据类型 4 C语言的数据类型 5 算法设计目标和算法效率度量

1.4 C语言的数据类型 1、基本数据类型 int short; long; unsigned float float; double; long double 2、指针类型 3、数组类型 4、字符串 5、结构体类型 6、共用体类型 7、枚举类型 8、自定义类型

第一章 绪论 1 数据结构讨论的范畴 2 数据结构的基本概念 3 数据类型和抽象数据类型 4 C语言的数据类型 5 第一章 绪论 1 数据结构讨论的范畴 2 数据结构的基本概念 3 数据类型和抽象数据类型 4 C语言的数据类型 5 算法设计目标和算法效率度量

1.5 算法设计目标和算法效率度量 定义:一个有穷的指令集,这些指令为解决某一特定任务规定了一个运算序列 特性: 输 入 有0个或多个输入 输 入 有0个或多个输入 输 出 有一个或多个输出(处理结果) 确定性 每步定义都是确切、无歧义的 有穷性 算法应在执行有穷步后结束 有效性 每一条运算应足够基本 算法的描述:c++,c,PASCAL等语言

算法的特点: 1、有穷性:要求序列中的指令是有限的;每条指令的执行包含有限的工作量;整个指令序列的执行在有限的时间内结束。 2、确定性:算法中的每一个步骤都必须是确定的,而不应当含糊、模棱两可。 3、有零个或多个输入 4、有一个或多个输出 5、有效性:算法中的每一个步骤都应当能被有效的执行,并得到确定的结果。例如:被零除的计算动作是不能被有效执行的。

算法设计 自顶向下,逐步求精 设计算法的基本方法:把一个具体问题转变成一个算法 事例学习:选择排序问题 明确问题:非递减排序 解决方案:逐个选择最小数据 算法框架: for ( int i=0; i<=n-2; i++ ) { //n-1趟 从a[i]检查到a[n-1]; 若最小的整数在a[k], 交换a[i]与a[k]; } 细化程序:程序 SelectSort

性能分析与度量 算法的性能标准 算法的后期测试 算法的事前估计

分析评价算法时应考虑的因素: 1、正确性 在给定有效的输入数据后,算法经过有穷时间 的计算能给出正确的答案。 2、复杂度 时间复杂度 1、正确性 在给定有效的输入数据后,算法经过有穷时间 的计算能给出正确的答案。 2、复杂度 时间复杂度 3、简单性 4、最优性 算法A是最优的是指:在给定问题的所有算法中,A执行的进步运算次数最少 5、可读性 要求算法易于理解,便于分析 6、可修改可扩展性 如果问题P 的一个算法是A,为了解答一个与P类似的问题,希望对A稍做改动就可正确运行,如算法A满足这一点,则说A的可修改性好。

与算法效率有关的因素 定期集体上自习,讨论学习问题 4.问题的规模 1.程序设计语言 3.机器执行指令的速度 2.编译的代码质量

如何评价算法的好坏 首先算法必须是正确的。此外还需考虑: 1、算法易于理解,易于编程(在计算机上实现), 易于调试。 2、要求算法高效,节省时间与空间。 一个算法运行所需时间的长短、空间的大小具有非常重要的意义。 时间和空间相互之间有一种制约关系,何者为重需视具体情况而定。

这两个要求有时互相矛盾。因此,对反复运行特别是实时的算法,首先考虑的是高效性,对偶尔运行的算法,则需突出算法易理解和易编程。 算法高效与算法易理解、易编程之间也有一种制约关系 这两个要求有时互相矛盾。因此,对反复运行特别是实时的算法,首先考虑的是高效性,对偶尔运行的算法,则需突出算法易理解和易编程。

我们重点考虑时间因素。 一个算法所耗费的时间,应该是该算法中每条语句的执行时间之和,而每条语句的执行时间又是该语句的执行次数(频度)与该语句执行一次所需时间的乘积。 我们假定,每条语句一次执行的时间都是相同的,为单位时间。这样我们对时间的分析就可以独立于软硬件系统。

我们将算法求解问题的输入量称为问题的规模,用一个整数来表示,一个算法的时间复杂度是该算法的时间耗费,一般地说,时间复杂度是问题规模的函数 - T( n )。 当问题的规模n 趋于无穷大时,把时间复杂度T( n )的数量级(阶)称为算法的渐进时间复杂度(有时简称为时间复杂度)。 严格的数学定义为:若T( n ) 和 f( n ) 是定义在正整数集合上的两个函数,当存在两个正的乘数C和n0时,使得对所有的 都有 成立,则 这时称T( n )的时间复杂度为f( n )数量级。

算法运行所需要的时间与两个因素有关: 1、问题实例的大小(如1000个数的排序); 2、实例的具体情况(如1000个数的排列情况)

算法分析 1、假定每条语句的执行时间为单位时间。算法的时间复杂度是该算法中所有语句的执行频度之和。 例:求两个方阵的乘积 C=A*B #define n 自然数 MATRIXMLT(float A[n][n],float B[n][n],float C[n][n]) { int i,j,k; for(i=0;i<n;i++) //n+1 for(j=0;j<n;j++) //n(n+1) C[i][j]=0; //n*n for( k=0;k<n;k++) //n*n*(n+1) C[i][j]=A[i][k]*B[k][j] //n*n*n } }

2、一般情况下,对步进循环语句只考虑循环体语句的执行次数,而忽略该语句中步长加一、终值判别、循环转移等成份。因此,当有若干个循环语句时,算法的时间复杂度是由嵌套层数最多的循环语句中最内层语句的频度所决定的。 例 1:x=0;y=0; for (k=1;k<=n;k++) x++; for (i=1;i<=n;i++) for (j=1;j<=n;j++) //n*n y++; 一般情况下,对步进循环语句只需考虑循环体中语句的执行次数,而忽略循环体中步长加1、终值判断、控制转移等成分。

例 2 : x=1; for (i=1;i<=n;i++) for (j=1;j<=i;j++) for (k=1;k<=j;k++) x++;

3、选择执行的成分,如 if 语句的执行时间,决定于then 子句、else 子句耗时较多的部分 4、如果算法的执行时间是一个与问题规模n无关的常数,则算法的时间复杂度为常数阶,记作T(n)=O(1) 。 例: temp = i; i = j; j = temp;

while ((i>=0)&&A[i]!=k)) j--; return i; 5、很多算法的时间复杂度不仅与问题的规模有关,而且还与它所处理的数据集的状态有关。通常是根据数据集中可能出现的最坏情况估计出算法的最坏时间复杂度。 例 1 : i=n-1; while ((i>=0)&&A[i]!=k)) j--; return i; 此问题不仅与规模 n 有关,而且与数组A中各元素的取值有关。

例 2 : fact(n) { if (n <= 1) return 1; else return (n*fact(n-1)); } 设 fact 的运行时间函数为T(n),则有

常见的时间复杂度,按数量级递增排序: 常数阶 对数阶 线性阶 线性对数阶 平方阶 立方阶 ……… K次方阶 指数阶

算法的后期测试 在算法中的某些部位插装时间函数 time ( ) 测定算法完成某一功能所花费的时间

第一章 绪论 1 数据结构讨论的范畴 2 数据结构的基本概念 3 数据类型和抽象数据类型 4 C语言的数据类型 5 第一章 绪论 1 数据结构讨论的范畴 2 数据结构的基本概念 3 数据类型和抽象数据类型 4 C语言的数据类型 5 算法设计目标和算法效率度量