大学数据结构（C语言描述）-马秋菊-课件PPT
收藏
资源目录
压缩包内文档预览：(预览前20页/共30页)
编号：21835895
类型：共享资源
大小：12.16MB
格式：ZIP
上传时间：2019-09-06
上传人：QQ24****1780
认证信息
个人认证
王**（实名认证）
浙江
IP属地：浙江
25
积分
- 关 键 词：
-
大学
数据结构
语言
描述
描写
马秋菊
课件
ppt
- 资源描述：
-
大学数据结构（C语言描述）-马秋菊-课件PPT,大学,数据结构,语言,描述,描写,马秋菊,课件,ppt
- 内容简介：
-
2019年9月6日星期五,第1页,数据结构,（C 语言描述）,马秋菊 主编,中国水利水电出版社,2019年9月6日星期五,第2页,第1章 绪论 第2章 线性表 第3章 栈和队列 第4章 数组、特殊矩阵 和广义表,主要内容,第5章 串 第6章 树 第7章 图 第8章 查找 第9章 排序,（C 语言描述）马秋菊 主编中国水利水电出版社第1章 绪论第2章 线性表第3章 栈和队列第4章 数组、特殊矩阵 和广义表主要内容第5章 串第6章 树第7章 图第8章 查找第9章 排序2019年9月6日,1,1.1 为什么学习数据结构 1.2 数据结构的有关概念和术语 1.3 算法和算法描述 1.4 算法的时空效率分析方法 1.5 小结与习题,第一章 数据结构概述,2019年9月6日,2,主要介绍课程中常用术语、常用数据结构及用类C语言实现算法描述的一般规则，算法的时间复杂度和空间复杂度分析与评价。,本章主要内容,通过本章学习，应掌握如下内容： 数据结构中的基本概念及常用术语。 线性结构、树型结构和图型结构等的逻辑特点。 算法的定义、特性及用类C语言描述算法的规则。 评价算法优劣的标准：时间复杂度、空间复杂度的定义及表示。,2019年9月6日,3,1.1 为什么要学习数据结构,研究数据的特性、数据间的相互关系及其对应的存储表示，并利用这些特性、关系和存储表示设计出相应的算法和程序。,为什么要学习数据结构？ 计算机处理的数据量越来越大； 数据的类型越来越多； 数据的结构越来越复杂。,解决一个问题时几个步骤：抽象出一个适当的数学模型，设计或选择一个解决此类数学模型的算法，编写程序进行调试、测试，直至得到最终的解答。,2019年9月6日,4,【例1-1】学生信息检索问题。学生信息包括学号、姓名、性别和成绩等，一行为一个记录，表示一个学生的信息（也称为一个数据元素），一列为一个属性。,线性关系:对线性表的主要操作有查找、修改、插入和删除等。,2019年9月6日,5,【例1-2】某大学专业设置问题。显然这种关系用“树”型结构来表示更形象。通常用来表示结点的分层组织，结点之间是一对多的关系。对树型结构主要操作有查找、修改、插入和删除等。,2019年9月6日,6,【例1-3】通信网络问题。带圆圈的顶点表示城市，顶点和顶点之间的连线和数据表示城市之间的通信线路及其长度。，各顶点之间是多对多的关系，是网状结构，也称为图型结构，操作有：求从一个顶点到另一个顶点的最短路径等。,由以上三个例子可见，描述这类非数值计算问题的数学模型有线性表、树、图等。所有的计算机系统软件和应用软件都要用到各种类型的数据结构。,2019年9月6日,7,1. 2 数据结构的有关概念和术语,1.2.1 基本概念和术语 1数据（Data）是描述客观事物的数值、字符以及所有能被输入到计算机并能被计算机识别、存储和处理的符号的集合。客观事物包括数值数据和非数值数据。数值数据：整数、实数或复数；非数值数据：字符、文字、图形、图像和声音等。 2数据元素（Data Element）是数据的基本单位。在不同的条件下，数据元素又可称为元素、结点、顶点、记录等。 数据项：数据结构中讨论的最小单位。一个数据元素可由若干个数据项（Data Item）组成。例如，学生信息表的每一个数据元素就是一个学生记录，它包括学生的学号、姓名、性别、成绩等数据项。,2019年9月6日,8,3数据对象（Data Object）是具有相同性质数据元素的集合。,4数据类型(Data Type) 在用高级语言编写的程序中，每个变量、常量或表达式都有一个它所属的确定的数据类型。,5抽象数据类型（Abstract Data Type，简称ADT）是指基于逻辑关系的数据类型以及定义在该类型之上的一组操作。,ADT 抽象数据类型名 数据对象：（数据对象的定义） 数据关系：（数据关系的定义） 基本操作：（基本操作的定义） ,2019年9月6日,9,【例1-4】线性表的抽象数据类型可描述如下： ADT Linear_list 数据元素 所有ai属于同一数据对象，i=1，2，n （n1） 逻辑结构 所有数据元素ai存在次序关系（ai，ai+1），a1无前驱，an无后继。 操作 /* 设L为Linear_list类型的线性表*/ InitList（L）； /* 建立一个空的线性表L */ Length（L）； /* 求线性表L的长度*/ GetElement（L，i）；/* 取线性表L中的第i个元素*/ Locate（L，x）；/* 确定元素x在线性表L中的位置*/ Insert（L， i，x）； /* 在线性表L中的第i个位置处插入数据元素x */ Delete（L，i）； /* 删除表L中第i个位置的元素 */ ； /* ADT Linear_list */,2019年9月6日,10,1.2.2 数据结构定义 数据结构（Data Structure）是指互相之间存在着一种或多种关系的数据元素的集合。数据元素之间的关系称为结构。数据的结构包括逻辑结构和物理结构。 （1）逻辑结构：是数据元素之间的相互逻辑关系，它与数据的存储无关，是独立于计算机而存在。,数据结构是由两个集合构成的一个二元组： Data_Structure(D，R) Data_Structure是一种数据结构，它由同属一个数据对象的数据元素的有限集合D和D上二元关系的有限集合R组成。其中： D=di|1in, n1 R=rj|1jm, m1,2019年9月6日,11,di表示第i个数据元素，rj表示第j个关系。 D上二元关系R是序偶的集合。对于R中的任一序偶(x, yD)，x称为序偶的第一元素，y称为序偶的第二元素，又称序偶的第一元素是第二元素的直接前驱；第二元素为第一个元素的直接后继。,【例1-5】树型结构中的圆圈代表数据元素，带箭头的连线表示元素之间的关系，试用二元组表示法表示其逻辑结构。 解：二元组为 ( D , R ) 其中，D = A,B,C,E,F,G,H,I ,J; R= , , , , , , , ,2019年9月6日,12,通常有下列四种基本的结构： a.集合结构。集合是元素关系极为松散的一种结构。 b.线性结构。线性结构的逻辑特征是：若结构是非空集，则有且仅有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前驱和一个直接后继。 c.树型结构。该结构的数据元素之间存在着一对多的关系。 d.图型结构。该结构的数据元素之间存在着多对多的关系，图型结构也称作网状结构。,（2）物理结构（或存储结构）是数据结构在计算机中的表示（又称映像），它包括数据元素的机内表示和关系的机内表示。具体实现的方法有顺序、链接、索引、散列等多种，数据的具体操作与存储结构有很密切的联系。,数据结构作为一门学科主要研究数据的各种逻辑结构和存储结构，以及对数据的各种操作。同时还要考虑执行算法时的时间和空间效率。,2019年9月6日,13,1.3 算法和算法描述, 有穷性。一个算法必须在有穷步之后结束，即必须在有限时间内完成。 确定性。算法的每一步必须有确切的定义，无二义性。 可行性。算法中的每一步都可以通过已经实现的基本运算的有限次执行得以实现。 输入。一个算法具有零个或多个输入，这些输入取自特定的数据对象集合。 输出。一个算法具有一个或多个输出，这些输出同输入之间存在某种特定的关系。,1.3.1 算法与算法特性 算法（Algorithm）是对特定问题求解步骤的一种描述，是指令的有限序列。一个算法应该具有下列特性：,2019年9月6日,14,一个好的算法通常要达到以下的要求：,正确。执行结果应当满足预先规定的功能和性能要求。 可读。应当思路清晰、层次分明、简单明了、易读易懂。 健壮。当输入不合法数据时，应能作适当处理，不至引起严重后果。 高效。有效使用存储空间和有较高的时间效率。,1.3.2 算法描述 最简单的方法是使用自然语言，其优点是简单且便于人们对算法的阅读；缺点是转换成高级语言困难。 类C语言忽略高级程序设计语言中一些严格的语法规则与描述细节，因此它比程序设计语言更容易描述和被人理解，比自然语言更接近程序设计语言，很容易被转换成高级语言。,2019年9月6日,15,本书对所用类C语言作如下约定： 1问题的规模用MAXSIZE #define MAXSIZE 60,2预定义常量和类型： #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define OVERFLOW -1 typedef int Status;,3数据结构（存储结构）的表示用类型定义（typedef）描述。数据元素类型约定为 ElemType，由用户在使用该数据类型时自行定义。,例1.学生信息检索系统中，用一维数组作存储 n 个学生的信息，数组中的数据元素有4个域：学号、姓名、性别和成绩： typedef struct std_info long int Num; /* 学号域 */ char Name8; /* 姓名域 */ char Sex; /* 性别域 */ float Score; /* 成绩域 */ ElemType ;,2019年9月6日,16,4基本操作的算法都用以下形式的函数描述 函数类型 函数名(函数参数表) /* 算法说明 */ 语句序列； /* 函数名 */,5C语言中的常用语句 赋值（=）、选择（if、if else、 switch case default）、循环（for、 while、do while）、结束（return、break、continue、exit）、输入和输出等语句。,6基本运算和基本函数 基本运算有+、-、*、/、%、-、&和 | 等。 基本函数有max、min、abs、fabs、eof 等。,2019年9月6日,17,例设某班级有n个学生，编写算法，查找班级中成绩最高的学生，并输出该学生的所有信息。 分析：，算法依次查看数组中的元素，并保存当前最高成绩及其下标。使用类C语言编写：,int largest（ElemType SMAXSIZE，int n） float currlarge=0.0 ; int i, j=0; /* 赋初值 */ for （i=0 ; i currlarge) j=i; currlarge= Si.Score; printf(“%10ld%10s%10c%10fn”,Sj.Num, Sj. name,Sj.Sex, Sj. Score); /* largest */,typedef struct std_info long int Num; char Name8; char Sex; float Score; ElemType ;,2019年9月6日,18,1.4 算法时空效率分析方法,评价算法的性能用时间复杂度与空间复杂度来度量。,1、算法的时间复杂度 算法的时间复杂度（Time complexity）是指算法转换为程序后(这里仍称为算法)在计算机上从开始运行到结束所需要的时间。运行所需要的时间取决于下列因素： 硬件的速度。与硬件的配置高低有关。 书写程序的语言。语言的级别越高，其执行效率就越低。 编译程序所生成目标代码的质量。 依据算法所选用的策略。 问题的规模。一般情况下，处理的数据量越大，执行的时间相对也越长。,2019年9月6日,19,通常的做法是：不考虑不确定的情况，而以算法中简单操作重复执行的次数作为算法的时间度量。为此，一个特定算法的运行时间长短就只依赖于问题的规模n，或者说它是问题规模n的函数f (n)。,【例1-7】求累加求和 int sum(int b ，int n） int sum=0; /* 第1条定义并赋初值语句执行1次 */ for（int i=0；in；i+）/* 3n+2 次 */ sum+=bi; /* n次 */ return sum ; /* 返回语句执行1次 */,2019年9月6日,20,要精确地计算f (n)是困难的，引入渐进时间复杂度在数量上估计一个算法的执行时间。算法时间的度量记作 T(n)=(f(n) 它表示随问题的规模n的增大，算法执行时间的增长率和f (n)相同。使用大记号，(f (n)称为算法的渐进时间复杂度（Asymptotic Time Complexity），简称时间复杂度。,例如，一个程序的实际执行时间为 T(n)2.7n3+3.8n2+5.3。则T(n)(n3)。,2019年9月6日,21,【例1-8】求下面程序段的时间复杂度。 s=0; for (j=1;j=n;j+) for (x=1,k=1;k=n;k+) x=x*k; s+=x; ,解：该算法中“s=0;”的频度为1，后面由两个“for”语句构成了一个二重循环结构，其内循环体执行的频度为n2，用最高数量级n2的表示，则该程序段的时间复杂度为O(n2)。 通常将称(1)为常数阶，(n)为线性阶，O(n2) 为平方阶。算法还可能呈现的复杂度有：对数阶(log2n)，指数阶(2n)等，不同数量级时间复杂度的关系有： (1)(log2n)(n)(nlog2n)(n2)(n3)(2n),2019年9月6日,22,2019年9月6日,23,2、算法的空间复杂度 一个程序的空间复杂度（Space complexity）是指程序运行从开始到结束所需的最大存储空间。 包括以下三部分： （1）输入数据所占空间； （2）程序本身所占空间； （3）辅助变量所占空间。 只需要分析辅助变量所占空间即可。通常以算法的空间复杂度作为算法所占用存储空间的量度。定义： S(n)=O(g (n),2019年9月6日,24,小 结,术语：数据（Data）、数据元素（Data Element）、数据项、数据对象、数据类型等,线性结构、树型结构和图型结构等的逻辑特点。 算法的定义、特性及用类C语言描述算法的规则。 评价算法优劣的标准：时间复杂度、空间复杂度的定义及表示。, 1.1 为什么学习数据结构 1.2 数据结构的有关概念和术语 1.3 算法和算法描述 1.4 算法的时空效率分析方法 1.5 小结与习题主要介绍课程中常用术语、常用数据结构及用类C语言实现算法描述的一般规则，算法的时间复杂度和空间复杂度分析与评价。本章主要内容 通过本章学习，应掌握如下内容： 数据结构中的基本概念及常用术语。 线性结构、树型结构和图型结构等的逻辑特点。 算法的定义、特性及用类C语言描述算法的规则。 评价算法优劣的标准：时间复杂度、空间复杂度的定义及表示。1.1 为什么要学习数据结构 研究数据的特性、数据间的相互关系及其对应的存储表示，并利用这些特性、关系和存储表示设计出相应的算法和程序。为什么要学习数据结构？计算机处理的数据量越来越大；数据的类型越来越多；数据的结构越来越复杂。解决一个问题时几个步骤：抽象出一个适当的数学模型，设计或选择一个解决此类数学模型的算法，编写程序进行调试、测试，直至得到最终的解答。【例1-1】学生信息检索问题。学生信息包括学号、姓名、性别和成绩等，一行为一个记录，表示一个学生的信息（也称为一个数据元素），一列为一个属性。线性关系:对线性表的主要操作有查找、修改、插入和删除等。 【例1-2】某大学专业设置问题。显然这种关系用“树”型结构来表示更形象。通常用来表示结点的分层组织，结点之间是一对多的关系。对树型结构主要操作有查找、修改、插入和删除等。【例1-3】通信网络问题。带圆圈的顶点表示城市，顶点和顶点之间的连线和数据表示城市之间的通信线路及其长度。，各顶点之间是多对多的关系，是网状结构，也称为图型结构，操作有：求从一个顶点到另一个顶点的最短路径等。由以上三个例子可见，描述这类非数值计算问题的数学模型有线性表、树、图等。所有的计算机系统软件和应用软件都要用到各种类型的数据结构。 1. 2 数据结构的有关概念和术语 1.2.1 基本概念和术语1数据（Data）是描述客观事物的数值、字符以及所有能被输入到计算机并能被计算机识别、存储和处理的符号的集合。客观事物包括数值数据和非数值数据。数值数据：整数、实数或复数；非数值数据：字符、文字、图形、图像和声音等。2数据元素（Data Element）是数据的基本单位。在不同的条件下，数据元素又可称为元素、结点、顶点、记录等。数据项：数据结构中讨论的最小单位。一个数据元素可由若干个数据项（Data Item）组成。例如，学生信息表的每一个数据元素就是一个学生记录，它包括学生的学号、姓名、性别、成绩等数据项。3数据对象（Data Object）是具有相同性质数据元素的集合。4数据类型(Data Type) 在用高级语言编写的程序中，每个变量、常量或表达式都有一个它所属的确定的数据类型。5抽象数据类型（Abstract Data Type，简称ADT）是指基于逻辑关系的数据类型以及定义在该类型之上的一组操作。ADT 抽象数据类型名 数据对象：（数据对象的定义）数据关系：（数据关系的定义）基本操作：（基本操作的定义） 【例1-4】线性表的抽象数据类型可描述如下：ADT Linear_list 数据元素 所有ai属于同一数据对象，i=1，2，n （n1）逻辑结构 所有数据元素ai存在次序关系（ai，ai+1），a1无前驱，an无后继。操作 /* 设L为Linear_list类型的线性表*/ InitList（L）； /* 建立一个空的线性表L */ Length（L）； /* 求线性表L的长度*/ GetElement（L，i）；/* 取线性表L中的第i个元素*/ Locate（L，x）；/* 确定元素x在线性表L中的位置*/ Insert（L， i，x）； /* 在线性表L中的第i个位置处插入数据元素x */ Delete（L，i）； /* 删除表L中第i个位置的元素 */ ； /* ADT Linear_list */1.2.2 数据结构定义数据结构（Data Structure）是指互相之间存在着一种或多种关系的数据元素的集合。数据元素之间的关系称为结构。数据的结构包括逻辑结构和物理结构。（1）逻辑结构：是数据元素之间的相互逻辑关系，它与数据的存储无关，是独立于计算机而存在。数据结构是由两个集合构成的一个二元组： Data_Structure(D，R)Data_Structure是一种数据结构，它由同属一个数据对象的数据元素的有限集合D和D上二元关系的有限集合R组成。其中：D=di|1in, n1R=rj|1jm, m1di表示第i个数据元素，rj表示第j个关系。D上二元关系R是序偶的集合。对于R中的任一序偶(x, yD)，x称为序偶的第一元素，y称为序偶的第二元素，又称序偶的第一元素是第二元素的直接前驱；第二元素为第一个元素的直接后继。【例1-5】树型结构中的圆圈代表数据元素，带箭头的连线表示元素之间的关系，试用二元组表示法表示其逻辑结构。解：二元组为 ( D , R )其中，D = A,B,C,E,F,G,H,I ,J; R= , , , , , , , 通常有下列四种基本的结构：a.集合结构。集合是元素关系极为松散的一种结构。b.线性结构。线性结构的逻辑特征是：若结构是非空集，则有且仅有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前驱和一个直接后继。c.树型结构。该结构的数据元素之间存在着一对多的关系。d.图型结构。该结构的数据元素之间存在着多对多的关系，图型结构也称作网状结构。 （2）物理结构（或存储结构）是数据结构在计算机中的表示（又称映像），它包括数据元素的机内表示和关系的机内表示。具体实现的方法有顺序、链接、索引、散列等多种，数据的具体操作与存储结构有很密切的联系。数据结构作为一门学科主要研究数据的各种逻辑结构和存储结构，以及对数据的各种操作。同时还要考虑执行算法时的时间和空间效率。1.3 算法和算法描述 有穷性。一个算法必须在有穷步之后结束，即必须在有限时间内完成。 确定性。算法的每一步必须有确切的定义，无二义性。 可行性。算法中的每一步都可以通过已经实现的基本运算的有限次执行得以实现。 输入。一个算法具有零个或多个输入，这些输入取自特定的数据对象集合。 输出。一个算法具有一个或多个输出，这些输出同输入之间存在某种特定的关系。1.3.1 算法与算法特性算法（Algorithm）是对特定问题求解步骤的一种描述，是指令的有限序列。一个算法应该具有下列特性：一个好的算法通常要达到以下的要求：正确。执行结果应当满足预先规定的功能和性能要求。可读。应当思路清晰、层次分明、简单明了、易读易懂。健壮。当输入不合法数据时，应能作适当处理，不至引起严重后果。高效。有效使用存储空间和有较高的时间效率。1.3.2 算法描述最简单的方法是使用自然语言，其优点是简单且便于人们对算法的阅读；缺点是转换成高级语言困难。类C语言忽略高级程序设计语言中一些严格的语法规则与描述细节，因此它比程序设计语言更容易描述和被人理解，比自然语言更接近程序设计语言，很容易被转换成高级语言。本书对所用类C语言作如下约定：1问题的规模用MAXSIZE#define MAXSIZE 602预定义常量和类型：#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0 #define OVERFLOW -1typedef int Status;3数据结构（存储结构）的表示用类型定义（typedef）描述。数据元素类型约定为 ElemType，由用户在使用该数据类型时自行定义。例1.学生信息检索系统中，用一维数组作存储 n 个学生的信息，数组中的数据元素有4个域：学号、姓名、性别和成绩：typedef struct std_info long int Num; /* 学号域 */ char Name8; /* 姓名域 */ char Sex; /* 性别域 */ float Score; /* 成绩域 */ ElemType ; 4基本操作的算法都用以下形式的函数描述函数类型 函数名(函数参数表)/* 算法说明 */语句序列；/* 函数名 */5C语言中的常用语句赋值（=）、选择（if、if else、 switch case default）、循环（for、 while、do while）、结束（return、break、continue、exit）、输入和输出等语句。6基本运算和基本函数基本运算有+、-、*、/、%、-、&和 | 等。基本函数有max、min、abs、fabs、eof 等。 例设某班级有n个学生，编写算法，查找班级中成绩最高的学生，并输出该学生的所有信息。分析：，算法依次查看数组中的元素，并保存当前最高成绩及其下标。使用类C语言编写：int largest（ElemType SMAXSIZE，int n） float currlarge=0.0 ; int i, j=0; /* 赋初值 */ for （i=0 ; i currlarge) j=i; currlarge= Si.Score; printf(“%10ld%10s%10c%10fn”,Sj.Num, Sj. name,Sj.Sex, Sj. Score); /* largest */typedef struct std_info long int Num; char Name8; char Sex; float Score; ElemType ; 1.4 算法时空效率分析方法评价算法的性能用时间复杂度与空间复杂度来度量。1、算法的时间复杂度算法的时间复杂度（Time complexity）是指算法转换为程序后(这里仍称为算法)在计算机上从开始运行到结束所需要的时间。运行所需要的时间取决于下列因素： 硬件的速度。与硬件的配置高低有关。 书写程序的语言。语言的级别越高，其执行效率就越低。 编译程序所生成目标代码的质量。 依据算法所选用的策略。 问题的规模。一般情况下，处理的数据量越大，执行的时间相对也越长。通常的做法是：不考虑不确定的情况，而以算法中简单操作重复执行的次数作为算法的时间度量。为此，一个特定算法的运行时间长短就只依赖于问题的规模n，或者说它是问题规模n的函数f (n)。【例1-7】求累加求和int sum(int b ，int n） int sum=0; /* 第1条定义并赋初值语句执行1次 */ for（int i=0；in；i+）/* 3n+2 次 */ sum+=bi; /* n次 */ return sum ; /* 返回语句执行1次 */要精确地计算f (n)是困难的，引入渐进时间复杂度在数量上估计一个算法的执行时间。算法时间的度量记作T(n)=(f(n)它表示随问题的规模n的增大，算法执行时间的增长率和f (n)相同。使用大记号，(f (n)称为算法的渐进时间复杂度（Asymptotic Time Complexity），简称时间复杂度。 例如，一个程序的实际执行时间为 T(n)2.7n3+3.8n2+5.3。则T(n)(n3)。【例1-8】求下面程序段的时间复杂度。 s=0; for (j=1;j=n;j+) for (x=1,k=1;k=n;k+) x=x*k; s+=x; 解：该算法中“s=0;”的频度为1，后面由两个“for”语句构成了一个二重循环结构，其内循环体执行的频度为n2，用最高数量级n2的表示，则该程序段的时间复杂度为O(n2)。通常将称(1)为常数阶，(n)为线性阶，O(n2) 为平方阶。算法还可能呈现的复杂度有：对数阶(log2n)，指数阶(2n)等，不同数量级时间复杂度的关系有：(1)(log2n)(n)(nlog2n)(n2)(n3)(2n)2、算法的空间复杂度一个程序的空间复杂度（Space complexity）是指程序运行从开始到结束所需的最大存储空间。包括以下三部分：（1）输入数据所占空间；（2）程序本身所占空间；（3）辅助变量所占空间。只需要分析辅助变量所占空间即可。通常以算法的空间复杂度作为算法所占用存储空间的量度。定义：S(n)=O(g (n)小 结术语：数据（Data）、数据元素（Data Element）、数据项、数据对象、数据类型等 线性结构、树型结构和图型结构等的逻辑特点。 算法的定义、特性及用类C语言描述算法的规则。 评价算法优劣的标准：时间复杂度、空间复杂度的定义及表示。2019年9月6日星期五,第1页,2.1 线性表的逻辑结构,2.2 线性表的顺序存储结构及运算实现,2.3 线性表的链式存储结构及运算实现,2.4 线性表的典型应用,小结,第2章 线性表,2019年9月6日星期五,第2页,本章学习目标,线性表是最简单、最基本、最常用的一种数据结构 通过本章学习，应掌握如下内容： 线性表的概念及表示方法 线性表的两种存储方式：顺序存储和链式存储 线性表的基本运算及其实现算法 线性表的典型应用,2019年9月6日星期五,第3页,例2:奇数序列 (1,3,5,7,9,11),例1:字母序列 (A,B,C,D,E,F),例3：随机的学生成绩序列,2.1 线性表的逻辑结构,2.1.1 线性表的定义 问题的引入,2019年9月6日星期五,第4页,3.举例： A=(,) 该线性表的长度为 5 B=(a1 ,a2 ,a3 ,，am) 该线性表的长度为 m C=(b1 ,b2 ,b3 ,，bn) 该线性表的长度为 n,1.定义：具有相同类型的 n 个数据元素组成的有限序列。 记为 (a1，a2， ai-1，ai，ai+1，an) 其中n为表长，当n=0 时称为空表。 关键点: (1) 相同类型 (2) 线性表的长度 n (n0) (3) 有限序列,2019年9月6日星期五,第5页,1.线性表的长度 线性表中所包含的元素个数 n (n0)； 2.空线性表 线性表的长度 n=0 ； 3.（直接）前驱和后继 在相邻元素中，ai 是ai+1的前驱（第一个元素 a1无前驱） 在相邻元素中，ai+1是ai的后继（最后一个元素an无后继） 4.举例： 长度为10的奇数序列 (1,3,5,7,9,11,13,15,17,19),线性表可以看作是除第一个元素无前驱，最后一个元素无后继外，其余元素都有唯一的直接前驱和直接后继的一组元素构成的有序集合。,2019年9月6日星期五,第6页,通常将 ai的数据类型抽象为ElemType。例如，学生信息表中数据元素可以定义为一个结构类型： typedef struct std_info long int Num; /* 学号域 */ char Name8; /* 姓名域 */ char Sex; /* 性别域 */ float Score; /* 成绩域 */ ElemType ;,2019年9月6日星期五,第7页,2.1.2 线性表的基本操作, 线性表初始化： Init_List(L)； 建立一个空的线性表； 求线性表的长度：Length_List(L)； 返回线性表中数据元素的个数。 取表中元素：Get_Elem(L, i)； 返回线性表L中第个数据元素的值或地址。 按值查找：Locate_List(L, x)； 在表L中查找值为的数据元素的位置。 插入操作：Insert_List(L, i, x)；在线性表L的第i个位置上插入一个值为x的数据元素。 删除操作：Delete_List(L, i)； 在线性表L中删除序号为 i 的数据元素。,2019年9月6日星期五,第8页,ADT List 数据对象：D=ai|ai ELEMTP i=1,2, ,n ,n 0 数据关系：R= | ai , ai+1 D i=1,2, ,n-1 ,n 0 基本操作： InitList（&L）：线性表的初始化； ListLength（L）：求线性表的长度； ListInsert（&L , i , e）： 在第 i 个位置插入元素 e ； ListDelete（&L , i , e）： 在线性表第 i 个位置删除元素 e ； ,2019年9月6日星期五,第9页,2.2 线性表的顺序存储结构及运算实现,2.2.1 顺序表 是指在内存中用一块地址连续的存储空间按顺序存储线性表的各个数据元素。 特点：采用连续的空间来存储线性表顺序表。,顺序存储结构可描述如下： typedef struct ElemType elemMAXSIZE; int length; /* 线性表长度 */ SeqList;,2019年9月6日星期五,第10页,线性表的长度及元素在线性表中的位置 已知该线性表的首地址(a1)为，那么任意一个元素的地址为: ai(i-1) d （其中d为该类型元素所占空间）,定义一个顺序表： SeqList *L ； 顺序表的长度为L-length; 数据元素是L-data1L-dataL-length。 因为在 C语言中数组的下标是从0开始的，为了与线性表中元素的序号保持一致，不使用数组下标为“0”的单元，下标的取值范围1iMAXSIZE-1。,2019年9月6日星期五,第11页,(1) 将anai 按从后向前的顺序向下移动，为新元素让出位置； (2) 将x置入空出的第i个位置； (3) 修改length值。 Length+1,2.2.2 顺序表上基本运算的实现,1顺序表的初始化-构造一个空表,void init_SeqList(SeqList *L) L-length =0; ,2. 插入运算,2019年9月6日星期五,第12页,【算法2.2】在顺序表的第i个位置上插入一个值为x的新元素。 int Insert_SeqList(SeqList *L，int i，ElemType x) int j; if (L-length=MAXSIZE-1) printf(表满); return OVERFLOW; if (iL-length+1) /* 检查插位置的正确性 */ printf(位置错); return ERROR ; for ( j=L-length;j=i;j-) L-elemj+1=L-elemj; L-elemi=x ; L-length+ ; return OK; /* 插入成功，返回 */ ,2019年9月6日星期五,第13页,算法说明：在线性表中，按照某顺序查找与其给定一致的元素是否存在，如果存在返回其位置，否则给出相关信息。,i的取值范围为 ： 1in+1 即有n1个位置可以插入。,2019年9月6日星期五,第14页,插入算法的时间性能分析：,在第i个位置上插入 x ，从 ai 到 an 都要向下移动一个位置，共需要移动 ni1个元素，而 i 的取值范围为 ： 1= i= n+1，即有 n1个位置可以插入。设在第i个位置上作插入的概率为Pi，则平均移动数据元素的次数：,设：Pi=1/ (n+1) ，即为等概率情况，则：,这说明：在顺序表上做插入操作需移动表中一半的数据元素。显然时间复杂度为(n)。,2019年9月6日星期五,第15页,3. 删除运算,删除第i个元素，i 的取值范围为：1in。运算的步骤为：先将ai+1an 依次向上移动，然后将length 值减1。,删除算法 int Delete_SeqList(SeqList *L, int i) int j; if(iL-length) printf (不存在第i个元素); return ERROR ; for(j=i;jlength-1; j+) L-elemj=L-elemj+1; L-length-; return OK ; ,2019年9月6日星期五,第16页,删除第i个元素时，其后面的元素 ai+1an 都要向上移动一个位置，共移动了 n-i 个元素，所以平均移动数据元素的次数：,在等概率情况下，pi =1/ n，则：,这说明顺序表上作删除运算时大约需要移动表中一半的元素，显然该算法的时间复杂度为 (n)。,2019年9月6日星期五,第17页,4按值查找,【算法2.4】在线性表中查找与给定值x相等的数据元素。,int Location_SeqList(SeqList *L, ElemType x) int i=1; while(ilength /* 返回x的存储位置 */ ,时间复杂度分析：当 a1=x 时，只比较一次；当 an=x 时需要比较 n 次；平均比较次数为（n+1）/2，所以时间复杂度为O(n)，即时间复杂度与表长有关。,2019年9月6日星期五,第18页,【例2-3】有两个顺序表 A 和 B，其元素均按从小到大的升序排列，编写一个算法将它们合并成一个顺序表 C，要求 C 的元素也是从小到大排列。算法的时间复杂度是O(m+n)，,void merge(SeqList *A,SeqList *B,SeqList *C) int i,j,k; i=1;j=1;k=1; while (ilength ,2019年9月6日星期五,第19页,2.3 线性表的链式存储和运算实现,问题的引入： 1.顺序存储结构必须在程序编译前就规定好数组元素的多少(即数组长度)，事先难估计，多了造成浪费存储空间，少了不够用； 2.顺序存储结构在查找和删除运算中可能需要大量移动元素，降低程序执行效率。 基于上述两点，需要引入链式存储结构。 注意：与顺序存储结构的不同点是内存位置不一定相邻，即每一个数据项都有一个链接字段，用来存放下一个数据项的地址，形成链表结构。,2019年9月6日星期五,第20页,链式存储结构结点（数据项）最少有两个域：数据域和指针域。采用不连续空间存储线性表，使用指针指向下一元素的位置。,2.3.1 单链表,2019年9月6日星期五,第21页,链式存储结构特点：,1.使用任意的存储单元存储线性表，不需要空间连续；,2.通过前一个结点得到后一个结点的地址，使它们前后之间建立一一对应的关系（即：前趋和后继的关系）。,结点定义如下： typedef struct node ElemType data; /* 数据域 */ struct node *next; /* 指针域 */ LNode，*LinkList；,【说明】 ELEMTP为通用数据类型； next 为指向结构体类型的指针，指示下一结点（后继，除最后一个元素）所在的位置。,2019年9月6日星期五,第22页,头指针变量定义方法如下： LinkList H; 算法中用到指向某结点的指针变量时按如下格式进行说明： LNode *p； 则语句： p=(LinkList)malloc(sizeof(LNode)；,声明后，系统会分配足够的空间来容纳Linklist结构，同时指针p指向新的内存位置。,p所指的结点为*p，*p的类型为LNode型，该结点的数据域为 (*p).data或p-data，指针域为 (*p).next 或 p-next。 free(p) 则表示释放指针p所指向的结点空间。,2019年9月6日星期五,第23页,2.3.2 单链表基本运算的实现,1. 建立单链表,(1) 在链表的头部插入结点建立单链表 。如（16，20，65，12）的链表的建立过程 。,2019年9月6日星期五,第24页,【算法2.6】在链表的头部插入结点建立单链表。 LinkList Creat_LinkList1( ) LinkList H=(LinkList)malloc(sizeof(LNode); /* 生成头结点 */ H -next=NULL； /* 空表 */ LNode *s; int x; /* 设数据元素的类型为int */ scanf(%d, ,2019年9月6日星期五,第25页,(2) 在单链表的尾部插入结点建立单链表。如（16，20，65，12）的链表的建立过程 。,2019年9月6日星期五,第26页,【算法2.7】在链表的尾部插入结点建立单链表。,LinkList Creat_LinkList2( ) LinkList H=(LinkList)malloc(sizeof(LNode); H -next=NULL； /* 空表 */ LNode *s,*r=H ; int x; /* 设数据元素的类型为int */ scanf(%d, ,2019年9月6日星期五,第27页,2. 求表长,算法思路：设一个指针和计数器，初始化使指向头结点H，=0。若所指结点还有后继结点，向后移动，计数器加 1，重复上述过程，直到p-next=NULL为止。 【算法2.8】设H是带头结点的单链表，求带头结点单链表的表长。 Status Length_LinkList (LinkList H) LNode * p= H ; int j=0; while(p-next) p=p-next; j+； return j; ,2019年9月6日星期五,第28页,按序号查找第 k 个数据元素,LinkList Get_LinkList(LinkList H,int k); LNode *p=H; int j=0; while (p-next!=NULL ,例如： i =3: 当p指向85时， j=1； p指向60时， j=2； p指向76时， j=3； 退出循环。,例如： k =6 。 当p指向85时， j=1； 当p指向90时， j=5； 再执行p=p-next时， p= NULL，退出循环。,【时间复杂度均为O(n),2019年9月6日星期五,第29页,链表中查找 x 的算法实现,LNode * Locate_LinkList( LinkList H, ElemType x) LNode * p=H-next; while(p!=NULL ,例如：查找76，p指向76结点时，退出while循环，返回p指向的结点。,【时间复杂度均为O(n),2019年9月6日星期五,第30页,4插入操作,设p指向单链表中某结点，s指向待插入的新结点，将*s插入到*p的后面。, s-next=p-next; p-next=s;,将新结点*s 插入到*p 的前面，在插入操作前首先要找到 *p的前驱*q，然后再将*s 插入到*q 之后。,q=H; while (q-next!=p) q=q-next; s-next=q-next; q-next=s;,2019年9月6日星期五,第31页,【算法2.11】将新结点s插入到第i个结点的位置上，即插入到ai-1与ai 之间。 算法思路： (1) 查找第 i-1个结点；若存在继续(2)，否则结束； (2) 创建新结点； (3) 将新结点插入，结束。,2019年9月6日星期五,第32页,int Insert_LinkList( LinkList H, int i, ElemType x) /* 在单链表H的第i个位置上插入值为x的元素 */ LNode * p,*s; p=Get_LinkList(H,i-1); if (p=NULL) printf(插入位置i错);return ERROR; else s=(LinkList)malloc(sizeof(LNode); s-data=x; s-next=p-next; p-next=s； return OK; /* Insert_LinkList */,时间复杂度为O(n),2019年9月6日星期五,第33页,5. 删除操作,【算法2.12】删除链表中第 i 个结点。 算法思路： (1) 查找第 i-1 个结点；若存在，则继续(2)，否则结束； (2) 若存在第 i 个结点则继续(3)，否则结束； (3) 删除第 i 个结点，结束。, q-next=p-next; free(p);,2019年9月6日星期五,第34页,int Del_LinkList(LinkList H，int i) /* 删除单链表H上的第i个数据结点 */ LinkList p, q; p=Get_LinkList(H,i-1); if (p=NULL) printf(第i-1个结点不存在) ;return ERROR ; else if(p-next=NULL) printf(第i个结点不存在);return ERROR; else q=p-next; /* q指向第i个结点 */ p-next=q-next; free(q); return OK; /* Del_LinkList */,时间复杂度为O(n),2019年9月6日星期五,第35页,从上面的讨论可以看出： (1) 在单链表上插入、删除一个结点，必须知道其前驱结点。 (2) 单链表不具有按序号随机访问的特点，只能从头指针开始依次进行访问。 (3)链表上实现的插入和删除运算，不用移动结点，仅需修改指针。,考虑的几个问题：,(1)如果在链表中第i个结点后插入一个值为y的结点，如果i不存在，则把结点插在表尾。如何实现？,(2)如果在不带头结点的链表中第i （i=1）个结点前插入一个值为y的结点（在链表中值为x的结点前插入一个值为y的结点） ，如何实现？,2019年9月6日星期五,第36页,(2)删除所有值为x的结点，并返回1值为x的结点个数。,int Delete_Linkst2 (LNode *H, Elemtype x ) LNode *p, *q; q =H ; count=0; while( q -next ) p=q-next ; if(!p -data = =x) q-next=p-next ; /*逐个判断结点值，为x则删除*/ free(p); +count; /* count +1*/ else q=p; /* while */ return count; /* Delete_Linkst2 */,例如x =80的情况。,时间复杂度为O(n).,考虑不带表头结点的情况，删除算法相对考虑的因素要多些。,2.3.3 循环链表,单链表,双向链表,2019年9月6日星期五,第38页,定义：循环链表是另一种形式的链表存储结构，实现方法是将表中最后一个结点的指针域指向单链表的表头结点，这样就形成了一个环。这种结构便于查找结点。,循环条件： 1. 单链表的循环条件是 p 或 p-next 是否为空。 2. P 或 p-next 是否等于头结点 通常在循环链表中只设尾结点而不设头结点，这样尾结点就起到了既指头又指尾的功能。,2019年9月6日星期五,第39页,例如对两个单循环链表HA、HB的连接操作，： p=RAnext; RA-next=RB-next-next; free(RB-next); RB-next=p; 时间复杂度为O(1),2019年9月6日星期五,第40页,2.3.4 双向链表,问题的引出：在单链表中，从任何一个结点可以找到它的后继结点，但是寻找它的前趋结点，就需要从表头开始顺序查找。,定义：双向链表的每一个结点除了数据域外，还包括两个指针域，一个指向后继结点，另一个指针指向前趋结点。,双向循环链表,2019年9月6日星期五,第41页,特点: (1)可从两个方向搜索某个结点。 (2)无论利用向前这一链还是向后这一链，都可以遍历这个链表。特别是如果一根链失效了，还可以利用另一根链修复整个链表 。,双向链表结点的定义如下： typedef struct dlnode ElemType data; struct dlnode *prior, *next; DLNode, *DLinkList;,2019年9月6日星期五,第42页,当p指向双向循环链表中的某一结点时，则有以下等式： p-prior-next=p
- 温馨提示:
1: 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
2: 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
3.本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
人人文库网所有资源均是用户自行上传分享，仅供网友学习交流，未经上传用户书面授权，请勿作他用。
川公网安备: 51019002004831号