数据结构
-
数据结构的定义
- 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。
- 例如，学生信息管理系统中每个学生的信息（姓名、年龄、学号等）构成一个数据元素，所有学生信息组成的数据结构可用于管理和操作这些数据。
-
逻辑结构
- 集合：所有数据平等地处于同一集合中，没有明显的相互关系。例如，在一个学校中，所有学生组成的集合，不考虑学生之间的其他关联时，就是集合结构。
- 线性：数据之间是一对一的关系。如数组，
int arr[5] = {1, 2, 3, 4, 5};，每个元素与其相邻元素存在一对一的顺序关系。 - 树：呈现一对多的关系。例如，公司的组织结构图，一个领导对应多个下属。
- 图：多对多的关系。像城市之间的交通网络，一个城市可以与多个城市有道路连接，同时也被多个城市连接。
-
物理结构
- 顺序存储：数据存放在连续的存储单元中，逻辑关系和物理关系一致。比如数组，在内存中是连续存放的。
int arr[10];，arr[0]、arr[1]等元素在内存中是依次相邻的。 - 链式：数据存放的存储单元可以是随机或任意的，可以连续也可以不连续。例如链表，每个节点包含数据和指向下一个节点的指针，节点在内存中的位置可以不连续。
- 顺序存储：数据存放在连续的存储单元中，逻辑关系和物理关系一致。比如数组，在内存中是连续存放的。
-
数据元素、数据对象和数据类型
struct Per 数据元素{char name;//数据项int age;char phone;} struct Per list[100]; //数据对象- 数据元素：例如
struct Per结构体定义了一个人的信息作为数据元素，其中包含char name、int age和char phone等数据项。 - 数据对象：
struct Per list[100];是一个数据对象，它是具有相同数据结构的元素的集合。 - 数据类型
- 原子类型：像
int、char、float等基本数据类型，int num = 5;，num只能存储整数。 - 结构类型：如
struct、union。struct可以组合多个不同类型的数据项，union可以使多个成员共享同一段内存。 - 抽象数据类型 ADT（abstract data type）：是数学模型和操作的结合。例如栈，它的数学模型是后进先出（LIFO），操作包括入栈、出栈等。
- 原子类型：像
- 数据元素：例如
算法
-
算法的定义
- 算法是解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，每条指令表示一个或多个操作。比如计算一个数组中所有元素的和，从第一个元素开始依次相加直到最后一个元素的过程就是一个算法。
-
算法的特征
- 输入、输出特性：输入是可选的，例如计算
1+2+3不需要额外输入，但有些算法需要输入数据。输出是必须的，算法执行完要有结果输出，如排序算法输出排序后的数组。 - 有穷性：执行的步骤会自动结束，不能是死循环，并且每一步是在可以接受的时间内完成。例如求两个数的最大公约数的欧几里得算法，经过有限步计算就会得到结果，而不是无限循环下去。
- 确定性：对于给定的输入，算法的输出是唯一确定的。比如对一个有序数组进行二分查找，相同的查找值每次执行算法都会得到相同的结果。
- 可行性：每一个步骤都是可以实现的。
- 输入、输出特性：输入是可选的，例如计算
-
算法的设计要求
- 正确性
- 语法正确：算法在编程实现时要符合编程语言的语法规则。
- 合法输入能得到合理结果：如编写一个除法算法，当除数不为 0 时应能正确计算商。
- 对非法输入给出满足要求的规格说明：对于除法算法，当除数为 0 时，应给出明确的错误提示或者按照特定的规则处理。
- 对精心选择、甚至刁难的测试都能正常运行且结果正确：例如对排序算法，要考虑各种不同的输入数据情况，包括有序、无序、部分有序等，算法都应能正确排序。
- 可读性：代码结构清晰、有良好的注释，便于其他人理解。例如在复杂的递归算法中添加详细的注释解释递归的逻辑。
- 健壮性：当输入非法数据时，能进行相应的处理而不是产生异常。比如在接收用户输入的年龄时，如果用户输入了字符，程序应提示用户重新输入而不是崩溃。
- 高效（存储低、效率高）：在设计算法时，要考虑时间和空间复杂度。
- 正确性
-
算法时间复杂度
- 是对执行算法所花时间的度量。例如，在一个简单的循环中遍历一个长度为
n的数组，时间复杂度为O(n)；而直接访问数组中的一个元素，不随数组大小变化而改变操作次数，时间复杂度为O(1)。 - 推导时间复杂度的步骤：
- 用常数 1 取代运行时间中的所有加法常数。
- 在修改后的运行函数中，只保留最高阶项。
- 如果最高阶存在且不是 1，则去除这个项相乘的常数。
- 常见的时间复杂度顺序：
O(1)<O(logn)<O(n)<O(nlogn)<O(n^2)<O(n^3)<O(2^n)<O(n!)<O(n^n)。 - 例如，在一个有序数组中进行二分查找，每次查找都将搜索范围缩小一半，时间复杂度为
O(logn)；而冒泡排序算法，需要比较和交换数组中几乎每一对元素，时间复杂度为O(n^2)。
- 是对执行算法所花时间的度量。例如，在一个简单的循环中遍历一个长度为