频道栏目
首页 > 程序开发 > Web开发 > 其他 > 正文
相关基础知识
2015-09-22 11:44:31           
收藏   我要投稿
声明:在作者学习数据结构的过程中发表的博文,一般是自己学习后知识点的总结,同时有些是摘抄于教材的,学习教材为《数据结构 C语言版》秦峰主编。特此声明,后续博文不在重复说明。

 

一、基本概念

    数据(data)是对客观事物的符号表示,它能够被计算机识别、存储、和加工处理。

    数据元素(data element)是数据的基本单位,有时也成为元素、节点、顶点或记录。

    数据项是最小的标识单位,也称字段、域或属性。

    数据结构(data structure)是指数据元素之间的相互关系,即数据的组织形式。

 

    数据结构一般包括以下三个方面:

        (1)数据元素之间的逻辑关系,也称数据的逻辑结构,它是数据本身的一种属性。

        (2)数据元素及其之间的逻辑关系在计算机中的表示方式,即数据的存储结构。它必须依赖于计算机。

        (3)数据运算,对数据元素的操作。运算的定义依赖于逻辑结构,运算的实现依赖于存储结构。

    

    数据元素常见的逻辑关系:

    集合:结构中的任意两个数据元素之间都没有逻辑关系,它们都是独立存在的。

    线性结构:结构中的数据元素之间存在一对一的关系。

    树形结构:结构中的数据元素之间存在一对多的关系。

    图状结构:结构中的数据元素之间存在多对多的关系。

 

    数据的常见存储结构:

    顺序存储:数据元素被依次存放在一组连续的地址空间中的存储方式。

    链式存储:数据元素被存放在随机的地址空间中,每个数据元素中设置一个指针域,用来标识数据元素间一对一的关系,这种存储结构成为链式存储。

    引索存储:在存储数据元素的同时,附加一个引索表,其常见格式<关键字,地址>,其中关键字是能唯一标识数据元素的数据项。若每个数据元素中均有一个引索项,则称稠密引索。若一个引索项对应一组数据元素,则称稀疏引索。

    散列存储:依据数据元素中的关键字,通过散列函数计算出一个地址空间,将数据元素存放到该地址空间中,这种方式即为散列存储。散列函数是指预先设计的能通过关键字计算得到地址空间的函数,该地址成为散列地址。

 

    数据类型:一个值的集合及在该集合上定义的一组操作的统称。

    数据类型可分为原子类型和结构类型。

        原子类型的值不可再分解。

        结构类型是由原子类型或结构类型组成的。

    抽象数据类型:指一个数学模型及定义在该模型上的一组操作。一般可以由元素、关系及操作三个要素来定义。(例:整数类型是一个抽象数据类型,尽管其加减乘除等操作在不同的处理器上实现方式不同,但由于其定义的数学特性相同,在用户看来它们都是相同的。因此,“抽象”的意义在于数据类型的数学抽象特性。)

 

    算法:指解决特定问题的方法步骤的描述。

    算法的5个特性:有穷性、确定性、可行性、输入、输出。

    算法评价标准:正确性、可读性、健壮性、时空效率。

 

    时间复杂度:指算法从运行开始到运行结束的所消耗的时间,一般用算法中所有语句所需的频度之和表示。

    空间复杂度:算法对输入数据进行运算所需的辅助工作单元和存储为实现计算所需信息的辅助空间。

点击复制链接 与好友分享!回本站首页
相关TAG标签 基础知识
上一篇:firefox设置代理服务器时怎样设置才能使得访问局域网时不使用代理
下一篇:获取一个数二进制序列中所有的偶数位和奇数位,分别输出二进制序列
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站