Chap1算法与数据结构—C语言描述第2版张乃孝编.ppt

《Chap1算法与数据结构—C语言描述第2版张乃孝编.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、数据结构的地位“数据结构”在计算机科学中是一门综合性的专业基础课。数据结构是介于数学、计算机硬件和计算机软件三者之间的一门核心课程。数据结构这一门课的内容不仅是一般程序设计（特别是非数值性程序设计）的基础，而且是设计和实现编译程序、操作系统、数据库系统及其他系统程序的重要基础。程序=数据结构+算法课程目的能够分析研究计算机加工的对象的特性，获得其逻辑结构，根据需求，选择合适存储结构及其相应的算法；学习一些常用的算法；复杂程序设计的训练过程，要求编写的程序结构清楚和正确易读；初步掌握算法的时间分析和空间分析技术；第一章概论问题和实例数据结构？抽象数据类型AD

2、T类C描述算法和算法分析问题和实例(1)当我们使用计算机来解决一个具体问题时，一般需要经过下列几个步骤：问题抽象数据结构算法程序问题和实例(2)快速送达疫苗已知有临近的五个村子发生了疫情，我们要用汽车快速地将疫苗送达到5个村子。目标是寻找一条耗时最少的路线。胜利发生疫情的五个村子河源长利太华桦南1275344123村子联系网络v1v5v2v4v31275413432耗时矩阵穷举法贪心算法数据结构是一门研究非数值计算的程序设计问题中，计算机操作的对象以及它们之间的关系和操作的学科例子书目自动检索系统人机对奕问题快速送达疫苗问题例1书目自动检索系统登录号：书名

3、：作者名：分类号：出版单位：出版时间：价格：书目卡片书目文件按书名按作者名按分类号索引表线性表数据结构例2人机对奕问题树……..……..…...…...…...…...例3：问题：快速送达疫苗模型：图形结构图形结构胜利发生疫情的五个村子河源长利太华桦南1275344123图数据结构基本概念和术语数据(Data)：客观事物在计算机中的符号表示，是能被计算机识别和处理的符号总称。(数值型、非数值型)数据元素(DataElement)：数据的基本单位，用于完整地描述一个对象;数据项(DataObject)：组成数据元素的有特定意义的最小单位。数据对象(DataO

4、bject)：相同特性数据元素的集合，是数据的一个子集合。数据结构：相互之间存在一种或多种特定关系的数据元素的集合。根据数据元素间关系的基本特性，有四种基本数据结构（集合）——数据元素间除“同属于一个集合”外，无其它关系线性结构——一个对一个，如线性表、栈、队列树形结构——一个对多个，如树图状结构——多个对多个，如图基本概念和术语基本概念和术语形式定义：数据结构是一个二元组Data_Structure＝（D，R）,其中，D是数据元素的有限集，R是D上关系的有限集。数据结构主要关心的是下面三个方面：结构中各元素之间的逻辑关系线性结构：如图书馆的书目索引树形结

5、构：如人机对奕问题图形结构：交通图2.结构中各元素的存储方式(物理结构)3.结构具有的行为特征(关系与操作)基本概念和术语存储结构(物理结构)数据结构在计算机中的表示。顺序存储结构：借助元素在存储器中的相对位置表示数据元素之间的关系。链式存储结构：借助指示元素存储地址的指针（Pointer）表示数据元素之间的逻辑关系。a[0]a[n-1]1000a[1]a[2]10021004a[0]a[2]a[3]a[1]300020001000数据的逻辑结构数据的存储结构数据的运算：检索、排序、插入、删除、修改等线性结构非线性结构顺序存储链式存储线性表栈队树形结构图形

6、结构数据结构的三个方面：基本概念和术语抽象数据类型抽象数据类型:（AbstractDataType）ADT:一个数学模型以及定义在该模型上的一组操作。ADT抽象数据类型名{数据对象：{数据对象定义}数据关系：{数据关系定义}基本操作：{基本操作定义}}ADT抽象数据类型名复数抽象数据类型ADTComplex{数据对象：D={c1,c2

7、c1,c2R(R为实数集）}数据关系：S={（c1为实部，c2为虚部）}基本操作：voidAssign(*A,c1,c2）voidAdd(*A,B)voidMinus(*A,B)voidMultiply(*A

8、,B)voidDivide(*A,B)...}ADTComplex复数抽象数据类型示例typedefdoubleItemType;typedefstruct{ItemTyper;ItemTypev;}Complex;/*复数抽象数据类型*/voidAssign(Complex*A,ItemTyper,ItemTypev);/*赋值*/voidAdd(Complex*A,ComplexB);/*A+B*/voidMinus(Complex*A,ComplexB);/*A-B*/voidMultiply(Compex*A,ComplexB);/*A*B*/vo

9、idDivide(Complex*A,ComplexB);/*A/