《数据结构教程》PPT课件.ppt

《《数据结构教程》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《数据结构教程》PPT课件.ppt（88页珍藏版）》请在三一办公上搜索。

1、概述模块1：线性表模块2：树型结构模块3：图型结构模块4：其他,1.数据结构的定义,数据数据元素数据项,数据结构是指数据以及相互之间的联系（或关系）。包括：（1）数据的逻辑结构。（2）数据的存储结构（物理结构）。（3）施加在该数据上的运算。,概述,数据的逻辑结构是从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。数据的存储结构是逻辑结构用计算机语言的实现（亦称为映象），它是依赖于计算机语言的。数据的运算是定义在数据的逻辑结构上的，每种逻辑结构都有一组相应的运算。但运算的实现与数据的存储结构有关。,程序数据结构算法,概述,（1）线性结构（2）树形结构（3）图形结构,概述,逻辑结构主要有

2、三大类：,存储结构分为如下四种：,（1）顺序存储方法（2）链式存储方法（3）索引存储方法（4）散列存储方法,概述,2.算法,算法是对特定问题求解步骤的一种描述，它是指令的有限序列。,概述,算法的五个重要的特性：（1）有穷性（2）确定性（3）可行性（4）有输入（5）有输出,概述,算法的时间复杂度：是指其基本运算在算法中重复执行的次数。,算法中基本运算次数T(n)是问题规模n的某个函数f(n)，记作：T(n)=O(f(n)记号“O”读作“大O”，它表示随问题规模n的增大算法执行时间的增长率和f(n)的增长率相同。,概述,例 分析以下程序段的时间复杂度。i=1;while(i=n)i=i*2;,解：

3、上述算法中基本操作是语句i=i*2，设其频度为T(n)，则有：2T(n)n即T(n)log2n=O(log2n)。所以，该程序段的时间复杂度为O(log2n)。,算法空间复杂度：是对一个算法在运行过程中临时占用的存储空间大小的量度。,对于空间复杂度为O(1)的算法称为原地工作或就地工作算法。,概述,递归定义,3.算法设计方法：递归,在定义一个算法时出现调用本算法的成分，称之为递归。,概述,递归模型,由递归出口和递归体组成,例如，求二叉树所有结点个数：f(b)=0 b=NULLf(b)=f(b-lchild)+f(b-rchild)+1 bNULL,概述,递归算法设计,对原问题f(s)进行分析，

4、假设出合理的“较小问题”f(s);假设f(s)是可解的，在此基础上确定f(s)的解，即给出f(s)与f(s)之间的关系；确定一个特定情况（如f(1)或f(0)）的解，由此作为递归出口.,概述,b,b-rchild,b-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(f(b-lchild)+f(b-rchild)+1);,求解算法：,概述,例 设计求

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

6、放顺序表的长度*/SqList;,存储结构之一,模块1：线性结构,顺序表基本运算的实现,插入数据元素算法：元素移动的次数不仅与表长n有关；插入一个元素时所需移动元素的平均次数 n2。平均时间复杂度为O(n)。,模块1：线性结构,删除数据元素算法:元素移动的次数也与表长n有关。删除一个元素时所需移动元素的平均次数为(n-1)/2。删除算法的平均时间复杂度为O(n)。,模块1：线性结构,（2）链表,定义单链表结点类型:typedef struct LNode ElemType data;struct LNode*next;/*指向后继结点*/LinkList;,存储结构之二,模块1：线性结构,定义

7、双链表结点类型:typedef struct DNode ElemType data;struct DNode*prior;/*指向前驱结点*/struct DNode*next;/*指向后继结点*/DLinkList;,模块1：线性结构,单链表基本运算的实现,重点：（1）头插法建表和尾插法建表算法，它是很多算法设计的基础；（2）查找、插入和删除操作。,模块1：线性结构,头插法建表 该方法从一个空表开始,读取字符数组a中的字符,生成新结点,将读取的数据存放到新结点的数据域中,然后将新结点插入到当前链表的表头上,直到结束为止。采用头插法建表的算法如下:,模块1：线性结构,void CreateL

8、istF(LinkList*,模块1：线性结构,尾插法建表 头插法建立链表虽然算法简单,但生成的链表中结点的次序和原数组元素的顺序相反。若希望两者次序一致,可采用尾插法建立。该方法是将新结点插到当前链表的表尾上,为此必须增加一个尾指针r,使其始终指向当前链表的尾结点。采用尾插法建表的算法如下:,模块1：线性结构,void CreateListR(LinkList*/*终端结点next域置为NULL*/,双链表基本运算的实现,重点：插入和删除结点的算法。,模块1：线性结构,循环链表基本运算的实现,重点：判断最后一个结点。,模块1：线性结构,例 设计一个算法在单链表中查找元素值为e的结点序号的算法

9、LocateElem(L,e)。,思路：在单链表L中从头开始找第1个值域与e相等的结点,若存在这样的结点,则返回位置,否则返回0。int LocateElem(LinkList*L,ElemType e)LinkList*p=L-next;int n=1;while(p!=NULL,2.栈(1)栈的定义 栈是一种先进后出表。插入删除受限的线性表。栈的基本运算:进栈，出栈。,逻辑结构,模块1：线性结构,（2）顺序栈,typedef struct ElemType elemMaxSize;int top;/*栈指针*/SqStack;,存储结构之一,模块1：线性结构,栈空条件:s.top=-1 栈

10、满条件:s.top=MaxSize-1 进栈:top+;s.datas.top=e;出栈:e=s.datas.top;s.top;,顺序栈的4要素:,模块1：线性结构,（3）链栈,typedef struct linknode ElemType data;/*数据域*/struct linknode*next;/*指针域*/LiStack;,存储结构之二,模块1：线性结构,带头结点的单链表来实现(也可不带头结点),栈空条件:s-next=NULL 栈满条件:?,模块1：线性结构,3.队列,(1)队列的定义 队列是一种先进先出表。插入删除受限的线性表。队列的基本运算:进队,出队,逻辑结构,模块1

11、：线性结构,（2）顺序队,typedef struct ElemType elemMaxSize；int front,rear；/*队首和队尾指针*/SqQueue；,存储结构之一,模块1：线性结构,队空:q.front=q.rear 队满:(q.rear+1)%MaxSize=q.front 进队:q.rear=(q.rear+1)MaxSize;q.dataq.rear=e;出队:q.front=(q.front+1)MaxSize;e=q.dataq.front;,环形队列的4要素:,模块1：线性结构,（3）链队,struct qnode/*数据结点*/ElemType data;str

12、uct qnode*next;QNode;typedef struct/*头结点*/QNode*front;QNode*rear;LiQueue;,存储结构之二,模块1：线性结构,（2）顺序串,（3）链串,（4）串的模式匹配算法（不作要求）,4.串（1）串的定义 串、子串、串相等、空串、空格串,模块1：线性结构,5.数组和稀疏矩阵(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)*

13、(d1-c1+1)+(i-c1)*k,以数组Ac1.d1,c2.d2 为例,模块1：线性结构,（3）特殊矩阵的压缩存储,对称矩阵 若一个n阶方阵Ann中的元素满足ai,j=aj,i（0i，jn-1），则称其为n阶对称矩阵。,A0.n-10.n-1 B0.n(n+1)/2,模块1：线性结构,三角矩阵,采用类似的压缩方法.,模块1：线性结构,（4）稀疏矩阵,存储结构：三元组表示 十字链表表示 各种表示的基本思路。,非零元素远小于元素总数。,模块1：线性结构,一个广义表中所含元素的个数称为它的长度.,6.广义表,GL=(a,(a),(a,b,c,d),()长度为4。,模块1：线性结构,一个广义表中括

14、号嵌套的最大次数为它的深度.,GL=(a,(a),(a,b,c,d),()深度为2。,模块1：线性结构,表的第一个元素a1为广义表GL的表头，其余部分(a2，ai，ai+1，an)为GL的表尾.,GL=(a,(a),(a,b,c,d),()表头为a，表尾为(a),(a,b,c,d),(),模块1：线性结构,模块2：树形结构,（1）树的定义 递归定义 适合于表示层次结构的数据,1.树,（2）树的表示法(逻辑表示方法),树形表示法 文氏图表示法 凹入表示法 括号表示法,模块2：树形结构,（3）树的遍历,先根遍历算法 后根遍历算法,模块2：树形结构,（4）树和二叉树的相互转换,树 二叉树 二叉树 树

15、,模块2：树形结构,2.二叉树,（1）二叉树的定义 根、左子树、右子树 完全二叉树,满二叉树的定义,模块2：树形结构,性质1 非空二叉树上叶结点数等于双分支结点数加1。即n0=n2+1.性质2 非空二叉树上第i层上至多有2i-1个结点（i1）。,（2）二叉树性质,模块2：树形结构,性质3 高度为h的二叉树至多有2h-1个结点（h1）。性质4 完全二叉树的性质。性质5 具有n个（n0）结点的完全二叉树的高度为log2n+1或log2n+1。,（2）二叉树性质,模块2：树形结构,例 将一棵有98个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点

16、的右孩子编号为。A.98 B.99 C.50 D.不存在,答：D,模块2：树形结构,例 深度为5的二叉树至多有 个结点。A.16 B.32 C.31 D.10,答：相同满度时满二叉树结点最多，h=5的满二叉树结点个数=25-1=31。C。,模块2：树形结构,（3）二叉树存储结构,二叉树的顺序存储结构,模块2：树形结构,A,B,C,D,E,F,i,2i,2i+1,左孩子,右孩子,二叉链存储结构 typedef struct node ElemType data;/*数据元素*/struct node*lchild;/*指向左孩子*/struct node*rchild;/*指向右孩子*/BTNo

17、de;,A,B,C,左孩子,右孩子,（4）二叉树的遍历,先序遍历 中序遍历 后序遍历,模块2：树形结构,例 假设二叉树采用二叉链存储结构存储,试设计一个算法,输出一棵给定二叉树的所有叶子结点。解：输出一棵二叉树的所有叶子结点的递归模型f()如下：f(b)：不做任何事件 若b=NULL f(b)：输出*b结点的data域 若*b为叶子结点 f(b)：f(b-lchild);f(b-rchild)其他情况,模块2：树形结构,void DispLeaf(BTNode*b)if(b!=NULL)if(b-lchild=NULL,模块2：树形结构,先序遍历思想,2.哈夫曼树,（1）哈夫曼树的定义,WPL

18、最小，没有单分支结点即n1=0,模块2：树形结构,（2）哈夫曼树的构造过程,（3）哈夫曼编码的构造过程,模块2：树形结构,顶点的度、入度和出度 完全图 子图 路径和路径长度 连通、连通图和连通分量 强连通图和强连通分量 权和网,模块3：图形结构,（1）图的基本概念,（2）图的存储结构,邻接矩阵存储方法,掌握两种存储方法的优缺点，同一种功能在不同存储结构上的实现算法。,邻接表存储方法,模块3：图形结构,（3）图的遍历,深度优先搜索遍历,离初始点越远越优先访问。,访问序列：1，2，3，4，5，6，7,模块3：图形结构,void DFS(ALGraph*G,int v)ArcNode*p;Visit

19、edv=1;/*置已访问标记*/printf(%d,v);/*输出被访问顶点的编号*/p=G-adjlistv.firstarc;while(p!=NULL)if(visitedp-adjvex=0)DFS(G,p-adjvex);p=p-nextarc;,模块3：图形结构,广度优先搜索遍历,离初始点越近越优先访问。,访问序列：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

20、;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;queuerear=p-adjvex;p=p-next

21、arc;,模块3：图形结构,（4）最小生成树,普里姆算法 给定起始点；算法过程；O(n2),模块3：图形结构,克鲁斯卡尔算法 不给定起始点；算法过程；O(elog2e),模块3：图形结构,（5）最短路径,狄克斯特拉算法过程 弗洛伊德算法过程,模块3：图形结构,（1）线性表的查找,模块4：其他,1.查找,在顺序表上进行。方法有：顺序查找（过程和算法）二分查找（过程和算法）分块查找(过程),（2）树表的查找,二叉排序树,定义 查找（过程和算法）插入和删除（过程）,与堆的区别,模块4：其他,性质：二叉排序树的中序序列是一个有序序列,平衡二叉树,定义 查找（过程和算法）调整（过程）,模块4：其他,（3

22、）哈希表查找,哈希函数主要有除留余数法。,哈希冲突解决方法 主要有线性探查法、拉链法,模块4：其他,2.内排序,插入排序（1）直接插入排序（2）希尔排序,模块4：其他,交换排序（1）冒泡排序（2）快速排序,过程,选择排序（1）直接选择排序（2）堆排序,过程,归并排序 基数排序,过程,例 在待排序的元素序列基本有序的前提下，效率最高的排序方法是。A.插入排序B.选择排序C.快速排序D.归并排序,解 插入排序是将待排序的记录插入到前面已排好序的子区间中，即考虑已排好序的子区间。本题答案为A。,例 快速排序在最坏情况下时间复杂度是O(n2)，比 的性能差。A.堆排序B.冒泡排序C.直接选择排序 D.直接插入排序,解 A。,强调各种排序方法的比较是否需要比较排序方法的区别时间复杂度空间复杂度,