数据结构c(王红梅)课件.ppt

主教材王红梅.数据结构（C版）.清华大学出版社辅导及实验教材王红梅.数据结构学习辅导与实验指导.清华大学出版社参考教材1.严蔚敏.数据结构.清华大学出版社.19972.王晓东.数据结构与算法设计.电子工业出版社.20023.曹宏庆译.如何求解问题.中国水利水电出版社.2003,关于教材,课程性质,数据结构是计算机专业的专业基础课 公共基础课、专业基础课、专业方向课、专业选修课在教学计划中的地位：核心、承上启下 前导课：高等数学、离散数学、程序设计语言 后续课：数据库、操作系统、编译原理属于武术中的“练功”科目“练武不练功，到头一场空”考研,学习目标,掌握基本的数据结构 工具箱复用、修改、重组培养算法设计能力、程序设计能力 算法程序的灵魂 问题求解过程：问题想法算法程序 程序设计研究的层次：算法方法学语言工具培养算法分析能力 评价算法、改进算法,学习要求,循序渐进，切忌心浮气躁 提高课外学习的时间和内容 理解科学而不是背诵科学读书 正确对待考试作习题 华罗庚：“学数学不做习题等于入宝山而空返”作实验 计算机学科是一门科学性与工程性并重的学科，表现为理论和实践紧密结合的特征。,如何使用立体化教材,主教材 思想火花、人物小传辅导教材 知识结构、学习要点、重点难点释疑、习题解析实验教材 验证实验综合实验设计实验网站 学校精品课程网站,成绩组成,实验成绩 30：出勤程序报告期末考试成绩 70：接近同类学校考研水平课程设计 成绩：优、良、中、及、不及,第 1 章 绪 论,数据结构的兴起和发展数据结构的研究对象 数据结构的基本概念算法及算法分析,本章的基本内容是：,1938年出生，25岁毕业于加州理工学院数学系，博士毕业后留校任教，28岁任副教授。30岁时，加盟斯坦福大学计算机系，任教授。从31岁起，开始出版他的历史性经典巨著：The Art of Computer Programming他计划共写7卷，然而出版三卷之后，已震惊世界，使他获得计算机科学界的最高荣誉图灵奖，此时，他年仅36岁。,数据结构的创始人克努特,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）：介于自然语言和程序设计语言之间的方法，它采用某一程序设计语言的基本语法，操作指令可以结合自然语言来设计。优点：表达能力强，抽象性强，容易理解,算法的描述方法伪代码,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 算法及算法分析,基本语句的执行次数是否只和问题规模有关？,最好情况：出现概率较大时分析最差情况：实时系统平均情况：已知输入数据是如何分布的，通常假设等概率分布,结论：如果问题规模相同，时间代价与输入数据有关，则需要分析最好情况、最坏情况、平均情况。,1.4 算法及算法分析,最好情况、最坏情况、平均情况,本章小结知识结构图,作业：,公元5世纪末，我国古代数学家张丘建在它所撰定的算经中，提出这样一个问题：“鸡翁一，值钱五；鸡母一，值钱三，鸡雏三，值钱一，百钱买百鸡，问鸡翁、母、雏各几何？”意思是说公鸡每只5元，母鸡每只3元，小鸡3只1元，用100元钱买100只鸡，求公鸡、母鸡、小鸡的只数。试设计算法求解该问题，并分析你所设计的算法的时间复杂度。（要求：算法分别用伪代码和C描述）,