数据结构与算法.pdf

数据结构与算法

1.数据结构

数据结构是带结构的数据元素的集合。（结构是指数据元素之间的关系）

数据结构包含：

逻辑结构：数据之间的逻辑关系

物理结构（存储结构）：数据元素及其关系在计算机内部的表示

数据的运算和实现

2.逻辑结构

线性结构：有且只有一个开始和一个终端结点，并且所有结点最多只有一个直接

前驱和一个直接后继。

非线性结构：一个结点可能有多个直接前驱和直接后继；具体有集合结构，树形

结构，图状结构。

3.存储结构

顺序存储结构：用一组连续的存储单元依次存储数据元素，数据元素之间的逻辑关系由

元素的存储位置来表示。优点：随机存取；缺点：只能使用相邻的一整块存储单元，可

能产生较多外部水片。

链式存储结构：用一组任意的存储单元存储数据元素，数据元素之间的逻辑关系用指针

来表示。优点：不会产生碎片现象，能充分利用所有存储单元；缺点：每个元素因指针

而占用额外的存储空间，只能实现顺序存储。

索引存储结构：在存储元素信息的同时，还建立附加的索引表。优点：检索速度快；缺

点：索引表占用额外的存储空间，增加和删除数据会修改索引表，耗时较多。

散列存储结构：根据元素的关键字直接计算出该元素的存储地址。优点：检索、增加、

删除结点操作很快；缺点：可能出现冲突，解决冲突会增加时间和空间开销。

4.数据类型

数据类型是一组性质相同的值的集合，以及定义于这个集合上的一组操作的总称。

在C语言中，声明了某个数据类型的变量，意味着规定了该变量的存储空间大小，以及

能够执行的运算。

5.抽象数据类型（AbstractDataType,ADT）三要素D,S,P

数据对象

数据对象的关系集

数据对象的操作集

6.算法

算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每条指令表示一个

或多个操作。此外算法具有如下5个重要特性：

有穷性：一个算法必须总在执行有穷不之后结束，且每一步都可在有穷时间内完

成；

确定性：算法中每条指令必须有确切的含义，对于相同的输入只得得到相同的输

出；

可行性：算法中描述的操作都可以通过已经实现的基本运算执行有限次来实现；

输入

输出

7.算法效率的度量

时间复杂度

时间复杂度是指算法中基本运算的执行次数的数量级。

空间复杂度

空间复杂度是指算法运行过程中所使用的辅助空间的数量级；

例如O(1)表示的是该算法最多只使用常数个额外的辅助空间，而不是不使用辅助

空间。

O，,的含义

8.递归

1.递归是指函数的定义中直接或间接调用自身的一类描述问题和解决问题的方法；

2.递归有一个明确的递归结束条件，称为递归出口。

9.程序

程序是某种程序设计语言对算法的实现。简单理解为：程序=数据结构+算法

10.线性表

线性表是具有相同数据类型的n(n0)个数据元素的有限序列，表示为（a1,a2,...,an）.

具有的逻辑特征：

非空的线性表有且只有一个开始结点，它没有直接qi

非空的线性表有且只有一个结束结点，它没有直接后继，有且只有一个直接前

驱；

其余的内部结点都有且只有一个直接前驱和直接后继；

11.顺序表vs链表

顺序表既可以顺序访问，也可以随机访问；链表只能顺序访问。

顺序表的元素，逻辑上相邻的元素，对应的物理存储位置也相邻；链表则不一定。

顺序表插入删除一般需要移动元素的位置，效率较低；链表插入删除只需要修改相关结

点的指针域。

12.静态链表：借助数组来描述线性表的链式存储结构。

13.栈：后进先出LIFO

14.队列：先进先出F