数据结构和软件工程简介.doc

数据结构和软件工程简介 数据结构的基本概念 数据是描述客观事物并能为计算机加工处理的符号的集合。数据元素是数据的基本单位，即数据集合中的个体。有些情况下也把数据元素称为结点、记录等。一个数据元素可由一个或多个数据项组成。数据项是有独立含义的数据最小单位，有时也把数据项称为域、字段等。 数据结构（Data Structure）是指数据元素的组织形式和相互关系。数据结构一般包括以下三方面的内容。 1、数据的逻辑结构 数据的逻辑结构从逻辑上抽象地反映数据元素间的结构关系，它与数据在计算机中的存储表示方式无关。因此，数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。 数据的逻辑结构有两大类： 线性结构——线性结构的逻辑特征是：有且仅有一个始端结点和一个终端结点，并且除两个端点结点外的所有结点都有且仅有一个前趋结点和一个后继结点。线性表、堆栈、队列、数组、串等都是线性结构。 非线性结构——非线性结构的逻辑特征是：一个结点可以有多个前趋结点和后继结点。如树形结构、图等 2、数据的物理结构 数据的物理结构是逻辑结构在计算机存储器里的映像，也称为存储结构。 数据的存储结构可用以下四种基本存储方法体现： 顺序存储方法——把逻辑上相邻的结点存储在物理位置上相邻的存储单元里，结点之间的逻辑关系由存储单元的邻接关系来体现。由此得到的存储结构称为顺序存储结构。 链式存储方法——不要求逻辑上相邻的结点在物理位置上也相邻，结点之间的逻辑关系是由附加的指针字段表示的。由此得到的存储结构称为链式存储结构。 索引存储方法——在存储结点信息的同时，还建立附加的索引表，索引表中的每一项称为索引项。索引项由关键字和地址组成，关键字是能惟一标识一个结点的那些数据项，而地址一般是指示结点所在存储位置的记录号。 散列存储方法——根据结点的关键字直接计算出该结点的存储地址。 用不同的存储方法对同一种逻辑结构进行存储映像，可以得到不同的存储结构。四种基本的存储方法也可以组合起来对数据逻辑结构进行存储映像。 3、数据的运算 数据的运算是指对数据施加的操作。它是定义在数据的逻辑结构上的，但运算的具体实现要在物理结构上进行。数据的每种逻辑结构都有一个运算的集合，常用的运算有检索、插入、删除、更新、排序等 线性表： 1．顺序表 当线性表采用顺序存储结构时称之为顺序表。在顺序表中，数据元素按逻辑次序依次放在一组地址连续的存储单元里。由于逻辑上相邻的元素存放在内存的相邻单元里，所以顺序表的逻辑关系蕴含在存储单元的邻接关系中。在高级语言中，可以直接用数组实现。 2. 单链表 采用链式存储结构的链表是用一组任意的存储单元来存放线性表的数据元素，这组存储单元既可以是连续的，也可以是不连续的，甚至可以是零星分布在内存中的任何位置上，从而可以大大提高存储器的使用效率。 在线性链表中，每个元素结点除存储自身的信息外，还要用指针域额外存储一个指向其直接后继的信息（即后继的存储位置：地址）。 3. 栈与队列 栈与队列是两种特殊的线性表。即它们的逻辑结构与线性表相同，只是其插入、删除运算仅限制在线性表的一端或两端进行。 （1）栈 栈是仅限于在表的一端进行插入和删除运算的线性表，通常称插入、删除的这一端为栈顶，另一端称为栈底。当表中没有元素时称为空栈。 栈的特点是：后进先出（LIFO——Last In，First Out）。 如：入栈顺序为 1，2，3，4，5，出栈为 5，4，3，2，1。 （2）队列 队列是一种操作受限的线性表，它只允许在线性表的一端进行数据元素的插入操作，而在另一端才能进行数据元素的删除操作。其中，允许插入的一端称为队尾，允许删除的另一端称为队头。 · 特点：先进先出（FIFO——First In，First Out）。 树 1．树结构 树是一个或多个结点元素组成的有限集合T，且满足条件如下： 树结构的重要术语与概念： 叶子——没有后继结点的结点称为叶子（或终端结点）。 分支结点——非叶子结点称为分支结点。 结点的度——一个结点的子树数目就称为该结点的度。 树的度——树中各结点的度的最大值称为该树的度。 子结点——某结点子树的根称为该结点的子结点。 父结点——相对于某结点的子树的根，称为该结点的子树的父结点。 兄弟——具有同一父结点的子结点称为兄弟。 结点的层次——根结点的层次数是1，其他任何结点的层数等于它的父结点的层数加1。 树的深度——一棵树中，结点的最大层次数就是树的深度。 2．二叉树 二叉树结构也是非线性结构中重要的一类，它是有序树，不是树的特殊结构。在二叉树中，每个结点最多只有两棵子树，一个是左子树，一个是右子树。 满二叉树和完全二叉树是两种特殊形式的二叉树。一棵深度为k且有2k(1个结点的二叉树称为满二叉树。满二叉树的特点是每一层上的结点数都达到最大值，2