数据结构最全课件

数据结构与算法DataStructures讲课学时：42上机学时：20教学安排邮箱:hjh20070826@163.com教师:黄俊恒11.1什么是数据结构例1.1、煤气管道的铺设问题。在城市的各小区之间铺设煤气管道，共有4个小区，由于地理环境不同等因素使各条管线所需投资不同，如何使投资成本最低？abdc181819152025abdc181815abdc1815202数据结构:数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科。（P3）数据结构的三个层次：1、逻辑结构（问题的数学模型）2、存储结构3、建立在二者之上的基本运算1.1什么是数据结构3程序设计=数据结构+算法程序设计：为计算机处理问题编制的一组指令集算法：处理问题的策略**1.1什么是数据结构4教材情况1.《数据结构》严蔚敏等清华大学出版社2.《数据结构与算法》

廖明宏郭福顺等高等教育出版社前序课程后序课程5考试考核1.出勤与作业

每缺少一次扣3分,满三次扣10分,满四次取消考试资格。2.实验

占总成绩30%3.期末闭卷考试占总成绩70%***6第一章绪论1.1什么是数据结构1.2基本概念和术语1.3抽象数据类型的表示和实现1.4算法和算法分析71.数据数据是用于描述客观事物的符号表示，在计算机科学中指一切可以输入到计算机中的并由计算机程序处理的符号的集合。1.2基本概念和术语2.数据元素

数据的基本单位是数据元素，通常作为一个整体进行考虑和处理。一般由若干数据项组成。数据元素有时又称为结点、记录或表目。83.数据项是数据的不可分割的最小单位，一个数据元素可由若干个数据项组成。是对数据元素属性的描述。有时称域或字段。姓名性别年龄专业班级

数据项例如：学生(数据元素)1.2基本概念和术语94.数据对象性质相同的元素的集合叫做数据对象，是数据的子集。1.2基本概念和术语5、数据结构:

数据结构指的是数据元素之间的抽象的相互关系，是数据元素及其相互间的关系的数学描述。数据结构的三个层次：

(1)、逻辑结构（问题的数学模型）

(2)、存储结构

(3)、建立在二者之上的基本运算101.集合ABCD数据结构的四种基本结构2.线性结构ABCD例1-1图书检索（P1）3.树型结构ABCD例1-2人机对弈（P1）4.图状结构ABCD例1-3交通灯管理（P2）11数据结构的形式定义：DataStructure=(D,S)其中D是数据无素的集合，S是D上关系的集合。1.2基本概念和术语12数据结构:数据结构指的是数据元素之间的抽象的相互关系，是数据元素及其相互间的关系的数学描述。数据结构的三个层次：1、逻辑结构（问题的数学模型）2、存储结构3、建立在二者之上的基本运算1.2基本概念和术语132、存储结构（物理结构）数据结构包括结点的值及结点之间的关系。(1).顺序存储结构；(2).链接存储结构；(3).索引存储结构；(4).散列存储结构。1.2基本概念和术语146.数据类型是一个值的集合和定义在这个值的集合上的一组操作的总称。分为原子数据类型和结构数据类型。1.2基本概念和术语15抽象数据类型AbstractDataTypes(ADT)

ADT数据型是程序设计语言中数据类型概念的推广和抽象。例如：对一个线性表L，我们可以声明它的类型，数据元素的类型，定义它的有关操作：int=({x︱x∈Z},{+,-,*,/,%,≤,≥,==})表类型LIST，位置position,FIRST(),END(),NEXT(),SAME(),DELETE(),RETRIEVE().16例1.2编一个函数PURGE，删除线性表L中所有重复出现的元素。表类型LIST，位置position,FIRST(),END(),NEXT(),SAME(),DELETE(),RETRIEVE().抽象数据类型AbstractDataTypes(ADT)17voidPURGE(LISTL){positionp,q;p=FIRST(L);

while(p!=END(L)){q=NEXT(p,L);

while(q!=END(L))if(same(RETRIEVE(p,L),RETRIEVE(q,L)))

DELETE(q,L);elseq=NEXT(q,L);p=NEXT(p,L);}}抽象数据类型AbstractDataTypes(ADT)181、抽象数据型的定义

[定义]：抽象数据类型是指一个数学模型和定义在该模型上的一组操作。

ADT特点：使用者只要知道这些操作的用途就可以编程序了；至于这些操作是怎样实现的，以及内存中是如何表示的，并不影响使用者所编程序的编码形式。192、抽象数据类型的形式定义

抽象数据类型的形式定义可用三元组表示：

（D,S,P）

D是数据对象，S是D上的关系集，P是对D的基本操作集。

数据结构与抽象数据型的关系？

数据结构是抽象数据型中的数学模型，抽象数据型是数据结构加上一组操作。202、抽象数据类型的形式定义

该书对抽象数据型的抽述方式

ADT抽象数据类型名｛数据对象：<数据对象的定义>

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

基本操作：<基本操作的定义>

｝ADT抽象数据类型名21(1)预定义常量和类型

#defineTRUE1#defineFALSE0#defineOk1#defineERROR0#defineINFEASIBLE-1#defineOVERFLOW-2

typedef

intStatus;1.3抽象数据类型的表示与实现22(2)数据结构的表示（存储结构）用类型定义（typedef）描述，数据元素类型约定为ElemType,由用户使用该数据类型时自行定义。1.3抽象数据类型的表示与实现23(3)基本操作的算法都用以下形式的函数描述：函数类型函数名（参数表）｛

//算法说明语句序列｝//函数名1.3抽象数据类型的表示与实现241.3抽象数据类型的表示与实现(4)赋值语句有：简单赋值变量名=表达式；串联赋值变量1=变量2=…=变量k=表达式；成组赋值

(变量名1,…,变量名k)=(表达式1，…,表达式k）;

结构名=结构名；结构名=（值1，…,值k）;

变量名［］=表达式；变量名[起始下标..终止下标]=变量名[起始下标..终止下标]

交换赋值变量名←→变量名条件赋值变量名=条件表达式？表达式T：表达式F;251.3抽象数据类型的表示与实现(5)选择语句有：

if…elseswitch(6)循环语句有：

forwhiledowhile261.3抽象数据类型的表示与实现(7)结束语句有：

returnbreakexit(8)输入输出

scanf

printf271.3抽象数据类型的表示与实现(9)基本函数有

max(表达式1,…,表达式n)min(表达式1,…,表达式n)abs(表达式)floor(表达式)ceil(表达式)

eof(表达式)

eoln(表达式)281.3抽象数据类型的表示与实现(10)逻辑运算***抽象数据型的表示和实现包括数据模型的表示和在其上定义的各种操作的实现。291.4算法和算法分析1.4.1算法算法（Algorithm）：是对特定问题求解步骤的一种描述，它是指令（规则）的有限序列，其中每一条指令表示一个或多个操作。算法的特征：①输入、②输出、③确定性、④有穷性、⑤可行性。算法与程序的区别？程序不一定满足有穷性。301.4.2、算法设计的要求

1、正确性(Correctness)2、可读性(readability)3、健壮性(robustness)4、效率与低存储量的要求。

（时间复杂性与空间复杂性）

1.4算法和算法分析31

算法的时间复杂性

(TimeComplexity)

（1）事后统计的方法（2）事前分析估算的方法一个用高级程序语言编写的程序在计算机上运行时所消耗的时间取决于下列因素。

①依据算法选用的何种策略;②问题的规模③所用语言④编译程序产生的机器代码的质量⑤机器执行指令的速度1.4.3算法效率的度量32

1、算法的时间复杂性

(TimeComplexity)

把算法的基本操作的重复执行的次数作为算法的时间度量。1.4.3算法效率的度量33

2.空间复杂性(SpaceComplexity)

算法的空间复杂性是指算法在执行过程中的存储量需求；

一个算法的存储量需求除了存放算法本身所有的指令、常数、变量和输入数据外，还包括对数据进行操作的工作单元和存储实现计算所需信息的辅助空间；一般指辅助空间所占的存储空间。1.4算法及其性能评价准则34例1.3两个n×n的矩阵相乘。其中矩阵的“阶”n为问题的规模。

voidMATRIXMLT(int

A[][n],

int

B[][n],int

C[][n])

{int

i,j,k;

for(i=0;i<n;i++)(1)

for(j=0;j<n;j++)(2){C[i][j]=0;(3)

for(k=0;k<n;k++)(4)

C[i][j]+=A[i][k]*B[k][j];(5)

}}1.4算法时间复杂性分析方法35

T(n)=2n3+3n2+2n+1

当n趋于无穷大时，T(n)与n3是同阶的，我们称为T(n)与n3的数量级相同，可记作：T(n)=O(n3)。1.4算法时间复杂性分析方法36

渐近时间复杂度表示法

(1)O()表示法：

若T(n)和f(n)是定义在正整数集合上的两个函数，当存在两个正常数c和n0时，使得对所有的n≥n0,都有T(n)≤c×f(n)成立，则T(n)=O(f(n))

渐近紧密上限1.4算法时间复杂性分析方法37

(2)

()表示法：

若T(n)和f(n)是定义在正整数集合上的两个函数，当存在两个正常数c和n0时，使得对所有的n≥n0,都有T(n)≥c×f(n)成立，则T(n)=

(f(n))

渐近紧密下限1.4算法时间复杂性分析方法38

(3)

()表示法：

若T(n)和f(n)是定义在正整数集合上的两个函数，当存在正常数c、d和n0时，使得对所有的n≥n0,都有c×f(n)≤T(n)≤d×f(n)成立，则T(n)=

(f(n))

渐近紧密限度1.4算法时间复杂性分析方法39常数阶对数阶线性阶线性对数阶平方阶立方阶………K次方阶指数阶指数时间的关系为：

O(2n)<O(n!)<O(nn)1.4算法时间复杂性分析方法40最坏时间复杂度平均时间复杂度序号姓名电话号码1张一...2…...3李一...4张三...5…...6…............n王五...查找成功的平均时间复杂度为O(n);查找不成功的时间复杂度为O(n)。1.4算法时间复杂性分析方法最好时间复杂度41例