计算机系数据结构与算法设计.pptx

数 据 结 构 计算机系 计算机系数据结构与算法设计全文共241页，当前为第1页。 第一章 绪 论 1.1 什么是数据结构 1.2 基本概念和术语 1.3 抽象数据类型的表示与实现 1.4 算法和算法分 1.4.1 算法 1.4.2 算法设计的要求 1.4.3 算法效率的度量 1.4.4 算法的存储空间的需求 计算机系数据结构与算法设计全文共241页，当前为第2页。 第一章 绪 论 计算机是一门研究用计算机进行信息表示和处理的科学。这里面涉及到两个问题： 信息的表示 信息的处理 而信息的表示和组又直接关系到处理信息的程序的效率。随着计算机的普及，信息量的增加，信息范围的拓宽，使许多系统程序和应用程序的规模很大，结构又相当复杂。因此，为了编写出一个"好"的程序，必须分析待处理的对象的特征及各对象之间存在的关系，这就是数据结构这门课所要研究的问题。 计算机系数据结构与算法设计全文共241页，当前为第3页。 1.1什么是数据结构 众所周知，计算机的程序是对信息进行加工处理。在大多数情况下，这些信息并不是没有组织，信息（数据）之间往往具有重要的结构关系，这就是数据结构的内容。那么，什么是数据结构呢？先看以下几个例子。 例1、电话号码查询系统 设有一个电话号码薄，它记录了N个人的名字和其相应的电话号码，假定按如下形式安排： (a1，b1)(a2，b2)…(an，bn) 其中ai，bi(i=1，2…n) 分别表示某人的名字和对应的电话号码要求设计一个算法，当给定任何一个人的名字时，该算法能够打印出此人的电话号码，如果该电话簿中根本就没有这个人，则该算法也能够报告没有这个人的标志。 计算机系数据结构与算法设计全文共241页，当前为第4页。 算法的设计，依赖于计算机如何存储人的名字和对应的电话号码，或者说依赖于名字和其电话号码的结构。 数据的结构，直接影响算法的选择和效率。 上述的问题是一种数据结构问题。可将名字和对应的电话号码设计成：二维数组、表结构、向量。 假定名字和其电话号码逻辑上已安排成N元向量的形式，它的每个元素是一个数对(ai，bi)， 1 i n 数据结构还要提供每种结构类型所定义的各种运算的算法。 计算机系数据结构与算法设计全文共241页，当前为第5页。 例2、图书馆的书目检索系统自动化问题 例3、教师资料档案管理系统 例4、多叉路口交通灯的管理问题 P3 通过以上几例可以直接地认为：数据结构 就是研究数据的逻辑结构和物理结构以及它们 之间相互关系，并对这种结构定义相应的运算， 而且确保经过这些运算后所得到的新结构仍然 是原来的结构类型。 计算机系数据结构与算法设计全文共241页，当前为第6页。 1.2 基本概念和术语 数据(Data):是对信息的一种符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。 数据元素(Data Element):是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 一个数据元素可由若干个数据项组成。数据项是数据的不可分割的最小单位。 数据对象(Data Object)：是性质相同的数据元素的集合。是数据的一个子集。 数据结构(Data Structure)：是相互之间存在一种或多种特定关系的数据元素的集合。 计算机系数据结构与算法设计全文共241页，当前为第7页。 数据结构主要指逻辑结构和物理结构 数据之间的相互关系称为逻辑结构。通常分为四类基本结构： 一、集合 结构中的数据元素除了同属于一种类型外，别无其它关系。 二、线性结构 结构中的数据元素之间存在一对一的关系。 三、树型结构 结构中的数据元素之间存在一对多的关系。 四、图状结构或网状结构 结构中的数据元素之间存在多对多的关系。 计算机系数据结构与算法设计全文共241页，当前为第8页。 数据结构的形式定义为：数据结构是一个二元组： Data-Structure=(D，S) 其中：D是数据元素的有限集，S是D上关系的有限集。 例 复数的数据结构定义如下： Complex=(C，R) 其中：C是含两个实数的集合 C1，C2 ，分别表示复数的实部和虚部。R={P}，P是定义在集合上的一种关系{〈C1，C2〉}。 数据结构在计算机中的表示称为数据的物理结构，又称为存储结构。 计算机系数据结构与算法设计全文共241页，当前为第9页。 数据对象可以是有限的，也可以是无限的。 　数据结构不同于数据类型，也不同于数据对象，它不仅要描述数据类型的数据对象，而且要描述数据对象各元素之间的相互关系。 抽象数据类型：一个数学模型以及定义在该模型上的一组操作。 　　抽象数据类型实际上就是对该数据结构的定义。因为它定义了一个数据的逻辑结构以及在此结构上的一组算法。 　　用三元组描述如下： 　　　（Ｄ，Ｓ，Ｐ） 计算机系数据结构与算 数据结构是计算机科学中至关重要的基础概念，它研究如何组织和管理数据，以便高效地进行信息处理。在第一章“绪论”中，我们了解到数据结构是关于数据的逻辑结构、物理结构及其相互关系的研究，目的是设计出高效算法来处理数据。 1.1 什么是数据结构 数据结构不仅仅是数据的简单集合，而是包含了数据元素之间的重要关系。通过实例，如电话号码查询系统，我们看到数据结构的选择直接影响到解决问题的算法设计和效率。数据结构可以是二维数组、表结构或向量等形式，每种结构都有其特定的运算算法。 1.2 基本概念和术语 - 数据(Data)：是信息的符号表示，是计算机程序处理的对象。 - 数据元素(Data Element)：数据的基本单位，可以是单一的或由多个数据项组成。 - 数据项(Data Item)：数据的不可分割的最小单位。 - 数据对象(Data Object)：性质相同的数据元素集合，是数据的子集。 - 数据结构(Data Structure)：是数据元素的集合，它们之间存在特定的关系，包括逻辑结构和物理结构。 - 逻辑结构：数据元素间的关系，如集合、线性结构、树型结构和图状结构。 - 物理结构：数据在计算机内存中的实际存储方式。 1.3 抽象数据类型(ADT) 抽象数据类型是数学模型与定义在模型上的一组操作。它定义了一个数据的逻辑结构和相关的操作集合，不涉及具体的实现细节。例如，复数数据结构定义了包含两个实数的集合，以及定义在该集合上的关系。 1.4 算法与算法设计 - 算法：解决特定问题的明确指令序列。 - 算法设计要求：清晰性、可行性、输入/输出、有限性。 - 算法效率的度量：通常通过时间复杂性和空间复杂性来评估。 - 算法的存储空间需求：除了运行时间，还需考虑内存使用。 数据结构与算法设计课程的核心是理解和应用各种数据结构（如链表、队列、栈、树、图等）以及设计高效的算法来解决实际问题。学习这门课程有助于提升编程能力，优化程序性能，并为开发大规模、复杂系统奠定坚实基础。