数据结构(软件).ppt

数 据 结 构 第 一 章 绪 论 [学习内容] 常用术语 算法评价 时间复杂度与空间复杂度的分析 [重点]了解逻辑结构 物理结构和数据的运算三方面相关概念及相互关系 [难点] 时间复杂度的分析方法 [掌握] 用类C语言的表示方法会用类C编写程序 计算机科技 是 一门研究用计算机进行信息表示和处理的科学。 主要涉及两方面的问题：信息的表示和信息的处理 信息的表示和组织直接关系到处理信息的程序 的效率，随着计算机的应用领域的扩大。信息量的增加，信息范围的拓宽，使系统程序和应用程序的规模的日趋增大，结构也日趋增大。因此，为了编写出一个“好”的程序，必须分析 处理的对象的特征及个对象之间的存在的关系。这就是本课程所要研究的问题。 计算机程序 是 对信息进行加工处理。这些信息之间大多数情况下往往具有重要的结构关系。这就是数据结构的内容。那么，什么是数据结构呢？ (1)要对所加工的对象进行逻辑组织 (2)如何把加工对象存储到计算机中去？ (3)数据运算 数据结构 是一门研究非数值 计算的程序设 计问题中计算机的 操作对象以及它们之间的关系和 操作等等的科。 数据元素(data element) 数据基本单位，也称节或孩子，可由若干个数据项组成。数据项是数据最小单位 数据(data) 是对客观事物的 表示，指所有能输入到计算机并被计算机程序处理的符号的总称。 数据对象( data object)性质相同的数据元素的集合 数据结构 数据元素之间的相互关系 1) 集合 1) 集合 2）线形： 3）树形： 4）图或网络： （6）物理结构(存储结构)： DE及关于在计算机中的表示。 DE存储称为节点 关系存储：a. 顺序存储 b. 链式存储 （7）DS广义定义： DE 的逻 辑 结 构 DE 的物 理 结 构 DE 的 抽 象 运 算 （8）基本操作 加工型：查找 删除 更新 排序 引用型：查找 算法是对特定问题求解步骤的一种描述，是指令的有限序列。 特性： 有穷性 确定性 可行性 输入 输出 二、算法的描述与分析 描述：类C语言 要求 正确性： a. 语法 b. n个输入 c. 一组典型的苛刻的输入 d. 所有输入 可读性 健壮性 效率与存贮量 分析标准 a 、时间复杂度 ：算法中基本操作重复执行的次数(频度)。 T(o)=O(f(n)) 时间复杂度分为平均时间复杂度和最坏时间复杂度 复杂度的值取规模函数最高阶 分析标准 a 、时间复杂度 ：算法中基本操作重复执行的次数。 T(o)=O(f(n)) 时间复杂度分为平均时间复杂度和最坏时间复杂度 复杂度的值取规模函数最高阶 第 二 章 线 性 表 [学习内容] 线性表定义 线性表的抽象数据结构 线性表的顺序存储和操作实现 线性表的链接存储 线性表在链表上的操作实现 线性表在双向链表操作实现 在数据元素的非空有限集合中 1）“第一个 ”唯一 2）“最后一个”唯一 3）除第一个外，每一个有且仅有一个直接前驱 4）除最后一个外，每一个均有且仅有一个直接后继 一、线性表的定义 一、线性表的定义 一个线性表可以用一个标识符来命名： A=(a1 , a2 , … , ai , ai+1 , … , an) ai可以是基本数据类型也可以是struct 类型 二、线性结构特点 在数据元素的非空有限集中 元素个数n—表长度，n=0空表 存在唯一的一个被称作“第一个”的数据元素 存在唯一的一个被称作“最后一个”的数据元素 除第一个外，集合中的每个数据元素均只有一个前趋 除最后一个外，集合中的每个数据元素均只有一个后继 元素同构，且不能出现缺项 线性表几个具体例子 L1=（’a’,’b’,’c’,’4’,’7’,’+’,’-’,’*’,’/’） L2=（25,35,28,49,51,87,46,32,88） L3=（“BASIC”,“PASCAL”,“JAVA”,“OK”） L