数据结构考研冲刺讲义：逻辑结构与存储方式解析

"2009考研计算机冲刺班数据结构讲义-崔微.doc" 这篇文档是针对准备2009年计算机专业考研的学生所编写的关于数据结构的讲义，作者为崔微。文档旨在帮助考生梳理数据结构的核心概念和重要知识点。 1. 数据结构的定义：数据结构是一门研究非数值计算的程序设计问题中数据的操作对象、它们之间的关系以及操作的学科。它是一个二元组Data_Structure = (D, R)，其中D代表数据元素的有限集合，R代表D上关系的有限集合。 2. 数据与数据元素：数据是对信息的符号表示，是计算机程序处理的对象。数据元素是数据的基本单位，由一个或多个数据项组成，数据项是不可分割的最小单位。数据对象是性质相同的数据元素集合。 3. 抽象数据类型（ADT）：ADT是一个数学模型，包括数据类型定义的数据集D、数据上的操作集S以及这些操作的定义P，通常表示为(D, S, P)。它是对数据结构的逻辑定义，独立于具体的实现方式。 4. 数据的逻辑结构：逻辑结构描述了数据元素之间的关系，主要包括集合、线性结构（如数组、链表）、树型结构（如二叉树、堆）和图状结构（如网、图）。 5. 存储结构：数据的物理表示，有顺序存储、链式存储、索引存储和散列存储四种基本方法。顺序存储适合线性结构，链式存储可以灵活处理结构变化，索引存储通过索引快速访问，散列存储则利用哈希函数实现快速查找。 6. 算法：算法是解决问题的指令序列，应具备有穷性、确定性、可行性、输入和输出五个特性。评价算法好坏主要看其正确性、可读性、健壮性和效率，效率通常通过时间复杂度来衡量。 7. 时间复杂度分析：时间复杂度表示算法运行时间与问题规模n的关系，常见的渐进时间复杂度有Ο(1)至Ο(nn)等，其中Ο(n!)表示最坏情况。在不同的输入数据集下，时间复杂度可能不同。 8. 空间复杂度：衡量算法所需额外空间，如果与输入数据量相比是常数，则称算法为原地工作。 9. 举例分析：文档中提供了两个嵌套循环的例子，用于解释时间复杂度的计算，第一个例子的语句频度是n(n+1)/2，第二个例子没有给出完整代码，但可以看出是涉及两层循环，其时间复杂度与n的平方有关。 这份讲义全面介绍了数据结构的基本概念和重要知识点，对于准备考研的学生来说，是复习和理解数据结构的关键参考资料。