数据结构和算法——绪论
一、绪论
1.1 数据结构的研究内容
1、数据的各种逻辑结构和物理结构（存储结构），以及它们之间的相应关系
2、对每种结构定义相适应的各种运算
3、设计出相应的算法
4、分析算法的效率
1.2 基本概念和术语
1.2.1 数据、数据结构、数据项和数据对象
举个例子说明：假设有两张表，上表为人员表，下表为课程表，表的格式如下：
| 姓名 | 性别 | 身高 | 课程代号 |
| 小明 | 男 | 180 | A |
| 小红 | 女 | 180 | A |
| 小绿 | 女 | 180 | B |
| 课程代号 | 课程名 |
| A | 语文 |
| B | 数学 |
这两张表就是数据
而单独的一张表就是数据对象， 即人员表和课程表都是一个数据对象，而每张表的每一行就是数据元素。而姓名、身高、课程代号、性别就是数据项，是最小的不可分割的最小单位。
1.2.2 数据结构
数据结构包括逻辑结构和物理结构（存储结构）两个层次。
数据结构是相互之间存在一种或者多种特定关系的数据元素的集合。
a、逻辑结构
逻辑结构是分为四种类型：集合结构、线性结构、树形结构、图结构
集合结构：数据元素同属一个集合，单个数据元素之间没有任何关系。
![[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-4zzJGWwu-1604820044558)(images/20201107113322490.png)]](https://img-blog.csdnimg.cn/20201108152252689.png#pic_center)
线性结构：类似于线性关系，线性结构中的数据元素之间是一对一的关系。
![[转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-xcX4kHLt-1604820044561)(images/20201107113349349.png)]](https://img-blog.csdnimg.cn/20201108152305210.png#pic_center)
树形结构：树形结构中数据元素之间存在一对多的关系。（各元素及元素关系所组成图形类似于树状图）。
![[存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-i1iwm9J6-1604820044565)(images/2020110711340070.png)]](https://img-blog.csdnimg.cn/20201108152317754.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nob25neWFuZ18=,size_16,color_FFFFFF,t_70#pic_center)
图形结构：数据元素之间是多对多的关系。如下图所示。
![[(img-WetcYd94-1604820044567)(images/20201107113413856.png)]](https://img-blog.csdnimg.cn/20201108152332114.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nob25neWFuZ18=,size_16,color_FFFFFF,t_70#pic_center)
总结：逻辑结构是独立于计算机的，总体可以划分为线性结构和非线性结构，其中线性结构是指每个元素都有且仅有一个前驱和后继，而非线性结构是一个结点可能有多个直接前驱和多个直接后继。
b 存储结构（物理结构）
物理结构又叫存储结构，分为四种:顺序存储结构、链式存储结构、索引存储结构、散列存储结构，主要关注于前面两种存储结构。
（1）顺序存储结构
顺序存储结构就是把数据元素放到地址连续的存储单元里面，其数据间的逻辑关系和物理关系是一致的。之前学习的数组就是一种顺序存储结构，（如下图所示）
![[转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Md4Jd1I6-1604820044569)(images/20201107113434453.png)]](https://img-blog.csdnimg.cn/20201108152347937.png#pic_center)
（2）链式存储结构
链式存储结构：是把数据元素存放在任意的存储单元里面，这组存储单元可以是连续的也可以是不连续的。根据指针找出相邻元素的位置。
1.2.3 数据类型和抽象数据类型
a、数据类型
一般包括整型，实型、字符型等基本类型外、还有数组、结构体和指针等构造数据类型。
b、抽象数据类型（Abstract Data Type,ADT）
类似于C语言中的结构体和C++、Java中的类。
通俗的讲，抽象数据类型，泛指除基本数据类型以外的数据类型。
1.3 抽象数据类型的表示与实现
抽象数据类型的概念与面向对象的思想是一致的。
1.4 算法和算法分析
程序 = 数据结构 + 算法
1.4.1 算法的定义及特性、
算法是为了解决某类问题而规定的一个有限长的操作序列。
一个算法必须满足以下5个重要特性：有穷性、确定性、可行性、输入、输出、
1.4.2 评价算法优劣的基本标准
正确性、可读性、健壮性（鲁棒性）、高效性
1.4.3 算法的时间复杂度
详细可看这个：(5条消息) 一套图 搞懂“时间复杂度”_12 26 25的博客-CSDN博客_时间复杂度
看以下代码的时间复杂度：
![\转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ozjmldFC-1604820044571)(images/20201107113605227.png)]](https://img-blog.csdnimg.cn/20201108152431470.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nob25neWFuZ18=,size_16,color_FFFFFF,t_70#pic_center)
最好、最坏和平均时间复杂度
1.最好时间复杂度：指的是算法计算量可能达到的最小值
2.最坏时间复杂度：指的是算法计算量可能达到的最大值。
3.平均时间复杂度：是指算法在所有可能情况下，按照输入实例以等概率出现时，算法计算量的加权平均值
1.4.4 算法的空间复杂度
空间复杂度只需要分析辅助变量所占的额外空间。一个算法的空间包括算法本身占用的空间以及辅助空间。
空间复杂度：S（n）= O(f(n))
如果算法执行所需要的临时空间不随着某个变量n的大小而变化，即此算法空间复杂度为一个常量，可表示为O（1）
举个例子
int i = 1;
int j = 1;
++i;
++j;
int m = i+j;
代码中的i，j，m所分配的空间不能随着处理数据量的变化，因此它的空间复杂度S（n） = O（1）
我们再看一个代码：
int []m = new int[n];
for (i = 1; i <= n; ++i) {
j = i;
j++;
}
这段代码中，第一行new了一个数组出来，这个数据占用的大小为n，这段代码的2-5行，虽然有循环，但没有再分配新的空间，因此，这段代码的空间复杂度主要看第一行即可，即 S(n) = O(n)
第一章 总结
![[片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-sj3ANZIY-1604820044572)(images/20201107123513793.jpg)]](https://img-blog.csdnimg.cn/20201108152448527.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nob25neWFuZ18=,size_16,color_FFFFFF,t_70#pic_center)
数据、数据对象和数据元素、数据项的关系如下
![[转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-JbbYJOEX-1604820044573)(images/20201107113623372.png)]](https://img-blog.csdnimg.cn/202011081525424.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nob25neWFuZ18=,size_16,color_FFFFFF,t_70#pic_center)
数据结构是相互之间存在一种或者多种特定关系的数据元素的集合，同样是结构，从不同角度来讨论，会有不同的分类，如下图所示
![[失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-A2q352GF-1604820044574)(images/20201107113637948.png)]](https://img-blog.csdnimg.cn/2020110815255868.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nob25neWFuZ18=,size_16,color_FFFFFF,t_70#pic_center)
算法是为了解决某类问题而规定的一个有限长的操作序列。
算法具有五个特性：有穷性、确定性、可行性、输入和输出
算法分析的重点方面是分析算法的时间复杂度和空间复杂度。