【数据结构】数据结构概述

写在前面：这是博主考研期间整理的数据结构的笔记，如有错误，请路过的大神批评指正

第一章 概论

1.1数据结构的基本概念

概念理解而已

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

数据元素：数据元素是数据的基本单位，通常作为一个整体进行考虑和处理。**一个数据元素可由若干数据项组成，数据项是构成数据元素的不可分割的最小单位。**例如，学生记录就是一个数据元素,它由学号、姓名、性别等数据项组成。

数据对象：数据对象是具有相同性质的数据元素的集合，是数据的-一个子集。例如，整数数据对象是集合N= {0, -1, +2}。

数据类型：数据类型是一个值的集合和定义在此集合上的一组操作的总称。
1)原子类型。其值不可再分的数据类型。
2)结构类型。其值可以再分解为若干成分(分量)的数据类型。
3)抽象数据类型。抽象数据组织及与之相关的操作。

数据结构：数据结构是相互之间存在一种或多种特定关系的数据元素的集合。在任何问题中，数据元素都不是孤立存在的，它们之间存在某种关系，这种数据元素相互之间的关系称为结构(Structure)。数据结构包括三方面的内容:逻辑结构、存储结构和数据的运算。数据的逻辑结构和存储结构是密不可分的两个方面，一个算法的设计取决 于所选定的逻辑结构，而算法的实现依赖于所采用的存储结构”。

数据结构的三要素

数据的逻辑结构

数据元素之间的逻辑关系，从逻辑关系上描述数据。与数据的存储无关，独立于计算机。分为线性结构（线性表）和非线性结构（集合、树和图等）。
数据的逻辑机构的如图所示：

集合。结构中的数据元素之间除“同属一个集合”外，别无其他关系，如图1.2(a)所示。
线性结构。结构中的数据元素之间只存在一对一的关系，如图1.2(b)所示。
树形结构。结构中的数据元素之间存在一对多 的关系，如图1.2©所示。
图状结构或网状结构。结构中的数据元素之间存在多对多的关系，如图1.2(d)所示。

数据的存储结构

存储结构是指数据结构在计算机中的映像，也叫做物理结构。包括数据元素的表示和关系表示。存储结构不同，运算实现的方式也不同

• 顺序存储：顺序存储。把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中元素之间的关系由存储单元的邻接关系来体现。其优点是可以实现随机存取，每个元素占用最少的存储空间;缺点是只能使用相邻的一整块存储单元，因此可能产生较多的外部碎片。
• 链式存储：不要求逻辑上相邻的元素在物理存储上也相邻，通过指针表示元素之间的逻辑关系。优点就是不会出现碎片现象，能够充分利用所有存储单元；缺点就是每个元素因为存储指针而需要占用额外的存储空间，且只能顺序存储。
• 索引存储：在存储元素信息的同时,还建立附加的索引表。索引表中的每项称为索引项，索引项的一般形式是(关键字,地址)。其优点是检索速度快;缺点是附加的索引表额外占用存储空间。另外，增加和删除数据时也要修改索引表，因而会花费较多的时间。
• 散列存储：根据元素的关键字直接计算出该元素的存储地址，又称哈希(Hash) 存储。其优点是检索、增加和删除结点的操作都很快;缺点是若散列函数不好，则可能出现元素存储单元的冲突，而解决冲突会增加时间和空间开销。

数据的运算

数据结构有哪些基本操作？

本节例题

链式存储设计，各个节点存储空间可以不连续，但是节点内的存储单元地址必须连续！。节点内部有值域和指向下一个节点的指针，这两个数据的存储单元是连续的。

1.2 算法和算法评价

算法是对特定问题求解步骤的一种描述，指指令的有限序列，其中每一条指令表示一个或者多个操作。有5个特性：

• 有穷性：一个算法必须在有穷的步骤完成并且在有穷的时间内完成，一个步骤必须在有穷的时间内完成。
• 确定性：算法中每一条指令必须有确切的含义，对于相同的输入只能有相同的输出。
• 可行性：算法的操作都可以通过已经实现的基本运算执行有限次数来实现。
• 输入：零个或者多个输入，输入取自某个特点的集合
• 输出：一个或者多个输出，输出是与输入有特定关系的两。

算法需要达到的目标：

• 正确性：算法可以正确的求解问题
• 可读性：算法应该具有良好的可读性
• 健壮性：对于非法输入数据，算法能够适当地做出反应和进行处理，而不会产生奇怪的结果。
• 高效率与低存储需求：效率指的是算法的时间复杂度，存储量就是算法所需要的最大空间需求。

算法效率的度量

分治算法的时间复杂度的计算

时间复杂度<⭐️>

最坏时间复杂度：最坏情况下算法的时间复杂度

平均时间复杂度：所有可能输入实例在等概率出现的情况下，算法的期望运行时间

最好时间复杂度：最好情况下算法的时间复杂度

一般都是考虑最坏时间复杂度，这样可以保证算法的运行时间不会比这个更长。

加法规则：
$$T(n)=T_1(n)+T_2(n)=O(f(n))+O(g(n))=O(max(f(n),g(n)))$$
乘法规则：
$$T(n)=T_1(n)\times T_2(n)=O(f(n))\times O(g(n))=O(max(f(n)\times g(n)))$$
常见的渐进时间复杂度为：
$$O(1)<O(lo{g}_{2}n)<O(n)<O(nlo{g}_{2}n)<O(n^2)<O(n^3)<O(2^n)<O(n!)<O(n^n)$$

空间复杂度

一个程序在执行时除需要存储空间来存放本身所用的指令、常数、变量和输入数据外，还需要一些对数据进行操作的工作单元和存储-一些为实现计算所需信息的辅助空间。若输入数据所占空间只取决于问题本身，和算法无关，则只需分析除输入和程序之外的额外空间。

本节例题

算法就是对问题求解的步骤，我错选了C，C只是算法的特性，但不是算法的定义。

两个有序的列表合并成一个新的列表，利用两个指针从两个列表指，合并成一个降序链表，那么两个指针谁小就把那个头插到待合并的链表里，直到其中一个链表全部合并到新的链表里。这样再将长的那个直接加入到待合并的链表中。所以需要max(m, n)

这里sum += i++ 等价于 i++; sum += i;最后的式子就变成了这样：1 + 2 + 3 + …… + i = (i + 1)i / 2;i循环的次数只需要达到O(x^1/2)

这道题目就不应该呀，很明白的，认真分析一下：每次都是1²,2²,3²,……,x²;所以x最大可以执行到O(n^1/2)

这道题就需要分析一下：外层循环到i，里层就执行i，因此假设外层循环到k，那么循环一共执行了1 + 2 + 2² + 2 ³ + …… + 2^k-1= 2 ^k- 1.外层的k最大可以达到log₂n，那么一共就可以执行n - 1次。时间复杂度就是O(n)

这道题目也是需要具体分析一下的，记住，事件复杂度就是去算操作次数！

设n = 2 ^k; 那么 T(2 ^k) = 2 T(2 ^k-1) + 2 ^k= 2²T(2 ^k-2 ) + 2 * 2 ^k = 2³ T(2 ^k-3) + 3 * 2 ^k = 2^k + k * 2 ^k = 2 ^k (k + 1)

k = log₂n 所以最后的操作数为：n（log₂n + 1） 时间复杂度为O(nlog₂n)

本章总结

对于递归程序如何求时间复杂度？

使用公式进行一步一步的递推

例题：

这是一个求n！的算法，n！=n(n - 1)(n - 2)……1，每一次递归传入的参数都-1，那么只需要递归n次，其实也就是循环n次。所以时间复杂度为O(n).

原文地址：https://blog.csdn.net/weixin_54438368/article/details/136453789

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！