《《数据结构与算法》PPT课堂课件-第1章-引论》由会员分享，可在线阅读，更多相关《《数据结构与算法》PPT课堂课件-第1章-引论（33页珍藏版）》请在金锄头文库上搜索。
1、2021/6/13122021/6/13学学时时安安排排与与成成绩绩评评定定n总学时90 = 授课（72）+ 上机（18）n总评成绩 = 考试（70%）+ 平时成绩（10%）+上机（20%）32021/6/13为为什什么么要要学学习习数数据据结结构构 数数据据结结构构问问题题起起源源于于程程序序设设计计的的发发展展程程序序设设计计经经历历了了三三个个阶阶段段：1.1.无无结结构构阶阶段段：四四十十年年代代六六十十年年代代 程程序序设设计计主主要要针针对对科科学学计计算算，数数据据对对象象单单纯纯，程程序序以以算算法法为为中中心心， 程程序序设设计计技技术术以以机机器器语语言言、汇汇编编语语言言
2、的的机机制制为为基基础础2.2.结结构构化化程程序序设设计计阶阶段段：六六十十年年代代末末八八十十年年代代 认认识识到到程程序序设设计计的的规规范范性性，提提出出程程序序结结构构模模块块化化，以以功功能能为为中中心心 主主要要标标志志：19681968年年D.E.KnuthD.E.Knuth的的巨巨著著 “ “The art of computer programming” The art of computer programming” 的的发发表表 3.面面向向对对象象阶阶段段：八八十十年年代代初初兴兴起起，九九十十年年代代流流行行 数数据据是是程程序序的的“主主人人”，对对象象是是划划分
3、分与与构构造造程程序序的的主主要要单单位位 42021/6/13为为什什么么要要学学习习数数据据结结构构 从从6060年年代代末末到到7070年年代代初初，出出现现了了大大型型程程序序，软软件件也也相相对对独独立立，结结构构化化程程序序设设计计成成为为程程序序设设计计方方法法学学的的主主要要内内容容，人人们们就就越越来来越越重重视视数数据据结结构构，数数据据结结构构的的引引入入，对对程程序序设设计计的的规规范范化化起起到到重重大大作作用用。认认为为程程序序设设计计的的实实质质是是对对确确定定的的问问题题选选择择一一种种好好的的结结构构，加加上上一一种种好好的的算算法法: : 算算法法 + +
4、数数据据结结构构 = = 程程序序52021/6/13 数数据据结结构构作作为为一一们们独独立立的的课课程程在在国国外外是是从从1968年年开开始始设设立立的的。它它是是计计算算机机科科学学的的一一门门综综合合性性的的专专业业基基础础课课。它它不不仅仅是是一一般般程程序序设设计计的的基基础础，而而且且是是设设计计和和实实现现编编译译系系统统、操操作作系系统统、数数据据库库系系统统及及其其它它系系统统程程序序和和大大型型程程序序的的重重要要基基础础。 程程序序设设计计是是计计算算机机专专业业的的“入入门门课课” 数数据据结结构构课课程程是是计计算算机机软软件件课课程程系系列列中中最最主主要要的的
5、 “看看家家本本领领” 为为什什么么要要学学习习数数据据结结构构62021/6/13教教学学目目的的：n学习常常用用的的数数据据结结构构，熟悉各种基本数据结构的特点、存储表示、运算方法、典型应用；n了解每一种数据结构的使用代价和益处，培养同学根据实际问题的要求，选选择择合合适适的的数数据据结结构构设设计计算算法法的的能能力力；n掌握一些典典型型算算法法，培养算法分析的能力；n进行复杂程序设计的训练，解解题题能能力力和和技技巧巧的的训训练练是整个教学活动的重要环节；72021/6/13n第第1 1章章 引引 论论理解算法的概念。理解什么是程序，程序与算法的区别和内在联系。掌握算法的计算复杂性概念
6、。掌握算法渐近复杂性的数学表述。熟悉抽象数据类型的基本概念。熟悉数据类型和数据结构的概念。理解数据结构、数据类型和抽象数据类型三者的区别和联系。掌握用C语言描述数据结构与算法的方法。82021/6/13例例1 鸡鸡兔兔同同笼笼，鸡鸡脚脚 X 只只，兔兔脚脚 Y 只只，问问鸡鸡、兔兔各各几几只只？例例2 预预计计人人口口增增长长情情况况，现现有有人人口口13亿亿，要要在在5年年内内控控制制在在15亿亿以以内内，每每年年的的增增长长率率不不能能超超过过多多少少？数数学学模模型型：数数学学方方程程数数值值计计算算问问题题：92021/6/13非非数数值值计计算算问问题题例例1 图图书书管管理理系系统
7、统关关键键：如如何何有有效效组组织织图图书书？例例2 学学生生信信息息表表关关键键：如如何何合合理理存存放放记记录录？数学模型：数据结构102021/6/13第一章 引论n1.1 什么是数据结构 程序=数据结构+算法例1 书目自动检索系统登录号：书名：作者名：分类号：出版单位：出版时间：价格：书目卡片书目文件按书名按作者名按分类号索引表线性表112021/6/13 对对表表中中任任一一结结点点，与与它它相相邻邻且且在在它它前前面面的的结结点点最最多多只只有有一一个个（亦亦称称为为直直接接前前驱驱）； 与与表表中中任任一一结结点点相相邻邻且且在在其其后后的的结结点点也也最最多多只只有有一一个个（
8、亦亦称称为为直直接接后后继继）； 表表中中只只有有第第一一个个结结点点没没有有直直接接前前驱驱（亦亦称称为为开开始始结结点点）； 表表中中只只有有最最后后一一个个结结点点没没有有直直接接后后继继（亦亦称称为为终终端端结结点点）。逻逻辑辑特特征征：一一对对一一122021/6/13例2 人机对奕问题树.132021/6/13 若若将将从从对对弈弈开开始始到到结结束束的的过过程程中中所所有有可可能能出出现现的的格格局局都都画画在在一一张张图图上上，则则可可得得到到一一棵棵倒倒长长的的“树树”。“树树根根”是是对对弈弈开开始始之之前前的的棋棋盘盘格格局局，而而所所有有的的“叶叶子子”就就是是可可能能
9、出出现现的的结结局局，对对弈弈的的过过程程就就是是从从树树根根沿沿树树叉叉到到某某个个叶叶子子的的过过程程。逻逻辑辑特特征征：一一对对多多142021/6/13多叉路口交通灯管理问题CEDABABACADBABCBDDADBDCEAEBECED图152021/6/13101582551750810109220在在N个个城城市市之之间间建建立立通通信信网网络络问问题题：如如何何使使该该网网络络造造价价最最低低？逻逻辑辑特特征征：多多对对多多数据结构：图162021/6/13逻逻辑辑特特征征：多多对对多多 每每个个城城市市表表示示成成一一个个顶顶点点，城城市市之之间间的的通通信信线线路路表表示示成
10、成一一个个连连线线。若若干干个个顶顶点点及及其其连连线线构构成成一一个个图图的的结结构构。 不不同同的的连连线线方方法法得得到到不不同同的的图图，造造价价最最低低的的通通信信网网络络就就是是求求最最小小连连通通图图的的问问题题。172021/6/13数数据据组组织织的的特特点点：线线性性（一一对对一一）树树（一一对对多多）图图（多多对对多多）逻辑结构182021/6/13数据结构定义: 是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等等的学科192021/6/13n1.2 基本概念和术语数据（data)所有能输入到计算机中去的描述客观事物的符号数据元素（data
11、element）数据的基本单位，也称结点（node）或记录（record）数据项（data item）有独立含义的数据最小单位，也称域(field)数据结构（data structure)数据元素和数据元素关系的集合根据数据元素间关系的基本特性，有四种基本数据结构（集合）数据元素间除“同属于一个集合”外，无其它关系线性结构一个对一个，如线性表、栈、队列树形结构一个对多个，如树图状结构多个对多个，如图202021/6/13数据的逻辑结构只抽象反映数据元素的逻辑关系数据的存储（物理）结构数据的逻辑结构在计算机存储器中的实现212021/6/13 数数据据的的逻逻辑辑结结构构 数数据据的的存存储储结
12、结构构 数数据据的的运运算算：检检索索、排排序序、插插入入、删删除除、修修改改等等 线线性性结结构构 非非线线性性结结构构 顺顺序序存存储储 链链式式存存储储 线线性性表表栈栈队队树树形形结结构构图图形形结结构构数数据据结结构构的的三三个个方方面面：2021/6/13221.3 1.3 什什什什么么么么是是是是抽抽抽抽象象象象数数数数据据据据类类类类型型型型1 数数据据类类型型与与抽抽象象数数据据类类型型的的区区别别？2 抽抽象象数数据据类类型型如如何何定定义义？3 抽抽象象数数据据类类型型如如何何表表示示和和实实现现？ 讨讨论论：抽抽象象数数据据类类型型和和伪伪码码是是学学习习数数据据结结构
13、构的的工工具具2021/6/13231 数数据据类类型型与与抽抽象象数数据据类类型型的的区区别别数数据据类类型型：是是一一个个值值的的集集合合和和定定义义在在该该值值上上的的一一组组操操作作的的总总称称。抽抽象象数数据据类类型型：由由用用户户定定义义，用用以以表表示示应应用用问问题题的的数数据据模模型型。它它由由基基本本的的数数据据类类型型构构成成，并并包包括括一一组组相相关关的的服服务务（或或称称操操作作）它它与与数数据据类类型型实实质质上上是是一一个个概概念念，但但其其特特征征是是使使用用与与实实现现分分离离，实实行行封封装装和和信信息息隐隐蔽蔽（独独立立于于计计算算机机）2021/6/1
14、3242 抽抽象象数数据据类类型型如如何何定定义义抽抽象象数数据据类类型型可可以以用用以以下下的的三三元元组组来来表表示示： ADT = ADT = （D D，R R，P P）ADTADT抽抽象象数数据据类类型型名名 数数据据对对象象： 数数据据关关系系： 基基本本操操作作 ： ADT ADT抽抽象象数数据据类类型型名名ADT常常用用定定义义格格式式数数据据对对象象D D上上的的关关系系集集D D上上的的操操作作集集例例：给给出出自自然然数数(Natural Number )的的抽抽象象数数据据类类型型定定义义。ADT Natural_Number isobjects: 一个整数的有序子集合，
15、它开始于0，结束于机器能表示的最大整数 (MAX INT)functions: 对于所有的 x, y Natural_Number； TRUE, FALSE Boolean； +, -, , = = ,=等都是可用的服务。Zero ( )Zero ( )： NaturalNatural NumberNumber 返返回回 0 0IsZero(xIsZero(x) )： Boolean if (x=0) Boolean if (x=0) 返返回回TRUETRUE else else 返返回回 FALSEFALSEAdd(x, y)Add(x, y)： NaturalNatural NumberN
16、umber if (x+y = MAX INT)if (x+y = MAX INT)返返回回 x+yx+y else else 返返回回 MAX INTMAX INTSubtract(x,y): NaturalNatural NumberNumber if (xy)返返回回0 else 返返回回x-yEqual(x,y): Boolean Equal(x,y): Boolean if (x= y)if (x= y)返返回回TRUE else TRUE else 返返回回FALSEFALSESuccessor(x) : NaturalNatural NumberNumber if (x = MA
17、X INT)返返回回x else 返返回回x+1end Natural_Number 2021/6/13263 抽抽象象数数据据类类型型如如何何表表示示和和实实现现 抽抽象象数数据据类类型型可可以以通通过过固固有有的的数数据据类类型型（如如整整型型、实实型型、字字符符型型等等）来来表表示示和和实实现现。 即即利利用用处处理理器器中中已已存存在在的的数数据据类类型型来来说说明明新新的的结结构构，用用已已经经实实现现的的操操作作来来组组合合新新的的操操作作。 注注 ：它它有有些些类类似似C C语语言言中中的的结结构构（structstruct) )类类型型，但但增增加加了了相相关关的的服服务务。但
18、但上上机机时时要要用用具具体体语语言言实实现现，如如C C或或C+C+等等272021/6/13n1.4 算法的描述和算法分析简介算法（algorithm）解决某一特定问题的具体步骤的描述，是指令的有限序列算法特性算法的描述采用C语言算法的评价衡量算法优劣的标准n正确性(correctness)n可读性(readability)n健壮性(robustness)n效率与低存储量282021/6/13n评价算法的标准： 评价一个算法主要看这个算法所占用机器资源的多少，而这些资源中时间代价与空间代价是两个主要的方面，通常是以算法执行所需的机器时间和所占用的存储空间来判断一个算法的优劣。 292021
19、/6/13时间复杂度：基本操作重复执行的次数的阶数 T(n)=O(f(n)空间复杂度：S(n)=O(f(n)算算法法语语句句 对对应应的的语语句句频频度度 1 1forfor（i=0i=0；i n;i+i n;i+） n n 2 2 for for （j=0j=0；jn;j+jn;j+） n n2 2 3 cij=0; n 3 cij=0; n2 2 4 for (k=0;k n; k+) n 4 for (k=0;k=(y+1)*(y+1) y+;C312021/6/13n 空间效率的分析n 一个算法的空间效率是指在算法的执行过程中，所占据的辅助空间数量。辅助空间就是除算法代码本身和输入输出
20、数据所占据的空间外，算法临时开辟的存储空间单元。在有些算法中，占据辅助空间的数量与所处理的数据量有关，而有些却无关。后一种是较理想的情况。在设计算法时，应该注意空间效率。322021/6/13算算法法语语句句 1 1forfor（i=0i=0；i n;i+i n;i+） 2 2 for for （j=0j=0；jn;j+jn;j+） 3 cij=0; 3 cij=0; 4 for (k=0;k n; k+) 4 for (k=0;k n; k+) 5 cij=cij+aik*bkj; 5 cij=cij+aik*bkj; 使用的辅助空间为：cnn，所以其大小为：332021/6/13n习题：nP16 1.8, 1.9
