数据结构 第1章 绪论学习资料_第1页
数据结构 第1章 绪论学习资料_第2页
数据结构 第1章 绪论学习资料_第3页
数据结构 第1章 绪论学习资料_第4页
数据结构 第1章 绪论学习资料_第5页
已阅读5页,还剩49页未读, 继续免费阅读

付费下载

下载本文档

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

文档简介

zengyan@数据结构曾艳12相关介绍成绩评定卷面:70%(期中21%,期末49%)平时:30%作业+上机+点名3上机安排----软件1101-02时间:2#438地点:第3周一3-4第3周三1-2第7周一3-4第7周五1-2第9周三1-2第9周五1-2第10周五3-4第12周五3-4第13周三1-2第13周五1-2第18周三1-2第18周五3-44上机安排----软件1103-04时间:2#438地点:第3周一1-2第3周三3-4第7周一1-2第7周五3-4第9周三3-4第9周五3-4第10周五1-2第12周五1-2第13周三3-4第13周五3-4第18周三3-4第18周五1-25数据结构计算机的应用涉及到的更多的是非数值计算的问题。即计算机处理的对象是纯粹的数值以外的表格、图像、声音等各种具有一定结构的数据。计算机应用系统中的两个关键问题:1.表示:对象及其关系在计算机中的表示。只有对象及其相互关系已存储在计算机中,才能被进一步处理;2.操作:对对象进行处理,访问。6第1章绪论1.1数据结构的基础概念1.2数据结构的内容1.3算法设计1.5对算法的性能评价1.4算法描述工具1.7

关于学习数据结构1.6

数据结构与C语言表示7第1章绪论1.1数据结构的基础概念相关名词:◆数据(Data)◆数据元素(DataElement)◆数据对象(DataObject)◆数据结构(DataStructure)◆数据类型(DataType)◆数据抽象与抽象数据类型8第1章绪论1.1数据结构的基础概念数据(Data):数据是描述客观事物的数值、字符以及能输入机器且能被处理的各种符号集合。数据包含整型、实型、布尔型、图象、字符、声音等一切可以输入到计算机中的符号集合。9第1章绪论1.1数据结构的基础概念数据元素(DataElement):例如:..................学委计算机系计科女罗文春13职务系别专业性别姓名学号数据元素数据项一个数据元素可由一个或多个数据项(DataItem)组成,数据项是有独立含义的最小单位。记录是组成数据的基本单位,是数据集合的个体,在计算机中通常作为一个整体进行考虑和处理。910第1章绪论1.1数据结构的基础概念数据对象(DataObject):数据对象是性质相同的数据元素的集合,是数据的一个子集。例如:整数集合:N={0,±1,±2,…}无限集字符集合:C={‘A’,‘B’,…,‘Z’}有限集11第1章绪论1.1数据结构的基础概念数据结构(DataStructure):例如:表结构是指相互之间存在一种或多种特定关系的数据元素集合,是带有结构的数据元素的集合,它指的是数据元素之间的相互关系,即数据的组织形式。..................学委计算机系计科女罗文春13职务系别专业性别姓名学号12第1章绪论1.1数据结构的基础概念例如:树结构教研室实验室系处科研机构学校图结构125431213第1章绪论1.1数据结构的基础概念数据类型(DataType):例如:在高级语言中,整型类型的取值范围为:-32768~+32767,运算符集合为加、减、乘、除、取模,即+、-、*、/、%。数据类型是一组性质相同的值集合以及定义在这个值集合上的一组操作的总称。原子类型:其值不可分解。如C语言中的标准类型(整型、实型、字符型)。结构类型:其值是由若干成分按某种结构组成的,因此是可以分解的,并且它的成分可以是非结构的,也可以是结构的。14第1章绪论1.1数据结构的基础概念数据的抽象汇编语言中十进制表示的数据98.65、9.6E3等,它们是二进制数据的抽象;高级语言中,给出更高一级的数据抽象,如整型、实型、字符型等,还可以进一步定义更高级的数据抽象,如各种表、队、栈、树、图、窗口、管理器等复杂的抽象数据类型。15第1章绪论1.1数据结构的基础概念抽象数据类型(AbstractDataType):指基于一类逻辑关系的数据类型以及定义在这个类型之上的一组操作。一个抽象数据类型确定了一个模型,但将模型的实现细节隐藏起来;它定义了一组运算,但将运算的实现过程隐藏起来。1516第1章绪论1.1数据结构的基础概念ADT有两个重要特征:①数据抽象:②数据封装:将实体的外部特性和其内部实现细节分离,并且对外部用户隐藏其内部实现细节。用ADT描述程序处理的实体时,强调的是其本质的特征、其所能完成的功能以及它和外部用户的接口(即外界使用它的方法)。返回17第1章绪论1.2数据结构的内容

逻辑结构存储结构运算集合18第1章绪论1.2数据结构的内容

逻辑结构:指数据元素之间逻辑关系描述。形式化描述:

Data_Structure=(D,R)其中D是数据元素的有限集,R是D上关系的有限集。四类基本的结构集合结构、线性结构、树型结构、图状结构。19第1章绪论1.2数据结构的内容

集合结构:结构中的数据元素之间除了同属于一个集合的关系外,无任何其它关系。例如:20第1章绪论1.2数据结构的内容

线性结构:结构中的数据元素之间存在着一对一的线性关系。

例如:21第1章绪论1.2数据结构的内容

树型结构:结构中的数据元素之间存在着一对多的层次关系。例如:22第1章绪论1.2数据结构的内容

图状结构或网状结构

:结构中的数据元素之间存在着多对多的任意关系。例如:23第1章绪论1.2数据结构的内容

存储结构:逻辑结构在计算机中的存储映象,是逻辑结构在计算机中的实现,它包括数据元素的表示和关系的表示。

是数据结构的实现;是数据结构的抽象。数据元素之间关系在计算机中的表示方法:顺序映象

(顺序存储结构)

非顺序映象(非顺序存储结构)24第1章绪论1.2数据结构的内容

例如工资表:编号姓名性别基本工资工龄工资应扣工资实发工资100001张爱芬女345.67145.4530.00451.12100002李

林

男

445.90185.6045.00586.50100003刘

晓峰

男

345.00130.0025.00450.00100004赵

俊

女

560.90225.9065.00721.80100005孙

涛

男

450.60190.8050.00591.80……

……………100121张兴强

男

1025.98365.53100.001291.51人员的增加、删除、工资的调整、工资额的计算等24运算集合25第1章绪论1.2数据结构的内容

数据结构的内容可归纳为三个部分,即逻辑结构、存储结构和运算集合。按某种逻辑关系组织起来的一批数据,按一定的映象方式把它存放在计算机存贮器中,并在这些数据上定义了一个运算的集合,就叫做数据结构。返回26第1章绪论1.3算法设计算法(Algorithm)定义算法的特性算法设计的要求27第1章绪论1.3算法设计Algorithmisafinitesetofruleswhichgivesasequenceofoperationforsolvingaspecifictypeofproblem.算法是规则的有限集合,是为解决特定问题而规定的一系列操作。

算法定义:28第1章绪论1.3算法设计算法特性:①

有限性:有限步骤之内正常结束,不能形成无穷循环;②确定性:算法中的每一个步骤必须有确定含义,无二义性得以实现;③输入:有多个或0个输入;④输出:至少有一个或多个输出;⑤可行性:原则上能精确进行,操作可通过已实现基本运算执行有限次而完成。29第1章绪论1.3算法设计设计的要求:①

正确性

例如:求n个实数的最大值问题算法如下:

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

{scanf("%f",&x);if(x>max)max=x;}

算法的正确性2025/4/28301.算法应明确表述问题的需求(严格描述)。2.对“正确”的理解可以有以下四个层次:a.程序中不含语法错误;b.程序对几组输入数据能够得出满足要求的结果;c.程序对于精心选择的、典型、苛刻且带有刁难性的几组输入数据都能够得出满足要求的结果;通常以C层意义作为衡量一个算法是否合格的标准。d.对于一切合法输入数据都能得出满足要求的结果;3031第1章绪论1.3算法设计设计的要求:①

正确性

②可读性③健壮性④高效率和低存储量例如:求n个实数的最大值问题算法如下:

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

{scanf("%f",&x);if(x>max)max=x;}返回32第1章绪论1.4算法描述工具算法、语言、程序的关系设计实现算法过程步骤类描述算法的语言选择33第1章绪论1.4算法描述工具算法、语言、程序的关系算法:描述了数据对象的元素之间的关系(包括数据逻辑关系、存贮关系描述)。描述算法的工具:算法可用自然语言、框图或高级程序设计语言进行描述。程序:是算法在计算机中的实现。34第1章绪论1.4算法描述工具设计实现算法过程步骤:①找出与求解有关的数据元素之间的关系;②确定在某一数据对象上所施加运算;③考虑数据元素的存储表示;④选择描述算法的语言;⑤设计实现求解的算法,并用程序语言加以描述。35第1章绪论1.4算法描述工具类语言:类语言是接近于高级语言而又不是严格的高级语言,具有高级语言的一般语句设施,撇掉语言中的细节,以便把注意力主要集中在算法处理步骤本身的描述上。算法描述的常用工具

1.自然语言2.框图3.类语言(伪语言)返回36第1章绪论1.5对算法作性能评价评价算法的标准:评价一个算法主要看这个算法所占用机器资源的多少,而这些资源中时间代价与空间代价是两个主要的方面,通常是以算法执行所需的机器时间和所占用的存储空间来判断一个算法的优劣。37第1章绪论1.5对算法作性能评价性能评价:对问题规模与该算法在运行时所占的空间S与所耗费的时间T给出一个数量关系的评价。问题规模N—对不同的问题其含义不同:

对矩阵是阶数;对多项式运算是多项式项数;对图是顶点个数;对集合运算是集合中元素个数。38第1章绪论1.5对算法作性能评价有关数量关系计算数量关系评价体现在时间——算法在机器中所耗费时间。数量关系评价体现在空间——算法在机器中所占存储量。39第1章绪论1.5对算法作性能评价关于算法执行时间:大致上等于其所有语句执行时间的总和,对于语句的执行时间是指该条语句的执行次数和执行一次所需时间的乘积。

不是针对实际执行时间的精确地算出算法执行具体时间,而是针对算法中语句的执行次数做出估计,从中得到算法执行时间的信息。40第1章绪论1.5对算法作性能评价语句频度

:指该语句在一个算法中重复执行的次数。例如:两个n*n阶矩阵相乘算法语句对应的语句频度

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

2 for(j=0;j<n;j++)

{3

c[i][j]=0;4for(k=0;k<n;k++)5c[i][j]+=a[i][k]*b[k][j];}nn2n2n3n341第1章绪论1.5对算法作性能评价算法的时间复杂度

:就是算法的时间量度。记做:T(n)=O(f(n))例如:对语句X=X+1①

x=x+1;时间复杂度为O(1),称为常量阶;②for(i=1;i<=n;i++)x=x+1;时间复杂度为O(n),称为线性阶;③for(i=1;i<=n;i++)for(j=1;j<=n;j++)x=x+1;时间复杂度为O(n2),称为平方阶。42第1章绪论1.5对算法作性能评价常用的时间复杂度频率计数O(1)常数型O(n)线性型O(n2)平方型O(n3)立方型O(2n)指数型O(log2n)对数型O(nlog2n)二维型2147483648327681024160325655365096256641642565126424831664168424842212110102nn3n2nlog2nnlog2n可实现只有对n限制在很小范围才有意义4243第1章绪论1.5对算法作性能评价最坏时间复杂度:讨论算法在最坏情况下的时间复杂度,即分析最坏情况下以估计出算法执行时间的上界。例如:冒泡排序算法voidbubble(inta[],intlength){inti=0,j,temp;

intchange;

do{

change=false;for(j=1;j<length-i;j++)if(a[j]>a[j+1]){temp=a[j];a[j]=a[j+1];a[j+1]=temp;change=true;}i=i+1;}while(i<length&&change==true);}44第1章绪论1.5对算法作性能评价算法的空间复杂度:作为算法所需存储空间的量度,记做:S(n)=O(f(n))

。返回数学模型抽象数据模型数据结构非形式算法伪语言程序可执行程序

用抽象数据类型的概念来指导问题的求解过程为:1.选择数学模型描述问题,确定解决问题的算法2.为模型定义抽象数据类型,并用伪语言描述算法3.确定抽象数据类型的实现方法,用程序实现算法第1章绪论1.6数据结构与C语言表示4546第1章绪论ADT的定义:ADT<ADT名>

{

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

结构关系:<结构关系的定义>

基本操作:<基本操作的定义>}ADT<ADT名>基本操作的定义格式为:<操作名称>(参数表)操作前提:<操作前提描述>操作结果:<操作结果描述>1.6数据结构与C语言表示例:简化线性表的ADT定义ADTLinear_list数据元素

所有ai属于同一数据对象,

i=1,2,……,nn≥0;逻辑结构

所有数据元素ai(i=1,2,…,n-1)存在次序关系<ai,ai+1>,a1无前趋,an无后继;操作

设L为Linear_list Initial(L)初始化空线性表;

Length(L)求线性表的表长;

Get(L,i)取线性表的第i个元素;

Insert(L,i,b)在表的第i个位置插入元素b;

Delete(L,i)删除线性表的第i个元素;第1章绪论1.6数据结构与C语言表示47用C语言实现ADT(1)用typedef定义所需的新类型结构:

typedef可以用来创建新数据类型,也可以为新创建的数据类型命名,使用很方便,这在数据结构的抽象描述方面很有用。(2)用子函数实现各个操作。第1章绪论1.6数据结构与C语言表示48算法描述规范与设计风格

1、算法表示形式:[函数返回值类型]函数名([形式参数及说明])

{内部数据说明;执行语句组;

}/*函数名*/2、算法描述要点加注释、…、退出语句的区别等(p23-24)第1章绪论1.6数据结构与C语言表示49函数参数的传递

变量的作用域:全局变量、局部变量参数的传递方式:传值、传地址

温馨提示

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

评论

0/150

提交评论