大学计算机基础第5章 程序设计基础.ppt

5.2 算法与数据结构 伪代码法描述求和算法 5.2 算法与数据结构 伪代码法描述选择计算算法 5.2 算法与数据结构 5.2.3　算法与数据结构的关系 　　一个程序应该包含2个方面的内容：一是程序要处理的对象，人们用数据和数据之间的关系来表示，即数据结构；二是对这些对象的处理方法，即操作步骤，人们用算法来描述。著名计算机科学家沃思（Niklaus Wirth）提出了一个公式： 　　　　　程序 = 数据结构 + 算法 　　诠释了程序设计中的本质，揭示了算法与数据结构的关系。 5.2 算法与数据结构 1）数据结构的定义 　　数据与数据之间彼此的相互关系称为结构。为了进一步理解什么是数据结构，我们来看一个具体的例子：图书馆是大家所熟悉的，一本图书由书名、作者、出版社等数据来描述，根据需要，我们选择其中的若干项组成一个数据元素来对应一本书，图书馆的编目表反映了书与书之间的关系，是数据元素之间的结构。书是具体地放在某个书架上的，它是编目表的物理实现。这样图书馆从2个方面管理图书：物理的藏书和逻辑的编目表。和图书馆一样，计算机管理数据也有2个方面：即物理的存储和逻辑的关系。　数据结构是相互之间存在一种或多种特定关系的数据元素的集合。数据结构是信息的组织形式，即一个数据由哪些数据元素构成、以什么方式构成、呈现什么结构，数据结构指的是数据之间的结构关系。 　　数据的逻辑结构包括线性结构（如线性表、栈、队列）和非线性结构（如树、二叉树和图）；数据的物理结构指数据元素在存储器中的表示，即存储结构（如向量、链表）。 5.2 算法与数据结构 2）数据结构的分类 　　一般情况下，数据元素之间不是孤立的，常常存在某些逻辑上的联系，这些联系与它们在计算机中的存储位置无关，是独立于计算机的。我们把客观事物本身的数据元素之间抽象化的相互关系，即对数据元素之间的逻辑关系的描述称为数据的逻辑结构。　 　　数据的逻辑结构按数据元素之间的相互关系，可以把数据结构分为4种基本结构。 5.2 算法与数据结构 数据结构分类 5.2 算法与数据结构 3)数据的存储结构 　　数据要能被计算机处理，就必须存储在计算机内，我们把这种数据元素及其关系（数据结构）在计算机内的存储表示称为数据的存储结构，也称为物理结构，它是数据的逻辑结构在计算机存储器里的映像。映像就是对给定的逻辑结构，找出恰当的与其对应的存储结构，以便在计算机中存储。数据的存储结构，按关系的映像分为顺序存储结构和链式存储结构。 　　一般情况下，一个结点所占用的空间并不止一个存储单元，不同类型的结点所占用的存储单元数量也各不相同。数据结构包括结点的值及结点之间的关系，其存储结构除了必须存储结点的值外，还得能以直接或隐含的方式体现出结点之间的关系。一种逻辑结构通过映像便得到它相应的存储结构，同一种逻辑结构可以映像成不同的内部存储结构，反过来，数据的存储结构一定要反映数据之间的逻辑关系。 5.2 算法与数据结构 3)数据的存储结构 　　数据的存储结构中应该有2方面的内容：数据元素自身值的表示（数据域）和该结点与其他结点关系的域（链域）。 (1)数据元素的映像方法 　　用二进制位(bit)的位串表示数据元素： 5.2 算法与数据结构 3)数据的存储结构 (2)关系的映像方法 　　数据元素之间的关系在计算机中有顺序映像和非顺序映像2种表示方法，并由此得到顺序存储结构和链式存储结构2种存储结构。 　　顺序存储结构是逻辑上相邻的数据元素存储在物理位置上相邻的存储单元里，元素的关系由存储单元的邻接关系来体现；链式存储结构是数据元素可以在计算机内任意位置上存储（它不要求逻辑上相邻的元素在物理位置上也相邻)，它们的逻辑关系用指针来链接。链式存储结构将数据元素存放的存储单元分为2个部分，分别存放数据和指针，称为数据域和指针域。 5.2 算法与数据结构 数据结构分类 5.2 算法与数据结构 3)数据的存储结构 　　链式存储结构中，每个结点除了元素信息本身的数据外，还必须增加一个指针域(link)，用来存放该元素逻辑上的后继元素所占存储空间的首地址，这样，存储结构中的结点可以表示为下图所示。 链式存储结构中结点的组成 5.1 程序设计语言概述 5.2 算法与数据结构 5.3 程序设计基本过程 5.4 程序设计的基本思想 第 5 章　程 序 设 计 基 础 5.3 程序设计基本过程 　　程序设计主要有2个方面的任务：首先是将需要用计算机处理的实际问题抽象为数学模型，并设计出解决这个问题所需要的方法和步骤，即算法设计；其次选用适合的计算机程序设计语言，对所设计的算法进行编码处理，即程序编制。程序设计步骤一般分为问题定义、算法设计、程序编制和调试运行等步骤。 5.3.1　问题定义 通过计算机来解决问