《大话数据结构》学习笔记-day01-数据结构

程序设计 = 数据结构 + 算法

“巧妇难为无米之炊”,再强大的计算机,也是要有”米”下锅才可以干活,否则就是一堆破铜烂铁,这个”米”就是数据

一, 基本概念和术语

1.1 数据

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

整型(int,Long….)：整形简单来说就是整数，比如1，2，3等。整形数据可以分为长整型和短整型。

实型(char,double….)：实际就是浮点数，分为 单精度浮点数 和 双精度浮点数 。通俗来说就是带有小数点的数字，比如1.12，2.0等。

字符型(String….)：字符型量包括字符常量和字符变量。字符常量通常用单引号标注，如‘a’,’’b’等。字符变量用char 说明。

​ 其实数据,其实就是符号,而这些符号必须具备两个前提

• 可以输入到计算机中
• 能被计算机程序处理

对于整型,实型等数据类型,可以进行数值计算,

对于字符数据类型,就需要进行非数值的处理,而声音 图像 视频 等 其实是可以通过编码的手段变成字符数据来处理的

1.2 数据元素

是组成数据的,有一定意义的基本单位,在计算机中通常作为整体处理,也被称为记录

比如,在人类中,什么是数据元素? 当然是人啊!

畜类呢? 牛 马 羊 鸡 猪 等动物都是禽类的数据元素

1.3 数据项

​ 数据项 : 一个数据元素可以由若干数据项组成

数据元素 人 : 可以有 五官 这些数据项,也可以有 姓名 年龄 性别 出生地址 联系方式等数据项,

具体有哪些数据项,要看你的需求了

​ 数据项是数据不可分割的最小单位,把它定义成最小单位,是有助于我们更好的解决问题,所以要记住,真正讨论问题时,数据元素才是数据结构中建立数据模型的着眼点,是讨论这部电影角色这样的”数据元素”,而不是针对这个角色的姓名 年龄这样的”数据项”去研究分析

1.4 数据对象

​ 数据对象: 是性值相同的数据元素的集合,是数据的子集, 比如人有 名字 性别 爱好 身高 等数据项,在实际应用中,处理的数据元素通常具有相同性质,在不产生混淆的情况下,我们都将数据对象成为数据

1.4 数据结构

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

结构是指各个组成部分相互搭配和排列的方式,现实世界中,不同数据元素之间不是独立的,而是存在特定关系,我们称这些关系为结构

计算机中,数据元素不是杂乱无序的,而是具有内在联系的数据集合,数据元素之间存在的一种或多种特定关系,也是数据的组织形式

二, 逻辑结构与物理结构

1.逻辑结构

数据对象中数据元素之间的相互关系

• 集合结构

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

  

• 线性结构

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

  

• 树性结构

  • 数据元素之间存在一种一对多的层次关系

  

• 图形结构

  • 对多关系

  

2.物理结构

数据的逻辑结构再计算机中的存储形式

很多书中叫做存储结构,理解成一回事就行

​ 数据是数据元素的集合,那么根据物理结构的定义,实际上就是如何把数据元素存储到计算机的存储器中,存储器主要针对内存而言, 像硬盘 软盘 光盘等外部存储的数据组织通常用文件结构来描述

​ 数据的存储结构应正确的反应数据元素之间的逻辑关系,这才是最为关键的,如何存储数据元素之间的逻辑关系,是实现物理结构的重点和难点

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

顺序结构:

数据元素放在地址连续的存储单元里,其数据间的逻辑关系和物理关系是一致的

说白了,就是排队占位,大家都按顺序排好队,谁也不能插队,每个人有自己的空间

数组就是这样的顺序存储结构

链式存储结构:

​ 事实上不是所有人都很有素质,有的人会喜欢插队,面对时常变化的结构,顺序存储是不科学的,怎么办?

​ 比如银行 医院设置了排队系统,给你一个号码,你愿意去哪就去哪,到时候叫你你就过去

链式存储结构: 是把数据元素存放在任意的存储单元里,这组存储单元可以是连续的,也可以是不连续的

​ 链式存储灵活多了,数据在哪不重要,只需要一个指针存放了相应地址就可以找到它

三, 抽象数据类型

1. 数据类型

数据类型: 是指一组性质相同的值的集合及定义在此集合上的一些操作的总称

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

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

抽象是指抽取出事务具有的普遍性的本质

抽象是一种思考问题的方式,它隐藏了繁杂的细节,只保留实现目标所必须的信息

2. 抽象数据类型

抽象数据类型(Abstract Data Type,ADT) : 是指一个数学模型及定义在该模型上的一组操作,抽象数据类型的定义仅仅取决于它的一组逻辑特性,而与其计算机内部如何表示和实现无关

​ 电脑手机平板等都拥有 “整数”类型,尽管不同的计算机中实现方法不一样,但由于其定义的数学特性相同,在开发者看来,他们都是相同的,因此, “抽象”的意义在于数据类型的数学抽象特性

​ 不仅仅是已经定义并实现的数据类型,还可以是开发者自己定义的类型,比如:

• 定义坐标 x,y,z

  坐标中总会有成对的x,y出现,再3d中还会有z的出现,既然他们始终都会出现,那我就定义一个point的抽象数据类型,他有 x y z三个整型变量,这样我们很方便地操作一个 point 数据变量就能知道这一点地坐标了

比如 任天堂的 超级玛丽游戏里面的 马里奥有: 移动(前进,后退,上,下),跳,发射子弹等,一个抽象数据类型定义了: 一个数据对象 , 数据对象中各数据元素之间地关系及对数据元素的操作,至于,抽象类型到底需要哪些操作,这就由开发者决定

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

描述抽象数据类型的标准格式:

1
2
3
4
5
6
7
8
9
10
11
12
13
14

ADT 抽象数据类型别名

Data(数据)
	数据元素之间逻辑关系的定义
	
Operation(操作)
	操作1
		初始条件
		操作结果描述
	操作2
		....
	操作n
		....
	endADT

总结回顾

由于以上概念,给出了数据结构的定义:

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

同样是结构,从不同的角度来讨论,会有不同的分类:

下一章 : 算法