数据结构 四川理工(精品·公开课件).ppt

@ DCS of SUSE 基本概念 (1)数据：所有能被计算机识别、存储和处理的符号的集合（包括数字、字符、声音、图像等信息 ）。 (2)数据元素:是数据的基本单位，具有完整确定的实际意义。在计算机程序中通常作为一个整体进行考虑和处理。一个数据元素可由若干个数据项组成。 (3)数据项:构成数据元素的项目。它是数据不可分割的最小单位。 (4)数据类型：指一个类型和定义在这个类型上的操作集合。例：C语言（基本类型：整型、浮点型、字符型等构造类型：数组、结构、联合、指针、枚举等） (5)抽象数据元素：抽象定义的、没有实际含义的数据元素。 (6)抽象数据类型：用户自己定义的数据类型。 数据结构 （1） R=(D, S) D={ a, b, c, d, e, f } S={a,e, b,c, c,a, e,f, f,d} 　　物理结构亦称存储结构，是数据的逻辑结构在计算机存储器内的表示（或映像）。它依赖于计算机。 第2章 线性表 复习要点： 1.基本概念 线性结构、线性表、位序、长度、空表等 2.线性表的基本操作 主要掌握插入、删除等运算及特性 3.顺序存储、链式存储特点，组织方式 顺序表、单链表、双链表的查找、插入和删除等操作 一、线性表（linear_list） 线性表是n个数据元素的有限序列，记为： L=（a1,a2, …,an） 线性表的顺序存储结构 一、顺序存储结构 用一组地址连续的存储单元依次存储线性表的元素。设线性表的每个元素占用k个存储单元，则第i个元素ai 的存储位置为：Loc(ai)=Loc(a1)+(i-1)*k 其中，Loc(ai)为线性表的起址。 二. 插入和删除操作 1. 插入运算 INSERT（L, i, b） 插入前：L=（a1, ... , ai-1, ai, ... ,an） 插入后：L=（a1, ... , ai-1, b, ai, ... ,an ） 线性表上的基本运算 插入运算 含义： 　　将元素e插入到线性表：(a1, a2, …, ai-1, ai, …, an)中，构成新的线性表(a1, a2, …, ai-1, e, ai, …, an)，满足ai-1 ≤e ≤ai,(其中≤为比较关系),即不破坏原线性关系。 表的长度为n+1 将元素e插入到元素ai-1之后，ai-1的直接后继和ai 的直接前驱就改变了，需要在顺序表的存储结构上反映出来。 2. 删除运算DELETE（L,i） 删除前：L=（a1,...,ai-1,ai,ai+1,...,an） 删除后：L=（a1,...,ai-1,ai+1,...,an） 线性表顺序存储结构的特点 (1). 逻辑上相邻的元素，其物理位置也相邻； (2). 可随机存取表中任一元素； (3). 必须按最大可能长度预分存储空间，存储空间利用率低，表的容量难以扩充，是一种静态存储结构； (4). 插入删除时，需移动大量元素，平均移动元素为n/2。 顺序表的基本运算的复杂度 插入 T(n)=O(n) ，S(n)=O(1) 删除 T(n)=O(n) ，S(n)=O(1) 线性表的链式表示和实现 链表---线性表的链式存储 内涵： 线性表的链式存储指用任意的存储单元存放线性表中的元素，每个元素与其直接前驱和（或）直接后继之间的关系用指针来存储。这称为链表。 术语 结点：数据元素及与其有直接关系的元素的地址构成的存储单位。 单链表的表示和实现 单链表上的查找运算 在单链表中，必须从头指针出发进行查找： 查找第i个元素 查找指定的元素是否在表中 ... 若找到，则返回该元素的值，否则返回ERROR。 在单链表上查找第i个元素的示意图 单链表上的插入运算(第i个位置上插入新的结点) 逻辑运算 (a1, a2, …, ai-1, ai, ai+1, …, an) 链表的优缺点 优点： 插入、删除时无须移动元素，只需修改指针 根据需要申请存储空间，且不要求连续的存储空间 缺点： 对表中的元素只能进行顺序访问 用指针指示元素之间的逻辑关系（直接前驱、后继），存储空间利用率低 双向链表 双向链表上的插入操作(将元素e插入到链表的第i个结点前) 双向链表上的删除操作(删除第i个结点) 第3章 栈和队列 一、栈的概念 栈（stack）是插入和删除操作限定在表尾进行的线性表。 栈的逻辑表示为：S =（a1,a2, …,an） 表尾元素an称为栈顶(top) 表头元素a1称为栈底(bottom) 不含元素的空表称为空栈 栈的运算特性是后进先出(Last In First Out-