郝斌老师数据结构大纲word版.docx
《郝斌老师数据结构大纲word版.docx》由会员分享，可在线阅读，更多相关《郝斌老师数据结构大纲word版.docx（14页珍藏版）》请在冰点文库上搜索。
郝斌老师数据结构大纲word版
教材：
《数据结构》严蔚敏吴伟民清华大学出版社
《数据结构算法实现及解析》高一凡西安电子科技大学出版社
第一部分数据结构概述
一、定义（研究是数据结构的存储和数据的操作的）
如何把现实中大量而复杂的问题以特定的数据类型和特定的存储结构保存到主存储器（内存）中，以及在此基础上为实现某个功能（比如查找某个元素，删除某个元素，对所有元素进行排序）而执行的相应操作，这个相应的操作也叫做算法。
数据结构=个体的存储（从某个角度而言，可忽略）+个体与个体之间关系的存储（核心）
算法=对存储数据的操作
二、算法
解题的方法和步骤
衡量算法的标准
1.时间复杂度
大概程序要执行的次数，而非执行的时间
2.空间复杂度
算法执行过程中大概所占用的最大内存
3.难易程度（即可读性）
4.健壮性
三、数据结构的地位
数据结构是软件中最核心的内容
程序=数据的存储+数据的操作+可以被计算机执行的语言
第二部分预备知识
一、指针
指针的重要性：
指针是C语言的灵魂
定义
地址：
内存单元的编号
从零开始的非负整数
范围：
0--FFFFFFFF（即0--4G-1）
指针：
指针就是地址，地址就是指针
指针变量是存放内存单元地址的变量
指针的本质是一个操作受限的非负整数（只能进行减运算）
分类：
1.基本类型的指针
2.指针和一维数组的关系
二、结构体
为什么会出现结构体
为了表示一些复杂的数据，而普通的基本类型变量无法满足要求
什么叫结构体
结构体是用户根据实际需要自己定义的数据类型
如何使用结构体
两种方式：
structStudentst={1000,"zhangsan",20}
structStudent*pst=&st;
1.st.sid
2.pst->sid
pst所指向的结构体变量中的sid这个成员
注意事项
结构体变量不能加减乘除，但可以相互赋值
普通结构体变量和结构体指针变量作为函数传参问题
三、动态内存的分配和释放
假设动态构造一个int型的一位数组
intlen；
int*pArr=（int*）malloc（sizeof（int）*len）;
①本语句分配了两块内存，一块内存是动态分配的，总共len个字节；另一块是静态分配的，是pArr变量本身所占的内存，总共4个字节。
②malloc只有一个int型的形参，表示要求系统分配的字节数
③malloc函数的功能是请求系统分配len个字节的内存空间，如果分配成功，则返回第一个字节的地址，如果分配不成功，则返回NULL
④malloc函数能且只能返回第一个字节的地址，所以我们需要把这个无任何实际意义的第一个字节的地址（俗称干地址）转化为一个有实际意义的地址，因此，malloc函数前面必须加强制类型转换（数据类型*），表示把这个无实际意义的第一个字节的地址转化为相应类型的地址。
⑤free（*pArr）
表示把pArr所指向的内存给释放掉
pArr本身的内存是静态的，不能有程序员手动释放，只能在pArr变量所在的函数运行终止时有系统自动释放
⑥跨函数使用内存
静态内存不可以跨函数使用：
静态内存在函数执行期间可以被其它函数使用
静态内存在函数执行完毕之后就不能在被其它函数使用
动态内存可以跨函数使用
动态内存在函数执行完毕之后仍然可以被其它函数使用
第三部分模块一：
线性结构[把所有的结点用一条直线穿起来]
一、连续存储[数组]
1.什么叫做数组
元素类型相同，大小相等
2.数组的优缺点（相对于链表）
优点：
存取速度快
缺点：
实现必须知道数组的长度
需要大块连续的内存块
插入和删除元素很慢
空间通常是有限制的
二、离散存储[链表]
1.定义
N个结点离散分配
彼此通过指针相连
每个结点只有一个前驱结点，每个结点只有一个后续结点
首结点没有前驱结点，尾结点没有后续结点
专业术语：
首结点：
第一个存放有效数据的结点
尾结点：
最有一个存放有效数据的结点
头结点：
头结点的数据类型和首结点的类型是一样的
首结点之前的结点
头结点并不存放有效数据
加头结点的目的是为了方便对链表的操作
头指针：
指向头结点的指针变量
尾指针：
指向尾结点的指针变量
确定一个链表需要几个参数：
（如果希望通过一个函数来对链表进行处理，我们至少需要接受链表的那些参数）
一个参数，即头指针，因为我们通过头指针可以推算出链表的其它所有的信息
2.分类
单链表
双链表：
每一个结点有两个指针域
循环链表：
能通过任何一个结点找到其它所有的结点
非循环链表
3.算法
遍历/查找/清空/销毁/求长度/排序/删除结点/插入结点
插入结点：
（伪算法）
①r=p->pNext;p->pNext=q;q->pNext=r;
②q->pNext=p->pNext;p->pNext=q;（这两行代码不能倒过来）
删除结点：
（伪算法）
r=p->pNext;p->pNext=p->pNext->pNext;free（r）;
算法：
狭义的算法是与数据的存储方式密切相关
广义的算法是与数据的存储方式无关
泛型：
利用某种技术达到的效果就是：
不同的存储方式，执行的操作是一样的
同一种逻辑结构（包括线性结构和非线性结构，其中非线性结构包括树和图），无论该逻辑结构物理存储（包括数组和链表）是什么样子的，我们都可以对它执行相同的操作
4.链表的优缺点（相对于数组）
优点：
空间没有限制
插入和删除元素很快
缺点：
存取的速度很慢
三、线性结构的两种常见应用之一栈
1.定义：
一种可以实现“先进后出”的存储结构
栈类似于箱子
2.分类
静态栈：
以数组为内核
动态栈：
以链表为内核
3.算法
出栈/入栈
4.应用
函数调用/中断/表达式求值/内存分配/缓冲处理/迷宫
四、线性结构的两种常见应用之一队列
1.定义：
一种可以实现“先进先出”的存储结构
队列类似于排队买票
2.分类
链式队列----用链表实现
静态队列----用数组实现
静态队列通常都必须是循环队列
循环队列的讲解：
①静态队列为什么必须是循环队列
普通队列的参数front和rear只增不减，导致内存浪费
②循环队列需要几个参数来确定
需要两个参数：
front/rear
③循环队列各个参数的含义
两个参数在不同的场合有不同的含义
①队列初始化
front和rear的值都为零
②队列非空
front代表的是队列的第一个元素
rear代表的是队列的最后一个有效元素的下一个元素
③队列空
front和rear的值相等，但不一定是零
④循环队列入队伪算法讲解（在尾部入队）
第一步：
将值存入rear所指向的位置
第二步：
rear=（rear+1）%数组的长度
⑤循环队列出队伪算法讲解（在头部出队）
front=（front+1）%数组的长度
⑥如何判断循环队列为空
如果front与rear的值相等，则该队列一定为空
⑦如何判断循环队列为满
第一种方法：
多增加一个标识参数，即数组的长度
（常用）第二种方法：
少用一个元素，如果front==（rear+1）%数组的长度，则循环队列已满
3.算法
出队/入队
4.应用
所有和时间有关的操作都有队列的影子
五、专题：
递归（使用栈实现的）
1、定义:
一个函数自己直接或间接调用自己
2、函数的调用
当在一个函数的运行期间调用另一个函数时，在运行被调函数之前，系统需要完成三件事：
a、将所有的实际参数、返回地址等信息传递给被调函数保存
b、为被调函数的局部变量（包括形参）分配存储空间
c、将控制转移到被调函数的入口
从被调函数返回主调函数之前，系统也要完成三件事：
a、保存被调函数返回结果
b、释放被调函数所占的存储空间
c、依照被调函数保存的返回地址将控制转移到调用函数
当有多个函数相互调用时，按照“后调用先返回”的原则，上述函数之间的信息传递和控制转移必须借助“栈”来实现，即系统将整个程序运行时所需的数据空间安排在一个栈中，每当调用一个函数时，就在栈顶分配一个存储区，进行压栈操作；每当一个函数退出时，就释放它的存储区，进行出栈操作，当前运行的函数永远都在栈顶位置。
A函数调用A函数与A函数调用B函数在计算机看来是没有任何区别的，只不过用我们日常的思维方式理解比较怪异而已。
3、递归必须满足的三个条件：
a、递归必须得有一个明确的终止条件
b、该函数处理的数据规模必须在递减
c、这个转化必须是可解的
4、循环和递归之间的关系
理论上循环能解决的问题，肯定可以转化为递归解决，但是这个过程是复杂的数学转化过程，递归能解决的问题不一定能转化为循环解决
递归的优缺点：
易于理解
速度慢
存储空间大
循环的优缺点：
不易理解
速度快
存储空间小
5、举例：
1.1+2+3+4+...+100的和
2.求阶乘
①使用for循环实现：
求和求阶乘
#include#include
intmain（void）intmain（void）
{{
longsum=0;longmult=1;
for（inti=1;i<=100;i++）intval;
sum=sum+i;printf（"请输出整数：
"）
printf（"1到100的和是：
%ld",sum）;scanf（"%d",&val）;
return0;for（inti=1;i<=val;i++）
}mult=mult*i;
printf（"%d的阶乘是%ld",val,mult）;
return0;
}
②使用递归实现：
#include#include
longsum（intval）longmult（intval）
{{
if（1==val）if（1==val）
return1;return1;
elseelse
returnval+sum（val-1）;returnval*mult（val-1）;
}}
intman（void）intmain（void）
{{
printf（"1到100的和是：
%ld",sum（100））;printf（"请输出整数：
"）
return0;scanf（"%d",&val）;
}printf（"%d的阶乘是%ld",val,mult（val））;
return0;
}
3.汉诺塔
伪算法：
if（1==n）
直接将盘子从A移动到C
else
{（三步）
第一步：
将A柱子上的前n-1个盘子借助C移动到B
第二步：
将A柱子上的第n个盘子直接移动到C
第三步：
将B柱子上的n-1个盘子借助A移动到C
}
4.走迷宫
6、递归的应用
树和森林就是以递归的方式定义的
树和图的很多算法都是以递归来实现的
很多数学公式就是以递归的方式定义的（例如：
斐波拉契序列）
第四部分模块二：
非线性结构
一、树
1、定义
（专业定义）有且只有一个称为根的结点；有若干个互不相交的子树，这些子树本身也是一棵树
（通俗定义）树是由结点和边（即指针）组成；每一个结点只有一个父结点但可以有多个子结点；但是有一个结点例外，该结点没有父结点，此结点称为根结点
专业术语
结点/父结点（只有一个）/子结点/子孙/堂兄弟
深度:
从根结点到最底层结点的层数（根结点是第一层）
叶子结点：
没有子结点的结点
非终端结点：
实际就是非叶子结点，即有子结点的结点
度：
子结点的个数
2、分类
一般树：
任意一个结点的子结点的个数都不受限制
二叉树：
任意一个结点的子结点的个数最多两个，且子节点的位置不可更改
二叉树的分类：
一般二叉树
满二叉树：
在不增加树的层数的情况下，无法再多添加一个结点的二叉树就是满二叉树
完全二叉树：
如果只是删除满二叉树最底层最右边的连续若干个结点，这样形成的二叉树就是完全二叉树
满二叉树是完全二叉树的特例，完全二叉树包含满二叉树
森林：
n个互不相交的树的集合
3、存储（解决非线性结构用线性结构表示的问题）
二叉树的存储
连续存储[完全二叉树]
一般二叉树要以数组的方式存储，要先转化成完全二叉树，因为如果只存有效节点（无论以哪种规则：
先序，中序，后序），则无法知道这个树的原本样子。
优点：
查找某个结点的父结点和子结点（也包括判断有没有子结点）速度很快
缺点：
耗用内存空间过大
链式存储
一般树的存储
双亲表示法（求父结点方便）
孩子表示法（求子结点方便）
孩子双亲表示法（求父结点和子结点都方便）
二叉树表示法
把一棵普通树转化成二叉树来存储
具体转化方法：
设法保证任意一个结点的左指针域指向它的第一个孩子，右指针域指向它的下一个兄弟
一棵普通树转化为的二叉树一定没有右子树
森林的存储
先把森林转化为二叉树，再存储二叉树
具体方式为：
根节点之间可以当成是兄弟来看待
4、操作
树的遍历
先序遍历[先访问根结点]
先访问根结点，再先序访问左子树，后先序访问右子树
中序遍历[中间访问根结点]
先中序遍历左子树，再访问根节点，后中序访问右子树
后序遍历[最后访问根结点]
先中序遍历左子树，再中序遍历右子树，后访问根结点
已知两种遍历求原始二叉树
通过先序遍历和中序遍历或者中序遍历和后序遍历我们可以还原出原始的二叉树，但是通过先序遍历和后序遍历是无法还原出原始的二叉树的。
换种说法：
只有通过先序遍历和中序遍历或者中序遍历和后序遍历我们才可以唯一的确定一个二叉树的。
5、应用
树是数据库中数据组织的一种重要形式
操作系统子父进程的关系本身就是一棵树
面向对象语言中类的继承关系本身就是一棵树
赫夫曼树
二、图
第五部分模块三：
查找和排序
两者的关系：
排序是查找的前提，排序是重点
折半查找
排序：
（考虑三个问题：
时间、空间、稳定性）
冒泡
插入
选择
快速排序
归并排序
第六部分Java中容器和数据结构相关知识
Iterator接口
Map
哈希表
升级会员 