《自考数据结构导论第一章ppt课件.ppt》由会员分享，可在线阅读，更多相关《自考数据结构导论第一章ppt课件.ppt（27页珍藏版）》请在三一办公上搜索。
1、数据结构导论,开篇语,1 课程性质介于数学，计算机硬件和计算机软件三者之间的一门核心课程是计算机相关专业一门专业基础课在计算机软件的各个领域中均会使用到数据结构的有关知识,开篇语,2 学习目标知识学习从数据结构与实现层次，系统学习基本数据结构掌握在各种常用的数据结构上实现的排列和查找运算技能培养掌握不同算法与设计思想提高分析问题以及解决问题的能力编程技能,开篇语,3 课程内容第一部分： 概论第二部分： 各种数据结构及其实现方法（线性表、 栈、队、树、图等）第三部分：数据结构的查找与排序,开篇语,4 学习方法 正确掌握本课程的知识体系纵横比较学习注意复习与重读注意循序渐进注意多练习,第1章 概论
2、,1.1 引 言,1.1 引 言,数据结构计算机组织数据和存储数据的方式,编程,处理要求,算法,数据结构（逻辑结构）,程序语句序列,数据结构（存储结构）,建立模型,原始数据,实际问题,数学模型,计算机程序实现,学生档案信息,表格,程序实现档案管理功能（查找、读取、插入、删除、更新）,计算机解决问题的步骤,1.1 引 言,应用举例1学生档案信息表,1.1 引 言,数据特点：每个学生的信息占据一行，所有学生的信息按学号顺序依次排列构成一张表格；表中每个学生的信息依据学号的大小存在着一种前后关系，这就是我们所说的线性结构； 对它的操作通常是：在学生档案中查找出某人的档案，读取某个学生的信息，插入某个
3、学生的信息，删除某个学生的信息，更新某个学生的信息等等。,1.1 引 言,应用举例2制定教学计划在制定教学计划时，需要考虑： 各门课程的开设顺序，即有些课程需要先导课程，有些课程则不需要，而有些课程又是其他课程的先导课程。,应用举例2制定教学计划,第1章 概论,1.2 基本概念和术语,1.2 基本概念和术语,数据(Data)：是对信息的一种符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。数据元素(Data Element)：是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。数据项(Data Item)：一个数据元素可由若干个数据项组成。数据项是数据
4、的不可分割的最小单位。（数据可由若干个数据元素组成，数据元素又可由若干数据项组成）,1.2 基本概念和术语,1.2 基本概念和术语,学生档案信息表,数据元素,数据项,1.2 基本概念和术语,数据的逻辑结构：数据元素之间的结构关系。数据的逻辑结构是一种数学模型，体现了数据的组织方式。四类基本结构集合结构 线性结构树型结构图状结构或网状结构,1.2 基本概念和术语,特别注意： 逻辑结构与数据元素本身形式、内容无关 逻辑结构与数据元素的相对位置无关 逻辑结构与所含结点个数无关,1.2 基本概念和术语,数据的存储结构（物理结构）： 数据的逻辑结构在计算机中的实现。四类存储方式:顺序存储方式：借助数据元
5、素的相对存储位置来表示数据 的逻辑结构；链式存储方式：借助数据元素地址的指针表示数据的逻辑 结构；索引存储方式：借助索引表中的索引指示各存储节点的存 储位置散列存储方式：用散列函数指示各节点的存储位置,1.2 基本概念和术语,运算：对逻辑结构的加工。 加工型运算：其操作改变原逻辑结构的值。 如：结点个数、结点内容等。 引用型运算：其操作不改变原逻辑结构的值基本运算：建立查找读取插入删除,第1章 概论,1.3 算 法,1.3 算 法,算法规定了求解给定类型问题所需的所有处理步骤及执行顺序，使给定类型问题能在有限时间内被机械的求解。 算法必须使用某种语言描述：程序伪语言算法非形式算法（自然语言）
6、本教材采用类C语言描述算法 printf 表示输出，scanf表示输入,第1章 概论,1.4 算法分析,1.4算法分析,评价算法的好坏标准：正确性(Correctness )易读性(Readability)健壮性(Robustness)高效性(Effectiveness) 一个算法的时空性是指算法的 时间复杂度和空间复杂度（算法的计算量和存储量）。 算法分析主要分析算法的 时间复杂度和空间复杂度，目的是提高算法的效率。,1.4算法分析,合理地选择一种或几种操作作为“标准操作”，无特殊说明，默认以赋值语句作为标准操作。确定每个算法共执行多少次标准操作，并将此次数规定为该算法的计算量。 以算法在所
7、有输入下的计算量的最大值作为算法的计算量，称为算法的最坏情况时间复杂度 以算法在所有输入下的计算量的加权平均值作为算法的计算量，称为算法的平均情况时间复杂度 最坏时间复杂度和平均时间复杂度，度量算法的性能,第1章 练习,void max1(int a,b,c,d) a*=d;b*=d;c*=d; if(ab) x=a; else x=b; if(cx) x=c; printf(%dn,x);,void max2(int a,b,c,d) if(ab) x=a; else x=b; if(cx) x=c; x*=d;printf(%dn,x);,求算法max1和max2最坏情况时间复杂度,设a、b、c、d中各含一个整数。求a、b、c中最大值与d的乘积,第1章 练习,下列程序段的时间复杂度为_。product = 1;for (i = n;i0; i-)for (j = i; j=n; j+)product *=j;,基本操作执行次数 T(n)=1+2+n= (n+1)n/2时间复杂度量级为 t(n)=O(n2),上节回顾,基本概念：Data, Data Element, Data Item数据的逻辑结构：4类基本结构5种基本运算数据的物理结构：4类存储方式算法：基本要求 C.R.R.E,
