第一章绪论
一概念
数据结构是一门研究程序设计中计算机操作的对象以及它们之间的关系和运算的一门学科
数据是描述额观事物的数字符以及所有能输入到计算机中被计算机程序加工处理的信息的集合
数据元素数据元素是数据的基本单位(一个数据项或多个数据项(域)数据项是数据的最小单位结点顶点记录
数据对象是性质相同的数据元素的集合
数据结构研究是是数据元素之间抽象化的相互关系和这种关系在计算机中的存贮表示并对每种结构定义各自的运算设计出相应的算法而且经过运算后所得的新结构一般仍然是原来的结构类型
数据类型是指程序设计语言中各变量可取的数据种类
算法是执行特定计算的有穷过程特点
·动态有穷·确定性·输入·输出·可行性
第二章 线性表和数组
概念
一线性表是N个元素构成的有限序列
顺序存贮结构地址计算插入删除
链式存贮结构单链表查找插入删除
循环链表
双向链表
二数组
以行为主;
以列为主;计算地址
三栈是一种特殊的线性表这种表只能在固定的一端进行插入与删除运算
队列是另一种特殊的线性表删除运算限定在表的一端进行而插入运算在另一端进行
第三章串
概念:是由N个字符组成的有限序列
存贮结构
顺序表示法
紧缩格式 非紧缩格式 以单字节为单位的存贮方式
链式表示法
串名的存贮映象
第四章树
一概念
树是一个或多个结点的有穷集合T且满足以下条件
有且仅有一个指定的称作树根的结点;
除根以外的其余结点被分成m个不相交的集合这些集合的每一个又都是树并且称为根的子树
结点的度结点N的子树数称为结点的度
树的度树T中各结点的度的最大值称的树T的度
叶子树中度为的结点称为叶子(终端结点)
分枝结点树中度不为的结点称为分枝结点(非终端结点)
双亲和孩子若树中结点P的一棵子树的根是结点C则我们称P是C的双亲或父母反之称C是P的孩子
结点的层数树的层数为其余任一结点的层数等于它的双亲的层数加
树的深度树中各结点的层数的最大值称为T的深度(高度)
兄弟和堂兄弟同一双亲的孩子之间互称为兄弟其双亲在同一层的结点互为堂兄弟
祖先和子孙一个点的祖先是指从树的根到该结点所经分枝上的所有结点一个结点的子树的所有结点都称为该结点的子孙
有序树和无序树如果树中结点各棵子树规定从左至右是有次序的则称树为有序树否则为无序树
森林N棵互不相交的树的集合称为森林
二树的存贮表示
双亲数组表示记录型一维数组dataparent
孩子链表表示法
·多重链表表示法: datadegreelinklink…
·单链表表示法:datalikn
左孩子右兄弟链表示法lchilddatarsibling
三二叉树
概念是有限个结点的集合它或者为空集或者是由一个根结点以及两棵互不相交的且分别称为根的左子树和右子树的二叉树组成五种形态空根左右左右 性质
·位于二叉树第I层上的结点最多为I;(I)=
·深度为K的二叉树的结点总数最多为K(K)=
·N=N+
满二叉树一棵深度为K的具有K个结点的二叉树
完全二叉树在一棵二叉树中若所有结点的度为或为的二叉树
顺序二叉树如果深度为K的具有N个结点的二叉树它的每一个结点都与深度为K的满二叉树中顺序编号是到N的结点相对应的二叉树
三二叉树的存贮表示
顺序存贮
链表表示lchilddatarchlid
遍历
·前序根—左—右
·中序左—根—右
·后序左—右—根
四线索二叉树
五树的二叉树表示森林与二叉树的转换
六路径长度树中一个结点到另一个结点之关的路径由这两个结点之间的分枝所构成路径上的分枝数目称为它的路径长度
哈夫曼树WPL哈夫曼码
第五章图
概念一个图G由两个集合V和E组成V是有限的非空顶点集E是用顶点对表示的边集
无向图有向图;
邻接关联邻接到(于)关联于孤立顶点
顶点的度图G中关联于顶点V的边的数目称为V的度
所有顶点的度等于边的两倍
子图
完全图每对顶点之间都有一条边相连的图在有向图中每对顶点之间都有两条有向边相互关联的图
在无向完全图中边的总数为Cn=n(n)/
在有向完全图中边的总数为Pn=n(n)
路径由边组成
回路
连通图对于无向图如果图中任何两顶点都是可达的则称此图为连能图
对于有向图如果图中任何两个顶点都是相互可达的则此有向图是强连通的如果图中任何两顶点至少有一个顶点另一个顶点可达则称此有向图是单向连通的
强连通分量有向图的最大强连通子图称为它的强连通分量 树图其本质特征是连通性和无圈性把不含圈的无向连通图称为树图
网络是每条边上带有数量指标的连通图
邻接矩阵邻接表
第六章 查找
查找就是确定一个已给的数据是否出现在某个数据表中
域(字段)组成记录的每个数据项
关键字通常记录中总存在某个或某组数据项它们的值能唯一标识一个记录这个(组)数据项称为关键字
方法顺序
二分
线性插值
分区
二叉排序树如果将记录的键码按二叉树的结构来组织并且假定树中任意非叶子结点的键码大于其左子树所有结点的键码(若左子树存在的话)而小于其右子树所有结点的键码(如右子树存在的话)这样的二叉树叫二叉排序树(二叉查找树) 哈 希查找
哈希函数能把关键字映射成记录存贮地址的函数
哈希表假定数组HT[··m]为存贮记录的地址空间哈希函数H以每个记录的关键字值K作为输入产生一个落在[··m]内的整数H(K)并以它作为K所标识的记录在表HT中的地址或索引号这样产生的记录表H(K)叫做 ··]
构造哈希函数的方法
直接定址法
除留余数法
平方取中法
折叠法与移位法
数字分析法
沖突处理
开放定址法 线性探测法 伪随机探测法
链地址法
第七章排序
内部排序
外部排序
内部冒泡 选择 插入 归并 堆排序 快速排序 基数
堆每个非终端结点的关键字大于等于它的孩子结点的关键字
第八章文件
基本概念
