数据结构与算法（c语言版）第2版上ppt

《数据结构与算法（c语言版）第2版上ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构与算法（C语言版）第2版上作者：郭龙源、胡虚怀、何光明、戴仕明第1章绪论本章主要内容1.1学习数据结构与算法的意义1.2数据结构1.3抽象数据类型1.4算法1.5算法分析1.1学习数据结构与算法的意义1.1.1学习数据结构的意义1.1.2学习算法的意义1.1.1学习数据结构的意义数据结构为研究非数值计算问题提供了数据的表示与操作途径。数据结构是计算机科学与技术专业的专业基础课，是十分重要的核心课程。所有的计算机系统软件和应用软件都要用到各种类型的数据结构。因此，要想更好地运用计算机来解决实际问题，仅掌握几种计算机程序设计语言是难以应付众多复杂课题

2、的。要想有效地使用计算机，充分发挥计算机的功能，还必须学习和掌握好数据结构的有关知识。扎实地打好“数据结构”这门课程的基础，对于学习计算机专业的其他课程，如操作系统、编译原理、数据库管理系统、软件工程及人工智能等都是十分有益的。1.1.2学习算法的意义学习和研究算法可以明确分析所得到的算法的好坏，寻找能满足要求的较优算法，从而更加高效地解决问题。学习算法设计的方法和算法分析的技术后，可以帮助我们设计较好的算法，分析算法的优、缺点，从而找出解决某一问题的最好方法。1.2数据结构1.2.1数据结构概述1.2.2基本概念和相关术语1.2.1数据结构概述数据结构

3、是在整个计算机科学与技术领域中广泛使用的术语。它用来反映一个数据的内部构成，即一个数据由哪些成分构成？以什么方式构成？呈现什么样的结构？数据结构有逻辑上的数据结构和物理上的数据结构之分。逻辑上的数据结构反映数据之间的逻辑关系，而物理上的数据结构反映数据在计算机内部的存储安排。数据结构是数据存在的形式。1.2.2基本概念和相关术语数据(data)是信息的载体，是描述客观事物的数、字符以及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。数据分为两类：数值型数据(主要用于数学计算等)和非数值型数据(文字、图形、图像、音频和视频等)。数据元素(data

4、element)是数据的基本单位。在不同的条件下，数据元素又可称为元素、结点、顶点、记录等。一个数据元素可由不可分割的若干个数据项(dataitem)组成。数据对象(dataobject)是性质相同的数据元素的集合，是数据的一个子集。数据结构(datastructure)是指相互之间存在着一种或多种关系的数据元素的集合。在任何问题中，数据元素之间总是存在联系的。把某一数据对象及该数据对象中所有数据成员之间的关系组成的实体叫做数据结构。数据结构有以下4种基本结构。(1)集合结构：数据元素之间存在着“属于同一个集合”的关系，如图1.2(a)所示。(2)线性结

5、构：数据元素之间存在着“一对一”的关系，如图1.2(b)所示。(3)树形结构：数据元素之间存在着“一对多”的关系，如图1.2(c)所示。(4)图形结构：数据元素之间存在着“多对多”的关系，如图1.2(d)所示。图1.24类基本数据结构示意图数据结构的形式定义为Data_Structure=(D,R)其中，D是数据元素的有限集；R是D上关系的有限集。数据结构可以分为逻辑上的数据结构和物理上的数据结构。数据结构的形式化定义为逻辑结构。物理结构为数据在计算机中的表示，它包括数据元素的表示和关系表示。数据元素之间的关系在计算机中有两种不同的表示方法：顺序存储和非

6、顺序存储。顺序存储结构是把逻辑上相邻的元素存储在物理位置相邻的两个单元中，它是一种最基本的存储方法，一般采用数组来实现。链式存储结构对逻辑上相邻的元素不要求其物理位置也相邻，元素间的逻辑关系通过指针来表示，一般采用链表来实现。1.3抽象数据类型抽象数据类型(AbstractDataType，ADT)是指一个数学模型以及定义在此数学模型上的一组操作。抽象数据类型由元素、关系及操作3种要素来定义。抽象数据类型用三元组来表示：(D、R、P)其中：D是数据对象；R是D上的关系集；P是对D的基本操作集。抽象数据类型名称定义的一般形式为：ADT抽象数据类型名称{数据

7、对象：…数据关系：…操作集合：操作名1;……操作名n;}ADT抽象数据类型名称1.4算法1.4.1算法概述1.4.2算法与数据结构之间的关系1.4.3算法的度量1.4.1算法概述算法(Algorithm)是解题的步骤，是指令的有限序列。一个算法应该具有以下特征：(1)有穷性。对于任何合法的输入值，一个算法必须保证执行有限步之后结束。(2)确定性。算法的每一步必须有确切的含义，无二义性，并且在任何条件下，算法只有唯一的一条执行路径，即对相同的输入只能得出相同的输出。(3)输入。一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身设定

8、了初始条件。(4)输出。一个算法有一个或多个输出，以反映对输入数据加工后的结果。