数据结构4川理工.ppt

第1章　绪　论;基本概念;数据结构;集合结构： 仅同属一个集合 线性结构: 一对一（1:1) 树 结 构: 一对多（1:n) 图 结 构: 多对多 (m:n);（1） R=(D, S) D={ a, b, c, d, e, f } S={a,e, b,c, c,a, e,f, f,d};　　物理结构亦称存储结构，是数据的逻辑结构在计算机存储器内的表示（或映像）。它依赖于计算机。;时间复杂度和空间复杂度如何表示？;特别说明：如果无论算法规模怎样变化，其执行时间为一常数，则该算法的时间复杂度为O(1).;;第2章 线性表; 一、线性表（linear_list） 线性表是n个数据元素的有限序列，记为： L=（a1,a2, …,an）;线性表的顺序存储结构;二. 插入和删除操作 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个位置上插入新的结点) 逻辑运算 (a1, a2, …, ai-1, ai, ai+1, …, an);链表的优缺点 优点： 插入、删除时无须移动元素，只需修改指针 根据需要申请存储空间，且不要求连续的存储空间 缺点： 对表中的元素只能进行顺序访问 用指针指示元素之间的逻辑关系（直接前驱、后继），存储空间利用率低;head;双向链表上的删除操作(删除第i个结点);第3章 栈和队列;二、队列的概念 队列（Queue）是限定仅在一端插入,另一端删除的线性表。 允许插入的一端叫队尾( rear), 允许删除的一端叫队头(front), 不含元素的空表称为空队列 队列的运算特性是先进先出(First In First Out--FIFO);插入、删除操作;第4章 串;第5章 数组和广义表;第6章 树与二叉树;树的基本术语 1. 树的结点:包含一个DE和指向其子树的所有分支; 2. 结点的度:一个结点拥有的子树的个数,度为零的结点称为叶结点; 3. 树的度:树中所有结点的度的最大值Max(D(I)) 含义:树中最大分支数为树的度; 4. 结点的层次及树的深度:根为第一层,根的孩子为第二层,若某结点为第k层,则其孩子为k+1层. 树中结点的最大层次称为树的深度或高度 5.森林:是m(m=0)棵互不相的树的集合 森林与树概念相近,相互很容易转换.; 二叉树性质(扩展要求掌握各性质的推论) 性质1. 在二叉树的第i层上至多有2i-1个结点(i≥1)。 性质2. 深度为k的二叉树至多有2k-1个结点(k≥1)。 （深度一定，二叉树的最大结点数也确定） 性质3. 二叉树中,终端结点数n0与度为2的结点数n2有如下关系: n0=n2+1 性质4. 结点数为n的完全二叉树，其深度为 └log2n┘ + 1 ;性质5. 在按层序编号的n个结点的完全二叉树中，任意一结点i(1≤i≤n)有： ⑴ i=1时，结点i是树的根；否则(i1)，结点i的双亲为结点└i/2┘。 ⑵ 2i＞n时，结点i无左孩子，为叶结点；否则，结点i的左孩子为结点2i。 ⑶ 2i+1＞n时，结点i无右孩子；否则，结点i的右孩子为结点2i+1。 性质6. 含有n个结点的二叉链表中，有n+1个空链域。;二叉树的遍历;线索二叉树： ⑴ 结点结构 在二叉链表中增加 lta