数据结构复习题课件.ppt

1、 概述概述 模块模块1：线性结构：线性结构 模块模块2：树型结构：树型结构 模块模块3：图型结构：图型结构 模块模块4：其他：其他数据结构复习数据结构复习1.1.数据结构的定义数据结构的定义 数据数据数据元素数据元素数据项数据项 数据结构是指数据以及相互之间的联系（或数据结构是指数据以及相互之间的联系（或关系）。包括：关系）。包括：（1）数据的逻辑结构。）数据的逻辑结构。（2）数据的存储结构（物理结构）。）数据的存储结构（物理结构）。（3）施加在该数据上的运算。）施加在该数据上的运算。概述概述 数据的逻辑结构数据的逻辑结构是从逻辑关系上描述数据，它是从逻辑关系上描述数据，它与数据的存储无关，是

2、独立于计算机的。与数据的存储无关，是独立于计算机的。数据的存储结构数据的存储结构是逻辑结构用计算机语言的实是逻辑结构用计算机语言的实现（亦称为映象），它是依赖于计算机语言的。现（亦称为映象），它是依赖于计算机语言的。数据的运算数据的运算是定义在数据的逻辑结构上的，每是定义在数据的逻辑结构上的，每种逻辑结构都有一组相应的运算。但运算的实现与种逻辑结构都有一组相应的运算。但运算的实现与数据的存储结构有关。数据的存储结构有关。程序数据结构算法程序数据结构算法概述概述（1）线性结构）线性结构（2）树形结构）树形结构（3）图形结构）图形结构概述概述逻辑结构主要有三大类：逻辑结构主要有三大类：存储结构分为

3、如下四种：存储结构分为如下四种：（1）顺序存储方法）顺序存储方法（2）链式存储方法）链式存储方法（3）索引存储方法）索引存储方法（4）散列存储方法）散列存储方法 概述概述2.算法算法 算法是对特定问题求解步骤的一种描算法是对特定问题求解步骤的一种描述，它是指令的有限序列。述，它是指令的有限序列。概述概述算法的五个重要的特性算法的五个重要的特性：（1）有穷性）有穷性（2）确定性）确定性（3）可行性）可行性（4）有输入）有输入（5）有输出）有输出 概述概述 算法的时间复杂度：是指其基本运算在算算法的时间复杂度：是指其基本运算在算法中重复执行的次数。法中重复执行的次数。算法中基本运算次数算法中基本运

4、算次数T(n)是问题规模是问题规模n的某的某个函数个函数f(n)，记作：，记作：T(n)=O(f(n)记号记号“O”读作读作“大大O”，它表示随问题规，它表示随问题规模模n的增大算法执行时间的增长率和的增大算法执行时间的增长率和f(n)的增长的增长率相同。率相同。概述概述例例 分析以下程序段的时间复杂度。分析以下程序段的时间复杂度。i=1;while(ilchild)+f(b-rchild)+1 bNULL概述概述 递归算法设计递归算法设计 对原问题对原问题f(s)进行分析，假设出合理的进行分析，假设出合理的“较小问题较小问题”f(s);假设假设f(s)是可解的，在此基础上确定是可解的，在此基

5、础上确定f(s)的解，即给出的解，即给出f(s)与与f(s)之间的关系；之间的关系；确定一个特定情况（如确定一个特定情况（如f(1)或或f(0)）的）的解，由此作为递归出口解，由此作为递归出口.概述概述bb-rchildb-lchild 假设出合理的假设出合理的“较小问题较小问题”：假设左右子树的结点个数可求假设左右子树的结点个数可求 求出求出f(s)与与f(s)之间的关系：之间的关系：f(b)=f(b-lchild)+f(b-rchild)+1 确定递归出口：确定递归出口：f(NULL)=0概述概述int f(BTNode*b)if(b=NULL)return(0);else return(

6、f(b-lchild)+f(b-rchild)+1);求解算法：求解算法：概述概述例、假设非空二叉树例、假设非空二叉树bt采用二叉链存储，其中所有节点采用二叉链存储，其中所有节点数据域为正整数，设计一个递归算法求其中的最大值。数据域为正整数，设计一个递归算法求其中的最大值。递归模型如下：递归模型如下：f(bt)=0 若若bt为空为空 f(bt)=bt-data 若若bt是叶子节点是叶子节点f(bt)=MAX3(bt-data,f(bt-lchild),f(bt-rchild)其他情况其他情况int f(BTNode*bt)int m,n;if(bt=NULL)return 0;if(bt-lc

7、hild=NULL&bt-rchild=NULL)return bt-data;else m=f(bt-lchild);/求左子树中的最大值求左子树中的最大值n=f(bt-rchild);/求右子树中的最大值求右子树中的最大值if(mbt-data)return m;else return bt-data;例例 设计求设计求f(n)=1+2+.+n的递归算法的递归算法解：解：f(n)为前为前n项之和，则项之和，则f(n-1)=1+2+.+(n-1)假设假设f(n-1)可求，则可求，则f(n)=f(n-1)+n，所以：，所以：f(n)=1 当当n=1f(n)=f(n-1)+n 当当n1对应的递归

8、算法如下：对应的递归算法如下：int f(int n)if(n=1)return(1);else return(f(n-1)+n);1.1.一般线性表一般线性表 线性表：具有相同特性的数据元素的一个线性表：具有相同特性的数据元素的一个有限序列。不是集合。有限序列。不是集合。元素之间是一对一的关系。元素之间是一对一的关系。模块模块1 1：线性结构：线性结构逻辑结构逻辑结构（1）顺序表）顺序表 typedef struct ElemType elemMaxSize;/*存放顺序表元素存放顺序表元素*/int length;/*存放顺序表的长度存放顺序表的长度*/SqList;存储结构之一存储结构之

9、一模块模块1 1：线性：线性结构结构顺序表基本运算的实现顺序表基本运算的实现 插入数据元素算法：元素移动的次数不仅与表插入数据元素算法：元素移动的次数不仅与表长长n有关有关；插入一个元素时所需移动元素的平均次；插入一个元素时所需移动元素的平均次数数 n/2。平均时间复杂度为。平均时间复杂度为O(n)。模块模块1 1：线性：线性结构结构删除数据元素算法删除数据元素算法:元素移动的次数也与元素移动的次数也与表长表长n有关有关。删除一个元素时所需移动元素的。删除一个元素时所需移动元素的平均次数为平均次数为(n-1)/2。删除算法的平均时间复杂。删除算法的平均时间复杂度为度为O(n)。模块模块1 1：

10、线性结构：线性结构 例、在一个长度为例、在一个长度为n的顺序表中删除第的顺序表中删除第i个元素（个元素（1in）时，需向前移动时，需向前移动 个元素。个元素。A.nB.i-1C.n-iD.n-i+1例、设线性表有例、设线性表有n个元素，以下操作中，个元素，以下操作中，在顺序表上在顺序表上实现比在链表上实现效率更高。实现比在链表上实现效率更高。A.输出第输出第i（1in）个元素值）个元素值B.交换第交换第1个元素与第个元素与第2个元素的值个元素的值C.顺序输出这顺序输出这n个元素的值个元素的值D.输出与给定值输出与给定值x相等的元素在线性表中的序号相等的元素在线性表中的序号例已知长度为例已知长度

11、为n的线性表的线性表L采用顺序存储结构，试设计采用顺序存储结构，试设计一个在时间和空间两方面都尽可能高效的算法，删除其中所一个在时间和空间两方面都尽可能高效的算法，删除其中所有元素值在有元素值在x,y之间的所有元素。之间的所有元素。解法一：解法一：对应的算法如下：对应的算法如下：void delxy1(SqList&L,ElemType x,ElemType y)int k=0,i;/k记录不满足条件的元素个数记录不满足条件的元素个数 for(i=0;i=x&L.datai=y)L.datak=L.datai;k+;/不满足条件的元素个数增不满足条件的元素个数增1L.length=k;/顺序表

12、顺序表L的长度等于的长度等于k解法二解法二：对应的算法如下：对应的算法如下：void delnode2(SqList&L,ElemType x,ElemType y)int k=0,i=0;/k记录满足条件的元素个数记录满足条件的元素个数 while(i=x&L.datainext=NULL;for(i=0;idata=ai;s-next=L-next;/*将将*s插在原开始结点之前插在原开始结点之前,头结点之后头结点之后*/L-next=s;模块模块1 1：线性结构：线性结构 尾插法建表尾插法建表 头插法建立链表虽然算法简单头插法建立链表虽然算法简单,但生成的链表但生成的链表中结点的次序和原

13、数组元素的顺序相反。若希望中结点的次序和原数组元素的顺序相反。若希望两者次序一致两者次序一致,可采用尾插法建立。该方法是将可采用尾插法建立。该方法是将新结点插到当前链表的表尾上新结点插到当前链表的表尾上,为此必须增加一为此必须增加一个尾指针个尾指针r,r,使其始终指向当前链表的尾结点。使其始终指向当前链表的尾结点。采用尾插法建表的算法如下采用尾插法建表的算法如下:模块模块1 1：线性结构：线性结构 void CreateListR(LinkList*&L,ElemType a,int n)LinkList*s,*r;int i;L=(LinkList*)malloc(sizeof(LinkLi

14、st);/*创建头结点创建头结点*/r=L;/*r始终指向终端结点始终指向终端结点,开始时指向头结点开始时指向头结点*/for(i=0;idata=ai;r-next=s;/*将将*s插入插入*r之后之后*/r=s;r-next=NULL;/*终端结点终端结点next域置为域置为NULL*/例、设一个整数线性表采用带头节点的例、设一个整数线性表采用带头节点的hc单链表存放，设单链表存放，设计一个算法在不破坏原有单链表的前提下，创建两个单链表计一个算法在不破坏原有单链表的前提下，创建两个单链表ha和和hb，前者由，前者由hc中值为奇数的节点构成，后者由中值为奇数的节点构成，后者由hc中值为偶数中

15、值为偶数的节点构成。的节点构成。void split(LinkList*hc,LinkList*&ha,LinkList*&hb)LinkList*p=hc-next,*ra,*rb,*s;ha=(LinkList*)malloc(sizeof(LinkList);ra=ha;hb=(LinkList*)malloc(sizeof(LinkList);rb=hb;while(p!=NULL)if(p-data%2=1)/奇数节点奇数节点 s=(LinkList*)malloc(sizeof(LinkList);s-data=p-data;/复制产生节点复制产生节点*s ra-next=s;/将

16、将*s节点链接到节点链接到ha尾部尾部 ra=s;else/偶数节点偶数节点 s=(LinkList*)malloc(sizeof(LinkList);s-data=p-data;/复制产生节点复制产生节点*s rb-next=s;/将将*s节点链接到节点链接到hb尾部尾部 rb=s;p=p-next;ra-next=rb-next=NULL;/两链表尾节点两链表尾节点next均置为均置为NULL 双链表基本运算的实现双链表基本运算的实现 重点：重点：插入和删除结点的算法。插入和删除结点的算法。模块模块1 1：线性结构：线性结构 循环链表基本运算的实现循环链表基本运算的实现 重点：重点：判断最

17、后一个结点。判断最后一个结点。模块模块1 1：线性结构：线性结构2.栈栈（1）栈的定义）栈的定义 栈是一种栈是一种先进后出先进后出表。插入删除受限的线表。插入删除受限的线性表。性表。栈的基本运算栈的基本运算:进栈，出栈。进栈，出栈。逻辑结构逻辑结构模块模块1 1：线性结构：线性结构（2）顺序栈）顺序栈typedef struct ElemType dataMaxSize;int top;/*栈顶指针栈顶指针*/SqStack;存储结构之一存储结构之一模块模块1 1：线性结构：线性结构栈空条件栈空条件:s.top=-1栈满条件栈满条件:s.top=MaxSize-1进栈进栈:top+;s.dat

18、as.top=e;出栈出栈:e=s.datas.top;s.top;顺序栈的顺序栈的4要素要素:模块模块1 1：线性结构：线性结构（3）链栈）链栈 typedef struct linknode ElemType data;/*数据域数据域*/struct linknode*next;/*指针域指针域*/LiStack;存储结构之二存储结构之二模块模块1 1：线性结构：线性结构带头结点的单链表来实现带头结点的单链表来实现(也可不带头结点也可不带头结点)lhead a1 an a2 栈底结点 栈顶结点 头结点 栈空条件栈空条件:s-next=NULL 栈满条件栈满条件:?模块模块1 1：线性结构

19、：线性结构3.队列队列（1）队列的定义队列的定义 队列是一种队列是一种先进先出先进先出表。插入删除受限的表。插入删除受限的线性表。线性表。队列的基本运算队列的基本运算:进队进队,出队出队逻辑结构逻辑结构模块模块1 1：线性结构：线性结构（2）顺序队顺序队typedef struct ElemType dataMaxSize；int front,rear；/*队首和队尾指针队首和队尾指针*/SqQueue；存储结构之一存储结构之一模块模块1 1：线性结构：线性结构队空队空:q.front=q.rear队满队满:(q.rear+1)%MaxSize=q.front进队进队:q.rear=(q.re

20、ar+1)MaxSize;q.dataq.rear=e;出队出队:q.front=(q.front+1)MaxSize;e=q.dataq.front;环形队列的环形队列的4要素要素:模块模块1 1：线性结构：线性结构（3）链队）链队struct qnode /*数据结点数据结点*/ElemType data;struct qnode*next;QNode;typedef struct /*头结点头结点*/QNode*front;QNode*rear;LiQueue;存储结构之二存储结构之二模块模块1 1：线性结构：线性结构（2）顺序串）顺序串 （3）链串）链串 （4）串串的模式匹配算法：的模

21、式匹配算法：BF、KMP4.4.串串（1）串的定义）串的定义 串、子串、串相等、空串、空格串串、子串、串相等、空串、空格串模块模块1 1：线性结构：线性结构5.数组和稀疏矩阵数组和稀疏矩阵（1）数组的定义）数组的定义 相同类型数据元素、有限序列相同类型数据元素、有限序列模块模块1 1：线性结构：线性结构（2）数组的存储结构数组的存储结构 以行序为主序以行序为主序:LOC(ai,j)=LOC(ac1,c2)+(i-c1)*(d2-c2+1)+(j-c2)*k 以列序为主序以列序为主序 LOC(ai,j)=LOC(ac1,c2)+(j-c2)*(d1-c1+1)+(i-c1)*k 以数组以数组Ac

22、1.d1,c2.d2 为例为例模块模块1 1：线性结构：线性结构（3）特殊矩阵的压缩存储）特殊矩阵的压缩存储 对称矩阵对称矩阵 若一个若一个n阶方阵阶方阵Ann中的元素满足中的元素满足ai,j=aj,i（0i，jn-1），则称其为），则称其为n阶对称矩阵。阶对称矩阵。A0.n-10.n-1 B0.n(n+1)/2 i(i+1)/2+j 当当ij时时k=j(j+1)/2+i 当当ij时时 模块模块1 1：线性结构：线性结构 三角矩阵三角矩阵 采用类似的压缩方法采用类似的压缩方法.模块模块1 1：线性结构：线性结构（4）稀疏矩阵）稀疏矩阵 存储结构：存储结构：三元组表示三元组表示 十字链表表示十字

23、链表表示 各种表示的基本思路。各种表示的基本思路。非零元素远小于元素总数。非零元素远小于元素总数。模块模块1 1：线性结构：线性结构 一个广义表中所含元素的个数称为它的长一个广义表中所含元素的个数称为它的长度度.6.广义表广义表GL=(a,(a),(a,b,c,d),()长度为长度为4。模块模块1 1：线性结构：线性结构 一个广义表中括号嵌套的最大次数为它一个广义表中括号嵌套的最大次数为它的深度的深度.GL=(a,(a),(a,b,c,d),()深度为深度为2。模块模块1 1：线性结构：线性结构 表的第一个元素表的第一个元素a1为广义表为广义表GL的表头，的表头，其余部分其余部分(a2，ai，

24、ai+1，an)为为GL的表的表尾尾.GL=(a,(a),(a,b,c,d),()表头为表头为a，表尾为，表尾为(a),(a,b,c,d),()模块模块1 1：线性结构：线性结构模块模块2：树形结构：树形结构 （1）树的定义）树的定义 递归定义递归定义 适合于表示层次结构的数据适合于表示层次结构的数据 1.1.树树（2）树的表示法（逻辑表示方法）树的表示法（逻辑表示方法）树形表示法树形表示法 文氏图表示法文氏图表示法 凹入表示法凹入表示法 括号表示法括号表示法 模块模块2：树形结构：树形结构 （3）树的遍历）树的遍历 先根遍历算法先根遍历算法 后根遍历算法后根遍历算法模块模块2：树形结构：树形

25、结构 （4）树和二叉树的相互转换）树和二叉树的相互转换 树树 二叉树二叉树 二叉二叉树树 树树模块模块2：树形结构：树形结构 2.二叉树二叉树 （1）二叉树的定义）二叉树的定义 根、左子树、右子树根、左子树、右子树 完全二叉树完全二叉树,满二叉树的定义满二叉树的定义模块模块2：树形结构：树形结构 性质性质1 非空二叉树上叶结点数等于双分支结点数非空二叉树上叶结点数等于双分支结点数加加1。即。即n0=n2+1.性质性质2 非空二叉树上第非空二叉树上第i层上至多有层上至多有2i-1个结点个结点（i1）。）。（2）二叉树性质）二叉树性质模块模块2：树形结构：树形结构 性质性质3 高度为高度为h的二叉

26、树至多有的二叉树至多有2h-1个结点个结点（h1）。性质性质4 完全二叉树的性质完全二叉树的性质。性质性质5 具有具有n个（个（n0）结点的完全二叉树）结点的完全二叉树的高度为的高度为 log2(n+1)或或 log2n+1。（2）二叉树性质）二叉树性质模块模块2：树形结构：树形结构 例、将一棵有例、将一棵有98个结点的完全二叉树从根这一个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根层开始，每一层从左到右依次对结点进行编号，根结点的编号为结点的编号为1，则编号为，则编号为49的结点的右孩子编号的结点的右孩子编号为为 。A.98 B.99 C.50 D.不存在不存在模块模

27、块2：树形结构：树形结构 例例 深度为深度为5的二叉树至多有的二叉树至多有 个结点。个结点。A.16 B.32 C.31 D.10 答：相同满度时满二叉树结点最多，答：相同满度时满二叉树结点最多，h=5的满二叉树结点个数的满二叉树结点个数=25-1=31。C。模块模块2：树形结构：树形结构 （3）二叉树存储结构）二叉树存储结构 二叉树的顺序存储结构二叉树的顺序存储结构 模块模块2：树形结构：树形结构 ABCDEF1234567891011121314ABCDEFi2i2i+1左孩子左孩子右孩子右孩子 二叉链存储结构二叉链存储结构 typedef struct node ElemType dat

28、a;/*数据元素数据元素*/struct node*lchild;/*指向左孩子指向左孩子*/struct node*rchild;/*指向右孩子指向右孩子*/BTNode;ABC左孩子左孩子右孩子右孩子（4）二叉树的遍历）二叉树的遍历 先序遍历先序遍历 中序遍历中序遍历 后序遍历后序遍历 层次遍历层次遍历通常用递归算法实现通常用递归算法实现模块模块2：树形结构：树形结构 例、若二叉树的中序遍历序列是例、若二叉树的中序遍历序列是abcdef，且，且c为根节点，为根节点，则则 。A.节点节点c有两个孩子有两个孩子B.二叉树有两个度为二叉树有两个度为0的节点的节点C.二叉树的高度为二叉树的高度为5

29、D.以上都不对以上都不对例、例、的先序序列和后序序列正好相反。的先序序列和后序序列正好相反。A.二叉排序树二叉排序树B.3个节点的二叉树个节点的二叉树C.平衡二叉树平衡二叉树D.无右孩子的二叉树无右孩子的二叉树例、在任何一棵二叉树中，如果节点例、在任何一棵二叉树中，如果节点a有左孩子有左孩子b、右孩、右孩子子c，则在节点的先序序列、中序序列、后序序列中，则在节点的先序序列、中序序列、后序序列中，。A.节点节点b一定在节点一定在节点a的前面的前面B.节点节点a一定在节点一定在节点c的前面的前面C.节点节点b一定在节点一定在节点c的前面的前面D.节点节点a一定在节点一定在节点b的前面的前面例、设例

30、、设n、m为一棵二叉树上的两个节点，在中序遍历时，为一棵二叉树上的两个节点，在中序遍历时，n在在m前的条件是前的条件是 。A.n在在m右方右方B.n是是m祖先祖先C.n在在m左方左方D.n是是m子孙子孙 例、假设二叉树采用二叉链存储结构存储，试设计一个算例、假设二叉树采用二叉链存储结构存储，试设计一个算法，输出一棵给定二叉树的所有叶子结点。法，输出一棵给定二叉树的所有叶子结点。解：输出一棵二叉树的所有叶子结点的递归模型解：输出一棵二叉树的所有叶子结点的递归模型f()如下：如下：f(b)：不做任何事件：不做任何事件 若若b=NULL f(b)：输出：输出*b结点的结点的data域域 若若*b为叶

31、子结点为叶子结点 f(b)：f(b-lchild);f(b-rchild)其他情况其他情况模块模块2：树形结构：树形结构 void DispLeaf(BTNode*b)if(b!=NULL)if(b-lchild=NULL&b-rchild=NULL)printf(%c,b-data);DispLeaf(b-lchild);DispLeaf(b-rchild);模块模块2：树形结构：树形结构 先序遍历先序遍历思想思想2.哈夫曼树哈夫曼树（1）哈夫曼树的定义哈夫曼树的定义WPL最小，没有单分支结点即最小，没有单分支结点即n1=0模块模块2：树形结构：树形结构 （2）哈夫曼树的构造过程）哈夫曼树的

32、构造过程（3）哈夫曼编码的构造过程）哈夫曼编码的构造过程模块模块2：树形结构：树形结构 例、设哈夫曼编码的长度不超过例、设哈夫曼编码的长度不超过4，若已经对两个字符编码，若已经对两个字符编码为为1和和01，则最多还可以对，则最多还可以对 个字符编码。个字符编码。A.2B.3C.4D.5 顶点的度、入度和出度顶点的度、入度和出度 完全图完全图 子图子图 路径和路径长度路径和路径长度 连通、连通图和连通分量连通、连通图和连通分量 强连通图和强连通分量强连通图和强连通分量 权和网权和网 模块模块3：图形结构：图形结构（1）图的基本概念）图的基本概念（2）图的存储结构）图的存储结构 邻接矩阵存储方法邻

33、接矩阵存储方法 掌握两种存储方法的优缺点，同一种功掌握两种存储方法的优缺点，同一种功能在不同存储结构上的实现算法。能在不同存储结构上的实现算法。邻接表存储方法邻接表存储方法模块模块3：图形结构：图形结构（3）图的遍历）图的遍历 深度优先搜索遍历深度优先搜索遍历 离初始点越远越优先访问。离初始点越远越优先访问。1267354访问序列：访问序列：1，2，3，4，5，6，7模块模块3：图形结构：图形结构void DFS(ALGraph*G,int v)ArcNode*p;Visitedv=1;/*置已访问标记置已访问标记*/printf(%d ,v);/*输出被访问顶点的编号输出被访问顶点的编号*/

34、p=G-adjlistv.firstarc;while(p!=NULL)if(visitedp-adjvex=0)DFS(G,p-adjvex);p=p-nextarc;模块模块3：图形结构：图形结构1267354 广度优先搜索遍历广度优先搜索遍历 离初始点越近越优先访问。离初始点越近越优先访问。访问序列：访问序列：1，2，6，7，3，5，4模块模块3：图形结构：图形结构 void BFS(ALGraph*G,int v)ArcNode*p;int queueMAXV,front=0,rear=0;int visitedMAXV;int w,i;for(i=0;in;i+)visitedi=0

35、;printf(%2d,v);visitedv=1;/*置已访问标记置已访问标记*/rear=(rear+1)%MAXV;queuerear=v;/*v进队进队*/模块模块3：图形结构：图形结构 while(front!=rear)/*若队列不空时循环若队列不空时循环*/front=(front+1)%MAXV;w=queuefront;/*出队并赋给出队并赋给w*/p=G-adjlistw.firstarc;while(p!=NULL)if(visitedp-adjvex=0)printf(%2d,p-adjvex);visitedp-adjvex=1;rear=(rear+1)%MAXV;

36、queuerear=p-adjvex;p=p-nextarc;模块模块3：图形结构：图形结构（4）最小生成树）最小生成树 普里姆算法普里姆算法 给定起始点；给定起始点；算法过程；算法过程；O(n2)模块模块3：图形结构：图形结构 克鲁斯卡尔算法克鲁斯卡尔算法 不给定起始点；不给定起始点；算法过程；算法过程；O(elog2e)模块模块3：图形结构：图形结构（5）最短路径）最短路径 狄克斯特拉算法过程狄克斯特拉算法过程 弗洛伊德算法过程弗洛伊德算法过程模块模块3：图形结构：图形结构（1）线性表的查找）线性表的查找模块模块4：其他：其他1.1.查找查找 在顺序表上进行。方法有：在顺序表上进行。方法有

37、：顺序查找顺序查找（过程和算法）（过程和算法）二分查找二分查找（过程和算法）（过程和算法）分块查找分块查找(过程过程)（2）树表的查找树表的查找 二叉排序树二叉排序树 定义定义 查找（过程和算法）查找（过程和算法）插入和删除（过程）插入和删除（过程）与堆的区别与堆的区别模块模块4：其他：其他性质：二叉排序树的中序序列是一个有序序列性质：二叉排序树的中序序列是一个有序序列 平衡二叉树平衡二叉树 定义定义 查找（过程和算法）查找（过程和算法）调整（过程）调整（过程）模块模块4：其他：其他（3）哈希表查找哈希表查找 哈希函数哈希函数主要有除留余数法。主要有除留余数法。哈希冲突解决方法哈希冲突解决方法

38、 主要有线性探查法、拉链法主要有线性探查法、拉链法模块模块4：其他：其他 插入排序插入排序 （1）直接插入排序）直接插入排序（2）希尔排序）希尔排序模块模块4：其他：其他 交换排序交换排序 （1）冒泡排序）冒泡排序（2）快速排序）快速排序 选择排序选择排序 （1）简单选择排序）简单选择排序（2）堆排序）堆排序 归并排序归并排序 基数排序基数排序 例、在待排序的元素序列基本有序的前提下，效率最例、在待排序的元素序列基本有序的前提下，效率最高的排序方法是高的排序方法是 。A.直接插入排序直接插入排序B.选择排序选择排序C.快速排序快速排序D.归并排序归并排序 例例 快速排序在最坏情况下时间复杂度是

39、快速排序在最坏情况下时间复杂度是O(n2)，比，比 的的性能差。性能差。A.堆排序堆排序B.冒泡排序冒泡排序C.直接选择排序直接选择排序 D.直接插入排序直接插入排序强调各种排序方法的比较强调各种排序方法的比较是否需要比较是否需要比较排序方法的区别排序方法的区别时间复杂度时间复杂度空间复杂度空间复杂度外排序的过程。外排序的过程。磁盘排序：置换选择算法、败者树、最佳平衡归并树。磁盘排序：置换选择算法、败者树、最佳平衡归并树。学习数据结构对于求解问题的思路。学习数据结构对于求解问题的思路。学习数据结构课程的几点提示学习数据结构课程的几点提示注重算法的关联性。如较高效算法是如何提高效率的，注重算法的

40、关联性。如较高效算法是如何提高效率的，如何从问题中找出如何从问题中找出“启发启发”信息的？信息的？顺序查找算法顺序查找算法二分查找算法二分查找算法利用了数据的有序性利用了数据的有序性示例示例1串简单匹配算法串简单匹配算法串串KMP匹配算法匹配算法利用子串中部分匹配特性利用子串中部分匹配特性示例示例2简单选择排序算法简单选择排序算法堆选择排序算法堆选择排序算法利用了连续多次查找最大记录的特性利用了连续多次查找最大记录的特性示例示例3算法的作用。一些复杂的问题的基础可能就是一个算法的作用。一些复杂的问题的基础可能就是一个“简简单单”的算法。的算法。示例：机器人规划问题示例：机器人规划问题AB找路径：找路径：ABABAB 膨胀所有物体。膨胀所有物体。将路径搜索转换为图将路径搜索转换为图的顶点搜索。的顶点搜索。