数据结构绪论

数据结构,C+语言描述,教学基本要求,平时提问，课堂练习。书面作业，每周交一次。分纸质与电子两种。完成2个左右实验和报告，实验课上机测试。平时成绩10%，实验成绩20%，期中考试10%，期终考试60%。考勤：迟到、旷课扣平时分。禁止在实验课上做与教学无关的事。上课应关闭手机或置于禁音状态，违者严禁课上吃食物(可以喝水),数据结构的创始人,程序=算法+数据结构,算法和程序设计技术的先驱者，计算机排版系统TEX和METAFONT的发明者，他因这些成就和大量创造性的影响深远的著作(19部书和160篇论文)而誉满全球。作为斯坦福大学计算机程序设计艺术的荣誉退休教授，他当前正全神贯注于完成其关于计算机科学的史诗性的七卷集。这一伟大工程在1962年他还是加利福尼亚理工学院的研究生时就开始了。 Knuth教授获得了许多奖项和荣誉，包括美国计算机协会图灵奖(ACM Turing Award)，美国前总统卡特授予的科学金奖(Medal of Science)，美国数学学会斯蒂尔奖(AMS Steele Prize)，以及1996年11月由于发明先进技术荣获的极受尊重的京都奖(KyotoPrize)。现与其妻Jill生活于斯坦福校园内。,D.E.Knuth(唐纳德.E.克努特),数据结构的重要性,计算机程序设计语言不等于程序，是实现程序的工具。通过算法训练培养计算思维的能力，通过程序设计的技能训练来促进综合应用能力和专业素质的提高。本课程是研究生入学考试必考内容，也是高级程序员证书、软件公司用人必考内容。,第 1 章 绪 论,数据结构的兴起和发展数据结构的研究对象 数据结构的基本概念算法及算法分析,本章的基本内容是：,1.1 数据结构的兴起和发展,程序设计的实质是什么?,数据表示：将数据存储在计算机中数据处理：处理数据，求解问题,数据结构问题起源于程序设计,数据结构随着程序设计的发展而发展,数据结构的发展并未终结,1. 无结构阶段2. 结构化阶段：数据结构算法程序3. 面向对象阶段： （数据结构算法）程序,1.1 数据结构的兴起和发展,1.2 数据结构的研究对象,计算机求解问题: 问题抽象出问题的模型求模型的解问题数值问题、非数值问题 数 值 问 题数学方程 非数值问题数据结构,例1 学籍管理问题表结构,1.2 数据结构的研究对象,完成什么功能?各表项之间是什么关系？,例2 人机对弈问题树结构,1.2 数据结构的研究对象,如何实现对弈?各格局之间是什么关系？,例3 教学计划编排问题图结构,1.2 数据结构的研究对象,如何表示课程之间的先修关系？,数据结构是研究非数值问题中计算机的操作对象以及它们之间的关系和操作的学科。,1.2 数据结构的研究对象,1.3 数据结构的基本概念,数据：所有能输入到计算机中并能被计算机程序识别和处理的符号集合。 数值数据：整数、实数等 非数值数据：图形、图象、声音、文字等 数据元素：数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。数据项：构成数据元素的不可分割的最小单位。数据对象：具有相同性质的数据元素的集合。,数据结构的基本概念,数据、数据元素、数据项之间的关系,包含关系：数据是由数据元素组成，数据元素是由数据项组成。数据元素是讨论数据结构时涉及的最小数据单位，其中的数据项一般不予考虑。,1.3 数据结构的基本概念,数据结构：相互之间存在一定关系的数据元素的集合。按照视点的不同，数据结构分为逻辑结构和存储结构。逻辑结构：指数据元素之间逻辑关系的整体。,1.3 数据结构的基本概念,数据结构的基本概念,数据的逻辑结构是从具体问题抽象出来的数据模型,数据结构：相互之间存在一定关系的数据元素的集合。按照视点的不同，数据结构分为逻辑结构和存储结构。逻辑结构：指数据元素之间逻辑关系的整体。存储结构：又称为物理结构，是数据及其逻辑结构在计算机中的表示。,1.3 数据结构的基本概念,数据结构的基本概念,存储结构实质上是内存分配，在具体实现时，依赖于计算机语言。,数据结构从逻辑上分为四类： 集合：数据元素之间就是 “属于同一个集合” ；,1.3 数据结构的基本概念,数据结构的基本概念,数据结构从逻辑上分为四类： 集合：数据元素之间就是 “属于同一个集合” ； 线性结构：数据元素之间 存在着一对一的线性关系；,1.3 数据结构的基本概念,数据结构的基本概念,数据结构从逻辑上分为四类： 集合：数据元素之间就是 “属于同一个集合” ； 线性结构：数据元素之间 存在着一对一的线性关系； 树结构：数据元素之间存在 着一对多的层次关系；,1.3 数据结构的基本概念,数据结构的基本概念,数据结构从逻辑上分为四类： 集合：数据元素之间就是 “属于同一个集合” ； 线性结构：数据元素之间 存在着一对一的线性关系； 树结构：数据元素之间存在 着一对多的层次关系； 图结构：数据元素之间存在 着多对多的任意关系。,1.3 数据结构的基本概念,数据结构的基本概念,通常有两种存储结构：1. 顺序存储结构：用一组连续的存储单元依次存储数据元素，数据元素之间的逻辑关系由元素的存储位置来表示。,1.3 数据结构的基本概念,数据结构的基本概念,通常有两种存储结构：1. 顺序存储结构：用一组连续的存储单元依次存储数据元素，数据元素之间的逻辑关系由元素的存储位置来表示。2. 链接存储结构：用一组任意的存储单元存储数据元素，数据元素之间的逻辑关系用指针来表示 。,例：（bat, cat, eat）,1.3 数据结构的基本概念,数据结构的基本概念,bat0200,cat0325,eat ,逻辑结构和存储结构之间的关系,数据的逻辑结构属于用户视图，是面向问题的，反映了数据内部的构成方式；数据的存储结构属于具体实现的视图，是面向计算机的。 一种数据的逻辑结构可以用多种存储结构来存储，而采用不同的存储结构，其数据处理的效率往往是不同的。,1.3 数据结构的基本概念,数据结构的访问接口,对数据结构的访问是指对数据的读取、修改、加工、处理等操作。数据结构的基本操作：各种应用都能通过这些操作实现对数据结构的各种访问。 基本操作的特性：抽象性、基本性、完备性、一般性 访问接口：操作的调用形式与规范（例如形参表、返回类型等）。数据结构的访问接口：数据结构基本操作接口的全体。,1.3 数据结构的基本概念,抽象数据类型,1. 数据类型（Data Type）：一组值的集合以及定义于这个值集上的一组操作的总称。 例如：C+中的整型变量 2. 抽象（Abstract）:抽出问题本质的特征而忽略非本质的细节。 例如： 地图、驾驶汽车3. 抽象数据类型（Abstract Data Type，ADT）:一个数据结构以及定义在该结构上的一组操作的总称。,1.3 数据结构的基本概念,ADT是对数据类型的进一步抽象,ADT的不同视图,1.3 数据结构的基本概念,ADT 抽象数据类型名Data 数据元素之间逻辑关系的定义Operation 操作1 前置条件：执行此操作前数据所必须的状态 输 入：执行此操作所需要的输入 功 能：该操作将完成的功能 输 出：执行该操作后产生的输出 后置条件：执行该操作后数据的状态 操作2 操作n endADT,ADT的定义形式,1.3 数据结构的基本概念,1.3 数据结构的基本概念（小结）,数据的操作：插入、删除、修改、检索、排序等,算法的相关概念,1.算法（Algorithm）:是对特定问题求解步骤的一种描述，是指令的有限序列。,2. 算法的五大特性： 输入：一个算法有零个或多个输入。 输出：一个算法有一个或多个输出。 有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。 确定性：算法中的每一条指令必须有确切的含义，对于相同的输入只能得到相同的输出。 可行性：算法描述的操作可以通过已经实现的基本操作执行有限次来实现。,1.4 算法及算法分析,欧几里德算法,m,n,r,例：欧几里德算法辗转相除法求两个自然数 m 和 n 的最大公约数,1.4 算法及算法分析,算法的描述方法自然语言,优点：容易理解缺点：冗长、二义性使用方法：粗线条描述算法思想 注意事项：避免写成自然段,1.4 算法及算法分析, 输入m 和n； 求m除以n的余数r； 若r等于0，则n为最大公约数，算法结束；否则执行第步； 将n的值放在m中，将r的值放在n中； 重新执行第步。,例：欧几里德算法,自然语言,1.4 算法及算法分析,优点：流程直观 缺点：缺少严密性、灵活性使用方法：描述简单算法注意事项：注意抽象层次,算法的描述方法流程图,1.4 算法及算法分析,流 程 图,例：欧几里德算法,1.4 算法及算法分析,优点：能由计算机执行 缺点：抽象性差，对语言要求高使用方法：算法需要验证注意事项：将算法写成子函数,算法的描述方法程序设计语言,1.4 算法及算法分析,#include int CommonFactor(int m, int n) int r=m % n; while (r!=0) m=n; n=r; r=m % n; return n;void main( ) coutCommonFactor(63, 54)endl;,程序设计语言,例：欧几里德算法,1.4 算法及算法分析,4 算法及算法分析,伪代码（Pseudocode）：介于自然语言和程序设计语言之间的方法，它采用某一程序设计语言的基本语法，操作指令可以结合自然语言来设计。优点：表达能力强，抽象性强，容易理解使用方法：7 2,算法的描述方法伪代码,1.4 算法及算法分析,1. r = m % n; 2. 循环直到 r 等于0 2.1 m = n; 2.2 n = r; 2.3 r = m % n; 3. 输出 n ;,伪 代 码,上述伪代码再具体一些，用C+的函数来描述。请同学们自行完成！,例：欧几里德算法,1.4 算法及算法分析,算法分析,度量算法效率的方法： 事后统计：将算法实现，测算其时间和空间开销。 缺点： 编写程序实现算法将花费较多的时间和精力； 所得实验结果依赖于计算机的软硬件等环境因素。 事前分析：对算法所消耗资源的一种估算方法。,1.4 算法及算法分析,算法分析,算法分析（Algorithm Analysis）：对算法所需要的计算机资源时间和空间进行估算。 时间复杂性（Time Complexity） 空间复杂性（Space Complexity）,1.4 算法及算法分析,算法的时间复杂度分析,1.4 算法及算法分析,算法分析,算法的执行时间每条语句执行时间之和,for (i=1; i=n; i+) for (j=1; j=n; j+) x+;,问题规模：输入量的多少。基本语句：是执行次数与整个算法的执行次数成正比的操作指令。,for (i=1; i=n; i+) for (j=1; j=n; j+) x+;,问题规模：n基本语句：x+,1.4 算法及算法分析,算法分析,定义 若存在两个正的常数c和n0，对于任意nn0，都有T(n)cf(n)，则称T(n)=O(f(n),当问题规模充分大时在渐近意义下的阶,1.4 算法及算法分析,算法分析大O符号,定理：若A(n)=amnm+am-1nm-1+a1n+a0是一个m次多项式，则A(n)=O(nm)。,说明：在计算算法时间复杂度时，可以忽略所有低次幂和最高次幂的系数。,1.4 算法及算法分析,算法分析大O符号,例1-5 +x; 例1-6 for (i=1; i=n; +i) +x; 例1-7 for (i=1; i=n; +i) for (j=1; j=n; +j) +x; 例1-8 for (i=1; i=n; +i) for (j=1; j=i-1; +j) +x;,1.4 算法及算法分析,算法分析,例1-9 for (i=1; i=n; +i) for (j=1; j=n; +j) cij=0; for (k=1; k=n; +k) cij+=aik*bkj; 例1-10 for (i=1; i=n; i=2*i) +x;,(1)(log2n)(n)(nlog2n)(n2)(n3) (2n)(n!),1.4 算法及算法分析,算法分析,最好情况、最坏情况、平均情况,例：在一维整型数组An中顺序查找与给定值k相等的元素（假设该数组中有且仅有一个元素值为k）。,int Find(int A , int n) for (i=0; in; i+) if (Ai= =k) break; return i; ,1.4 算法及算法分析,基本语句的执行次数是否只和问题规模有关？,最好情况：出现概率较大时分析最差情况：实时系统平均情况：已知输入数据是如何分