数据结构公式速览：35关键知识点总结

本资源汇总了35个关键的数据结构知识点，涵盖了计算机科学中的基础概念和常见操作。以下是这些知识点的详细解释： 1. **时间复杂度** - 提供了不同复杂度级别的表示方法：O(1)表示常数时间，O(log2n)代表对数时间，O(n)是线性时间，O(nlog2n)是线性对数时间，O(n2)是平方时间，O(n3)和O(nk)代表更高阶的多项式时间，O(2n)则是双线性时间。 2. **顺序表操作** - 描述了在顺序表中插入和删除操作的平均移动次数，如插入第i个元素可能需要移动n-i个元素，删除则需移动n-i-1或(n-1)/2次。 3. **动态内存分配** - 使用`malloc`函数为链表节点分配内存，通过定义`p`指向动态分配的`ListNode`或`LinkNode`类型结构。 4. **链表判断** - 单循环链表的头结点判断空条件是`head == head->next`，表示链表是否为空。 5. **共享向量空间** - 共享向量空间满状态检查的简单逻辑是`top1 = top2 - 1`，意味着当两个指针重合时，表示空间已满。 6. **队列操作** - 队列操作包括入队`EnQueue`和出队`DeQueue`，队列为空和避免假溢出的特殊情况处理，例如使用循环队列时，队满的条件是`(rear+1)%m = front`。 7. **队列状态检查** - 链队列的空判断通过`Q->front = Q->rear = NULL`，队列长度计算可能涉及循环队列的特殊处理。 8. **字符串操作** - 包括字符串长度计算`strlen`、复制`strcpy`、连接`strcat`、比较`strcmp`等，以及字符定位函数`strchr`。 9. **字符串处理算法** - 如子串定位（模式匹配）的时间复杂度为最坏情况下的O((n-m+1)*m)，体现了查找效率。 10. **数组索引计算** - 提供了二维和三维数组的按行优先和列优先计算下标的公式，如`LOC(a00) + [i*n+j]*d`和`LOC(a000) + [i*n*p+j*p+k]*d`。 11. **矩阵存储** - 对称矩阵的元素总数计算、上三角矩阵和下三角矩阵的存储位置计算，以及对角矩阵的特点（元素为零的条件）。 12. **三元组表** - 描述了三元组表（行、列、值）的结构及其转置操作的时间复杂度，以及带行表的顺序存储结构特点。 13. **二叉树性质** - 计算二叉树各层节点数、深度与结点总数的关系，包括终端结点、度为2的结点数量和二叉树总结点数的公式。 这些知识点覆盖了数据结构基础中的基本概念、算法分析、数组和矩阵操作、链表与队列管理、字符串处理、以及二叉树的特性和遍历等方面，对于学习和理解数据结构具有重要参考价值。