《数据结构》学习笔记一:绪论-阿里云开发者社区

开发者社区> 数据库> 正文
登录阅读全文

《数据结构》学习笔记一:绪论

简介: 个人看法: 数据结构的重要性对于码农而言就像盖房子的图纸,做饭的菜谱,没有它,也许也能盖得成房子,也能做的熟菜,但是质量如何就不敢说了。我们从大学的时候就把《数据结构》作为重要的基础课程来认真学习,但是真正听懂的,弄明白的,并不是很多。

个人看法:
数据结构的重要性对于码农而言就像盖房子的图纸,做饭的菜谱,没有它,也许也能盖得成房子,也能做的熟菜,但是质量如何就不敢说了。我们从大学的时候就把《数据结构》作为重要的基础课程来认真学习,但是真正听懂的,弄明白的,并不是很多。工作了几年,体会到它的重要性,决定回过头来再次抱起书本,系统的再次学习这门课程。我相信,一定会有不一样的感受和收获。闲谈少叙,书归正传。

一、本节解决问题:

1.什么是数据结构?

二、主要内容:

1.学习前的心里准备
2.一个小例子
3.起源
4.概念和术语
5.逻辑结构和物理结构
6.数据类型
7.总结

三、开始学习吧

1.学习前的心理准备

数据结构很重要我们知道了,我们学习这门课程的时候一定是抱着好好学,认真踏实的学习的心态的,但是呢,这中间也许会有一个个疑团,一道道障碍,别放弃,就对了!
学习数据结构就像过年回家一样,也许是做高铁,也许是飞机,也许是绿皮车,也许是大巴车,还可能是搭顺风车,兜兜转转只要到达目的地,就是成功了。

2.一个小例子

有个同学叫“小菜”,他刚入职场,做了一位码农。工作中,他们要做一个客服电话系统,他们领导给他一个任务就是完成客户排队模块的代码。
小菜觉得很容易啊,不就是排队吗,用数据库就能简单的解决啊。于是他设计了一张客户排队表,用自动递增的整型数字作为客户编号。来一个客户,在表的末尾插入一条数据。等系统一空闲,就从表中取出编号最小的客户提交,并删除该记录。写好后,小菜高高兴兴的提交了。
领导看完代码,把小菜叫到跟前,对他说:“你数据结构怎么学的啊?这种实时排队内存就能搞定,用什么数据库啊!”
小菜回去后,细细思考,决定用数组来实现,又怕数组溢出,还要考虑数组的长度。
小菜战战兢兢地提交了代码。
果然,没过多久,领导再次叫来了小菜,告诉他,只需要用数据结构的队列结构就能解决这个问题,回去好好想想,再重新写来。
小菜回去一宿没睡,仔细学习了“队列结构”,重新设计了实时排队的代码,提交了。这一次,领导跟小菜说:“小伙子,还不错。”

既然数据结构这么重要,那一定要好好学啊。

3.起源

《数据结构》是怎么来的?
1968年,美国有个叫做高德纳的教授写了一本书叫做《计算机程序设计艺术》,其中第一卷《基本算法》中,他系统的阐述了数据的 逻辑结构 和 物理结构还有数据操作,开创了《数据结构》的课程体系。从这一年起,《数据结构》正式诞生了。

4.概念和术语

1》数据
数据结构,顾名思义是“数据的结构”。那么就有必要知道什么是“数据”呢?

数据就是描述客观事物的符号,是计算机可以操作的对象,是能被计算机识别、输入的符号集合。例如:1,2,3等数字、“你好”,“hello”等文字符号,逗号,括号等标点符号、图片、音频、视频等。

思考:这些符号为什么能够被计算机识别呢?
个人思考:因为这些符号在计算机中有约定的编码,比如 a 的编码是65,编码之后的符号能够被计算机识别。计算机也是人设计的,它是根据人的设定工作的,你说 编码是65的是字符a,它就认为是a。

2》数据元素

数据元素:组成数据的、有一定意义的基本单位,在计算机中通常作为整体处理,也被称为记录。
例如:人类中,小明,小华都是数据元素;
车类中,小汽车,大卡车,公交车都是数据元素。

3》数据项

数据项:一个数据元素可以由若干数据项组成。
例如:小明这个数据元素,他的眼睛、耳朵、手、脚、姓名、年龄、家庭住址等等都是数据项。其实就是类的属性。

4》数据对象

数据对象:性质相同的数据元素的集合,是数据的子集。
什么是性质相同呢?比如,人都有姓名、性别和出生日期这些相同的数据项。

我们把数据结构中的基本概念都介绍完了,那么到底什么是数据结构呢?

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

数据结构之所以难以理解,是因为它讨论的是“关系”,还不是一种关系,而是可能有多种关系。到底都有哪些关系呢?

5.逻辑结构和物理结构

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

逻辑结构:数据对象(性质相同的数据元素)中数据元素之间的互相关系。
1.集合结构
2.线性结构
3.树形结构
4.图形结构

集合结构:元素之间的关系是同在一个集合中。

img_50b22818958b0711064393375a519cf5.png
image.png

线性结构:1对1的关系

img_f355dfa2a0422daebd17d0b77e3d5895.png
image.png

树形结构:1对多的关系

img_9b077354a632ee415af3af7e381b54ad.png
image.png

图形结构: 多对多的关系

img_d77e2e85144bc69b936057f438f1b0dc.png
image.png

物理结构:也叫做存储结构,是指数据的逻辑结构在计算机中的存储形式。
注意:这里的存储主要指的是内存的存储,而不是像硬盘啊,光盘啊这些外部存储器的存储。
存储结构有两种:
1.顺序存储:例如数组
2.链式存储:例如链表等

什么是顺序存储?
就是把数据元素存放在连续的内存单元里面,其数据间的逻辑关系和物理关系是一致的。

img_84d1137504a791eb3e2963ee46b595c1.png
image.png

(请忽略丑陋的文字)


img_f626de4a87ff23bef7d68517d75df816.png
image.png

什么是链式存储?
就是数据元素存储在任意的存储单元里,这组存储单元可以是连续的,也可以是不连续的。
这就像什么呢?就像上学时候早晨做早操站队,假如站成一队,每个人不可能把所有人的位置都记得,他只需要记住自己的前一个同学是谁就行了。而第一个同学知道自己是第一个,最后一个同学知道自己是最后一个,这样每次排队,大家都能找到自己的位置了。

img_eb23adc372c50fde2fadb268dd59fb0e.png
image.png

注意:逻辑结构是面向问题的,物理结构是面向计算机的,其基本目标是将数据以及逻辑关系存储在计算机中。

6.数据类型

前面我们知道了什么是数据,而数据也是有类型的,这个类型是什么回事呢?就像每个人都有自己的姓氏一样,同一个类型的数据也有共同的特征。
为什么需要类型呢?
因为计算机的内存是有限的,我们声明了一个变量 a ,那么给它多大的空间存储它好呢?给太大了,浪费内存,给太小了,又怕不够,怎么办呢?就根据数据的特征,给他们不同的类型。比如,整型的数据,所占的存储空间是4位,一位是8个字节,,留出一个字节用作正负符号表示,整型的取值范围就是2的31次方减1.
打个比方说吧,大家都要住房子,都希望房子越大越好,但是呢,有的有钱,有的没钱,所以呢,房子也就有大的,有小的。
这里顺便提一下“溢出”是什么回事儿。
我们知道了,一个整型的数据占4位,一个浮点型的占8位(当然了,不同计算机也是不一样的),你把一个超过整型范围的浮点型数据硬要塞到放整型的房子里,那能放得下吗?放不下,不就漏出来了,叫“溢出”。
具体每种语言都有什么类型,这些类型是如何定义的,我们这里不做讨论。

7.总结

本节说了这么多,就是为了解决开头的一个问题:什么是数据结构。

数据结构是研究数据元素之间一种或者多种关系的集合。

程序设计与数据结构的关系:

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

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
数据库
使用钉钉扫一扫加入圈子
+ 订阅

分享数据库前沿,解构实战干货,推动数据库技术变革

其他文章