引入
前面我们学习了 C 语言的部分知识,我们知道要用计算机解决一个问题大致分为一下几个步骤:
- 具体问题 抽象出 数学模型
- 设计一个算法,解该数学模型
- 编写一个程序
- 调试程序,直到解决问题
那么第一步,找到数学模型
,就是解决此问题的关键,我们从模型中找到操作对象
,然后找到这些操作对象之间的关系
,然后用数学语言去描述
它们。
什么是数据结构
程序设计=数据结构+算法
再进一步,数据结构其实研究的就是关系,是数据元素
相互之间存在的一种或多重特定关系的集合。
逻辑结构和物理结构
我们把数据结构分为逻辑结构
和物理结构
- 逻辑结构:数据对象中数据
元素之间的相互关系
,也是我们需要关注和讨论的问题。 - 物理结构:表示数据的
逻辑结构
在计算机中的存储形式。
逻辑结构
我们知道数据结构中,我们主要讨论的就是元素之间的相互关系,也就是数据结构中的逻辑结构,其实逻辑结构也大致分为四类。
- 集合结构:集合结构比较好理解,就是所有
数据元素
,除了同属于一个集合
外,别无其他关系。 - 线性结构:结构中的数据元素之间存在
一个对一个的关系
,也就是常说的一对一的关系。可以理解位一个元素只对应另一个元素,类似学 C 语言时构建的链表。 - 树形结构:数据元素之间存在
一个对多个
的层次关系,类似金字塔的结构。有点像树,有树干也有枝条,纸条上还有树叶等等。 - 图状结构/网状结构:数据元素之间存在
多个对多个
的关系。类似朋友圈,我认识你,你认识他,他认识我,我也认识他。
物理结构
其实就是我们讨论的这些个数据元素,如何存储到计算机的存储器中,存储器主要包括:
- 硬盘
- 软盘
- 关盘
- 等等
数据元素的存储形式
,有两种:
顺序存储和链式存储
- 顺序存储:就是把
数据存放在地址连续的存储单元
里的。所以数据间的逻辑关系和物理关系是一致的。类似:数组,数组元素之间是顺序存储的。 - 链式存储:把数据元素
存放在任意存储单元
里,可以是连续的,也可以是不连续的。类似银行取号,你不用排队了,你愿意在哪就在哪,叫到你你就去就行了。
这个之前在 C 语言的课程中,学习过了,顺序存储就是把数据元素存放在地址连续的存储单元里,链式存储就是上一个数据元素的内存放着下一个数据元素的指针,也就是地址。
引入算法
我们刚才讲了程序设计=数据结构+算法
,所以,算法也是程序设计的另一个灵魂,数据结构总是和算法在一起
。
单纯讲数据结构,没什么感觉,配合算法,就会发现,以前的大牛们确实做了很多工作,解决了很多很难的问题。
算法初体验
小时候我们都算过,从1+2+3+4+....+99+100
我们之前呢,只能一个一个的算,算到天荒地老,然后有一天如果题目是1+2+3+4+....+999+1000
,那你估计就会崩溃了。
在很久以前,德国数学家高斯,小时候老师就让他们算1加到100,高斯没过几分钟就说自己算完了,说出了答案,5050,老师问他,他就说
1 和 100 是 101
2 和 99 是 101
3 和98 是 101
……
50 和 51 是 101
有 50 对儿 101
101 X 50 = 5050
也就是小时候说的(首项+末项)X 项数 / 2
也就是等差数列
的算法
什么是算法?
算法是解决特定问题求解步骤的描述
,在计算机中表现为指令的有限序列
,并且每条指令表示一个或多个操作。
简单来说,就是解决实际问题的技术,技术阅读,解决的越快,也越省资源。
要记住:就像一种药不能包治百病,同样的,一种算法也不能解决所有问题。
算法的特点
算法具有五个基本特征:
- 输入
- 输出
- 有穷性
- 确定性
- 可行性
输入
算法需要具有零个或多个输入
。
1 | void haha(){ |
上面这个 haha 函数没有参数,即算法没有输入,只是执行一个语句。但是绝大多数的算法都是有参数的。
输出
算法至少有一个
或多个输出。
算法如果设计了半天,没有输出,会很奇怪。我们可以打印这个输出,也可以返回这个输出。
有穷性
算法在执行有限的步骤之后自动结束,不会出现无线循环
。每一个步骤都是在可接受的时间内完成
。
同样,一个永远不会结束的算法,要它做甚?
确定性
算法的每一个步骤都具有确定的含义,不会出现二义性
。也就是步骤要明确,所以相同的输入必须有相同的输出
。
不能含糊其词。
可行性
算法的每一步都必须是可行的
,也就是说,每一步都能够通过执行有限次数完成
。
算法设计要求
因为一个问题可以通过不同的算法来解决,所以我们要多掌握一些好的算法,来帮助我们解决问题。算法设计要求有以下几点:
- 正确性
- 可读性
- 健壮性
- 时间效率高和存储量低
正确性
正确性其实就是指算法至少应该具有输入、输出和加工处理。无歧义性、并且能正确反应问题的需求,能
够得到问题的正确答案,即
- 算法的设计
不能有语法错误
- 算法对
合法的输入
能够产生满足要求的输出
- 算法对于
非法输入
能够产生满足条件的说明
- 算法对于
故意刁难的测试输入
有满足要求的输出结果。
可读性
算法设计的另一个目的,就是便于阅读、理解和交流。
除了让计算机执行我们的算法,我们也要为自己以后的修改和更新留下提示。
健壮性
输入数据不合法时,算法也能做出响应处理,而不是崩溃。
时间效率高和存储量低
执行速度快,又不占用太多的内存空间!
一句话总结就是,让马儿快跑,又不用吃草…
尾巴
这是我的个人学习笔记,主要是应付考研复习使用,充斥着一些吐槽和个人观点,并不严谨,欢迎大家参考、指正。