数据结构.docx
《数据结构.docx》由会员分享，可在线阅读，更多相关《数据结构.docx（18页珍藏版）》请在冰点文库上搜索。
数据结构
衡量算法的标准：
1.时间复杂度
大概程序要执行的次数，而非执行的时间
2空间复杂度
算法执行过程中大概所占用的最大内存
3难易程度
4健壮性
数据结构的地位
数据结构是软件中最核心的课程
指针
地址是内存单元的编号从0开始的非负整数
指针式是地址地址就是指针
指针变量是存放内存单元地址的变量
指针的本质是一个操作受限的非负整数
Int*p//p只能指向整形变量
1基本类型的指针
Int*p=&i;//等价于int*p;p=&i;
2指针和数组关系
Doublex;x占8个字节，一个字节是八位
Double*q；print（“%p\n”,q）;输出q的值即存放某个变量的地址。
结构体
StructStudent
{
Intpid;
Intname;
Intage;
};
StructStudentst={1000,”zhangsan”,20};
St.sid=99;//right
St.name=“lisi”;//error
Strcpy（st.name,”lisi”）;//right
使用结构体
1.structStudent*pst;
pst=&st;
pst->pid=99;//pst->pid等价于（*pst）.sid等价于st.pid
2.st.pid
结构体变量可以相互赋值但是不可以进行算术运算
模块一：
线性结构【把所有的节点用一根直线穿起来】
连续存储【数组】
Inta[10];
Int*pArr=（int*）malloc（sizeof（int）*len）;
1.什么叫数组
元素类型相同，大小相等
2.数组的优缺点
离散存储【链表】
线性结构的两种常见应用之一栈
线性结构的两种常见应用之二队列
TypedefstructStudent
{
Intsid;
Charname[100];
Charsex;
}ST;/等价于structStudentST
TypedefstructStudent
{
Intsid;
Charname[100];
Charsex;
}*PST;//等价于structStudent*PST
TypedefstructStudent
{
Intsid;
Charname[100];
Charsex;
}ST，*PST;
离散存储平【链表】：
定义：
N个节点离散分配
彼此通过指针相连
每个节点只有一个前驱节点，每个节点只有一个后续节点
首节点没有前驱节点，尾节点没有后续节点
专业术语：
首节点：
第一个存放有效数据的节点
尾节点：
最后一个有效存放数据的节点
头结点、：
通常在首节点前加上头结点，没有存放数据，也没有存放有效节点个数。
是用来简便对链表的操作。
头指针：
指向头结点的指针变量，即头结点地址
尾指针：
指向尾节点的指针变量
如果希望通过一个函数来对链表进行处理，我们至少需要接受链表的哪些参数：
只需要一个参数：
头指针。
因为我们通过头指针可以推算出链表的其他所有参数。
分类：
单链表
双链表：
每个节点有两个指针域
循环链表：
能通过任何一个节点找到其他所有节点
非循环链表
算法：
算法是对存储数据的操作
遍历
查找
清空
销毁
求长度
排序
删除节点
插入节点
狭义的算法是与数据的存储方式密切相关的
广义的算法是与数据的存储方式无关
泛型：
利用某种技术达到的效果就是：
不同的存储方式，执行的操作时一样的
链表的优缺点：
数据结构
狭义的来讲：
数据结构是专门研究数据存储的问题
数据的存储包括两个方面：
个体的存储+个体关系的存储
广义来讲：
数据结构既包含数据的存储也包含数据的操作
对存储数据的操作就是算法
算法：
狭义
算法是和数据的存储方式密切相关
广义
算法和数据的存储方式无关
这就是泛型的思想
数据的存储结构有几种
线性
连续存储【数组】
优点
存取速度快
缺点
事先必须知道数组的长度
需要大块连续的内存块
插入删除元素的效率极低
插入删除元素很慢
空间通常有限制
非连续存储【链表】
优点
空间没有限制
插入删除元素很快
缺点
存取速度很慢
线性结构的应用------栈
定义
一种可以实现“先进后出”的存储结构
栈类似于箱子先放进去的后拿出来
分类
静态栈
动态栈
算法
出栈
压栈
应用
函数调用
中断
内存分配
缓冲处理
迷宫
pTop头部
pBattom尾部
线性结构的应用------队列
定义：
一种可以实现“先进先出”的存储结构
分类：
front头部rear尾部
F指向第一个元素r指向最后一个元素的下一个元素
链式队列
----------用链表实现
静态队列
----------用数组实现
静态队列通常都必须是循环队列
1.静态队列为什么必须是循环队列
2.循环队列需要几个参数来确定
两个front和rear
3.循环队列各个参数的含义
1）队列初始化
Front和rear的值都为零
2）队列非空
Front代表队列的第一个元素，
Rear代表队列的最后一个有效元素的下一个元素。
3）队列空
Front和rear的值相等但不一定为零。
4.循环队列入队伪算法讲解
两步完成：
1.将值存入r所代表的位置
2.错误的写法r=r+1;
正确的写法是：
r=（r+1）%数组的长度。
5.循环队列出对伪算法讲解
F=（f+1）%数组的长度
6.如何判断循环队列是否为空
如果front与rear的值相等，则该队列一定为空。
7.如何判断循环队列是否已满
1.If（（r+1）%数组长度==f）
已满
2.多添加一个标识参数
队列算法：
入队
出对
队列的具体应用：
所有和时间有关的操作都与队列有关
专题：
递归
定义：
一个函数自己直接或间接调用自己
递归必须满足三个条件
1.递归必须有一个明确的中止条件
2.该函数所处理的数据规模必须在递减
3.这个转化必须是可解的
递归和循环
递归：
易于理解
速度慢
存储空间大
循环：
不易理解
速度慢
存储空间大
举例：
1.求阶乘
1）阶乘的递归实现
#include
//假定n的值是1或大于1的值
longf（longn）
{
if（1==n）
return1;
else
returnf（n-1）*n;
}
intmain（void）
{
printf（"%d\n",f（100））;
return0;
}
2）阶乘的循环实现
#include
intmain（void）
{
intval;
inti,mult=1;
printf（"请输入一个数字:
"）;
printf（"val="）;
scanf（"%d",&val）;
for（i=1;i<=val;i++）
{
mult=mult*i;
}
printf（"%d",mult）;
return0;
}
1.1+2+3+...+100
#include
longsum（intn）
{
if（1==n）
return1;
else
returnn+sum（n-1）;
}
intmain（void）
{
printf（"%ld\n",sum（100））;
return0;
}
2.汉诺塔
#include
voidhannuota（intn,charA,charB,charC）
{
/*如果是1个盘子
直接将A柱子上的盘子从A移到C
否则
现将A柱子上的n-1个盘子借助C移到B
直接将A柱子上的盘子从A移到C
最后将B柱子上的n-1个盘子借助A移到C
*/
if（1==n）
printf（"将编号为%d的盘子直接从%c柱子移到%c柱子\n",n,A,C）;
else
{
hannuota（n-1,A,C,B）;
printf（"将编号为%d的盘子直接从%c柱子移动到%c柱子\n",n,A,C）;
hannuota（n-1,B,A,C）;
}
}
intmain（void）
{
charch1='A';
charch2='B';
charch3='C';
intn;
printf（"请输入要移动盘子的个数：
"）;
scanf（"%d",&n）;
hannuota（n,'A','B','C'）;
return0;
}
3.走迷宫
递归的应用：
树和森林就是以递归的方式定义的
树和图的很多算法都是以递归来实现的
很多数学公式就是以递归的方式定义的
非线性结构
树
树定义
专业术语：
1.有且只有一个称为根的节点
2.有若干个互不相交的子树，这些子树本身也是一棵树
通俗的定义：
1.树是由节点和边组成
2.每个节点只有一个父节点，但可以有多个子节点
3.有一个节点没有父节点，这个节点称为父节点
专业术语
节点父节点子节点
子孙堂兄弟
深度：
从根节点到最底层节点的层数称为深度
根节点是第一层
叶子节点：
没有子节点的节点
非终端节点：
实际就是非叶子节点
树分类：
一般树：
任意一个子节点的个数都不受限制
二叉树：
任意一个节点的子节点个数最多两个，且子节点的位置不可更改
分类：
一般二叉树
满二叉树
在不增加树的层数的前提下，无法再多添加一个节点的二叉树就是满二叉树。
完全二叉树
如果只是删除了满二叉树最底层最右边的连续若干结点，这样形成的二叉树就是完全二叉树。
森林
N个互不相交的树的集合
树的存储
二叉树的存储
连续存储[完全二叉树]
优点：
查找某个节点的父节点和子节点（也包括判断有没有父节点和子节点）
缺点：
耗用内存空间过大
链式存储
一般树的存储
双亲表示法
求父节点比较方便
孩子表示法
求子节点比较方便
双亲孩子表示法
求父节点和子节点都很方便
二叉树表示法
把一个普通树转化为二叉树来存储
具体转换方法：
左指针域指向它的第一个孩子
右指针域指向它的下一个兄弟
只要能满足此条件，就可以把一个普通树转化为二叉树
一个普通树转化成的二叉树一定没有右子树
森林的存储
先把森林转化为二叉树，再存储二叉树
树操作
二叉树操作
遍历
先序遍历【先访问根节点】
先访问根节点
再先序访问左子树
再先序访问右子树
下图所示二叉树的遍历结果是：
ABDECF
⑴中序序列（inordertraversal）
中序遍历二叉树时，对结点的访问次序为中序序列
【例】中序遍历上图所示的二叉树时，得到的中序序列为：
DBAECF
⑵先序序列（preordertraversal）
先序遍历二叉树时，对结点的访问次序为先序序列
【例】先序遍历上图所示的二叉树时，得到的先序序列为：
ABDCEF
⑶后序序列（postordertraversal）
后序遍历二叉树时，对结点的访问次序为后序序列
【例】后序遍历上图所示的二叉树时，得到的后序序列为：
DBEFCA
⑷层序遍历（leveltraversal）二叉树的操作定义为：
若二叉树为空，则退出，否则，按照树的结构，从根开始自上而下，自左而右访问每一个结点，从而实现对每一个结点的遍历
【例】层序遍历上图所示的二叉树时，得到的层序序列为：
ABCDEF
中序遍历【中间访问根节点】
中序遍历左子树
在访问根节点
再中序遍历右子树
左子树（BDE）还是左边开始（D），然后是（B）,再是右边（E），完后经过（A），接着右子树（CF）还是左边开始（F）,再是中间（C），
即顺序是DBEAFC
后序遍历【最后访问根节点】
中序遍历左子树
中序遍历右子树
再访问根节点
遍历结果：
DEBFCA
已知两种遍历序列求原始二叉树
已知先序和中序或者中序和后序可以推断出原始二叉树
但是知道先序和后序无法推断出原始二叉树
也就是说只有通过先序和中序或中序和后序才可以唯一确定一个二叉树
应用
树是数据库中数据组织一种重要形式
操作系统子父进程的关系本身就是一棵树
面向对象语言中的类的继承关系本身就是一棵树
郝夫曼树
图
再次讨论什么是数据结构
数据结构研究的是数据的存储和数据的操作的一门学科
数据的存储分为两部分：
个体的存储
个体关系的存储
从某个角度而言，数据的存储最核心的就是个体关系的存储，个体的存储可以忽略不计
再次讨论到底什么是泛型
同一种逻辑结构，无论该逻辑结构物理存储是什么样子的
我们可以对它执行相同的操作
升级会员 