数据结构与算法——绪论

数据结构与算法——绪论

    • 前言
      • 什么是数据结构?
      • 数据结构能干什么?
    • 数据结构基本概念
      • 数据
      • 数据元素
      • 数据项
      • 数据结构
      • 数据对象
    • 数据结构三要素
      • 逻辑结构
        • 线性结构
        • 树形结构(树)
        • 图形结构(图)(网状结构)
        • 集合
      • 存储结构(物理结构)
        • 顺序存储
        • 链式存储
        • 索引存储
        • 散列存储
      • 数据的运算
      • 数据类型、抽象数据类型
        • 数据类型
        • 抽象数据类型(ABstract Data Type ADT)
    • 总结

前言

数据结构与算法在计算机行业领域可以说运用很广泛,特别是算法,编程少不了算法,而数据结构呢,要求小伙伴们更多的是要掌握扎实的理论知识,所以,接下来,我也会持续不断学习数据结构与算法的内容,然后坚持总结创作出对小伙伴们有帮助的文章,希望我们共同进步。

数据结构与算法——绪论_第1张图片

什么是数据结构?

数据结构(data structure)是带有结构特性的数据元素的集合,它研究的是数据的逻辑结构和数据的物理结构以及它们之间的相互关系,并且对这种结构定义相适应的运算,设计出相应的算法,并确保经过这些运算以后得到的新结构仍保持原来的结构类型,简单理解就是,数据结构是相互之间存在一种或多种特定关系的数据元素的集合,即带“结构”的数据元素集合,“结构”指的就是数据元素之间所存在的关系,分为逻辑结构和存储结构。

数据结构能干什么?

数据结构是一门抽象、研究数据集合与集合中元素关系的学科,那学习数据结构与算法能干什么呢,其实数据结构与我们的生活息息相关。

比如说,我们平时去餐厅吃饭一般都要经过:取号——排队——叫号——进场吃饭这几个环节,程序要实现这一系列流程,自然少不了数据结构与算法中的队列

数据结构与算法——绪论_第2张图片

再比如说,如果让你把自己的社交关系表示出来,该如何表示?这时候,就可以用数据结构中的来表示。

数据结构与算法——绪论_第3张图片

所以,简而言之,学习数据结构并不是学习具体的技术与编程语言基础,更多的,是锻炼学习者的思维逻辑和理解能力,提供学习者一种编程的思想,在程序编写中能有更高效更好的编程思路。


数据结构基本概念


数据

数据是信息的载体,是描述客观事物属性的数、字符及所有能输入到计算机中并能被计算机识别和处理的符号的集合。

数据元素

简单理解,数据元素就是一个集合,数据元素是数据的基本单位,通常情况下作为一个整体来考虑和处理

数据项

数据项是构成数据元素不可分割的最小单位,一个数据元素由若干个数据项构成

怎么来理解数据元素和数据项之间的关系呢,其实很简单,举个例子,把数据元素看做一个班级,而组成这个班级的学生就好比数据项,不同的学生就构成了班级这个集合。那再换个角度看一看,每个学生又是一个数据元素,而学生的身高、年龄、身份证号等等数据项由构成了不同学生的数据元素。

数据结构与算法——绪论_第4张图片

数据结构

所谓的结构就是各个元素之间的关系,那数据结构表达的就是相互之间存在一种或多种特定关系的数据元素的集合,是计算机存储,组织数据的方式

数据对象

数据对象是具有相同性质的数据元素的集合,是数据的一个子集


总结关系:数据项 < 数据元素 < 数据对象< 数据


数据结构三要素


逻辑结构

  • 线性结构
  • 非线性结构
    • 树形结构
    • 图形结构(网状结构)
    • 集合

线性结构

数据元素之间是一对一的关系。除了第一个元素,所有元素都有唯一前驱,除了最后一个元素,所有元素都有唯一后继。

数据结构与算法——绪论_第5张图片

树形结构(树)

数据元素之间是一对多的关系

数据结构与算法——绪论_第6张图片

图形结构(图)(网状结构)

数据元素之间是多对多的关系

数据结构与算法——绪论_第7张图片

集合

各个元素同属于一个集合,除此之外别无其他关系

数据结构与算法——绪论_第8张图片

存储结构(物理结构)

存储结构分为

  • 顺序存储
  • 链式存储
  • 索引存储
  • 散列存储

顺序存储

把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中,元素之间的关系是由存储单元的相邻关系来体现的。线性结构中的顺序表就是顺序存储的表现形式。采用顺序存储,那么也就要求在内存上要开辟一片连续的存储空间。用来存放数据元素。所以逻辑上有关系的元素占用一片连续的存储空间。

链式存储

逻辑上相邻的元素在物理位置上可以不相邻,借助指示元素存储地址的指正来表示元素之间的逻辑关系,所以,链式存储是通过指针指向来表现出元素的逻辑关系,在链式存储中,指针是一个重要的点。

索引存储

在存储元素信息的同时,还要建立附加的索引表,索引表中的每向称为索引项,索引项一般形式是(关键字、地址)

散列存储

根据元素的关键字直接计算出该元素的存储地址,又称为哈希(Hash)存储。散列表就是散列存储的具体表现。

总结
若采用顺序存储,则各个数据元素在物理上必须是连续的;若采用非顺序存储,那么对数据存放的位置没有什么强制要求,可以连续,也可以分散存储。


数据的存储结构会影响存储空间分配的方便程度。采用顺序存储,那么在内存上只需要开辟一片连续的空间即可,空间分配速度较快,若采用非顺序存储,那么在内存开辟空间时不仅仅要开辟元素存放空间,还要开辟用于存储链接元素关系的指针或是索引。空间分配速度较顺序存储相对慢一些,且空间利用率低于顺序存储


数据的存储结构也会影响对数据运算的速度,不同的存储结构,在进行数据操作时所耗费的时间也不同

数据的运算

施加在数据上的运算包括运算的定义和实现,运算的定义是针对逻辑结构指出运算的功能;运算的实现是针对存储结构的指出运算的具体操作步骤。

数据类型、抽象数据类型


数据类型

数据类型是一个值的集合和定义在此集合上的一组操作的总称

  • 原子类型。其值不可在分的数据类型
    • int
    • bool
    • string
    • float
    • 等等

  • 结构类型。其值可以在分解为若干成分(分量的数据类型)
    • 结构体

抽象数据类型(ABstract Data Type ADT)

  • 高级的数据类型
  • 是数据对象,对象上的关系,和对象的基本操作封装在一起的一种表达方式
  • 可以用来独立的定义数据结构
  • 包含:数据对象集D,数据关系集S,基本操作集P
  • 三元组表示法:ADT=(D,S,P)

抽象数据类型是抽象数据组织及与之相关的操作。其用数学化的语言定义数据的逻辑结构、定义运算。与具体的实现无关。


总结

到此,对数据结构与算法绪论章节的数据结构的基本概念就结束了,接下来我也会持续更新剩下的内容,在本篇文章中,所涉及的知识点都比较抽象,不太让人容易理解,所以我也采用图形、举例的方式帮助小伙伴们理解,对于表述错误或是表述不清的地方还望小伙伴们见谅。

觉得不错的话记得点赞收藏呀!!

别忘了给我关注~~

你可能感兴趣的