数据结构与常用算法.ppt

数据结构 　与常用算法 什么是程序? 程序(Programming) 数据结构(Data Structure) 算法(Algorithm) Programming = Data Structure + Algorithm 什么是数据结构 数据(data) 是对客观事物的符号的表示。例如数值、图像、声音都属于数据的范畴。 数据元素(data element) 是数据的基本单位 数据对象（data object）是性质相同的数据元素的集合，是数据的一个子集。 数据结构（data structure）是相互之间存在一种或多种特定关系的数据元素的集合。 人员卡片表 红楼梦贾家谱系 多叉路口交通灯的管理 。 数据结构的内涵 数据结构的含义 数据 关系 操作 例子：数组 数据：a[1], a[2], …, a[n] 关系：前驱/后继 操作：随机存取，插入，删除… 数据结构为算法服务 根据算法对数据的操作要求，设计合适的数据结构 实现同一套操作，可以用多种数据结构 如何降低时空复杂度，又方便实现？ 逻辑结构 数据元素之间是逻辑关系 抽象数据类型没有办法转化成程序 需要设计逻辑结构！ 所有电话记录形成线性结构，记录的顺序无要求 无序线性表 有了逻辑结构，可以设计算法 插入：直接插到表的头部或者尾部 删除：直接删除，再把两段合并在一起 查找：从头开始沿着表找一遍 这个算法仍然不能转化成程序 甚至无法进行复杂度分析！ 物理结构(存储结构) 数据结构在计算机中的存储方式 顺序结构：借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系。 逻辑上关联的数据元素，物理存储结构中相邻。 链式结构 ：借助元素存储地址的指针(pointer）表示数据元素之间的逻辑关系 。 逻辑上关联的数据元素，物理存储结构中不一定相邻。 抽象数据类型(ADT) ADT包括数据数据元素，数据关系以及相关的操作数据对象 算法对数据结构的要求 维护一个电话薄，方便进行插入删除和查找 操作：插入，删除，查找 如何实现？ 算法不关心！ 只要提供这些操作都可以！ 抽象数据类型：集合 如何学习数据结构 了解常见的抽象数据类型 对每种ADT，了解常见的逻辑结构 设计逻辑结构是最难的！ 对给定的逻辑结构，自己设计物理结构 物理结构一般只是数组和链结构 数组可以随机访问（设计下标计算公式） 经典例子：哈希表，二叉堆，并查集，线段树 链结构应该根据元素间关系（链接）进行“移动” 经典例子：伸展树，二项堆，跳跃表 *特殊算法需要自己归纳出ADT并设计逻辑结构 PQ树，后缀树 入门学什么？ 线性表 栈和队列 串：匹配 二叉树、树 图 *基本检索算法 *基本排序算法 线性表 线性表的表示 顺序存储结构 用数组类型： list: array [1..max] of elemtp ; 链式存储结构 用指针类型： point = p_list ^ ; p_list = record elm : elemtp ; link : point ; end; 无序线性表操作 物理结构：数组 插入：插到尾部比较方便，O(1) 删除：“合并两半”导致元素移动，最坏O(n) 查找：最坏O(n) 物理结构：链表 插入：插到头部比较方便，O(1) 删除：找到位置后O(1) 查找：最坏O(n) 不同的物理结构，得到不同的效果！ 有序线性表操作 物理结构：数组 插入最坏O(n) 删除最坏O(n) 查找最坏O(logn)：二分查找 物理结构：链表 插入（找到后）最坏O(1) 删除（找到后）最坏O(1) 查找最坏O(n)，平均n/2 比较一下 线性表及其基本运算 例：求两个集合的并,即A=A∪B 分析：设A、B分别由两个线性表LA和LB表示， 要求: 将LB中存在而LA中不存在的DE插入到表LA中。 线性表及其基本运算 形式化算法描述（类PASCAL）： PROC union(VAR LA:Linear_list； LB:Linear_list)； {将所有在LB中存在而LA中不存在的DE插入到LA中去} n:=LENGTH(LA)； {确定线性表LA的长度} FOR i:=1 TO LENGTH(LB) DO [ x:=GET(LB,i)； {取LB中第i个数据元素} k:=LOCATE(LA,x)； {在LA中进行有哪些信誉好的足球投注网站} IF k=0 THEN [ INSERT(LA,n+1,x)；{在LA表尾插入} n:=n+1 {表长加1} ] ] ENDP； {union} 线性表的典型实例 约瑟夫问题 M个人围成一圈，从