《数据结构》第4版高职全套教学课件.pptx

;目录;学习目标;;1.1数据结构的发展;1968年，美国的唐纳德·欧文克努特(DonaldE.Knuth)教授在他的历史性经典巨著《计算机程序设计艺术》(TheArtofComputerProgramming)第一卷《基本算法》中较系统地阐述了数据结构的逻辑结构和存储结构及其操作，开创了数据结构的课程体系。20世纪70年代初，数据结构作为一门独立的课程进入大学课堂。在我国，自1978年美籍华裔学者冀中田在国内首开这门课程以来，经过几十年的发展，该课程已经成为各大学计算机专业的学科主干课程，也成为非计算机专业学生学习计算机的主要选修课程之一。;;数据结构是一门综合性很强的专业基础课，是介于数学、计算机硬件和计算机软件三者之间的一门核心课程。

瑞士计算机科学家沃斯(N.Wirth)曾提出：

程序＝数据结构+算法;;1.3.1基本概念和术语;5.数据类型

数据类型(DataType)是一组性质相同的值的集合和定义在该值集上的一组操作的总称。每个数据项属于某一确定的数据类型。按“值”的特性不同，高级程序设计语言中的数据类型可以分为两类：

(1)原子类型：其值不可分解。例如，C语言中的整型、实型和字符型等。

(2)结构类型：其值通常可以分解成为若干个成分。它的成分可以是非结构的，也可以是结构的，如数组类型和结构类型等。

6.数据结构

数据结构(DataStructure)是指相互之间存在一定关系的数据元素的集合。数据结构包含三方面的内容：数据的逻辑结构、数据的存储结构和数据的运算。算法的设计取决于选定的数据的逻辑结构，算法的实现取决于数据的存储结构。数据的运算定义在数据的逻辑结构上，实现在数据的存储结构上。;1.3.2数据的逻辑结构;1.线性结构

数据元素之间存在着一对一的关系。线性结构中有且仅有一个首结点和一个尾结点，首结点只有一个直接后继结点，尾结点只有一个直接前驱结点，其他结点有且仅有一个直接前驱结点和一个直接后继结点。如图1.1(a)所示。;2.非线性结构

非线性结构可细分为以下几部分：

(1)集合：数据元素之间同属于一个集合，除此之外没有其他关系。如图1.1(b)所示。它是数据结构的一个特例，本书不予讨论。

(2)树形???构：数据元素之间存在着一对多的关系。如图1.1(c)所示。

在现实生活中，部门的组织结构、棋盘对弈格局、体育比赛赛制安排和家谱等问题都可以用树形结构来描述。

(3)图结构：数据元素之间存在着多对多的关系。如图1.1(d)所示。

当数据元素间有着多对多关系时，形成图结构。例如，交通和网络布线等许多问题模型都属于图结构。;1.3.3数据的存储结构;1.3.4抽象数据类型;;1.4.1算法;2.算法设计的要求

一个问题可以有多种算法，一个“好”算法应该具有以下几个方面的基本特性：

(1)正确性

正确性是设计一个算法的首要条件，所设计的算法要满足具体问题的要求。在输入合法的数据时，算法能在有限的时间内得到正确的结果。

可以理解为以下四个层次：

①程序不含语法错误。

②程序对几组输入数据能给出满足规格说明要求的结果。

③程序对精心选择的、典型的、苛刻而有刁难性的几组输入数据能给出满足规格说明要求的结果。

④程序对一切合法的输入数据都能给出满足规格说明要求的结果。;(2)可读性

一个好的算法首先要便于人们阅读、理解，其次才是计算机可以执行。可读性是软件开发的一项重要原则，算法的可读性好，则其可维护性也强。

(3)健壮性

当输入不合法的数据时，算法应该给出相应的处理结果，而不是产生错误动作或是陷入瘫痪。

(4)高效率和低存储量

效率是指算法的执行时间。对于解决一个特定问题的不同算法，执行时间短的算法效率高。存储量是指算法执行过程中所需要的最大存储空间。这二者与输入的规模和输入数据的性质有关。设计时应尽量选择高效率和低存储量的算法。;1.4.1算法;1.4.2算法分析;(2)事前分析

事前分析方法不上机运行根据算法编制的程序，而是依据统计方法对算法执行时间进行估算。

程序在计算机上运行的影响因素有：

①机器执行指令的速度。

②算法本身选用的策略。

③编译产生的机器代码质量。

④输入算法的数据量，称为问题规模，问题规模越大，耗时越多。

⑤书写程序的语言，语言越高级，耗时越多。

;当算法采用不同的编译系统、不同的策略及不同的编程语言在不同的计算机上运行时，其效率均会不同。所以，不宜使用绝对时间衡量算法效率。因此，最重要的因素是问题规模。

一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，所花费的时间就多。

一般情况下，