码农小屋 码农小屋
  • 首页
  • 文章
    • Python
    • 计算机基础
    • C语言
    • Java
    • 数据库
    • Linux
  • 资源
  • 随笔
  • 优秀软件
  • 24h新鲜事
  • 专题
  • 留言板
  • 注册 登录
立即登录
0文章
0评论
0获赞
  • 首页
  • 博客中心
    • 文章
    • 资源
  • 随笔
  • 优秀软件
  • 24h新鲜事
  • 专题
  • 留言板
主页 › 文章 › 计算机基础 › 数据结构——绪论
#计算机基础#

数据结构——绪论

4月前
66 0 2

数据结构形成和发展的背景

目前计算机的应用已不再局限于科学计算,而更多的用于控制、管理及数据处理等非数值计算的处理工作。与此相应,计算机加工处理的对象由纯粹的数值发展到字符、表格和图像等各种具有一定结构的数据,这给程序设计带来了一些新的问题。为了编出一个“好”的程序,必须分析待处理的对象的特性以及各处理对象之间存在的关系。

数据结构的定义

一般来说,用计算机解决一个具体问题时,大致需要经过下列几个步骤:

  • 首先要从具体问题中抽象出一个适当的数学模型
  • 然后设计一个解此数学模型的算法
  • 最后编写出程序、进行测试、调整直至得到最终解答

寻求数学模型的实质是分析问题,从中提取操作的对象,并找出这些操作对象之间的关系,然后用数学语言加以描述。有些问题的数据模型可以用具体的数学方程等来表示,但更多的实际问题是无法用数学方程来表示的,这就需要从数据人手来分析并得到解决问题的方法。

基本概念和术语

数据(data)

数据是对客观事物的符号表示。在计算机科学中其含义是指所有能够输入到计算机中并被计算机程序处理的符号集合。

数据元素(data element)

  • 是数据的基本单位,在计算机程序中通常作为一个整体进行考虑和处理。例如“树”中的一个棋盘格局,“图”中的一个圆圈都是一个数据元素。
  • 数据元素又被称为元素、结点(node)或记录(record)。

数据项(data item )

  • 一个数据元素可以由若干个数据项组成,例如一本书的书目信息为一个数据元素,而书目信息中的每一项(书名、作者等)为一个数据项。
  • 数据项是数据不可分割的最小单位。

数据结构(data structure)

数据结构是指所有数据元素以及数据元素之间的关系,可以看作是相互之间存在着某种特定关系的数据元素的集合,我们可以把数据结构看成是带结构的数据元素的集合。

数据结构通常包括以下几个方面:

(1)数据的逻辑结构( logical structure): 由数据元素之间的逻辑关系构成。

(2)数据的存储结构(storage structure):数据元素及其关系在计算机存储器中的存储表示,也称为数据的物理结构( physical structure)。

(3)数据的运算(operation): 施加在该数据上的操作。

逻辑结构

数据的逻辑结构可以采用多种方式表示,常见的有图表和二元组等。

图表表示

逻辑结构的图表表示就是采用表格或者图形直接描述数据的逻辑关系。

二元组表示

二元组是一种通用的逻辑结构表示方法。一个二元组表示为:

      B=(D,R)

      其中,B是一种数据结构,它由数据元素的集合D和D上二元关系的集合R所组成。其中:

      D={ di | 1≤i≤n,n≥0}:数据元素的集合

      R={ rj  | 1≤j≤m,m≥0}:关系的集合   

每个关系的用若干个序偶来表示:

  • 序偶<x,y>(x,y∈D)Þ x为第一元素,y为第二元素。
  • x为y的前驱元素。
  • y为x的后继元素。
  • 若某个元素没有前驱元素,则称该元素为开始元素;若某个元素没有后继元素,则称该元素为终端元素。

序偶<x,y>表示x、y是有向的,序偶(x,y)表示x、y是无向的。

逻辑结构的类型

(1)集合

(2)线性结构

(3)树形结构

(4)图(网)状结构

集合

元素之间关系:无。

特点:数据元素之间除了“属于同一个集合”的关系外,别无其他逻辑关系。是最松散的,不受任何制约的关系。

线性结构

元素之间关系:一对一。

特点:开始元素和终端元素都是唯一的,除此之外,其余元素都有且仅有一个前驱元素和一个后继元素。

树形结构

元素之间关系:一对多。

特点:开始元素唯一,终端元素不唯一。除终端元素以外,每个元素有一个或多个后续元素;除开始元素外,每个元素有且仅有一个前驱元素。

图形结构

元素之间关系:多对多。

特点:所有元素都可能有多个前驱元素和多个后继元素。

存储结构

数据逻辑结构在计算存储器中的存储表示称为数据的存储结构(也称为映像),也就是逻辑结构在计算机中的存储实现。当把数据对象存储到计算机中时,通常要求既要存储逻辑结构中的每一个数据元素,又要存储数据元素之间的逻辑关系。

常见的存储结构

顺序存储结构:特点是借助于数据元素的相对存储位置来表示数据元素之间的逻辑关系;

链式存储结构:特点是借助于指示数据元素地址的指针表示数据元素之间的逻辑关系。

结论

  • 可以用所有高级语言中都有的“数组”类型来描述顺序存储结构
  • 以C语言提供的“指针”来描述链式存储结构

写在最后

数据结构——绪论-码农小屋
2
独家记忆
相关文章
算法时间复杂度和空间复杂度简介
计算机的基本组成
HTTP协议报文结构
线性表的顺序和链式存储结构
数据结构——线性表
评论 (0)
再想想
独家记忆作者
一个爱学习的程序猿
28文章 2评论 29获赞
文章推荐
ZIP Pro 3 – 文件压缩分享加密管理套件
2月前
Uninstall Tool-专业的软件卸载工具
3月前
Speccy:优秀的硬件检测工具
4月前
CleanMyPC-专为 Windows打造的清理工具
4月前
Internet Downloader Manager-一款专业的Win下载工具
4月前
Wise Care 365-Windows 系统清理和加速工具
4月前
新鲜事
新Mac太牛:在电脑上运行iPhone、iPad的软件、游戏
2月前
自从苹果M1芯片发布之后,使用这颗芯片的Mac电脑,就被大家认为是有史以来最强的Mac,因为这颗小米的芯片,在性能上已经打败了苹果使用的最高端的i9芯 ...[阅读全文]
苹果发布会总结:一个芯片,三款产品!苹果这把棋下得可真深
2月前
北京时间11月11日凌晨2点,苹果在圣何塞召开了本年度最后一场发布会。在这次发布会上,苹果推出了基于ARM架构的全新M1自研处理器。 ...[阅读全文]
荣耀命运落定:救了自己,也救华为
2月前
华为出售荣耀一事终于落槌。 ...[阅读全文]
发布会停不下来,苹果下月发布新Mac
3月前
今年的苹果有些与众不同,往年只开一次秋季发布会,今年在九月十月连开两场。 ...[阅读全文]
iPhone 12 开启 5G 续航锐减,苹果回应
3月前
对于今年的 iPhone 12 来说,除了回归直角边框设计之外,最大的亮点就是 5G 了。 ...[阅读全文]
华为Mate40正式发布
3月前
定位高端旗舰的华为Mate40系列共发布四款新机:华为Mate40(6.5英寸)、华为Mate40 Pro(6.76英寸)、华为Mate40 Pro+ ...[阅读全文]
更多
  • 专题
  • 文章
  • 友情链接
  • 留言板
Copyright © 2020-2021 码农小屋. 苏ICP备20033168号