数据结构课件第一章节.pptVIP

数据结构;课时安排;成绩计算;教材与参考书;课程重要性简介; 数据结构在学科中的地位;课程主要内容简介;本课程章节主要内容 第一章：绪论 第二章：线性表和数组 第三章：栈和队列 第四章：串 第五章：树和二叉树 第六章：图 第七章：排序 第八章：查找 第九章：文件;第一章 绪 论;高等数学;例2 计算机和人的对弈问题－－“树”形数据结构，1：N的关系;例3 多叉路口交通灯的管理问题－－“图”形数据结构，M：N的关系; 数据（Data) 客观事物的符号表示，能输入到计算机中并被计算机中程序处理的符号的总称。 数据元素 (Data element) 数据的基本单位，可由数据项组成。 数据类型 (Data Type) 是一个值的集合和定义在这个值集上的一组操作的总称。 如：int数据类型，取值范围为－32768～32767，操作运算有加、减、乘、除、取模、乘方等。;数据对象 (Data Object) 性质相同的数据元素的集合，是数据的子集。 数据结构 (Data Structure) 相互之间存在一种或多种特定关系的数据元素的集合。数据元素之间的相互关系称为结构。有下列四种基本结构： （1）集合（2）线形结构（3）树形结构（4）图状结构(网状结构）。 ;数据结构DS的形式定义：数据结构是一个二元组。 DS＝（K，R） 其中： K是数据元素的有限集 R是数据元素之间关系的有限集 对于R中任意二元关系x，y（x，y∈K），称x为第一元素（或y的前驱），y为第二元素（或x的后继）。; 数据元素之间的关系在计算机中的表示：有顺序映象和非顺序映象两种方法，由此得到两种存储结构：; 数据操作描述; ; ; ;空间复杂度： 一个上机执行的程序除了需要存储空间来积存本身所用指令，常数，变量和输入数据外，也需要一些对数据进行操作的工作单元和存储一些实现计算所需信息的辅助空间。该辅助空间的大小及反映了该算法的空间复杂性。计作：S（n）= O（f（n））。 频度：某语句重复执行的次数。;程序段一： { ++x; s=0； };程序段二： for(i=1;i=n;++i) { ++x; s+=x; };程序段三： for(j=1;j=n;++j) for(k=1;k=n;++k) { ++x; s+=x; };程序段四： for(i=2;i=n;++i) for(j=2;j=i-1;++j) { ++x; a[i][j]=x; };常见的几种时间复杂度数量级;衡量两个算法的好坏，应当是在n足够大的情形下，对算法的工作量进行比较，即对算法进行渐近性态分析。;算法的阶;算法的阶;算法的阶;本章重点;作业1