自考数据结构导论--第一章-概论介绍.ppt

数据结构导论 主讲：徐青香 2013、4 第1章 概论 1.1引言 1.2基本概念和术语 1.3算法及描述 1.4算法分析 1.1 引言 1.1 引言 数据结构主要研究： 1）数据（计算机加工对象）的逻辑结构。 2）实现各种基本操作的算法。 应用举例1——学籍档案管理 数据特点： 每个学生的信息占据一行，所有学生的信息按学号顺序依次排列构成一张表格； 表中每个学生的信息依据学号的大小存在着一种前后关系，这就是我们所说的线性结构； 对它的操作通常是：在学生档案中查找出某人的档案，读取某个学生的信息，插入某个学生的信息，删除某个学生的信息，更新某个学生的信息等等。 应用举例2——制定教学计划 在制定教学计划时，需要考虑： 各门课程的开设顺序，即有些课程需要先导课程，有些课程则不需要，而有些课程又是其他课程的先导课程。 1.2 基本概念和术语 基本术语 数据（Data)：所有能被计算机处理的符号的集合。 数据元素（Data Element）：是数据这个集合中的一个个体即数据的基本单位。 数据项（Data Item）：数据元素常常还可分为若干个数据项，数据项是数据具有意义的最小单位。 逻辑结构（Logical Structure）： 指数据元素之间的结构关系。 物理结构（Physical Structure）也成为存储结构： 指数据结构在机内的表示，数据的逻辑结构在计算机中的实现。 数据的逻辑结构(D, {R}) 可分为下列几种: D = {d1, d2, …, dn} 。 1. 集合: 数据元素同“属于一个集合”。 R = {}。 2. 线性结构: R= {(d1, d2), (d2, d3), …, (dn-1, dn)}, 即除起始节点和终端结点d1, dn外,每个节点有一个前驱和一个后继。 3. 树状结构: (D, {R}) 构成树, 即每个元素最多有一个前驱, 可以有多个后继。 4. 图状结构: (D, {R})构成一个图。 逻辑结构的种类： 特别注意： 数据的存储结构 数据在计算机内的表示形式称为 数据的存储结构 存储结构的主要部分 存储结点（每个存储结点存放一个数据元素） 数据元素之间关联方式的表示 数据的存储结构 数据结构的存储包含数据元素的存储及其逻辑关系的存储 存储结构可分为: 顺序存储结构、链式存储结构、索引存储方式和散列存储方式等。 顺序存储结构与链式存储结构最基本，应该重点掌握。如，如何操作，各有什么特点，什么时候选择顺序结构，什么时候选择链式结构等。 4种存储结构 顺序存储结构：借助数据元素的相对存储位置来表示数据的逻辑结构；线性表的顺序存储方法：将表中的结点一次存放在计算机内存中一组连续的存储单元中。 链式存储结构：借助数据元素地址的指针表示数据的逻辑结构； 索引存储结构：借助索引表中的索引指示各存储节点的存储位置 散列存储结构：用散列函数指示各节点的存储位置 存储结构的分类: 顺序结构 顺序的方法: 将元素存储到一片连续的存储区. 存储结构的分类: 链式结构 这种结构是给结点附加一个指针字段, 指出其后继节点的位置, 即存放结点的存储单元分为两部分: 特点： 1）动态分配，不需要预先确定内存分配； 2）插入和删除不需要移动其他元素； 3）非随机存取结构。 逻辑结构与存储结构的关系 运算 运算就是指在某种逻辑结构上施加的操作，即对逻辑结构的加工。 加工型运算：其操作改变原逻辑结构的值 如：结点个数，结点内容等 引用型运算：其操作不改变原逻辑结构的值 查找 读取 插入 删除 更新 以上操作哪些是加工型操作，那些是引用型操作？ 1.3算法及描述(运算的实现) 算法规定了求解给定类型问题所需的所有“处理步骤”及执行顺序，使给定类型问题能在有限时间内被机械的求解。 算法必须使用某种语言描述： 程序 介于自然语言和程序设计语言的伪代码 非形式算法（自然语言） 框图(N-S图) 本教材中使用了类C语言描述算法 一个算法是对特定问题求解步骤的一种描述,它是指令的有穷序列。 算法具有以下特性： 1) 有穷性: 一个算法总是在执行有穷步后结束。 2) 确定性: 算法的每一步都必须是明确地定义的。 3) 可行性: 算法中的每一步都是可以通过已经实现的操作来完成的。 4) 输入: 一个算法有零个或者多个输入, 这些输入取自于特定的对象集合。 5) 输出:　一个算法有一个或者多个输出，它们是与输入有特定关系的量。 算法描述 我们教程主要用C语言描述。 以下简单复习下C语言的内容。 5、语句 int a,b,sum; sum=a+b; printf