数据结构基本概念(1).doc

《数据结构基本概念(1).doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第一章数据结构基本概念数据：计算机程序所加工处理的描述客观事物的符号表示。数据元素：数据的基本单位，是数据集合中的一个个体,在计算机程序中通常作为一个整体进行考虑和处理。数据元素可由一个或若干个数据项所组成。数据项：是具有独立意义的数据的最小单位。数据对象：性质相同的数据元素的集合,是数据的一个子集。数据结构：相互之间存在一种或多种特定关系的数据元素的集合。即数据的组织形式。数据元素相互之间的关系称为结构。四种基本的数据结构是：集合、线性结构、树形结构、和图形结构。数据结构包括三个方面的内容：逻辑结构、存储结构、基本操作（运算）数据类型：一个值的

2、集合和定义在这个值集上的一组操作。程序设计语言中对于给定变量的所有可能取值的集合。抽象数据类型（ADT）：一种数据类型及在这种数据类型上定义的一组操作。包括数据类型的定义和这种数据类型的操作集合。第二章线性表线性表是n(n>=0)个数据元素的有限序列，同一线性表中的数据元素必定具有相同特性，即属于同一数据对象，相邻数据元素之间存在序偶关系。n定义为线性表的长度；n为0表示该线性表为空表；数据元素可以是一个数、一个符号或由多个数据项所构成的。线性表中任一数据元素的存储位置为：线性链表是一种动态存储结构，所占用的存储空间是在程序的执行过程中得到的，当

3、线性链表要增加一个结点时，向系统申请一个存储空间，删除结点时要将空间释放。由线性链表的结点定义，每个结点中均只含有一个指针域，用于指向其后继结点，故也称单链表。循环链表是线性表的另一种形式的链式存储表示。它的特点是表中最后一个结点的指针域指向头结点，整个链表成为一个由链指针相链接的环，并且可将头指针设成指向最后一个结点（尾指针）。空的循环链表由只含一个自成循环的头结点表示。若双向链表中的两个链均构成回路，则称为双向循环链表。第三章栈和队列栈是限定只能在表的一端（表尾）进行插入和删除操作的线性表；允许插入和删除的一端，称为栈顶(top)；另一端则称

4、为栈底(bottom)；栈又叫做后进先出（LIFO）的线性表。为了指示当前的栈顶元素，需设一个指针top指示当前栈顶的位置，称为栈顶指针。队列也是受限的线性表。限定只能在队列的一端插入元素，另一端删除元素。插入元素的一端是队尾(rear)，删除元素的一端是队头(front)。队列具有先进先出的特点，因此称为先进先出（FIFO）线性表。第一章串串是由n(n>=0)个任意字符组成的有限序列。当n为零时，称为空串。由一个或多个空格符组成的串称为空格串。子串：串中任意连续的字符组成的子序列称为该串的子串。主串：包含子串的串。子串的位置：子串的第一个字符在

5、主串中的序号称为子串的位置。两个串相等：当且仅当两个串的长度相等且对应位置上的字符都相同。第二章数组与广义表数组是连续的、有限的、有序的、同构的数据元素的集合；LOC(ai)=LOC(a1)+(i-1)*L（一维数组）LOC(aij)=LOC(a11)+[(i-1)*N+j-1]*L（行序为主的存储方式）特殊矩阵：三角矩阵、对称矩阵或对角矩阵，值相同或零元素的分布在矩阵中有一定的规律。稀疏矩阵:非零元素个数远小于矩阵元素个数。压缩存储：为多个值相同的元只分配一个存储空间以节省存储空间；对零元不分配空间。广义表：LS=(a1,a2,…,an)LS为

6、广义表的名称，n为广义表的长度，ai可以是单个元素，也可以是广义表，称为LS的原子和子表。当广义表非空时，称第一个元素a1为表头（Head），称其余元素组成的表（a2,a3…,an）为表尾（Tail）。第三章树和二叉树树结点树中一个独立单元。包含一个数据元素及若干指向其子树的分支。树根树中唯一没有前趋的结点。结点的度(Degree)结点拥有的子树数，称为结点的度。树的度树中各结点的度的最大值。树叶(Leaf)度为0的结点。也称叶结点。除根和叶子以外的其他结点称为中间结点。双亲(Parent)和孩子(Child)我们把一个树结点的直接前趋称之为该结

7、点的双亲；反之把一个树结点的所有直接后趋称为该结点的孩子。兄弟(Sibling)：同一双亲的孩子之间互称为兄弟。结点的层次(Level)从根算起，根为第一层，根的孩子为第二层，树中任一结点的层次等于它的双亲的层次加1。树的深度(Depth)树中各结点层次的最大值称为树的深度或高度。有序树和无序树如果树中结点的各子树可看成从左至右是有次序的（即不能互换），则称该树为有序树。否则称为无序树。在有序树的最左边的子树的根称为第一孩子。最右边称为最后一个孩子。森林(Forest)m(m≥0)棵互不相交的树的集合。对树中每个结点而言，其子树的集合即为森林。由

8、此也可以以森林和树的相互递归定义来描述树。线索二叉树：为每个结点加上线索的二叉树称为线索二叉树。线索:指向前驱结点和后继结点的指针称为线