一、基础知识

1、数据结构常用术语：

1.1数据结构中的五个基本概念：

数据<-数据对象<-数据元素<-数据项

数据结构

1.2名词解析：

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

• 数据对象: 性质相同的数据元素的集合(数据的子集)

• 数据元素: 数据的基本单位，且有一定意义的基本单位,在计算机中通常作为整体处理(一个数据元素可以由若干数据项组成)

• 数据项: 组成数据元素的最小单位(不可分割)

• 数据结构: 指的数据对象中的数据元素之间的关系.

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

 在C语⾔中,按照取值不同,数据类型可以分为2类:

• 原⼦类型: 是不可以在分解的基本数据类型,包含整型,浮点型,字符型等;

• c结构类型: 由若⼲类型组合⽽成,是可以再分解的.例如,整型数组就是由若⼲整型数据组成的.

example：

代码示例

2、数据结构

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

2.1 逻辑结构

指的是数据对象中的数据元素之间的相互关系. 逻辑结构分为四种: 集合结构,线性结构,树形结构,图形结构，其中除了线性结构外其他三种也可以叫非线性结构。

线性结构特点：

• 结构关系是一对一的，并且是一种先后的次序

• 主要特征为存在唯一的被叫做第一个和最后一个数据，

• 除第一个元素之外每个数据元素均有⼀个前驱。

• 除最后一个元素之外每个数据元素均有一个后继。

• 表现形式为：线性表、栈和队列、字符串（特殊的线性结构）

2.1.1 集合结构：集合结构中的数据元素除了同属于一个集合外,它们之间没有其他关系

2.1.2 线性结构: 线性结构中的数据元素之间是一对一的关系.常用的线性结构有：线性表，栈，队列，双队列，数组，串。

2.1.3 树型结构: 重要的非线性数据结构。树形数据结构可以表示数据表素之间一对多的关系.树型结构中的数据元素之间存在一种一对多的层次关系. 常见的树形结构: 二叉树,B树,哈夫曼树,红黑树等.

2.1.4 图形结构: 图形结构的数据元素是多对多的关系. 常见的图形结构: 邻近矩阵,邻接表.

2.2 物理结构

物理结构,别称"存储结构".指的是数据的逻辑结构在计算机的存储形式

设计好逻辑数据结构之后,数据的存储也是非常重要的. 数据存储结构应该正确反映数据元素之间的逻辑关系.这才是关键! 如何存储数据元素之间的逻辑关系,是实现物理结构的重点和难点.

数据元素的常用存储结构形式有2种: 顺序存储和链式存储;

不常用两种：散列，索引

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

顺序存储结构

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

 链式存储结构

二、算法小常识

1、算法定义：算法就是解决特定问题求解步骤的描述,在计算机中表现为指令的有限序列列, 并且每个指令表示⼀一个或多个操作.

2、算法特性

• 有输入有输出：输入代表初始条件，输出代表结果

• 有穷性：执行次数与执行时间有限

• 确定性：每一步的执行都是唯一的

• 可行性：每个操作切实可行

3、算法设计要求

• 正确性 :执行结果正确

• 可读性：阅读的传播难易程度

• 健壮性：异常情况处理

• 时间效率⾼高和储存量量低：执行算法需要消耗的时间资源和空间资源

4、时间复杂度

每条执行语句执行次数相加

5、空间复杂度

算法的空间复杂度通过计算算法所需的存储空间实现,算法空间复杂度的计算公式 记做: S(n) = n(f(n)),其中,n为问题的规模,f(n)为语句句关于n所占存储空间的函数，算法的空间复杂度指的并不是整个算法在内存占用空间,而是指的是该算法在实现时所需要的辅助空间就可以

如果算法执行时所需要的辅助空间相对于输入数据量是一个常数,则成这个算法原地工作,辅助空间为O(1).

程序空间计算因素:寄存本身的指令、常数、变量、输入、对数据进行操作的辅助空间

在考量算法的空间复杂度,主要考虑算法执行时所需要的辅助空间

示例