0

Image Description

荆文征

Zhidu Inc.


你好,再见

大话数据结构 - 数据结构绪论 (1)

  • 小酒馆老板
  • /
  • 2017/12/27 14:22:0


H2

数据结构绪论

数据结构: 是相互之间存在一种或多种特定关系的数据元素的集合。


H3

数据结构起源

早起人们都把计算机理解为数值计算工具,就是感觉计算机当然是用来计算的,所以计算机额解决问题,应该先从具体问题抽象成一个适当的数据模型,设计出一个借此数据模型的算法,然后在编写程序,得到一个实际的软件。

可现实中,我们更多的不是解决数值计算的问题,而是需要一些更可可续有效的手段(比如表,树和图等数据结构)的帮助,才能更好的处理问题。所以 数据结构是一门研究非数值计算的程序设计问题中的操作对象,以及它们之间关系和操作等相关问题的学科


H3

基础概念和术语

说到数据结构是什么,我们得先来谈谈什么是数据。
正所谓“巧妇难为无米之炊”,在强大的计算机,也是要有“米”下锅才可以干活儿的,否则就是一堆破铜烂铁,这个“米”就是数据


H4

数据

数据:是描述客观事物的符号,是计算机中可以操作的对象,是能被计算机识别,并输入给计算机处理的符号集合。 数据不仅仅包括整型,实型等数值类型,还包括字符以及声音 图像 视频等非数值类型

比如我们现在常用的搜索引擎,一般会有网页,MP3,图片,视频等分类。MP3就是声音数据,图片当然是图像数据,视频就不用说了,而网页其实指的就是全部数据的搜索,包括最重要的数字和字符等文字数据

也就是说,我们这里说的数据,其实就是符号,而且这些符号必须具备两个前提:

  • 可以输入到计算器中
  • 能被计算机程序处理
    对于整型,实型等数值类型,可以进行数值计算。
    对于字符数据类型,就需要进行非数值的处理。而声音,图像,视频等其实可以通过编码的手段变成字符数据来处理的。

H4

数据元素

数据元素: 是组成数据的,有一定意义的基本单位,在计算机中通常作为整体处理,也被称为记录。
比如,在人类中什么事数据元素呀?当然使人了
畜类呢?牛 吗 羊 鸡 猪 够 等动物当然就是畜类的数据元素。


H4

数据项

数据项:一个数据元素可以有若干个数据项组成
比如人这样的数据元素,可以有眼,耳朵,鼻子,嘴巴,手脚这些数据项,也可以有姓名,年龄,性别出生地址,联系电话等数据项,具体有哪些数据项那个,要是你做的系统来决定。

数据项是数据不可分割的最小单位。 在数据机构这门课程中,我们把数据项定义为最小单位,是有助于我们更好的解决问题。所以,记住了,数据形式数据的最小单位。但是真正讨论问题的时候,数据元素才是数据结构建立数据模型的着眼点,就像我们讨论一部电影时,是要论这部电影角色这样的数据元素,而不是针对这个角色的姓名或者年龄这样的“数据项”去研究分析。


H4

数据对象

数据对象:是性质相同的数据元素的集合,是数据的子集
什么叫性质相同呢。是指数据元素具有相同数量和类型的数据项,比如,还是刚才的例子,人都有姓名,生日,性别等相同的数据项。
既然数据对象是数据的子集,在实际应用中,处理的数据元素通常具有相同性质,在不产生混淆的情况下,我们都将数据对象简称为数据。
好了,有了这些感念的铺垫,我们的主角登场了。
说了数据的定义,那么数据结构中的结构又是什么呢?


H4

数据结构

结构,简单的理解就是关系,比如分子结构,就是说组成分子的原子之间的排列方式。严格点说,结构是指各个组成部分相互搭配和排序的方式。在现实生活中 不同数据元素之间不是独立的,而是存在特定的关系的,我们将这些关系成为结构。 那数据结构是什么?

数据结构:是相关之间存在一种或者多种特定关系的数据元素的集合。

在计算机中,数据元素并不是孤立,杂乱无序的,而是具有内在联系的数据集合。数据元素之间存在的一种或多种特定关系,也就是数据的组织形式。
为编写好一个“好”的程序,必须分析待处理对象的特性及个处理对象之间存在的关系。这也就是研究数据结构的意义存在。

定义中提到的一种或多种特定关系,具体是什么样的关系,这正是我们下面要讨论的问题。


H4

个人理解与总结 数据-数据对象-数据元素-数据项之间的关系

我们首先学习了什么是数据,之后说明了一些名词。那么他们是什么关系呢

                                          数据
                      +--------------------|------------------+
                      |                                       |
                   数据对象                                  数据对象
            +---------|---------+                    +---------|----------+    
            |                   |                    |                    |
         数据元素              数据元素              数据元素               数据元素
      +-----|-----+        +-----|-----+        +-----|-----+        +-----|-----+  
      |           |        |           |        |           |        |           |
  数据项1       数据项2    数据项1     数据项2    数据项1       数据项2   数据项1     数据项2

简单就是说,“耳朵 ,鼻子 嘴巴 ”这些 数据项,组成了“人”这些 数据元素,而人又组成了人类这个 数据对象,而人类是 又是 生物的一个子集,也就是包含 那么生命就是 数据

数据项组成了数据元素,而数据对象是性质相同的数据元素的集合,是数据的子集~~


H3

逻辑结构与物理结构

按照视点的不同,我们把数据结构分为逻辑结构和物理结构


H4

逻辑结构

逻辑结构:是指数据对象之间的相互关系。 其实这也是我们今后最徐耀关注的问题。
逻辑结构分为以下4种:

  1. 集合结构
    集合结构: 集合结构中的元素除了同属于一个集合外,他们之间没有其他关系。各个数据元素是“平等”的,他们的共同属性是“同属于一个集合”。数据结构中的数据关系就类似于数学中的集合

    Image Description
    集合结构示意图
  2. 线性结构
    线性结构:线性结构中的数据元素之间是一对一的关系

    Image Description
    线形结构示意图
  3. 树形结构
    树形结构:树形结构中的数据元素存在一种一对多的层次关系

    Image Description
    树形结构示意图
  4. 图形结构
    图形结构:图形结构中的数据元素存在多对多的关系

    Image Description
    图形结构示意图


    我们在用示意图表示数据的逻辑机构是,要注意两点:
    • 将每一个数据元素看作一个节点,永远泉表示
    • 元素之间的逻辑关系用节点之间的连线表示,如果这个关系是有方向的,那么用带箭头的连线表示

从之前的例子也可以看出,逻辑机构是针对具体问题的,是为了解决某个问题的,在对问题理解的基础上,选择一个合适的数据结构表示数据元素之间的逻辑关系。


H4

物理结构

说完了逻辑结构,我们再来看看物理结构(很多书中也叫存储结构,你只要理解上把他们当作一回事就好了)。
物理结构: 是指数据的逻辑结构在计算机的存储形式
数据是数据元素的集合,那么根据物理结构的定义,实际上就是如何把数据存储到计算机的存储器中,存储器主要是针对内存而言,像硬盘,软盘,光盘等外部的存储器数据组织通常用文件结构来描述。
数据的存储结构应正确反应数据元素之间的逻辑关系,这才是最关键的,如何存储数据元素之间的逻辑关系,是实现物理结构的重点和难点。

数据元素的存储结构形式有两种: 顺序存储和链式存储。

  1. 顺序存储结构
    顺序存储结构: 是把数据元素存储在地址连续的存储单元里,其数据见的逻辑关系与物理关系是一致的。

    Image Description
    顺序存储结构示意图

    这种存储结构其实很简单,说白了,就是排队占位。大家都按顺序排好,每个人,占一小段空间,大家谁也别插谁的队。我们之前学计算机语言时,数组就是这样的顺序存储结构。当你告诉计算机,你要建立一个又9个整型数组时,计算机就在内存找了一片空地,按照一个模型所占的位置乘以9,开辟一段连续的空间,于是第一个就放在第一个位置,第二个数据就放在第二个,这样依次摆放。
  2. 链式存储结构
    如果就是这么简单和有规律,一切就都好办了。可实际上,又会有人插队,也会有人要上厕所,有人放弃排队。所以这个队伍当中会添加新成员,也有可能会去掉老成员,整个结构时刻都处于变化中。显然,面对这样市场要变化的结构,顺序存储是不科学的。那怎么办呢?
    现在如银行,医院等地方,设置了排队系统,也就是每个人去了,限领一个号,等着叫号,叫到时去办理业务或看病。在等待的时候,你爱在哪儿在哪儿,可以坐着,站着或者走动,甚至出去逛一圈,只要及时赶回来就行。你关注的是前一个号有没有被叫到,叫到了,下一个就轮到了。
    链式存储结构:是把数据元素存放在任意的存储单位中,这组存储单元可以是连续的,也可以是不连续的。 数据元素的春初关系并不能反映其逻辑关系,但是需要用一个指针存放数据元素的地址,这样通过地址就可以找到相关数据元素的位置

    Image Description
    链式存储结构示意图

    显然,链式存储就灵活多了,数据存放哪里不重要,只要有一个指针,存放了相应的地址就能找到他了。

逻辑结构是面向问题的,而物理结构是面向计算机的,其基础的目标就是将数据及其逻辑关系存到计算机的内存中。

先说说,逻辑结构和物理结构。书上总结的已经很好了。

逻辑结构是面向问题的,而物理结构是面向计算机的。

其实简单来说就是, 如果把人类存储起来,那么 按照他们的籍贯。还是年龄大小。还是之间的亲戚关系。这种叫做 逻辑结构。
如果是把人放到 放在广场。是排队还是随便走动,这个是物理结构。。。感觉解释的还是不行。。。

顺序结构和 链式结构的区别和相同

我就一展示数据的表格
名称 不同点
顺序存储结构 顺序结构是连续的内存地址,所以数量必须提前定好。
链式存储结构 链式存储是非连续内存地址,只需要知道下一个数据元素在那里就好了,所以理论上在内存不满之前是无限个个数的

H3

抽象数据类型


H4

数据类型

数据类型:是指一组性质相同值的集合及定义在此集合上的一些操作的总称
数据类型是按照值的不同进行划分的。在高级语言中,每个变量,常量和表达式都有各自的取值范围。类型就用来说明变量或表达式的取值范围和所能进行的操作。
当年那些设计计算机语言的人,为什么会考虑到数据类型呢?
比如,大家都需要住房子,也都希望房子越大越好。很显然,没有钱,考虑房子没啥意义。于是商品房就出现了各种各样的方形,有别墅的,有错层的,有单间的。有一百多平的,也有几十平的,甚至北京还出了胶囊公寓。这眼就满足了不同人的需求。
同样,在计算机中,内存也不是无限大的,你要计算一个1+1=2,3+5=8的这样的整型数字的减价运算,显然不徐耀开辟很大的适合小数甚至字符运算的内存空间。于是计算机的研究者门就考虑,要对数据进行分类,分出来多种数据类型。

在C语言中,按照取值的不同,数据可以分为两类

  • 原子类型: 是不可以在分解的基本类型,包括 整型,实型,字符型等。
  • 结构类型: 是由若干各类型组合而成,是可以在分解的。例如,整型数组是有若干整型数据组成。

比如,在C语言中变量生变int a,b ,这就意味着,再给变量a和b复制时不能超出 int 的取值范围,变量a和b之间的运算也只能是int类型所允许的运算。
因为不同的计算机有不同的硬件系统,这就要求程序语言最终通过编译器或者解释器转换成底层语言,如汇编语言甚至是通过机器语言的数据类型来实现的。可事实上,高级语言的编程者不管最终程序原型在什么计算机上,他的目的就是为了实现两个整型数字的运行,如 a+b,a-b,axb,a/b等,他才不关系证书在计算机内部是如何表示的,也不需要知道,CPU为了实现1+2进行了几次开关操作,这些操作是如何实现的,对高级语言开发者来讲根本不重要。于是我们就会考虑,无论什么计算机,什么计算机语言,大都会面临着 整数运算,实数运算,字符运算等操作我们可以考虑把他们抽象出来

抽象是指抽取出食物具有的普遍性的本质。 它是抽出问题的特征而忽略非本质的细节,是对具体事物的一个概括。抽象是一种思考问题的方式,它隐藏了繁杂的细节,只保留了实现目标所需的信息。


H4

抽象数据类型

我们对已有的数据类型进行抽象,就有了抽象数据类型。
抽象数据类型(Abstract Data Type,ADT):是指一个数据模型以及定义在该模型的一组操作。 抽象数据类型的定义仅取决于他的一组逻辑特性,而与其在计算机内部如何表示和实现无关。
比如刚才的例子,各个计算机,不管是大型机,小型机,PC,平板电脑,PDA甚至智能手机都有“整数”类型,也需要整数间的运算,那么整形其实就是一个抽象数据类型,尽管他在上面提到的这些不同计算机中实现方法不一样,但是由于其定义的数学特性相同,在计算机编程者看来,他们都是相同的。因此,“抽象”的意义在于数据类型的数学抽象特性
而且,抽象数据类型不仅仅指那些已经定义并实现的数据类型,还可以是计算机编程者在设计软件程序时自己定义的数据类型,比如我们便携计算机绘图或者地图累的软件系统,经常会用到坐标,也就是说,总是有成对出现的X和Y,在3D的软件中甚至会出现Z。既然这三个整型数字是始终出现在在一起出现,我们就定一个叫 point的抽象属类型,他有XYZ三个整型变量,这样我们很方的操作一个point数据变量就能知道这一点的坐标了。

根据抽象数据类型的定义,它还包括定义在该模型的一组操作。就像“超级玛丽”这个经典的任天堂游戏,里面的游戏主角是马里奥(Mario)。我们给他定义了几个基本操作,走(前进,后退,上,下)跳,打子弹等。一个抽象数据类型定义了:一个数据对象,数据对象中个数据元素之间的关系及数据元素的操作。至于,一个抽象数据类型到底需要那些操作,这就只能由设计者根据实际需要来定。像马里奥,可能开始只有两种操作,走和跳,后来发现应该要增加一种打子弹的操作,再后来发现有些玩家希望他可以走的快一点,就有了按住子弹后前进就会“跑”的操作。这些都是根据实际情况来设计的

事实上,抽象数据类型体现了程序设计中问题分解,抽象和信息隐藏的特性。抽象数据类型把实际生活中的问题分解为多个规模小且容易处理的问题,然后建立一个计算机能处理的数据模型,并把每个功能模块的实现细节都作为一个独立的单位,从而使具体的实现过程隐藏起来。

为了便于我们在之后的讲解中对抽象数据进行规范的描述,我们给出了描述对象书库类型的标准格式:

/// 抽象数据类型
Class ADT{
    /// 数据元素之间的逻辑关系的定义
    let data1
    let data2
    /// 操作
    func oper1{}
    func oper2{}
}

H3

总结回顾

数据结构的相关结构


Image Description
数据结构概念图

由这些概念,给出了数据结构的定义:数据结构是相互之间存在的一种或多种特定关系的数据元素的集合。 同样是结构,从不同的角度讨论会有不同的分类。


Image Description
结构分类示意图

总结:

  1. 数据 是有数据元素 或者 数据对象构成,数据对象是由特性一样的一群数据元素构成,一个或者多个数据项构成了数据元素
  2. 数据结构按照 分类有两种结构,逻辑结构和物理结构。 逻辑结构多表示数据见的逻辑关系,包含(1.集合机构(无关系)2.线性关系(一对一)3.树性关系(一对多)4.图形关系(多对多))等。而物理结构,则是其存储在计算机的存储器中的无力位置来定的。(比如:必须在连续的内存地址中的 顺序存储结构,以及相对应的 不要再连续地址中的 链式存储结构)
  3. 计算器的数据存储器是内存,硬盘等存储,存储的是文件结构。
  4. 抽象数据类型是为了规定某一种数据元素的 取值 以及 操作。这个还不是非常明白。但是大概就是 目前我们所学的对象。比如 人抽象承认,那么他就是一个人,需要由消化系统等变量,当然还需要拥有,呼吸,眨眼等操作
专栏: 数据结构
标签: 数据结构 计算机基础