数据结构绪论什么是数据结构.pptx

《数据结构绪论什么是数据结构.pptx》由会员分享，可在线阅读，更多相关《数据结构绪论什么是数据结构.pptx（63页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、开设本课程的背景：开设本课程的背景：数数据据结结构构是是计计算算机机相相关关专专业业的的一一门门重重要要的的专专业业基基础础课课。它它主主要要研研究究计计算算机机加加工工对对象象的的逻逻辑辑结结构构、在在计计算算机机中中的的存存储储结结构构以以及及实实现现各各种种基基本本操操作作的的算算法法。它它是是学学习习操操作作系系统统、编编译译原原理理、数数据据库库原原理理等等计计算算机机专专业业核核心心课课程程的的基基础础，掌掌握握好好这这门门课课程程的的内内容容，是是学学习习计计算算机机其其他他相相关关课课程程的的必备条件。必备条件。第1页/共63页本课程讲述的主要内容：本课程讲述的主要内容：分分别

2、别讲讲述述数数据据结结构构的的基基本本概概念念、线线性性表表、栈栈和和队队列列、串串、数数组组和和广广义义表表、树树和和二二叉叉树树、图、查找、排序等内容。图、查找、排序等内容。学习本课程的基本方法：学习本课程的基本方法：l上课认真听讲；上课认真听讲；l仔仔细细阅阅读读教教材材中中的的大大量量例例题题，从从而而体体会会并最终掌握数据结构中的基本概念；并最终掌握数据结构中的基本概念；l独立完成每个章节的练习题和作业题。独立完成每个章节的练习题和作业题。第2页/共63页 1.1 什么是数据结构什么是数据结构第一章 绪论1.3 算法和算法分析算法和算法分析1.2 基本概念和术语基本概念和术语第3页/

3、共63页学习提要：1.熟悉各名词术语的含义，掌握基本概熟悉各名词术语的含义，掌握基本概念。念。2.了了解解抽抽象象数数据据类类型型的的定定义义、表表示示和和实实现方法。现方法。3.理理解解算算法法五五个个要要素素的的确确切切含含义义，掌掌握握估算算法时间复杂度的方法。估算算法时间复杂度的方法。重难点内容：数数据据的的逻逻辑辑结结构构、数数据据存存储储结结构构、时时间间复杂度的估算方法复杂度的估算方法 第4页/共63页1.1 什么是数据结构程序设计程序设计:为计算机处理问题编制为计算机处理问题编制 一组指令集。一组指令集。算法算法:处理问题的策略。处理问题的策略。数据结构数据结构:问题的数学模型

4、。问题的数学模型。程序程序 =算法算法 +数据结构数据结构 第5页/共63页数值计算数值计算的程序设计问题：的程序设计问题：例如：例如：结构静力分析计算结构静力分析计算 线性代数方程组线性代数方程组 预报人口增长情况预报人口增长情况 微分方程微分方程第6页/共63页非数值计算非数值计算的程序设计问题：的程序设计问题：算法:?模型：？基本操作是“比较两个数的大小比较两个数的大小”取决于整数值的范围整数值的范围例例1 1：求一组(n个)整数整数中的最大值。第7页/共63页例2 书目自动检索系统登录号：书名：作者名：分类号：出版单位：出版时间：价格：书目卡片书目文件按书名按作者名按分类号索引表线性表

5、算法：算法：需要检索的书目？如何检索？用户界面？需要检索的书目？如何检索？用户界面？模型：模型：？第8页/共63页例3 3 人机对奕问题树.算法：算法：对奕的规则和策略对奕的规则和策略模型：模型：？第9页/共63页例4 4 教学计划编排问题 图课程代号课程代号课程代号课程代号课程名称课程名称课程名称课程名称先修课程先修课程先修课程先修课程C1计算机导论计算机导论无无C2数据结构数据结构C1,C4C3汇编语言汇编语言C1C4C语言语言C1C5计算机图形学计算机图形学C2,C3,C4C6接口技术接口技术C3C7数据库原理数据库原理C2,C9C8编译原理编译原理C4C9操作系统操作系统C2C1C3C

6、4C7C6C5C2C8C9 算法：算法：如何确定课程的次序关系如何确定课程的次序关系?模型：模型：？第10页/共63页概括地说：概括地说：数据结构是一门讨论数据结构是一门讨论“描述现描述现实世界实体的实世界实体的数学模型数学模型(非数值计非数值计算算)及其上的及其上的操作操作在计算机中如何在计算机中如何表示和实现表示和实现”的学科。的学科。第11页/共63页1.2 基本概念和术语基本概念和术语一、数据与数据结构一、数据与数据结构二、数据类型二、数据类型三、抽象数据类型三、抽象数据类型第12页/共63页数据数据（data)：所有能被输入到计算机：所有能被输入到计算机中，且被计算机处理的符号的集合

7、中，且被计算机处理的符号的集合，是计算机操作的对象的总称。，是计算机操作的对象的总称。数据元素数据元素（data element）：是数据）：是数据（集合）中的一个（集合）中的一个“个体个体”，是数据，是数据的的基本基本单位单位，由若干个数据项组成，由若干个数据项组成，也称结点、元素、顶点或也称结点、元素、顶点或记录。记录。一、数据与数据结构一、数据与数据结构第13页/共63页 数据项：数据项：是数据结构中讨论的是数据结构中讨论的最小最小单位。单位。例如：例如：描述一个学生基本信息的数据描述一个学生基本信息的数据元素可以是元素可以是称之为组合项称之为组合项学号学号姓名姓名性别性别专业班级专业班

8、级 出生日期出生日期 籍贯籍贯年年 月月 日日第14页/共63页数据结构数据结构(data structure)：是是指指互互相相之之间间存存在在着着一一种种或或多多种种关关系系的数据元素的的数据元素的集合集合。或或者者说说，数数据据结结构构是是带带结结构构的的数数据据元素的集合。元素的集合。第15页/共63页例例：一一个个含含12位位数数的的十十进进制制数数可可以以用三个用三个4位的十进制数表示位的十进制数表示 3214,6587,9345 a1(3214),a2(6587),a3(9345)在在a1、a2、a3 之之间间存存在在“次次序序”关关系：系：a1,a2、a2,a3 3214，65

9、87，9345 a1 a2 a3 6587，3214，9345 a2 a1 a3第16页/共63页又例，又例，在2行3列的二维数组a1,a2,a3,a4,a5,a6行的次序关系:列的次序关系:row=,col=,a1 a3 a5 a2 a4 a6 a1 a2 a3a4 a5 a6第17页/共63页再例，再例，在一维数组 a1,a2,a3,a4,a5,a6 的数据元素之间存在如下的次序关系:|i=1,2,3,4,5 可见，不同的“关系关系”构成不同的“结构结构”。第18页/共63页集合结构：集合结构：数据元素间数据元素间 “同属于一个集合同属于一个集合”数据的逻辑结构逻辑结构可归结为以下四类四类

10、:线性结构：线性结构：一个对一个一个对一个树形结构：树形结构：一个对多个一个对多个图状结构：图状结构：多个对多个多个对多个第19页/共63页数据结构的形式定义数据结构的形式定义为:数据结构是一个二元组 Data_Structure=(D,S)其中:D 是数据元素的有限集数据元素的有限集，S 是 D上关系的有限集关系的有限集。第20页/共63页例例：在在计计算算机机科科学学中中，复复数数可可取取如如下下定义定义 Complex=（C，R）其其中中，C是是含含两两个个实实数数集集合合c1，c2；R=P，P是是定定义义在在集集合合C上上的的一种关系一种关系。第21页/共63页数据的逻辑结构：只抽象反

11、映数据元素的逻辑关系。数据的存储结构：数据的存储结构：逻辑结构在存储逻辑结构在存储器中的映象。器中的映象。“数据元素”的映象？“关系”的映象？第22页/共63页数据元素的映象方法：数据元素的映象方法：用用二进制位二进制位(bit)(bit)的位串表示数的位串表示数据元素。据元素。(321)10 =(501)8 =(101000001)2 A =(101)8 =(001000001)2第23页/共63页关系的映象方法：关系的映象方法：（表示x,y的方法）1 1、顺序映象、顺序映象以相对的存储位置表示后继关系。以相对的存储位置表示后继关系。例如例如:令 y 的存储位置和 x 的存储位置之间差一个常

12、量 C。而 C 是一个隐含值，整个存储结整个存储结构中只含数据元素本身的信息构中只含数据元素本身的信息 x y第24页/共63页2 2、链式映象、链式映象以附加信息以附加信息(指针指针)表示后继关系。表示后继关系。需要用一个和 x 在一起的附加信附加信息息指示 y 的存储位置。y x第25页/共63页例如：例如：复数复数z1=3.0-2.3i，z2=-0.7+4.8i的存的存储结构。储结构。顺序存储结构顺序存储结构链式存储结构链式存储结构3.03.0第26页/共63页二、数据类型二、数据类型 在用高级程序语言编写的程序中，必须对程序中出现的每个变量、常量或表达式，明确说明明确说明它们所属的数据

13、类型数据类型。第27页/共63页例例：C语言语言中，提供中，提供int,char,float等等基本数据类型基本数据类型，数组、结构体、共用体、枚举等数组、结构体、共用体、枚举等构造数据类型构造数据类型指针、空指针、空(void)类型等。类型等。用户也可用用户也可用typedef 自己定义数据类型自己定义数据类型typedef struct int num;char name20;float score;STUDENT;STUDENT stu1,stu2,*p;第28页/共63页 数据类型数据类型 是一个 值的集合值的集合和定义在此集合上的 一组操作一组操作的总称。不同类型的变量，其所能取的值

14、的值的范围范围不同，所能进行的操作进行的操作不同。第29页/共63页三、抽象数据类型三、抽象数据类型 (Abstract Data Type 简称简称ADT)vADT定义：定义：指一个指一个数学模型数学模型以及定义在该模型以及定义在该模型上的一组上的一组操作操作。“抽象抽象”的意义在于数据类型的的意义在于数据类型的数数学抽象特性学抽象特性。第30页/共63页 例如：例如：矩阵+（求转置、加、乘、求逆、求特征值）构成一个矩阵的抽象数据类型。第31页/共63页vADT的描述方法：的描述方法：抽象数据类型抽象数据类型可用三元组 （D，S，P）表示。其中：D 是数据对象；S 是 D 上的关系集；P 是

15、对 D 的基本操作集。第32页/共63页ADT 抽象数据类型名抽象数据类型名 数据对象：数据对象：数据对象的定义 数据关系：数据关系：数据关系的定义 基本操作：基本操作：基本操作的定义 ADT 抽象数据类型名其中基本操作基本操作的定义格式定义格式为:基本操作名基本操作名（参数表）初始条件：初始条件：初始条件描述 操作结果操作结果：操作结果描述 第33页/共63页赋值参数:只为操作提供输入值。引用参数:以&打头，除可提供输入值外，还将返回操作结果。初始条件初始条件:描述了操作执行之前数据结构和参数应满足的条件，若不满足，则操作失败，并返回相应出错信息。操作结果操作结果:说明了操作正常完成之后，数

16、据结构的变化状况和应返回的结果。若初始条件为空，则省略之。第34页/共63页例如，例如，抽象数据类型复数复数的定义：数据对象：数据对象：De1,e2e1,e2RealSet 数据关系：数据关系：R1|e1是复数的实数部分|e2 是复数的虚数部分 ADT Complex 第35页/共63页基本操作：基本操作：AssignComplex(&Z,v1,v2)操作结果：操作结果：构造复数 Z,其实部和虚部 分别被赋以参数 v1 和 v2 的值。DestroyComplex(&Z)操作结果操作结果：复数Z被销毁。GetReal(Z,&realPart)初始条件：复数已存在。操作结果：用realPart返

17、回复数Z的实部值。第36页/共63页 GetImag(Z,&ImagPart)初始条件：复数已存在。操作结果：用ImagPart返回复数Z的虚部值。Add(z1,z2,&sum)初始条件：z1,z2是复数。操作结果：用sum返回两个复数z1,z2 的 和值。ADT Complex第37页/共63页假设假设:z1和z2是上述定义的复数则 Add(z1,z2,z3)操作的结果z3=z1+z2即为用户所求的结果第38页/共63页ADT 有两个重要特征:数据抽象：数据抽象：用ADT描述程序处理的实体时，强调的是其本质的特征本质的特征、其所能完成的其所能完成的功能功能以及它和外部用户的接口外部用户的接口

18、（即外界外界使用它的方法使用它的方法）。数据封装：数据封装：将实体的外部特性和其内部外部特性和其内部实现细节分离实现细节分离，并且对外部用户隐藏对外部用户隐藏其内部实现细节。其内部实现细节。第39页/共63页vADT的表示和实现：的表示和实现：抽象数据类型需要通过固有数据固有数据类型类型(高级编程语言中已实现的数据类型)来实现。例如，对以上定义的复数。例如，对以上定义的复数。第40页/共63页typedef struct float realpart；float imagpart；complex；/-存储结构的定义存储结构的定义/-基本操作的函数原型说明基本操作的函数原型说明void Assi

19、gn(complex&Z,float realval,float imagval)；/构造复数 Z,其实部和虚部分别被赋以 /参数 realval 和 imagval 的值第41页/共63页float GetReal(complex Z)；/返回复数 Z 的实部值float Getimag(complex Z)；/返回复数 Z 的虚部值void add(complex z1,complex z2,complex&sum)；/以 sum 返回两个复数 z1,z2 的和 第42页/共63页/-基本操作的实现基本操作的实现void add(complex z1,complex z2,complex&

20、sum)/以 sum 返回两个复数 z1,z2 的和 sum.realpart=z1.realpart+z2.realpart;sum.imagpart=z1.imagpart+z2.imagpart;其它省略 第43页/共63页一、算法的定义一、算法的定义二、算法设计的原则二、算法设计的原则三、算法效率的衡量方法和准则三、算法效率的衡量方法和准则四、算法的存储空间需求四、算法的存储空间需求1.3 算法和算法和算法算法分析分析第44页/共63页 算法算法是对特定问题求解步骤的描求解步骤的描述述，是指令的有限序列。1.有穷性 2.确定性 3.可行性4.有输入 5.有输出一、算法的定义一、算法的定

21、义一个算法必须满足以下五五个重要特性个重要特性：第45页/共63页1.有穷性有穷性：对于任意一组合法输入值，在执行有穷步骤有穷步骤之后一定能结束，即算法中的每个步骤都能在有限时间有限时间内完成。2.2.确定性：确定性：对于每种情况每种情况下所应执行的操作，在算法中都有确切确切的规定，使算法的执行者或阅读者都能明确其含义及如何执行。并且并且在任何条件下，算法都只有一条在任何条件下，算法都只有一条执行路径。执行路径。第46页/共63页3.可行性：可行性：算法中的所有操作都必须足够基本，都可以通过已经实现的基本操作运算有限次实现之。4.有输入：有输入：有零个或多个输入，取自特定的对象集合。5.有输出

22、：有输出：有一个或多个输出，是算法进行信息加工后得到的结果。第47页/共63页二、算法设计的原则二、算法设计的原则 设计算法时，通常应考虑达到以下目标：1正确性正确性2.可读性可读性3健壮性健壮性4高效率与低存储量需求高效率与低存储量需求第48页/共63页1.1.正确性：正确性：在在合理合理的数据输入下，能在的数据输入下，能在有限的运算时间有限的运算时间内得到内得到正确结果正确结果。对算法是否对算法是否“正确正确”的理解可以有以下四个层次：的理解可以有以下四个层次：a a程序中不含语法错误；程序中不含语法错误；b b程序对于程序对于几组几组输入数据能够得出满足要求的输入数据能够得出满足要求的结

23、果；结果；c c程序对于程序对于精心选择的、典型、苛刻切带有刁精心选择的、典型、苛刻切带有刁难性难性的几组输入数据能够得出满足要求的结果；的几组输入数据能够得出满足要求的结果；d d程序对于程序对于一切合法一切合法的输入数据都能得出满足的输入数据都能得出满足要求的结果；要求的结果；第49页/共63页2.2.可读性：可读性：易于人对算法的理解；另一方面，晦涩难读的程序易于隐藏较多错误而难以调试；3.3.健壮性：健壮性：当输入的数据非法非法时，算法应当恰当地作出反映或进行相应处理进行相应处理，而不是产生莫名奇妙的输出结果。并且，处理处理出错的方法出错的方法不应是中断程序的执行，而应是返回返回一个表

24、示错误或错误性质的值表示错误或错误性质的值，以便在更高的抽象层次上进行处理。第50页/共63页4.高效率与低存储量需求：高效率与低存储量需求：效率效率指的是算法执行时间。存储量存储量指的是算法执行过程中所需的最大存储空间。两者都与问题的规模问题的规模有关。第51页/共63页有两种衡量算法效率的方法:1.事后统计法：利用计算机内记时功能，用一组或多组相同的统计数据区分。2.事前分析估计法：求出算法的一个时间界限函数。三三、算法效率的衡量方法和准则、算法效率的衡量方法和准则第52页/共63页和算法执行时间时间相关的因素因素：1 1算法算法选用的策略的策略2 2问题的规模问题的规模3 3编写程序的语

25、言语言4 4编译编译程序产生的机器代码的质量的质量5 5计算机计算机执行指令的速度的速度第53页/共63页 设解决一个问题的规模问题的规模为n，基本操基本操作作被重复执行的次数是f(n)。假如，随着问题规模 n 的增长，算算法执行时间的增长率和法执行时间的增长率和 f(n)的增长率相的增长率相同同，则可记作：T(n)=O(f(n)称称T(n)为算法的为算法的渐近时间复杂度，时间复杂度，简称简称时间复杂度时间复杂度。第54页/共63页算法算法 =控制结构控制结构 +原操作原操作 （固有数据类型的操作）算法的执行时间算法的执行时间=原操作原操作(i)(i)的执行次数的执行次数原操作原操作(i)(i

26、)的执行时间的执行时间如何估算算法的时间复杂度？如何估算算法的时间复杂度？第55页/共63页 从算法中选取一种对于所研究的问题来说是 基本操作基本操作 的原操作，以该基本操作 在算法中重复执行在算法中重复执行的次数的次数 作为算法运行时间的衡量准则。第56页/共63页void mult(int a,int b,int&c)/以二维数组存储矩阵元素，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 两个两个矩阵相乘

27、矩阵相乘第57页/共63页例例2 +x;s=0;T(n)=T(n)=(1)(1)T(n)=T(n)=O(n)O(n)(1)(log2n)(n)(n2)(n3)(2n)例例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)第58页/共63页 change=FALSE;/change 为元素进行交换标志 for(j=0;j aj+1)aj aj+1;change=TRUE;/一趟起泡void bubble_sort(int&a,int n)/将 a 中整数序列重新排列

28、成自小至大有序的整数序列。for(i=n-1,change=TRUE;i1&change;-i)/bubble_sort基本操作:交换操作时间复杂度:O(n2)例例5 5 起泡排序起泡排序第59页/共63页四、算法的存储空间需求四、算法的存储空间需求算法的空间复杂度空间复杂度:表示随着问题规模表示随着问题规模 n 的增大，算的增大，算法运行法运行所需存储量所需存储量的增长率与的增长率与 g(n)的增长率相同。的增长率相同。S(n)=O(g(n)第60页/共63页算法的存储量包括：算法的存储量包括：（1）输入数据输入数据所占空间；（2）程序本身程序本身所占空间；（3）辅助变量辅助变量所占空间。第61页/共63页 数据的逻辑结构数据的逻辑结构 数据的存储结构数据的存储结构 数据的运算：查找、排序、插入、删除、修改等数据的运算：查找、排序、插入、删除、修改等 线性结构线性结构 非线性结构非线性结构 顺序存储顺序存储 链式存储链式存储 线性表线性表栈和队列栈和队列串串树形结构树形结构图形结构图形结构数组和广义表数组和广义表数据结构的三个方面：数据结构的三个方面：第62页/共63页感谢您的观看。第63页/共63页