数据结构剖析课件

算法与数据结构算法与数据结构03 八月 20241课程学习课程学习教材：教材：数数据据结结构构（C语语言言版版）严严蔚蔚敏敏，吴吴伟伟民民 清清华华大大学学出出版版社社 2007参考书：参考书：数数据据结结构构（用用面面向向对对象象方方法法与与C+描描述述）殷殷人人昆昆等等 清清华华大大学学出版社出版社 1999数据结构教程数据结构教程(第第3版版)李春葆等李春葆等 清华大学出版社清华大学出版社 2009(另另配套学习指导和上机指导两书，作为参考）配套学习指导和上机指导两书，作为参考）学时：总学时学时：总学时72，理论，理论52，上机，上机20，4学时学时/周周考试方式：本课程为闭卷考试。其成绩评定方法：平时成绩占考试方式：本课程为闭卷考试。其成绩评定方法：平时成绩占30%，期末考试占，期末考试占70%。考试题型：选择题、填空题、判。考试题型：选择题、填空题、判断简答题、程序填空和设计题。考试时间：断简答题、程序填空和设计题。考试时间：110分钟。分钟。03 八月 20242教学方式教学方式l理论教学理论教学l习题课（每章一次，考研）习题课（每章一次，考研）l程序单步跟进与分析程序单步跟进与分析l上机实验（必须用上机实验（必须用Visual C+）03 八月 20243数据结构教学要求教材前言数据结构是一门专业技术基础课。要求：学会分析研究计算机加工的数据结构的特性，以便为应用涉及的数据选择适当的逻辑结构、存储结构及其相应算法，并初步掌握算法的时间和空间复杂度分析方法。03 八月 20244前期课程前期课程数据结构数据结构计算机基础计算机基础C语言语言离散数学离散数学后期课程后期课程操作系统操作系统编译原理编译原理数据库原理数据库原理软件工程软件工程算法设计与分析。承上承上启下启下计算机科学课程体系（偏软）03 八月 20245C语言语言数据结构数据结构软件工程软件工程掌握基本编掌握基本编程方法程方法掌握数据组掌握数据组织和数据处织和数据处理的方法理的方法掌握大型软掌握大型软件开发方法件开发方法学习识字学习识字学习写作文学习写作文学习写小说学习写小说基本要求课程关系与语文学习过程类比动手能力（上机）数据结构-数据组织与处理03 八月 20246算法-求解问题的策略迭代算法：递推法、倒推法、迭代法解方程蛮力法：选择排序、冒泡排序、插入排序、顺序查找、朴素的字符串匹配等分治法：折半查找（二分搜索）、合并排序、快速排序等贪心算法：哈夫曼编码（树）、迪杰斯特拉算法（图）、最小生成树（克鲁斯卡尔算法、普里姆算法）、分数背包等动态规划：最长公共子序列（串）、数塔问题、0/1背包（整数规划）图搜索算法：广度优先搜索：回溯法 深度优先搜索：分支限界法随机算法03 八月 20247与数据结构的区别：与数据结构的区别：考虑问题的考虑问题的角度角度：数据结构关心不同的数据结构在解题中：数据结构关心不同的数据结构在解题中的作用和效率；算法关心不同设计技术的适用性和效率。的作用和效率；算法关心不同设计技术的适用性和效率。考虑问题的考虑问题的高度高度：数据结构关心的是解具体问题，算法不：数据结构关心的是解具体问题，算法不仅如此，它提供一种解决问题的通用方法。仅如此，它提供一种解决问题的通用方法。数据结构&算法区别高级程序设计语言（C,C+）数据结构 算法设计与分析 03 八月 20248教学内容（数据结构穿插算法教学内容（数据结构穿插算法）第一章第一章 绪论绪论第二章第二章 线性表线性表第三章第三章 栈和队列栈和队列第四章第四章 串串第五章第五章 数组和广义表数组和广义表第六章第六章 树树第七章第七章 图图第九章第九章 查找查找第十章第十章 内部排序内部排序03 八月 20249第第1章章绪论绪论 1.2算法及其描述算法及其描述 1.1什么是数据结构什么是数据结构1.3算法分析基础算法分析基础 本章小结本章小结1.4数据结构算法程序数据结构算法程序 03 八月 2024101.1.1数据结构的定义数据结构的定义1.1.2逻辑结构类型逻辑结构类型 1.1.3存储结构类型存储结构类型1.1.4数据结构和数据类型数据结构和数据类型1.1 1.1 什么是数据结构什么是数据结构03 八月 202411数据数据：是所有能被输入到计算机中：是所有能被输入到计算机中,且能被计算机处理的且能被计算机处理的符号的集合。它是计算机操作的对象的总称符号的集合。它是计算机操作的对象的总称,也是计算机也是计算机处理的信息的某种特定的符号表示形式。处理的信息的某种特定的符号表示形式。数据元素数据元素：是数据：是数据(集合集合)中的一个中的一个“个体个体”,是数据的基是数据的基本单位。本单位。数据对象数据对象：是具有相同性质的若干个数据元素的集合。：是具有相同性质的若干个数据元素的集合。1.1.1数据结构的定义数据结构的定义03 八月 202412 例如例如,长江大学计科长江大学计科1205班为一个学生班为一个学生数据对象数据对象,而学生而学生“专志武专志武”就是其中的一个数据元素就是其中的一个数据元素)。数据结构数据结构：是指：是指数据数据以及数据元素相互之间的以及数据元素相互之间的联系联系。可以看。可以看作是相互之间存在着某种特定关系的数据元素的集合。作是相互之间存在着某种特定关系的数据元素的集合。因此因此,可时把可时把数据结构数据结构看成是带结构的数据元素的集合。看成是带结构的数据元素的集合。03 八月 202413数据结构数据结构包括如下几个方面：包括如下几个方面：数据元素之间的逻辑关系数据元素之间的逻辑关系,即数据的即数据的逻辑结构逻辑结构。数数据据元元素素及及其其关关系系在在计计算算机机存存储储器器中中的的存存储储方方式式,即即数数据据的的存储结构存储结构,也称为数据的物理结构。也称为数据的物理结构。施加在该数据上的操作施加在该数据上的操作,即数据的即数据的运算运算。03 八月 202414 例例1.1有有一一个个学学生生表表如如表表1.1所所示示。这这个个表表中中的的数数据据元元素素是是学学生生记记录录,每每个个数数据据元元素素由由四四个个数数据据项项(即即学学号号、姓姓别别、性别和班号性别和班号)组成。组成。03 八月 202415学号学号姓名姓名性别性别班号班号1张斌张斌男男99018刘丽刘丽女女990234李英李英女女990120陈华陈华男男990212王奇王奇男男990126董强董强男男99025王萍王萍女女9901表表1.1学生表学生表 逻辑结构表示逻辑结构表示103 八月 202416 该该表表中中的的记记录录顺顺序序反反映映了了数数据据元元素素之之间间的的逻逻辑辑关关系系,用用学学号标识每个学生记录号标识每个学生记录,这种这种逻辑关系逻辑关系可以表示为：可以表示为：,其其中中尖尖括括号号“”表表示示元元素素ai和和ai+1之之间间是是相相邻邻的的,即即ai在在ai+1之前之前,ai+1在在ai之后。之后。逻辑结构表示逻辑结构表示203 八月 202417数据在计算机存储器中的存储方式就是数据在计算机存储器中的存储方式就是存储结构存储结构。逻辑结构逻辑结构存储结构存储结构映射映射映射应满足两个条件：映射应满足两个条件：存储元素存储元素 存储关系存储关系03 八月 202418存放学生表的结构体数组存放学生表的结构体数组Stud定义为：定义为：struct int no;/存储学号存储学号 char name8;/存储姓名存储姓名 char sex2;/存储性别存储性别 char class4;/存储班号存储班号 Stud7=1,“张斌张斌”,“男男”,“9901”,5,王萍王萍,女女,9901;C/C+语语言言中中，通通常常采采用用结结构构体体数数组组和和链链表表两两种种方方式式实实现现其存储结构。其存储结构。03 八月 202419结构体数组结构体数组Stud各元素在内存中顺序存放各元素在内存中顺序存放,即第即第i(1i6)个个学生对应的元素学生对应的元素Studi存放在第存放在第i+1个学生对应的元素个学生对应的元素Studi+1之前之前,Studi+1正好在正好在Studi之后。之后。9901女王萍59901男张斌张斌1Stud0Stud6Stud数组起始地址数组起始地址存储结构表示存储结构表示103 八月 202420存放学生表的链表的结点类型存放学生表的链表的结点类型StudType定义为：定义为：typedef struct studnode int no;/存储学号存储学号 char name8;/存储姓名存储姓名 char sex2;/存储性别存储性别 char class4;/存储班号存储班号 struct studnode*next;/存储指向下一个学生的指针存储指向下一个学生的指针 StudType；03 八月 202421链表首结点地址链表首结点地址head1张斌张斌男男 99018刘丽刘丽女女 990234李英李英女女 990120陈华陈华男男 990212王奇王奇男男 990126董强董强男男 99025王萍王萍女女 9901学生表构成的链表如学生表构成的链表如右图所示。其中的右图所示。其中的head为第一个数据元为第一个数据元素的指针。素的指针。学生表构成的链表学生表构成的链表存储结构表示存储结构表示203 八月 202422 对对于于“学学生生表表”这这种种数数据据结结构构,可可以以进进行行一一系系列列的的运运算算,例例如如,增增加加一一个个学学生生记记录录、删删除除一一个个学学生生记记录录、查查找找性性别别为为“女女”的学生记录、查找班号为的学生记录、查找班号为“9902”的学生记录等等。的学生记录等等。运算运算运算运算03 八月 202423 例如例如,查找学号为查找学号为20的学生的姓名的学生的姓名：对对于于Stud数数组组：从从Stud0开开始始比比较较,Stud0.no不不等等于于20,再再与与Stud1.no比较比较,直到直到Stud3.no等于等于20,返回返回Stud3.name。9902男陈华209901男张斌张斌1Stud0Stud3i3运算的实现过程运算的实现过程运算的实现过程运算的实现过程1103 八月 202424对于对于head为首结点为首结点指针的链表：指针的链表：从从p=head所指结点开所指结点开始比较始比较,p-no不等于不等于20,从它的从它的next得到下一个得到下一个结点的地址结点的地址,再与下一个再与下一个结点的结点的no域比较域比较,直到直到某结点的某结点的no域等于域等于20,返返回其回其p-name域。域。head1张斌张斌男男 99018刘丽刘丽女女 990234李英李英女女 990120陈华陈华男男 990212王奇王奇男男 990126董强董强男男 99025王萍王萍女女 9901p运算的实现过程运算的实现过程运算的实现过程运算的实现过程2203 八月 202425结论：结论：同一逻辑结构可以对应多种存储结构。同一逻辑结构可以对应多种存储结构。同样的运算同样的运算,在不同的存储结构中在不同的存储结构中,其实现过程是不同其实现过程是不同的。的。03 八月 202426思考题：思考题：数据的逻辑结构和存储结构有什么不同？数据的逻辑结构和存储结构有什么不同？03 八月 202427 为了更确切地描述一种数据结构为了更确切地描述一种数据结构,通常采用通常采用二元组二元组表示：表示：B=(K,R)其中其中,B是一种数据结构是一种数据结构,它由数据元素的集合它由数据元素的集合K和和K上上二元关系的集合二元关系的集合R所组成。其中：所组成。其中：K=ki|1in,n0R=rj|1jm,m0 逻辑结构的描述或表示：逻辑结构的描述或表示：一种通用的逻辑结构表示方法一种通用的逻辑结构表示方法03 八月 202428其中：其中：uki表示集合表示集合K中的第中的第i个结点或数据元素。个结点或数据元素。un为为K中中结结点点的的个个数数,特特别别地地,若若n=0,则则K是是一一个个空空集集,因因而而B也就无结构可言也就无结构可言,有时也可以认为它具有任一结构。有时也可以认为它具有任一结构。urj表示集合表示集合R中的第中的第j个关系，每个关系用序偶表示。个关系，每个关系用序偶表示。um为为R中中关关系系的的个个数数,特特别别地地,若若m=0,则则R是是一一个个空空集集,表表明明集合集合K中的元结点间不存在任何关系中的元结点间不存在任何关系,彼此是独立的。彼此是独立的。03 八月 202429序偶序偶(x,yK)x为第一结点为第一结点,y为第二结点。为第二结点。x为为y的的直接前驱结点直接前驱结点(通常简称通常简称前驱结点前驱结点)y为为x的的直接后继结点直接后继结点(通常简称通常简称后继结点后继结点)。若若某某个个结结点点没没有有前前驱驱结结点点,则则称称该该结结点点为为开开始始结结点点；若若某某个个结点没有后继结点结点没有后继结点,则称该结点为则称该结点为终端结点终端结点。说明：说明：表示有向关系，表示有向关系，(x,y)表示无向关系。表示无向关系。采用离散数学的表示方法。采用离散数学的表示方法。03 八月 202430例如，有一个如下表所示的城市表，假设城市名是唯一的，例如，有一个如下表所示的城市表，假设城市名是唯一的，给出其逻辑结构的二元组表示。给出其逻辑结构的二元组表示。城市表城市表City中共有中共有5个记录，其逻辑结构的二元组表示如下：个记录，其逻辑结构的二元组表示如下：City=(D,R)D=Beijing,Shanghai,Wuhan,Xian,NanjingR=r只有一种关系只有一种关系r=,城市名城市名区号区号说明说明Beijing010首都首都Shanghai021直直辖市市Wuhan027湖北省省会湖北省省会Xian029陕西省省会西省省会Nanjing025江江苏省省会省省会03 八月 202431又例如又例如,有如下数据即一个矩阵：有如下数据即一个矩阵：对应的二元组表示为对应的二元组表示为B=(K,R),其中：其中：K=2,6,3,1,8,12,7,4,5,10,9,11R=r1,r2其中其中,r1表示行关系表示行关系,r2表示列关系表示列关系r1=,r2=,一个二维数组一个二维数组03 八月 202432 可以可以利用图形形象地表示逻辑结构。利用图形形象地表示逻辑结构。例如，上述例如，上述“学生表学生表”数据结构用下图的图形表示。数据结构用下图的图形表示。学生表数据结构图示学生表数据结构图示03 八月 202433 (1)线性结构线性结构 结点之间关系：结点之间关系：一对一。一对一。特特点点：开开始始结结点点和和终终端端结结点点都都是是唯唯一一的的,除除了了开开始始结结点点和和终终端端结结点点以以外外,其其余余结结点点都都有有且且仅仅有有一一个个前前驱驱结结点点,有有且且仅仅有有一一个个后继结点。顺序表就是典型的线性结构。后继结点。顺序表就是典型的线性结构。1.1.2逻辑结构类型逻辑结构类型 03 八月 202434线性结构示例例1 图书馆的书目自动检索系统（线性表）03 八月 202435 (2)树形结构树形结构 结点之间关系：结点之间关系：一对多。一对多。特特点点：开开始始结结点点唯唯一一,终终端端结结点点不不唯唯一一。除除终终端端结结点点以以外外,每每个个结结点点有有一一个个或或多多个个后后续续结结点点；除除开开始始结结点点外外，每个结点有且仅有一个前驱结点。每个结点有且仅有一个前驱结点。03 八月 202436 例2 人机对弈问题（三子棋）（树）OXXOXOXXXOXOXXOXOXXOOXXXOOXXO树形结构实例树形结构实例03 八月 202437 (3)图形结构图形结构 结点之间关系：结点之间关系：多对多。多对多。特特点点：没没有有开开始始结结点点和和终终端端结结点点，所所有有结结点点都都可可能有多个前驱结点和多个后继结点。能有多个前驱结点和多个后继结点。03 八月 202438例3 田径赛的时间安排问题（图）设有六个比赛项目，规定每个选手至多可参加三个项目，有五人报名参加比赛（如下表所示）设计比赛日程表，使得在尽可能短的时间内完成比赛。1、设用如下六个不同的代号代表不同的项目：跳高 跳远 标枪 铅球 100米 200米A B C D E F2、不能同时进行比赛的项目之间连上一条边EABFDC图形结构实例图形结构实例03 八月 202439(2)链式存储方法链式存储方法(3)索引存储方法索引存储方法(4)散列（哈希）存储方法散列（哈希）存储方法1.1.3存储结构类型存储结构类型(1)顺序存储方法顺序存储方法前面通过示例已介绍前面通过示例已介绍第第9章介绍（操作系统中文章介绍（操作系统中文件系统的存储方式）件系统的存储方式）03 八月 202440(1)数据类型数据类型高级程序语言中高级程序语言中,一般须对程序中出现的每个变量、常量或一般须对程序中出现的每个变量、常量或表达式表达式,明确说明它们所属的数据类型。不同类型的变量明确说明它们所属的数据类型。不同类型的变量,其所其所能取的值的范围不同能取的值的范围不同,所能进行的操作不同。所能进行的操作不同。数据类型数据类型是一个值的集合和定义在此集合上的一组操作是一个值的集合和定义在此集合上的一组操作的总称。的总称。1.1.4数据结构和数据类型数据结构和数据类型 03 八月 202441 如如C/C+中的中的int就是整型数据类型。它是所有整数的集合就是整型数据类型。它是所有整数的集合(在在16位计算机中为位计算机中为3276832767的全体整数的全体整数)和相关的整数和相关的整数运算运算(如、等如、等)。int i=2,j=5,k;k=i+j;.因为因为i、j和和k都属于都属于int，而，而int提供了各种运算，所以可以进行提供了各种运算，所以可以进行相应运算。相应运算。int i=9999999999;i*;03 八月 202442 (2)抽象数据类型抽象数据类型抽象数据类型抽象数据类型(AbstractDataType简写为简写为ADT)指的是用指的是用户进行软件系统设计时从问题的数学模型中抽象出来的逻辑户进行软件系统设计时从问题的数学模型中抽象出来的逻辑数据结构和逻辑数据结构上的运算数据结构和逻辑数据结构上的运算,而不考虑计算机的具体存而不考虑计算机的具体存储结构和运算的具体实现算法。储结构和运算的具体实现算法。抽象数据类型抽象数据类型=数据元素集合抽象运算数据元素集合抽象运算 抽象数据类型实质上就是描述一个求解问题本身（与计算抽象数据类型实质上就是描述一个求解问题本身（与计算机无关），计算机人员就是在理解问题基础上实现用计算机机无关），计算机人员就是在理解问题基础上实现用计算机求解问题的过程。求解问题的过程。03 八月 202443例如例如,抽象数据类型抽象数据类型复数复数的定义：的定义：ADTComplex数据对象：数据对象：D=e1,e2|e1,e2均为实数均为实数数据关系：数据关系：R1=|e1是复数的实数部分是复数的实数部分,e2是复数的是复数的虚数部分虚数部分e1e2i（e1，e2）03 八月 202444基本操作：基本操作：AssignComplex(&Z,v1,v2)：构造复数：构造复数Z。DestroyComplex(&Z):复数复数Z被销毁。被销毁。GetReal(Z,&real):返回复数返回复数Z的实部值。的实部值。GetImag(Z,&Imag):返回复数返回复数Z的虚部值。的虚部值。Add(z1,z2,&sum):返回两个复数返回两个复数z1,z2的和。的和。ADTComplex03 八月 202445思考题：思考题：数据类型和抽象数据类型有什么不同？数据类型和抽象数据类型有什么不同？03 八月 2024461.2算法及其描述算法及其描述 1.2.1什么是算法什么是算法 1.2.2算法描述算法描述03 八月 2024471.2.1什么是算法什么是算法 数据元素之间的关系有逻辑关系和物理关系数据元素之间的关系有逻辑关系和物理关系,对应的对应的操作有操作有逻辑结构上的操作功能逻辑结构上的操作功能和和具体存储结构上的操作实具体存储结构上的操作实现现。通常把具体存储结构上的操作通常把具体存储结构上的操作实现实现步骤或过程称为步骤或过程称为算算法法。属属ADT的一部分的一部分算法算法03 八月 202448算法的五个重要的特性算法的五个重要的特性(1)有穷性有穷性:在有穷步之后结束。在有穷步之后结束。(2)确定性确定性:无二义性。无二义性。(3)可行性可行性:可通过基本运算有限次执行来实现。可通过基本运算有限次执行来实现。(4)有输入有输入 (5)有输出有输出 表示存在数据处理表示存在数据处理03 八月 202449例例考虑下列两段描述：考虑下列两段描述：(1)描述一描述一void exam1()int n2;while(n%20)nn+2;printf(%dn,n);华中科大考研题华中科大考研题03 八月 202450(2)描述二描述二void exam2()int x,y;y=0;x=5/y;printf(“%d,%dn”,x,y);这这两两段段描描述述均均不不能能满满足足算算法法的的特特征征,试试问问它它们们违违反反了了哪哪些特征？些特征？03 八月 202451 解：解：(1)算法是一个死循环算法是一个死循环,违反了算法的有穷性特征。违反了算法的有穷性特征。(2)算法包含除零错误算法包含除零错误,违反了算法的可行性特征违反了算法的可行性特征。03 八月 202452思考题：思考题：算法和程序有什么不同？算法和程序有什么不同？03 八月 2024531.2.2算法描述算法描述 本书中采用本书中采用C/C+语言描述算法。语言描述算法。03 八月 202454 例例1.3编编写写一一个个算算法法,读读入入三三个个整整数数x,y和和z的的值值,要要求求从从大大到到小小输出这三个数。输出这三个数。解解：依依次次输输入入x,y和和z这这三三个个整整数数,通通过过比比较较交交换换后后,使使得得xyz,然后输出然后输出x,y,z。在在算算法法中中应应考考虑虑对对这这三三个个元元素素作作尽尽可可能能少少的的比比较较和和移移动动,如如下述算法在最坏的情况下只需进行下述算法在最坏的情况下只需进行3次比较和次比较和7次移动。次移动。用用C/C+描述算法示例描述算法示例03 八月 202455void Descending()printf(输入输入x,y,z);scanf(%d,%d,%d,&x,&y,&z);if(x=y if(yz if(x=temp)y=temp；else y=x;x=temp;printf(%d,%d,%dn,x,y,z);03 八月 2024561.3算法分析算法分析 1.3.1算法时间复杂度分析算法时间复杂度分析 1.3.2算法空间复杂度分析算法空间复杂度分析 03 八月 202457一一个个算算法法是是由由控控制制结结构构(顺顺序序、分分支支和和循循环环三三种种)和和原原操操作作(指指固固有有数数据据类类型型的的操操作作)构构成成的的,则则算算法法时时间间取取决于两者的综合效果。决于两者的综合效果。1.3.1算法时间复杂度分析算法时间复杂度分析 控制语句控制语句1原操作原操作控制语句控制语句n原操作原操作一个算法的构成一个算法的构成03 八月 202458同同一一问问题题可可以以采采用用多多种种算算法法实实现现。如如何何比比较较算算法执行效率？法执行效率？算法描述的语言不同算法描述的语言不同算法执行的环境不同算法执行的环境不同 其他因素其他因素 所以不能用绝对执行时间进行比较所以不能用绝对执行时间进行比较03 八月 202459为为了了便便于于比比较较同同一一问问题题的的不不同同算算法法,通通常常从从算算法法中中选选取取一一种种对对于于所所研研究究的的问问题题来来说说是是基基本本运运算算的的原原操操作作(以以下下将基本运算的原操作简称为将基本运算的原操作简称为基本运算基本运算)。算算法法执执行行时时间间大大致致为为基基本本运运算算所所需需的的时时间间与与其其运运算算次次数数(也称为频度也称为频度)的乘积。的乘积。被视为算法被视为算法基本运算基本运算的一般是最深层循环内的语句。的一般是最深层循环内的语句。03 八月 202460频率计数：频率计数：算法中算法中语句句或或运算运算的的执行次数。行次数。例：例：x=x+y for(i=1;i=n;i+)for(i=1;i=n;i+)x=x+y;for(j=1;j=n;j+)x=x+y;(a)(b)(c)分析：分析：(a)：x=x+y执行了行了1次次 (b)：x=x+y执行了行了n次次 (c)：x=x+y执行了行了n2次次 注：在事前分析中，只限于确定与所使用机器及其他环境注：在事前分析中，只限于确定与所使用机器及其他环境因素无关的频率计数，依此建立一种理论上分析模型。因素无关的频率计数，依此建立一种理论上分析模型。03 八月 202461数量级数量级语句的数量级语句的数量级：语句的执行频率。：语句的执行频率。例：例：1，n，n2 算法的数量级算法的数量级：算法包含所有语句的执行频率之和。：算法包含所有语句的执行频率之和。算法的数量级从本质上反映了一个算法的执行特性。算法的数量级从本质上反映了一个算法的执行特性。例：求解同一问题的三个算法分别具有例：求解同一问题的三个算法分别具有n,n2,n3数量级。数量级。若若n=10，则可能的执行时间将分别是，则可能的执行时间将分别是10，100，1000 个单位时间个单位时间与环境因素无关。与环境因素无关。03 八月 2024622.1.5.计算时间的渐近表示计算时间的渐近表示记：算法的计算时间为记：算法的计算时间为f(n)数量级限界函数为数量级限界函数为g(n)其中，其中，n是输入或输出规模的某种测度。是输入或输出规模的某种测度。f(n)表示算法的表示算法的“实际实际”执行时间执行时间与机器及语言有关与机器及语言有关。g(n)是是形式简单形式简单的函数，如的函数，如nm，logn，2n，n!等。是等。是事前分析中通过对计算时间或频率计数统计分析所得的事前分析中通过对计算时间或频率计数统计分析所得的与与机器及语言无关机器及语言无关的函数。的函数。以下给出算法执行时间：以下给出算法执行时间：上界上界（）、）、下界下界（）、）、“平均平均”（）的定义。）的定义。03 八月 2024渐进意义下的记号：渐进意义下的记号：O,定义定义1.1 如果存在两个正常数如果存在两个正常数c和和N0,对于所有的对于所有的NN0，有，有|f(N)|C|g(N)|，则记作：作：f(N)=O(g(N)。N0f(N)g(N)当说一个算法具有O(g(n)的计算时间时，指的就是如果此算法用n值不变的同一类数据在某台机器上运行时，所用的时间总是小于g(n)的一个常数倍。g(n)是计算时间f(n)的一个上界函数，f(n)的数量级就是g(n)。03 八月 2024Example因为对所有的因为对所有的N N11有有3 3N N44N N，所以有，所以有3 3N N=O O(N N););因为当因为当N N11时有时有N N+10241025+10241025N N，所以有，所以有N N+1024=+1024=O O(N N););因为当因为当N N1010时有时有2 2N N2 2+11+11N N-103-103N N2 2,所以有所以有 2 2N N2 2+11+11N N-10=-10=O O(N N2 2)因为对所有因为对所有N N11有有N N2 2N N2 2,我们有我们有N N2 2=O O(N N2 2)作为一个反例作为一个反例N N3 3O O(N N2 2),),因为若不然，则存在正因为若不然，则存在正的常数的常数C C和自然数和自然数N N0 0,使得当使得当N NN N0 0，有有N N3 3CNCN2 2,即即N NC C。显然，当取。显然，当取N N=max=maxN N0 0,C C+1+1时这个不等式不时这个不等式不成立，所以成立，所以N N3 3O O(N N2 2)03 八月 202465多项式定理多项式定理:定理定理1.1 若若A(n)=amnm+a+a1 1n+an+a0 0是一个是一个m m次次多项多项 式，则有式，则有A(n)=A(n)=(nm)即：变量即：变量n n的固定阶数为的固定阶数为m m的任一多项式，与此多的任一多项式，与此多 项式的最高阶项式的最高阶nm同阶。同阶。证明：取证明：取n n0 0=1,=1,当当nnnn0 0时，有时，有|A(n)|am|nm+|a1|n+|a0|(|am|+|am-1|/n+|a0|/nm)nm (|am|+|am-1|+|a0|)nm 令令c=|am|+|am-1|+|a0|定理得证。定理得证。03 八月 202466 计算时间的数量级对算法有效性的影响计算时间的数量级对算法有效性的影响 数量级数量级的大小对算法的有效性有的大小对算法的有效性有决定性决定性的影响。的影响。例：假设解决同一个问题的两个算法，它们都有例：假设解决同一个问题的两个算法，它们都有n个输个输入，计算时间的数量级分别是入，计算时间的数量级分别是n2和和nlogn。则：。则：n=1024：分别需要：分别需要1048576和和10240次运算。次运算。n=2048：分别需要：分别需要4194304和和22528次运算。次运算。分析：在分析：在n加倍的情况下，一个加倍的情况下，一个(n(n2 2)的算法计算时间增长的算法计算时间增长4 4 倍，而一个倍，而一个(nlogn)(nlogn)算法则只用算法则只用两两倍多一点的时间即倍多一点的时间即 可完成。可完成。03 八月 202467 算法分类（计算时间）算法分类（计算时间）多项式时间算法：多项式时间算法：可用多项式（函数）对其计算可用多项式（函数）对其计算时间限界的算法。时间限界的算法。常见的多项式限界函数有：常见的多项式限界函数有：(1)(1)(logn)(logn)(n)(n)(nlogn)(nlogn)(n(n2 2)(n(n3 3)指数时间算法：指数时间算法：计算时间用指数函数限界的算法计算时间用指数函数限界的算法 常见的指数时间限界函数：常见的指数时间限界函数：(2(2n n)(n(n！)0 0，则则f(n)=f(n)=(n(nm m)。该定义的优点是与该定义的优点是与O O的定义对称，缺点是的定义对称，缺点是f f(N N)对自然对自然数的不同无穷子集有不同的表达式，且有不同的阶数的不同无穷子集有不同的表达式，且有不同的阶时，不能很好地刻画出时，不能很好地刻画出f f(N N)的下界。的下界。比如当比如当100N为正偶数为正偶数 f(N)=6N2 N为正奇数为正奇数按照定义，得到按照定义，得到f f(N N)=)=(1),(1),这是个平凡的下界，对这是个平凡的下界，对算法分析没有什么价值。算法分析没有什么价值。03 八月 202472定义定义1.3如果存在正常数如果存在正常数c1，c2和和n0，对于所有的，对于所有的nn0，有，有c1|g(N)|f(N)|c2|g(N)|则记作则记作f(N)=(g,(N)含义：含义：算法在最好和最坏情况下的计算时间就一个常数因子范算法在最好和最坏情况下的计算时间就一个常数因子范围内而言是相同的。可看作：围内而言是相同的。可看作：既有既有f(N)=f(N)=(g(N)(g(N)，又有，又有f(N)=f(N)=(g(N)(g(N)“平均情况”限界函数03 八月 202403 八月 202474思考题：思考题：为什么要进行算法的时间复杂度分析？为什么要进行算法的时间复杂度分析？03 八月 202475例例1.4求求两两个个n阶阶方方阵阵的的相相加加C=A+B的的算算法法如如下下,分分析其时间复杂度。析其时间复杂度。#define MAX 20 /定义最大的方阶定义最大的方阶 void matrixadd(int n,int AMAXMAX,int BMAXMAX,int CMAXMAX)int i,j;for(i=0;in;i+)for(j=0;jn;j+)Cij=Aij+Bij;03 八月 202476 该该 算算 法法 中中 的的 基基 本本 运运 算算 是是 两两 重重 循循 环环 中中 最最 深深 层层 的的 语语 句句Cij=Aij+Bij,分析它的频度分析它的频度,即：即：T(n)=O(n2)03 八月 202477例例1.5分析以下算法的时间复杂度。分析以下算法的时间复杂度。int fun(int n)int i,j,k,s;s=0;for(i=0;i=n;i+)for(j=0;j=i;j+)for(k=0;k=j;k+)s+;return(s);基本语句或基本操作基本语句或基本操作03 八月 202478 解：解：该算法的基本操作是语句该算法的基本操作是语句s+,其频度：其频度：T(n)=O(n3)则该算法的时间复杂度为则该算法的时间复杂度为O(n3)。03 八月 202479例例1.6 分析以下算法的时间复杂度。分析以下算法的时间复杂度。void func(int n)int i=0,s=0;while(sn)i+;s=s+i;基本语句基本语句03 八月 202480解：对于解：对于while循环语句，设执行的次数为循环语句，设执行的次数为m，i从从0开始递增开始递增1，直到，直到m为止，有：为止，有：s=0+1+2+(m-1)=m(m-1)/2，并满足并满足s=m(m-1)/2n，则有，则有m。T(n)=O()所以，该算法的时间复杂度为所以，该算法的时间复杂度为O()。03 八月 202481例例1.7有如下算法：有如下算法：void fun(int a,int n,int k)/数组数组a共有共有n个元素个元素 int i;if(k=n-1)for(i=0;in;i+)/n次次 printf(%dn,ai);else for(i=k;in;i+)/n-k次次ai=ai+i*i;fun(a,n,k+1);调用上述算法的语句为调用上述算法的语句为fun(a,n,0)，求其时间复杂度。，求其时间复杂度。03 八月 202482解解：设设fun(a,n,0)的的时时间间复复杂杂度度为为T(n),则则fun(a,n,k)的的执执行行时间为时间为T1(n,k)，由，由fun()算法可知：算法可知：T1(n,k)=n当当k=n-1时时T1(n,k)=(n-k)+T1(n,k+1)其他情况其他情况则则T(n)=T1(n,0)=n+T1(n,1)=n+(n-1)+T1(n,2)=n+(n-1)+2+T1(n,n-1)=n+(n-1)+2+n=O(n2)所以调用所以调用fun(a,n,0)的时间复杂度为的时间复杂度为O(n2)。03 八月 202483空间复杂度空间复杂度是对一个算法在运行过程中是对一个算法在运行过程中临时占用的存储空间临时占用的存储空间大小的量度大小的量度,一般也作为问题规模一般也作为问题规模n的函数的函数,以数量级形式给出以数量级形式给出,记记作：作：S(n)=O(g(n)若若所所需需额额外外空空间间相相对对于于输输入入数数据据量量来来说说是是常常数数,则则称称此此算算法法为为原原地地工工作作。若若所所需需存存储储量量依依赖赖于于特特定定的的输输入入,则则通通常常按按最最坏坏情情况况考虑。考虑。1.3.2 1.3.2 算法空间复杂度分析算法空间复杂度分析 03 八月 202484 例例1.8分析例分析例1.4和例和例1.5的空间复杂度。的空间复杂度。解：由于这两个算法中临时变量的个数与问题规模解：由于这两个算法中临时变量的个数与问题规模n无关无关,所以空间复杂度均为所以空间复杂度均为O(1)。03 八月 2024851.4数据结构算法程序数据结构算法程序 数据结构对算法的影响主要在两方面数据结构对算法的影响主要在两方面 数据结构的存储能力数据结构的存储能力数据结构存储能力强、存储信息多算法将会较好设数据结构存储能力强、存储信息多算法将会较好设计（时间少），存储空间大。计（时间少），存储空间大。时间和空间的平衡时间和空间的平衡定义在数据结构上的操作定义在数据结构上的操作在数据结构上定义基本操作算法调用这些基本操作。在数据结构上定义基本操作算法调用这些基本操作。03 八月 202486基本操作越完整，基本操作越完整，算法设计就越容算法设计就越容易易算法算法基本操作基本操作基本算法基本算法应用程序应用程序应用程序是通过应用程序是通过调用基本算法实调用基本算法实现的现的03 八月 202487选择数据结构需要考虑的几个方面：选择数据结构需要考虑的几个方面：数据结构要适应问题的状态描述。数据结构要适应问题的状态描述。数据结构应与所选择的算法相适应。数据结构应与所选择的算法相适应。数据结构的选择同时要兼顾程序设计的方便。数据结构的选择同时要兼顾程序设计的方便。灵活应用已有知识。灵活应用已有知识。03 八月 202488问题描述：问题描述：有若干学生数据（学生数小于有若干学生数据（学生数小于50），），每个学生数据包含学号（每个学生学号是唯一的，每个学生数据包含学号（每个学生学号是唯一的，但学生记录不一定按学号顺序存放）、姓名、班但学生记录不一定按学号顺序存放）、姓名、班号和若干门课程成绩（每个学生所选课程数目可号和若干门课程成绩（每个学生所选课程数目可能不等，但最多不超过能不等，但最多不超过6门）。门）。要求：要求：设计一个程序输出每个学生的学号、姓名设计一个程序输出每个学生的学号、姓名和平均分以及每门课程（课程编号从和平均分以及每门课程（课程编号从16）的平）的平均分。均分。03 八月 202489设计方案设计方案1：将学生的全部数据项放在一个表中，一将学生的全部数据项放在一个表中，一个学生的全部数据对应一条记录。由于课程最多可选个学生的全部数据对应一条记录。由于课程最多可选6门，门，对应的成绩项也应有对应的成绩项也应有6个。对应的数据结构如下：个。对应的数据结构如下：struct studint no;/学号学号char name10;/姓名姓名int bno;/班号班号int deg1;/课程课程1分数分数int deg2;/课程课程2分数分数int deg3;/课程课程3分数分数int deg4;/课程课程4分数分数int deg5;/课程课程5分数分数int deg6;/课程课程6分数分数;03 八月 202490nonamebnodeg1deg2deg3deg4deg5deg61张斌张斌99017882639285838刘丽刘丽9902659572788079特点：特点：存储空间：中（若学生没有选该课程，对应空间仍存在）存储空间：中（若学生没有选该课程，对应空间仍存在）算法时间：少算法时间：少 算法简洁性差：算法完全依赖数据结构算法简洁性差：算法完全依赖数据结构存储结构存储结构103 八月 202491设计方案设计方案2：将学生的全部数据项放在一个表中，但一：将学生的全部数据项放在一个表中，但一个学生的一门课程成绩对应一条记录。这样成绩项只需要个学生的一门课程成绩对应一条记录。这样成绩项只需要一个，为了区分不同课程成绩，需增加一个课程编号项。一个，为了区分不同课程成绩，需增加一个课程编号项。对应的数据结构如下：对应的数据结构如下：struct studint no;/学号学号char name10;/姓名姓名int bno;/班号班号int cno;/课程编号课程编号int deg;/课程分数课程分数;03 八月 202492nonamebnocnodeg1张斌张斌99011781张斌张斌99012821张斌张斌99013631张斌张斌99014921张斌张斌99015851张斌张斌99016838刘丽刘丽99021658刘丽刘丽99022958刘丽刘丽99023728刘丽刘丽99024788刘丽刘丽99025808刘丽刘丽9902679存储结构存储结构203 八月 202493特点：特点：存储空间：大存储空间：大 算法时间：多算法时间：多 算法简洁性：好算法简洁性：好03 八月 202494设计方案设计方案3：将学生的学号、姓名和班号放在一个表中，将学生的学号、姓名和班号放在一个表中，将成绩数据放在另一个表中，两者通过学号关联。前者一将成绩数据放在另一个表中，两者通过学号关联。前者一个学生对应一个记录，后者一门课程成绩对应一条记录。个学生对应一个记录，后者一门课程成绩对应一条记录。对应的数据结构如下：对应的数据结构如下：struct stud1int no;/学号学号char name10;/姓名姓名int bno;/班号班号;struct stud2int no;/学号学号int cno;/课程编号课程编号int deg;/分数分数;03 八月 202495nonamebno1张斌张斌99018刘丽刘丽9902nocnodeg117812821363149215851683816582958372847885808679关联关联存储结构存储结构303 八月 202496特点：特点：存储空间：少。存储空间：少。算法时间：中。算法时间：中。算法简洁性：好。算法简洁性：好。最佳方案最佳方案03 八月 202497数据结构数据结构算法算法数据类型数据类型ijk求解问题编写程序的代码：求解问题编写程序的代码：ijk种种优优选选最佳方案最佳方案本课程的目标本课程的目标:确定求解问题的最佳方案确定求解问题的最佳方案03 八月 202498思考题：思考题：学习第学习第1章有什么体会？章有什么体会？03 八月 202499本章小结本章小结 本章介绍了数据结构的基本概念本章介绍了数据结构的基本概念,主要学习要点如下：主要学习要点如下：(1)数数据据结结构构的的定定义义,数数据据结结构构包包含含的的逻逻辑辑结结构构、存存储储结结构构和运算三方面的相互关系。和运算三方面的相互关系。(2)各各种种逻逻辑辑结结构构即即线线性性结结构构、树树形形结结构构和和图图形形结结构构之之间间的差别。的差别。03 八月 2024100(3)数据结构和数据类型的差别和联系。数据结构和数据类型的差别和联系。(4)算法的定义及其特性。算法的定义及其特性。(5)算法的时间复杂度和空间复杂度分析。算法的时间复杂度和空间复杂度分析。熟悉熟悉VC+6.0环境环境03 八月 2024101