《数据结构》电子教案.ppt
《《数据结构》电子教案.ppt》由会员分享,可在线阅读,更多相关《《数据结构》电子教案.ppt(59页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、开放教育本科计算机科学与技术专业数据结构电子教案第一章 概论n理解和掌握u 数据和数据结构的基本概念u 数据的逻辑结构和物理结构u 算法的定义和质量要求u 算法的渐进时间复杂度分析n需要掌握的知识点 数据与数据结构的基本概念 数据元素是数据处理的基本单位,数据项是数据处理的最小单位。 数据结构是数据对象中元素之间的关系的表示。 数据类型是数据结构的使用方式。 基本数据类型是计算机中已经实现了的数据结构。 数据的逻辑结构和物理结构 逻辑结构分为线性结构和非线性结构。 非线性结构又分为集合结构、层次结构和图结构。物理结构分为顺序结构、链接结构、索引结构和散列结构。 逻辑结构与数据内容、物理安排、元
2、素个数无关。区分线性或非线性结构的依据在于直接前驱和直接后继的数目。 算法复杂度分析 大O表示法:时间渐进复杂度。 并列程序段中各段时间复杂度的迭加规则。 嵌套程序段中各段时间复杂度的相乘规则。第二章 数组n理解和掌握u 一维数组和二维数组的概念u 数组和顺序表的异同u 特殊矩阵的压缩存储n需要掌握的知识点 一维数组和二维数组的概念u一维数组是相同类型元素的集合u二维数组是数组元素为一维数组的一维数组u 二维数组不是线性结构,有最多二个直接前驱和二个直接后继。 一维有序数组插入新元素的算法 一维数组各元素逆置的算法 数组与顺序表的异同u 顺序表是线性表的顺序存储表示。其逻辑顺序与物理顺序一致。
3、u 一维数组中非零元素可以不连续存放, 顺序表中非零元素必须连续存放。u 数组与顺序表可以随机存取和顺序存取。u 顺序表的存储可以借助一维数组。 特殊矩阵的压缩存储u 对称矩阵的下三角压缩存储时的地址转换公式。u 一维、二维数组元素地址的计算。v 按行存储计算v 按列存储计算 求一般矩阵各行元素之和的算法 求一般矩阵转置的算法11121110122221201112111010020100nnnnnnnnaaaaaaaaaaaaaaaa下三角矩阵B a00 a10 a11 a20 a21 a22 a30 a31 a32 an-1n-1 0 1 2 3 4 5 6 7 8 n(n+1)/2-1若
4、 i j, 数组元素Aij在数组B中的存放位置为 1 + 2 + + i + j = (i + 1)* i / 2 + j若 i j,Aij = Aji = j *(j +1) / 2 + i第三章 链接表n理解和掌握u 单链表的基本概念u 循环链表u 双向链表n需要掌握的知识点 单链表的基本概念u 单链表是线性表的链接存储表示。u 不能随机访问, 只能顺序访问。u 存储空间可以不断扩充。u 元素的物理顺序与逻辑顺序可不同。u 链表的插入与删除仅改变指针值。 有序单链表插入与删除算法。 有序单链表建立算法及性能分析。 循环链表u 链表最后一个结点的链接指针指示表头结点。只要知道任一结点地址就能
5、遍历其他所有结点。u 若操作仅在链表两头, 可仅给出链尾指针, 它的下一结点即链头 。 对于需要循环操作的线性表, 可用循环链表存储,例如链式队列的实现。 循环单链表的插入与删除算法。 双向链表u有两个链接指针:前驱和后继。u 链表中同时存在两个链:一个按前驱方向,一个按后继方向。u 在前驱方向和后继方向遍历, 时间复杂性都是O(1)。 在双向链表中两个方向的搜索算法。 在双向链表中插入新结点的算法。 在双向链表中删除一个结点的算法。第四章 栈与队列n理解和掌握u 栈与队列的结构与特点u 循环队列的结构与特点 n需要掌握的知识点 栈和队列的结构与特点u 栈与队列都是限制存取点的线性表。u 栈与
6、队列都只能顺序存取。u 栈是先进后出, 队列是先进先出。 u 顺序存储表示有“满”的问题。u 链表存储表示可以扩充,不存在“满”的问题。u 它们都有“空”的情形。 循环队列的结构与特点u 其存储表示是顺序的环形结构。u 队头指针指示实际队头的前一位置。u 队尾指针指示实际队尾位置。 判断循环队列队空与队满的算法。 循环队列:将一个新元素进队的算法。 循环队列:从队列退出元素的算法。 循环链表表示队列时的进队列和出队列的算法。第五章 递归与广义表n理解和掌握u 递归与递归算法u 递归算法的编制n需要掌握的知识点 递归与递归算法u 递归的定义可用递归过程解决。u 递归数据结构(链表、树等)可用递归
7、算法求解。u 递归算法包含两部分:基本项和归纳项。u 递归与递推的关系。u 单向递归与尾递归。 递归算法的编制 二叉树前序遍历的算法。 二叉树后序遍历的算法。 二叉树中序遍历的算法。 二叉树中交换根结点的左、右子树的算法。 完全二叉树用前序遍历实现顺序存储表示与二叉链表表示相互转换的算法。第六章 树与森林n理解和掌握u 二叉树的定义与性质u 二叉树的三种遍历u 树的存储表示u 霍夫曼树与霍夫曼编码u 堆 n需要掌握的知识点 二叉树的定义与性质u 二叉树的定义是递归的。u 二叉树各层最大结点数2i ( i = 0,1,u 二叉树高度为h时的最大结点数n = 2h+1 - -1。u 完全二叉树有n
8、个结点时的高度h : log2(n+1) - -1 。 u 完全二叉树结点i的双亲 (i- -1)/2 、左子女 2i+1、右子女 2i+2。 二叉树的三种遍历u 二叉树的前序遍历方法。u 二叉树的中序遍历方法。u 二叉树的后序遍历方法。u 二叉树的前序序列与中序序列唯一确定二叉树的方法。u 二叉树的后序序列与中序序列唯一确定二叉树的方法。u 二叉树的后序序列与前序序列只能确定一个结点的二叉树。 树的存储表示u 树的左子女/右兄弟表示(图示)。u 树的左子女/右兄弟表示中根没有右兄弟。u 森林的左子女/右兄弟表示中有n个非叶结点, 右指针为空的结点有n+1 个。u k叉树各层最大结点个数、高度
9、为h时的最大结点个数(kh+1- -1)/(k- -1)。u 树的先根、后根遍历过程与算法。T1 T2 T3AFHT1 T2 T3ABC DGIJEKFBCDEGHIKJABCEDHIKJFG3 棵树的森林各棵树的二叉树表示森林的二叉树表示 霍夫曼树与霍夫曼编码u 霍夫曼树的构造方法。u 霍夫曼编码的构造方法。u 霍夫曼树带权路径长度(霍夫曼编码长度)的计算。 构造霍夫曼树时权大的离根最近,权小的离根最远。 根的权值相同时,新构造出来的树的根一般位于右边。但若用“堆”存储各树的根结点,则要看它们在堆中调整的结果来定哪一个做左子树。6128242461286*:2461286*2461286*1
10、2*2012*2461286*12*2032 堆u 堆的定义:顺序存储的关键码集合。u 堆的插入与删除。 形成堆时用到的向下调整算法。 堆插入时用到的向上调整算法。 堆的插入与删除算法。第七章 集合与搜索n理解和掌握u 顺序搜索u 折半搜索u 二叉搜索树u AVL树 n需要掌握的知识点 顺序搜索u 顺序搜索的过程u 顺序搜索的平均搜索长度ASL 搜索成功时无序表与有序表的ASL ASL = (n+1)/2 搜索不成功时无序表的ASL = n+1 搜索不成功时有序表的ASL n1iin1n1ASL 有序表的折半搜索u 折半搜索的过程u 折半搜索的平均搜索长度 搜索成功时的平均搜索长度ASL 元素
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 电子 教案
限制150内