数据结构导论.docVIP

数据结构导论 课程代码：02142 数据结构:计算机组织数据和存储数据的方式。 数据：所有被计算机存储，处理的对象。 数据元素：数据的基本单位，数据元素简称元素。 数据的元素由数据项组成。 数据库中数据项又称字段或域。 数据项是数据不可分割的最小标识单位。 数据结构包括：数据的逻辑结构，数据的存储结构和数据的基本运算。 数据元素之间关系的不同特性，集合，线性结构，树结构，图结构。 数据元素之间的关联方式：顺序存储方式和链式存储方式（主要的）索引存储方式，散列存储方式。算法分析因素： 正确性 易读性 健壮性 时空性 时间复杂度：0（1）常数阶，（算法的时间复杂度与输入规模n无关）；O（log2n）对数阶；O(n)线性阶；O(nc)多项式阶；O(Cn)指数阶。（C为大于1的正整数） 线性表 2.1线性表的基本概念 线性表是一种线性结构,它是由n(=o)个数据元素组成的有穷序列，数据元素又称结点。 2.2线性表的顺序存储 数据存储是最简单的一种存储方式。 线性表顺序存储的方法是：表中的结点一次存放在计算机内存中一组连续的存储单元中。 用顺序表存储实现的线性表称为顺序表。 一般情况下元素比较和移动的次数为n—i+1。插入的算法平均移动次数约为n/2，时间复杂度o(n) 删除算法，最坏情况下元素移动次数为n-1,时间复杂度为o(n),平均移动次数为（n-1）/2,时间复杂度O(n) 定位算法，平均时间复杂度为o（n）求表长和读表元素算法的时间复杂度为o(1)。 2.3线性表的连接存储 线性表常见的链式存储结构有单链表，循环链表和双向 链表，最简单的是单链表。 Data部分称为数据域，用于存储线性表的一个数据元素，next称为指针域，指针指向本结点所含数据元素的直接后继结点。尾借点指针域的值Null成为空指针。Head等于null，表示该链表无任何结点，是空单链表。 -head链表的每个结点包含有数据域和指针域，指针域存放的是下一个 结点的地址。 头结点的数据域可以不存放任何信息，也可以存放一个特殊标志或表长，也可以根据算法的需要定义。 定位运算又称作按值查找 建表算法的计算的计算量约1+2+3……+n-1=n(n-1)/2,时间复杂度o(n*n)。 时间与个数成正比，时间复杂为o(n) 直接前驱结点的指针域prior,每个结点有两个指针。 双向循环链表的对称性可以用p=p-prior-next=p-next-prior。 按位置查找运算，顺序表是随机存取，时间复杂度o(1).单链表时间复杂度o(n). 单链表的每个结点包括数据域与指针域。 栈，队列和数组 3.1 允许进行插入和删除的一端称为栈顶，另一端称为栈底。不含任何数据元素的栈称为空栈。处于栈顶位置的数据元素称为栈顶元素。 栈的修改原则是后进先出，栈又称后进先出线性表，栈的插入和删除运算分别称进栈和出栈。通常用一个一维数组和一个记录栈顶位置的变量来实现的顺序存储。 3.2 队列是有限个类型数据元素的线性序列，是一种先进先出的线性表，新加入的数据元素插在队列的尾端，出队列的数据元素在队列首部被删。 顺序队列结构类型中有三个域：data,front,rear。 当队列为空时，front==rear,也为满。解决方法，一是为队列另一个标志，用来区分是空还是满；二是队列少用一个元素空间，当只剩下一个单元时就认为队列满。 队列的链接实现实际上是使用一个带有头结点的单链表来表示队列，称为练队列。 3.3数组的存储结构 一维数组元素的内存单元地址是连续的，二维数组可有两种存储方法：一种是以列序为主序的存储：另一种是一行序为主的存储。 一维数组M(n(n+1)/2)作为n阶对称矩阵。 数和二叉数 4,1 线性结构中的一个结点至多只有一个直接后继，而树形结构中一个节点可以有一个或多个直接后继。 当n=0时，称为空树； 当n0时，有且仅有一个称为根的结点，除根结点外，其余结点分为m=0个不相交的非空集合，这些集合中的每一个都是一棵树，称为根的子树。 4,1 结点的度：树上任意结点所拥有的子树的数目称为该结点的度。 叶子:度为0的结点成为叶子或终端结点。 树的度;一颗树中所有结点的度的最大值称为该树的度。 结点的层次;从根开始算起，根的层次为1，其余结点的层次为其双亲的层次加1. 树的高度：一棵树中所有结点层次树的最大值称为该树的高度或深度。 有序树：若树中个结点的字树从左到右是有次序的，不能互换，称为有序树。 无序树：若树中各结点的子树是无次序的，可以互换，则称为无序树。 4,2二叉树 二叉树是n(n=0)个元素的有限集合，该集合或者为空，或者由一个根及两颗互不相交的左子树和右子树组成，其中左子树和右子树均为二叉树 。 4,2，2二叉树的性质 1.二叉树