这篇文章上次修改于 308 天前,可能其部分内容已经发生变化,如有疑问可询问作者。

数据结构与算法的关系

什么是数据结构?

很多时候,我们无法仅使用简单的数字、字符串、布尔就能完整的描述数据,可能我们希望使用数组、对象、或它们组合而成的复合结构来对数据进行描述。这种复合的结构就是数据结构。

而在实际开发中,我们会发现很多场景中使用的数据结构有着相似的特征,于是,数据结构这门学科,就把这些相似的结构单独提取出来进行研究。

常见的数据结构有:数组、链表、树、图等

概念术语
1、数据(Data)是能被计算机处理的符号或符号集合,含义广泛,可理解为“原材料”。如字符、图片、音频、视频等。

2、数据元素(data element)是数据的基本单位。例如一张学生统计表。

3、数据项(data item)组成数据元素的最小单位。例如一张学生统计表,有编号、姓名、性别、籍贯等数据项。

4、数据对象(data object)是性质相同的数据元素的集合,是数据的一个子集。例如正整数N={1,2,3,····}。

5、数据结构(data structure)是数据的组织形式,数据元素之间存在的一种或多种特定关系的数据元素集合。

6、数据类型(data type)是按照数据值的不同进行划分的可操作性。在C语言中还可以分为原子类型和结构类型。原字类型是不可以再分解的基本类型,包括整型、实型、字符型等。结构类型是由若干个类型组合而成,是可以再分解的。

数据的逻辑结构
逻辑结构(logical structure)是指在数据中数据元素之间的相互关系。数据元素之间存在不同的逻辑关系构成了以下4种结构类型。

1、集合结构:集合的数据元素没有其他关系,仅仅是因为他们挤在一个被称作“集合”的盒子里。

2、线性结构:线性的数据元素结构关系是一对一的,并且是一种先后的次序,就像a-b-c-d-e-f-g·····被一根线穿连起来。

3、树形结构:树形的数据元素结构关系是一对多的,这就像公司的部门级别,董事长-CEOCTO-技术部人事部市场部.....。

4、图结构:图的数据元素结构关系是多对多的。就是我们常见的各大城市的铁路图,一个城市有很多线路连接不同城市。

数据的存储结构

存储结构(storage structure)也称物理结构,表示数据的结构在计算机中的存储形式,数据的存储结构可以反映数据元素之间的逻辑关系。分为以下两种:

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

2、链式存储结果:是把数据元素存放在任意的存储单元里,这组存储单元可以是连续的,也可以是不连续的,数据元素的存储关系并不能反映其逻辑关系,因此需要借助指针来表示数据元素之间的逻辑关系。

什么是算法?

一个程序,很多时候都需要根据一种已知数据,通过计算,得到另一个未知数据,这个运算过程使用的方法,就是算法。

而在很多的场景中,它们使用的算法有一些共通的特点,于是把这些共通的算法抽象出来,就行了常见算法。

从一个更高的角度来对算法划分,常见的算法有:穷举法、分治法、贪心算法、动态规划

算法的五大特性

1、有穷性,是指算法在执行有限的步骤之后,自动结束而不是出现无限循环,并且每一个步骤在可接受的时间内完成。

2、确定性,是指算法执行的每一步骤在一定条件下只有一条执行路径,也就是相同输入只能有一个唯一的输出结果。

3、可行性,是指算法每一步骤都必须可行,能够通过有限的执行次数完成。

4、输入,是指算法具有零个或多个输入。

5、输出,是指算法至少有一个或多个输出。

数据结构与算法的关系

存储(内存)和运算(CPU)是程序的两大基础功能,数据结构是专门研究数据的存储,算法是专门研究运算过程的。一个面向的是存储,一个面向的是运算,它们共同构成了计算机程序的两个重要部分。

有了相应的数据结构,免不了对这种数据结构的各种变化进行运算,所以,很多时候,某种数据结构都会自然而然的搭配不少算法。

程序=算法+数据结构

  • 数据结构是算法实现的基础,算法总是要依赖某种数据结构来实现的。
  • 算法的操作对象是数据结构。
  • 数据结构关注的是数据的逻辑结构、存储结构有一集基本操作,而算法更多的是关注如何在数据结构的基本上解决实际问题。
  • 算法是编程思想,数据结构则是这些思想的基础。

数据结构与算法涉及的计算机语言

数据结构与算法与具体的语言无关,任何语言都能实现。