第一章绪论
一概念
数据结构是一门研究程序设计中计算机操作的对象以及它们之间的关系和运算的一门学科
数据是描述额观事物的数字符以及所有能输入到计算机中被计算机程序加工处理的信息的集合
数据元素数据元素是数据的基本单位(一个数据项或多个数据项(域)数据项是数据的最小单位结点顶点记录
数据对象是性质相同的数据元素的集合
数据结构研究是是数据元素之间抽象化的相互关系和这种关系在计算机中的存贮表示并对每种结构定义各自的运算设计出相应的算法而且经过运算后所得的新结构一般仍然是原来的结构类型
数据类型是指程序设计语言中各变量可取的数据种类
算法是执行特定计算的有穷过程特点
·动态有穷·确定性·输入·输出·可行性
第二章 线性表和数组
概念
一线性表是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哈夫曼码
[] []