数据结构复习大纲
基本概念及定义
需了解的概念
1) 数据:数据是信息的载体,它能够被计算机识别、存储和加工处理。
2) 数据元素:数据元素是数据的基本单位。
3) 数据结构:数据结构指的是数据及数据之间的相互关系,即数据的组织形式。
数据元素之间的逻辑关系,数据的逻辑结构
数据元素及其关系在计算机存储器内的表示,存储结构
数据的运算,即对数据施加的操作
4) 数据类型:所谓数据类型是一个值的集合以及在这些值上定义的一组操作的总称。
5) 数据的逻辑结构有两大类:线性结构、非线性结构。
6) 数据的存储结构有四种方法:顺序存储、链接存储、索引存储、散列存储。
需背诵的概念
1) 线性表(Linear list):线性表是由 n(n>=0)个数据元素组成的有限序列。
2) 栈(Stack):栈是限制仅在表的一端进行插入和删除运算的线性表,通常称插入、
删除的这一端为栈顶(Top),另一端称为栈底(Bottom)。当表中没有元素时成为空
栈。
先进后出。
3) 队列(Queue):队列是一种运算受限制的线性表,它只允许在表的一端进行插入,
而在表的另一端进行删除。允许删除的一段称为对头(Front),允许插入的一段称为
队尾(Rear)。
先进先出。
4) 串(String):串是零个或多个字符组成的有限序列。
5) 树(Tree):树是 n(n>=0)个结点的有限集 T,T 为空时称为空树,否则它满足一下两
个条件:
(1) 有且仅有一个特定的称为根(Root)的结点;
(2) 其余的结点可分为 m(m>=0)各户不相交的子集,其中每个子集本身又是一棵
树,并称其为根的子树(Subtree)。
6) 二叉树:二叉树(Binary Tree)是 n(n>=0)个结点的有限集,他或者是空集,或者是
一个根结点及两棵互不相交、分别称作这个根的左子树和右子树的二叉树组成。
7) 图:图是一种复杂的非线性结构,它的结点的前趋和后继个数都是不加限制的,
可作如下定义:图 G 是由两个集合 V 和 E 组成,记为 G=(V,E),其中 V 是顶
点的有穷非空集合,E 是 V 中顶点偶对(称为边)的有穷集。
评论2