数据结构与算法概述

《数据结构与算法概述》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、写在前面的话n本课程学习的是什么？学习在思考问题时，不仅按人的逻辑方式思考，也按计算机的逻辑思维方式思考学习在解决问题时，不仅考虑人的处理方式，也要考虑计算机的处理方式第一章概论为什么要学数据结构？数据结构研究什么？重新理解算法。如何分析算法的优劣？第一问题：为什么要学数据结构DataStructure？n用计算机处理的实际问题可分为两大类问题：¨数值计算¨非数值计算n数值计算问题：在计算机发展初期，人们主要应用计算机来完成科学计算，即处理数值计算问题，对于这类问题，可以通过抽象出合适的数学模型，然后设计一个相应的算法来解决。•在建筑设计时计算梁结构的应力要求解线性方程组•预报人

2、口增长情况时要求解微分方程等。•非数值计算问题：但是随着计算机应用领域的不断扩大，计算机更多地应用于处理非数值计算问题，这类问题涉及到数据元素间复杂的相互关系，一般无法用数学方程来描述。现实中对象之间的关系n线性关系：如列车中各车箱之间的关系、排队买车票人之间的关系、一叠盘子中各盘子之间的关系等。n层次关系：如学校的组织结构、人的辈分关系等。n网状关系：如城市铁路交通网、电话网、计算机网络等。实际问题中对象之间的关系——学生成绩表例1：学生成绩管理大学英C语数据结学号姓名…语言构n关系：线性A07001王萍908595…A07002马玲808590…n特征：一个直接前趋，A070

3、03张兰959199…一个直接后继A07004李建708486…A07005黄勇827678…:：：：：：A07001A07002A07003A07004A07005王萍马玲张兰李建黄勇908095708285859184769590998678实际问题中对象之间的关系n例2：“井字棋”的人机对弈关系：树型××特征：一个直接前趋，O多个直接后继O××O××××××××OOOOOOOOOOOOOO××O××O××××××O…OO…×OO×OOOOO实际问题中对象之间的关系n例3：交通图的最短路径问题关系：图型特征：多个直接前趋，多个直接后继A6745A2A489A112A3A56第

4、一问题：什么要学数据结构计算机处理的大多属于非数值计算问题。解决非数值问题的首要任务是选取一种合适的数据结构表示该问题，然后才考虑如何编？写有效的算法。第二问题数据结构研究？什么几个基本概念1.数据2.数据元素3.数据项1.数据:所有能被输入到计算机中，且能被计算机处理的符号(数值、字符等)的集合。2.数据元素:如果把数据作为一个集合，则集合中的每一个独立“个体”称为数据元素。数据元素是数据结构中讨论的基本单位。数据集合中的所有数据元素的属性相同。3.数据项数据元素也可以由若干数据项构成。例如：描述一个学生信息的数据元素姓名学号班号性别出生日期入学成绩年月日原子项称之为组合项数据

5、结构的研究内容n研究数据之间的相互关系，即数据的组织形式，包括：¨数据元素之间的逻辑关系，也称为数据的逻辑结构(Logicalstructure)。¨数据元素及其关系在计算机存储器内的表示，称为数据的存储结构(storagestructure)。n数据的运算，即基于某种存储结构对数据施加的操作或运算。4.数据结构：对于一个有相同特性的数据元素的集合，如果在数据元素之间存在一种或多种特定的关系，则称为一个数据结构。带结构的数据元素的集合指的是数据元素之间存在的关系不同的“关系”构成不同的“结构”例如，IP地址（IPv4）是一个用四个3位的十进制数表示一个数据结构。166,111,1

6、02,2─a1(166),a2(111),a3(102),a4(2)则在数据元素a1、a2、a3和a4之间存在着“次序”关系a1,a2、a2,a3、a3,a4166,111,102,2≠111,166,102,2a1a2a3a4a2a1a3a4又例，在2行3列的二维数组a1a2a3{a1,a2,a3,a4,a5,a6}中六个元素之间存在什么关系？a4a5a6行的次序关系:row={,,,}列的次序关系:col={,,}a1a3a5a1a2a3a2a4a6a4a5a65.分

7、类从关系或结构分，数据结构可归结为以下四类:线性结构树形结构图状结构集合结构6.逻辑结构和物理结构数据结构包括“逻辑结构”和“物理结构”两个方面(层次):逻辑结构是对数据元素之间的逻辑关系的描述。它对应一个数据元素的集合和定义在此集合上的若干关系;物理结构是逻辑结构在计算机中的表示和实现，故又称“存储结构”。7.数据结构的存储结构—逻辑结构在存储器中的映象“数据元素”的映象所有数据元素都映象为二进制位串(321)10=(501)8=(101000001)2A=(101)8=(00