郝斌老师数据结构笔记

### 郝斌老师数据结构笔记知识点总结 #### 数据结构与算法概述 - **定义**: 数据结构涉及如何将现实世界中的复杂问题转化为特定的数据类型及存储结构，并基于这些结构设计算法来解决问题。简单来说，数据结构关注如何存储数据，而算法侧重于如何处理这些数据。 - **数据结构与算法的关系**: - **数据结构**: 包括数据的存储形式（如数组、链表等）及其之间的关系。 - **算法**: 是一系列明确指令的集合，用于解决特定问题或执行特定任务。 - **算法评价标准**: - **时间复杂度**: 衡量算法执行效率的关键指标，通常关注最坏情况下的计算步骤数量。 - **空间复杂度**: 指算法运行过程中所需的最大内存空间。 - **难易程度**: 算法的可理解性和实现难度。 - **健壮性**: 算法应对异常输入的能力。 - **数据结构的重要性**: 数据结构被视为软件开发的核心课程之一，对于编写高效且易于维护的代码至关重要。 #### 数据库与数据结构的区别 - **数据库**: 更像是数据结构的一种应用形式，专注于数据的组织、存储和检索。 - **数据结构**: 关注数据的逻辑结构和物理结构，以及它们之间的关系。 #### 预备知识 - **指针**: C语言中极其重要的概念，用于存储内存地址。 - **定义**: 指针是一个变量，用于存储其他变量的地址。 - **地址**: 内存单元的标识符，CPU只能访问内存，而不能直接访问硬盘。 - **指针变量**: 专门用来存储地址的变量。 - **指针运算**: - 指针与整数的加减运算表示相对于原地址的偏移。 - 同一数组中的指针可以进行相减操作。 - 不同类型的指针不能直接比较大小。 - **通过函数修改变量值**: - 要修改主函数中的变量值，可以通过传递变量的地址给被调函数实现。 - 被调函数中通过指针解引用操作可以直接修改主函数中的变量。 #### 结构体 - **出现原因**: 为了表示更为复杂的数据结构，基本数据类型不足以满足需求。 - **定义**: 结构体是由用户自定义的数据类型，允许组合不同类型的变量形成复合数据类型。 - **成员变量**: 结构体内部包含的变量。 - **成员函数**: 可以对结构体成员变量进行操作的函数。 #### C语言中的指针与数组 - **数组名**: 代表数组的首元素地址，本质上是一个指针。 - **一维数组名**: 总是指向数组的第一个元素。 - **下标与指针的关系**: `a[i]` 等价于 `*(a + i)`。 - **指针的算术运算**: - `p + i` 的值是 `p + i * sizeof(*p)`。 - `p - i` 的值是 `p - i * sizeof(*p)`。 - 指针不能进行乘法或除法运算，但可以与整数进行加减操作。 #### 动态内存分配与释放 - **动态内存**: 在程序运行时动态分配和释放的内存。 - **malloc()**: 分配指定大小的内存块。 - **free()**: 释放之前分配的内存。 #### 总结 郝斌老师的笔记强调了数据结构与算法的基础知识，包括但不限于数据结构的定义、算法的评估标准、指针的概念与使用方法、结构体的定义及其应用场景。通过对这些核心概念的深入理解，能够帮助学习者更好地掌握高级编程技巧，尤其是在处理复杂数据结构和算法设计方面。此外，通过具体示例展示了如何利用指针来有效地管理内存资源，这对于提高程序性能具有重要意义。