数据结构章.ppt
《数据结构章.ppt》由会员分享,可在线阅读,更多相关《数据结构章.ppt(57页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、数据结构章现在学习的是第1页,共57页上机时间地点安排上机:周五(双周)晚上第11-13节;地点为:浙大紫金港校区计算中心 联系老师:裘雯联系电话:88206072,13858091198现在学习的是第2页,共57页 随着个人计算机和Internet的迅猛发展,以计算机科学技术为核心的信息技术正在深刻地改变着人们的工作方式、生活方式和思维方式。有人预计21世纪的计算机软件业将成为全球高科技产业发展的最主要的推动力。因此,作为软件设计技术的理论基础,“数据结构与数据库技术”就不仅仅是计算机科学技术学科的核心课程,也是所有应用计算机的其它理工学科需要掌握的课程。现在学习的是第3页,共57页智慧城市
2、关键技术取得的新进展智慧城市关键技术取得的新进展 (1)云计算从概念走向实施IBM“蓝云计划”可以对企业现有的基础架构进行整合,实现企业硬件资源和软件资源的统一管理、统一分配、统一部署、统一监控和统一备份,帮助中小企业实现云计算“Google Computer Engine”云计算服务用户可快速、廉价(免费使用限定的流量和存储)地部署自己开发的互联网应用,如网站、游戏等现在学习的是第4页,共57页Amazon Web Services 依靠亚马逊的计算和存储服务,用户能够建立可靠、强大、低成本的互联网应用Apple的“iCloud”适用于 Mac(Macintosh,苹果电脑)、iPhone、
3、iPad 和 iPod touch等设备,不仅可存储 Mac 和所有iOS(由苹果公司开发的手持设备操作系统)设备上的内容,还可以在所有设备上访问你的照片、日历、通讯录、文档以及更多内容,并随时随地保持更新。现在学习的是第5页,共57页大数据:正在到来的数据革命涂子培爆发:大数据时代预见未来的新思维(美)艾伯特-拉斯洛巴拉巴西(2)大数据受到高度关注大数据时代:生活、工作与思维的大变革(英)维克托迈尔-舍恩伯格现在学习的是第6页,共57页全球技术研究和咨询公司Gartner表示,2013年是企业大规模采用大数据技术的一年。根据Gartner针对全球IT主管进行的调查,42%的受访者表示已投资于
4、大数据技术,或将于未来一年内进行相关投资大数据的产生现在学习的是第7页,共57页大数据的重要性大数据的未来现在学习的是第8页,共57页大数据的应用 奥巴马总统连任之路 定位“多金族”通过大数据库,竞选团队发现参与了“快速捐献”计划(允许在网上或者通过短信重复捐钱,而无须重新输入信用卡信息)的人,捐出的资金是其他的捐献者4倍。该计划被迅速推广,并成为竞选重要组成部分。最终竞选资金达到了10亿美元 搞定“摇摆州”利用大数据库,通过计算机模拟竞选,来推算出奥巴马在每个“摇摆州”的胜算,从而确定可以赢得这些州的机会,再进行资源分配 广告精准投放不再依赖于外部媒体顾问来决定广告应该在哪里出现,将广告的购
5、买决策建立在内部大数据库上来精准定位可劝服的选民,使电视广告效率提高了14%现在学习的是第9页,共57页大数据正在对竞选、商业、犯罪预防等涉及政治、经济、大数据正在对竞选、商业、犯罪预防等涉及政治、经济、社会等领域的运作和管理模式产生深刻的影响。社会等领域的运作和管理模式产生深刻的影响。现在学习的是第10页,共57页“大数据”是智慧城市建设的核心问题之一5Vs:量大(Volume):对海量数据进行处理 种类多(Variety):对多部门、多行业同构或异构的数据进行处理速度快(Velocity):对即时数据进行处理真实性要求高(Veracity):需要对获取的数据进行清洗 价值高(Value):
6、基于人工智能的数据分析和知识管理大数据的核心:基于海量、复杂(同构或异构)、即时、真实数据的 智能分析预测能力现在学习的是第11页,共57页 数据结构与数据库技术主要内容包括两大部分:第一部分为数据结构,包括线性表、栈和队、串、数组、树、图等,以及排序和查找等操作;第二部分为数据库技术,包括数据库概论、数据库技术基础、关系数据库基本理论、数据库设计、关系数据库标准语言SQL等。现在学习的是第12页,共57页第一部分数 据 结 构现在学习的是第13页,共57页1.1 数据结构的概念数据结构的概念 1.1.1 研究内容研究内容 1.1.2 有关概念和术语有关概念和术语1.2 算法和算法分析算法和算
7、法分析 1.2.1 算法特性算法特性 1.2.2 算法描述算法描述 1.2.3 算法性能分析与度量算法性能分析与度量第一章 绪论现在学习的是第14页,共57页 在用计算机解决实际问题时,一般要经过以下几个步骤:首先,对具体问题抽象出数学模型;然后针对数学模型设计出求解算法;选择或设计合适的数据结构存储相关数据;最后编出程序上机调试,直至得到最终的解答。下面简述各环节的有关内容。1.1.1 研究内容现在学习的是第15页,共57页问题求解之一:问题建模n 一般情况下,实际应用问题可能会各式各样,例如:我们所熟悉的工资表的处理问题,学生成绩管理问题,电话号码查询,数据加密、压缩问题等。n 这些问题中
8、,无论是所涉及到的数据,还是其操作要求,都可能存在一定的差异,但许多问题还是具有一定的相似之处的。例如:现在学习的是第16页,共57页虽然工资表和学生成绩表的具体信息(栏目)不同,但如果将两个表中的每个人的工资信息和成绩信息分别看作一个整体,则这两个表结构之间就有了某些共性。从操作方面来看,虽然对这两种表的操作存在差异,但也存在一些相同或相似的基本操作。例如,查询一个人的工资信息和成绩信息,修改有关信息等。现在学习的是第17页,共57页n 正因为许多不同的问题之间存在着的某些共性,可以将一个具体问题用这些共性的形式描述出来问题建模。n 问题建模通常包括:所描述问题中的数据对象的集合;对象间关系
9、及其描述;问题求解的要求及方法等。现在学习的是第18页,共57页n 建立问题模型的好处:通过建立模型,就可以将一个具体的问题转换为所熟悉的模型,然后借助于这一模型来实现。数据结构、离散数学及许多数学课程中就介绍了许多模型。现在学习的是第19页,共57页问题求解之二:构造求解算法n 通过问题建模,将一个具体的问题转换成一个用模型所描述的抽象的问题。n 借助于这一模型以及已有的知识(例如数据结构中有关图结构的基本知识),可以相对容易地描述出原问题的求解方法,即算法。n 该算法不仅能实现原问题的求解,而且还可能实现许多类似的具体问题的求解。现在学习的是第20页,共57页问题求解之三:选择或设计存储结
10、构n 在构造出求解算法之后,需要考虑在计算机上实现求解了。为此,需要做两方面的工作:选择或设计合适的存储结构,以便将问题所涉及到的数据存储到计算机中。设计程序,实现问题求解。存储形式和问题要求决定了程序设计的方法。现在学习的是第21页,共57页问题求解之四:测试 如何实现预定的功能和目标?n 理论证明:这是计算机科学领域曾经开展过的工作。由于算法和程序的复杂性急剧增长,因而难以实用。n测试:通过对所开发的系统或模块,运行给定的测试数据,以发现存在的错误,而不是证明其正确。现在学习的是第22页,共57页这是当前软件开发领域普遍采用的方法,通常要占系统开发40%以上的工作量。详细描述可参考“软件工
11、程”相关的描述。所设计的算法和程序,需要经过充分的测试才能交付使用。对程序的测试态度反映出学生的治学态度:如果是认真负责的态度,就会认识到,任何设计都难免有疏漏,或者受环境的影响,因而需要高度重视。对程序的测试设计也反映出学生的治学能力:如何设计测试用例?需要依据多种方法、策略和实践。现在学习的是第23页,共57页现在学习的是第24页,共57页1.1.2 有关概念和术语 数据数据(Data):是能够被计算机识别、存储和加工处理的信息的载体。例如:工资表(编号,姓名,基本工资,奖金),学生成绩表(学号,姓名,考试成绩),电话号码簿;一个家族关系的表示形式;一个群体之间关系的图形描述等。虽然数据的
12、形式及运算存在较大的差异,但存在共性:由若干具有独立意义的个体所组成,个体间存在着某些关系。对这些数据的运算也有某些相似之处。例如,在家族关系数据中,组成数据的基本个体是个人信息,其中各人之间存在着多种关系,如父子关系、兄弟关系等。现在学习的是第25页,共57页 从工资表、学生成绩表这些示例数据可见,数据可以分解为元素的集合。数据元素数据元素(Data Element):是数据的基本单位(具有完整的独立意义)。也称为元素、结点、顶点、记录。例如:工资表中的个人工资信息;成绩表中的学生成绩信息;家族关系中的个人等。编号姓名基本工资奖金0001张三300020000002李四31002100杭州科
13、力特公司工资表学号姓名考试成绩6001张三956002李四841301班 数学课程学生成绩表现在学习的是第26页,共57页 数据项数据项(Data Item):有独立含义的数据最小单位,也称域有独立含义的数据最小单位,也称域(Field)或字段。它是元素的具体描述信息。或字段。它是元素的具体描述信息。学号姓名考试成绩6001张三956002李四846003王五76表中一行对应一个元素表中一行对应一个元素表中一列对应一个字段表中一列对应一个字段 数据对象数据对象(Data Object):是具有相同特性的数据元素的集合:是具有相同特性的数据元素的集合,是数据的一个子集。,是数据的一个子集。现在学
14、习的是第27页,共57页 数据结构数据结构(Data Structure):是指构成数据的元素之间的结构关系:是指构成数据的元素之间的结构关系,即数据的组织形式。,即数据的组织形式。数据元素之间存在以下几类内在的关系:线性结构线性结构:元素之间具有次序关系。树形结构树形结构(树型结构):元素之间的关系类似于现实中的树。图结构图结构(网状结构):元素间的关系较复杂。集合集合:元素之间没有关系。逻辑结构现在学习的是第28页,共57页更一般地,数据结构包括以下三个方面的内容:更一般地,数据结构包括以下三个方面的内容:(1)数据元素之间的内在结构关系(逻辑关系),也称为数据的逻辑结构(Logical
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构
限制150内