数据结构引言.ppt

该【数据结构引言 】是由【我是药神】上传分享，文档一共【61】页，该文档可以免费在线阅读，需要了解更多关于【数据结构引言 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。文档名
Romtstosutsoutstekosotshetotsotsomt
IDEA
集合结构
线性结构
树形结构
图形结构
8
数据结构的操作
创建:创建一个数据结构
清除:删除数据结构
插入:在数据结构指定的位置上插入一个新元素
删除:将数据结构中的某个元素删去
搜索:在数据结构中搜索满足特定条件的元素
更新:修改数据结构中的某个元素的值
访问:访问数据结构中的某个元素
遍历:按照某种次序访问数据结构中的每一元素,使每个元素恰好被访问一次
每一种数据结构的特定操作
9
数据结构的存储实现
包括两个部分:
数据元素的存储
数据元素之间的关系的存储
物理结构由三个部分组成:
存储结点,每个存储结点存放一个数据元素;
数据元素之间的关系的存储,也就是逻辑结构的机内表示;
附加信息,便于运算实现而设置的一些“哑结点”,如链表中的头结点。
10
基本的存储方式
数据元素的类型可以是各种各样的,通常不会是简单的内置类型,因此存储结点可以是一个结构体类型的变量或对象
数据结构主要讨论关系的存储。因此,数据结构主要采用泛型程序设计的思想
11
关系的存储
顺序存储:用存储的位置表示元素之间的关系。主要用数组实现。
链接存储:用指针显式地指出元素之间的关系,如单链表就是表示线性关系的
哈希存储方式:是专用于集合结构的数据存放方式。在哈希存储中,各个结点均匀地分布在一块连续的存储区域中,用一个哈希函数将数据元素和存储位置关联起来。
索引存储方式:所有的存储结点按照生成的次序连续存放。另外设置一个索引区域表示结点之间的关系。
12
第一章引言
什么是数据结构
算法分析
面向对象的数据结构
13
算法分析
数据结构是讨论一组数据的处理问题。
每一种存储方式下对应的每一种操作的实现都是一个算法
每种操作有多种实现方式
如何评价这些算法的好坏
14
算法的质量评价
正确性:算法应能正确地实现预定的功能;
易读性:算法应易于阅读和理解,以便于调试、修改和扩充;
健壮性:当环境发生变化(如遇到非法输入)时,算法能适当地做出反应或进行处理,不会产生不正确的运算结果;
高效率:具有较高的时间和空间性能。
这四个指标往往是互相冲突的,数据结构主要考虑的是时空性能
15
算法效率分析
如何确定一个算法是高效的算法就是分析该算法所需要的资源。算法的资源包括:
时间:程序运行所需要的时间。要运行一年的算法是很难让人接受的
空间:程序运行所需要的空间。需要几个G的内存的算法同样也令人难以接受。
16