数据结构大纲.pdf

数据结构=个体的存储+个体关系的存储；

核心研究的是个体关系的存储

算法=对存储数据的操作；

算法的衡量标准：时间复杂度（程序大概执行的次数，不是时
间）；空间复杂度；程序的健壮性；程序的难易程度；

数据结构：

一，线性结构【把所有的节点用一根直线穿起来】

连续存储【数组】

优点：存取速度快；

缺点：插入删除元素很慢；事先必须知道数组的长度；需要大
块的内存块

离散存储【链表】

优点：空间没有限制；插入删除元素很快；

缺点：存取的速度很慢；

定义：

n个节点连续分配；

彼此通过指针相连；

每个节点只有一个前驱节点，每个节点只有一个
后续节点；
首节点没有前驱节点为节点没有后续节点；

术语：

首节点：第一个有效的节点

尾节点：最后一个有效的节点

头结点：

头结点的数据类型和首结点的数据类型
一样

第一个有效节点之前的那个节点；头结
点并不存放有效数据；

加头结点主要是为了方便对链表的操作

头指针：指向头结点的指针变量

尾指针：指向尾结点的指针变量

如果希望通过一个函数来对链表进行处理，我们至
少需要接收链表的哪些参数只需要一个参数：头指针；

因为我们通过头指针可以推算出链表的其他参数；

分类：

单链表

双联表：每一个节点有两个指针域

循环链表：能通过任何一个节点找到其他
所有节点
非循环链表

算法：

狭义的算法：是与数据的存储方式密切相
关；

广义的算法：是与数据的存储方式无关；

泛型：利用某种技术达到的效
果就是：不同的存储方式，执行的操作是一样的；（c++中的模
板）

同一种逻辑结构，无论
该逻辑结构物理存储是什么样子的

我们可以对它执行相同
的操作

遍历

查找

清空

销毁

求长度

排序

删除结点

插入节点

线性结构的两种常见应用之一【栈】

定义：

一种可以实现“先进后出的存储结构”

栈类似于箱子；

分类：

静态栈：

动态栈：

算法：

出栈

压栈

静态分配变量内存在栈里面分配，动态内存分配在堆里面
分配；

应用

函数调用

中断

表达式求值

内存分配

缓冲处理

迷宫
线性结构的两种常见应用之二【队列】

定义：一种可以实现“先进先出”的存储结构

分类：链式队列--用链表实现；静态队列--用数组实现

静态队列：

静态队列通常都必须是循环队列

讲解：

1.静态队列为什么必须是循环队列

2.循环队列需要几个参数来确定

需要两个参数确定font和rear

3.循环队列参数的含义

两个参数不同场合有不同的含义

1）队列初始化

font和rear的值都是零

2）队列非空

font代表的是队列的的第一个
元素

rear代表的是队列的最后一个
元素的下一个元素

3）队列空

front和rear的值相等但不一
定是零

4.循环队列入队伪算法

两步完成：

1.将值存入rear所代表的位置

2.错误写法：rear=rear+1

正确写法：rear=（rear+1）%数组
长度

5.循环队列出队伪算法

两步完成：

1.将font所代表的位置的值保存

2.错误写法：font=font+1

正确写法：font=（font+1）%数组
长度

6.如何判断循环队列是否为空

如果font和rear的值相等则该队列
一定为空

7.如何判断循环队列是否已满

font的值和rear的值之间无大小关
系

两种方式：
1.多增加一个参数队列的长度

2.少用一个元素（当队列长度为
数组长度-1时队列已满）

如果f和r相邻是队列已满;

if（（r+1）%数组长度==f）

队列已满

else

队列不满

算法:

入队；出队；

队列的应用：

所有和时间有关的操作；

递归

定义：一个函数自己直接或间接调用自己

像这种明确执行次数的问题都用递归来解决

递归要满足的三个条件：

1.递归必须得有一个明确的终止条件

2.该函数所处理的数据规模必须在递减

3.这个转化必须是可解的
循环和递归:

递归：易于理解；速度慢；存储空间大；

循环：不易理解；速度快；存储空间小；

举例

1.求阶乘

2.1+2+3+4...+100的和

3.汉诺塔

4.走迷宫

函数调用的过程：

递归的应用：
树和森林就是以递归的方式定义的

树和图的很多算法都是以递归来实现的

很多数学公式就是以递归的方式定义的

二，非线性结构

树

定义：1）（树的递归定义）有且只有一个成为根的节点，
有若干个互不相交的子树，这些子树本身也是一棵树；

2）树是由结点和边组成的，每个节点只有一个父节
点但可以有多个子节点，但有一个节点例外

该节点没有父节点，此节点成为根节