- 1、本文档共67页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
- 5、该文档为VIP文档,如果想要下载,成为VIP会员后,下载免费。
- 6、成为VIP后,下载本文档将扣除1次下载权益。下载后,不支持退款、换文档。如有疑问请联系我们。
- 7、成为VIP后,您将拥有八大权益,权益包括:VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。
- 8、VIP文档为合作方或网友上传,每下载1次, 网站将根据用户上传文档的质量评分、类型等,对文档贡献者给予高额补贴、流量扶持。如果你也想贡献VIP文档。上传文档
查看更多
数据结构6集合与字典.ppt
字典及其抽象数据类型 考虑的问题是数据的存储和检索(查询),就像在新华字典里字词的组织和查找一个字的相关解释等 ? 存储和检索是计算过程中最重要的基本操作 ? 本章主要讨论基于关键码的数据存储和检索,需要根据某些线索找出相关的数据 ? 支持这种操作的数据结构,通常称为字典或查找表 ? 不是介绍一种结构,而是介绍计算中最重要的一种问题的许多不同解决方式,以及各种相关性质 ? 将用到前面讨论过的许多结构。包括各种线性结构、树性结构及其各种组合,涉及在这些结构上操作的许多算法 抽象模型 设有关键码集合KEY和值(或称属性)集合VALUE 关联(Association)是二元组(k,v)∈KEYxVALIUE 字典:以关联为元素的有穷集合(key不相同) 关键码到值的有穷函数:key-value 主要字典操作: ? 检索(search) ? 插入元素(insert) ? 删除元素(delete) ? 修改某key对应的值 p269字典的抽象数据结构 最主要也是使用最频繁的操作是检索(也称查找) 检索效率是字典实现中最重要的考虑因素 静态字典:建立后保持不变的字典 动态字典:内容经常动态变动的字典 静态字典的基本操作就是检索。实现中主要考虑检索效率 动态字典除检索外还有插入和删除,实现中还需要考虑: ? 插入删除操作的效率 ? 插入删除可能导致字典结构变化,动态变化中能否保证检索效率?(使字典性能不随操作的进行而逐渐恶化) ? 存储和检索是计算机信息处理中最基本的工作 ? 字典就是实现存储和检索的结构 ? 需要存储和检索的信息有许多具体情况,因此要考虑各种不同的字典实现技术。 ? 这里的基本问题是空间利用率和操作效率检索效率的评价标准:检索过程中关键码的平均比较次数,即平均检索长度ASL(average search length),定义为: ASL =Σni=1pici ci 和pi 分别为元素i 的检索长度和概率。若各元素的检索概率相等,就有pi=1/n。ASL = 1/n Σ ci 。 字典的组织方法很多,如:顺序、跳表、散列、二叉树和B树等。 线性表表示 线性表可以保存信息,因此可以作为字典的实现基础 关联在线性表里顺序排列,形成关联的序列 检索就是在线性表里查找关键码合适的元素 数据元素的插入删除都是很平常的线性表操作 顺序表表示 链表表示(p270) 顺序检索算法 /*在字典中顺序检索关键码为key的元素*/ int seqSearch(SeqDic *pdic, KeyType key, int *position) { int i; for(i = 0; i pdic-n; i++) /* 从头开始向后扫描*/ if(pdic-element[i].key == key) { *position = i; return TRUE; /* 检索成功*/ } *position = -1; return FALSE; /* 检索失败*/ } 失败时由position 设置一个特殊值。 平均检索长度分析 ASL = 1*p1 +2* p2 + …+n* pn = (1+2+…+n)/n (pi=1/n 时) = (n+1)/2 = O(n) 优点:数据结构和算法简单,元素是否有序均可使用 缺点:平均检索长度大,n很大时检索耗时太多 不适合动态变化频繁的字典 删除元素需顺序检索,O(n) ,可能大量移动数据 插入元素(关联)时可保存在已有元素之后,O(1) 操作;若要防止出现重复关键码,就需要检查所有元素,O(n) 动态变化中字典的检索效率不变(已经是最低效的) 二分法检索算法 如果字典元素之间有关系,就可能利用它加快检索速度。最常见的关系是关键码有序,这时将元素按序排列(从小到大或从大到小)排列,就可以快速检索(二分法) 二分法检索基本过程(假设元素按关键码升序排列): 1. 初始时,考虑范围是整个字典(顺序表) 2. 取考虑范围中位于中间的元素,用这个元素的关键码与检索关键码比较。如果相等则检索结束;否则 3. 如果检索关键码较大,把检索范围改为位置高的一半;如果检索关键码较小,把检索范围改为低一半 4. 如果范围里已经无元素,检索失败结束,否则回到2 /* 在字典中用二分法检索关键码为key的元素*/ int biSearch(SeqDic *pdic, KeyType key, int *position) { int low = 0, high = pdic-n-1, mid; while(low=high) { mid = (low+high)/2; /* 当前检索的中间位置*/ if(pdi
您可能关注的文档
- 数字摄影测量系统.ppt
- 市场营销学(专科)作业一(福建).doc
- 中国传媒大学产业经济学专业考研复试科目目录.pdf
- 北京大学产业经济学考研参考书分数线资料.pdf
- 大学英语B2_unit2a课件.ppt
- 控制工程基础课后习题解答.ppt
- 上半年道路交通检查汇报.doc
- 2011年真题解析班刑事诉讼法讲义.pdf
- 房屋建筑学第六章习题.doc
- 数字逻辑自测题3.doc
- 2025年中国美洲樱桃木木地板数据监测报告.docx
- 2025年人工智能在药物合成中的智能化合成路径研究.docx
- 2025年氢能源产业技术创新成果转化与产业发展报告.docx
- 2025年人工智能在药物分子设计中的应用突破报告.docx
- 2025年人工智能在网络安全中的成本控制与防护策略研究.docx
- 安全员考试高频难、易错点题(典优)附答案详解.docx
- 防尘绿化工程施工方案范本(3篇).docx
- 2025年人工智能在药物合成中的生物信息学数据分析与药物发现报告.docx
- 2025年Z世代消费群体宠物消费行为与市场前景分析报告.docx
- 2025年线上宠物行为训练平台与人工智能技术应用报告.docx
最近下载
- 2023ESC急性冠脉综合征管理指南(完整版).pdf
- 2025美国急性冠脉综合征(ACS)患者管理指南解读课件PPT.pptx
- 《设计小房子》教案-2024-2025学年教科版(2024)小学科学二年级上册.docx VIP
- 《夜晚的月亮》教案-2024-2025学年教科版(2024)小学科学二年级上册.docx VIP
- 1.4设计小房子 课件 2024新教科版科学二年级上册.ppt
- DELTA台达垂直多关节机器人手持式教导器 DTV 系列操作手册.pdf VIP
- 医院常见传染病感染防控的管理要点.pdf
- 2.7夜晚的月亮 课件 2024新教科版科学二年级上册.ppt
- 华成多轴机械手控制系统说明书培训资料.pdf
- 小学奥数教师版(合辑)1-1-2-3 分数四则混合运算综合.pdf VIP
文档评论(0)