数据结构基础概念VIP专享VIP免费

第一章 绪论 程序设计的一般过程是“问题——想法——算法——程序”，其实质是数据表示和数据处理。 数据结构是研究非数值问题中计算机的操作对象以及它们之间关系和操作的学科。 数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 数据项是数据的最小单位，数据元素是讨论数据结构时涉及的最小数据单位。 从逻辑关系上讲，数据结构主要分为集合，线性结构，树结构，图结构。 数据的内存结构主要有顺序存储结构，链接存储结构两种基本方法，不论哪种存储结构，都要存储两方面的内容:数据元素和数据元素之间的关系。 算法具有五个特性分别是有零个或多个输入，有一个或多个输出，有穷性，确定性，可行性。 算法的描述方法通常有自然语言，程序设计语言，流程图和伪代码，其中伪代码被称为算法语言。 在一般情况下，一个算法的时间复杂度是问题规模的函数。 顺序存储结构中数据元素之间的逻辑关系是由存储位置表示的，链接存储结构中的数据元素之间的逻辑关系是由指针表示的。 可以用抽象数据类型定义一个完整的数据元素。 算法指的是对特定问题求解步骤的一种描述，是指令的有限序列。 算法分析的目的是分析算法的效率以求改进，算法分析的两个主要方面是数据复杂性和程序复杂性。 时间复杂度要通过算法中基本语句执行次数的数量级来确定。 逻辑结构与数据元素本身的内容和形式无关。 顺序存储结构的特点是用元素在存储器中的相对位置来表示数据元素之间的逻辑关系，链接存储结构的特点是用指示元素存储地址的指针表示数据元素之间的逻辑关系。 算法在发生非法操作时可以做出处理的特性称为健壮性。 常见的算法时间复杂度用大O 记号表示为：常数阶 O（1），对数阶O(lo g2n )，线性阶O（n ），平方阶O(n ^2)，指数阶O(2^n ) 第二章 线性表 对顺序表和单链表的比较要考虑时间性能和空间性能两个方面。作为一般规律，若线性表需频繁查找却很少进行插入和是删除操作，或其操作和“数据元素在线性表中的位置”密切相关时，宜采用顺序表作为存储结构；若线性表需频繁进行插入和删除操作，则宜采用单链表作为存储结构；当线性表元素个数变化较大或者未知时，最好使用单链表实现；若用户事先知道线性表的大致长度，使用顺序表的空间效率会更高。 对于顺序表，在等概率情况下，插入和删除一个元素平均需移表长的一半个元素，具体移动元素的个数与表长和该元素在表中的位置有关。 单链表中设头结点...