数据结构知识点总结

上传者：田卫
|
上传时间：2015-05-05
|
密次下载

数据结构知识点总结

数据结构知识点总结

第一章绪论

1. 数据结构(Data Structure)：是指相互之间具有(存在)一定联系(关系)的数据元素的集合。元素之间的相互联系(关系)称为逻辑结构。数据元素之间的逻辑结构有四种基本类型： ① 集合：结构中的数据元素除了“同属于一个集合”外，没有其它关系。

② 线性结构：结构中的数据元素之间存在一对一的关系。

③ 树型结构：结构中的数据元素之间存在一对多的关系。

④ 图状结构或网状结构：结构中的数据元素之间存在多对多的关系。

2. 算法(Algorithm)：是对特定问题求解方法(步骤)的一种描述，是指令的有限序列，其中每一条指令表示一个或多个操作。

算法具有以下五个特性

①有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。 ②确定性：算法中每一条指令必须有确切的含义。不存在二义性。且算法只有一个入口和一个出口。

③可行性：一个算法是能行的。即算法描述的操作都可以通过已经实现的基本运算执行有限次来实现。

④ 输入：一个算法有零个或多个输入，这些输入取自于某个特定的对象集合。 ⑤ 输出：一个算法有一个或多个输出，这些输出是同输入有着某些特定关系的量。

一个算法可以用多种方法描述，主要有：使用自然语言描述；使用形式语言描述；使用计算机程序设计语言描述。

3. 算法设计的要求

①正确性 ② 可读性 ③ 健壮性 ④ 通用性

4. 时间复杂度：

表示时间复杂度的阶有：

O(1)：常量阶；O(n)：线性阶；O(log n)：对数阶；O(nlog n)：线性对数阶

以下六种计算算法时间的多项式是最常用的。其关系为：

O(1)<O(logn)<O(n)<O(nlogn)<O()<O()

指数时间的关系为：

O(2n)<O(n!)<O()

5. 空间复杂度

一维数组a[n]：空间复杂度 O(n)

二维数组a[n][m]：空间复杂度 O(n*m)

第二章线性表

1. 线性表(Linear List) ：是由n(n≧0)个数据元素(结点)a1，a2， …an组成的有限序列。该序列中的所有结点具有相同的数据类型。其中数据元素的个数n称为线性表的长度。当n=0时，称为空表。当n>0时，将非空的线性表记作：(a1，a2，…an) a1称为线性表的第一个(首)结点，an称为线性表的最后一个(尾)结点。a1，a2， ai-1都是ai(2≦i≦n)的前驱，其中ai-1是ai的直接前驱；ai+1，ai+2， an都是ai(1≦i ≦n-1)的后继，其中ai+1是ai的直接后继。

2. 线性表的逻辑结构和顺序结构

线性表中的数据元素ai所代表的具体含义随具体应用的不同而不同，在线性表的定义中，只不过是一个抽象的表示符号。

设线性表的每个元素需占用l个存储单元，以所占的第一个单元的存储地址作为数据元素的存储位置。则线性表中第i+1个数据元素的存储位置LOC(ai+1)和第i个数据元素的存

数据结构知识点总结

储位置LOC(ai)之间满足下列关系：LOC(ai+1)=LOC(ai)+l 线性表的第i个数据元素ai的存储位置为：LOC(ai)=LOC(a1)+(i-1)*l

3. 顺序表的特点：

线性表的顺序存储结构的特点是：逻辑关系上相邻的两个元素在物理位置上也相邻，因此可以随机存取表中任意元素。弱点：在插入或删除操作时，需移动大量元素。

4. 线性表的链式存储结构

链式存储：用一组任意的存储单元存储线性表中的数据元素。用这种方法存储的线性表简称线性链表。

存储链表中结点的一组任意的存储单元可以是连续的，也可以是不连续的，甚至是零散分布在内存中的任意位置上的。

链表中结点的逻辑顺序和物理顺序不一定相同。