java版数据结构 第1章 绪论课件.ppt

《java版数据结构 第1章 绪论课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构第一章概述第一章概述教学目标：了解数据结构的相关概念和掌握算法的基本概念和性质算法的性能分析和评价重点：算法的概念、描述方法、评价标准和分析难点：算法分析为什么要学习数据结构软件设计是计算机学科各个领域的核心。软件设计时要考虑的首要问题是数据的表示、组织和处理方法。数据结构设计和算法设计是软件系统设计的核心。数据结构十算法=程序例1-1学生信息检索系统学生文件线性表学号姓名性别专业年级980001吴承志男计算机科学与技术98级980002李淑芳女信息与计算科学98级990301刘丽女数学与应用数学9

2、9级990302张会友男信息与计算科学99级990303石宝国男计算机科学与技术99级000801何文颖女计算机科学与技术2000级000802赵胜利男数学与应用数学2000级000803崔文靖男信息与计算科学2000级010601刘丽女计算机科学与技术2001级010602魏永鸣男数学与应用数学2001级例1学生信息检索系统按姓名线性表崔文靖8何文颖6李淑芳2刘丽3,9石宝国5魏永鸣10吴承志1赵胜利7张会友4索引表例1学生信息检索系统按专业索引表线性表例1学生信息检索系统按年级索引表线性表2000级6,

3、7,82001级9,1098级1,299级3,4,5例1-2人机对奕问题树……..……..…...…...…...…...图课程编号课程名称先修课程C1计算机导论无C2数据结构C1，C4C3汇编语言C1C4C程序设计语言C1C5计算机图形学C2，C3，C4C6接口技术C3C7数据库原理C2，C9C8编译原理C4例1-3教学计划编排问题数据结构课程主要是研究非数值计算的程序设计问题中所出现的计算机操作对象以及它们之间的关系和操作的学科。学习数据结构的目的就是为了了解计算机处理对象的特性，将实际问题中所涉及的处

4、理对象在计算机中表示出来并对它们进行处理。数据结构的学科地位.综合性的专业基础课.介于数学、计算机硬件和计算机软件之间的核心课程.不仅仅是程序设计的基础，而且是设计和实现编译程序、操作系统、数据库系统及其他系统程序和大型应用程序的基础1.1.2有关概念和术语数据（data)—所有能输入到计算机中去的描述客观事物的符号。数据元素（dataelement）—数据的基本单位，也称节点（node）或记录（record）。数据对象（dataObject）—具有共同特性的元素集合，是数据的一个子集。数据结构（datas

5、tructure)—数据元素和数据元素关系的集合。根据数据元素间关系的基本特性，有四种基本数据结构（集合）——数据元素间除“同属于一个集合”外，无其它关系线性结构——一个对一个，如线性表、栈、队列树形结构——一个对多个，如树图状结构——多个对多个，如图一个数据结构有两个要素：数据元素的集合；关系的集合。Data_Structure=(D，R)其中D是数据元素的有限集，R是D上的关系的有限集。数据的逻辑结构数据的逻辑结构—指数据结构中元素之间的逻辑关系。它是从具体问题中抽象出来的数学模型。是独立于计算机存储器

6、（与具体的计算机无关）。可分为如下几种基本类型：集合结构：线性结构：树型结构：图形结构：数据的存储结构数据的存储结构—数据的逻辑结构在计算机存储器中的存储方式，又称物理结构。可分为如下两种类型。顺序存储结构：链式存储结构：元素n……..元素i……..元素2元素1LoLo+mLo+(i-1)*mLo+（n-1)*m存储地址存储内容Loc(元素i)=Lo+（i-1)*m顺序存储1536元素21400元素11346元素3∧元素41345h存储地址存储内容指针1345元素114001346元素4∧…….……..……

7、.1400元素21536…….……..…….1536元素31346链式存储h数据的逻辑结构数据的存储结构数据的运算：检索、排序、插入、删除、修改等线性结构非线性结构顺序存储链式存储线性表栈队树形结构图形结构数据结构的三个方面：1.2算法的概念及其特征算法（algorithm）：是在解决问题时，按照某种机械的步骤一定可以得到问题的结果的处理过程；是计算机解决问题的过程，是解决某一特定问题的具体步骤的描述，是指令的有限序列。1.2.2算法的三要素操作：算术运算：加、减、乘、除。关系比较：大于、小于、等于、不等于

8、逻辑运算：与、或、非数据传送：输入、输出（计算）、赋值（计算）。控制结构：顺序结构：选择结构：循环结构：数据结构：1.2.3算法的基本性质目的性分步性有序性有限性操作性1.2.4算法的基本特征有穷性确定性可行性算法有零个或多个的输入算法有一个或多个的输出1.2.5算法设计的要求正确性可读性稳健性高效率与低存储量的要求1.3算法分析和评价对算法的分析和评价，一般应考虑正确性、可维护性、可读性、运算量、占用存储空间等