本章主要讲解数据结构和算法的基本概念，在文中标有*的是重点内容一定要熟记！

数据结构考纲

数据结构的三要素（考点）

1.逻辑结构：分为线性结构和非线性结构。*线性结构：线性表，栈，队列；非线性结构：树，图，集合

2.*存储结构（物理结构）

3.数据的运算

数据结构的五个特征

有穷性，确定性，可行性，输入，输出

效率的度量（重点+考点）

时间复杂度*和空间复杂度（时间复杂度是重中之重，选择题大题都会出现）

数据结构知识点

基本概念

1.数据：数据是信息的载体，是描述客观事物属性的数，字符及所有能输入到计算机中并被计算机程序识别和处理的符号集合。数据是计算机程序加工的原料。

（1）数值型数据：整数，实数等

（2）非数值型数据：文字，图像，图形，声音等

2.数据元素：数据元素是数据的基本单位，通常作为一个整体考虑。也称为记录、顶点、结点。

3.数据项：一个数据元素由若干个数据项组成，数据项是数据元素中不可分割的最小单位。

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

（1）逻辑结构：数据元素之间的逻辑关系

​ a.线性结构：有且仅有一个开始和一个终端结点，并且所有节点最多只有一个之间前趋和一个直接后继。

​ 例如：线性表、栈、队列、串

​ b.非线性结构：一个结点可能有多个直接前趋和直接后继

​ 例如：树、图

（2）物理结构（存储结构）：数据元素及其关系在计算机内存中的表示。

​ a.顺序存储结构：用一组连续的存储单元依次存储数据元素，数据元素之间的逻辑关系由元素的存储位置来表示，C中用数组来实现顺序存储关系。方便查找。

​ b.链式存储结构：用任意的存储单元存储数据元素，数据元素之间的逻辑关系用指针表示，C用指针来实现链式存储结构。方便插入和删除。

​ c.索引存储结构：需建立附加的索引表，索引表中每一项称为索引项，一般形式为（关键字，地址）

​ d.散列存储：根据关键字计算出结点的存储地址

5.数据对象：数据对象是具有相同性质的数据元素的集合，是数据的一个子集。如整数的数据对象是集合N={1,2,3,…}

6.数据类型：是指一组性质相同的值的集合和定义在此集合上的一组操作的总称。

（1）原子类型：是不可以再分解的基本类型，包括整型（int），实型，字符型（char）等

（2）结构类型：由若干个类型组合而成，是可以再分解的。如整型数组是由若干个整型数据组成的

7.抽象数据类型（ADT）：抽象数据类型可用三元组（D，S，P）表示，D是数据对象，S是D上的关系集，P是对D的基本操作集。

​ 抽象数据类型的标准格式如下：

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

ADT 抽象数据类型名{
Data
数据元素之间逻辑关系的定义
Operation
操作1
初始条件
操作结果描述
操作2
...
操作n
...
} ADT 抽象数据类型名

综上：数据>数据对象>数据元素>数据项

算法知识点

基本概念

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

2.算法的特性：算法具有五个基本特性：输入，输出，有穷性，确定性，可行性。

​ （1）输入和输出：算法具有零个或多个输入，尽管大部分的函数都需要有输入。算法至少需要一个或多个输出，输出的形式可以是打印输出也可以是返回一个或多个值。

​ （2）有穷性：指算法在执行有限步骤之后，自动结束循环而不会出现无限循环，并且每个步骤在一个可接受的时间内。

​ （3）确定性：算法的每一个步骤都有确定的含义，不会出现二义性。即相同的输入只能出现相同的输出。

​ （4）可行性：算法的每一步都必须是可行的，即每一步都能够通过执行有限步骤完成。

算法设计的要求

1.正确性：算法的正确性是指算法至少应该具有输入，输出和加工处理无歧义性，能正确反映问题的需求、得到问题的正确答案。

正确性的要求分为以下四点，按照难度依次递增：

（1）算法程序没有语法错误。

（2）算法程序对于合法的输入能够产生符合其要求的结果。

（3）算法程序对于非法的输入数据能得出满足规格说明的结果。

（4）算法程序对于精心选择的，甚至刁难的程序都有满足要求的输出结果。

2.可读性：算法设计的另一目的是为了便于阅读、理解和交流。为了让别人看得懂啊。

3.健壮性（处理异常问题的能力）：当输入数据不合法时，算法也能做出相关的处理，而不是产生异常或莫名其妙的结果。

4.时间效率高和存储量低：设计算法应该尽量满足时间效率和存储量低的需求。

算法效率的度量方法

1.事后统计方法：利用计算机的计时器功能，对算法的运行时间进行对比，从而得出算法效率的高低。

2.事前分析估计方法：在计算机程序编制之前，依据统计方法对算法进行估算。

​ 下面我们来对比1+2+3+…+100的两种算法：

1
2
3
4
5
6
7
8

//算法一
int i,sum=0,n=100;
//执行1次
for(i=1;i<=n;i++){
//执行n+1次
sum = sum + i;
//执行n次
}
printf("%d",sum)
//执行一次
//一共执行了1+(n+1)+n+1 = 2n+3次，即n次

1
2
3
4
5
6

//算法二
int sum = 0,n = 100;
//执行一次
sum = (1+n)*n/2;
//执行一次
printf("%d",sum);
//执行一次
//执行了三次，即1次

算法中函数的渐近增长（重点！）

定义：给定两个函数f(n)和g(n)，如果存在一共整数N，是的队员所有的n>N，f(n)总是比g(n)大，那么我们说f(n)的增长渐近快于g(n).

对于算法A：2n^2+n 和 算法B：n^3+n^2 我们只需要看最高次幂的幂数，连与最高次项相乘的常数都不重要！

综上可知：判断一个算法的效率时，我们只需观察最高阶项，而函数中的常数和其他次要项往往可以忽略不计！

算法的时间复杂度

使用O（）来体现算法时间复杂度的记法。

推导大O阶：

1.用常数1取代运行时间中的所有加法常数。

2.在修改后的运行次数函数中，只保留最高阶项。

3.如果最高阶项存在且不是1，则去除与这个项相乘的常数。

得到的结果就是大O阶！

常数阶

常数阶不论运行了10次20次100次都只能记作O(1)不能记作O(3)O(10)，初学者常常犯这样的错误

对于分支结构而言，无论是真是假，时间复杂度都是O(1)

线性阶

1
2
3

//线性阶的时间复杂度时O(n)
int i;
for(i=0;i<n;i++){}

对数阶

1
2
3
4

int count = 1;
while(count<n){
count = count * 2;
//因为2^x=n，所以x=log2(n),即O(logn)
}

平方阶

1
2
3
4
5
6

#平方阶的时间复杂度是O(n^2)
int i,j;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++){}
}

拓展

1
2
3
4
5
6

//一个比较常见的时间复杂度判断
int i,j;
for(i=0;i<n;i++){
for(j=i;j<n;j++){
//当i=0，执行n次，当i=1，执行n-1次...总执行次数是等差数列求和问题，n(n+1)/2=n^2/2 + n/2,所以O(n^2).
}
}

数列知识点（做题的基础）

1
2

//等差数列的计算：前n项和等于n(n+1)/2
//等比数列的前n项和：(a1-an*q)/(1-q)

时间复杂度所耗费的时间

O(1)<O(logn)<O(n)<O(nlogn)<O(n^2)<O(n^3)<O(2^n)<O(n!)<O(n^n)

总结

要做好大O阶时间复杂度的题目，要学好数列的相关知识

算法的空间复杂度

算法空间复杂度的计算公式为S(n) = O(f(n))，其中n为问题的规模，f(n)是n所占存储空间的函数。

最后

以上就是潇洒老师为你收集整理的数据结构--基本概念本章主要讲解数据结构和算法的基本概念，在文中标有*的是重点内容一定要熟记！的全部内容，希望文章能够帮你解决数据结构--基本概念本章主要讲解数据结构和算法的基本概念，在文中标有*的是重点内容一定要熟记！所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。