《计算机软件技术基础 教学课件 ppt 作者 李金 第1章_数据结构》由会员分享，可在线阅读，更多相关《计算机软件技术基础 教学课件 ppt 作者 李金 第1章_数据结构（394页珍藏版）》请在金锄头文库上搜索。
1、计算机软件技术基础,哈尔滨工程大学 李金 教授,第1章 数据结构,1.1 绪论 1.2 线性数据结构及其应用 1.3 递归与非线性数据结构 1.4 内部排序 1.5 查找,1.1 绪论,1.1.1 数据结构产生的背景 1.1.2 什么是数据结构 1.1.3 数据结构的重要性 1.1.4 基本概念和术语 1.1.5 算法和算法分析,1.1.1 数据结构产生的背景,计算机科学和软件工程的惊人发展使计算机的应用已渗透到各个领域，十分有效地解决了数值计算的各种问题。 但是，解决数值问题的许多理论、方法和技术一般不适应于解决诸如数据的分类与查找、情报检索、数据库、企业管理、系统工程、图形图像处理、人工智
2、能以及日常生活等各领域的非数值处理问题。 计算机若要也能有效地处理这些非数值问题，就需要探索新的方法和技术。 “数据结构”就是为研究和解决这些非数值问题而提出的理论和方法，是解决这些问题的重要基础知识。,1.1 绪论,1.1.1 数据结构产生的背景 1.1.2 什么是数据结构 1.1.3 数据结构的重要性 1.1.4 基本概念和术语 1.1.5 算法和算法分析,1.1.2 什么是数据结构,从提出一个实际问题到计算机解出答案需有经过下列步骤： 首先从实际问题中抽取出数学模型， 然后设计相应的算法， 再编程序、调试、求解。 抽取数学模型的过程，就是提取操作的对象以及这些操作对象之间的关系 并不是所
3、有的实际问题都能抽象出数学方程这种形式，三个例子：,例1.1 学生入学情况简表,表1.1 学生入学情况简表,这是一张二维表，其中每行均是一名学生的有关情况。要查找某人的情况只能用顺序检索的方法，显然这不是好的办法。,例1.2 学校组织体系,在这种情况下，各数据元素之间的逻辑关系就不是线性的，所以应采用树型结构分级管理，如图1.1所示。,要查找某位教师，可顺着“系教研室个人”的路线往下查找，显然，这种结构便于检索。,图 1.1 学校组织体系示意图,例1.3 部分城市公路交通网,因为任意两个城市之间都可能有公路相通，所以，这是一种比树形结构更为复杂的数据结构，称其为图结构。,图 1.2 部分城市公
4、路交通网,1.1.2 什么是数据结构,图 1.2 部分城市公路交通网,从上面三个例子可以看出，描述这样一类问题的数学模型不再是数值方程，而是诸如表、树、图等非数值处理的数据结构及其运算。对数据进行不同的组织，形成不同的结构。,表1.1 学生入学情况简表,图 1.1 学校组织体系示意图,1.1.2 什么是数据结构,数据结构 是一门研究非数值应用型程序设计中的对象以及它们之间的关系和运算等等的学科 即研究数据的 逻辑结构、 物理结构以及 适合这些结构的运算方法， 研究各种结构在计算机科学中的应用等问题。,1.1 绪论,1.1.1 数据结构产生的背景 1.1.2 什么是数据结构 1.1.3 数据结构
5、的重要性 1.1.4 基本概念和术语 1.1.5 算法和算法分析,1.1.3 数据结构的重要性,程序设计语言大体可以分成两类： 以程序为中心 侧重于建立程序， 程序是在简单数据结构上进行复杂运算， 适合于数值计算问题。,1.1.3 数据结构的重要性,程序设计语言大体可以分成两类： 以数据为中心， 把数据结构作为问题的中心部分（如数据库）， 而程序则围绕数据结构进行加工，它时尔查询，时尔对数据进行修改， 这类系统要求采用复杂的数据结构来描述系统的状态。 可以说，程序设计以数据为中心的观点对数据结构的发展起到了推动作用。,1.1.3 数据结构的重要性,近几十年来，由于社会生产力的高速发展，新技术不
6、断涌现，信息量急剧膨胀，迫使人们对信息的处理和数据的利用不得不实行自动化、网络化和社会化，也就是说整个人类社会进入了信息化的时代， 计算机在企业部门和经济部门的管理工作中发挥了巨大的作用，如情报检索、企业管理、数据处理、数据库、网络通讯、人工智能等。,1.1.3 数据结构的重要性,在这些领域中，数据结构是重要的基础和有效的手段。 因为计算机所处理的信息决不是杂乱无章的数据堆积，而是存在着内部联系的，只有分析清楚它们之间的内在联系并采取适当的结构，才能对数据进行行之有效的处理。 因此，单纯依靠程序设计人员的经验和技巧已不能编出高效率的处理程序，必须对程序设计方法进行系统的研究，这不仅涉及到程序的
7、结构和算法，也包含了研究程序所加工的对象数据的结构。 也就是说，为解决给定的问题而设计的程序，其有效性、清晰性和复杂性同程序中用到的数据的组织形式，即所选取的数据结构有着密切的联系。,1.1.3 数据结构的重要性,应该指出的是，算法和数据结构之间存在着本质的联系： 因为研究某种类型的数据结构时总是离不开要讨论加于这种数据结构之上的运算（如插入、删除等）， 只有通过某种算法实现这些运算，数据结构才能体现出它的意义和作用； 反之，当研究某种算法时也离不开要考虑该算法处理对象所采取的数据结构。,1.1.3 数据结构的重要性,目前在我国，数据结构已经不仅仅是计算机专业的核心课程之一，而且，是其它非计算
8、机专业的主要选修课甚至是必修课之一。,图 1.3 数据结构的地位,1.1.3 数据结构的重要性,数据结构在计算机科学中是一门综合性的专业基础课。 数据结构的研究不仅涉及到计算机硬件（特别是编码理论、存储器和存取方法等）的研究范围，而且是和计算机软件的研究有着更密切的联系。 在研究信息检索时也必须考虑如何组织数据,因此，可以认为数据结构是介于数学、计算机硬件和计算机软件三者之间的一门核心课程（如图1.3所示）。,1.1.3 数据结构的重要性,数据结构不仅是一般程序设计（特别是非数值应用型程序设计）的基础，而且是设计和实现编译程序、操作系统以及其它系统程序和大型应用程序的重要基础。 近年来，数据库
9、和人工智能的发展大大促进了数据结构的研究，但对非计算机专业来说，数据结构主要侧重于实践技术和应用。 本章列举了许多应用例子并附有上机调试通过的程序，以帮助理解和应用。,1.1 绪论,1.1.1 数据结构产生的背景 1.1.2 什么是数据结构 1.1.3 数据结构的重要性 1.1.4 基本概念和术语 1.1.5 算法和算法分析,1.1.4 基本概念和术语,数据：是描述客观事物的 数、 字符、 图形、 声音、 所有能输入到计算机中并被计算 机程序处理的符号的集合。 编译程序所使用的数据则是程序 员编写的源程序。,1.1.4 基本概念和术语,数据项 数据项是数据的最小单位，是不可再分的。 例如，表1
10、.1中每一行中的每一项如学号、姓名等均为数据项。 数据元素 是数据的基本单位，即数据集合中的一个个体。 有时一个数据元素可由若干个数据项组成。 例如，表1.1中每一行为一个数据元素，它由准考证号、姓名等数据项组成。,表1.1 学生入学情况简表,1.1.4 基本概念和术语,数据对象：性质相同的数据元素的集合。 例如，表1.1所示的整个一张表就是一个数据对象，它由每一个学生的情况组成； 又例如，整数的集合N0，1，2，；一周七天的集合DateSunday，Monday，Saturday。 N和Date都是数据对象， 而其中的单个项0，1，或Sunday，Monday等都是数据元素， 这种情况下数据
11、元素由单个数据项组成。,1.1.4 基本概念和术语,数据结构：通常数据对象中的元素不是孤立的，而是彼此之间存在着某种联系，数据元素相互之间的这种关系就称为数据的结构。 数据的逻辑结构 数据的物理结构,1.1.4 基本概念和术语,数据的逻辑结构：用计算机处理数据时，首先应该很好地研究数据元素之间的相互关系，选用一个合适的结构将这些数据组织起来，以便于提高程序编制的质量和计算机运行的效率。 数据元素之间的逻辑关系叫做数据的逻辑结构。 数据的逻辑结构有多种形式，大体上分： 线性：表、堆栈、队列、链表等 非线性：树、图等 对于各种逻辑结构要定义相应的运算，常见的运 算有：插入、删除、检索、更新、排序等
12、。,1.1.4 基本概念和术语,数据的物理结构：也称存储结构，它是数据的逻辑结构在计算机中的映象（或表示）。 由于映象的方法不同，数据元素之间的关系在计算机中有两种不同的表示： 顺序映象 顺序存储结构 两种不同的存储结构 非顺序映象 非顺序存储结构 （也称链式存储结构）,1.1.4 基本概念和术语,顺序存储结构是把逻辑上相邻的结点存储在物理上相邻的存储单元上； 链式存储是给每个结点附加一个指针域，存放它后继结点的地址（即指针），由指针把各数据元素链接起来，故指针也就是链。 后继结点可以是一个也可以是多个，也就是说链可 以是单链，也可以是多链，随数据的逻辑结构而定。 在链式存储中由于有了指针，所
13、以物理结构不一定 与该数据的逻辑结构相同。,1.1.4 基本概念和术语,任何一个算法在编制程序之前首先需选择合适的存储结构 同一运算在不同的存储结构中实现的方法不同 因此，对程序设计而言，数据的逻辑结构和物理结构是紧密相连的两个方面，在有些数据结构的书中并不严格区分之,1.1.5 算法和算法分析,1.1.1 数据结构产生的背景 1.1.2 什么是数据结构 1.1.3 数据结构的重要性 1.1.4 基本概念和术语 1.1.5 算法和算法分析,1.1.5 算法和算法分析,1. 算法 2. 算法语言的说明 3. 评定良好算法的标准,1. 算法,算法（Algorithm）是对特定问题求解步骤的一种描述
14、，它是指令的有限序列，其中每一条指令表示一个或多个操作。 算法具有 有穷性、 确定性、 可行性、 输入和输出等特性。,1.1.5 算法和算法分析,1. 算法 2. 算法语言的说明 3. 评定良好算法的标准,2. 算法语言的说明,由于研究数据结构的目的是为了更好地进行程序设计，所以本章在讨论各种数据结构的基本运算的算法时都给出了用TURBO C实现的程序。 C语言是一种结构式的语言，便于进行模块化程序设计，它在处理非数值型数据方面有较强的功能，并且，其数据类型丰富，特别是指针型变量在处理非线性的数据结构（如树和图等）及数据的链式存储都很方便。,1.1.5 算法和算法分析,1. 算法 2. 算法语
15、言的说明 3. 评定良好算法的标准,3. 评定良好算法的标准,前面已经讲过，研究数据结构的目的是为了要很好地组织数据，寻求合理的存储结构和算法。因而，评定一个良好算法的标准是： （1）正确性即设计或选择的算法应当能正确地反映某种需求。 （2）结构清晰即具有良好的可读性，难懂的程序易于隐藏较多的错误而难于调试和修改。 （3）健壮性即当输入数据非法时，算法也能适当地作出反应或进行处理，而不会产生莫名其妙的输出结果。,3. 评定良好算法的标准,（4）效率即应考虑依据算法编制成的程序在计算机中运行时所消耗的时间。 程序在计算机上运行时所耗费的时间取决于下列因素： 程序运行时所需输入的数据总量，即问题的
16、规模； 计算机执行每条指令所需时间； 程序中的指令重复执行的次数。 前两条依赖于计算机的软、硬件资源，如果计算机可以进行脱机输入，则输入数据的时间可以忽略不计。 因此，习惯上常常把语句重复执行的次数，称为语句的频度，作为算法的时间量度。,3. 评定良好算法的标准,举例：通过判定程序段中重复执行次数最多的语句的频度来估算算法的时间复杂度，记作T(n)，n为问题的规模。 xx+1 1 FOR (i1;i=n;i+) xx+1 n FOR (i1;i=n;i+) FOR (j1;j=n;j+) xx+1 n2 其中，语句的频度如上右列所示。 记号“”：(n2)则表示当n较大时，该程序的运行时间和n2成正比，或者说T(n)的数量级和n2的数量级相同。 因此，上述三
