搜索
2020/9/41《数据结构》《数据结构教程（第4版）》——李春葆主编清华大学出版社2课程性质：必修、考试课，3学分授课学时：56学时=42（理论）+14（实验）考核方式：成绩=期末闭卷（60％）+平时成绩（40％）平时成绩包括作业、考勤、测验、实验等授课班级：计算机15-1、2、3、4授课时间：星期三1-2节（1-14周）[1-103]星期五3-4节（1-14周）[1-103]、机房课程设计：1周（17周）、1学分辅导答疑：西办公楼111课程介绍3数据结构教程（第4版）第1章绪论第2章线性表第3章栈和队列第4章串第5章递归第6章数组和广义表第7章树和二叉树第8章图第9章查找第10章内排序4学习背景数据结构是计算机等相关专业的一门非常重要的专业基础课。为了编写出一个“好”的程序，必须分析待处理对象的特征及各对象间存在的关系，这就是数据结构这门课所要研究的问题。形成阶段：1968年，“数据结构”被列入美国一些大学计算机科学系的教学计划。开始在国外作为一门独立课程设立。70年代后期，我国高校陆续开设该课程。由美国唐纳德·克努特教授开创其最初体系。51938年出生，25岁毕业于加州理工学院数学系，博士毕业后留校任教，28岁任副教授。30岁时，加盟斯坦福大学计算机系，任教授。从31岁起，开始出版他的历史性经典巨著：TheArtofComputerProgramming他计划共写7卷，然而出版三卷之后，已震惊世界，使他获得计算机科学界的最高荣誉图灵奖，此时，他年仅36岁。数据结构的创始人——克努特6前期课程数据结构计算机基础C/C++、Java等离散数学后期课程操作系统数据库原理编译原理软件工程承上启下计算机科学课程体系（偏软）7学习目标熟悉基本的数据结构掌握数据结构的实现方法以及经典算法（模仿）掌握初步的算法分析技术（评价算法、改进算法）培养算法设计能力、程序设计能力算法——程序的灵魂问题求解过程：问题→想法→算法→程序培养计算机思维能力逻辑思维和抽象思维数据结构+算法=程序8课程学习要求课堂认真听讲，注意讲课思路。课前预习，课后及时复习，按时独立完成作业。重视实验课，准备充分，讲求效率。不断总结摸索学习方法。教学互动。91.《数据结构教程（第4版）学习指导》李春葆主编清华大学出版社2.《数据结构》严蔚敏等清华大学出版社3.《数据结构（用面向对象方法与C++语言描述）》殷人昆等清华大学出版社4.《数据结构（Java版）》叶核亚等电子工业出版社5.其它参考资料10第1章绪论1.2算法及其描述1.1什么是数据结构1.3算法分析本章小结1.4数据结构＋算法＝程序111.1.1数据结构的定义1.1.2逻辑结构类型1.1.3存储结构类型1.1.4数据类型和数据结构1.1什么是数据结构12数据：是所有能被输入到计算机中，且能被计算机处理的符号的集合。它是计算机操作的对象的总称，也是计算机处理的信息的某种特定的符号表示形式。数据元素：是数据（集合）中的一个“个体”，是数据的基本单位。1.1.1数据结构的定义数据对象：具有相同性质的数据元素的集合。数据项：具有独立含义的最小数据单位。13•数据结构：是指所有数据元素以及数据元素之间的关系。可以把数据结构看成是带结构的数据元素的集合。•数据结构包括如下几个方面：（1）数据元素之间的逻辑关系，即数据的逻辑结构。（2）数据元素及其关系在计算机存储器中的存储方式，即数据的存储结构，也称为数据的物理结构。（3）施加在数据上的操作，即数据的运算。1.1.1数据结构的定义14【例1.1】学生表学号姓名性别班号1张斌男99018刘丽女990234李英女990120陈华男990212王奇男990126董强男99025王萍女99011,8,8,34,34,20,20,12,12,26,26,5——C/C++语言中，通常采用结构体数组和链表两种方式实现其存储结构。15存放学生表的结构体数组Stud定义为：struct{intno;/*存储学号*/charname[8];/*存储姓名*/charsex[2];/*存储性别*/charclass[4];/*存储班号*/}Stud[7]={{1,“张斌”,“男”,“9901”},…,{5,王萍,女,9901}};9901女王萍5…9901男张斌1Stud[0]Stud[6]Stud数组起始地址16存放学生表的链表的结点类型StudType定义为：typedefstructstudnode{intno;/*存储学号*/charname[8];/*存储姓名*/charsex[2];/*存储性别*/charclass[4];/*存储班号*/structstudnode*next;/*存储指向下一个学生的指针*/}StudType；1张斌男99018刘丽女99025王萍女9901∧为了确切地描述一种数据结构，通常采用二元组表示：B=(D,R)17（a）线性结构ABDEGHABCABCDEF（b）树（c）图DC线性结构：数据元素之间具有线性关系，最简单的数据结构。非线性结构：树结构、图结构。1.1.2逻辑结构类型18（1）线性结构：除第一个和最后一个元素外，每个数据元素只有一个前驱元素和一个后继元素。第一个元素没有前驱，最后一个元素没有后继。（2）树结构：层次关系（一对多），根结点没有前驱，除根结点之外的其它结点有且仅有一个前驱结点，所有结点可有零个或若干个后继结点。（3）图结构：网状关系（多对多），每个结点可有零个或若干个前驱结点，也可以有零个或若干个后继结点。（4）集合19（2）链式存储结构（3）索引存储结构（4）散列存储结构1.1.3存储结构类型（1）顺序存储结构20（1）数据类型数据类型是一组性质相同的值的集合和定义在此集合上的一组操作的总称。1.1.4数据类型和数据结构（2）抽象数据类型抽象数据类型（AbstractDataType，简写为ADT）指的是用户进行软件系统设计时从问题的数学模型中抽象出来的逻辑数据结构和逻辑数据结构上的运算，不考虑计算机的具体存储结构和运算的具体实现算法。ADT抽象数据类型名{数据对象：〈数据对象的定义〉数据关系：〈数据关系的定义〉基本运算：〈基本运算的定义〉}ADT抽象数据类型名21例如，抽象数据类型复数的定义：ADTComplex{数据对象：D={e1,e2|e1,e2均为实数}数据关系：R1={e1,e2|e1是复数的实数部分，e2是复数的虚数部分}基本运算：AssignComplex(&Z,v1,v2)：构造复数ZDestroyComplex(&Z)：销毁复数ZGetReal(Z,&real)：返回复数Z的实部值GetImag(Z,&Imag)：返回复数Z的虚部值Add(z1,z2,&sum)：返回两个复数z1,z2的和}ADTComplexe1＋e2i221.2算法及其描述1.2.1什么是算法1.2.2算法描述23•算法——是对特定问题的求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示计算机的一个或多个操作。1.2.1什么是算法算法的主要特性：•有穷性：在有穷步之后结束•确定性：无二义性•可行性：可通过执行有限次基本运算来实现•有输入：零个或多个输入•有输出：一个或多个输出24【例】考虑下列描述：（1）描述一voidexam1(){n＝2;while(n%2＝＝0)n＝n+2;printf(%d\n,n);}这两段描述均不能满足算法的特征，试问违反了？（2）描述二voidexam2(){y=0;x=5/y;printf(“%d,%d\n”,x,y);}（1）算法是一个死循环，违反算法的有穷性特征。（2）算法包含除零错误，违反算法的可行性特征。251.2.2算法描述——本书中采用C/C++语言描述算法。描述算法的工具自然语言、流程图、N-S图、伪代码、计算机语言等。261.3算法分析1.3.2算法效率分析1.3.3算法存储空间分析1.3.1算法设计的目标271.3.1算法设计的目标正确性：算法应满足具体问题的需求。（最基本）可读性：算法应该容易阅读。以有利于读者对程序的理解。可使用性：算法应该方便使用。（用户友好性）健壮性：算法应具有容错处理的功能。当输入非法数据时，算法应对其作出反应，而不应产生莫名其妙的输出结果。（异常处理）高效率与低存储量需求：算法执行的时间和空间利用率。通常这两者与问题的规模有关。（比较权衡）28intt=a;a=b;b=t;a=a+b;b=a-b;a=a-b;a=b-a;b=b-a;a=a+b;（1）（2）（3）【例】比较分析下面的程序段：已知inta=8,b=6;291.3.2算法效率分析【例】for(i=1;i=n;i++)for(j=1;j=n;j++)s++;•算法执行时间=∑每条语句执行时间•每条语句执行时间=执行次数×执行一次的时间基本语句（运算）——最深层循环内的语句•算法执行时间大致为基本运算所需的时间与其运算次数（也称为频度）的乘积。30•通常把算法中基本运算的执行次数称为算法的时间复杂度。•算法中基本运算次数T(n)是问题规模n的某个函数f(n)，记作：T(n)=O(f(n))记号“O”读作“大O”。它表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同。【例】T(n)=3n2-5n+10000=O(n2)31•一个没有循环的算法中基本运算次数与问题规模n无关，记作O(1)，也称作常数阶。•一个只有一重循环的算法中基本运算次数与问题规模n呈线性关系，记作O(n)，也称线性阶。•其余常用的还有平方阶O(n2)、立方阶O(n3)、对数阶O(log2n)、指数阶O(2n)等。•各种不同数量级对应的值存在着如下关系：O(1)O(log2n)O(n)O(nlog2n)O(n2)O(n3)O(2n)O(n!)32时间复杂度随问题规模n变化情况的比较时间复杂度n=8n=10n=100n=1000O(1)1111O(log2n)33.3226.6449.966O(n)8101001000O(nlog2n)2433.22664.49966O(n2)641001000010633【例1.8】求两个n阶方阵的和C=A+B的算法如下，分析其时间复杂度。#defineM20//定义最大的方阶voidmatrixadd(intn,intA[M][M],intB[M][M],intC[M][M]){inti,j;for(i=0;in;i++)for(j=0;jn;j++)C[i][j]=A[i][j]+B[i][j];}T(n)=n*n=n2=O(n2)34【例1.9】分析以下算法的时间复杂度。intfun(inta[],intn,intk){inti=0;while(in&&a[i]!=k)i++;return(i);}•最坏情况下的时间复杂度•算法的平均时间复杂度•算法的平均运算次数35【例1.10】有如下算法：voidfun(inta[],intn,intk)//数组a共有n个元素{inti;if(k==n-1)for(i=0;in;i++)//n次printf(%d\n,a[i]);else{for(i=k;in;i++)//n-k次a[i]=a[i]+i*i;fun(a,n,k+1);}}调用上述算法的语句为fun(a,n,0)，求其时间复杂度。36【例】分析以下算法的时间复杂度。voidfunc(intn){inti=0,s=0;while(sn){i++;s=s+i;}}【解】对于while循环语句，设执行的次数为m，i从0开始递增1，直到m为止，有：s=1+2+…+m=m(m+1)/2，并满足s=m(m+1)/2≤n-1，则有m=O()所以，该算法的时间复杂度为O()。37•空间复杂度是对一个算法在运行过程中临时占用的存储空间大小的量度，一般也作为问题规模n的函数，以数量级形式给出，记作：S(n)=O(g(n))•若所需额外空间相对于输入数据量来说