数据结构培训课件.ppt
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《数据结构培训课件.ppt》由用户(林田)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 培训 课件
- 资源描述:
-
1、2022-8-19数据结构1数据结构数据结构 2022-8-19数据结构2讲课安排:讲课安排:串讲全书内容串讲全书内容典型习题分析典型习题分析前年、去年考题分析前年、去年考题分析 2022-8-19数据结构3数据结构及其概念 如何评价一个算法2022-8-19数据结构4一、术语一、术语 是信息的载体,能被计算机识别、存储、加工处理。是信息的载体,能被计算机识别、存储、加工处理。数据的基本单位数据的基本单位,即数据集合中的一个个体。也称即数据集合中的一个个体。也称元素、元素、结点、顶点、记录结点、顶点、记录是具有独立含义的最小标识单位是具有独立含义的最小标识单位唯一能识别一个数据元素的数据项。唯
2、一能识别一个数据元素的数据项。数据元素由数据元素由组成组成2022-8-19数据结构5 是具有相同性质的计算机数据的集合及在这个是具有相同性质的计算机数据的集合及在这个集合上的一组操作集合上的一组操作。数据的逻辑结构数据的逻辑结构 数据的存储结构数据的存储结构 数据的运算:既对数据施加的操作数据的运算:既对数据施加的操作2022-8-19数据结构6逻辑结构:逻辑结构:(有时直接称为数据结构)有时直接称为数据结构)线性结构:线性表、栈、队列、串线性结构:线性表、栈、队列、串(最多只有一个直接前趋和一个直接后继最多只有一个直接前趋和一个直接后继)非线性结构:树非线性结构:树、图、多维数组、广义表、
3、图、多维数组、广义表说明:说明:1、逻辑结构与数据元素本身的形式、内容无关、逻辑结构与数据元素本身的形式、内容无关2、逻辑结构与数据元素的相对位置无关、逻辑结构与数据元素的相对位置无关3、逻辑结构与所含结点个数无关、逻辑结构与所含结点个数无关2022-8-19数据结构7存储结构:存储结构:顺序存储方法:顺序存储方法:数据元素在内存中按序连续存储,数据元素在内存中按序连续存储,结点间的逻辑关系由存储单元的邻接关系来体现结点间的逻辑关系由存储单元的邻接关系来体现链接存储方法:链接存储方法:用指针指出其直接后继结点的存储位置,用指针指出其直接后继结点的存储位置,结点间的逻辑关系由存储单元的邻接关系来
4、体现结点间的逻辑关系由存储单元的邻接关系来体现索引存储方法:索引存储方法:数据元素连续存放,再设一个索引表(有数据元素连续存放,再设一个索引表(有序),索引表由索引项组成,每个索引项由关键字和地址构成序),索引表由索引项组成,每个索引项由关键字和地址构成 分为稠密索引和稀疏索引分为稠密索引和稀疏索引散列存储方法:散列存储方法:确定散列函数后,根据结点的关键字直接确定散列函数后,根据结点的关键字直接 计算出该结点的存储地址。计算出该结点的存储地址。2022-8-19数据结构8关系:关系:逻辑结构是从逻辑关系上描述数据,与存储无关,是独立于逻辑结构是从逻辑关系上描述数据,与存储无关,是独立于计算机
5、的。计算机的。逻辑结构是从具体问题抽象出来的数学模型逻辑结构是从具体问题抽象出来的数学模型存储结构是逻辑结构用计算机语言的实现(亦称映象)存储结构是逻辑结构用计算机语言的实现(亦称映象)数据的运算是定义在数据的逻辑结构上的一个运算的集合数据的运算是定义在数据的逻辑结构上的一个运算的集合运算的实现与存储结构密切相关运算的实现与存储结构密切相关逻辑结构与存储结构是多对多的关系逻辑结构与存储结构是多对多的关系2022-8-19数据结构9例:一个学生成绩表:例:一个学生成绩表:是一个数据结构是一个数据结构每行是一个结点(或记录),由学号、姓名、各科成绩每行是一个结点(或记录),由学号、姓名、各科成绩
6、及平均成绩等数据项组成。及平均成绩等数据项组成。逻辑关系:线性结构逻辑关系:线性结构存储结构:存储结构:表的运算:表的运算:2022-8-19数据结构10 逻辑结构上定义的定义的基本运算在存储结构上的实现是通过算法来描述的。一、算法定义一、算法定义 算法算法是对特定问题求解步骤的一种描述,由有限的指令序列构成,其中每一条指令表示一个或多个操作。2022-8-19数据结构11 二、算法应具有的五个特性:二、算法应具有的五个特性:(1)输入输入 一个算法有零个或多个的输入,它们是算法开始前给出的最初量(2)输出输出 一个算法至少有一个输出,它们是同输入 有某种关系的量(3)有穷性有穷性 每一条指令
7、的执行次数必须是有限的(4)确定性确定性 每一条指令必须有确切的含义,无二义性(5)可行性可行性 每条指令的执行时间都是有限的。2022-8-19数据结构12一、算法评价五要素一、算法评价五要素 2022-8-19数据结构13二、算法的时间复杂度二、算法的时间复杂度 一个算法所耗费的时间一个算法所耗费的时间:该算法中每条语句的执行时间之和。该算法中每条语句的执行时间之和。每条语句的执行时间每条语句的执行时间:该语句的执行次数乘以该语句执行一次:该语句的执行次数乘以该语句执行一次所需时间。所需时间。频度频度:语句重复执行的次数:语句重复执行的次数算法的时间耗费算法的时间耗费T(n)=每条语句的执
8、行的时间每条语句的执行的时间=(语句频度(语句频度语句执行一次所需时间)语句执行一次所需时间)=语句频度语句频度算法的时间复杂度:算法的时间复杂度:就是算法的时间耗费就是算法的时间耗费T(n)2022-8-19数据结构14三、(渐进)时间复杂度三、(渐进)时间复杂度(O(f(n)当问题的规模当问题的规模n趋向无穷大时,时间复杂度趋向无穷大时,时间复杂度T(n)的数量的数量级(阶)称为算法的级(阶)称为算法的渐近时间复杂度渐近时间复杂度,简称简称时间复杂度时间复杂度四、最坏时间复杂度四、最坏时间复杂度依据数据集中可能出现的最坏情况估算出的时间复杂度依据数据集中可能出现的最坏情况估算出的时间复杂度
9、称为最坏时间复杂度。称为最坏时间复杂度。五、平均时间复杂度五、平均时间复杂度在假设数据集的分布是等概率的条件下,估算出的时间在假设数据集的分布是等概率的条件下,估算出的时间复杂度称为平均时间复杂度。复杂度称为平均时间复杂度。例:顺序查找例:顺序查找2022-8-19数据结构15五、空间复杂度五、空间复杂度S(n):算法所耗费的存储空间,仍是问题规模算法所耗费的存储空间,仍是问题规模n的函数。的函数。2022-8-19数据结构161、掌握数据、数据元素、数据结构等基本概念。、掌握数据、数据元素、数据结构等基本概念。2、掌握数据逻辑结构和物理结构的分类。、掌握数据逻辑结构和物理结构的分类。3、学会
10、算法分析的基本方法。、学会算法分析的基本方法。2022-8-19数据结构17本章要学习的主要内容本章要学习的主要内容1、线性表的逻辑结构及基本运算、线性表的逻辑结构及基本运算2、线性表的顺序存储结构、线性表的顺序存储结构3、线性表的链式存储结构:单链表、循环链表、双、线性表的链式存储结构:单链表、循环链表、双链表、静态链表链表、静态链表4、顺序表和链表的比较、顺序表和链表的比较2022-8-19数据结构18 线性表是由线性表是由n(n=0)个数据元素个数据元素(点点)a1,a2,.,ai,.,an组成的有限序列。其中,数据元素的个数组成的有限序列。其中,数据元素的个数n定义为表长。定义为表长。
11、当当n=0时称为空表,非空的线性表时称为空表,非空的线性表(n0)记为:记为:(a1,a2,.,ai,.,an)1.数据元素数据元素ai是一个抽象的符号是一个抽象的符号 2.ai可取各种数据类型可取各种数据类型 3.一般情况下一般情况下,同一线性表中的元素具有相同的数据类型同一线性表中的元素具有相同的数据类型 4.i是元素的序号是元素的序号(1=i=n):仅有一个开始结点和一个终端结点,并且所有结仅有一个开始结点和一个终端结点,并且所有结点都最多只有一个直接前趋和一个直接后继点都最多只有一个直接前趋和一个直接后继2022-8-19数据结构19线性表的常见基本运算包括:线性表的常见基本运算包括:
12、(1)置空表)置空表SETNULL(L)(2)建表)建表CREATLIST(L)(4)取结点)取结点GET(L,i)(5)定位)定位LOCATE(L,x)(6)插入)插入INSERT(L,x,i)(7)删除)删除DELETE(L,i)(3)求表长)求表长LENGTH(L)复杂的运算可以由这些基本运算组合来实现复杂的运算可以由这些基本运算组合来实现2022-8-19数据结构201、顺序存储:将线性表的结点按逻辑次序依次存放在一组地、顺序存储:将线性表的结点按逻辑次序依次存放在一组地址连续的存储单元里。址连续的存储单元里。3 3、存储地址的计算:、存储地址的计算:LOC(aiLOC(ai)=LOC
13、(a1)+(i-1)=LOC(a1)+(i-1)*c 1=i=nc 1=idata=ch;s-next=head;head=s;ch=getchar();return head;2022-8-19数据结构29尾插法建表:尾插法建表:将新结点插入到当前链表的表尾(需引入将新结点插入到当前链表的表尾(需引入r)dsrabcHeadr不带头结点的尾插法:不带头结点的尾插法:插入时插入时,第一个结点的处理与其,第一个结点的处理与其它结点的处理有区别。它结点的处理有区别。结束时结束时,空表和非空表的处理有区别。,空表和非空表的处理有区别。2022-8-19数据结构30Linklist*CREATLIST
14、R()char ch;linklist*head,*s,*r;head=NULL;r=NULL;ch=getchar();while(ch!=$)s=malloc(sizeof(linklist);s-data=ch;if(head=NULL)head=s else r-next=s;r=s;ch=getchar();if(r!=NULL)r-next=NULL;return head;2022-8-19数据结构31尾插法建表:将新结点插入到当前链表的表尾(需引入尾插法建表:将新结点插入到当前链表的表尾(需引入r)dsrabcHeadr不带头结点的尾插法:不带头结点的尾插法:插入时插入时,第一
15、个结点的处理与其,第一个结点的处理与其它结点的处理有区别。它结点的处理有区别。结束时结束时,空表和非空表的处理有区别。,空表和非空表的处理有区别。带头结点的尾插法:带头结点的尾插法:1)链表第一个位置上的操作与其)链表第一个位置上的操作与其它位置上的操作相一致。它位置上的操作相一致。2)空表和非空表的处理相一致。)空表和非空表的处理相一致。2022-8-19数据结构32Linklist*CREATLISTR1()char ch;linklist*head,*s,*r;head=malloc(sizeof(linklist);r=head;ch=getchar();while(ch!=“$”)s
16、=malloc(sizeof(linklist);s-data=ch;r-next=s;r=s;ch=getchar();r-next=NULL;return head;dsrcHeadr2022-8-19数据结构33(1)按序号查找)按序号查找 GET(L,i)给定一个序号,在单链表中查找该序号对应的结点,给定一个序号,在单链表中查找该序号对应的结点,若结点存在,则返回该结点的指针,否则返回空指针。若结点存在,则返回该结点的指针,否则返回空指针。:非随机存储结构非随机存储结构的链表,决定了上述查找运算只能通过扫描单链表来完成。设置一个计数器设置一个计数器j一个一个p,初始指向头结点,初始指向
17、头结点P向后每移动一个位置向后每移动一个位置j+当当j=i时返回时返回2022-8-19数据结构34按值查找即在链表中查找是否有值等于给定值按值查找即在链表中查找是否有值等于给定值key的的结点。若有则返回首次找到的其值为结点。若有则返回首次找到的其值为key的结点的指的结点的指针,否则返回针,否则返回NULL。算法描述如下:算法描述如下:linklist*locate(head,key)linklist*head;datatye key;linklist*p;p=head next;在等概率的情况下,该算法的平均时间复杂度亦为在等概率的情况下,该算法的平均时间复杂度亦为O(n)(2)按值查找
18、)按值查找 LOCATE(head,key)while(p!=NULL)if(p data!=key)p=p next;else break;return p;2022-8-19数据结构35 (1)后插操作)后插操作:在指针在指针p所指结点之后插入所指结点之后插入xs(2)前插操作)前插操作:在指针在指针p所指结点之前插入所指结点之前插入Headp时间复杂度度时间复杂度度O(1)O(1)xs平均时间复杂度平均时间复杂度 O(n)O(n)先从头指针起先从头指针起,顺链找到顺链找到*p的前趋结点的前趋结点*q.Headpq2022-8-19数据结构36Headpax将前插操作转变为后插操作将前插操
19、作转变为后插操作xsxsaINSERTBEFORE(p,x)linklist*p;datatype x;linklist*s;s=malloc(sizeof(linklist);s-data=p-data;s-next=p-next;p-data=x;p-next=s;时间复杂度时间复杂度 O O(1)(1)2022-8-19数据结构37时间复杂度时间复杂度 O O(1)(1)删除指定结点的直接后继删除指定结点的直接后继Headprr=p-next;p-next=r-next;free(r);删除指定结点删除指定结点时间复杂度时间复杂度O(n)O(n)链表的优点链表的优点:在链表上实现插入、删
20、除运算无须移动结点,在链表上实现插入、删除运算无须移动结点,仅须修改指针仅须修改指针改进改进?2022-8-19数据结构382.单循环链表的特点:链表尾结点的单循环链表的特点:链表尾结点的next域不为空,而是指向域不为空,而是指向头结点或开始结点。(头结点或开始结点。(优点:优点:从任一结点从任一结点开始,均可找到其前趋和后继结点。)开始,均可找到其前趋和后继结点。)3、引入单循环链表的目的在于方便一些运算的实现。、引入单循环链表的目的在于方便一些运算的实现。实用中常采用实用中常采用尾指针单循环链表尾指针单循环链表,而不是头指针单循环链表。而不是头指针单循环链表。4、单循环链表上的操作与单链
21、表基本一致、单循环链表上的操作与单链表基本一致 差别差别仅在于:循环控制条件不是判空,而是判断是否等于仅在于:循环控制条件不是判空,而是判断是否等于头指针或尾指针。头指针或尾指针。1.循环链表循环链表:是一种首尾相接的链表是一种首尾相接的链表单循环链表单循环链表双循环链表双循环链表2022-8-19数据结构39 1.双链表的特点:每个结点有两个指针域,分别指向其直接双链表的特点:每个结点有两个指针域,分别指向其直接 前趋和后继。前趋和后继。2.双链表存储结构描述如下双链表存储结构描述如下:typedef struct dnode datatype data;struct dnode*prior
22、,*next;dlinklist;dlinklist*head;对于双向链表,当将头、尾结点链起来时,便成了对于双向链表,当将头、尾结点链起来时,便成了双向循环双向循环链表。链表。2.3.4 2.3.4 双链表双链表 priornextdata为了指示双链表,也须引入一为了指示双链表,也须引入一个头指针个头指针head,指指向其开向其开始结点始结点。2022-8-19数据结构403.双向链表基本运算的实现:双向链表基本运算的实现:(1)删除运算)删除运算(2)插入运算)插入运算插入和删除都非常方便插入和删除都非常方便p-prior-next=p=p-next-prior删除运算删除运算DELE
23、TENODE(p)/*删除双链表结点删除双链表结点*p*/dlinklist*p;p-prior-next=p-next;p-next-prior=p-prior;free(p);Headp2022-8-19数据结构41插入运算插入运算DINSERTBEFORE(p,x)dlinklist*p;datatype x;dlinklist*s;Pxss=malloc(sizeof(dlinklist);s-data=x;s-prior=p-prior;s-next=p;p-prior-next=s;p-prior=s;2022-8-19数据结构42 实现方法实现方法 存储空间存储空间 分配和释放分
24、配和释放 静态链表静态链表 游游 标标 预分配的一预分配的一个连续空间个连续空间 用户定义用户定义 动态链表动态链表 指指 针针 内存所有可内存所有可用空间用空间 系统提供系统提供 静态链表与动态链表的区别静态链表与动态链表的区别2022-8-19数据结构43 2、静态链表存储结构描述如下:、静态链表存储结构描述如下:define maxsize 1024typedef int datatype;typedef int cursor;typedef struct datatype data;数据域数据域 cursor next;游标游标 node;node nodepoolmaxsize;存储
25、池存储池 cursor av;游标变量游标变量 1、用数组和、用数组和“游标游标”实现链式存储的方法是实现链式存储的方法是:事先定义一个规模较大的结构数组作为备用结点空间事先定义一个规模较大的结构数组作为备用结点空间(即存储池),当申请结点空间时,从存储池中取出结点,(即存储池),当申请结点空间时,从存储池中取出结点,当释放结点空间时,将其归还于存储池内。采用这种方法实当释放结点空间时,将其归还于存储池内。采用这种方法实现的链表称为现的链表称为静态链表静态链表。12Maxsize-13NULL012Maxsize-1av0nodepoolmaxsize2022-8-19数据结构44说明说明:静
展开阅读全文