大学《数据结构教程》(第5版)---李春葆-----清华大学出版社课件第1章-绪论

数据结构目标:一方面理解数据结构中的基本概念掌握几种常见逻辑结构对应的算法及相应存储结构上的算法实现初步了解算法的时间复杂度和空间复杂度分析方法。课程教学目标及要求另一方面通过本课程算法设计和上机实现的训练，培养学生联系实际分析问题、解决问题的能力，提高编程能力和自学能力。同时为算法设计与分析、操作系统、编译原理等后续课程的学习奠定良好的编程基础要求:多读、多想、多练课程教学目标及要求总学时：48理论学时：32实验学时：16教材：《数据结构教程》(第5版)李春葆清华大学出版社教学参考书：(1)《数据结构》严蔚敏吴伟民清华大学出版社(2)《数据结构算法解析》高一凡清华大学出版社课程安排第1章：绪论第2章：线性表（重点）第3章：栈和队列（重点）第4章：串、多维数组与广义表第5章：树和二叉树（重点）第6章：图（重点）第7章：查找（重点）第8章：内部排序（重点）课程内容数据结构第1章绪论数据结构的基本概念本章知识要点：数据类型和抽象数据类型算法和算法分析1、了解数据、数据对象、数据元素、数据项、数据类型、数据结构、数据的逻辑结构与物理结构概念及逻辑结构与物理结构间的关系2、了解算法的定义、算法的特性、算法的时间代价、算法的空间代价3、掌握计算语句频度和估算算法时间复杂度的方法教学要求重点：1、基本概念：数据、数据对象、数据元素、数据项、数据类型、数据结构、数据的逻辑结构、物理结构等2、算法含义、特性、算法时间复杂度分析难点：算法时间复杂度分析重点、难点1.1数据结构的基本概念1.1.1数据结构的研究内容1.1.2基本概念和术语1.1.3数据结构课程的内容1.1.1数据结构的研究内容数据结构主要研究非数值计算问题。（多种复杂的具有一定结构关系的数据）例1-1电话号码查询问题：电话号码薄(a1,b1)(a2,b2)…..(an,bn)其中：ai为某人姓名，bi为该人的电话号码；要求：设计一个算法，给定一个姓名时能查出此人的电话号码？非数值计算问题：如果姓名和电话号码的排列次序无规律，则只能逐一比较姓名进行查找；如果姓名是按字典顺序组织，则查找就快捷多了；要写出好的查找算法，取决于这张表的结构及存储方式电话号码表的结构和存储方式决定了查找（算法）的效率。诸如此类的还有考试成绩查询问题、企业进、销、存管理系统等。例1-2田径赛的时间安排问题（无向图的着色问题）：设有六个比赛项目，规定每个选手至多可参加三个项目，有五人报名参加比赛（如下表所示）设计比赛日程表，使得在尽可能短的时间内完成比赛。非数值计算问题：姓名项目1项目2项目3丁一跳高跳远100米马二标枪铅球张三标抢100米200米李四铅球200米跳高王五跳远200米（1）设用如下六个不同的代号代表不同的项目：跳高跳远标枪铅球100米200米ABCDEF（2）用顶点代表比赛项目不能同时进行比赛的项目之间连上一条边。（3）某选手比赛的项目必定有边相连（不能同时比赛）。非数值计算问题----田径赛的时间安排问题解法姓名项目1项目2项目3丁一ABE马二CD张三CEF李四DFA王五BFAEBFDC比赛时间比赛项目1A，C2B，D3E4F只需安排四个单位时间进行比赛不直接相连的顶点就可以同时进行比赛求解非数值计算的问题：主要考虑的是设计出合适的数据结构及相应的算法。即：首先要考虑对相关的各种信息如何表示、组织和存储？因此，可以认为：数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作的学科。是介于数学、计算机硬件和软件之间的一门核心课程。硬件软件（计算机系统设计）（计算机程序设计）存储设备数据类型数据结构数据表示数据存取机器组织编码原理算子关系数据运算数学代数关系数据结构----学习数据结构有什么用？答：计算机内的数值运算依靠方程式，而非数值运算（如表、树、图等）则要依靠数据结构。程序设计的实质是对实际问题选择一个好的数据结构，加之设计一个好的算法。而好的算法在很大程度上取决于描述实际问题的数据结构。同样的数据对象，用不同的数据结构来表示，运算效率可能有明显的差异。1.1.2基本概念和术语(学籍信息表)•数据（Data）：是信息的载体，能够被计算机识别、存储和加工处理。•数据元素（DataElement）：是数据的基本单位。•数据项（DataItem）：是组成数据元素的、有独立含义、不可分割的最小单位。•数据对象（DataObject）：是相同性质的数据元素的集合，是数据集合的一个子集。•数据结构（DataStructure）：是指互相之间存在着一种或多种特定关系的数据元素的集合。数据结构的形式定义为一个二元组：Data_Structure=(D，R)其中，D是数据元素的有限集，R是D上关系的有限集。数据结构包括数据的逻辑结构和数据的存储结构。逻辑结构（a）集合结构（b）线性结构（c）树结构(d）图结构有一数据结构采用二元组描述为D_S=(D，R)，其中：D={a，b，c，d，e，f，g}；R={e，d，d，c，c，a，a，b，b，f，f，g}acdegfb【例1-3】存储结构1）顺序存储结构2）链式存储结构04020400地址内容5.0-5.32字节地址04020400内容5.005152字节0515-5.3存储结构3）索引存储结构P84）哈希（或散列）存储结构P8数据运算数据的运算主要有修改、插入、删除、查找、排序。1.1.3数据结构课程的内容数据结构的内容可归纳为三个部分：逻辑结构、存储结构和数据运算。1.2数据类型和抽象数据类型1.2.1数据类型1.2.2抽象数据类型1.2.1数据类型数据类型（DataType）是一个值的集合和定义在这个值集上的一组操作的总称。数据类型中定义了两个集合，即该类型的取值范围及该类型中可允许使用的一组运算。比如：整型1.2.2抽象数据类型抽象数据类型:用于表示实际应用问题的数据模型以及定义在该模型上的一组操作;可用以下三元组表示：ADT=（D,S,P）其中：D是数据元素的有限集；S是D上关系集；P是对D的基本操作集。1.2.2抽象数据类型抽象数据类型的定义格式如下：ADT抽象数据类型名｛数据对象：数据对象的定义结构关系：结构关系的定义基本操作：基本操作的定义｝ADT抽象数据类型名1.2.2抽象数据类型抽象数据类型的2个重要特征：P14数据抽象(抽象出数据的逻辑结构和逻辑结构上的运算)数据封装(把外部特性和内部实现细节分离,并对用户隐藏实现细节—汽车空调按钮)给出“线性表”的抽象数据类型的定义【例1-4】ADTList{数据元素：所有ai属于同一数据对象，i=1，2，…，n，n≥0；[用一组人排队来想]结构关系：所有数据元素ai（i=1，2，…，n-1）存在次序关系ai，ai+1，a1无前趋，an无后继；基本操作：设L为List，则有InitList(L)：初始化线性表；ListLength(L)：求线性表的表长；GetData(L,i)：取线性表的第i个元素；InsList(L,i,b)：在线性表的第i个位置插入元素b；DelList(L,i)：删除线性表的第i个数据元素；}ADTList;1.3算法和算法分析1.3.1算法特性1.3.2算法描述1）有穷性(有穷步、每一步对应有穷的时间)2）确定性(含义确定、输入相同时结果确定）（咬死了猎人的狗）3）可行性(每一个操作都能准确执行。例：x/0？）4）输入(0个或多个输入）5）输出(1个或多个输出）1.3.1算法特性算法的含义：对特定问题求解步骤的一种描述算法具有5个重要特性：P14【例1-5】不符合有穷性voidtest(){intn=8；while(n%8==0)//死循环n+=8；printf(“%d\n”,n)；}1）正确性(能实现预先规定的功能和性能)2）可读性（易读、易理解）3）健壮性（当输入非法数据时，能检测出错误，并进行适当的处理）如:输入3条边,计算三角形面积4）高效性（运行的时间和空间需求）算法的优劣从以下来评价：P151.3.2算法描述•自然语言•程序流程图、N-S图等算法描述工具•程序设计语言(定义函数)•伪码语言1.3.3算法性能分析算法在计算机上执行时，其运行所需要的时间取决于下列因素：1）硬件的速度2）书写程序的语言3）编译程序所生成目标代码的质量4）问题的规模前3者都与具体机器相关,而数据结构只讨论算法本身的效率高低,所以只与程序执行的数据量相关,也就是考虑最后1条,抽象为问题规模1.算法耗费的时间和语句频度语句频度指的是语句的重复执行的次数【例1-6】for(i=1;i=n;i++)//频度为n+1for(j=1;j=n;j++)//频度为n*(n+1)c[i][j]=a[i][j]+b[i][j];//频度为n2该算法的执行时间，用T（n）表示。T(n)=2n2+2n+1算法的时间复杂度T(n)是该算法的时间度量记作T(n)=O(f(n))2.问题规模和算法的时间复杂度一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n),使得当n趋近于无穷大时，T（n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数（记作T(n)=Ｏ(f(n)),称Ｏ(f(n))为算法的渐近时间复杂度，简称时间复杂度。例如，若T(n)=n(n+1)/2,则有T(n)/n2=1/2+1/n，当n∞时，T(n)/n2=1/2故它的时间复杂度为Ｏ(n2),即Ｔ(n)与n2数量级相同。显然,被称做问题的基本操作的原操作应是其重复执行次数与算法的执行时间成正比的原操作;多数情况下，它就是最深层循环内的语句中的原操作，它的执行次数和包含它的语句频度相同。语句的频度指的是该语句的重复执行的次数一般情况下,对一个问题(或一类算法)只需选择一种基本操作来讨论算法的时间复杂度即可++x;s=0;时间复杂度为O(1)。没有循环语句，其基本运算次数与问题规模无关，称为常数阶，记作O(1)。【例1-7】for(i=1;i=n;++i){++x;s+=x;}时间复杂度为O(n)。一重循环，其基本运算次数与问题规模n成线性增长关系，称为线性阶，记为O(n)【例1-8】for(j=1;j=n;++j)for(k=1;k=n;++k){++x;s+=x;}时间复杂度为O(n2)。二重循环，其基本运算次数于问题规模n成平方级增长关系，称为平方阶，记为O(n2)。【例1-9】for(j=1;j=n;++j)for(k=1;k=j;++k){++x;s+=x;}时间复杂度为?课堂讨论【例1-10】•课后思考题：例1-11x=1;for(i=1;i=n;i++)for(j=1;j=i;j++)for(k=1;k=j;k++)x++;•由于内循环的执行次数虽与规模n无直接关系，但与外循环的变量取值有关。分析过程：分析算法规律可知时间频度T(n)=1+(1+2)+(1+2+3)+...+(1+2+3+…+n)===+=[+]由于有1/6≤T（n)/n3≤1，故时间复杂度为Ｏ(n3)。nkk1)...321(nkkk12)1(nkk122nkk12216)12)(1(nnn2)1(nn各种不同数量级对应的值存在着如下关系：O(1)O(log2n)O(n)O(n*log2n)O(n2)O(n3)O(2n)O(n!)3.常用算法时间复杂度指的是该算法在运行过程中所耗费的辅助存储空间，如果一个算法所耗费的存储空间与问题规模n无关，记作S(n)=O(1)。有关:S(n)=O(f(n))201510520001000300002nn3/25n2100n200log2nnT(n)4.算法的空间复杂度1.4本章小结1.掌握数据结构的基本概念数据的逻辑结构数据的运算集合顺序结构链式结构线性结构（线性表、栈、队列、字符串、数组、广义表）非线性结构（树、图）数据的存储结构2.逻辑结构与存储结构的区别3.抽象数据类型4