计算机科学概论（微课版）· 第6章 数据结构 · 教学课件

高等学校计算机专业核心课程精品系列教材计算机科学概论（微课版）第6章数据结构数据表示·数组·链表·结构体·抽象数据类型数据不能杂乱地堆在存储设备里。本章从旅行信息整理与成绩管理两个例子出发，认识四类基本结构，吃透数组、链表与结构体，再抽象出栈、队列、树、图四种数据类型。图6-13树（教材第108页）LEARNINGGOALS学习目标与知识导图第6章知识导图（教材第98页）本章学习目标❶理解数据结构的定义及其在计算机科学中的重要性；❷掌握集合、线性、树状、图状四类结构的特点与应用场景；❸理解数组的定义、操作及多维数组的应用；❹掌握链表的定义、操作及其与数组的比较；❺理解结构体在组织复杂数据时的应用。能力落点：为编程实践和算法设计打下数据结构基础。计算机科学概论（微课版）｜第6章数据结构02CONTENTS本章目录6.1数据表示及数据结构信息世界层的数据表示｜四类基本结构6.2数组数组的定义｜数组的操作｜多维数组6.3链表数组与链表｜链表的操作｜链表的类型6.4结构体结构体的定义｜结构体的操作｜结构体数组6.5抽象数据类型定义｜栈｜队列｜树｜图章末6.6本章小结｜6.7拓展知识｜6.8课后习题计算机科学概论（微课版）｜第6章数据结构036.1数据表示及数据结构·导入信息世界层的数据表示情境：旅行爱好者的信息困境你热爱旅行，每次出行都收集大量信息：景点介绍、交通安排、餐厅推荐……旅行越来越多，信息变得杂乱无章，甚至在目的地迷路——找不到当初记下的重要信息。解决办法：为每次旅行建一个目的地文件夹，下设景点、交通、餐厅、照片子文件夹，再用电子表格记录每日行程。需要时打开对应文件夹即可。这个做法，正是"信息世界层的数据表示"文件夹按目的地归拢信息→计算机中的目录结构电子表格每日行程逐行排列→计算机中的线性结构子文件夹嵌套按天再按上下午细分→计算机中的树状结构好的数据表示，让信息更有结构性、更容易访问——无论旅行还是数字世界。计算机科学概论（微课版）｜第6章数据结构046.1数据表示及数据结构·分类数据结构的四种基本类型数据结构：相互之间存在一种或多种特定关系的数据元素的集合。按关系的不同特征，分为4种基本类型。①集合结构——元素间仅"同属一个集合"，别无关系。例：保存旅行笔记的文件夹；计算机中的结构体。②线性结构——元素间一对一。例："每日行程安排"逐日相接；计算机中的数组、链表。③树状结构——元素间一对多。例：照片按"天→上/下午景点"分层收纳，如一棵树不断分叉。④图状（网状）结构——元素间多对多。例：城市为节点、铁路为连线，每城可与多城相连。图6-1树状结构（教材第99页）图6-2图状结构（教材第100页）计算机科学概论（微课版）｜第6章数据结构056.2数组·定义数组：一个名字管住一批数据情境：开发学生成绩管理系统，要存100名学生的数学成绩。定义mathScores0…mathScores99共100个独立变量？太笨拙——我们希望它们同属一个数据结构，用1个名字统一操作。数组的定义数组是元素的顺序集合，元素通常具有相同的数据类型。用"数组名[索引]"（索引从0开始）表示任意元素：mathScores[0]、mathScores[1]…即第1、2…名学生的成绩。图6-3数组（教材第100页）连续存储：mathScores[i]与mathScores[i+1]在内存中地址相邻。100个成绩一次性存入内存，用索引随取随用——这就是数组的威力。计算机科学概论（微课版）｜第6章数据结构066.2数组·操作数组的两大基本操作①创建数组：先定大小·数组连续存储，创建时必须指定大小，申请一整块连续空间；·已知学生恒为100名→创建大小为100的数组；·若人数事先未知，就无法保证数组装得下——定长是数组的硬约束。②访问元素：索引直达·读/改第20名学生的成绩：直接用mathScores[19]；·索引访问是一步到位的，无需逐个翻看；·比管理100个独立变量高效、简洁、易维护。例：循环求平均分令循环变量i从0递增到99，循环体中把mathScores[i]累加进sum；循环结束后sum÷100即得平均分。若用100个独立变量，同样的累加需要手写100行代码——数组+循环，一段代码通吃。计算机科学概论（微课版）｜第6章数据结构076.2数组·多维数组多维数组：数组的数组学生不只考数学，还有语文、英语……用二维数组studentScores：每一行是一名学生，每一列是一门科目。studentScores[0][0]、[0][1]、[0][2]即第1名学生的语文、数学、英语成绩。图6-4二维数组（教材第101页）两个看二维数组的视角·本质：数组的数组——每个元素本身又是一个数组；·直观：一张二维表格，行=学生，列=科目。行扫与列扫：两类典型统计·求某学生的各科总分：循环遍历这一行的所有元素并累加；·求某科目的全班平均分：循环遍历这一列，累加后除以总行数。计算机科学概论（微课版）｜第6章数据结构086.3链表·数组与链表为什么需要链表情境：班主任保存"谈话学生列表"。月考后顺序频繁调整——不及格的要插队提前，考进前50名的要删除，谈完一个删一个。数组能胜任吗？不能。图6-5删除数组元素（教材第102页）数组删除的两大代价·删掉元素33后，其后所有元素前移一格，计算开销大；·数组大小固定，尾部空出的位置白白浪费。图6-6链表（教材第102页）链表：用指针串起来的集合·每个元素（节点）=数据data+下一节点地址next指针；·最后一个节点的next为空地址NULL；·节点在内存中不必相邻，靠指针串联；·只需保存头节点地址，即可访问整个链表。计算机科学概论（微课版）｜第6章数据结构096.3链表·操作链表操作：访问、插入、删除①访问：只能从头遍历没有索引可用：从头节点出发，沿next指针逐节点前进。找第3个节点，必须先经过第1、2个。②插入：改两个指针·非头部插入：前节点next→新节点；新节点next→后节点；·头部插入：新节点next→原头节点，再更新头节点指针；·就像对小明说"你的下一个是小刚"，对小刚说"你的下一个是小红"。③删除：前节点next改为指向后节点；删头节点则改头指针。"你的下一个不是小刚，而是小红"——小刚即被剔除。图6-7链表的插入和删除（教材第103页）关键：插入与删除都不需要搬动数据，只改指针——这正是链表对数组的最大优势。计算机科学概论（微课版）｜第6章数据结构106.3链表·类型链表的四种类型图6-8链表的类型（教材第103页）①单向链表：只有next指针，从头向后遍历（上图6-8a）。②循环链表：末节点next指向头节点，首尾相接成环，支持循环遍历。③双向链表：每节点含pre+data+next，可正反向遍历（上图6-8c）。④双向循环链表：兼具双向与循环的结构。能力越强，代价越高·遍历方式越多，结构越复杂；·例：删除双向链表的非头尾节点，既要改前节点的next，又要改后节点的pre；·代码更难写，运行也更慢。杀鸡焉用牛刀班主任的谈话列表只需"找下一个"，单向链表足矣——按任务需求选择最合适的结构。计算机科学概论（微课版）｜第6章数据结构116.4结构体·定义与操作结构体：把相关的不同类型绑在一起二维数组的两个软肋·[0][0]是语文还是数学？索引不表意，对应关系全靠记；·数组只能存同类型数据——没法让"小明"（字符串）和95（整数）住进同一个数组。结构体的定义由一组称为成员的不同数据组成，成员可各具类型；成员有名字，用点操作符访问：studentI、studentInfo.score。三步走：①定义结构体类型（studentInfoType：stringname+intscore）→②创建该类型的变量studentInfo→③用"."读写成员。C++代码（教材第104页）structstudentInfoType{stringname;intscore;};studentInfoTypestudentInfo;studentI="小明";studentInfo.score=95;cout<<studentI<<endl;cout<<studentInfo.score<<endl;计算机科学概论（微课版）｜第6章数据结构126.4结构体·结构体数组结构体数组：100名学生全装下一个studentInfo只装一名学生。创建大小为100的数组studentInfos，每个元素都是一个含name和score的结构体——100名学生的姓名与成绩各就各位。图6-9结构体数组（教材第105页）例：统计全班平均分循环变量i从0到99，循环体中累加studentInfos[i].score，最后除以100。索引定位"哪个人"，成员名定位"哪项数据"。三种结构，各归其位·数组：同类型数据的顺序集合；·结构体：相关但不同类型的组合；·结构体数组：两者叠加，程序更有组织、更易理解。计算机科学概论（微课版）｜第6章数据结构136.5抽象数据类型·定义抽象数据类型（ADT）情境：开发社交媒体平台——动态按最新显示、私信按序到达、动态分文件夹收纳、用户互加好友。四种需求，恰好对应栈、队列、树、图四种抽象数据类型。定义：数据+操作的封装体抽象数据类型=与对该数据类型有意义的操作封装在一起的数据类型。定义包含三部分：数据的定义、操作的定义、封装数据和操作。·模型内部：数据结构（数组、链表）+操作（公有/私有）；·应用程序只能通过接口调用公有操作；·私有操作仅供内部使用，实现细节对外隐藏。图6-10抽象数据类型的模型（教材第106页）思想：使用者只关心"能做什么"，不必关心"怎么实现"。计算机科学概论（微课版）｜第6章数据结构146.5抽象数据类型·栈栈：后进先出（LIFO）情境：微博首页要按"新→旧"显示动态——新动态入栈压到栈顶，浏览时从栈顶依次出栈。插入与删除只在同一端（栈顶）进行，这就是栈。图6-11栈的三个示例（教材第106页）四个基本操作①建立一个空栈；②在栈顶插入一个元素（入栈）；③取出栈顶元素（出栈）；④检查栈是否为空。典型应用：倒转数据把(2,4,7,1,6,8)依次入栈再依次出栈，得到(8,6,1,7,4,2)。微博动态"逆时间显示"，本质就是一次数据逆序。计算机科学概论（微课版）｜第6章数据结构156.5抽象数据类型·队列队列：先进先出（FIFO）情境：私信功能——新到的私信插入队尾保存，查看时从队首取出最早一条。插入与删除分别在两端进行，这就是队列。图6-12队列的两个示例（教材第107页）四个基本操作①创建一个空队列；②在尾部插入元素（入列）；③在头部取出元素（出列）；④检查队列是否为空。典型应用：打印缓冲打印机慢、计算机快：待打印任务一次性放入打印队列缓冲，计算机转头去干别的，打印机按先来后到从队首取任务慢慢打——快慢解耦，互不等待。计算机科学概论（微课版）｜第6章数据结构166.5抽象数据类型·树树与二叉树图6-13树（教材第108页）基本术语·元素称节点，连线称弧；·弧直达的节点是子节点，出发端是双亲；同双亲互称兄弟；·节点分三类：根（唯一，无弧可达）、叶子（无弧出发）、内部节点；·以任意节点为根的树=子树。收纳应用：根节点=根目录，内部节点=文件夹，叶子节点=动态。图6-14二叉树（教材第108页）二叉树：最常用的特殊树·任意节点的子节点不超过2个；·六种常用操作：创建空树、插入、删除、检索、判空、遍历；·应用广泛：4.4节的Huffman编码就用到了二叉树。计算机科学概论（微课版）｜第6章数据结构176.5抽象数据类型·树的遍历二叉树的四种遍历方式遍历：按预定顺序处理每个节点，且仅处理一次。线性结构无需考虑顺序，非线性的二叉树必须约定。①前序遍历：根在最前根节点→左子树→右子树②中序遍历：根在中间左子树→根节点→右子树③后序遍历：根在最后左子树→右子树→根节点④层序遍历：逐层推进自上而下、逐层访问所有节点图6-15二叉树的四种遍历方式（教材第108页）计算机科学概论（微课版）｜第6章数据结构186.5抽象数据类型·图图：任意互联的关系网络情境：好友功能——节点表示用户，边表示好友关系。树中每个节点只能有一个双亲，表达不了好友网络；图中每个节点可与任意多个节点相连。图6-16图（教材第109页）有向图与无向图·无向图：边无方向——好友必须互认；·有向图：边有指向——允许"Alice是Bob的好友，但Bob不是Alice的好友"（关注/粉丝）。相关概念·度：无向图中依附顶点的边数；有向图分入度/出度；·权值：边上标注的有含义的数值。存储与遍历·存储：邻接矩阵、邻接表；·遍历：深度优先、广度优先；可用来算网络中两路由器的最短路径。计算机科学概论（微课版）｜第6章数据结构19章末·本章小结第6章小结：数据结构❶数据表示——数据要按一定方式组织管理；按元素间关系分为集合、线性、树状、图状四类基本结构，选对结构直接影响程序质量。❷数组——同类型元素的连续顺序集合，索引直达、定长约束；多维数组用"行×列"组织成绩表类数据。❸链表——节点=data+next指针，插入删除只改指针不搬数据，但访问须从头遍历；有单向、循环、双向、双向循环四种。❹结构体——把相关但不同类型的数据组合成自定义类型，成员具名