数据结构笔记.doc

//2018/5/23
数据结构概述：
预备知识
模块一：线性结构
连续存储[数组]
离散结构[链表]
线性结构的两种常见应用之一 栈（堆栈）
线性结构的两种常见应用之二 队列
专题：递归
1.1+2......+100的和
2.求阶乘
3.汉诺塔
4.走迷宫
模块二：非线性结构
树
图
模块三：查找和排序
折半查找
排序：冒泡 插入 选择 快速排序 归并排序
补录：Java中容器和数据结构相关知识
Iterator接口
Map 哈希表

严蔚敏---高一凡---黄国瑜

//2018/5/24
数据结构概述
定义
我们如何把现实中大量而复杂的问题以特定的数据类型和特定的存储结构保存到主存储器（内存）中，以及在此基础上为实现某个功能（比如查找或删除某个元素，对所有元素进行排序）而执行的相应操作，这个相应操作叫做算法。
特定的数据类型:个体如何保存
特定的存储结构:个体与个体的关系如何保存

数据结构 = 个体的存储 + 个体关系的存储
算法（狭义） = 对存储数据的操作

算法：即解题的方法和步骤
衡量算法的标准
1. 时间复杂度[重要]
大概程序要执行的次数，而非执行的时间
2. 空间复杂度[重要]
算法执行过程中大概所占用的最大内存
3. 难易程度
4. 健壮性

数据结构的地位
数据结构是软件中最核心的课程。
程序 = 数据的存储 + 数据的操作 + 可以被计算机执行的语言

预备知识：
指针
结构体
动态内存的分配和释放

指针：
指针的重要性:
表示一些复杂的数据结构
快速的传送数据
使函数返回一个以上的值
能否直接访问硬件
能够方便的使用数组和字符串
是理解面向对象语言中引用的基础

指针是C语言的灵魂
定义
地址
内存单元的编号
从0开始的非负整数
范围0-FFFFFFFF 【0 到 4G-1】
注：无论一个变量有多大，其地址只用第一个字节的地址表示，均只占四个字节。
指针
指针就是地址 地址就是指针
指针变量就是存放内存单元地址的变量
指针本质上就是一个操作受限的非负整数
分类
1、基本类型指针【略】
基本概念
int i=10;
int *p = &i; //等价于 int *p; p = &i;
详解这两部操作：
1）p存放了i的地址，所以我们说p指向了i
2）p和i是完全不同的两个变量，修改其中的任意一个变量的值，不会影响另一变量的值
3）p指向i，*p就是i变量本身。更形象的说所有出现 *p的地方都可以换成i，所有出现i的地方都可以换成*p
4）int * p，不是定义了*p的参数，而是定义了一个变量p，为int *类型。

总结：
1、如何一个指针变量(假定为p)存放了某个普通变量(假定为i)的地址，那我们就可以说：“p指向了i”， 但p与i是两个不同的变量，修改p的值不影响i的值，修改i的值不影响p的值.
2、*p等价于i 或者说*p可以与i在任何地方互换
3、如果一个指针变量指向了某个普通变量，则*指针变量 就完全等价于该普通变量
注意：
指针变量也是变量，只不过它存放的不能是内存单元的内容，只能存放内存单元的地址
普通变量前不能加*
常量和表达式前不能加&

如何通过被调函数修改主调函数中普通变量的值
Ⅰ 实参为相关变量的地址
Ⅱ 形参为以该变量的类型为类型的指针变量
Ⅲ 在被调函数中通过 *形参变量名 的方式就可以修改主函数相关变量的值
Eg:void f(int * p) //II
{
*p = 100; //III
}
int main(void)
{
int i = 9;
f(&i); //I
printf(“i = %d\n”, i);
}

指针和数组的关系
指针 和 一维数组
数组名
一维数组名是个指针常量，
它存放的是一维数组第一个元素的地址，
它的值不能被改变
一维数组名指向的是数组的第一个元素
下标和指针的关系
a[i] <<==>> *(a+i)
*a+3 = a[0]+3
假设指针变量的名字为p
则p+i的值是p+i*(p所指向的变量所占的字节数)
指针变量的运算
指针变量不能相加，不能相乘，不能相除
如果两指针变量属于同一数组，则可以相减
指针变量可以加减一整数，前提是最终结果不能超过指针允许指向的范围
p+i的值是p + i*(p所指向的变量所占的字节数)
p-i的值是p - i*(p所指向的变量所占的字节数)
p++ <==> p+1
p-- <==> p-1
举例

如何通过被调函数修改主调函数中一维数组的内容【如何界定一维数组】
两个参数
存放数组首元素的指针变量
存放数组元素长度的整型变量
所有的指针变量只占4个子节 用第一个字节的地址表示整个变量的地址

动态内存分配和释放：
[程序在运行过程中可以动态的增加或减少内存分配]
动态构造一维数组
假设动态构造一个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）：动态分配的内存，必须free()释放，系统不会自动释放。
释放p所指向的内存，而不是释放p本身所占用的内存
【重点：动态分配数组内存】
int * pArr = (int *) malloc (sizeof(int) * len);
(最后一个*代表了乘 分配了4 * len个字节)

模块一：线性结构【把所有的结点用一根直线穿起来】
连续存储[数组]
1.什么叫数组
元素类型
离散结构[链表]

线性结构中两种常用应用之一 栈
定义
一种可以实现“先进后出”的存储结构
只能从栈尾（栈顶）进和出。
栈类似于箱子，局部变量都是在栈中存储的。
分类
静态栈【以数组为内核】
动态栈【以链表为内核】
算法
出栈 pTop向下移一个，pBottom不变
压栈（入栈） pTop向上移一个，pBottom不变

应用
函数调用
中断
表达式求值（例如计算器的编写）
内存分配
缓冲处理
//2018/5/20
线性结构中两种常用应用之二 队列
定义： 一种可以实现“先进先出”的存储结构
分类： 变量名：front（头部） 和 rear（尾部）
链式队列---用链表实现
静态队列---用数组实现

注：在队首的位置删除元素，然后队首指针指向下一个元素
在队尾的位置添加元素，然后队尾指针指向下一个元素
【重点】Rear指向的是队列最后一个元素的下一个元素
【重点】Front指向的是队列的第一个元素
队列算法：
入队
出队
队列的具体应用：
所有和时间及有关的操作都有队列的影子。

静态队列：
注：将数组的部分功能给去掉，然后再加入一些功能。
静态队列通常都必须是循环队列。
问题：如果按照普通的数组来存储队列的话。每次删掉一个元素，头部指针都会指向下一个元素，会造成原来元素的位置空间浪费，只能被使用一次而不能重复被使用。只能增不能减。
循环队列的讲解：
1. 静态队列为什么必须是循环队列
问题：如果按照普通的数组来存储队列的话。每次删掉一个元素，头部指针都会指向下一个元素，会造成原来元素的位置空间浪费，只能被使用一次而不能重复被使用。只能增不能减。
解决方法：当front和rear移动到顶部（队尾）时，下一次移动时可以让它再移动到底部（队首），首尾相连，这实际就是循环队列。

2. 循环队列需要几个参数来确定
需要两个参数来确定
front
rear
3. 循环队列各个参数的含义
这两个参数在不同场合有不同的含义
建议初学者先记住，然后慢慢体会
1） 队列初始化
front和rear的值都是0
2） 队列非空
Front代表的是队列的第一个元素
Rear代表的是队列的最后一个有效元素的下一个元素
3） 队列空
front和rear的值相等，但不一定为0
4. 循环队列入队伪算法讲解
两步完成，详解见图

5. 循环队列出队伪算法讲解

6. 如何判断循环队列是否为空
如果front和rear的值相等，
则该队列就一定为空。
7. 如何判断循环队列是否为满

预备知识：
front的值可能比rear大，
也完全有可能比rear小，
当然也可能相等。
两种方式：
1.多增加一个标志位参数
2.少用一个元素【通常使用第二种元素】
队列中有n个元素，只要放到n-1个元素，即认为队列已满。

//2018/5/21
专题：递归
定义：一个函数自己直接或间接调用自己

递归满足的三个条件：
1. 递归必须得有一个明确的终止条件
2. 递归的值可以是递增的，但所处理的数据规模必须在递减
（n->n-1->n-2……）
3. 这个转化必须是可解的

循环和递归
所有的循环都可以用递归实现，
但所有的递归不一定都可以用循环实现。
递归： 循环：
易于理解 不易理解
速度慢 速度快
存储空间大（步骤麻烦） 存储空间小

n -> n-1 -> n-2 -> ……-> 1
举例：
1. 求阶乘
2. 1+2……+100的和
3. 汉诺塔
4. 走迷宫

递归的应用：
树和森林就是以递归的方式定义的
树和图的很多算法就是以递归来实现的
很多数学公式就是以递归的方式定义的(例如：斐波拉切数列)

线性结构总复习：
逻辑结构
线性 {数组 链表}
栈和队列是一种特殊的线性结构，算线性结构的应用
非线性 { 树 图}
物理结构
//2018/5/22
模块二：非线性结构
树
定义：
专业定义：
1. 有且只有一个称为根的节点
2. 有若干个互补相交的子树，这些子树本身也是一棵树
通俗定义：
1. 树是由节点和边组成
2. 每个节点只有一个父节点但可以有多个子节点
3. 但有一个节点例外，该节点没有父节点，此节点成为根节点。
专业术语
节点 父节点 子节点 子孙 堂兄弟
深度：从根节点到最底层节点的层数称之为深度（根节点是第一层）
叶子节点：没有子节点的节点。
非终端节点：实际就是非叶子节点。
度：子节点的个数成为度。

分类：
一般树：任意一个节点的子节点的个数都不受限制

二叉树：任意一个节点的子节点的个数最多两个，且子节点的位置不可更改。
分类：
一般二叉树
满二叉树（完全二叉树的特例）
在不增加树的层数的前提下，无法再多添加一个节点的二叉树就是满二叉树
完全二叉树（用数组存储树时，必须是完全二叉树）
如果只是删除了满二叉树最底层最后边的连续若干个节点，这样形成的二叉树就是完全二叉树。
优点：1.根据节点编号可以知道在第几层
2.可以知道父节点和子节点
森林：n个互不相交的树的集合

树的存储：
二叉树的存储
连续存储[将二叉树补充为完全二叉树]
以数组的形式存储时，如果根据只保存有效节点的形式，无法推出全树的样子。
优点：查找某个节点的父节点和子节点（也包括判断有没有父节点和子节点）速度很快。
缺点：耗用空间内存过大
链式存储
一般树的存储
双亲表示法（求父节点方便）
把每一个节点编号，然后在每一个节点后标记出其父节点的编号
孩子表示法（求子节点方便）
把每一个子节点都写在每一个节点之后。
双亲孩子表示法（求父节点和子节点都方便）
把每一个节点编号，然后在每一个节点后标记出其父节点的编号，再把每一个子节点写在之后。
二叉树表示法
把一个普通树转化为二叉树来存储。
具体转换方法：
设法保证任意一个节点的
左指针域指向它的第一个孩子
右指针域指向它下一个兄弟
只要满足此条件，就可以把一个普通树转化为二叉树
一个普通树转化成的二叉树一定没有右子树

森林的存储
先把森林转化为二叉树，再将二叉树存储
具体转换方法：
1.设法保证其他树的根节点当成第一颗树根节点的兄弟
2.设法保证其他任意一个节点的
左指针域指向它的第一个孩子
右指针域指向它下一个兄弟
只要满足此条件，就可以把一片森林转化为二叉树

操作：
遍历
先序遍历[先访问根节点][中左右]
先访问根节点
再先序访问左子树
再先序访问右子树

中序遍历[中间访问根节点][左中右]
中序遍历左子树
再访问根节点
再中序遍历右子树

后序遍历[最后访问根节点][左右中]
先后序遍历左子树
再后序遍历右子树
再访问根节点

只知道一颗二叉树的一种遍历方式是无法还原二叉树的原貌的。
已知两种遍历序列求原始二叉树
先中（可以） 中后（可以） 先后（不可以） 必须有一个中序

已知先序和中序求后序
例1：
先序：ABCDEFGH 中序：BDCEAFHG 求后序
讲解：先序中第一个出现的一定是根节点，即A；所以中序中根节点A左边的BDCE是左子树，右边的FHG是右子树；然后在先序序列中看左子树BDCE中哪个先出现，先出现的为根节点，即B；因为中序中DCE在B的右侧，所以DCE是B的右子树，哪个在先序中先出现为根节点，即C；中序中，C左侧是D，右侧是E，即为C的左右子节点；A右子树方法类同。
方法总结：由先序找到根节点（先出现为根节点），
由中序找到根节点的左右子树（左侧左子树，右侧右子树）。
后序：DECBHGFA

例2:
先序: ABDGHCEFI
中序: GDHBAECIF
求后序: GHDBEIFCA

已知中序和后序求先序
例：中序：BDCEAFHG 后序：DECBHGFA 求先序：
讲解：后序中第一个出现的一定是根节点，即A；所以中序中根节点A左边的BDCE是左子树，右边的FHG是右子树；然后在后序序列中看左子树BDCE中哪个后出现，后出现的为根节点，即B；因为中序中DCE在B的右侧，所以DCE是B的右子树，哪个在后序中后出现为根节点，即C；中序中，C左侧是D，右侧是E，即为C的左右子节点；A右子树方法类同。
方法总结：由后序找到根节点（后出现为根节点），
由中序找到根节点的左右子树（左侧左子树，右侧右子树）。

先序: ABCDEFGH
//2018/5/23
应用：
树是数据库中数据组织一种重要形式。
操作系统子父进程的关系本身就是一棵树。
面对对象语言中类的继承关系本身就是一棵树。
赫夫曼树。