数据结构1章线性表.ppt
《数据结构1章线性表.ppt》由会员分享,可在线阅读,更多相关《数据结构1章线性表.ppt(39页珍藏版)》请在三一办公上搜索。
1、数据结构(Java版),数据结构(Java版),第1章 绪论第2章 线性表第3章 排序第4章 栈与队列第5章 数组和广义表第6章 树和二叉树第7章 查找第8章 图第9章 综合应用设计,第1章 绪论,软件设计是计算机学科各个领域的核心。软件设计时要考虑的首要问题是数据的表示、组织和处理方法。数据结构设计和算法设计是软件系统设计的核心。“数据结构十算法=程序”。1.1 数据结构的基本概念1.2 算法与算法分析1.3 Java语言简介,数据结构(Java版)叶核亚,1.1 数据结构的基本概念,1.1.1 抽象数据类型与数据结构1.1.2 数据的逻辑结构1.1.3 数据的存储结构1.1.4 数据的操作
2、,数据结构(Java版)叶核亚,1.1.1 抽象数据类型与数据结构,数据、数据元素、数据项描述客观事物的数字、字符以及所有能输入到计算机中并能为计算机接受的各种符号集合统称为数据(data)。数据是计算机程序的处理对象。表示一个事物的一组数据称作一个数据元素(data element),数据元素是数据的基本单位;构成数据元素的数据称作该数据元素的数据项(data item),数据项是数据元素的不可分割的最小单位。数据类型类型是一组值的集合。数据类型(data type)是指一个类型和定义在这个类型上的操作集合。数据类型定义了数据元素的性质、取值范围以及对数据元素所能进行的各种操作。,数据结构(
3、Java版)叶核亚,表1.1 学生信息表,class StudentString number;String name;String sex;int age;,数据结构(Java版)叶核亚,抽象数据类型抽象数据类型(Abstract Data Type,缩写为ADT)是指一个逻辑概念上的类型和这个类型上的操作集合。没有定义具体数据类型的数据元素称作抽象数据元素。数据结构对一个数据元素集合来说,如果在数据元素之间存在一种或多种特定的关系,则称为数据结构(data structure)。因此,“结构”就是指数据元素之间存在的关系。,数据结构(Java版)叶核亚,1.1.2 数据的逻辑结构,线性结构
4、:数据元素只有一个前驱数据元素和一个后继数据元素。树结构:每个数据元素只有一个前驱数据元素,可有零个或若干个后继数据元素。图结构:每个数据元素可有零个或若干个前驱数据元素,零个或若干个后继数据元素。,图1.1 三种基本的数据结构,数据结构(Java版)叶核亚,1.1.3 数据的存储结构,数据元素在计算机中的存储表示方式称为数据的存储结构,也称为物理结构。顺序存储结构顺序存储结构是把数据元素存储在一块连续地址空间的内存中,其特点是逻辑上相邻的数据元素在物理上也相邻,数据间的逻辑关系表现在数据元素的存储位置关系上。链式存储结构指针是指向物理存储单元地址的变量。由数据元素域和指针域组成的一个整体称为
5、一个结点(node)。链式存储结构是使用指针把相互直接关联的结点(即直接前驱结点或直接后继结点)链接起来,其特点是逻辑上相邻的数据元素在物理上(即内存存储位置上)不一定相邻,数据间的逻辑关系表现在结点的链接关系上。,数据结构(Java版)叶核亚,图1.2 两种存储结构,数据结构(Java版)叶核亚,1.1.4 数据的操作,对一种数据类型的数据元素进行的某种处理称作数据的操作。访问数据元素。统计数据元素个数。更新数据元素值。插入数据元素,在数据结构中增加新的结点。删除数据元素,将指定数据元素从数据结构中删除。查找在数据结构中查找满足一定条件的数据元素。插入、删除、更新操作都包括一个查找操作,以确
6、定需要插入、删除、更新数据元素的确切位置。排序在线性结构中数据元素数目不变的情况下,将数据元素按某种指定的顺序重新排列。,数据结构(Java版)叶核亚,1.2 算法与算法分析,1.2.1 算法1.2.2 算法设计1.2.3 算法分析,数据结构(Java版)叶核亚,1.2.1 算法,算法定义有穷性算法必须在执行有穷步之后结束。确定性算法的每一个步骤必须是确切地定义的。输入算法有零个或多个输入。输出算法有一个或多个输出,即与输入有某种特定关系的量。可行性算法中有待执行的操作和操作必须是相当基本的,即是说,它们原则上都是能够精确地进行的,而且用笔和纸做有穷次就可以完成。算法的描述算法可用文字、高级程
7、序设计语言或类同于高级程序设计语言的伪码描述。此时算法是由语义明确的操作步骤组成的有限序列,它精确地指出怎样从给定的输入信息得到要求的输出信息。,数据结构(Java版)叶核亚,【例1.3】学生信息表的顺序查找算法。,图1.5 学生信息表的顺序查找过程,数据结构(Java版)叶核亚,算法与数据结构 算法是建立在数据的逻辑结构与存储结构上的。对于同样的逻辑结构和存储结构,根据问题的不同要求,采用不同的算法。同样的数据结构,不同的存储结构,则采用的算法必然不同。例如,存储结构不同的线性表其排序算法必然不同。,数据结构(Java版)叶核亚,算法与程序算法用抽象的语言描述解决特定问题的每一步的操作。程序
8、是计算机能理解和执行的指令序列。一个程序实现一个算法。算法和程序的区别是算法的执行是有穷的,而程序的执行可以是无限的。例如操作系统程序,只要系统不受破坏,操作系统的运行将不会停止。,数据结构(Java版)叶核亚,1.2.2 算法设计,算法设计目标正确性可读性健壮性高时间效率高空间效率算法设计实现,数据结构(Java版)叶核亚,【例1.4】求最大值算法的设计与调用。,从两个整数类型数据中得到较大数值的算法设计如下:int Max(int a,int b)return(a=b)?a:b;主函数中,调用Max(Max(a,b),c)将从三个整数中返回最大值,例如,System.out.println
9、(max=+Max(Max(a,b),c);,数据结构(Java版)叶核亚,1.2.3 算法分析,算法的时间复杂度算法的执行时间等于所有语句执行时间的总和,是算法所处理的数据个数n的函数,表示为O(f(n),O(f(n)称为该算法的时间复杂度。O(1)表示时间是一个常数,不依赖于n;O(n)表示时间与n成正比,是线性关系,O(n2)、O(n3)、O(2n)分别称为平方阶、立方阶和指数阶;O(log2n)为对数阶。算法的空间复杂度,数据结构(Java版)叶核亚,【例1.5】分析算法的时间复杂度。,一个简单语句的时间复杂度为O(1)。sum=0;一个循环的时间复杂度为O(n)。int n=10,s
10、um=0;for(int i=0;in;i+)sum+=n;时间复杂度为O(n2)的二重循环。int n=9;for(int i=0;in;i+)for(int j=0;jn;j+)System.out.print(i*j);如果int n=9;for(int i=0;in;i+)for(int j=0;ji;j+)System.out.print(i*j);二重循环的执行次数为,时间复杂度仍为O(n2)。,数据结构(Java版)叶核亚,时间复杂度为O(nlog2n)的二重循环。int n=8;for(int i=1;i=n;i*=2)for(int j=1;j=n;j+)System.out
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 线性
链接地址:https://www.31ppt.com/p-6578857.html