国二复习必备 数据结构.ppt

国二复习必备 数据结构.ppt

ID:52230661

大小:13.49 MB

页数:57页

时间:2020-04-03

国二复习必备 数据结构.ppt_第1页
国二复习必备 数据结构.ppt_第2页
国二复习必备 数据结构.ppt_第3页
国二复习必备 数据结构.ppt_第4页
国二复习必备 数据结构.ppt_第5页
资源描述:

《国二复习必备 数据结构.ppt》由会员上传分享,免费在线阅读,更多相关内容在应用文档-天天文库

1、数据元素集合元素间关系集合数据结构(datastructure)—数据元素和数据元素关系的集合Data_Structure={D,R}数据的逻辑结构—抽象反映数据元素的逻辑关系从逻辑关系上描述数据,与数据的存储无关从具体问题抽象出来的数据模型;与数据元素本身的形式、内容无关;与数据元素的相对位置无关。数据结构(datastructure)—数据元素和数据元素关系的集合Data_Structure={D,R}数据的逻辑结构—抽象反映数据元素的逻辑关系数据逻辑结构分为:(集合)——数据元素间除“同属于一个集合”外,无其它关系线性结构——一个对一个,如线性表、栈、队列树形结构——一个对多个,

2、如树图状结构——多个对多个,如图数据的存储结构(物理结构)—数据的逻辑结构在计算机存储器中的实现存储结构分为:顺序存储结构—借助元素在存储器中的相对位置来表示数据元素间的逻辑关系链式存储结构—借助指示元素存储地址的指针表示数据元素间的逻辑关系时间复杂度:同一问题可用不同算法解决,各种算法中,语句执行次数越多,则该算法耗费的时间越长。一个算法中的语句执行次数称为语句频度或时间频度,记为T(n)。T(n)=∑语句执行次数×该语句执行时间≈∑语句执行次数该方法可独立于机器的软件、硬件系统来分析算法在效率方面的优劣例x=0;y=0;for(k=0;k<2*n;k++)x++;for(i=0;i

3、

4、=T1(n)+T2(n)+T3(n)=O(max(1,2n,n2))=O(n2)例x=0;y=0;for(k=0;k<2n;k++)x++;for(i=0;i

5、存储空间的量度常用时间复杂度:O(1)-----常量型O(n)、O(n2)、O(n3)------多项式型O(log2n)、O(nlog2n)-------对数型O(2n)、O(en)------指数型O(1)O(log2n)O(n)O(nlog2n)O(n2)O(n3)O(nk)O(2n)……线性结构特点:在数据元素的非空有限集中存在唯一的一个被称作“第一个”的数据元素存在唯一的一个被称作“最后一个”的数据元素除第一个外,集合中的每个数据元素均只有一个前驱除最后一个外,集合中的每个数据元素均只有一个后继2.1线性表的逻辑结构定义:一个线性表是n个数据元素的有限序列例英文字母表(A,B

6、,C,…..Z)是一个线性表例数据元素特征:有限、序列、同构元素个数n—表长度,n=0空表1

7、进行操作,无需从表头查找特点:实现逻辑上相邻—物理地址相邻实现随机存取顺序存储结构的优缺点优点逻辑相邻,物理相邻可随机存取任一元素存储空间使用紧凑缺点插入、删除操作需要移动大量的元素2.3线性表的链式存储结构特点:用一组任意的存储单元存储线性表的数据元素利用指针(链)实现了用不相邻的存储单元存放逻辑上相邻的元素每个数据元素ai,除存储本身信息外,还需存储其直接后继的地址结点数据域:元素本身信息指针域:指示直接后继的存储位置数据域指针域结点“指针

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。