第3章算法与数据结构3.ppt

第三章 数据结构 3.2.1 数据结构概述 。 数据结构的研究内容 数据的逻辑结构、数据的存储结构、数据的运算 数据的逻辑结构：Data-Structure ＝ (D,R) 其中： D是数据元素的集合，R是D上关系的集合 一般将数据结构分为两大类：线性数据结构和非线性数据结构。线性数据结构有线性表、栈、队列、串和文件；非线性数据结构有树和图 程序中的数据运算是定义在数据的逻辑结构上的，但运算的具体实现要在存储结构上进行。每种逻辑结构都有一个运算集合。常用的运算有检索、插入、删除、更新、排序等 3.2.2 线性表 线性表的逻辑结构是n个数据元素的有限序列: (a1, a2 ,a3,...,an) n为线性表的长度(n≥0)，n=0的表称为空表 数据元素呈线性关系.必存在唯一的称为“第一个”的数据元素;必存在唯一的称为“最后一个”的数据元素； 除第一个元素外，每个元素都有且只有一个前驱元素； 除最后一个元素外，每个元素都有且只有一个后继元素。 所有数据元素ai在同一个线性表中必须是相同的数据类型 线性表按其存储结构可分为顺序表和链表。用顺序存储结构存储的线性表称为顺序表；用链式存储结构存储的线性表称为链表 线性表的基本运算主要有： (1)在两个确定的元素之间插入一个新的元素； (2)删除线性表中某个元素； (3)按某种要求查找线性表中的一个元素，需要 时，还可找到元素进行值的更新 1.顺序表和一维数组 将线性表中的数据元素依次存放在某个存储区域中,所形成的表称为顺序表。一维数组就是用顺序方式存储的线性表，其下标可看成元素的相对地址 运算： (1) 插入，在线性表(a1, a2....，ai，ai+1....，an)的第i个位置插入元素x，算法如下： (2)删除：在表长为n的线性表(a1,a2,..ai-1,ai,ai+1..an)中删除第i个数据元素，通常还需将第i+1个至第n个元素向前推动一个位置，即(a1, a2 ,…，ai-1,ai+1，…，an)，其算法描述如下: 2．链表 顺序表的不足： 最后一个结点没有后继结点，它的指针域为空(记为NIL 或∧)。另外还需要设置一个指针head，指向单链表的第一个结点 链表的一个重要特点是插入、删除运算灵活方便，不需移动结点，只要改变结点中指针域的值即可 (2）循环链表：循环链表和单链表的差别仅在于链　　　　表中最后一个结点的指针域不为“NIL”，而是指向　头一个结点，成为一个由链指针链结的环 (3）双向链表：设有一个指向后继结点的指针和一个指向前驱结点的指针 3．栈 栈(STACK)也是一种特殊的线性表，是一种“后进先出”的结构，它的运算规则受到一些约束和限定，故又称限定性数据结构 (1)栈的结构特点 　栈是限定仅在表尾进行插入和删除运算的线性表，表尾称为栈顶(top)，表头称为栈底(bottom) 　栈的物理存储可以用顺序存储结构，也可以用链式存储结构 　(2）栈的运算 　 设置一个空栈 判定栈是否为空 进栈 退栈 读取栈顶元素 4．队列 (1）队列的结构特点 队列(Queue)是限定所有的插入只能在表的一端进行，而所有的删除都在表的另一端进行的线性表 表中允许插入的一端称为队尾(Rear)，允许删除的一端称为队头(Front) 队列的操作是按先进先出的原则进行的 队列的物理存储可以用顺序存储结构，也可以用链式存储结构。 (2）队列的运算：设置一个空队列；判定队列是否是空队列；入队列；出队列；读取队头元素等 3.2.4 树和二叉树 树的形式化定义： 　树(Tree)是由 一个或多个结点 组成的有限集合T，其中有一个特定的称为根的结点；其余结点可分为m(m≥0)个互不相交的有限集T1,T2,T3 ,..,Tm，每一个集合本身又是一棵树，且称为根的子树 结点子树个数为结点的度,结点度的最大值为该树的度 图中结点B的度为2，树的度为3 度为m的树称为m叉树 2.树的存储结构 树的存储结构可以采用具有多个指针域的多重链表，结点中指针域的个数应由树的度来决定 但在实际应用中，这种存储结构并不方便，一般将树转化为二叉树表示，进行处理 3.树的运算 树的遍历 根据树的递归定义，有两种遍历树的方法： (1)先根(次序)遍历：若树中只有一个根结点，则访问树的根结点； 否则，首先访问树的根结点，然后依次先根遍历每棵子树。 (2)后根(次序)遍历：若树中只有一个根结点，则访问树的根结点； 否则，首先依次后根遍历每一棵子树，然后访问树的根结点。 4 二叉树 其结构定义为：二叉树是n(n=1)个结点的有限集，由一个根结点和两棵分别称为根的左子树和右子树的、互不相交