发帖
雷达卡
数据结构
一、核心概念解析
1. 数据结构的定义
广义角度：研究如何在计算机内存中高效地组织数据，以支持大规模数据的增、删、改、查等基本操作。
狭义角度：指具有一个或多个特定关系的数据元素所组成的集合。
2. 逻辑结构与物理结构对比
（1）逻辑结构 —— 从人类思维理解数据间的关系
| 类型 | 关系描述 | 示例 |
|---|---|---|
| 集合 | 元素之间无直接关联 | 数学中的集合模型 |
| 线性 | 一对一的关系（如排队） | 数组、链表 |
| 树 | 一对多的层级结构 | 文件目录、家谱图谱 |
| 图 | 多对多的网状连接 | 地图路径、社交网络关系 |
（2）物理结构 —— 数据在内存中的实际存储方式
| 类型 | 存储特点 | 逻辑与物理关系一致性 |
|---|---|---|
| 线性存储 | 使用连续的内存单元进行存储（例如数组） | 一致 |
| 链式存储 | 利用任意分布的内存空间，通过指针链接节点（如链表），可连续也可不连续 | 不一致 |
malloc3. 基本术语说明
- 数据：程序处理的对象，是输入和输出的基本单位，在C语言中体现为变量。
- 数据元素：表示一个完整信息实体，包含多个属性（即“数据项”），通常用结构体实现。
struct.h二、算法基础：解决问题的具体步骤
1. 算法的定义与四大特征
定义：针对特定问题求解的一组有限指令序列，每条指令代表一个或多个可执行操作。
特征包括：
- 输入输出性：可以有零个或多个输入，但必须至少有一个输出结果。
- 有穷性：算法应在有限步内结束，不能陷入无限循环；且每一步都能在合理时间内完成。
- 确定性：相同的输入必定产生唯一的输出结果。
- 可行性：所有操作都应是可实现的，比如算术运算、逻辑判断等基础操作。
2. 算法设计的核心目标
- 正确性：语法无误；对合法输入能给出正确响应；对非法输入能按规范处理；经受极端测试案例考验。
- 可读性：代码清晰易懂，便于他人阅读、交流与维护。
- 健壮性：当输入异常时能够妥善处理错误，避免系统崩溃。
- 高效性：资源占用少，运行速度快，兼顾时间与空间效率。
3. 时间复杂度分析
定义：用于评估算法执行时间随问题规模增长的趋势，重点关注增长率而非具体数值。
推导规则如下：
- 将所有加法常数项替换为常数
1； - 仅保留最高阶项；
- 将最高阶项的系数化简为
1。
11常见时间复杂度阶数（效率由高到低排列）：
O(1) < O(logn) < O(n) < O(nlogn) < O(n?) < O(n?) < O(2?) < O(n!) < O(n?)三、线性表：有序数据的存储机制
1. 定义与存储特性
定义：由零个或多个数据元素构成的有限序列。其内存空间位于堆区，生命周期由动态分配函数控制。
mallocfree抽象数据类型（ADT）示例（基于通用数据类型设计）：
DATATYPEtypedef struct person { // 数据元素（含数据项）
char name[32]; char sex; int age; int score;
} DATATYPE;
typedef struct list { // 顺序表结构
DATATYPE *head; // 数据存储区（堆区数组）
int tlen; // 总长度（容量）
int clen; // 当前长度（元素个数）
} SeqList;2. 顺序存储结构（SeqList）
（1）核心接口设计
SeqList* CreateSeqList(int len); // 创建（指定初始容量）
int DestroySeqList(SeqList* list); // 销毁（释放堆空间）
int InsertTailSeqList(SeqList* list, DATATYPE data); // 尾插
int InsertPosSeqList(SeqList* list, DATATYPE data, int pos); // 按位置插
int DeleteSeqList(SeqList* list, char* name); // 按条件删
int ShowSeqList(SeqList* list); // 遍历
// ...（判空IsEmpty、判满IsFull、查找Find、修改Modify、清空Clear等）（2）优缺点对比
| 优点 | 缺点 |
|---|---|
| 无需额外空间存储逻辑关系 | 插入或删除操作需移动大量元素，时间复杂度为 O(n) |
| 支持随机访问，访问时间为 O(1)，例如 arr[i] | 容量固定，无法动态扩展，需预先分配足够空间 |
3. 链式存储结构（单向链表）—— 克服顺序表局限
（1）基本组成
每个节点（Node）包含两个部分：
- 数据域：用于存储实际数据元素；
- 指针域：保存下一个节点的地址信息。
typedef struct node {
DATATYPE data; // 数据域
struct node* next; // 指针域（指向下一节点）
} LinkNode;
typedef struct list { // 链表结构
LinkNode* head; // 头节点（不存数据，仅作入口）
int clen; // 当前元素个数
} LinkList;（2）关键接口功能
旨在实现动态内存管理，并使插入与删除操作达到 O(1) 的理想效率。
LinkList* CreateLinkList(); // 创建空链表
int InsertHeadLinkList(LinkList* list, DATATYPE* data); // 头插（O(1)）
int InsertTailLinkList(LinkList* list, DATATYPE* data); // 尾插（O(n)）
int DeleteLinkList(LinkList* list, char* name); // 按条件删（需prev指针定位前驱）
DATATYPE* FindLinkList2(LinkList* list, PFUN fun, void* arg); // 函数指针解耦查找条件
int DestroyLinkList(LinkList* list); // 销毁（先删节点，再删头）
// ...（遍历Show、修改Modify、判空IsEmpty、求长度GetSize等）（3）主要优势
- 支持动态内存分配，按需申请节点空间，无需预设容量；
malloc四、开发工具与实践要点
内存泄漏检测方法
建议安装专用检测工具，通过指定命令行指令监控堆区内存的分配与释放情况，及时发现潜在泄漏问题。
valgrindvalgrind ./可执行文件核心总结
- 数据结构：关注数据之间的逻辑关系及其在内存中的物理存储方式。逻辑结构分为集合、线性、树形和图形结构；物理结构则分为连续的线性存储和离散的链式存储。
- 算法：具备输入/输出、有穷性、确定性和可行性四大特征。设计上追求正确、可读、健壮和高效的统一。时间复杂度是衡量其性能的重要指标。
- 线性表：顺序存储适合频繁访问但较少修改的场景，具备O(1)访问优势；链式存储适用于频繁插入删除的应用，支持动态扩容，操作更灵活。两者均可通过统一的ADT接口封装操作逻辑。
- 单向链表：由数据域和指针域构成的节点串联而成，通过动态内存分配实现灵活管理。头插法时间复杂度为O(1)，尾插为O(n)。使用函数指针可实现查找条件的解耦与复用。
京公网安备 11010802022788号
