数据结构复习：算法特性与数据结构概览

"数据预算法--数据结构复习-(1) 数据结构预算法.doc" 这篇文档主要探讨了数据结构的相关知识，包括算法特性、数据结构的种类及其特点、栈、递归、队列以及字符串和串匹配算法。以下是详细的内容： 1. 算法特性与评价 - 有穷性：算法必须在有限步骤内结束。 - 确定性：给定相同的输入，算法应产生相同的输出。 - 可行性：算法执行的每一步都在计算能力范围内。 - 输入：算法可能接受零个或多个输入。 - 输出：算法至少需要一个输出，不能无结果。 - 评价标准：正确性、可读性、健壮性和效率。其中，时间复杂度和空间复杂度是衡量效率的重要指标。 2. 数据结构 - 数据和二元关系：数据是信息的载体，二元关系描述了数据之间的关联。 - 等价关系（自反、对称、传递）、偏序和全序：这些都是数学中用于描述数据间关系的形式化概念。 3. 线性表 - 顺序表：存储位置连续，插入和删除操作可能导致大量元素移动，但随机访问速度快。 - 链表：存储位置不连续，插入和删除无需移动其他元素，但无法随机访问。 4. 栈 - 栈是一种后进先出（LIFO）的数据结构，适用于括号匹配、表达式求值等问题。有顺序栈和链式栈两种实现方式。 5. 递归 - 递归用于求解各种问题，如阶乘、最大公因子、斐波那契数列和汉诺塔问题。 - 尾递归：递归调用作为函数的最后操作，可优化为循环。 - 递归消除：通常通过迭代或显式栈来实现。 6. 队列 - 队列是一种先进先出（FIFO）的数据结构，队空和队满的处理是关键。循环队列和链式队列是常见实现。 7. 串与串匹配 - 子串在主串中的位置是指首次出现的位置，起始位置从0计数。 - Brute-Force算法是最直观的匹配方法，但效率低。 - KMP算法利用预处理的Next函数，提高匹配效率至线性时间复杂度。 这篇文档适合用于复习数据结构的基础知识，特别是对于准备算法竞赛、编程面试或学习数据结构的学生来说，提供了很好的复习材料。