数据结构与算法概述.pptxVIP

写在前面的话本课程学习的是什么？学习在思考问题时，不仅按人的逻辑方式思考，也按计算机的逻辑思维方式思考学习在解决问题时，不仅考虑人的处理方式，也要考虑计算机的处理方式

为什么要学数据结构？数据结构研究什么？重新理解算法。如何分析算法的优劣？第一章概论

第一问题：

为什么要学数据结构DataStructure？

用计算机处理的实际问题可分为两大类问题：数值计算非数值计算数值计算问题： 在计算机发展初期，人们主要应用计算机来完成科学计算，即处理数值计算问题，对于这类问题，可以通过抽象出合适的数学模型，然后设计一个相应的算法来解决。在建筑设计时计算梁结构的应力要求解线性方程组预报人口增长情况时要求解微分方程等。非数值计算问题： 但是随着计算机应用领域的不断扩大，计算机更多地应用于处理非数值计算问题，这类问题涉及到数据元素间复杂的相互关系，一般无法用数学方程来描述。

线性关系：如列车中各车箱之间的关系、排队买车票人之间的关系、一叠盘子中各盘子之间的关系等。层次关系：如学校的组织结构、人的辈分关系等。网状关系：如城市铁路交通网、电话网、计算机网络等。020301现实中对象之间的关系

实际问题中对象之间的关系——

例1：学生成绩管理学号姓名大学英语C语言数据结构…A07001王萍908595…A07002马玲808590…A07003张兰959199…A07004李建708486…A07005黄勇827678…:：：：：：A07001王萍908595学生成绩表A07002马玲808590A07003张兰959199A07004李建708486A07005黄勇827678关系：线性特征：一个直接前趋，一个直接后继

实际问题中对象之间的关系例2：“井字棋”的人机对弈××OO××OOO××OOO××OOO××OOO××OOO××O×OO××OO×O…×××OOO×××OOO关系：树型特征：一个直接前趋，多个直接后继…

实际问题中对象之间的关系例3：交通图的最短路径问题A4A2A6A3A1A554798612关系：图型特征：多个直接前趋，多个直接后继

第一问题：

什么要学数据结构解决非数值问题的首要任务是选取一种合适的数据结构表示该问题，然后才考虑如何编写有效的算法。计算机处理的大多属于非数值计算问题。010302

第二问题

数据结构研究什么？

数据数据元素数据项几个基本概念

所有能被输入到计算机中，且能被计算机处理的符号(数值、字符等)的集合。1.数据:2.数据元素:如果把数据作为一个集合，则集合中的每一个独立“个体”称为数据元素。数据元素是数据结构中讨论的基本单位。数据集合中的所有数据元素的属性相同。

3.数据项例如：描述一个学生信息的数据元素称之为组合项年月日姓名学号班号性别出生日期入学成绩原子项数据元素也可以由若干数据项构成。

数据结构的研究内容研究数据之间的相互关系，即数据的组织形式，包括：数据元素之间的逻辑关系，也称为数据的逻辑结构(Logicalstructure)。数据元素及其关系在计算机存储器内的表示，称为数据的存储结构(storagestructure)。数据的运算，即基于某种存储结构对数据施加的操作或运算。

02带结构的数据元素的集合对于一个有相同特性的数据元素的集合，如果在数据元素之间存在一种或多种特定的关系，则称为一个数据结构。指的是数据元素之间存在的关系不同的“关系”构成不同的“结构”014.数据结构：

例如，IP地址（IPv4）是一个用四个3位的十进制数表示一个数据结构。166,111,102,2─a1(166),a2(111),a3(102),a4(2)则在数据元素a1、a2、a3和a4之间存在着“次序”关系?a1,a2?、?a2,a3?、?a3,a4?166,111,102,2a1a2a3a4111,166,102,2a2a1a3a4≠

又例，在2行3列的二维数组{a1,a2,a3,a4,a5,a6}中六个元素之间存在什么关系？行的次序关系:列的次序关系:row={a1,a2,a2,a3,a4,a5,a5,a6}col={a1,a4,a2,a5,a3,a6}a1a3a5a2a4a6a1a2a3a4a5a6 a1a2a3a4a5a6

5.分类从关系或结构分，数据结构可归结为以下四类:线性结构树形结构图状结构集合结构

数据结构包括“逻辑结构”和“物理结构”两个方面(层次):逻辑结构是对数据元素之间的逻辑关系的描述。它对应一个数据元素的