数据结构介绍.ppt

《数据结构介绍.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构第三章第一讲数据结构概述1.1什么是数据结构程序=数据结构+算法登录号：书名：作者名：分类号：出版单位：出版时间：价格：书目卡片书目文件线性表举例说明:例2人机对奕问题树……..……..…...…...…...…...数据结构定义:是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等等的学科.1.2基本概念和术语数据（data)—所有能输入到计算机中去的描述客观事物的符号数据元素（dataelement）—数据的基本单位，也称节点（node）或记录（record）数据项（dataitem）—有独立含义的数据最小单位，也称域(f

2、ield)数据结构（datastructure)—数据元素和数据元素关系的集合书目文件数据的逻辑结构数据的存储结构数据的运算：检索、排序、插入、删除、修改等线性结构非线性结构顺序存储链式存储线性表栈队树形结构图形结构数据结构的三个方面：1.数据的存储（物理）结构:数据的逻辑结构在计算机存储器中的具体实现。存储结构分为：顺序存储结构——借助元素在存储器中的相对位置来表示数据元素间的逻辑关系.链式存储结构——借助指示元素存储地址的指针表示数据元素间的逻辑关系.2.数据的逻辑结构—只抽象反映数据元素的逻辑关系.元素n……..元素i……..元素2元素1LoLo+mLo

3、+(i-1)*mLo+（n-1)*m存储地址存储内容Loc(元素i)=Lo+（i-1)*m顺序存储1536元素21400元素11346元素3∧元素41345h存储地址存储内容指针1345元素114001346元素4∧…….……..…….1400元素21536…….……..…….1536元素31346链式存储h根据数据元素间逻辑关系的基本特性，有三种基本数据结构.线性结构——一个对一个，如线性表、栈、队列;树形结构——一个对多个，如树;图状结构——多个对多个，如图;数据的逻辑结构一、算法的概念算法是由一套规则组成的一个过程，算法是对某一特定问题的求解步骤的一种描

4、述。算法应当具备以下几个方面的特点：1.3算法及其描述瑞士计算机科学家N•沃思教授提出了程序定义的著名公式：程序=数据结构+算法1、一个算法必须保证执行有限步之后结束；2、算法的每一个步骤必须具有确切的定义；3、应对算法给出初始量；4、算法具有一个或多个输出；5、算法的每一步都必须是计算机能进行的有效操作。二、算法的描述方法算法是考虑实现某一个问题求解的框架流程，而程序设计则是根据这一求解的框架流程进行语言细化实现这一问题求解的具体过程。常用描述算法的工具有：1、自然语言：使用人们日常进行交流的语言。如：从a,b中找出一个大的数给max。⑴从键盘输入两个数给a

5、和b；⑵如果a比b大，则把a的值传给max，否则把b的值传给max；⑶输出max的值。2、专用工具：借助于有关图形工具或代码符号来描述。常用的工具有流程图、N-S图等。如用N-S图来描述从a和b中找大数的问题。输入a和ba>bmaxamaxb输出max3、程序设计语言：算法最终要用程序设计语言来描述，计算机才能保存、翻译和执行。如用C语言来描述从a和b中找大数的问题。常用的算法有：迭代法、枚举法、递归法、递推法等。scanf(“%d,%d”,&a,&b);if(a>b)max=a;elsemax=b;printf(“%d,%d”,a,b);选择算法描述语言

6、的准则:（1）该语言应该具有描述数据结构和算法的基本功能；（2）该语言应该尽可能地简捷，以便于掌握、理解；（3）使用该语言描述的算法应该能够比较容易地转换成任何一种程序设计语言。“类C”描述语言是通过对C语言进行精心筛选保留的一个核心子集，并为了便于描述，又做了若干扩展修改，从而增强了语言的描述功能。1.预定义常量及类型#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineOVERFLOW-1数据元素被约定为常量类型，用户需要根据具体情况，自行定义该数据类型。2.算法描述可以使用函数形式：函数类型函数名（

7、函数参数表）{语句序列；}为了简化函数的书写，提高算法描述的清晰度，我们规定除函数参数表中的参数需要说明数据类型外，函数中使用的局部变量可以不做变量说明，必要时给出相应的注释即可。另外，在书写算法时，应该养成对重点语句段落添加注解的良好习惯。3.在算法描述中可以使用的赋值语句形式有：简单赋值变量名=表达式；串联赋值变量名1=...=变量名n=表达式；成组赋值（变量名1，...，变量名n）=（表达1，...，表达式n）；结构赋值结构名1=结构名2；结构名=（值1，值2，...，值n）；条件赋值变量名=条件表达式?表达式1：表达式2；交换赋值变量名1变量名2；4

8、.在算法描述中可以使用的选择结构语句形