第1章--数据结构-绪论资料ppt课件.ppt

《第1章--数据结构-绪论资料ppt课件.ppt》由会员分享，可在线阅读，更多相关《第1章--数据结构-绪论资料ppt课件.ppt（41页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构数据结构数据结构教程（第4版）李春葆 主编 清华大学出版社5/7/20231篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统课程性质：必修、考试课，课程性质：必修、考试课，课程性质：必修、考试课，课程性质：必修、考试课，3 3 3 3学分学分学分学分授课学时：授课学时：授课学时：授课学时：56565656学时学时学时学时=42=42=42=42（理论）（理论）（理论）（理论）+14+14+14+14（实验）（实验）（实验）（实验）考核方式：考核方式：考核方式：考核方式：成绩成绩成绩成绩=期末闭卷（期末闭卷（期末闭卷（期末闭卷（

2、60606060）+平时成绩（平时成绩（平时成绩（平时成绩（40404040）平时成绩包括作业、考勤、测验、实验等平时成绩包括作业、考勤、测验、实验等平时成绩包括作业、考勤、测验、实验等平时成绩包括作业、考勤、测验、实验等授课班级：计算机授课班级：计算机授课班级：计算机授课班级：计算机15-115-115-115-1、2 2 2 2、3 3 3 3、4 4 4 4授课时间：星期三授课时间：星期三授课时间：星期三授课时间：星期三1-21-21-21-2节（节（节（节（1-141-141-141-14周）周）周）周）1-1031-1031-1031-103 星期五星期五星期五星期五3-43-43-

3、43-4节（节（节（节（1-141-141-141-14周）周）周）周）1-1031-1031-1031-103、机房、机房、机房、机房课程设计：课程设计：课程设计：课程设计：1 1 1 1周（周（周（周（17171717周）、周）、周）、周）、1 1 1 1学分学分学分学分辅导答疑：西办公楼辅导答疑：西办公楼辅导答疑：西办公楼辅导答疑：西办公楼111 111 111 111 课程介绍课程介绍2篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统数据结构教程数据结构教程（第（第4版）版）第第1章章 绪论绪论第第2章章 线性表线性表第第3章

4、章 栈和队列栈和队列第第4章章 串串第第5章章 递归递归第第6章章 数组和广义表数组和广义表第第7章章 树和二叉树树和二叉树第第8章章 图图第第9章章 查找查找第第10章章 内排序内排序3篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统学习背景学习背景n数据结构是计算机等相关专业的一门非常重要的数据结构是计算机等相关专业的一门非常重要的专业基础课。专业基础课。n为了编写出一个为了编写出一个“好好”的程序，必须分析待处理的程序，必须分析待处理对象的特征及各对象间存在的关系，这就是数据对象的特征及各对象间存在的关系，这就是数据结构这门课所

5、要研究的问题。结构这门课所要研究的问题。n形成阶段：形成阶段：19681968年，年，“数据结构数据结构”被列入美国一被列入美国一些大学计算机科学系的教学计划。些大学计算机科学系的教学计划。开始在国外作开始在国外作为一门独立课程设立。为一门独立课程设立。7070年代后期，我国高校陆年代后期，我国高校陆续开设该课程。续开设该课程。n由美国唐纳德由美国唐纳德克努特教授开创其最初体系。克努特教授开创其最初体系。4篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统1938年出生，年出生，25岁毕业于加州理工岁毕业于加州理工学院数学系，博士毕业后

6、留校任教，学院数学系，博士毕业后留校任教，28岁任副教授。岁任副教授。30岁时，加盟斯坦岁时，加盟斯坦福大学计算机系，任教授。从福大学计算机系，任教授。从31岁岁起，开始出版他的历史性经典巨著：起，开始出版他的历史性经典巨著：The Art of Computer Programming他计划共写他计划共写7卷，然而出版三卷之后，卷，然而出版三卷之后，已震惊世界，使他获得计算机科学已震惊世界，使他获得计算机科学界的最高荣誉图灵奖，此时，他年界的最高荣誉图灵奖，此时，他年仅仅36岁。岁。数据结构的创始人数据结构的创始人数据结构的创始人数据结构的创始人克努特克努特克努特克努特5篮球比赛是根据运动队

7、在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统前期课程前期课程数据结构数据结构计算机基础计算机基础C/C+、Java等等离散数学离散数学后期课程后期课程操作系统操作系统数据库原理数据库原理编译原理编译原理软件工程软件工程承上承上启下启下计算机科学课程体系（偏软）计算机科学课程体系（偏软）6篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统学习目标学习目标熟悉基本的数据结构熟悉基本的数据结构掌握数据结构的实现方法以及经典算法掌握数据结构的实现方法以及经典算法（模仿）（模仿）掌握初步的算法分析技术掌

8、握初步的算法分析技术（评价算法、改进算法）（评价算法、改进算法）培养算法设计能力、程序设计能力培养算法设计能力、程序设计能力 算法算法程序的灵魂程序的灵魂 问题求解过程：问题问题求解过程：问题想法想法算法算法程序程序培养计算机思维能力培养计算机思维能力 逻辑思维和抽象思维逻辑思维和抽象思维数据结构数据结构+算法算法=程序程序7篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统课程学习要求n课堂认真听讲，注意课堂认真听讲，注意讲课思路讲课思路。n课课前前预预习习，课课后后及及时时复复习习，按按时时独独立立完完成成作业作业。n重视重视实验实

9、验课，准备充分，讲求效率。课，准备充分，讲求效率。n不断总结摸索不断总结摸索学习方法学习方法。n教学互动。教学互动。8篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统1.1.数数据据结结构构教教程程（第第4 4版版）学学习习指指导导李李春春葆葆主主编编 清华大学出版社清华大学出版社 2 2.数据结构数据结构 严蔚敏严蔚敏等等 清华大学出版社清华大学出版社3.3.数据结构（用面向对象方法与数据结构（用面向对象方法与C+语言描述）语言描述）殷人昆等殷人昆等 清华大学出版社清华大学出版社4.4.数据结构（数据结构（Java版）叶核亚等版）叶

10、核亚等 电子工业出版社电子工业出版社 5.5.其它其它参考资料9篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统第第1章章 绪论绪论 1.2 算法及其描述算法及其描述 1.1 什么是数据结构什么是数据结构1.3 算法分析算法分析 本章小结本章小结1.4 数据结构算法程序数据结构算法程序 10篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统1.1.1 数据结构的定义1.1.2 逻辑结构类型 1.1.3 存储结构类型1.1.4 数据类型和数据结构1.1 1.1 什么是数据结构什么

11、是数据结构11篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统 数据数据：是所有能被输入到计算机中，且能被计算机是所有能被输入到计算机中，且能被计算机处理的符号的集合。它是计算机操作的对象的总称，处理的符号的集合。它是计算机操作的对象的总称，也是计算机处理的信息的某种特定的符号表示形式。也是计算机处理的信息的某种特定的符号表示形式。数据元素数据元素：是数据（集合）中的一个：是数据（集合）中的一个“个体个体”，是，是数据的基本单位。数据的基本单位。1.1.1 1.1.1 数据结构的定义数据结构的定义 数据对象数据对象：具有相同性质的数据

12、元素的集合。：具有相同性质的数据元素的集合。数据项数据项：具有独立含义的最小数据单位。：具有独立含义的最小数据单位。12篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统 数据结构数据结构：是指：是指所有数据元素所有数据元素以及数据元素之间的以及数据元素之间的关系关系。可以把数据结构看成是可以把数据结构看成是带结构的数据元素的集带结构的数据元素的集合合。数据结构包括如下几个方面：数据结构包括如下几个方面：（1）数据元素之间的逻辑关系，即）数据元素之间的逻辑关系，即数据的逻辑结构数据的逻辑结构。（2）数数据据元元素素及及其其关关系系在在计

13、计算算机机存存储储器器中中的的存存储储方方式式，即即数据的存储结构数据的存储结构，也称为数据的物理结构。，也称为数据的物理结构。（3）施加在数据上的操作，即施加在数据上的操作，即数据的运算数据的运算。1.1.1 1.1.1 数据结构的定义数据结构的定义13篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统【例【例1.1】学生表学生表学号学号姓名姓名性别性别班号班号1张斌张斌男男99018刘丽刘丽女女990234李英李英女女990120陈华陈华男男990212王奇王奇男男990126董强董强男男99025王萍王萍女女9901,C/C+语语

14、言言中中，通通常常采采用用结结构构体体数数组组和和链链表表两两种方式实现其存储结构。种方式实现其存储结构。14篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统存放学生表的结构体数组存放学生表的结构体数组Stud定义为：定义为：struct int no;/*存储学号存储学号*/char name8;/*存储姓名存储姓名*/char sex2;/*存储性别存储性别*/char class4;/*存储班号存储班号*/Stud7=1,“张张斌斌”,“男男”,“9901”,5,王王萍萍,女女,9901;99019901女女王萍王萍5 5990

15、19901男男张斌张斌1 1Stud0Stud6Stud数组起始地址数组起始地址15篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统存放学生表的链表的结点类型存放学生表的链表的结点类型StudType定义为：定义为：typedef struct studnode int no;/*存储学号存储学号*/char name8;/*存储姓名存储姓名*/char sex2;/*存储性别存储性别*/char class4;/*存储班号存储班号*/struct studnode*next;/*存储指向下一个学生的指针存储指向下一个学生的指针*/S

16、tudType；1 张斌张斌 男男 99018刘丽刘丽 女女 99025王萍王萍 女女 9901n 为为了了确确切切地地描描述述一一种种数数据据结结构构，通通常常采采用用二二元元组组表表示：示：B=(D,R)16篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统n线性结构线性结构：数据元素之间具有线性关系，最简单：数据元素之间具有线性关系，最简单 的数据结构。的数据结构。n非线性结构非线性结构：树结构、图结构。：树结构、图结构。1.1.2 1.1.2 逻辑结构类型逻辑结构类型 17篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负

17、的，因此，篮球比赛的计时计分系统是一种得分类型的系统（1）线性结构）线性结构：除第一个和最后一个元素外，每个：除第一个和最后一个元素外，每个数据元素只有一个前驱元素和一个后继元素。第数据元素只有一个前驱元素和一个后继元素。第一个元素没有前驱，最后一个元素没有后继。一个元素没有前驱，最后一个元素没有后继。（2）树结构）树结构：层次关系（一对多），根结点没有前：层次关系（一对多），根结点没有前驱，除根结点之外的其它结点有且仅有一个前驱驱，除根结点之外的其它结点有且仅有一个前驱结点，所有结点可有零个或若干个后继结点。结点，所有结点可有零个或若干个后继结点。（3）图结构）图结构：网状关系（多对多），每

18、个结点可有：网状关系（多对多），每个结点可有零个或若干个前驱结点，也可以有零个或若干个零个或若干个前驱结点，也可以有零个或若干个后继结点。后继结点。（4）集合）集合18篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统（2）链式存储结构）链式存储结构（3）索引存储结构）索引存储结构（4）散列存储结构）散列存储结构 1.1.3 1.1.3 存储结构类型存储结构类型（1）顺序存储结构）顺序存储结构 19篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统（1）数据类型）数据类型 数据类

19、型是一组性质相同的值的集合和定义在数据类型是一组性质相同的值的集合和定义在此集合上的一组操作的总称。此集合上的一组操作的总称。1.1.4 1.1.4 数据类型和数据结构数据类型和数据结构（2）抽象数据类型）抽象数据类型 抽象数据类型（抽象数据类型（Abstract Data Type，简写为，简写为ADT）指的是用户进行软件系统设计时从问题的数）指的是用户进行软件系统设计时从问题的数学模型中抽象出来的逻辑数据结构和逻辑数据结构学模型中抽象出来的逻辑数据结构和逻辑数据结构上的运算，不考虑计算机的具体存储结构和运算的上的运算，不考虑计算机的具体存储结构和运算的具体实现算法。具体实现算法。ADT A

20、DT 抽象数据类型名抽象数据类型名 数据对象：数据对象的定义数据对象：数据对象的定义 数据关系：数据关系的定义数据关系：数据关系的定义 基本运算：基本运算的定义基本运算：基本运算的定义 ADT ADT 抽象数据类型名抽象数据类型名20篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统例如，抽象数据类型例如，抽象数据类型复数复数的定义：的定义：ADT Complex 数据对象：数据对象：D=e1,e2|e1,e2均为实数均为实数 数据关系：数据关系：R1=|e1是复数的实数部分，是复数的实数部分，e2 是复数的虚数部分是复数的虚数部分 基

21、本运算：基本运算：AssignComplex(&Z,v1,v2)：构造复数：构造复数Z DestroyComplex(&Z)：销毁复数：销毁复数Z GetReal(Z,&real)：返回复数：返回复数Z的实部值的实部值 GetImag(Z,&Imag)：返回复数：返回复数Z的虚部值的虚部值 Add(z1,z2,&sum)：返回两个复数：返回两个复数z1,z2的和的和 ADT Complexe1e2i21篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统1.2 1.2 算法及其描述算法及其描述 1.2.1 1.2.1 什么是算法什么是算法

22、 1.2.2 1.2.2 算法描述算法描述22篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统 算法算法是对特定问题的求解步骤的一种描述，是对特定问题的求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示计算机它是指令的有限序列，其中每一条指令表示计算机的一个或多个操作。的一个或多个操作。1.2.1 1.2.1 什么是算法什么是算法算法的主要特性：算法的主要特性：有穷性有穷性：在有穷步之后结束：在有穷步之后结束 确定性确定性：无二义性：无二义性 可行性可行性：可通过执行有限次基本运算来实现：可通过执行有限次基本运算来实现 有输入

23、有输入：零个或多个输入：零个或多个输入 有输出有输出：一个或多个输出：一个或多个输出23篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统【例】【例】考虑下列描述：考虑下列描述：（1）描述一）描述一 void exam1()n2;while(n%20)nn+2;printf(%dn,n);这两段描述均不能满足算法的特征，试问违反了？这两段描述均不能满足算法的特征，试问违反了？（2）描述二）描述二 void exam2()y=0;x=5/y;printf(“%d,%dn”,x,y);（1）算法是一个死循环，违反算法的有穷性特征。）算法是一

24、个死循环，违反算法的有穷性特征。（2）算法包含除零错误，违反算法的可行性特征。）算法包含除零错误，违反算法的可行性特征。24篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统 1.2.2 1.2.2 算法描述算法描述本书中采用本书中采用C/C+C/C+语言描述算法。语言描述算法。n 描述算法的工具描述算法的工具 自然语言、流程图、自然语言、流程图、N-S图、伪代码、计算机图、伪代码、计算机语言等。语言等。25篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统1.3 1.3 算法分

25、析算法分析 1.3.2 算法效率分析 1.3.3 算法存储空间分析 1.3.1 算法设计的目标 26篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统1.3.1 1.3.1 算法设计的目标算法设计的目标 l l正确性正确性正确性正确性：算法应满足具体问题的需求。算法应满足具体问题的需求。（最基本）（最基本）l l可读性可读性可读性可读性：算法应该容易阅读。以有利于读者对程序算法应该容易阅读。以有利于读者对程序的理解。的理解。l l可使用性可使用性可使用性可使用性：算法应该方便使用。：算法应该方便使用。（用户友好性）（用户友好性）l l健

26、壮性健壮性健壮性健壮性 ：算法应具有容错处理的功能。当输入非算法应具有容错处理的功能。当输入非法数据时，算法应对其作出反应，而不应产生莫名法数据时，算法应对其作出反应，而不应产生莫名其妙的输出结果。其妙的输出结果。（异常处理）（异常处理）l l高效率与低存储量需求高效率与低存储量需求高效率与低存储量需求高效率与低存储量需求：算法执行的时间和空间利算法执行的时间和空间利用率。通常这两者与问题的规模有关。用率。通常这两者与问题的规模有关。（比较权衡）（比较权衡）27篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统int t=a;a=b;b

27、=t;a=a+b;b=a-b;a=a-b;a=b-a;b=b-a;a=a+b;（1）（2）（3）【例】比较分析下面的程序段：【例】比较分析下面的程序段：已知已知 int a=8,b=6;28篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统1.3.2 1.3.2 算法效率分析算法效率分析【例】【例】for(i=1;i=n;i+)for(j=1;j=n;j+)s+;算法执行时间算法执行时间=每条语句执行时间每条语句执行时间 每条语句执行时间每条语句执行时间=执行次数执行次数执行一次的时间执行一次的时间基本语句（运算）基本语句（运算）最深层

28、循环内的语句最深层循环内的语句 算算法法执执行行时时间间大大致致为为基基本本运运算算所所需需的的时时间间与与其其运运算算次数（也称为频度）的乘积。次数（也称为频度）的乘积。29篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统 通通常常把把算算法法中中基基本本运运算算的的执执行行次次数数称称为为算算法法的的时时间复杂度间复杂度。算算法法中中基基本本运运算算次次数数T(n)是是问问题题规规模模n的的某某个个函函数数f(n)，记作，记作：T(n)=O(f(n)记记号号“O”读读作作“大大O”。它它表表示示随随问问题题规规模模n的的增大，算法

29、执行时间的增长率和增大，算法执行时间的增长率和f(n)的增长率相同。的增长率相同。【例】【例】T(n)=3n2-5n+10000=O(n2)30篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统 一个没有循环的算法中基本运算次数与问题规模一个没有循环的算法中基本运算次数与问题规模n无关，记作无关，记作O(1)，也称作常数阶。，也称作常数阶。一个只有一重循环的算法中基本运算次数与问题规一个只有一重循环的算法中基本运算次数与问题规模模n呈线性关系，记作呈线性关系，记作O(n)，也称线性阶。，也称线性阶。其余常用的还有平方阶其余常用的还有平方

30、阶O(n2)、立方阶立方阶O(n3)、对数对数阶阶O(log2n)、指数阶指数阶O(2n)等。等。各种不同数量级对应的值存在着如下关系：各种不同数量级对应的值存在着如下关系：O(1)O(log2n)O(n)O(nlog2n)O(n2)O(n3)O(2n)O(n!)31篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统时间复杂度随问题规模时间复杂度随问题规模n变化情况的比较变化情况的比较时间复杂度时间复杂度n=8n=10n=100n=1000O(1)1111O(log2n)33.3226.6449.966O(n)8101001000O(n

31、log2n)2433.22664.49966O(n2)641001000010632篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统【例例1.8】求求两两个个n阶阶方方阵阵的的和和C=A+B的的算算法法如如下下，分分析其时间复杂度。析其时间复杂度。#define M 20 /定义最大的方阶定义最大的方阶 void matrixadd(int n,int AMM,int BMM,int CMM)int i,j;for(i=0;in;i+)for(j=0;jn;j+)Cij=Aij+Bij;T(n)=n*n=n2=O(n2)33篮球比赛是

32、根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统【例【例1.9】分析以下算法的时间复杂度】分析以下算法的时间复杂度。int fun(int a,int n,int k)int i=0;while(in&ai!=k)i+;return(i);最坏情况下的时间复杂度最坏情况下的时间复杂度 算法的平均时间复杂度算法的平均时间复杂度 算法的平均运算次数算法的平均运算次数34篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统【例【例1.10】有如下算法：】有如下算法：void fun(int a,

33、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)，求求其其时时间间复复杂度。杂度。35篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统【例】【例】分析以下算法的时间复杂度。分析以下算法的时间复杂度。void func(int n)int i=0,s=0;while(sn)

34、i+;s=s+i;【解】【解】对于对于while循环语句，设执行的次数为循环语句，设执行的次数为m，i从从0开始递增开始递增1，直到，直到m为止，有：为止，有：s=1+2+m=m(m+1)/2，并满足并满足s=m(m+1)/2n-1，则有，则有 m=O()所以，该算法的时间复杂度为所以，该算法的时间复杂度为O()。36篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统 空间复杂度是对一个算法在运行过程中空间复杂度是对一个算法在运行过程中临时占用的临时占用的存储空间存储空间大小的量度，一般也作为问题规模大小的量度，一般也作为问题规模n的函

35、数，的函数，以数量级形式给出，记作：以数量级形式给出，记作：S(n)=O(g(n)若若所所需需额额外外空空间间相相对对于于输输入入数数据据量量来来说说是是常常数数，则则称称此此算算法法为为原原地地工工作作。若若所所需需存存储储量量依依赖赖于于特特定定的的输输入，则通常按最坏情况考虑。入，则通常按最坏情况考虑。1.3.3 1.3.3 算法存储空间分析算法存储空间分析37篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统1.4 1.4 数据结构算法程序数据结构算法程序n 程序离不开数据结构。程序离不开数据结构。n 算法是程序的核心。算法是程

36、序的核心。n 一种数据的逻辑结构可以映射成多种存储结构，一种数据的逻辑结构可以映射成多种存储结构，数据存储结构会影响算法的好坏。数据存储结构会影响算法的好坏。38篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统【例【例1.13】有若干学生数据（学生数小于有若干学生数据（学生数小于50），每个），每个学生数据包含学号（每个学生学号是惟一的，但学生学生数据包含学号（每个学生学号是惟一的，但学生记录不一定按学号顺序存放）、姓名、班号和若干门记录不一定按学号顺序存放）、姓名、班号和若干门课程成绩（每个学生所选课程数目可能不等，但最多课程成绩（

37、每个学生所选课程数目可能不等，但最多不超过不超过6门）。门）。要求设计一个程序输出每个学生的学号、姓名和要求设计一个程序输出每个学生的学号、姓名和平均分以及每门课程（课程编号从平均分以及每门课程（课程编号从16）的平均分。）的平均分。39篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统【设计方案【设计方案1 1】将学生的全部数据项放在一个表中，一将学生的全部数据项放在一个表中，一个学生的全部数据对应一条记录。由于课程最多可选个学生的全部数据对应一条记录。由于课程最多可选6 6门，对应的成绩项也应有门，对应的成绩项也应有6 6个。个。【

38、设计方案【设计方案2 2】将学生的全部数据项放在一个表中，但将学生的全部数据项放在一个表中，但一个学生的一门课程成绩对应一条记录。这样成绩项一个学生的一门课程成绩对应一条记录。这样成绩项只需要一个，为了区分不同课程成绩，需增加一个课只需要一个，为了区分不同课程成绩，需增加一个课程编号项。程编号项。【设计方案【设计方案3 3】将学生的学号、姓名和班号放在一个表将学生的学号、姓名和班号放在一个表中，将成绩数据放在另一个表中，两者通过学号关联。中，将成绩数据放在另一个表中，两者通过学号关联。前者一个学生对应一个记录，后者一门课程成绩对应前者一个学生对应一个记录，后者一门课程成绩对应一条记录。一条记录

39、。40篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统本章小结本章小结本章主要介绍数据结构的基本概念，要点如下：本章主要介绍数据结构的基本概念，要点如下：(1)(1)数据结构的定义，数据结构包含的逻辑结构、数据结构的定义，数据结构包含的逻辑结构、存储结构和运算三方面的相互关系。存储结构和运算三方面的相互关系。(2)(2)各种逻辑结构即线性结构、树结构和图结构之各种逻辑结构即线性结构、树结构和图结构之间的差别。间的差别。(3)(3)各种存储结构即顺序存储、链式存储、索引存各种存储结构即顺序存储、链式存储、索引存储和散列存储之间的差别。储和散列存储之间的差别。(4)(4)算法的定义及其特性，算法设计的目标。算法的定义及其特性，算法设计的目标。(5)(5)算法时间复杂度分析。算法时间复杂度分析。作业：习题作业：习题1.3、1.4(3)、1.5(1)41