数据结构绪论--课件

数据结构数据结构1ppt课件23 六月六月 2024第一章第一章 绪论绪论基本概念和术语基本概念和术语1算法的表示与分析算法的表示与分析222ppt课件23 六月六月 20241.1 1.1 什么是数据结构什么是数据结构Q1如何采用计算机解决问题？Q2数据结构解决什么样的问题？Q3数据结构课程介绍33ppt课件23 六月六月 20241.1 1.1 什么是数据结构什么是数据结构Q1：如何采用计算机解决问题？答：寻求数学模型的实质：分析问题，从中提取操作的对象，并找出这些操作对象之间含有的关系，然后用数学的语言加以描述。(2)设计解此数学模型的算法；(1)从具体问题抽象出一个适当的数学模型；(3)编程，测试、调整直至得到最终解答。44ppt课件23 六月六月 20241.1 1.1 什么是数据结构什么是数据结构Q2：数据结构解决什么样的问题？答：数据结构研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科。55ppt课件23 六月六月 20241.1 1.1 什么是数据结构什么是数据结构Q3：数据结构数据结构课程介绍课程介绍介于数学、计算机硬件和计算机软件三者之间的一门核心课程6关系对象关系操作数学软件硬件对象关系操作6ppt课件23 六月六月 20241.1 1.1 什么是数据结构什么是数据结构算法算法+数据结构数据结构程序程序处理问题的策略处理问题的策略问题的数学模型问题的数学模型用计算机解决问题的一般步骤：用计算机解决问题的一般步骤：寻求一个适当的数学模型寻求一个适当的数学模型 设计一个解决问题的算法设计一个解决问题的算法 编写代码，调试直至得到解答编写代码，调试直至得到解答77ppt课件23 六月六月 2024【例例1 1】数据管理问题数据管理问题线性问题线性问题1.1 1.1 什么是数据结构什么是数据结构88ppt课件23 六月六月 2024【例例2 2】棋类对弈问题棋类对弈问题树型结构树型结构1.1 1.1 什么是数据结构什么是数据结构99ppt课件23 六月六月 2024【例例3 3】交通、道路等问题交通、道路等问题图型图型1.1 1.1 什么是数据结构什么是数据结构1010ppt课件23 六月六月 20241.2 1.2 基本概念与术语基本概念与术语Q1 什么是数据结构？什么是数据结构？Q2 数据结构涵盖的主要内容？数据结构涵盖的主要内容？Q3 学习数据结构有什么用？学习数据结构有什么用？1111ppt课件23 六月六月 2024答答:(见见教教材材P5)是是相相互互之之间间存存在在一一种种或或多多种种特特定定关系关系的的数据元素数据元素的集合，表示为：的集合，表示为：（数值或非数值）Data_Structure=（D,S）或：是指同一数据元素类中各元素之间存在的关系。或：是指同一数据元素类中各元素之间存在的关系。元素有限集元素有限集关系有限集关系有限集1.2 1.2 基本概念与术语基本概念与术语1 1 基本概念和术语基本概念和术语Q1：什么是数据结构？什么是数据结构？1212ppt课件23 六月六月 20241 1 基本概念和术语基本概念和术语1.2 1.2 基本概念与术语基本概念与术语术语：术语：数据、数据元素和数据项数据、数据元素和数据项（见教材见教材P4定义定义）：）：数数据据(data)所所有有能能被被计计算算机机识识别别、存存储储和和处处理理的的符符号号的的集合（集合（包括数字、字符、声音、图像等信息包括数字、字符、声音、图像等信息）。）。数数据据元元素素(data element)是是数数据据的的基基本本单单位位，具具有有完完整整确确定定的的实实际际意意义义(又又称称元元素素、结结点点，顶顶点点、记记录录等等）。数数据据项项(Data item)构构成成数数据据元元素素的的项项目目。是是具具有有独独立立含义的含义的最小最小标识单位（标识单位（又称字段、域、属性又称字段、域、属性 等等）。）。三者之间的关系：数据 数据元素 数据项例：例：班级通讯录班级通讯录 个人记录个人记录 姓名、年龄姓名、年龄1313ppt课件23 六月六月 2024Q2：数据结构涵盖的内容？数据结构涵盖的内容？数据结构定义数据关系和组织数据结构定义数据关系和组织结构，主要包含三部分内容：结构，主要包含三部分内容：v 逻辑结构逻辑结构v 存储结构存储结构v 基本操作（运算）基本操作（运算）逻辑结构唯一逻辑结构唯一存储结构不唯一存储结构不唯一运算的实现依赖运算的实现依赖于存储结构于存储结构1.2 1.2 基本概念与术语基本概念与术语1414ppt课件23 六月六月 20241 1 基本概念和术语基本概念和术语v 逻辑结构逻辑结构指数据元素之间的逻辑关系。即从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。S=D,R D表示数据元素的集合，表示数据元素的集合，R表示元素间关系的集合表示元素间关系的集合如：如：S=D,R,D=a,b,c,d,e,f,gR1=R2=,R3=,R4=,1.2 1.2 基本概念与术语基本概念与术语逻辑结构可细分为逻辑结构可细分为4类：类：1515ppt课件23 六月六月 2024abcefgS1-集合集合S2线性结构线性结构abcdefga ab bc cd de ef fg gS3树型结构树型结构S4图形结构图形结构1.2 1.2 基本概念与术语基本概念与术语a ab bc ce ef fg g仅同属一个集合一对一（1:1)一对多（1:n)多对多(m:n)1616ppt课件例：用图形表示下列数据结构，并指出它例：用图形表示下列数据结构，并指出它们是属于线性结们是属于线性结构还是非线性结构。构还是非线性结构。（1）S=(D,R)D=a,b,c,d,e,fR=(a,e),(b,c),(c,a),(e,f),(f,d)解：解：上述表达式可用图形表示为：上述表达式可用图形表示为：b c a e f d此结构为线性的。23 六月六月 20241717ppt课件（2）S=(D,R)D=di|1i5R=(di,dj),ij d1 d5 d2 d4 d3该结构是非线性的。解：上述表达式可用图形表示为：23 六月六月 20241818ppt课件23 六月六月 2024v 存储结构存储结构:数据的逻辑结构在计算机中的表示。包括数据的逻辑结构在计算机中的表示。包括两个方面：数据元素的表示及元素之间关系的表示。两个方面：数据元素的表示及元素之间关系的表示。1 1 基本概念和术语基本概念和术语1.2 1.2 基本概念与术语基本概念与术语存储结构可分为4大类：例：（见教材P6）复数3.02.3i 的两种存储方式：顺序、链式、索引、散列2.303023.00300041503023.0030004152.3法法1：地址地址 内容内容法法2：地址地址 内容内容2字节字节1919ppt课件23 六月六月 2024基本操作及其实现：在数据的逻辑结构上定义的操作算法。它在数据的存储结构上实现。最常用的数据运算有5种：插入、删除、修改、查找、排序。因此，完整的数据结构概念应该由逻辑结构、存储结构和基本操作三个部分所构成。1 1 基本概念和术语基本概念和术语1.2 1.2 基本概念与术语基本概念与术语2020ppt课件23 六月六月 20241.3 1.3 抽象数据类型的表示和实现抽象数据类型的表示和实现Q1数据类型与抽象数据类型的区别？Q2抽象数据类型如何定义？Q3抽象数据类型如何表示和实现？提示：教材中例1-6和例1-7分别给出了抽象数据类型“三元组”的定义、表示和实现，请试阅读。2121ppt课件23 六月六月 2024Q1 数据类型与抽象数据类型的区别？数据类型与抽象数据类型的区别？数据类型：是一个值的集合和定义在该值上 的一组操作的总称。抽象数据类型：由用户定义的一个数学模型以及在该模型上的一组操作。它与数据类型实质上是一个概念，但其特征是使用与实现分离，实行封装和信息隐蔽（独立于计算机）。221.3 1.3 抽象数据类型的表示和实现抽象数据类型的表示和实现22ppt课件23 六月六月 2024Q2 抽象数据类型如何抽象数据类型如何定义定义？抽象数据类型可以用以下的三元组来表示：ADT=（D，S，P）数据对象 D上的关系集 D上的操作集 ADT抽象数据类型名 数据对象：数据关系：基本操作：ADT抽象数据类型名ADT常用定义格式231.3 1.3 抽象数据类型的表示和实现抽象数据类型的表示和实现23ppt课件23 六月六月 2024例：例：给出自然数给出自然数(Natural Number)的抽象数据类型定义的抽象数据类型定义。ADT Natural_Number isobjects:一个整数的有序子集合，它开始于0，结束于机器能表示的最大整数(MAX INT)functions:对于所有的 x,y Natural_Number；TRUE,FALSE Boolean；+,-,=,=等都是可用的服务。Zero()Zero()：Natural Number Natural Number 返回返回 0 0IsZero(x)IsZero(x)：Boolean if(x=0)Boolean if(x=0)返回返回TRUETRUE else else 返回返回 FALSEFALSEAdd(x,y)Add(x,y)：Natural Number Natural Number if(x+y=MAX INT)if(x+y=MAX INT)返回返回 x+yx+y else else 返回返回MAX INTMAX INTSubtract(x,y):Natural NumberNatural Number if(xy)返回返回0 else 返回返回x-yEqual(x,y):Boolean Equal(x,y):Boolean if(x=y)if(x=y)返回返回TRUE else TRUE else 返回返回FALSEFALSESuccessor(x):Natural NumberNatural Number if(x=MAX INT)返回返回x else 返回返回x+1end Natural_Number 241.3 1.3 抽象数据类型的表示和实现抽象数据类型的表示和实现24ppt课件23 六月六月 2024Q3 抽象数据类型如何抽象数据类型如何表示和实现表示和实现？抽象数据类型可以通过抽象数据类型可以通过固有的固有的数据类型数据类型（如整型、实型、字符型等）来表示和实现。（如整型、实型、字符型等）来表示和实现。即利用处理器中已存在的数据类型来说明新的结构，即利用处理器中已存在的数据类型来说明新的结构，用已经实现的操作来组合新的操作。用已经实现的操作来组合新的操作。注：教材中用的是类C语言（介于伪码和C语言之间）作为描述工具。其描述语法见P10-11。但上机时要用具体语言实现，如C或C+等251.3 1.3 抽象数据类型的表示和实现抽象数据类型的表示和实现25ppt课件23 六月六月 2024Q1.什么是算法？什么是算法？Q2.算法设计的要求算法设计的要求？Q3.时间复杂度如何表示？时间复杂度如何表示？Q4.空间复杂度如何表示？空间复杂度如何表示？1.4 1.4 算法和算法分析算法和算法分析2626ppt课件23 六月六月 20241.4 1.4 算法和算法分析算法和算法分析1 1 算法：对特定问题求解步骤的一种描述，是指令的有限序列。算法：对特定问题求解步骤的一种描述，是指令的有限序列。有穷性（在有限的时间内结束）有穷性（在有限的时间内结束）确定性（每一步具有明确的含义）确定性（每一步具有明确的含义）可行性（可读，可理解，可执行）可行性（可读，可理解，可执行）输入（零个或多个输入）输入（零个或多个输入）输出（一个或多个输出）输出（一个或多个输出）(1)(1)开始开始开始开始(2)n=0(2)n5 ti t i1i ENDDO PRINT tENDint main()int i,t;i=2,t=1;while(i=n0时，都时，都满足：满足：1.4 1.4 算法和算法分析算法和算法分析Q3.时间复杂度如何表示？3131ppt课件23 六月六月 2024temp=i;temp=i;i=j;i=j;j=temp;j=temp;分析算法时间复杂度（分析算法时间复杂度（1 1）上面程序段的执行时间是与问题规模上面程序段的执行时间是与问题规模n无关的常数。因无关的常数。因此算法的时间复杂度为此算法的时间复杂度为常数阶常数阶，记做，记做T(n)=O(1)。若。若算法的执行时间不随问题规模算法的执行时间不随问题规模n的增加而增加，则即使的增加而增加，则即使算法中有成千条语句，其执行时间也是一个常数。其时算法中有成千条语句，其执行时间也是一个常数。其时间复杂度为间复杂度为O(1)。(1)(1)1 1次次(2)(2)1 1次次(3)(3)1 1次次总执行频度为总执行频度为3 31.4 1.4 算法和算法分析算法和算法分析3232ppt课件23 六月六月 2024s=0;for(i=0;in;i+)s=s+i;分析算法时间复杂度（分析算法时间复杂度（2 2）因此因此T(n)=2n+2=O(n)。上面算法的时间复杂度为。上面算法的时间复杂度为O(n)。(1)(1)1 1次次(2)(2)n+1n+1次次(3)(3)n n次次总执行频度为总执行频度为2n+22n+21.4 1.4 算法描述与分析算法描述与分析3333ppt课件23 六月六月 2024for(i=0;in;i+)for(i=0;in;i+)for(j=0;jn;j+)for(j=0;jn;j+)s=i*j;s=i*j;分析算法时间复杂度（分析算法时间复杂度（3 3）因此因此T(n)=n2+2n+2=O(n2)。上面算法的时间复杂度为。上面算法的时间复杂度为O(n2)。(1)(1)n+1n+1次次(2)(2)n+1n+1次次(3)(3)n*nn*n次次总执行频度为总执行频度为n n2 2+2n+2+2n+2一般地，算法中的基本操作可以理解为算法程序中最深层循一般地，算法中的基本操作可以理解为算法程序中最深层循环内的语句的基本操作。环内的语句的基本操作。1.4 1.4 算法和算法分析算法和算法分析3434ppt课件23 六月六月 20241.4 1.4 算法和算法分析算法和算法分析算法的时间复杂度有多种表现形式：算法的时间复杂度有多种表现形式：（1）常量时间）常量时间O(1)（2）线性时间）线性时间O(N)（3）平方时间）平方时间O(N2)（4）立方时间）立方时间O(N3)（5）对数时间）对数时间O(logN)（6）指数时间）指数时间O(2N)当当N充分大时，关系如下：充分大时，关系如下：O(1)O(logN)O(N)O(N2)O(N3)O(2N)3535ppt课件23 六月六月 2024渐进符号渐进符号（O）的定义：）的定义：当且仅当存在一个正的常数当且仅当存在一个正的常数 C C，使得对，使得对所有的所有的 n n n n0 0 ，有，有 f(n)f(n)C Cg(n)g(n)，则则f(n)=f(n)=O O(g(n)(g(n)3n+2=O(n)/*3n+2 4n for n 2*/3n+3=O(n)/*3n+3 4n for n 3*/100n+6=O(n)/*100n+6 101n for n 10*/10n2+4n+2=O(n2)/*10n2+4n+2 11n2 for n 5*/6*2n+n2=O(2n)/*6*2n+n2 7*2n for n 4*/例：3636ppt课件23 六月六月 20241.4 1.4 算法和算法分析算法和算法分析例例1：分析：分析N!的递归算法的时间复杂度。的递归算法的时间复杂度。int fact(int n)if(n=1)return 1;else return(n*fact(n-1);T(n)=O(n)3737ppt课件23 六月六月 20241.4 1.4 算法和算法分析算法和算法分析例例2：分析时间复杂度。：分析时间复杂度。i=1;while(i=n)i=i*5;语句频度语句频度O(1)语句频度语句频度f(x)O(log5n)3838ppt课件23 六月六月 2024v 空间复杂度：算法执行过程对存储空间的需求。空间复杂度：算法执行过程对存储空间的需求。S(n)=O(f(n)通常算法执行时除了存放指令、常量、变量、输出数据等，通常算法执行时除了存放指令、常量、变量、输出数据等，还需要一些辅助空间来对数据进行处理和存储中间信息。还需要一些辅助空间来对数据进行处理和存储中间信息。一般的，空间复杂度指的是对这种辅助空间的需求。一般的，空间复杂度指的是对这种辅助空间的需求。1.3 1.3 算法和算法分析算法和算法分析Q4.空间复杂度如何表示？3939ppt课件40复习复习 C C语言语言数据类型 C语言为什么要有数据类型？运算符与表达式 赋值表达式左边和右边的变量所代表的意义？流程控制：顺序、选择、循环函数、函数参数传递、递归调用数组、结构体、指针文件/数据库23 六月六月 202440ppt课件41结构体结构体：若一个数据元素可以由若干个数据项组成。C语言允许用户自己指定这样一种数据结构，它称为结构体(structure)。用户必须要在程序中建立所需的结构体类型。例如：用户必须要在程序中建立所需的结构体类型。例如：structstudent int num；charname20；charsex；intage；floatscore；charaddr30；typedef的用法23 六月六月 202441ppt课件指针：是C语言中的一个重要的概念，可以说，不掌握指针就是没有掌握C的精华。地址：内存区的每一个字节有一个编号，这就是“地址”，它相当于旅馆中的房间号。指针：一个变量的地址称为该变量的“指针”。如果有一个变量专门来存放另一个变量的地址（指针）就称为指针变量。相当于存放在总台的每个房间钥匙。指针23 六月六月 20244242ppt课件23 六月六月 202443int i;int*i_pointer;i=3i_pointer=&i2000i2000i_pointer50803指针43ppt课件23 六月六月 2024小结小结 数据结构是由若干特性相同的数据元素构成的集合，且在集合上存在一种或多种关系。抽象数据类型的三大要素为数据对象、数据关系和基本操作，同时数据抽象和数据封装是抽象数据类型的两个重要特性。算法及算法时间复杂度的衡量 4444ppt课件23 六月六月 2024作业：作业：1.思考思考:数据结构、数据类型、抽象数据类型的区别数据结构、数据类型、抽象数据类型的区别 算法与程序的区别算法与程序的区别2.请试做配套习题集请试做配套习题集(P10_16)。3.复习复习C/C+语言。语言。4545ppt课件