《数据结构软》PPT课件

《《数据结构软》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构（C语言版）作者：黎剑兵1第一章绪论[学习内容]常用术语算法评价时间复杂度与空间复杂度的分析[重点]了解逻辑结构物理结构和数据的运算三方面相关概念及相互关系[难点]时间复杂度的分析方法[掌握]用类C语言的表示方法会用类C编写程序2第一章绪论计算机科技是一门研究用计算机进行信息表示和处理的科学。主要涉及两方面的问题：信息的表示和信息的处理信息的表示和组织直接关系到处理信息的程序的效率，随着计算机的应用领域的扩大。信息量的增加，信息范围的拓宽，使系统程序和应用程序的规模的日趋增大，结构也日趋增大。因此，为了编写出一个“好

2、”的程序，必须分析处理的对象的特征及个对象之间的存在的关系。这就是本课程所要研究的问题。3第一章绪论计算机程序是对信息进行加工处理。这些信息之间大多数情况下往往具有重要的结构关系。这就是数据结构的内容。那么，什么是数据结构呢？4数学软件硬件DS1.地位第一章绪论5数学软件硬件DS1.地位第一章绪论数据结构DataStructure6机外表示处理要求逻辑机构基本运算存储机构算法数据模型问题实现2.主要内容第一章绪论7机外表示处理要求逻辑机构基本运算存储机构算法数据模型问题实现2.主要内容第一章绪论(1)要对所加工的对象进行逻辑

3、组织(2)如何把加工对象存储到计算机中去？(3)数据运算83.学科定义<1-1>什么是数据结构数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等等的科。9<1-2>基本概念和术语数据元素(dataelement)数据基本单位，也称节或孩子，可由若干个数据项组成。数据项是数据最小单位数据(data)是对客观事物的表示，指所有能输入到计算机并被计算机程序处理的符号的总称。数据对象(dataobject)性质相同的数据元素的集合数据结构数据元素之间的相互关系101)集合<1-2>基本概念和术语数

4、据间的四种典型结构：2）线形3）树形4）图或网络：11<1-2>基本概念和术语四种典型结构：1)集合12四种典型结构<1-2>基本概念和术语2）线形：13四种典型结构：<1-2>基本概念和术语3）树形：14四种典型结构：<1-2>基本概念和术语4）图或网络：15<1-2>基本概念和术语（5）逻辑结构：从具体问题抽象出的数学模型。体现逻辑关系。（6）物理结构(存储结构)：DE及关于在计算机中的表示。DE存储称为节点关系存储：a.顺序存储b.链式存储16<1-2>基本概念和术语（7）DS广义定义：DE的逻辑结构DE的物理结构DE

5、的抽象运算（8）基本操作加工型：查找删除更新排序引用型：查找171．数据的逻辑结构2、数据的存储结构3、数据的运算：检索、排序、插入、删除、修改等。A．线性结构B．非线性结构A顺序存储B链式存储线性表栈队树形结构图形结构数据结构的三个方面<1-2>基本概念和术语18<1-3>算法和算法分析一、算法定义算法是对特定问题求解步骤的一种描述，是指令的有限序列。特性：有穷性确定性可行性输入输出19<1-3>算法和算法分析二、算法的描述与分析描述：类C语言要求正确性：a.语法b.n个输入c.一组典型的苛刻的输入d.所有输入可读性健壮性

6、效率与存贮量20<1-3>算法和算法分析分析标准a、时间复杂度：算法中基本操作重复执行的次数(频度)。T(o)=O(f(n))时间复杂度分为平均时间复杂度和最坏时间复杂度复杂度的值取规模函数最高阶21分析标准a、时间复杂度：算法中基本操作重复执行的次数。T(o)=O(f(n))时间复杂度分为平均时间复杂度和最坏时间复杂度复杂度的值取规模函数最高阶<1-3>算法和算法分析b、空间复杂度：算法所需存贮空间S(n)=O(f(n))22<1-3>算法和算法分析例：分析下列语句段的时间复杂度m=0;1for(k=0;k

7、+1for(j=0;j

8、m=m+I;for(j=0;j