《数据结构》(C语言版)第一章 绪论.ppt

《《数据结构》(C语言版)第一章 绪论.ppt》由会员分享，可在线阅读，更多相关《《数据结构》(C语言版)第一章 绪论.ppt（70页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、教材:数据结构（C语言版）严蔚敏 吴伟民 编著 清华大学出版社计算机科学与技术学院计算机科学与技术学院1开设本课程的背景：开设本课程的背景：数数据据结结构构是是计计算算机机相相关关专专业业的的一一门门重重要要的的专专业业基基础础课课。它它主主要要研研究究计计算算机机加加工工对对象象的的逻逻辑辑结结构构、在在计计算算机机中中的的存存储储结结构构以以及及实实现现各各种种基基本本操操作作的的算算法法。它它是是学学习习操操作作系系统统、编编译译原原理理、数数据据库库原原理理等等计计算算机机专专业业核核心心课课程程的的基基础础，掌掌握握好好这这门门课课程程的的内内容容，是是学学习习计计算算机机其其他他相

2、相关关课课程程的的必备条件。必备条件。2本课程讲述的主要内容：本课程讲述的主要内容：分分别别讲讲述述数数据据结结构构的的基基本本概概念念、线线性性表表、栈栈和和队队列列、串串、数数组组和和广广义义表表、树树和和二二叉叉树树、图、查找、排序等内容。图、查找、排序等内容。学习本课程的基本方法：学习本课程的基本方法：l上课认真听讲；上课认真听讲；l仔仔细细阅阅读读教教材材中中的的大大量量例例题题，从从而而体体会会并最终掌握数据结构中的基本概念；并最终掌握数据结构中的基本概念；l独立完成每个章节的练习题和作业题。独立完成每个章节的练习题和作业题。3数据结构教学要求：数据结构教学要求：学学会会分分析析研

3、研究究计计算算机机加加工工的的数数据据结结构构的的特特性性，以以便便为为应应用用涉涉及及的的数数据据选选择择适适当当的的逻逻辑辑结结构构、存存储储结结构构及及其其相相应应的的算算法法，并并初初步步掌握算法的时间分析和空间分析技术。掌握算法的时间分析和空间分析技术。要要求求编编写写的的程程序序结结构构清清楚楚和和正正确确易易读读，符合软件工程的规范。符合软件工程的规范。4数据结构在计算机科学中的地位 数据结构是计算机软件和计算机应用专业的核心课程之一，由于在计算机系统软件和应用软件中都要用到各种数据结构，要想更有效地使用计算机，就必须学习数据结构的有关知识。程序设计的实质是对实际问题选择一种好的

4、数据结构，加之设计一个好的算法，而好的算法在很大程度上取决于描述实际问题的数据结构。结构运算逻辑结构存储结构+数据结构数据结构算法+程序瑞士计算机科学家沃思(N.Wirth)教授提出：结构运算逻辑结构存储结构+数据结构数据结构算法+程序瑞士计算机科学家沃思(N.Wirth)教授提出：5数据结构在软件从业人员的知识与技能结构中的地位编程语言解决问题的思想6 任何受过专业训练的程序员，对“数据结构”这门课程中涉及到的各种数据结构都不会陌生，但是在实际的编程工作中，大部分的数据结构都不会用到，而且也永远都不会用到。虽然如此，深入地理解基本数据结构的概念和实现细节，仍然是每个程序员的任务。这不仅仅是因

5、为，掌握这些知识将有利于更加正确和灵活地应用它们，而且也是因为，对于语言背后的实现细节的求知欲是一个优秀程序员的素质。-摘自最基础的数据结构7 1.1 什么是数据结构什么是数据结构第一章 绪论1.3 算法和算法分析算法和算法分析1.2 基本概念和术语基本概念和术语8学习提要：1.熟悉各名词术语的含义，掌握基本概熟悉各名词术语的含义，掌握基本概念。念。2.了了解解抽抽象象数数据据类类型型的的定定义义、表表示示和和实实现方法。现方法。3.理理解解算算法法五五个个要要素素的的确确切切含含义义，掌掌握握估算算法时间复杂度的方法。估算算法时间复杂度的方法。重难点内容：数数据据的的逻逻辑辑结结构构、数数据

6、据存存储储结结构构、时时间间复杂度的估算方法复杂度的估算方法 91.1 什么是数据结构什么是数据结构程序设计程序设计:为计算机处理问题编制为计算机处理问题编制 一组指令集。一组指令集。算法算法:处理问题的策略。处理问题的策略。数据结构数据结构:问题的数学模型。问题的数学模型。程序程序 =算法算法 +数据结构数据结构 10数值计算数值计算的程序设计问题：的程序设计问题：例如：例如：结构静力分析计算结构静力分析计算 线性代数方程组线性代数方程组 预报人口增长情况预报人口增长情况 微分方程微分方程11非数值计算非数值计算的程序设计问题：的程序设计问题：算法:?模型：？基本操作是“比较两个数的比较两个

7、数的大小大小”取决于整数值的范围整数值的范围例例1 1：求一组(n个)整数整数中的最大值。12例例2 书目自动检索系统书目自动检索系统登录号：书名：作者名：分类号：出版单位：出版时间：价格：书目卡片书目文件按书名按作者名按分类号索引表线性表算法：算法：需要检索的书目？如何检索？用户界面？需要检索的书目？如何检索？用户界面？模型：模型：？13例例3 3 人机对奕问题人机对奕问题树.算法：算法：对奕的规则和策略对奕的规则和策略模型：模型：？14例例4 4 教学计划编排问题教学计划编排问题 图课程代号课程代号课程代号课程代号课程名称课程名称课程名称课程名称先修课程先修课程先修课程先修课程C1计算机导

8、论计算机导论无无C2数据结构数据结构C1,C4C3汇编语言汇编语言C1C4C语言语言C1C5计算机图形学计算机图形学C2,C3,C4C6接口技术接口技术C3C7数据库原理数据库原理C2,C9C8编译原理编译原理C4C9操作系统操作系统C2C1C3C4C7C6C5C2C8C9 算法：算法：如何确定课程的次序关系如何确定课程的次序关系?模型：模型：？15概括地说：概括地说：数据结构是一门讨论数据结构是一门讨论“描述现描述现实世界实体的实世界实体的数学模型数学模型(非数值计非数值计算算)及其上的及其上的操作操作在计算机中如何在计算机中如何表示和实现表示和实现”的学科。的学科。161.2 基本概念和术

9、语基本概念和术语一、数据与数据结构一、数据与数据结构二、数据类型二、数据类型三、抽象数据类型三、抽象数据类型17数据数据（data)：所有能被输入到计算机：所有能被输入到计算机中，且被计算机处理的符号的集合中，且被计算机处理的符号的集合，是计算机操作的对象的总称。是计算机操作的对象的总称。数据元素数据元素（data element）：）：是数据是数据（集合）中的一个（集合）中的一个“个体个体”，是数据，是数据的的基本基本单位单位，由若干个，由若干个数据项数据项组成，组成，也称结点、元素、顶点或也称结点、元素、顶点或记录。记录。一、数据与数据结构一、数据与数据结构18 数据项：数据项：是数据结构

10、中讨论的是数据结构中讨论的最小最小单位。单位。例如：例如：描述一个学生基本信息的数据描述一个学生基本信息的数据元素可以是元素可以是称之为组合项称之为组合项学号学号姓名姓名性别性别专业班级专业班级 出生日期出生日期 籍贯籍贯年年 月月 日日19数据结构数据结构(data structure)：是是指指互互相相之之间间存存在在着着一一种种或或多多种种关关系系的数据元素的的数据元素的集合集合。或或者者说说，数数据据结结构构是是带带结结构构的的数数据据元素的集合。元素的集合。20例例：一一个个含含12位位数数的的十十进进制制数数可可以以用三个用三个4位的十进制数表示位的十进制数表示 3214,6587

11、,9345 a1(3214),a2(6587),a3(9345)在在a1、a2、a3 之之间间存存在在“次次序序”关关系：系：a1,a2、a2,a3 3214，6587，9345 a1 a2 a3 6587，3214，9345 a2 a1 a321又例，又例，在2行3列的二维数组a1,a2,a3,a4,a5,a6行的次序关系行的次序关系:列的次序关系列的次序关系:row=,col=,a1 a3 a5 a2 a4 a6 a1 a2 a3a4 a5 a622再例，再例，在一维数组 a1,a2,a3,a4,a5,a6 的数据元素之间存在如下的次序关系次序关系:|i=1,2,3,4,5 可见，不同的“

12、关系关系”构成不同的“结构结构”。23集合结构：集合结构：数据元素间数据元素间“同属于一个集合同属于一个集合”数据的逻辑结构逻辑结构可归结为以下四类四类:线性结构：线性结构：一个对一个一个对一个树形结构：树形结构：一个对多个一个对多个图状结构：图状结构：多个对多个多个对多个24数据结构的形式定义数据结构的形式定义为:数据结构数据结构是一个二元组 Data_Structure=(D,S)其中:D 是数据元素的有限集数据元素的有限集，S 是 D上关系的有限集关系的有限集。25例例：在在计计算算机机科科学学中中，复复数数可可取取如如下下定义定义 Complex=（C，R）其中，其中，C是含两个实数集

13、合是含两个实数集合c1，c2；R=P，P是是定定义义在在集集合合C上上的的一种关系一种关系。26数据的逻辑结构数据的逻辑结构：只抽象反映数据：只抽象反映数据元素的逻辑关系。元素的逻辑关系。数据的存储结构：数据的存储结构：逻辑结构在存储逻辑结构在存储器中的映象。器中的映象。“数据元素”的映象？“关系”的映象？27数据元素的映象方法：数据元素的映象方法：用用二进制位二进制位(bit)(bit)的位串表示数的位串表示数据元素。据元素。(321)10 =(501)8 =(101000001)2 A =(101)8 =(001000001)228关系的映象方法：关系的映象方法：（表示x,y的方法）1 1

14、、顺序映象、顺序映象以相对的存储位置表示后继关系。以相对的存储位置表示后继关系。例如例如:令 y 的存储位置和 x 的存储位置之间差一个常量 C。而 C 是一个隐含值，整个存储结整个存储结构中只含数据元素本身的信息构中只含数据元素本身的信息 x y292 2、链式映象、链式映象以附加信息以附加信息(指针指针)表示后继关系。表示后继关系。需要用一个和 x 在一起的附加信附加信息息指示 y 的存储位置。y x30例如：例如：复数复数z1=3.0-2.3i，z2=-0.7+4.8i的的存储存储结构。结构。顺序存储结构顺序存储结构链式存储结构链式存储结构3.03.031二、数据类型二、数据类型 在用高

15、级程序语言编写的程序中，必须对程序中出现的每个变量、常量或表达式，明确说明明确说明它们所属的数据类型数据类型。32例例：C语言语言中，提供中，提供int,char,float等等基本数据类型基本数据类型，数组、结构体、共用体、枚举等数组、结构体、共用体、枚举等构造数据类型构造数据类型指针、空指针、空(void)类型等。类型等。用户也可用用户也可用typedef 自己定义数据类型自己定义数据类型typedef struct int num;char name20;float score;STUDENT;STUDENT stu1,stu2,*p;33 数据类型数据类型 是一个 值的集合值的集合和定

16、义在此集合上的 一组操作一组操作的总称。不同类型的变量，其所能取的值的值的范围范围不同，所能进行的操作进行的操作不同。34数据类型可以分为两类数据类型可以分为两类:一类是原子类一类是原子类型。另一类是结构类型。型。另一类是结构类型。引入数据类型的目的：引入数据类型的目的：从硬件的角度看，是作为解释计算从硬件的角度看，是作为解释计算机内存中信息含义的一种手段。机内存中信息含义的一种手段。对使用数据类型的用户来说，实现对使用数据类型的用户来说，实现了信息的隐蔽，即将一切用户不必了了信息的隐蔽，即将一切用户不必了解的细节都封装在类型中。解的细节都封装在类型中。35三、抽象数据类型三、抽象数据类型 (

17、Abstract Data Type 简称简称ADT)vADT定义：定义：指一个指一个数学模型数学模型以及定义在该模型以及定义在该模型上的一组上的一组操作操作。“抽象抽象”的意义在于数据类型的的意义在于数据类型的数数学抽象特性学抽象特性。36 例如：例如：矩阵+（求转置、加、乘、求逆、求特征值）构成一个矩阵的抽象数据类型。37vADT的描述方法：的描述方法：抽象数据类型抽象数据类型可用三元组 （D，S，P）表示。其中：D 是数据对象；S 是 D 上的关系集；P 是对 D 的基本操作集。38ADT 抽象数据类型名抽象数据类型名 数据对象：数据对象：数据对象的定义 数据关系：数据关系：数据关系的定

18、义 基本操作：基本操作：基本操作的定义 ADT 抽象数据类型名其中基本操作基本操作的定义格式定义格式为:基本操作名基本操作名（参数表）初始条件：初始条件：初始条件描述 操作结果操作结果：操作结果描述 39赋值参数:只为操作提供输入值。引用参数:以&打头，除可提供输入值外，还将返回操作结果。初始条件初始条件:描述了操作执行之前数据结构和参数应满足的条件，若不满足，则操作失败，并返回相应出错信息。操作结果操作结果:说明了操作正常完成之后，数据结构的变化状况和应返回的结果。若初始条件为空，则省略之。40例如，例如，抽象数据类型复数复数的定义：数据对象：数据对象：De1,e2e1,e2RealSet

19、数据关系：数据关系：R1|e1是复数的实数部分|e2 是复数的虚数部分 ADT Complex 41基本操作：基本操作：AssignComplex(&Z,v1,v2)操作结果：操作结果：构造复数 Z,其实部和虚部 分别被赋以参数 v1 和 v2 的值。DestroyComplex(&Z)操作结果操作结果：复数Z被销毁。GetReal(Z,&realPart)初始条件：复数已存在。操作结果：用realPart返回复数Z的实部值。42 GetImag(Z,&ImagPart)初始条件：复数已存在。操作结果：用ImagPart返回复数Z的虚部值。Add(z1,z2,&sum)初始条件：z1,z2是复

20、数。操作结果：用sum返回两个复数z1,z2 的 和值。ADT Complex43假设假设:z1和z2是上述定义的复数则 Add(z1,z2,z3)操作的结果z3=z1+z2即为用户所求的结果44ADT 有两个重要特征:数据抽象：数据抽象：用ADT描述程序处理的实体时，强调的是其本质的特征本质的特征、其所能完成的其所能完成的功能功能以及它和外部用户的接口外部用户的接口（即外界外界使用它的方法使用它的方法）。数据封装：数据封装：将实体的外部特性和其内部外部特性和其内部实现细节分离实现细节分离，并且对外部用户隐藏对外部用户隐藏其内部实现细节。其内部实现细节。45vADT的表示和实现：的表示和实现：

21、抽象数据类型需要通过固有数据固有数据类型类型(高级编程语言中已实现的数据类型)来实现。例如，对以上定义的复数。例如，对以上定义的复数。46typedef struct float realpart；float imagpart；complex；/-存储结构的定义存储结构的定义/-基本操作的函数原型说明基本操作的函数原型说明void Assign(complex&Z,float realval,float imagval)；/构造复数 Z,其实部和虚部分别被赋以 /参数 realval 和 imagval 的值47float GetReal(complex Z)；/返回复数 Z 的实部值floa

22、t Getimag(complex Z)；/返回复数 Z 的虚部值void add(complex z1,complex z2,complex&sum)；/以 sum 返回两个复数 z1,z2 的和 48/-基本操作的实现基本操作的实现void add(complex z1,complex z2,complex&sum)/以 sum 返回两个复数 z1,z2 的和 sum.realpart=z1.realpart+z2.realpart;sum.imagpart=z1.imagpart+z2.imagpart;其它省略 49一、算法的定义一、算法的定义二、算法设计的原则二、算法设计的原则三、算

23、法效率的衡量方法和准则三、算法效率的衡量方法和准则四、算法的存储空间需求四、算法的存储空间需求1.3 算法和算法和算法算法分析分析50 算法算法是对特定问题求解步骤的描求解步骤的描述述，是指令的有限序列。1.有穷性 2.确定性 3.可行性4.有输入 5.有输出一、算法的定义一、算法的定义一个算法必须满足以下五五个重要特性个重要特性：511.有穷性有穷性：对于任意一组合法输入值，在执行有穷步骤有穷步骤之后一定能结束，即算法中的每个步骤都能在有限时间有限时间内完成。2.2.确定性：确定性：对于每种情况每种情况下所应执行的操作，在算法中都有确切确切的规定，使算法的执行者或阅读者都能明确其含义及如何执

24、行。并且并且在任何条件下，算法都只有一条在任何条件下，算法都只有一条执行路径。执行路径。523.可行性：可行性：算法中的所有操作都必须足够基本，都可以通过已经实现的基本操作运算有限次实现之。4.有输入：有输入：有零个或多个输入，取自特定的对象集合。5.有输出：有输出：有一个或多个输出，是算法进行信息加工后得到的结果。53二、算法设计的原则二、算法设计的原则 设计算法时，通常应考虑达到以下目标：1正确性正确性2.可读性可读性3健壮性健壮性4高效率与低存储量需求高效率与低存储量需求541.1.正确性：正确性：在在合理合理的数据输入下，能在的数据输入下，能在有限的运算时间有限的运算时间内得到内得到正

25、确结果正确结果。对算法是否对算法是否“正确正确”的理解可以有以下四个层次：的理解可以有以下四个层次：a a程序中不含语法错误；程序中不含语法错误；b b程序对于程序对于几组几组输入数据能够得出满足要求的输入数据能够得出满足要求的结果；结果；c c程序对于程序对于精心选择的、典型、苛刻切带有刁精心选择的、典型、苛刻切带有刁难性难性的几组输入数据能够得出满足要求的结果；的几组输入数据能够得出满足要求的结果；d d程序对于程序对于一切合法一切合法的输入数据都能得出满足的输入数据都能得出满足要求的结果；要求的结果；552.2.可读性：可读性：易于人对算法的理解；另一方面，晦涩难读的程序易于隐藏较多错误

26、而难以调试；3.3.健壮性：健壮性：当输入的数据非法非法时，算法应当恰当地作出反映或进行相应处理进行相应处理，而不是产生莫名奇妙的输出结果。并且，处理处理出错的方法出错的方法不应是中断程序的执行，而应是返回返回一个表示错误或错误性质的值表示错误或错误性质的值，以便在更高的抽象层次上进行处理。564.高效率与低存储量需求：高效率与低存储量需求：效率效率指的是算法执行时间。存储量存储量指的是算法执行过程中所需的最大存储空间。两者都与问题的规模问题的规模有关。57有两种衡量算法效率的方法有两种衡量算法效率的方法:1.事后统计法：事后统计法：利用计算机内记时利用计算机内记时功能，用一组或多组相同的统计

27、数据功能，用一组或多组相同的统计数据区分。区分。2.事前分析估计法：事前分析估计法：求出算法的一求出算法的一个时间界限函数。个时间界限函数。三三、算法效率的衡量方法和准则、算法效率的衡量方法和准则58和算法执行时间时间相关的因素因素：1 1算法算法选用的策略的策略2 2问题的规模问题的规模3 3编写程序的语言语言4 4编译编译程序产生的机器代码的质量的质量5 5计算机计算机执行指令的速度的速度59 设解决一个问题的规模问题的规模为n，基本操基本操作作被重复执行的次数是f(n)。假如，随着问题规模 n 的增长，算法算法执行时间的增长率和执行时间的增长率和 f(n)的增长率相同的增长率相同，则可记

28、作：T(n)=O(f(n)称称T(n)为算法的为算法的渐近时间复杂度，时间复杂度，简称简称时间复杂度时间复杂度。60算法算法 =控制结构控制结构 +原操作原操作 （固有数据类型的操作）算法的执行时间算法的执行时间=原操作原操作(i)(i)的执行次数的执行次数原操作原操作(i)(i)的执行时间的执行时间如何估算算法的时间复杂度？如何估算算法的时间复杂度？61 从算法中选取一种对于所研究的问题来说是 基本操作基本操作 的原操作，以该基本操作 在算法中重复执行在算法中重复执行的次数的次数 作为算法运行时间的衡量准则。62void mult(int a,int b,int&c)/以二维数组存储矩阵元素

29、，c 为 a 和 b 的乘积 for(i=1;i=n;+i)for(j=1;j=n;+j)ci,j=0;for(k=1;k=n;+k)ci,j+=ai,k*bk,j;/for/mult基本操作:乘法乘法操作时间复杂度:O(n3)例例1 1 两个两个矩阵相乘矩阵相乘63例例2 +x;s=0;T(n)=T(n)=(1)(1)T(n)=T(n)=O(n)O(n)例例3 for(i=1;i=n;+i)+x;s+=x;例例4 for(i=2;i=n;+i)for(j=2;j=i-1;+j)+x;ai,j=x;T(n)=T(n)=O(nO(n2 2)64 T(n)=T(n)=O(logO(log2 2n)

30、n)例例5 int n=8,count=0;for(int i=1;i=n;i*=2)count+;例例6 int n=8,count=0;for(int i=1;i=n;i*=2)for(int j=1;j=n;j+)count+;T(n)=T(n)=O(nlogO(nlog2 2n)n)65时间复杂度随n变化情况的比较时间复杂度n=8(23)n=10n=100n=1000O(1)1111O(log2n)33.3226.6449.966O(n)8101001000O(nlog2n)2433.22664.49966O(n2)6410010000106(1)(log2n)(n)(n2)(n3)(

31、2n)66 change=FALSE;/change 为元素进行交换标志 for(j=0;j aj+1)aj aj+1;change=TRUE;/一趟起泡void bubble_sort(int&a,int n)/将 a 中整数序列重新排列成自小至大有序的整数序列。for(i=n-1,change=TRUE;i1&change;-i)/bubble_sort基本操作:交换交换操作时间复杂度:O(n2)例例5 5 起泡排序起泡排序67四、算法的存储空间需求四、算法的存储空间需求算法的空间复杂度空间复杂度:表示随着问题规模表示随着问题规模 n 的增大，算的增大，算法运行法运行所需存储量所需存储量的增长率与的增长率与 g(n)的的增长率相同。增长率相同。S(n)=O(g(n)68算法的存储量包括：算法的存储量包括：（1）输入数据输入数据所占空间；（2）程序本身程序本身所占空间；（3）辅助变量辅助变量所占空间。69 数据的逻辑结构数据的逻辑结构 数据的存储结构数据的存储结构 数据的运算：查找数据的运算：查找、排序、插入、删除、修改等排序、插入、删除、修改等 线性结构线性结构 非线性结构非线性结构 顺序存储顺序存储 链式存储链式存储 线性表线性表栈和栈和队列队列串串树形结构树形结构图形结构图形结构数组和广义表数组和广义表数据结构的三个方面：数据结构的三个方面：70