下载后可任意编辑《数据结构》复习重点第一章 绪论要求、目标：了解数据逻辑结构的分类；掌握算法的特性及估算算法时间复杂度的方法；熟悉数据结构的基本基本概念和术语。一、基本概念和术语1．数据结构：是一门讨论非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科。2．数据：是对客观事物的符号表示，即所有能输入到计算机中并被计算机程序处理的符号的总称。3．数据项：数据的不可分割的最小单位。4．数据元素（数据结点）：数据的基本单位，在程序中作为一个整体处理由若干数据项组成。5．数据对象：性质相同的数据元素的集合，是数据的一个子集如：四季对象是集合：{春，夏，秋，冬}自然数对象是集合：{0，1，2，3，…}字母字符对象是集合 ：{‘A’，‘B’，…‘Z’}6．数据结构的分类：线性结构和非线性结构。7．数据结构的形式化定义：数据结构是一个二元组，可定义为Data_Structure=(D,S)其中：D 是数据元素的有限集合，S 是 D 上关系的有限集合8．序偶：两个元素间的前后关系。
a 是 b 的前驱结点，b 是 a 的后继结点例：四季的描述 B=（D，R） D={春，夏，秋，冬} R={<春，夏>,<夏，秋>,<秋，冬>}9．物理结构（存储结构或映像）：数据结构在计算机中的表示。10．存储结构的分类：① 顺序存储结构：利用元素的相对位置来表示元素间的位置关系，是1下载后可任意编辑一种随机存取结构，逻辑上相邻的数据物理上也紧临，静态分配空间；② 链式存储结构：借助元素存储的指针来表示元素之间的关系，逻辑上相邻的数据物理上不一定紧临，动态分配空间。11．逻辑结构和物理结构的关系：是密切相关的两个方面，任何一个算法的设计取决于逻辑结构，而算法的实现则依赖于采纳的存储结构。12．数据类型：是一个值的集合和定义在这个值集上的一组操作的总称，规定了在程序执行期间变量或表达式所有可能取值的范围，以及在这些值上允许进行的操作。二、算法和算法分析 1．算法：是对特定问题求解步骤的一种描述，它是指令的有限序列。 2．算法的特性：① 有穷性：算法在执行有究步之后结束，每一步在有穷时间内完成。② 确定性：每一条指令必须有确切的含义，不应产生二义性，相同的输入只能得出相同的输出。③ 可行性：一个算法可以通过已经实现的基本运算执行有限次来实现。④ 输入性：一个算法有零个或多个输入。⑤ 输出性：一个算法有一个或多个输出。 3．算法分析考虑的方面： ① 正确...
