资源描述
数据结构数据结构2024/7/15滨州学院信息工程系1数据结构概述数据结构概述数据结构基本概念数据结构基本概念22024/7/15 数据结构课程的地位数据结构课程的地位n它是计算机专业及相关专业的它是计算机专业及相关专业的核心课程核心课程之一，之一，是计算机及相关专业的是计算机及相关专业的重要骨干基础课程重要骨干基础课程。n它针对它针对非数值计算非数值计算的程序设计问题，研究的程序设计问题，研究计算计算机的操作对象以及它们之间的关系和操作机的操作对象以及它们之间的关系和操作。即。即其研究目的是研究有效地组织和处理非数值类其研究目的是研究有效地组织和处理非数值类型数据的理论、技术和方法。型数据的理论、技术和方法。32024/7/15数据结构的核心研究内容数据结构的核心研究内容n数据的逻辑结构、存储结构及它们之间的关数据的逻辑结构、存储结构及它们之间的关系和相应的基本操作运算的定义和实现。系和相应的基本操作运算的定义和实现。n教材围绕数据结构的三种基本结构：线性结教材围绕数据结构的三种基本结构：线性结构（第构（第2-5章）、树形结构（第章）、树形结构（第6章）和图形章）和图形结构（第结构（第7章）展开讨论，研究解决如下问章）展开讨论，研究解决如下问题：题：一个具体问题的逻辑结构是什么？适宜一个具体问题的逻辑结构是什么？适宜选用什么样的存储结构？采用什么样的操作选用什么样的存储结构？采用什么样的操作实现算法效率更高？实现算法效率更高？42024/7/15学时数：学时数：96（64学时授课学时授课32学时上机）学时上机）教材：严蔚敏编著，数据结构（教材：严蔚敏编著，数据结构（C语言版），语言版），清华大学出版社清华大学出版社52024/7/15章内 容 学时 章 内 容 学时 1绪 论47图82线性表88查找83栈和队列89排序104串45数组与广义表6上机326树和二叉树 8合计96内容安排内容安排62024/7/15本节内容本节内容n数据结构讨论的范畴数据结构讨论的范畴n数据结构中的基本概念数据结构中的基本概念72024/7/15Niklaus Wirth：Algorithm+Data Structures=Programs算法算法:数据结构数据结构:处理问题的策略处理问题的策略问题的数学模型问题的数学模型一、数据结构讨论的范畴一、数据结构讨论的范畴82024/7/15概括地说：概括地说：数据结构是一门讨论数据结构是一门讨论“描述现实世界描述现实世界实体的数学模型实体的数学模型(非数值计算非数值计算)及其上的及其上的操作在计算机中如何表示和实现操作在计算机中如何表示和实现”的的学科。学科。92024/7/151、问题举例、问题举例 学生信息包括学号、姓名、性别、籍贯。建学生信息包括学号、姓名、性别、籍贯。建立一个学生档案，要求：查找立一个学生档案，要求：查找“王红王红”是否存在。是否存在。1)1)如如何何记记录录所所有有学学生生记记录录（及及选选择择何何种种逻逻辑辑数数据据结构）？结构）？2)2)选择何种存储结构？选择何种存储结构？v若把所有记录依次存储在一个数组中若把所有记录依次存储在一个数组中采用顺序存储结构采用顺序存储结构v若采用指针链表若采用指针链表采用链式存储结构采用链式存储结构102024/7/15学生信息管理系统学生信息管理系统n计算机处理的对象是表计算机处理的对象是表n元素间的关系是线性关系元素间的关系是线性关系n施加于对象上的操作常见有查询、插施加于对象上的操作常见有查询、插入、删除等入、删除等112024/7/15n皇后问题皇后问题oooxxxoooxooxx ooxxxooxoooxxooo xxoooxxxoox ooxoo122024/7/15N皇后问题皇后问题 n计算机处理的对象是树形结构计算机处理的对象是树形结构n元素间的关系是层次关系元素间的关系是层次关系n施加于对象上的操作有查询、插入、施加于对象上的操作有查询、插入、删除等删除等132024/7/15 胜利利 发生疫情的五个村子生疫情的五个村子河源河源长利利太太华桦南南1275344123 村子村子联系网系网络图v1v5v2v4v31275413432已知五个村子已知五个村子发生了疫情，由一人将疫生了疫情，由一人将疫苗送达到苗送达到5个村庄。目个村庄。目标是是寻找一条耗找一条耗时最少的路最少的路线。142024/7/15快速送达疫苗快速送达疫苗n计算机处理的对象是图计算机处理的对象是图n元素间的关系是复杂的图形或网状关元素间的关系是复杂的图形或网状关系系n施加于对象上的操作有查询、插入、施加于对象上的操作有查询、插入、删除等删除等152024/7/152、数据结构研究的范畴、数据结构研究的范畴n由以上三个例子可见，描述这类非数由以上三个例子可见，描述这类非数值计算问题的数学模型不再是数学方值计算问题的数学模型不再是数学方程，而是诸如表、树、图之类的数据程，而是诸如表、树、图之类的数据结构。结构。n因此，简单说来，因此，简单说来，数据结构是一门研数据结构是一门研究究非数值计算非数值计算的程序设计问题中计算的程序设计问题中计算机的机的操作对象操作对象以及它们之间的以及它们之间的关系关系和和操作操作的学科。的学科。162024/7/153、数据结构课程的特点、数据结构课程的特点w数据数据结构是介于构是介于数学、数学、计算机硬件算机硬件和和计算机算机软件件之之间的一的一门计算机科算机科学与技学与技术专业的的核心核心课程，是程，是编译原理、操作系原理、操作系统、数据、数据库、人工智、人工智能等能等课程的基程的基础。w 同同时，数据，数据结构技构技术也广泛也广泛应用用于信息科学、系于信息科学、系统工程、工程、应用数学用数学以及各种工程技以及各种工程技术领域。域。172024/7/15数据结构课程特点（续）数据结构课程特点（续）w数据数据结构构课程集中程集中讨论软件开件开发过程程中的中的设计阶段段、同、同时涉及涉及编码和分析和分析阶段段的若干基本的若干基本问题。此外，。此外，为了构了构造出好的数据造出好的数据结构及其构及其实现，还需考需考虑数据数据结构及其构及其实现的的评价与价与选择。w因此，数据因此，数据结构的内容包括三个构的内容包括三个层次次的五个的五个“要素要素”，如下，如下图所示：所示：182024/7/15方面方面 层次次 数据表示数据表示 数据数据处理理 抽象抽象 逻辑结构构基本运算基本运算 实现 存存储结构构 算法算法 评价价不同不同结构的比构的比较及算法分析及算法分析数据结构课程内容体系数据结构课程内容体系192024/7/154、学习的目的、学习的目的程序设计好算法好结构程序设计好算法好结构n计算机内的数值问题依靠方程，而非计算机内的数值问题依靠方程，而非数值问题（如表、树、图等）则要依数值问题（如表、树、图等）则要依靠数据结构。靠数据结构。202024/7/155、学习目标、学习目标n对每个数据结构加强对存在代价与效益对每个数据结构加强对存在代价与效益的观念的观念n掌握常用的数据结构掌握常用的数据结构将常用的数据将常用的数据结构放入你的工具包结构放入你的工具包n理解怎样去衡量一个数据结构或程序的理解怎样去衡量一个数据结构或程序的代价代价212024/7/15 重基础重基础(牢固准确掌握牢固准确掌握)讲实际讲实际(实现、分析算法实现、分析算法)p上课认真听讲、适当做好笔记，认真独立完成上课认真听讲、适当做好笔记，认真独立完成作业作业p做好预习和及时复习；做好预习和及时复习；p课后需要多读教材和参考书，查看相关内容，课后需要多读教材和参考书，查看相关内容，在理解基本内容的基础上，勤思考多练习在理解基本内容的基础上，勤思考多练习p上机实验十分重要，一定要在上机前做好充分上机实验十分重要，一定要在上机前做好充分准备，多采用不同的数据存储结构和不同的实准备，多采用不同的数据存储结构和不同的实现算法解决同一个问题。现算法解决同一个问题。6、怎样学习数据结构、怎样学习数据结构222024/7/15二、数据结构中的基本概念二、数据结构中的基本概念n数据与数据结构数据与数据结构n数据类型数据类型n抽象数据类型抽象数据类型232024/7/151、数据与数据结构、数据与数据结构n数据：数据：数据是信息的载体，是描述客观事数据是信息的载体，是描述客观事物的数、字符、以及所有能输入到计算机物的数、字符、以及所有能输入到计算机中，被计算机程序识别和处理的符号的集中，被计算机程序识别和处理的符号的集合。合。是计算机操作的对象的总称。是计算机操作的对象的总称。n数据元素：数据元素：是数据的基本单位，是数据的基本单位，具有完整具有完整确定的实际意义。在程序中常作为一个整确定的实际意义。在程序中常作为一个整体进行考虑和处理。一个数据元素可由若体进行考虑和处理。一个数据元素可由若干个数据项组成。干个数据项组成。242024/7/15n数据项：数据项：是数据不可分割的最小单是数据不可分割的最小单位位，是构成数据元素的项目。，是构成数据元素的项目。n数据对象：数据对象：数据的子集。具有相同数据的子集。具有相同性质的数据成员（数据元素）的集性质的数据成员（数据元素）的集合。合。整数数据对象整数数据对象 N=0,1,2,字母字符数据对象字母字符数据对象C=A,B,Z252024/7/15n数据结构：数据结构：是相互之间存在一种或多种是相互之间存在一种或多种特定关系的数据元素的集合特定关系的数据元素的集合n 带带结构结构的数据元素的集合的数据元素的集合262024/7/15线性线性结构结构树形结构树形结构图状结构图状结构集合结构集合结构常见的数据结构常见的数据结构272024/7/15数据结构的表示数据结构的表示n二元组表示二元组表示Data_Structures=(D,S)其中其中:D 是数据元素的有限集数据元素的有限集，S 是 D上关系的有限集关系的有限集。282024/7/15 例：设计一数据结构表示复数，并给出例：设计一数据结构表示复数，并给出其二元组定义。其二元组定义。复数由实部和虚部构成（构成元素），复数由实部和虚部构成（构成元素），两者之间存在着一种次序关系（逻辑关系）两者之间存在着一种次序关系（逻辑关系）。可以表示为：可以表示为：Complex=(C,R)其中其中,C=c1,c2 、R=说明说明:表示有序数对，用图示法表示时表示有序数对，用图示法表示时画箭头；画箭头；()表示无序数对，用图示法表示表示无序数对，用图示法表示时画线段。时画线段。292024/7/15数据的存储结构数据的存储结构n逻辑结构在存储器中的表示（映像）逻辑结构在存储器中的表示（映像）“元素元素”的映像的映像“关系关系”的映像的映像302024/7/15元素的映像方法元素的映像方法n用二进制位串存储数据元素用二进制位串存储数据元素312024/7/15关系的映像方法关系的映像方法n即如何表示即如何表示，习惯称为前驱后继，习惯称为前驱后继关系关系顺序映像：用存储位置的关系表示顺序映像：用存储位置的关系表示前驱后继关系前驱后继关系链式映像：用附加信息（指针）表链式映像：用附加信息（指针）表示前驱后继关系示前驱后继关系322024/7/15 当用某种高级程序设计语言进行编程时，通当用某种高级程序设计语言进行编程时，通常可用该语言中提供的数据类型描述之。常可用该语言中提供的数据类型描述之。两种常见存储方法比较两种常见存储方法比较n顺序映像：占用最少的存储空间，但顺序映像：占用最少的存储空间，但易产生较多碎片易产生较多碎片n链式映像：不会产生碎片，但占用空链式映像：不会产生碎片，但占用空间较多（包含线索信息）间较多（包含线索信息）332024/7/15集合结构：集合结构：仅同属一个集合仅同属一个集合线性结构线性结构:一对一（一对一（1:1)树树 结结 构构:一对多（一对多（1:n)图图 结结 构构:多对多多对多 (m:n)非线性非线性线线 性性重点概念分析重点概念分析n解释解释1：什么叫数据的逻辑结构？什么叫数据的逻辑结构？答：指数据元素之间的逻辑关系。即从逻答：指数据元素之间的逻辑关系。即从逻辑关系上描述数据，它辑关系上描述数据，它与数据的存储无与数据的存储无关，是独立于计算机关，是独立于计算机的。的。342024/7/15（1）S=(D,R)D=a,b,c,d,e,f R=(a,e),(b,c),(c,a),(e,f),(f,d)解：解：上述表达式可用图形表示为：上述表达式可用图形表示为：b c a e f d此结构为此结构为线性线性的。的。用图形表示下列数据结构，并指出它们用图形表示下列数据结构，并指出它们是属于线性结构还是非线性结构。是属于线性结构还是非线性结构。举例举例352024/7/15 d1 d5 d2 d4 d3该结构该结构是非线性（图状）是非线性（图状）的。的。解：上述表达式可用图形表示为：解：上述表达式可用图形表示为：（2）S=(D,R)D=di|1i5 R=(di,dj),ij362024/7/15n解释解释2 2：什么叫数据的物理结构？：什么叫数据的物理结构？答答：物物理理结结构构亦亦称称存存储储结结构构，是是数数据据的的逻逻辑辑结结构构在在计计算算机机存存储储器器内内的的表表示示（或或映映像），它像），它依赖于计算机依赖于计算机。存存储储结结构构可可分分为为4 4大大类类：顺顺序序、链链式式、索索引引、散列。散列。重点概念分析重点概念分析372024/7/15 不同类型的变量，其取值范围不同，所能不同类型的变量，其取值范围不同，所能进行的操作（运算）不同。进行的操作（运算）不同。2、数据类型、数据类型n 在用高级程序语言编写的程序中，必在用高级程序语言编写的程序中，必须对程序中出现的每个变量、常量或表须对程序中出现的每个变量、常量或表达式，明确说明它们所属的数据类型。达式，明确说明它们所属的数据类型。n n 定义：定义：一组性质相同的值的集合一组性质相同的值的集合,以以及定义于这个值集合上的一组操作的总及定义于这个值集合上的一组操作的总称称.382024/7/15答答：在在数数据据的的逻逻辑辑结结构构上上定定义义的的操操作作算算法法。它它在数据的存储结构上实现在数据的存储结构上实现。最常用的数据运算有最常用的数据运算有 5 种：种：插入、删除、修改、查找、排序插入、删除、修改、查找、排序解释解释3：什么是数据的运算？：什么是数据的运算？392024/7/15 数据结构涵盖的内容数据结构涵盖的内容402024/7/153、抽象数据类型、抽象数据类型n抽象数据类型抽象数据类型（Abstract Data Type ADT）是一个数学模型以及定）是一个数学模型以及定义在在该模型上的一模型上的一组操作。操作。n 抽象数据抽象数据类型的定型的定义取决于它的一取决于它的一组逻辑特性，而特性，而与其在与其在计算机内部如何算机内部如何表示和表示和实现无关无关。即不。即不论其内部其内部结构构如何如何变化，只要它的数学特性不化，只要它的数学特性不变，都不影响其外部的使用。都不影响其外部的使用。412024/7/15(1)抽象数据类型的特点抽象数据类型的特点n 由用户定义，用以表示应用问题的由用户定义，用以表示应用问题的数据模型数据模型n 由由基本的数据类型基本的数据类型组成组成,并包括并包括一一组相关的服务（或称操作）组相关的服务（或称操作）n 信息隐蔽信息隐蔽和和数据封装数据封装，使用与实现使用与实现相分离相分离422024/7/15(2)抽象数据类型的表示抽象数据类型的表示n抽象数据类型可用（抽象数据类型可用（D，S，P）三元）三元组表示组表示。n其中：其中：D 是数据对象；是数据对象；S 是是 D 上的关系集；上的关系集；P 是对是对 D 的基本操作集的基本操作集432024/7/15n其中其中基本操作基本操作的定义格式为的定义格式为:基本操作名（参数表）基本操作名（参数表）初始条件：初始条件：初始条件描述初始条件描述 操作结果：操作结果：操作结果描述操作结果描述 一般定义格式一般定义格式ADT 抽象数据类型名抽象数据类型名 数据对象：数据对象：数据对象的定义数据对象的定义 数据关系：数据关系：数据关系的定义数据关系的定义 基本操作：基本操作：基本操作的定义基本操作的定义 ADT 抽象数据类型名抽象数据类型名442024/7/15说明说明n赋值参数赋值参数 只为操作提供输入值。只为操作提供输入值。n引用参数引用参数 以以&打头，除可提供输入值外，还将打头，除可提供输入值外，还将返回操作结果。返回操作结果。n初始条件初始条件 描述了操作执行之前数据结构和参描述了操作执行之前数据结构和参数应满足的条件，若不满足，则操作失败，并数应满足的条件，若不满足，则操作失败，并返回相应出错信息。返回相应出错信息。n操作结果操作结果 说明了操作正常完成之后，数据结说明了操作正常完成之后，数据结构的变化状况和应返回的结果。若初始条件为构的变化状况和应返回的结果。若初始条件为空，则省略之。空，则省略之。452024/7/15 数据对象：数据对象：De1,e2e1,e2RealSet 数据关系：数据关系：R1|e1是复数的实数部分是复数的实数部分|e2 是复数的虚数部分是复数的虚数部分 ADT Complex ADT定义举例定义举例n例如，抽象数据类型复数的定义：例如，抽象数据类型复数的定义：462024/7/15基本操作：基本操作：AssignComplex(&Z,v1,v2)操作结果：构造复数操作结果：构造复数 Z,Z,其实部和虚部其实部和虚部 分别被赋以参数分别被赋以参数 v1 v1 和和 v2 v2 的值。的值。DestroyComplex(&Z)操作结果：复数操作结果：复数Z Z被销毁。被销毁。GetReal(Z,&realPart)初始条件：复数已存在。初始条件：复数已存在。操作结果：用操作结果：用realPart返回复数返回复数Z Z的实部值。的实部值。472024/7/15 GetImag(Z,&ImagPart)初始条件：复数已存在。初始条件：复数已存在。操作结果：用操作结果：用ImagPart返回复数返回复数Z Z的虚部值。的虚部值。Add(z1,z2,&sum)初始条件：初始条件：z1,z2是复数。是复数。操作结果：用操作结果：用sum返回两个复数返回两个复数z1,z2 的和。的和。ADT Complex482024/7/15则则 Add(z1,z2,z3)操作的结果操作的结果即为用户企求的结果，即即为用户企求的结果，即z3=是是z1 和和 z2的和的和假设假设:z1和和z2是上述定义的复数是上述定义的复数492024/7/15抽象数据类型与数据类型的区别抽象数据类型与数据类型的区别 它与数据类型实质上是一个概它与数据类型实质上是一个概念，但其特征是念，但其特征是使用使用与与实现分离实现分离，实行实行封装封装和和信息隐蔽信息隐蔽（独立于计算（独立于计算机）机）502024/7/15 例如，对以上定义的例如，对以上定义的Complex，可有，可有如下实现：如下实现：(3)抽象数据类型的实现抽象数据类型的实现n抽象数据类型需要通过固有数据类型抽象数据类型需要通过固有数据类型(高级编程语言中已实现的数据类型高级编程语言中已实现的数据类型)来实现。来实现。512024/7/15typedef struct float realpart；float imagpart；complex；/-存储结构的定义存储结构的定义/-基本操作的函数原型说明基本操作的函数原型说明void Assign(complex&Z,float realval,float imagval)；/构造复数构造复数 Z,Z,其实部和虚部分别被赋以参数其实部和虚部分别被赋以参数 /realval 和和 imagval 的值的值522024/7/15float GetReal(cpmplex Z)；/返回复数返回复数 Z Z 的实部值的实部值float Getimag(cpmplex Z)；/返回复数返回复数 Z Z 的虚部值的虚部值void add(complex z1,complex z2,complex&sum)；/以以 sum 返回两个复数返回两个复数 z1,z2 的和的和 532024/7/15/-基本操作的实现基本操作的实现void add(complex z1,complex z2,complex&sum)/以以 sum 返回两个复数返回两个复数 z1,z2 的和的和 sum.realpart=z1.realpart+z2.realpart;sum.imagpart=z1.imagpart+z2.imagpart;其它省略 542024/7/15本讲小结本讲小结数据结构定义数据结构定义 指互相有关联的数据元素的集合，可指互相有关联的数据元素的集合，可用用data_Structure=(D,R)表示。表示。数据结构内容数据结构内容 数据的逻辑结构、存储结构和基本运数据的逻辑结构、存储结构和基本运算算。数据结构描述工具数据结构描述工具 抽象数据类型抽象数据类型、高级程序设计语言。、高级程序设计语言。552024/7/15n C语言：语言：1、函数有关知识、函数有关知识(定义、调用等定义、调用等)2、关于、关于typedef命令命令 3、动态存储管理函数动态存储管理函数 malloc()realloc()free()n 算法的时间复杂度、空间复杂度算法的时间复杂度、空间复杂度n算法的实现与验证算法的实现与验证课后预习内容课后预习内容
展开阅读全文