使用教材：严蔚敏，吴伟民编写的《数据结构》

但是书中的算法都是伪算法（不是程序），都是解题的思路

具体的程序由高一凡主编的书里面有。

黄国瑜写的数据结构也可以。

数据结构概述

定义：

我们如何把现实中大量而复杂的问题以特定的数据结构

和特定的存储结构保存到主存储器（内存）中，以及在

此基础上为实现某个功能（比如查找某个元素，删除某

个元素，对所有元素进行排序），而执行的相应操作，这

个相应的操作也叫算法。

如保存一个班级学生的信息，使用数组就可以。

但是保存一万个学生信息，就没有这么大的连续空间，

可以使用链表实现。如保存人事单，如果使用链表则不知道他们之间的关系

谁是领导，这种结构需要使用树结构。

再如交通图，几个站点之间修路，则需要使用图结构实现。

解决两个问题 1：复杂问题转换成数据以及数据怎么存储（个体怎么保存，

个体与个体之间的关系怎么保存）

2：数据的操作

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

算法 = 对存储数据的操作（对数据的操作依赖于特定的存储结构）

程序 = 数据的存储+数据的操作+可以被计算机执行的语言。

算法：

换种说法：解题的方法与步骤

衡量算法的标准：

1：时间复杂度：大概程序要执行的次数（一般最核心的步骤是循环），

而不是执行的时间。

因为不同的机器性能，状态存在差异

2：空间复杂度

算法执行过程中所占用的最大内存

3：难易程度

难度低，大家理解比较容易

4：健壮性，能应对各种非法输入。

2017年11月8日13:25:42

数据结构的地位

数据结构是软件中最核心的课程。栈内存与堆内存并不存在，只是

分配的内存的方法不一样。

很重要，难度很大，属于内化的课程。

预备知识

学习数据结构两种学习方法

1：只学习伪算法，不看具体的实现方法

2：通过编程语言实现它，带有指针的语言C/C++来实现

最重点的是链表的部分之间的知识，指针知识。

指针

指针的重要性：

指针是C语言的灵魂。

定义：地址，内存单元的编号。从零开始的非负整数，范围;0-- 4G-1

指针就是地址，地址就是指针。

指针变量是存放内存单元地址的变量。

指针的本质是一个操作受限的非负整数。

CPU通过地址总线，数据总线，控制总线来与内存进行数据的存储

读等操作。内存是CPU可以唯一访问的大容量存储设备。

内存以8位有一个编号，分别是0 --- 4G-1。但是编号为0的内存

单元不存放有用数据，因此没有指向的指针都要指向NULL，不能

没有指向。

分类：

1：基本类型指针（见源码）

内存是在操作系统的统一管理下使用的！

1. 软件在运行前需要向操作系统申请存储空间，在内存空闲

空间足够时，操作系统将分配一段内存空间并将外存储中的软

件拷贝一份存入内存空间中，并启动该软件运行！

2. 在软件运行期间，该内存所占内存空间不再分配给其他软件。

3. 当软件运行完毕，操作系统将回收该空间，（注意操作系统并

不清空该空间遗留下来的数据）以便再次分配给其他软件使用。

4. 综上所述，一个软件所分配的空间中极有可能存在着以前其他软

件使用过后的残留数据，这些数据成为垃圾数据。所以，我们为一个变量，

一个数组，分配好存储空间后要对该空间内存进行初始化

2：指针与数组的关系（具体参见源码文件夹下面的“指针”文档）

2、指针和数组

指针 和 一维数组

数组名

一维数组名是个指针常量，

它存放的是一维数组第一个元素的地址，

它的值不能被改变

一维数组名指向的是数组的第一个元素

下标和指针的关系

a[i] <<==>> *(a+i) //a指向第一个元素，a+i指向数组中标号为i的元素，然后再取地址

假设指针变量的名字为p

则p+i的值是p+i*(p所指向的变量所占的字节数)

指针变量的运算

指针变量不能相加，不能相乘，不能相除

如果两指针变量属于同一数组，则可以相减

指针变量可以加减一整数，前提是最终结果不能超过指针允许指向的范围

p+i的值是p+i*(p所指向的变量所占的字节数)

p-i的值是p-i*(p所指向的变量所占的字节数)

p++ <==> p+1

p-- <==> p-1

举例

如何通过被调函数修改主调函数中一维数组的内容【如何界定一维数组】

两个参数

存放数组首元素的指针变量

存放数组元素长度的整型变量

结构体

为什么会出现结构体？

为了表示一些复杂的数据类型，而单个基本类型无法满足需要

如表示一个学生点的年龄，性别，学号，

需要把简答数据类型表示一些复杂的事物

如

struct Student

{

int aga;

char address;

char sex;

};//分号不能省略，分号表示结构体定义结束

什么是结构体？

用户根据实际需要字节定义的复合数据类型。没有对数据的操作（c++中的操作）

如何使用结构体？

如何使用结构体

两种方式:

struct Student st = {1000, "zhangsan", 20};

struct Student * pst = &st;

1.

st.sid

2.

pst->sid

pst所指向的结构体变量中的sid这个成员（自己多读几遍）

注意事项：

结构体变量不能加减乘除，但是可以相互赋值

普通结构体变量和结构体指针变量作为函数参数传参的问题

动态内存的分配与释放

动态构造一维数组

假设动态构造一个int型数组

int *p = (int *)malloc(int len);

1、 malloc只有一个int型的形参，表示要求系统分配的字节数

2、 malloc函数的功能是请求系统len个字节的内存空间，如果请求分配成功，

则返回第一个字节的地址，如果分配不成功，则返回NULL

3、 malloc函数能且只能返回第一个字节的地址，所以我们需要把这个无任何实

际意义的第一个字节的地址（俗称干地址）转化为一个有实际意义的地址，因此

malloc前面必须加（数据类型 *）,表示把这个无实际意义的第一个字节的地址

转化为相应类型的地址。如：

int *p = (int *)malloc(50);

表示将系统分配好的50个字节的第一个字节的地址转化为int *型的

地址，更准确的说是把第一个字节的地址转化为四个字节的地址，这

样p就指向了第一个的四个字节，p+1就指向了第2个的四个字节，

p+i就指向了第i+1个的4个字节。p[0]就是第一个元素， p[i]就是第

i+1个元素

double *p = (double *)malloc(80);

表示将系统分配好的80个字节的第一个字节的地址转化为double *型的

地址，更准确的说是把第一个字节的地址转化为8个字节的地址，这

样p就指向了第一个的8个字节，p+1就指向了第2个的8个字节，

p+i就指向了第i+1个的8个字节。p[0]就是第一个元素， p[i]就是第

i+1个元素

free（p）

释放p所指向的内存，而不是释放p本身所占用的内存

模块一：线性结构

什么是线性结构？

把所有的结点（类似于数组的元素）可以用一根直线串起来

分类：

线性存储[数组]

数组元素在内存中是连续分配的

1：什么叫数组？

元素类型相同，大小相等

2：数组的优缺点：

与链表相比较

离线存储[链表]

定义：

（1）n个节点离散分配

（2）彼此通过指针相连接，上一结点保存了下一个结点的地址

（3）每个节点只有一个前驱节点，一个后续节点。首节点没有

前驱节点，尾结点没有后续节点。

链表的重要性：

是我们学习数据结构的基础，如下面的树（一个结点指向下面多个结点）

图（任何一个结点可以保存其他结点的地址）

主页术语：如（头结点，仅仅存放下一个元素的地址）-（1（首节点））-（2）-（5）-（8（尾结点））

首节点：第一个有效结点

尾结点：最后一个有效结点

头结点：第一个有效结点之前的结点（2）头结点不存放有效数据

（3）加头结点的目的是可以方便我们对链表的操作（4）头结点与其他结点数据类型完全一样

头指针：指向头结点的指针变量（可能不对，是指向第一个有效结点的指针）

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

我们在首节点的前面加一个没有实际意义的头结点是因为可以方便我们对链表的操作。

如果我们希望通过函数来对链表进行处理我们至少

需要接受链表的几个参数：

一个参数，（头指针）头结点的地址

因为我们通过头指针就可以推算出链表的所有其他信息。

（尾结点的指针域存储为NULL）

链表分类：

单链表

双链表：每一个结点有两个指针域 [指针][数据][指针]

循环链表：能通过任何一个结点找到其他所有结点。即最后一个

结点又指向了第一个结点

非循环链表

链表的算法：

遍历

查找

清空

销毁

求长度

排序

删除结点

非循环链表的插入的伪算法

（1）r = p->pNext;

（2）p->pNext = q;

（3）q->pNext = r;

如何把q指向的结点放在p指向节点的后面（看图再看下面的步骤）

（1）取出p所指向的结点的指针域

（2）p的指针域指向q

（3）把p的指针域的值（指向p后面的一个元素）赋值给q的指针域，

则q就指向p后面的一个元素

第二种方法（看同目录下的图）

q->pNext = p->pNext;

p->pNext = q;

（1）先使q指向后面一个结点（后面一个结点的地址存放在p的指针域部分）

（2）使p的指针域指向q

（q不是结点，,是一个指针变量，存放了节点的地址）

删除一个非循环链表的节点的伪算法

r = p->pNext;

p->pNext = p->pNext->pNext;//这样写会导致内存泄漏，所以需要释放

free(r);

删除一个链表的结点

（1）找不到第二个结点的地址，所以就不能释放，所以需要先指向

然后释放

（2） p->pNext->pNext //p指针域指向的元素的指针域。

学习数据结构的目的和要求：

（1）对基本的概念有了解，栈 图 树

（2）尽量掌握链表

（3）这是入门课程，为以后自己有机会自学数据结构

链表的优缺点：

算法：

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

而广义的算法与数据的存储结构无关

泛型：

利用某种技术达到的效果就是：不同的存储方式，执行的操作是一样的

（对数据的操作和对数据的存储方式无关）

具体的例子可以参见数组与链表的冒泡排序的例子。

即数组可以使用++符号，而链表需要使用地址来寻找。我们可以使用c++中的运算符

重载就可以屏蔽底层的细节。用户看到的操作是一样的。

2017年11月11日10:48:56

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

定义：

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

栈类似于箱子，先放的在底下，最后取出

分类：

静态栈

如果以数组为内核，如从上到下保存了（0）（1）（2）（3）等几个

元素，我们要想删除元素（2），则必须把前面的元素先删除了。

动态栈

以链表为内核，只能在1首部增加或者删除一个元素。

栈可以执行哪些操作（算法）

出栈

压栈

栈的应用

（1）函数调用（所有的函数调用都是压栈与出栈）

所谓函数A调用函数B就是把A的最后执行的一个语句的地址与调用的B函数的

所有内容压到一个栈内部去执行，执行完毕出栈，然后地址出栈接着执行A函数

（2）中断（中断一个进程去执行下一个进程）

（3）表达式求值（表达式的数值部分与运算符会分开存放，利用两个栈可以制作一个简易计算器）

（4）内存分配（动态内存在堆中分配）

（5）缓冲处理

（6）迷宫（游戏中的地图，为什么走到一部分就走不动了）

线性结构的两种常见应用之二 队列

定义：

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

队列类似于买票，先进先出，

只允许在一端插入元素，在另一端出，不能对中间的元素进行操作

队列的分类：

（1）链式队列（内核是链表）头front 为rear

删除一个元素在队首（front）（出对），添加一个元素在rear（入队）

（2）静态队列（内核是数组）

假设数组中有6个元素，编号为 0 1 2 3 4 5，

把数组的部分功能限制，只能在队首删除，只能在尾部添加元素

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

循环队列的讲解：

（1）静态队列为什么必须是循环队列？（见源码文件夹下的图）

（2）循环队列需要几个参数来确定？

两个参数

队首指针front与队尾指针rear

（3）循环队列各个参数的含义？

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

建议初学者先记住，慢慢体会。

（1）队列初始化

front与near的值都是零（开始时他们指向同一个元素0，赋值后才改变）

（2）队列非空

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

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

（3）队列空

front的值等于rear，但是不一定为空。

（4）循环队列入队伪算法讲解？（见PPT）

两步完成：见PPT

（5）循环队列出队伪算法讲解？（见PPT）

（6）如何判断循环队列是否为空？

如果front与rear的值相等，则判断该队列一定为空

（7）如何判断循环队列是否满？（具体见PPT）

f的大小与r的大小没有确定的关系，不一定r的值一定大于f。

当循环队列存储完全满的时候，r = f，则我们不能判断队列是满还是空。

解决办法有两个，（1）定义另外一个变量，保存有效元素的个数

（2）一直空着一个位置，即当f与r按着时候，就不能存储数字了。

我们采用第二种方法。

队列算法：（1）入队 （2） 出队

队列的具体应用：

所有和时间有关的操作都与队列有关

如任务的等待队列，执行的优先级

专题：递归

定义：

一个函数自己直接或者间接调用自己。

递归满足三个条件：

（1）递归必须有一个明确的终止条件

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

（3）这个转化必须是可解的。

循环和递归的关系

理论上所有的循环都可以转换成递归。

递归可以实现的不一定可以使用循环实现。

递归的特点：

（1）易于理解

（2）速度慢

（3）存储空间大

循环的特点：

（1）不易理解

（2）速度快

（3）存储空间小

递归的应用

（1）树和森林就是以递归的方式定义的，

（2）树和图的大多数算法都是以递归来实现的

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

比如裴波那契数列 1 1 2 3 5 8 13 21

1:1+2+3+.....+100的和

2：求阶乘

3：汉诺塔

4：走迷宫

为什么打游戏的时候为什么可以找到你，为什么到边缘就走不动了？

把整个地图分为很小很小的格子。机器就一个一个方向的走格子，直到找到

通路，（可以同时设置优先级，比如左右方向是优先走），

应用到栈与递归的知识。

模块二：非线性结构（非线性的算法比较复杂，理论没有线性结构的成熟）

树

树的的定义：

根节点向下每个节点指向多个结点（具有层次关系）

专业定义：

（1）有且只有一个称为根的结点

（2）有若干个互不相交的子树，这些子树本身也是一棵树。

通俗的定义：

（1）树是由节点与边组成（边是指针域）

（2）每个节点只有一个父节点但是可以有多个子节点

（3）但有一个节点例外，该节点没有父节点，此节点称为根节点

专业术语：

节点 父节点（注意父节点只有一个，不能跨）

子节点 子孙（父节点下面的全是，可以跨） 堂兄弟（不能使一个父节点的同级）

深度：从根节点到最底层节点的成熟称为深度。

根节点是第一层

叶子节点：没有子节点的结点。

非终端结点：实际就是非叶子节点。

度：

含有最大子节点的个数称为度。

树的分类：

一般树

任意一个节点的子节点的个数都不受限制。

二叉树

任意一个节点的子节点的个数最多2个，且子节点的位置

不可更改。

二叉树的分类：

（1）一般二叉树

（2）满二叉树

在不增加一个树层数的前提下，无法再增加一个

结点的二叉树就是满二叉树。

（3）完全二叉树（定义二叉树是为了后面存储结构）

如果只是删除满二叉树的最底层最右边连续若干个结点，

这样形成的二叉树就是完全二叉树。

满二叉树是完全二叉树的一个特例。

森林

n个互不相交的树的集合。

树的存储：

二叉树存储

连续存储[完全二叉树]

查找某个结点的父节点和子节点速度很快，判断有几个子节点

缺点：内存占用大

链式存储

每一个结点分为三块，左指针，有效数据，右指针（（左指针，指向左边元素）（有效数据）（右结点，指向右侧结点））

一般树的存储

（1）双亲表示法

创建一个双排数组，一排存储有效的元素，另一排存储父节点的下表

（2）孩子表示法

类似双清表示法，另一排存储子节点

（3）双亲孩子表示法

三排，有效元素，中间存储父节点下标，最右侧链表形式的子节点。

（4）二叉树表示法

把一个普通树转换成二叉树来存储

具体转换方法：

设法保证任意一个结点的左指针指向它的第一个孩子

右指针域指向它的兄弟结点。

只要能满足此条件，就可以把一个普通树转换成二叉树

一个普通树转换成的二叉树没有右子树。

森林的存储

一般树必须转换成完全二叉树来存储。（二叉树不是线性结构，保存时，哪个在前，哪个在后是个问题）

步骤：

（1）一般树转换成满二叉树（添加元素）

（2）删除最底层右侧可以删除的结点，转换成完全二叉树。

问题：保存结点的先后顺序？非线性结构转换成线性结构。先序遍历，中序遍历，后续遍历

如果只保存有效结点的值，则不能根据上面三种方法没办法求出原来二叉树的样子。

所以必须以完全二叉树的结构存储。这样存储空间太浪费空间，但是有一个巨大优点：

[教材p124]具有n个节点的完全二叉树的深度为（[log（2）n]+1），告诉我任何一个

结点的的编号，马上可以知道这个结点有几个子节点，父节点的编号。

树的操作：见示意图“森林转化为二叉树示意图.JPG”。

先把森林存储为二叉树，然后再存储二叉树。

树的操作：（重点，其他太难，考这里）

（1）遍历（按照访问根的顺序）

先序遍历（先访问根节点）

先访问根节点，再先序访问左节点，先序访问右子树

中序遍历（中间访问根节点）

中序遍历左子树

再访问根节点

再中序遍历右子树

后续遍历（最后访问根节点）

中序访问左子树

中序访问右子树

再访问根节点

（2）已知遍历求二叉树

已知先序和中序或者中序与后续我们可以还原原始二叉树

但是通过先序和后续是无法还原出原始二叉树

换种说法：

只有通过先序和中序或者通过中序和后续我们才可以唯一确定二叉树。

应用

树是数据库中数据组织的一种数据组织形式

操作系统子父进程的关系本身就是一棵树（Ctrl+alt+delete里面有结束进程树（进程及其创建的子进程））

面向对象语言中的类的集成关系

霍夫曼树：一个事物具有n种可能的取值，不同的取值的可能性是不同的。通过什么编程其效率最高。

图（没讲）

模块三: 查找与排序

折半查找

排序：

冒泡

插入

选择

快速排序

归并排序

排序和查找的关系

排序是查找的前提

排序是重点

java中容器和数据结构相关知识

Iterator 接口

Map

哈希表

再次讨论什么是数据结构？

数据结构研究是数据的存储和数据的操作的一门学问。

数据的存储分为两部分：

（1）数据的存储

（2）个体关系的存储

从某个角度而言，数据的存储最核心的就是个体关系的存储

个体的存储可以忽略不计。

再次讨论什么是泛型？

同一种逻辑结构（如线性结构的数组与链表，再如图）

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

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