【数据结构】(1)概述

【数据结构】(1)概述

一、概述

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

简单理解,学习数据结构就学习数据的存储方式。

二、作用

为了方便后期对数据的再利用

数据结构作用:为了方便后期对数据的再次利用

例:

  • 我们有一组数字{1, 2, 3, 4, 5}。我们可以用 数组(顺序表结构)来存储数据。方便后期对数据的再次利用。

  • 但是,如果是这样的数据呢?

具有有复杂关系的数据,如果此时还是用数组来进行存储,很显然是不明智的。这些数据存储没有问题,但是无法体现数据之间的逻辑关系,并不方便再次利用。切记 **无缘由的数据存储行为是对存储空间的不负责任** 。 对于上面此中类型的数据,数据结构中有提供专门的**树结构**来存储此类数据。

我们学数据结构就是学习:如何存储具有复杂关系的数据,以方便后期对数据的再次利用


三、数据结构(逻辑结构与物理结构)

1.逻辑结构

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

逻辑结构包括:

  • 集合:数据结构中的元素之间除了“同属一个集合” 的相互关系外,别无其他关系;
  • 线性结构:数据结构中的元素存在一对一的相互关系;
  • 树形结构:数据结构中的元素存在一对多的相互关系;
  • 图形结构:数据结构中的元素存在多对多的相互关系。

逻辑结构就是指数据与数据之间的关系(逻辑上关系,和计算机存储存储无关)。例如,父母子女关系。老师同学关系,家族谱中每个人(数据)之间的关系。

2.物理结构(也称存储结构)

指数据的逻辑结构在计算机存储空间的存放形式。

数据的物理结构是数据结构在计算机中的表示(又称映像),它包括数据元素的机内表示和关系的机内表示。由于具体实现的方法有顺序、链接、索引、散列等多种,所以,一种数据结构可表示成一种或多种存储结构。

就是数据在计算机中的存储结构(称为物理结构或存储结构)。一种数据结构(数据的逻辑结构)可以表示为一种或多种存储结构。也就是说,一种数据结构,在计算机中有一种或多种存储方式。


四、数据结构分类

数据结构有很多种,一般来说,按照数据的逻辑结构对其进行简单的分类,包括线性结构和非线性结构两类。

数据结构有多种,就是上面 数据的逻辑结构 讲的四种。不过一般简单分类成了两类:线性结构和非线性结构。

1.线性结构

简单地说,线性结构就是表中各个结点具有线性关系。如果从数据结构的语言来描述,线性结构应该包括如下几点:

  • 1.线性结构是非空集。
  • 2.线性结构有且仅有一个开始结点和一个终端结点。
  • 3.线性结构所有结点都最多只有一个直接前趋结点和一个直接后继结点。

线性表就是典型的线性结构,还有栈、队列和串等都属于线性结构。

线性结构就是,数据结构中的元素存在 一对一的相互关系

如:线性表(顺序存储( 数组 ), 链式存储( 链表 ))、栈、队列、串都属于线性结构。

2.非线性结构

简单地说,非线性结构就是表中各个结点之间具有多个对应关系。如果从数据结构的语言来描述,非线性结构应该包括如下几点:

  • 1、非线性结构是非空集。
  • 2、非线性结构的一个结点可能有多个直接前趋结点和多个直接后继结点。

在实际应用中,数组、广义表、树结构和图结构等数据结构都属于非线性结构。

非线性结构就是,数据结构中的元素存在 多个对应关系

如:二维及多维数组、树、图。

四、常见的数据结构

在计算机科学的发展过程中,数据结构也随之发展。程序设计中常用的数据结构包括如下几个

  • 数组(Array)
  • 链表( Linked List)
  • 栈( Stack)
  • 队列(Queue)
  • 树( Tree)
  • 图(Graph)
  • 堆(Heap)
  • 散列表(Hash)

以上这些都是一些常见的数据结构,在程序设计中我们也会经常用到。


五、常用算法(数据运算)

数据结构研究的内容:就是如何按一定的逻辑结构,把数据组织起来,并选择适当的存储表示方法把逻辑结构组织好的数据存储到计算机的存储器里。
研究的目的是为了更有效的处理数据,提高数据运算效率。
数据的运算是定义在数据的逻辑结构上,但运算的具体实现要在存储结构上进行。一般有以下几种常用运算:

  • (1)检索。检索就是在数据结构里查找满足一定条件的节点。一般是给定一个某字段的值,找具有该字段值的节点。
  • (2)插入。往数据结构中增加新的节点。
  • (3)删除。把指定的结点从数据结构中去掉。
  • (4)更新。改变指定节点的一个或多个字段的值。
  • (5)排序。把节点按某种指定的顺序重新排列。例如递增或递减。

1.检索(查找)

  • 顺序查找
  • 二分查找
  • 哈希查找

2.排序

  • 插入排序
  • 冒泡排序
  • 选择排序
  • 希尔排序
  • 快速排序
  • 堆排序
  • 归并排序

参考

数据结构概述:http://data.biancheng.net/intro/

数据结构百度百科:https://baike.baidu.com/item/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/1450?fr=aladdin#4

《软件设计师考试32小时通关》第3小时:数据结构与数据运算