ITKeyword,专注技术干货聚合推荐

注册 | 登录

数据结构-概述(1)

hejingyuan6 分享于 2014-05-12

推荐:数据与数据结构

数据与数据结构 1. 数据 1.1 数据(data) 数据:是信息的载体,是描述客观事物的数、字符,以及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。 1.2

2020腾讯云共同战“疫”,助力复工(优惠前所未有!4核8G,5M带宽 1684元/3年),
地址https://cloud.tencent.com/act/cps/redirect?redirect=1053

2020阿里云最低价产品入口,含代金券(新老用户有优惠),
地址https://www.aliyun.com/minisite/goods


    数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下,精心选择的数据结构可以带来更高的运行或者存储效率。


             


数据的逻辑结构:指反映数据元素之间的逻辑关系的数据结构,其中的逻辑关系是指数据元素之间的前后件关系,而与他们在计算机中的存储位置无关。

 

通常有下列四类基本的结构:

⑴集合结构。该结构的数据元素间的关系是“属于同一个集合”。

⑵线性结构。该结构的数据元素之间存在着一对一的关系。

⑶树型结构。该结构的数据元素之间存在着一对多的关系。

⑷图形结构。该结构的数据元素之间存在着多对多的关系,也称网状结构。

从上面所介绍的数据结构的概念中可以知道,一个数据结构有两个要素。一个是数据元素的集合,另一个是关系的集合。

对于线性结构,树型结构和图形结构的关系,如图:


        


数据的存储结构(物理结构):

 

数据的存储结构是指数据的逻辑结构在计算机中的表示。有四种基本的存储映像方法:顺序、链接、索引、散列。

 

1.顺序存储

 

主要用于线性的数据结构,它把逻辑上相邻的结点存储在物理上相邻的存储单元里,结点之间的关系由存储单元的邻接关系体现。

如图:


        


2.链式存储

 

就是给结点附加上指针字段。即,将结点所占的存储单元分为两部分:

 

(1)数据项  存放结点本身的信息。

(2)指针项  存放此结点的后继结点所对应的存储单元的地址。

 

指针项可以包括一个或多个指针,以指向结点的一个或多个后继,或记录其他信息。

推荐:数据结构——栈

说明:严蔚敏的《数据结构》(C语言版)学习笔记,记录一下,以备后面查看。 如上图所示,刚开始base指针和top指针都指向栈低,当压栈的时候,top指针向上移动,

 

如图:


        


顺序与链式对比:

 

1、比顺序存储结构的存储密度小(每个节点都由数据域和指针域组成,所以相同空间内假设全存满的话顺序比链式存储更多)。

2、逻辑上相邻的节点物理上不必相邻。

3、插入、删除灵活(不必移动节点,只要改变节点中的指针)。

4、查找结点时链式存储要比顺序存储慢。

5、每个结点是由数据域和指针域组成。

 

 

3.索引存储

 

在线性结构中,结点可以排成一个序列:p1,p2,…,pn,每个结点pi在序列里都有对应的位置I,这个位置数就可以作为结点的索引。

 

索引的存储结构:是用结点的索引号i来确定结点的存储地址。有2种实现方法:

 

(1)建立附加的索引表,索引表里第i项的值就是第i个结点的存储地址。

(2)当每个结点所占单元个数都相等时,可用位置数的线性函数的值来指出结点对应的存储地址,即第i个结点pi的地址是LOC(pi)=(i-1)*p+q。其中,p为结点所占的单元个数,q为开始结点p1对应的存储地址。

 

 

4.散列存储

 

散列存储,又称hash存储,是一种力图将数据元素的存储位置与关键码之间建立确定对应关系的查找技术。散列法存储的基本思想是:由节点的关键码值决定节点的存储地址。散列技术除了可以用于查找外,还可以用于存储。

 

总结:

 

对于数据结构的逻辑结构和物理结构的简单解释:

逻辑结构:数据元素之间的逻辑关系,即人对数据的理解,而进行抽象的模型。

物理结构:数据元素在计算机中的存储方法,即计算机对数据的理解,逻辑结构在计算机语言中的映射。

 

以上所述只是为了让大家对数据结构这个概念有一个全局的认识,便于我们对知识的理解,这样我们就不需要记忆知识,而是利用简单的结点去扩展整个知识网络!

 


 

推荐:数据结构 --- 图

一、基本术语 图:由有穷、非空点集和边集合组成,简写成G(V,E); Vertex:图中的顶点; 无向图:图中每条边都没有方向; 有向图:图中每条边都有方向; 无向边:

    数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下,精心选择的数据结构可以带来更高的运行或者存储效率。              

相关阅读排行


相关内容推荐

最新文章

×

×

请激活账号

为了能正常使用评论、编辑功能及以后陆续为用户提供的其他产品,请激活账号。

您的注册邮箱: 修改

重新发送激活邮件 进入我的邮箱

如果您没有收到激活邮件,请注意检查垃圾箱。