数据结构
2021-03-24 23:04:11 34 举报AI智能生成
数据结构
作者其他创作
大纲/内容
数据结构
第五章图
5.1 基本概念
1.定义
由集合V和E组成
V — 顶点集
E — 边集
G=（V， E）
分类
有向图
无向图
2、基本术语
1、顶点
2、完全图
无向
边数=n*(n-1)/2
有向
边数=n*(n-1)
3、权
4、子图
5、邻接
6、关联
7、度
出度OD(Vi)
入度ID(Vi)
8、路径
9、路径长度
10、简单路径
回路
简单回路
11、连通
12、连通图和连通分量
连通图
每对顶点间都连通
连通分量
极大的连通子图
强连通图
强连通分量
13、生成树
14、生成森林
3、基本运算
5.2 存储结构
5.2.1 邻接矩阵
对称矩阵
顶点和度的关系
矩阵
2、带权图(网)
5.2.2 邻接表
示例图
结论
n个顶点、 e条边，链表结点2e
i链结点数=Vi的度
i链结点数=Vi的出度
3.省单元
4.效率高
5.3 遍历
方法
深度优先搜索法
广度优先搜索法
辅助数组visited[n]
5.3.1连通图搜索法
深度优先（DFS）
算法分析
标志向量visited [n]
邻接矩阵或邻接表表示
栈
递归性
时间复杂度
邻接表
O(n+e)
邻接矩阵
O(n2)
广度优先BFS
分析
重复标志向量visited [n];
队列
先进先出
5.4应用
5.4.1生成树
1.生成树
深度
广度
2.最小生成
n点，n-1边
带权
边的权总和最小
构造算法
Prim法
邻接矩阵图
算法图
Kruskal法
最短路径（dijkstra算法）
5.4.2拓扑排序
例图
定义
AOV网络
无回路
第六章查找
6.1基本概念
查找表
关键字
主关键字
查找
根据给定的某个k值，在查找表寻找一个其键值等于k的数据元素。
静态查找表
是引用型运算
动态查找表
是加工型运算
子主题
6.2静态查找表的实现
6.2.1顺序表的查找
算法
过程
从表中最后一个记录开始顺序进行查找，若当前记录的关键字=给定值，则查找成功
6.2.2有序表的查找
二分查找算法
log2n +1
6.2.3索引顺序表的查找
4.三个算法对比
6.3动态查找表（二叉排序树）
什么是二叉排序树
性质
中序遍历一棵二叉排序树所得的结点访问序列是键值的递增序列
查找算法
二叉排序树的插入和生成★
查找分析
平均查找长度是介于O(n)和O(log2n)之间的，其查找效率与树的形态有关
6.4散列表（哈希表）
1、基本概念
散列函数（哈希函数）
散列地址——由散列函数决定数据元素的存储位置
散列查找
冲突
k1≠ k2 但 H（k1） =H（k2）的现象称为冲突
2、常用散列法
1、数字分析法
2、除留余数法
函数算法：H(key)= key mod p （p≤n ）
方法关键——如何取p ？
3、平方取中法
4、基数转换法
3、散列表的实现
链地址法
线性探测法
思想： 计算出的散列地址已被占用，则按顺序找“下一个” 空位
★要点
二次探测法
多重散列法
公共溢出区法
散列法的优缺点
优点：直接由关键字通过哈希函数计算出哈希地址，查找效率高
缺点：常发生冲突，影响查找效率
第七章排序
7.1 概述
数据排序
稳定排序
不稳定排序
排序类型
内部排序： 全部数据存于内存
插入排序
交换排序
选择排序
归并排序
外部排序:需要对外存进行访问的排序过程
7.2 插入排序
1.过程
7.3 交换排序
7.3.1 冒泡排序
1.基本思想
7.3.2 快速排序
7.4 选择排序
7.4.1 直接选择排序
7.4.2 堆排序
7.5 归并排序
第一章 概论
1.1引言
1.数据结构的概念
数据结构(Data structure）是指一组存在特定关系的数据的组织方式和它们在计算机内的存储方式，以及定义在该组数据上的一组操作
计算机解决问题的步骤
建立数学模型
设计算法
编程实现算法
数据结构主要研究
1）数据（计算机加工对象）的逻辑结构
2）实现各种基本操作的算法
学习数据结构的目的：
掌握常用的数据结构及其应用
学会合理地组织数据， 有效地表示数据和处理数据
掌握算法设计技术和分析技术。
掌握使用计算机解决问题的方法和技能，提高程序设计水平
1.2 基本概念和术语
基本术语
数据（Data)：
被计算机处理的符号集合
数据元素（Data Element）：
是数据集合中的基本单位
数据项（Data Item）：
数据元素分为若干个数据项， 具有意义的最小单位。
逻辑结构（Logical Structure）：
指数据元素之间的结构关系
物理结构（Physical Structure）也成为存储结构：
指数据结构在机内的表示，数据的逻辑结构在计算机中的实现
2.数据的逻辑结构
1. 集合
数据元素同“属于一个集合”
2. 线性结构
除起始节点和终端结点d1、 dn外，每个节点有一个前驱和一个后继
3. 树状结构
4. 图状结构
特别注意
逻辑结构与数据元素本身形式、内容无关
逻辑结构与数据元素的相对位置无关
逻辑结构与所含结点个数无关
3.数据的存储结构
存储
数据元素的存储
逻辑关系的存储
存储结构的主要部分
存储结点（每个存储结点存放一个数据元素）
数据元素之间关联方式的表示
4种存储结构
顺序存储结构
借助数据元素的相对存储位置来表示数据的逻辑结构
顺序的方法：将元素存储到一片连续的存储区
特点
1.预先分配好长度，需要预估存储数据需要的存储空间
2.插入和删除需要移动其他元素
3.存取快捷，是随机存取结构
链式存储结构
借助数据元素地址的指针表示数据的逻辑结构
存储单元分为：数据项和指针项
动态分配，不需要预先确定内存分配；
插入和删除不需要移动其他元素
非随机存取结构
索引存储方式
借助索引表中的索引指示各存储节点的存储位置
散列存储方式
用散列函数指示各节点的存储位置
逻辑结构与存储结构的关系
逻辑结构
数据结构定义中的关系，指数据间的逻辑关系，故数据结构也称逻辑结构
存储结构
数据结构在计算机中的表示，称物理结构或存储结构
4.运算
运算就是指在某种逻辑结构上施加的操作，即对逻辑结构的加工
加工型运算
其操作改变原逻辑结构的如：结点个数，结点内容等
引用型运算
其操作不改变原逻辑结构的值
1.3算法及描述
算法规定了求解给定类型问题所需的所有“处理步骤”及执行顺序，在有限时间内被机械的求解。
算法是对特定问题求解步骤的一种描述
描述
程序
介于自然语言和程序设计语言的伪代码
非形式算法（自然语言）
框图(N-S图)
算法特性
有穷性
一个算法总是在执行有穷步后结束。
确定性
算法的每一步都必须是明确地定义的
可行性
算法中的每一步都是可以通过已经实现 的操作来完成的
输入
输出
一个算法有一个或者多个输出，它们是 与输入有特定关系的量。
1.4算法分析
1.时间复杂度
算法运行时需要的总步数
如何确定算法的计算量
默认以赋值语句-->标准操作
执行多少次标准操作-->次数-->算法的计算量。
所有输入下的计算量的最大值-->算法的最坏情况时间复杂度
加权平均值-->平均情况时间复杂度
时间复杂度按数量级
2.空间复杂度
算法执行时所占用的存储空间-->一般只分析辅助变量所占用的空间
空间构成
程序代码所占用的空间；
输入数据所占用的空间；
辅助变量所占用的空间；
算法的设计原則
正确性
对于合法的输入产生符合要求的输出；
易读性
算法应该易读、便于交流， 这也是保证算法正确性 的前提；
健壮性
当输入非法时， 算法还能做出适当的反应而不会崩溃
时空性
时间复杂度和空间复杂度
目的是提高算法效率
1.5本书的组织结构
第二章线性表
2.1概念
是线性结构，由 n(n≥0)个数据元素组成的有穷序列，数据元素又称结点
2.基本特征
一对一的关系，起始结点没前驱，终端结点没有后继，一前一后
3.基本运算
1.初始化
2.求表长
3.读表元素
4.定位
5.插入
6.删除
区分引用型和加工型操作
2.2线性表的顺序存储
2.2.1类型定义
表中的结点在计算机内存连续的存储单元，邻接关系决定存储位置，逻辑相邻=存储相邻
1.逻辑结构与存储结构一致
2.可以随机读取
2.2.2线性表的基本运算的实现
优点
无需为表示结点间的逻辑关系而增加额外存储空间
可以方便地随机存取表中的任一结点
缺点
插入和删除运算不方便
要求占用连续的空间，存储分配只能预先进行
2.2.3顺序表实现算法的分析
分析数据元素的比较和移动的次数
插入算法
最坏时间复杂度O(n)
元素比较和移动的次数为 n-i+1 次
平均移动次数约为 n/2
删除算法
最坏情况下元素移动次数为 n-1
一般比较和移动次数是n-i次
平均移动次数约为（n-1）/2
时间复杂度为 O(n)
定位算法
求表长和读表元素算法的时间复杂度为 O(1)
2.3线性表的链式存储
2.3.1单链表的类型定义
1、结点结构
数据域
指针域或链域
任意存储
首结点
head头指针
2.3.2实现
产生新节点-->动态分配内存函数malloc函数（数据类型*） malloc（sizeof（数据类型））如： int *p;p=（int *） malloc（sizeof（int））
p=malloc(sizeof (Node) );p->data=x; //生成新结点
p->next=q->next; //新结点链域指向*q的后继结点
q->next=p; //修改*q的链域
p = q->next;
q->next = p->next;
free(p);
2.4其他运算在单链表上的实现
2.4.1建表
2.4.2删除重复节点
2.5其他链表
2.5.1循环链表
终端结点的next指向头结点
rear指针指向尾结点
2.5.2双向循环链表
在链表中设置两个指针域，一个指向后继结点一个指向前驱结点
插入
删除
2.6顺序实现与链表实现的比较
优缺点比较
时间性能的比较
第三章栈、队列和数组
3.1栈
3.1.1栈的基本概念
栈是只能在表的一端（表尾）进行插入和删除的线性表
特点--后进先出
基本操作
（1）初始化栈：InitStack(S);
（2）判栈空：EmptyStack (S);
（4）出栈：Pop (S);
（5）取栈顶： GetTop(S);
用途
暂时保存有待处理的数据
3.1.2栈的顺序实现
常用名词
顺序栈—— 即栈的顺序实现
栈容量——栈中可存放的最大元素个数
栈顶指针
栈空
栈满
下溢——当栈空时，再要求作出栈运算，则称“下溢”；
上溢——当栈满时，再要求作进栈运算，则称“上溢”
顺序栈的类型定义
顺序栈的运算
3.1.3栈的链接实现
1、链栈的定义
栈的链式存储结构称为链栈，它是运算受限的单链表，插入和删除操作仅限制在表头位置上进行。栈顶指针就是链表的头指针
3.1.4栈的简单应用和递归
(1)递归的定义
函数在完成之前又调用自身，则称之为递归函数
(2)递归的一般形式
3.2队列
3.2.1队列的基本概念
只允许在表的一端进行插入，而在另一端进行删除的线性表
特点：先进先出（FIFO）
用途——常用于暂时保存有待处理的数据
队列初始化 InitQueue(Q)
判队列空 EmptyQueue(Q)
出队列 OutQueue(Q)
取队列首元素GetHead(Q)
3.2.2队列的顺序实现—循环队列
队列容量
队头指针front
队尾指针 rear
初始： front=rear=0
进队： rear增1，元素插入尾指针所指位置
出队： front增1，取头指针所指位置元素
假溢出
1、顺序队列
2、循环队列
基本运算
3.2.3队列的链式实现
类型
3.2.4队列应用
3.3数组
3.3.1数组的逻辑结构和基本运算
读
写
3.3.2数组的存储结构
2. 寻址公式
3.3.3矩阵的压缩存储
特殊矩阵
1、对称矩阵
元素总数
∑(i)=n(n+1)/2
下标变换公式
2、三角矩阵
上三角矩阵
下三角矩阵
稀疏矩阵
三元组表结构：
第四章树和二叉树
4.1树的基本概念
4.1.1树的概念
递归是树的固有特性
4.1.2树的相关术语
结点
度
叶子（终端结点）
非终端结点
孩子（子结点）
双亲（父结点）
祖先
子孙
兄弟
结点的层次
堂兄弟
树的深度（高度）
有序树
无序树
森林
树的基本运算
求根Root(T)
遍历TraverseTree(T)
4.2二叉树
4.2.1二叉树的基本概念
由一个根及两棵互不相交的左子树和右子树组成
5种基本形态
初始化Initiate(BT)
建二叉树Create(BT)
先序遍历PreOrder(BT)
中序遍历InOrder(BT)
后序遍历PostOrder(BT)
层次遍历LevelOrder(BT)
4.2.2二叉树的性质
1.在第i(i>=1)层上至多有2i-1个结点
2.深度为k(k>=1)至多有2k-1个结点
满二叉树——深度为k(k>=1)且有2k-1个结点
3.叶结点数n0=度为2的结点数n2+1
完全二叉树
4.具有n个结点的完全二叉树的深度为⌊log2n⌋+1
性质5
4.3二叉树的存储结构
4.3.1二叉树的顺序存储结构
用于完全二叉树
节省内存
结点位置确定方便
用于一般二叉树
浪费空间
4.3.2二叉树的链式存储结构
4.4二叉树的遍历
4.4.1二叉树遍历的递归实现
1、先序遍历（递归算法）
2、中序遍历运算（递归算法）
3、后序遍历运算（递归算法）
4.4.2二叉树的层次遍历
4.4.3二叉树遍历的非递归实现
4.5树和森林
4.5.1树的存储结构
一、 双亲表示法
连续空间存储树的结点，即一维数组
结点构成：数据域和双亲域
类型定义
二、 孩子链表表示法
双亲孩子表示法
三、 孩子兄弟链表表示法
孩子兄弟链表的结构形式与二叉链表完全相同， 但结点中指针的含义不同
4.5.2树、森林与二叉树的关系
1、一般树 --> 二叉树
⑴ 各兄弟之间加连线；
⑵ 对任一结点，除最左孩子外，抹掉该结点与其余孩子的各枝；
⑶ 以根为轴心，将连线顺时针转45°
2、森林 --> 二叉树
（1）将每棵树转换成相应的二叉树
（2）将（1）中得到的各棵二叉树的根结点看做是兄弟连接起来
3、二叉树 --> 一般树
⑴ 从根结点起；
⑵ 该结点左孩和左孩右枝上的结点依次作为该结点孩子；
⑶ 重复⑴ 。
4.5.3树和森林的遍历
一、树的遍历
先序遍历
4.6判定树和哈夫曼树
4.6.1分类与判定树
4.6.2哈夫曼树和哈夫曼算法
4.6.3哈夫曼编码
0 条评论
回复 删除
下一页
