数据结构绪论-课件

数据结构1ppt课件22七月2023第一章绪论基本概念和术语1算法的表示与分析222ppt课件22七月20231.1什么是数据结构Q1如何采用计算机解决问题？Q2数据结构解决什么样的问题？Q3《数据结构》课程介绍33ppt课件22七月20231.1什么是数据结构Q1：如何采用计算机解决问题？答：寻求数学模型的实质：

分析问题，从中提取操作的对象，并找出这些操作对象之间含有的关系，然后用数学的语言加以描述。(2)设计解此数学模型的算法；(1)从具体问题抽象出一个适当的数学模型；(3)编程，测试、调整直至得到最终解答。44ppt课件22七月20231.1什么是数据结构Q2：数据结构解决什么样的问题？答：

数据结构研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科。55ppt课件22七月20231.1什么是数据结构Q3：《数据结构》课程介绍

介于数学、计算机硬件和计算机软件三者之间的一门核心课程6关系对象关系操作数学软件硬件对象关系操作6ppt课件22七月20231.1什么是数据结构算法+数据结构＝程序处理问题的策略问题的数学模型用计算机解决问题的一般步骤：寻求一个适当的数学模型设计一个解决问题的算法编写代码，调试直至得到解答77ppt课件22七月2023【例1】数据管理问题—线性问题1.1什么是数据结构88ppt课件22七月2023【例2】棋类对弈问题—树型结构1.1什么是数据结构99ppt课件22七月2023【例3】交通、道路等问题—图型1.1什么是数据结构1010ppt课件22七月20231.2基本概念与术语Q1什么是数据结构？Q2数据结构涵盖的主要内容？Q3学习数据结构有什么用？1111ppt课件22七月2023答:(见教材P5)是相互之间存在一种或多种特定关系的数据元素的集合，表示为：（数值或非数值）Data_Structure=（D,S）或：是指同一数据元素类中各元素之间存在的关系。元素有限集关系有限集1.2基本概念与术语1基本概念和术语Q1：什么是数据结构？1212ppt课件22七月20231基本概念和术语1.2基本概念与术语术语：数据、数据元素和数据项（见教材P4定义）：数据(data)——所有能被计算机识别、存储和处理的符号的集合（包括数字、字符、声音、图像等信息）。数据元素(dataelement)——是数据的基本单位，具有完整确定的实际意义(又称元素、结点，顶点、记录等）。数据项(Dataitem)——构成数据元素的项目。是具有独立含义的最小标识单位（又称字段、域、属性等）。三者之间的关系：数据>数据元素>数据项例：班级通讯录>个人记录>姓名、年龄……1313ppt课件22七月2023Q2：数据结构涵盖的内容？数据结构定义数据关系和组织结构，主要包含三部分内容：逻辑结构存储结构基本操作（运算）逻辑结构唯一存储结构不唯一运算的实现依赖于存储结构1.2基本概念与术语1414ppt课件22七月20231基本概念和术语

逻辑结构指数据元素之间的逻辑关系。即从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。

S={D,R}

D表示数据元素的集合，R表示元素间关系的集合如：S={D,R},D={a,b,c,d,e,f,g} R1={φ} R2={<a,b>,<b,c>,<c,d>,<d,e>,<e,f>,<f,g>} R3={<a,b>,<a,c>,<a,d>,<b,e>,<b,f>,<c,g>} R4={<a,e>,<b,c>,<c,a>,<e,f>,<f,g>,<c,f>}1.2基本概念与术语逻辑结构可细分为4类：1515ppt课件22七月2023abcefgS1-集合S2－线性结构abcdefgabcdefgS3－树型结构S4－图形结构1.2基本概念与术语abcefg仅同属一个集合一对一（1:1)一对多（1:n)多对多(m:n)1616ppt课件例：用图形表示下列数据结构，并指出它们是属于线性结构还是非线性结构。（1）S=(D,R)D={a,b,c,d,e,f}R={(a,e),(b,c),(c,a),(e,f),(f,d)}解：上述表达式可用图形表示为：bcaefd此结构为线性的。22七月20231717ppt课件（2）S=(D,R)

D={di|1≤i≤5}

R={(di,dj),i<j}d1d5d2

d4d3该结构是非线性的。解：上述表达式可用图形表示为：22七月20231818ppt课件22七月2023

存储结构:数据的逻辑结构在计算机中的表示。包括两个方面：数据元素的表示及元素之间关系的表示。1基本概念和术语1.2基本概念与术语存储结构可分为4大类：例：（见教材P6）复数3.0－2.3i的两种存储方式：顺序、链式、索引、散列－2.303023.00300041503023.003000415－2.3法1：地址内容法2：地址内容2字节1919ppt课件22七月2023基本操作及其实现：在数据的逻辑结构上定义的操作算法。它在数据的存储结构上实现。最常用的数据运算有5种：插入、删除、修改、查找、排序。因此，完整的数据结构概念应该由逻辑结构、存储结构和基本操作三个部分所构成。1基本概念和术语1.2基本概念与术语2020ppt课件22七月20231.3抽象数据类型的表示和实现Q1数据类型与抽象数据类型的区别？Q2抽象数据类型如何定义？Q3抽象数据类型如何表示和实现？

提示：教材中例1-6和例1-7分别给出了抽象数据类型“三元组”的定义、表示和实现，请试阅读。2121ppt课件22七月2023Q1数据类型与抽象数据类型的区别？数据类型：是一个值的集合和定义在该值上的一组操作的总称。抽象数据类型：由用户定义的一个数学模型以及在该模型上的一组操作。它与数据类型实质上是一个概念，但其特征是使用与实现分离，实行封装和信息隐蔽（独立于计算机）。221.3抽象数据类型的表示和实现22ppt课件22七月2023Q2抽象数据类型如何定义？抽象数据类型可以用以下的三元组来表示：

ADT=（D，S，P）数据对象D上的关系集D上的操作集ADT抽象数据类型名{

数据对象：<数据对象的定义>

数据关系：<数据关系的定义>

基本操作：<基本操作的定义>}ADT抽象数据类型名ADT常用定义格式231.3抽象数据类型的表示和实现23ppt课件22七月2023例：给出自然数(NaturalNumber

)的抽象数据类型定义。ADT

Natural_Number

isobjects:

一个整数的有序子集合，它开始于0，结束于机器能表示的最大整数(MAXINT)functions:

对于所有的x,yNatural_Number；TRUE,FALSEBoolean；

+,-,<,==,=等都是可用的服务。Zero()：NaturalNumber返回0IsZero(x)：Booleanif(x==0)返回TRUE

else返回FALSEAdd(x,y)：NaturalNumber if(x+y<=MAXINT)返回x+yelse返回MAXINTSubtract(x,y):NaturalNumber if(x<y)返回0else返回x-yEqual(x,y):Boolean if(x==y)返回TRUEelse返回FALSESuccessor(x):NaturalNumberif(x==MAXINT)返回xelse返回x+1end

Natural_Number

241.3抽象数据类型的表示和实现24ppt课件22七月2023Q3抽象数据类型如何表示和实现？

抽象数据类型可以通过固有的数据类型（如整型、实型、字符型等）来表示和实现。即利用处理器中已存在的数据类型来说明新的结构，用已经实现的操作来组合新的操作。注：教材中用的是类C语言（介于伪码和C语言之间）作为描述工具。其描述语法见P10-11。但上机时要用具体语言实现，如C或C++等251.3抽象数据类型的表示和实现25ppt课件22七月2023Q1.什么是算法？Q2.算法设计的要求？Q3.时间复杂度如何表示？Q4.空间复杂度如何表示？1.4算法和算法分析2626ppt课件22七月20231.4算法和算法分析1算法：对特定问题求解步骤的一种描述，是指令的有限序列。

有穷性（在有限的时间内结束）确定性（每一步具有明确的含义）可行性（可读，可理解，可执行）输入（零个或多个输入）输出（一个或多个输出）(1)开始(2)n<=0(3)n=n+1(4)重复(3)(5)结束算法？27Q1.

什么是算法？27ppt课件22七月2023算法和程序的主要区别：程序是用某种程序设计语言所书写的一个计算过程。而算法并不一定表现为一个计算机程序。它可以用不同方式和不同语言来描述。BEGIN1t2iDOUNTILi>5t×iti＋1iENDDOPRINTtENDintmain(){ inti,t; i=2,t=1; while(i<=5){ t=t×i; i++; } printf(“%d\n”,t); return0;}算法程序1.4算法和算法分析2828ppt课件22七月20231.4算法和算法分析2算法描述对于一个实际问题，分析采用适合的数学模型，选择合适的数据结构，将求解过程和步骤完整、准确地描述出来。自然语言描述伪码表示流程图表示

N-S图表示程序设计语言表示2929ppt课件22七月20233算法分析研究和比较各种算法的性能和优劣。

算法的衡量标准正确性（无语法错误，对于合法的数据输入能够得到正确的输出结果）可读性健壮性（对于非法的数据输入能够给出相应的反应）时间效率和存储需求1.4算法和算法分析Q2.

算法设计的要求？3030ppt课件22七月20233算法分析算法分析方法算法分析的两个主要方面时间复杂度：算法对时间的需求。

T(n)=O(f(n))n:表示问题的规模。f(n):表示基本操作执行的次数是问题规模n的某个函数。O表示T(n)的量级。严格的数学定义为，T(n)和f(n)是定义在正整数集合上的两个函数，则存在正的常数C和n0，使得当n>=n0时，都满足：1.4算法和算法分析Q3.

时间复杂度如何表示？3131ppt课件22七月2023temp=i;i=j;j=temp;分析算法时间复杂度（1）上面程序段的执行时间是与问题规模n无关的常数。因此算法的时间复杂度为常数阶，记做T(n)=O(1)。若算法的执行时间不随问题规模n的增加而增加，则即使算法中有成千条语句，其执行时间也是一个常数。其时间复杂度为O(1)。1次1次1次总执行频度为31.4算法和算法分析3232ppt课件22七月2023s=0;for(i=0;i<n;i++) s=s+i;分析算法时间复杂度（2）因此T(n)=2n+2=O(n)。上面算法的时间复杂度为O(n)。1次n+1次n次总执行频度为2n+21.4算法描述与分析3333ppt课件22七月2023for(i=0;i<n;i++) for(j=0;j<n;j++) s=i*j;分析算法时间复杂度（3）因此T(n)=n2+2n+2=O(n2)。上面算法的时间复杂度为O(n2)。n+1次n+1次n*n次总执行频度为n2+2n+2一般地，算法中的基本操作可以理解为算法程序中最深层循环内的语句的基本操作。1.4算法和算法分析3434ppt课件22七月20231.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课件22七月2023渐进符号（O）的定义：当且仅当存在一个正的常数

C，使得对所有的

nn0

，有f(n)Cg(n)，则f(n)=O(g(n))

3n+2=O(n)/*3n+24nforn2*/3n+3=O(n)/*3n+34nforn3*/100n+6=O(n) /*100n+6101nforn10*/10n2+4n+2=O(n2)/*10n2+4n+211n2forn5*/6*2n+n2=O(2n) /*6*2n+n27*2nforn4*/例：3636ppt课件22七月20231.4算法和算法分析例1：分析N!的递归算法的时间复杂度。intfact(intn){ if(n<=1)return1; elsereturn(n*fact(n-1));}T(n)=O(n)3737ppt课件22七月20231.4算法和算法分析例2：分析时间复杂度。

i=1; while(i<=n) i=i*5;语句频度O(1)语句频度f(x)O(log5n)3838ppt课件22七月2023

空间复杂度：算法执行过程对存储空间的需求。

S(n)=O(f(n))通常算法执行时除了存放指令、常量、变量、输出数据等，还需要一些辅助空间来对数据进行处理和存储中间信息。一般的，空间复杂度指的是对这种辅助空间的需求。1.3算法和算法分析Q4.

空间复杂度如何表示？3939ppt课件40复习C语言数据类型C语言为什么要有数据类型？运算符与表达式赋值表达式左边和右边的变量所代表的意义？流程控制：顺序、选择、循环函数、函数参数传递、递归调用数组、结构体、指针文件/数据库22七月202340ppt课件41结构体结构体：