数据结构复习指导

文章作者 100test 发表时间 2007:03:16 22:32:40
来源 100Test.Com百考试题网

第一章：绪论：

一、概念：

数据结构：是一门研究程序设计中计算机操作的对象以及它们之间的关系和运算的一门学科。

数据：是描述额观事物的数、字符以及所有能输入到计算机中被计算机程序加工处理的信息的集合。

数据元素：数据元素是数据的基本单位。（一个数据项或多个数据项（域）。数据项是数据的最小单位。结点、顶点、记录。

数据对象：是性质相同的数据元素的集合。

数据结构：研究是是数据元素之间抽象化的相互关系和这种关系在计算机中的存贮表示，并对每种结构定义各自的运算，设计出相应的算法，而且经过运算后所得的新结构一般仍然是原来的结构类型。

数据类型：是指程序设计语言中各变量可取的数据种类。

算法：是执行特定计算的有穷过程。特点：

·动态有穷·确定性·输入·输出·可行性。

第二章 线性表和数组：

概念：

线性表：是N个元素构成的有限序列。

顺序存贮结构：地址计算，插入、删除。

链式存贮结构：单链表，查找、插入、删除。

循环链表：

双向链表：

二、数组：

以行为主；

以列为主；计算地址：

三、栈：是一种特殊的线性表，这种表只能在固定的一端进行插入与删除运算。

队列：是另一种特殊的线性表，删除运算限定在表的一端进行，而插入运算在另一端进行。

第三章：串

是由N个字符组成的有限序列。

存贮结构：

顺序表示法：

1、紧缩格式 2、非紧缩格式 3、以单字节为单位的存贮方式

链式表示法：

串名的存贮映象：

第四章：树

一、概念：

树：是一个或多个结点的有穷集合T，且满足以下条件：

1、有且仅有一个指定的称作树根的结点；

2、除根以外的其余结点被分成m个不相交的集合，这些集合的每一个又都是树，并且称为根的子树。

结点的度：结点N的子树数称为结点的度。

树的度：树T中各结点的度的最大值称的树T的度。

叶子：树中度为0的结点称为叶子（终端结点）。

分枝结点：树中度不为0的结点称为分枝结点（非终端结点）。

双亲和孩子：若树中结点P的一棵子树的根是结点C，则我们称P是C的双亲或父母，反之称C是P的孩子。

结点的层数：树的层数为1，其余任一结点的层数等于它的双亲的层数加1。

树的深度：树中各结点的层数的最大值称为T的深度（高度）。

兄弟和堂兄弟：同一双亲的孩子之间互称为兄弟，其双亲在同一层的结点互为堂兄弟。

祖先和子孙：一个点的祖先是指从树的根到该结点所经分枝上的所有结点。一个结点的子树的所有结点都称为该结点的子孙。

有序树和无序树：如果树中结点各棵子树规定从左至右是有次序的，则称树为有序树，否则为无序树。

森林：N棵互不相交的树的集合称为森林。

二、树的存贮表示：

1、双亲数组表示：记录型一维数组：data,parent

2、孩子链表表示法：

·多重链表表示法: data,degree,link1,link2…

·单链表表示法:data,likn

3、左孩子右兄弟链表示法：lchild,data,rsibling