《数据结构与算法》PPT课堂课件-第1章-引论

1、2022/9/151算法与数据结构22022/9/15学时安排与成绩评定总学时90 = 授课（72）+ 上机（18）总评成绩 = 考试（70%）+ 平时成绩（10%）+上机（20%）32022/9/15为什么要学习数据结构 数据结构问题起源于程序设计的发展程序设计经历了三个阶段：1.无结构阶段：四十年代六十年代 程序设计主要针对科学计算，数据对象单纯，程序以算法为中心， 程序设计技术以机器语言、汇编语言的机制为基础2.结构化程序设计阶段：六十年代末八十年代 认识到程序设计的规范性，提出程序结构模块化，以功能为中心 主要标志：1968年D.E.Knuth的巨著 “The art of compu

2、ter programming” 的发表 3.面向对象阶段：八十年代初兴起，九十年代流行 数据是程序的“主人”，对象是划分与构造程序的主要单位 42022/9/15为什么要学习数据结构 从60年代末到70年代初，出现了大型程序，软件也相对独立，结构化程序设计成为程序设计方法学的主要内容，人们就越来越重视数据结构，数据结构的引入，对程序设计的规范化起到重大作用。认为程序设计的实质是对确定的问题选择一种好的结构，加上一种好的算法: 算法 + 数据结构 = 程序52022/9/15 数据结构作为一们独立的课程在国外是从1968年开始设立的。它是计算机科学的一门综合性的专业基础课。它不仅是一般程序设计

3、的基础，而且是设计和实现编译系统、操作系统、数据库系统及其它系统程序和大型程序的重要基础。 程序设计是计算机专业的“入门课” 数据结构课程是计算机软件课程系列中最主要的 “看家本领” 为什么要学习数据结构62022/9/15教学目的：学习常用的数据结构，熟悉各种基本数据结构的特点、存储表示、运算方法、典型应用；了解每一种数据结构的使用代价和益处，培养同学根据实际问题的要求，选择合适的数据结构设计算法的能力；掌握一些典型算法，培养算法分析的能力；进行复杂程序设计的训练，解题能力和技巧的训练是整个教学活动的重要环节；72022/9/15第1章 引 论理解算法的概念。理解什么是程序，程序与算法的区别

4、和内在联系。掌握算法的计算复杂性概念。掌握算法渐近复杂性的数学表述。熟悉抽象数据类型的基本概念。熟悉数据类型和数据结构的概念。理解数据结构、数据类型和抽象数据类型三者的区别和联系。掌握用C语言描述数据结构与算法的方法。82022/9/15例1 鸡兔同笼，鸡脚 X 只，兔脚 Y 只，问鸡、兔各几只？例2 预计人口增长情况，现有人口13亿，要在5年内控制在15亿以内，每年的增长率不能超过多少？数学模型：数学方程数值计算问题：92022/9/15非数值计算问题例1 图书管理系统关键：如何有效组织图书？例2 学生信息表关键：如何合理存放记录？数学模型：数据结构102022/9/15第一章 引论1.1

5、什么是数据结构 程序=数据结构+算法例1 书目自动检索系统登录号：书名：作者名：分类号：出版单位：出版时间：价格：书目卡片书目文件按书名按作者名按分类号索引表线性表112022/9/15 对表中任一结点，与它相邻且在它前面的结点最多只有一个（亦称为直接前驱）； 与表中任一结点相邻且在其后的结点也最多只有一个（亦称为直接后继）； 表中只有第一个结点没有直接前驱（亦称为开始结点）； 表中只有最后一个结点没有直接后继（亦称为终端结点）。逻辑特征：一对一122022/9/15例2 人机对奕问题树.132022/9/15 若将从对弈开始到结束的过程中所有可能出现的格局都画在一张图上，则可得到一棵倒长的“

6、树”。“树根”是对弈开始之前的棋盘格局，而所有的“叶子”就是可能出现的结局，对弈的过程就是从树根沿树叉到某个叶子的过程。逻辑特征：一对多142022/9/15多叉路口交通灯管理问题CEDABABACADBABCBDDADBDCEAEBECED图152022/9/15101582551750810109220在N个城市之间建立通信网络问题：如何使该网络造价最低？逻辑特征：多对多数据结构：图162022/9/15逻辑特征：多对多 每个城市表示成一个顶点，城市之间的通信线路表示成一个连线。若干个顶点及其连线构成一个图的结构。 不同的连线方法得到不同的图，造价最低的通信网络就是求最小连通图的问题。17

7、2022/9/15数据组织的特点：线性（一对一）树（一对多）图（多对多）逻辑结构182022/9/15数据结构定义: 是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等等的学科192022/9/151.2 基本概念和术语数据（data)所有能输入到计算机中去的描述客观事物的符号数据元素（data element）数据的基本单位，也称结点（node）或记录（record）数据项（data item）有独立含义的数据最小单位，也称域(field)数据结构（data structure)数据元素和数据元素关系的集合根据数据元素间关系的基本特性，有四种基本数据结构（集合）数

8、据元素间除“同属于一个集合”外，无其它关系线性结构一个对一个，如线性表、栈、队列树形结构一个对多个，如树图状结构多个对多个，如图202022/9/15数据的逻辑结构只抽象反映数据元素的逻辑关系数据的存储（物理）结构数据的逻辑结构在计算机存储器中的实现212022/9/15 数据的逻辑结构 数据的存储结构 数据的运算：检索、排序、插入、删除、修改等 线性结构 非线性结构 顺序存储 链式存储 线性表栈队树形结构图形结构数据结构的三个方面：2022/9/15221.3 什么是抽象数据类型1 数据类型与抽象数据类型的区别？2 抽象数据类型如何定义？3 抽象数据类型如何表示和实现？ 讨论：抽象数据类型和

9、伪码是学习数据结构的工具2022/9/15231 数据类型与抽象数据类型的区别数据类型：是一个值的集合和定义在该值上的一组操作的总称。抽象数据类型：由用户定义，用以表示应用问题的数据模型。它由基本的数据类型构成，并包括一组相关的服务（或称操作）它与数据类型实质上是一个概念，但其特征是使用与实现分离，实行封装和信息隐蔽（独立于计算机）2022/9/15242 抽象数据类型如何定义抽象数据类型可以用以下的三元组来表示： ADT = （D，R，P）ADT抽象数据类型名 数据对象： 数据关系： 基本操作 ： ADT抽象数据类型名ADT常用定义格式数据对象D上的关系集D上的操作集例：给出自然数(Natu

10、ral Number )的抽象数据类型定义。ADT Natural_Number isobjects: 一个整数的有序子集合，它开始于0，结束于机器能表示的最大整数 (MAX INT)functions: 对于所有的 x, y Natural_Number； TRUE, FALSE Boolean； +, -, , = = ,=等都是可用的服务。Zero ( )： Natural Number 返回 0IsZero(x)： Boolean if (x=0) 返回TRUE else 返回 FALSEAdd(x, y)： Natural Number if (x+y = MAX INT)返回 x+

11、y else 返回 MAX INTSubtract(x,y): Natural Number if (xy)返回0 else 返回x-yEqual(x,y): Boolean if (x= y)返回TRUE else 返回FALSESuccessor(x) : Natural Number if (x = MAX INT)返回x else 返回x+1end Natural_Number 2022/9/15263 抽象数据类型如何表示和实现 抽象数据类型可以通过固有的数据类型（如整型、实型、字符型等）来表示和实现。 即利用处理器中已存在的数据类型来说明新的结构，用已经实现的操作来组合新的操作。

12、注 ：它有些类似C语言中的结构（struct)类型，但增加了相关的服务。但上机时要用具体语言实现，如C或C+等272022/9/151.4 算法的描述和算法分析简介算法（algorithm）解决某一特定问题的具体步骤的描述，是指令的有限序列算法特性算法的描述采用C语言算法的评价衡量算法优劣的标准正确性(correctness)可读性(readability)健壮性(robustness)效率与低存储量282022/9/15评价算法的标准： 评价一个算法主要看这个算法所占用机器资源的多少，而这些资源中时间代价与空间代价是两个主要的方面，通常是以算法执行所需的机器时间和所占用的存储空间来判断一个算法的优劣。 292022/9/15时间复杂度：基本操作重复执行的次数的阶数 T(n)=O(f(n)空间复杂度：S(n)=O(f(n)算法语句 对应的语句频度 1for（i=0；i n;i+） n 2 for （j=0；jn;j+） n2 3 cij=0; n2 4 for (k=0;k=(y+1)*(y+1) y+;C312022/9/15 空间效率的分析 一个算法的空间效率是指在算法的执行过程中，所占据的辅助空间数量。辅助空间就是除算法代码本身和输入输出数据所占据的空间外，算法临时开辟的存储空间单元。在有些