数据结构高课件_第1页
数据结构高课件_第2页
数据结构高课件_第3页
数据结构高课件_第4页
数据结构高课件_第5页
已阅读5页,还剩62页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

1数据结构北京理工大学高春晓上课时间及安排2¤

《数据结构》上课时间(5-18周)¤

星期一,3/4节¤

星期三,1/2节¤

良乡1-506¤

学时安排¤

课堂教学:40学时¤

上机实验:16学时¤

主讲教师:高春晓¤¤

中心教学楼917室教材和参考资料3¤

教材¶

《数据结构(

C语言版)》——严蔚敏,吴伟民.清华大学出版社¤

参考书¶

《数据结构C++语言描述》——刘卫东,沈官林译.清华大学出版社¶

《数据结构与算法》——张铭,王腾蛟,赵海燕编.高等教育出版社¤

习题参考¶

数据结构题集(

C语言版)——严蔚敏,吴伟民.清华大学出版社4第一章绪论ListofContents5¤

1.1¤

1.2¤

1.3数据结构的定义基本概念算法和算法的量度1.1

数据结构的定义计算机程序处理输入数据输入结果计算机处理数学模型6算法程序用计算机解决问题的过程(程序设计)程序设计:为计算机处理问题编制一组指令集算法:处理问题的策略数据结构:数据的组织与操作数据处理7¤

Niklaus

Wirth:¶

Algorithm

+

Data

Structures

=

Programs¤

处理数据的种类和能力数字(整数,实数)字符、文字、图形、图象、声音¤

计算机应用数值领域非数值领域数值计算问题举例¤

数值计算的程序设计问题¶

例1:物体从100米高的塔顶落到地面的时间——二次方程¶

例2:结构静力分析计算——线性代数方程组¤

建模:¶

涉及对象:高度h,时间t,重力加速度g

(g=9.8)象之间的关系:h=½gt2求解问题的方法:t=sqrt(2h/g)¶

对¤

设计¤

编程:main

()8{float

t,

h

,

g

;

g=9.8;scanf

(”%f”,

&h);t

=

aqrt(2*h/g);printf

(”The

falling

time

is

%f\n”,

t);}非数值计算的程序设计问题11最¤

编模:涉及对象:5个整数对象之间的关系:大小关系计求解问题的方法:基本操作是“比较两个数的大小”首先将第一个数记为当前最大值,然后依次比较其余n-个整数,如果该某个整数大于当前最大值,就更新当前大值。程:¤

例1:求一组整数(5个)中的最大值¤

建main()9¶¶

设¶¶int

d[5],

i,

max;for(

i=0;

i<5;

i++)scanf

(”%d”,

&d[i]);max

=

d[0];for(

i=1;

i<5;

i++)if

(

max

<

d[i])

max

=

d[i];printf

(”The

max

number

is

%f\n”,

max);}非数值计算的程序设计问题210¤

例2

已知研究生的选课情况,试设计安排课程的考试日程的程序。

要求在尽可能短的时间内完成考试。ABCDEF算法分析形式语言计算机图形学模式识别网络技术人工智能杨润生石磊魏庆涛马耀先齐砚生选修1ACCDB选修2BDEFF选修3EFA非数值计算问题举例2:

建模11¤

建立模型¶

涉及对象:课程¶

约束关系:同一学生选修的课程不能安排在同一时间考试¶

模型:图——表达课程之间的约束关系ABCDEF算法分析形式语言计算机图形学模式识别网络技术人工智能杨润生石磊魏庆涛马耀先齐砚生选修1ACCDB选修2BDEFF选修3EFA杨润生石磊魏庆涛马耀先齐砚生选修1ACCDB选修2BDEFF选修3EFAC

DBAF12非数值计算问题举例2:

建模¤

图:顶点:表示课程;边:同一学生选修的课程用边连接E非数值计算问题举例2:

求解(着色法)¤

每种颜色代表一个考试时间,用尽量少的颜色为顶点着色;¤

着色原则:相邻顶点着不同颜色;不相邻顶点着相同颜色;¤

着相同颜色的顶点(课程)安排在同一时间考试;考试日程:1:

A,C2:

B,

D3:

E4:

FC

D13EBAF不冲突课程组{

A,

C}{B,

D}{E}{F}非数值计算问题举例2:

求解(着色法)¤

求解考试日程的流程i=1;

V={图中所有顶点的集合}若V

非空DO置NEW

为空集合;在V中取一点,找出所有与之“不相邻”的顶点;将这些顶点加入NEW,从V

中去掉这些顶点(第i天考试课程为NEW中顶点所对应的课程)输出NEW中顶点所对应的课程;i

=

i+1;若V

空,结束14非数值计算问题举例32831476512384765¤

非数值计算的程序设计问题¤

例3:八数码问题¶

涉及对象:棋盘棋盘的格局¶

对象关系:移动方格操作¶

基本关系:空格上移,空格下移,空格左移,空格右移S0

Sg1516八数码问题2

8

31

47

6

5S012

8

31

47

6

522

31

8

47

6

532

8

31

47

6

542

8

31

6

47

558

32

1

47

6

52

8

37

1

46

52

31

8

47

6

52

31

8

47

6

52

81

4

37

6

52

8

31

4

57

62

8

31

6

47

52

8

31

6

47

56789

1011

12138

32

1

47

6

528312323428283283283714841814314564166576576576576175754141521222324258381328328312312214247471484787657656156576563452627SgRoute: S0

→3

→8→

16

→26(Sg)数值问题对象:塔高度h,下落时间t——用数值表示模型(对象之间的关系)二元一次方程——用方程表示问题求解方法计算方法编程:非数值问题对象:课程——用课程名表示——不能用数值表示模型(对象之间的关系)课程间有“冲突”关系——不能用方程表示问题求解方法……编程:数值问题与非数值问题的程序设计比较17数据结构研究的主要内容18¤

概括地说:¶数据结构是一门研究“非数值计算的程序设计问题中计算机操作对象以及它们之间的关

系和操作”的学科。¤

具体地说:¶数据结构主要研究数据之间有哪些结构关系,如何表示,如何存储,如何处理。1.2

基本概念19¤

1.2.1

数据与数据结构¤

1.2.2

数据类型¤

1.2.3

抽象数据类型1.2.1

数据与数据结构20¤

数据(data):¶

所有能被输入到或产生在计算机中,且能被计算机处理的符号的集合。¶

是对计算机处理的对象的一个统称,被看作为信息的载体。¤

数据项(data

item):¶

数据不可分割的最小标识单位。¶

一个数据元素可由若干数据项组成。¤

数据元素(data

element):¶

是数据结构中讨论的基本单位¶

例如:描述一个学生的数据元素可以是学号姓名出生日期入学日期班级专业1.2.1

数据与数据结构¤

数据结构:带有关系和运算的数据集合a.集合关系b.线性关系c.

树型关系d.图型关系21数据结构22¤

数据结构:带有关系和运算的数据集合¤

数据之间结构关系:是具体关系的抽象。例1:学号姓名出生日期入学日期班级专业cs001张扬0212199001092009cs20091计算机cs002李明0711199001092009cs20091计算机cs003杨华0105199001092009cs20091计算机cs004贾茹1504199001092009cs20091计算机学生间学号顺序关系是一种线性结构关系线性结构关系是对学生间学号顺序关系的一种抽象表示数据结构23¤

数据结构:带有关系和运算的数据集合¤

例1:定义学生数据结构中的运算:¶

查询学生信息¶

插入学生信息¶

修改学生信息¶

删除学生信息学号姓名出生日期入学日期班级专业cs001张扬0212199001092009cs20091计算机cs002李明0711199001092009cs20091计算机cs003杨华0105199001092009cs20091计算机cs004贾茹1504199001092009cs20091计算机数据结构¤

例2:计算机文件系统文件夹或文件间的关系是一种树型结构关系树型结构关系是对文件系统关系的一种抽象表示C:文件夹1文件夹n…..子文件夹21子文件夹22子文件夹n1子文件夹n2子文件夹221子文件夹222子文件夹223文件夹2文件2211文件2212文件1文件n1124文件n12数据结构¤

例2:定义计算机文件系统中的操作¶

查找、新建、删除文件夹¶

查找、新建、删除文件C:文件夹1文件夹n…..子文件夹21子文件夹22子文件夹n1子文件夹n2子文件夹221子文件夹222子文件夹223文件夹2文件2211文件2212文件1文件n1125文件n1226数据结构¤

例3:地铁线路规划地铁站之间的连接关系是一种图型结构关系图型结构关系是对地铁站之间的连接关系的一种抽象表示数据结构27¤

例3:地铁线路规划¤

定义地铁图中的操作:¶

查询地铁站¶

规划乘车路线¶

增加地铁站¶

关闭地铁站…可见,不同的“关系”构成不同的“数据结构”。数据结构是相互之间存在着某种逻辑关系的数据元素集合及定义在该集合上的操作集合这些关系称为数据的逻辑结构。数据结构的表示28¤

图示表示图示表示是由顶点和边构成的图,其中顶点表示数据,边表示数据之间的结构关系。¤

二元组表示:¤

数据结构是一个二元组:Data_Structures

=

(D,

S)¶

D

是数据元素的有限集,¶

S

是D上关系的有限集。数据结构的表示学号姓名出生日期入学日期班级专业cs001张扬0212199001092009cs20091计算机cs002李明0711199001092009cs20091计算机cs003杨华0105199001092009cs20091计算机cs004贾茹1504199001092009cs20091计算机¤

线性关系的表示cs001

cs002

cs003

cs00429D

=

{

cs001,cs002,cs003,cs004}S

=

{

R

}R

=

{

<cs001,cs002>,

<cs002,cs003>,

<cs003,cs004>}30C:文件夹n…..22子文件夹n1子文件夹n2子文件夹223¤

树型关系的表示文件夹1子文件夹文件夹2子文件夹子文件夹221

文件2211文件2212子文件夹222文件1文件n11文件n12C:c1c2cnf1c21

c22c221c222c22321

f2211f2212cn1

cn2fn11fn12……C:c1c2cnf1c21

c22c221c222c223f2211f2212cn1

cn2fn11fn12……¤

树型关系的表示D

=

{

C,c1,c2,…,

cn,

f1,

c21,

c22,

cn1,

cn2,

c2221,

c222,c222,c223,

fn11,

fn12,

f2211,

f2212}C:31c1f1c21

c22c221

c222c223f2211

f2212cn1

cn2fn11fn12c2

……

cnS

=

{

R

}R

=

{

<C,c1>,

<C,c2>,

…,<C,cn>,

<C,f1>,

……

}数据的逻辑结构a.集合关系¤

数据的逻辑结构——描述数据间的逻辑关系¤

数据的逻辑结构可归结为以下四类:b.线性关系c.

树型关系d.图型关系32数据的存储结构33¤

数据的存储结构——逻辑结构在存储器中的映象¤

存储结构包含两个方面:¶

“数据元素”的映象¶

“关系”的映象数据的存储结构-数据元素的映象34¤

用二进制位(bit)的位串表示数据元素¶

(321)10

=

(101000001)2¶

A =

(001000001)2数据的存储结构-关系的映象35¤

即如何表示两个元素之间的关系<x,

y>¤

方法一:顺序映象(顺序存储结构)¶

用数据元素在存储器中的相对位置来表示数据元素之间的逻辑关系¤

例如:令y

的存储位置和x

的存储位置之间差一个常量Cxy数据的存储结构-关系的映象¤

方法二:链式映象(链式存储结构)¶

以附加信息(指针)表示数据关系¶

需要用一个和x

在一起的附加信息指示y

的存储位置yx36数据的存储结构-关系的映象树型结构¤

树型结构的链式存储结构1245

673^^765^

^

^

^

^

^432137数据的存储结构-38¤

在不同的编程环境中,存储结构可有不同的描述方法。¤

当用高级程序设计语言进行编程时,通常可用高级编程语言中提供的数据类型描述之。¤例如:以三个带有次序关系的整数表示一个长整数时,可利用C

语言中提供的整数数组类型。¶

定义长整数为:¶

typedef

int

Long_int

[3]1.2.2

数据类型39¤

数据类型:在一种程序设计语言中,变量所具有的数据种类。¤

例1:在FORTRAN语言中¶

变量的数据类型有整型、实型、和复数型¤

例2:在C语言中数据类型:基本类型和构造类型¶

基本类型:整型、浮点型、双精度、逻辑型、字符型¶

构造类型:数组、结构、联合、指针、枚举型、自定义¤

不同类型的变量,其取值范围不同,所能进行的操作不同40¤

数据类型:是一个值的集合和定义在此集合上的一组操作的总称。¤

如何处理不同语言中的数据类型呢?1.2.3

抽象数据类型41¤

抽象数据类型(Abstract

Data

Type

简称ADT)ADT是对数据结构的一种更准确的抽象描述,它忽略了数据结构的具体实现步骤,将更多的注意力放在数据的基本操作上,通过基本操作描述数据的逻辑关系。抽象数据类型的定义格式42ADT

抽象数据类型名{数据对象:〈数据对象的定义〉数据关系:〈数据关系的定义〉基本操作:〈基本操作的定义〉}ADT

抽象数据类型名基本操作名(参数表)初始条件:〈初始条件描述〉操作结果:〈操作结果描述〉¤

参数表¶

赋值参数只为操作提供输入值。¶

引用参数以&打头,除可提供输入值,还将返回操作结果。¤

初始条件描述了操作执行之前数据结构和参数应满足的条件,若不满足,则操作失败,并返回相应出错信息。¤

操作结果说明了操作正常完成之后,数据结构的变化状况和应返回的结果。43基本操作名(参数表)初始条件:〈初始条件描述〉操作结果:〈操作结果描述〉ADT举例44¤

例如,抽象数据类型“复数”的定义:ADT

Complex

{数据对象:

D={e1,e2|e1,e2∈RealSet

}数据关系:R1={<e1,e2>

|

e1是复数的实数部分|

e2

是复数的虚数部分}基本操作:AssignComplex(

&Z,v1,

v2

)操作结果:构造复数Z,其实部和虚部分别被赋以参数v1

和v2

的值DestroyComplex(

&Z)操作结果:复数Z被销毁。ADT举例(续)45GetReal(

Z,

&realPart

)初始条件:复数已存在。操作结果:用realPart返回复数Z的实部值。GetImag(

Z,

&ImagPart

)初始条件:复数已存在。操作结果:用ImagPart返回复数Z的虚部值。Add(

z1,z2,

&sum

)初始条件:z1,

z2是复数。操作结果:用sum返回两个复数z1,

z2

的和值}

ADT

ComplexADT

的特征46¤

特征一:数据抽象¶用ADT描述程序处理的实体时,强调的是其本质的特征、其所能完成的功能以及它和外部用户的接口(即外界使用它的方法)。¤

特征二:数据封装¶将实体的外部特性和其内部实现细节分离,并且对外部用户隐藏其内部实现细节。ADT

的实现¤

ADT需要通过固有数据类型(高级编程语言中已实现的数据类型)来实现¤

例如对上述复数ADT的实现://存储结构的定义typedef struct

{float

realpart;float

imagpart;}complex;//-----基本操作的函数原型说明void

Assign(

complex

&Z,

float

realval,

float

imagval

);//构造复数Z,其实部和虚部分别被赋以参数//realval

和imagval

的值float

GetReal(

complex

Z);//返回复数Z

的实部值

float

Getimag(

complex

Z);//返回复数Z的虚部值

void

add(complex

z1,

complex

z2,

complex

&sum);//以sum

返回两个复数z1,

z2

的和47ADT

的实现(续)////-----基本操作的实现void

add(

complex

z1,

complex

z2,

complex &sum

)

{//以sum

返回两个复数z1,

z2

的和

sum.realpart=z1.realpart+z2.realpart;sum.imagpart=z1.imagpart+2.imagpart;}481.3

算法和算法的衡量49¤

1.3.1

算法及其特征¤

1.3.2

算法设计的原则¤

1.3.3

算法效率的衡量方法和准则¤

1.3.4

算法的存储空间需求1.3.1

算法及其特征50¤

算法:是为了解决某类问题而规定的一个有限长的操作序列。¤

一个算法必须满足以下五个重要特性:¶

1.有穷性¶

2.确定性¶

3.可行性¶

4.有输入¶

5.有输出¤

1.有穷性:51¶

在执行有穷步骤之后一定能结束¶

每个步骤都能在有限时间内完成¤

2.确定性:¶

算法中每一条指令必须有确切的含义,不存在二义性。¶

算法只有一个入口和确定性的出口。¶

并且在任何条件下,算法都只有一条执行路径¤

3.可行性:¶

算法是可行的。¶

即算法描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。1.3.2

算法设计的原则52¤

评价一个好的算法有以下几个标准:正确性(Correctness):算法应满足具体问题的需求。可读性(Readability):算法应该好读。以有利于阅读者对程序的理解。健状性(Robustness):算法应具有容错处理。当输入非法数据时,算法应对其作出反应,而不是产年莫名其妙的输出结果效率与存储量需求:效率指的是算法执行的时间;存储

量需求指算法执行过程中所需要的最大存储空间。一般,这两者与问题的规模有关¤

对算法是否“正确”的理解可以有以下四个层次:53¶

a.程序中不含语法错误;¶

b.程序对于几组输入数据能够得出满足要求的结果;¶

c.程序对于精心选择的、典型、苛刻且带有刁难性的几组输入数据能够得出满足要求的结果;¶

d.程序对于一切合法的输入数据都能得出满足要求的结果;¤

通常以第c层意义的正确性作为衡量一个算法是否合格的标准。1.3.3

算法效率的衡量方法和准则54¤

和算法执行时间相关的因素:¶

1.计算机执行指令的速度¶

2.编译程序产生的机器代码的质量¶

3.编写程序的语言¶

4.问题的规模¶

5.算法选用的策略¤一个特定算法的“运行工作量”的大小,只依赖于问题的规模(通常用整数量n表示),即它是问题规模的函数。衡量算法效率的方法55¤

通常有两种衡量算法效率的方法:¤

方法一:事后统计法¶

缺点1.必须执行程序¶

缺点2.其它因素掩盖算法本质¤

方法二:事前分析估算法事前分析估算法¤

随着问题规模n

的增长,算法执行时间T(n)的增长率和f(n)的增长率相同,则可记作T(n)

=

O(f(n))称作算法的渐近时间复杂度。n

fi

¥f

(

n

)lim

T

(

n

)

=

C56如何估计算法的时间复杂度?¤

例1、矩阵乘法¤

基本操作在算法中重复执行的次数作为算法运行时间的衡量准则¤

频度:是指该语句重复执行的次数¤

总次数为:n2+n3¤

时间复杂度为T(n)=O(n3)void

mult(int

a[],

int

b[],

int&c[]

)

{//以二维数组存储矩阵元素,c为a

和b

的乘积for(i=1;

i<=n;

++i)for(j=1;j<=n;++j){c[i][j]=0;for(k=1;k<=n;++k)c[i][j]+=a[i][k]*b[k][j];}57如何估计算法的时间复杂度?58¤

算法=控制结构+原操作(固有数据类型的操作)¤

算法的执行时间=∑原操作(i)的执行次数×原操作(i)的执行时间¤

算法的执行时间与

原操作执行次数之和

成正比如何估计算法的时间复杂度?59¤

例2{++x;}¶

将x自增看成是基本操作,则语句频度为1,¶

时间复杂度为O(1),即常量阶¤

例3、for(i=1;i<=n;++i){++x;

s+=x;}¶

语句频度为:2n¶

其时间复杂度为O(n),即时间复杂度为线性阶。如何估计算法的时间复杂度?60¤

例4、for(i=0;i<n;

i++)for(j=0;j<n;j++){++x;s+=x;}¶

语句频度为:2n2¶

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论