《数据结构》基本概念

基本概念

数据

数据是信息的载体，在计算机科学中是指所有能输入到计算机中并能被计算机程序识别和处理的符号

集合。

数据元素数据元素也称为结点，是表示数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。

数据项

数据项是构成数据元素的不可分割的最小单位。

数据对象数据对象是具有相同性质的数据元素的集合，是数据的子集。注意：在不产生混淆的情况下，将数据对象简称为数据。

数据结构数据结构是指相互之间存在一定关系的数据元素的集合，即数据结构是一个二元组DataStructure = （D,

R），其中D是数据元素的集合，R是D上关系的集合。按照视点的不同，数据结构分为逻辑结构和存储结构。

数据的逻辑结构数据的逻辑结构是指数据元素之间逻辑关系的整体。根据数据元素之间逻辑关系的不同，数据结构分为四类：

⑴ 集合：数据元素之间就是“属于同一个集合”，除此之外，没有任何关系；

⑵ 线性结构：数据元素之间存在着一对一的线性关系；

⑶ 树结构：数据元素之间存在着一对多的层次关系；

⑷ 图结构：数据元素之间存在着多对多的任意关系。

注意：数据结构分为两类：线性结构和非线性结构。

数据的存储结构数据的存储结构又称为物理结构，是数据及其逻辑结构在计算机中的表示。通常有两种存储结构：顺序存储结构和链接存储结构。

顺序存储结构的基本思想是：用一组连续的存储单元依次存储数据元素，数据元素之间的逻辑关系是由元素的存储位置来表示的。

链接存储结构的基本思想是：用一组任意的存储单元存储数据元素，数据元素之间的逻辑关系是用指针来表示的。

注意：存储结构除了存储数据元素之外，必须存储数据元素之间的逻辑关系。

抽象数据类型抽象数据类型是一个数据结构以及定义在该结构上的一组操作的总称。抽象数据类型提供了使用和实现两个不同的视图，实现了封装和信息隐藏。

算法的定义通俗地讲，算法是解决问题的方法，严格地说，算法是对特定问题求解步骤的一种描述，是指令的有限序列。

算法的特性

⑴ 输入：一个算法有零个或多个输入（即算法可以没有输入），这些输入通常取自于某个特定的对象集合。

⑵ 输出：一个算法有一个或多个输出（即算法必须要有输出），通常输出与输入之间有着某种特定的关系。

⑶ 有穷性：一个算法必须总是(对任何合法的输入)在执行有穷步之后结束，且每一步都在有穷时间内完成。

⑷ 确定性：算法中的每一条指令必须有确切的含义，不存在二义性。并且，在任何条件下，对于相同的输入只能得到相同的输出。

⑸ 可行性：算法描述的操作可以通过已经实现的基本操作执行有限次来实现。

线性表的定义

线性表简称表，是零个或多个具有相同类型的数据元素的有限序列。数据元素的个数称为线性表的长度，长度等于零时称为空表。

线性表的逻辑关系

在一个非空表L= (a i, a2, , a n)中，任意一对相邻的数据元素和a i之间(1< i < n)存在序偶

关系(a i-i，a i)，且a i-i称为a i的前驱，a i称为的后继。在这个序列中，a i无前驱，a n无后继，其它每个元素有且仅有一个前驱和一个后继。

顺序表的存储结构定义

用MaxSize 表示数组的长度,顺序表的存储结构定义如下：

#define MaxSize i00

typedef struct

{

ElemType data[MaxSize]; // ElemType 表示不确定的数据类型

int length; //length 表示线性表的长度

} SeqList;

顺序表是随机存取结构

设顺序表的每个元素占用c个存储单元，则第i个元素的存储地址为：

LOC( a i) = LOC( a i) + (i —1) x c

顺序表的优缺点

顺序表利用了数组元素在物理位置上的邻接关系来表示线性表中数据元素之间的逻辑关系,这使得顺序表具有下列优点：

⑴ 无需为表示表中元素之间的逻辑关系而增加额外的存储空间；

⑵ 可以快速地存取表中任一位置的元素(即随机存取)。

同时,顺序表也具有下列缺点：

⑴ 插入和删除操作需移动大量元素。在顺序表上做插入和删除操作,等概率情况下,平均要移动表中一半的元素。

⑵ 表的容量难以确定。由于数组的长度必须事先确定,因此,当线性表的长度变化较大时,难以确定合适的存储规模。

⑶ 造成存储空间的“碎片”。数组要求占用连续的存储空间,即使存储单元数超过所需的数目,如果不连续也不能使用,造成存储空间的“碎片”现象。

单链表的存储结构定义

单链表的存储结构定义如下：

Struct Node

{ ElemType data; // ElemType 表示不确定的数据类型

struct Node *next;

} *first; //first 为单链表的头指针

双链表的存储结构定义双链表存储结构定义如下：

struct DulNode

{

ElemType data; // ElemType表示不确定的数据类型struct DulNode *prior, * next; // prior 为前驱指针域，next 为后继指针域

} *first; //first表示双链表的头指针

栈的定义

栈是限定仅在表尾进行插入和删除操作的线性表。允许插入和删除的一端称为栈顶，另一端称为栈底，

不含任何数据元素的栈称为空栈。

栈的操作特性

栈的操作具有后进先出的特性。

队列的定义

队列是只允许在一端进行插入操作，而另一端进行删除操作的线性表。允许插入的一端称为队尾，允

许删除的一端称为队头。

队列的操作特性

队列的操作具有先进先出的特性。

循环队列中解决队空队满的判断条件

方法一：附设一个存储队列中元素个数的变量num,当num=0时队空，当num=QueueSize时为队满;

方法二：修改队满条件，浪费一个元素空间，队满时数组中只有一个空闲单元；即队空的条件是

front=rear，队满的条件是(rear+1) % QueueSize=front，队列长度为(rear-front+QueueSize) % QueueSize。方法三：设置标志flag，当front=rear且flag=0时为队空，当front=rear且flag=1时为队满。

串的定义

串是零个或多个字符组成的有限序列。

空格串和空串的定义

只包含空格的串称为空格串。串中所包含的字符个数称为串的长度，长度为0的串称空串，记作”"

串的比较

串的比较是通过组成串的字符之间的比较来进行的。

给定两个串：

X="X1X2 …X n"

Y="y i y2 …y m"

则当n=m 且X i=y i,…，x n=y m 时，称X=Y;

当下列条件之一成立时，称X v Y：

⑴ n v m,且X i=y i (i=1 , 2,…，n);

⑵ 存在某个k w min( m, n)，使得x i=y i(i=1, 2，…,k-1) , x k v y k。

改进的模式匹配算法中next[j]的求法

用next[j]表示t j对应的k值(1w j w m)，其定义如下：

r o j=1

next[j]= max {k | 1w k v j 且"讯2 …t k -1 " =" t j-k+1t j-k+2 … 切"}

L1 其它情况

数组的基本操作

数组是一个具有固定格式和数量的数据集合，在数组上一般不能做插入、删除元素的操作。因此，在

数组中通常只有两种操作：

⑴ 读取：给定一组下标，读取相应的数组元素；

⑵ 修改：给定一组下标，存储或修改相应的数组元素。

二维数组的寻址

按行优先，设二维数组的行下标与列下标的范围分别为］l i, h］与［I2, h2】，则任一元素a j的存储

地址可由下式确定：

LOC(a j) = LOC( a|1|2) + (( i- IJ x (h?—l?+1) + (j-I2)) x c

特殊矩阵的定义

特殊矩阵是指矩阵中有很多值相同的元素并且它们的分布有一定的规律。

矩阵压缩存储的基本思想

压缩存储的基本思想是：⑴为多个值相同的元素只分配一个存储空间；⑵对零元素不分配存储空间。

对称矩阵的压缩存储中：下三角元素a ij (i >j)在一个数组SA中的下标为：k = i x (i-1)/2 + j-1。上三角中的元素a ij (i v j),则访问和它对应的下三角中的元素a ji即可，即：k = j x (j-1)/2 + i-1。

三角矩阵的压缩存储中：下三角矩阵中任一元素a j在一个数组SA中的下标k与i、j的对应关系为：——I i x (i-1)/2 + j-1 当i>j

=I n x (n + 1)/2 当i v j

上三角矩阵元素a j在SA中的下标为：k =(i-1) x (2n-i+2)/2+(j-i)。

稀疏矩阵的压缩存储方式

三元组顺序表和十字链表

三元组的定义

struct eleme nt

{

int row, col;

ElemType item

};

广义表的定义

广义表是n (n》0)个数据元素的有限序列。

表头

当广义表LS非空时，称第一个元素为LS的表头；

表尾

称广义表LS中除去表头后其余元素组成的广义表为LS的。

长度

广义表LS中的直接元素的个数称为LS的长度;

深度

广义表LS中括号的最大嵌套层数称为LS的深度。

树的定义

树是n ( n》0)个结点的有限集合。当n= 0时，称为空树；任意一棵非空树满足以下条件：

⑴ 有且仅有一个特定的称为根的结点；

⑵ 当n> 1时，除根结点之外的其余结点被分成m (m>0)个互不相交的有限集合「，T?,…，T m,其

中每个集合又是一棵树，并称为这个根结点的子树。

结点的度、树的度

某结点所拥有的子树的个数称为该结点的度；树中各结点度的最大值称为该树的度。

叶子结点、分支结点

度为0的结点称为叶子结点，也称为终端结点；度不为0 的结点称为分支结点，也称为非终端结点。

孩子结点、双亲结点、兄弟结点某结点的子树的根结点称为该结点的孩子结点；反之，该结点称为其孩子结点的双亲

路径、路径长度

如果树的结点序列n i, n2,…,n k满足如下关系：结点口是结点口+i的双亲（K i v k）,则把n i, n2,…,n k 称为一条由n i至n k 的路径；路径上经过的边的个数称为路径长度。

祖先、子孙

如果从结点x到结点y有一条路径，那么x就称为y的祖先，而y称为x的子孙。注意：某结点子树中的任一结点都是该结点的子孙。

结点的层数、树的深度（高度）

规定根结点的层数为1,对其余任何结点，若某结点在第k层，则其孩子结点在第k+1层；树中所有结点的最大层数称为树的深度,也称为树的高度。

二叉树的定义

二叉树是n （n > 0）个结点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。

二叉树的特点

二叉树的特点是：⑴ 每个结点最多有两棵子树，所以二叉树中不存在度大于2的结点；⑵ 子树的次

序不能任意颠倒,某结点即使只有一棵子树也要区分是左子树还是右子树。

注意：二叉树和树是两种树结构。

二叉树的基本形态

二叉树具有五种基本形态：⑴空二叉树；⑵ 只有一个根结点；⑶ 根结点只有左子树；⑷ 根结点只

有右子树；⑸ 根结点既有左子树又有右子树。

斜树所有结点都只有左子树的二叉树称为左斜树；所有结点都只有右子树的二叉树称为右斜树；左斜树和右斜树统称为斜树。

斜树的特点：①每一层只有一个结点，即只有度为1和度为0的结点并且只有一个叶子结点；② 斜树

的结点个数与其深度相同。

满二叉树在一棵二叉树中,如果所有分支结点都存在左子树和右子树,并且所有叶子都在同一层上,这样的二叉树称为满二叉树。

满二叉树的特点：① 叶子结点都在最下一层；②只有度为0和度为2的结点。

完全二叉树

对一棵具有n个结点的二叉树按层序编号，如果编号为i（1

号为i 的结点在二叉树中的位置完全相同,则这棵二叉树称为完全二叉树。

完全二叉树的特点是：① 叶子结点只能出现在最下两层，且最下层的叶子结点都集中在左面连续的位置；② 如果有度为1的结点，只可能有一个，且该结点只有左孩子。

二叉树的基本性质

性质1二叉树的第i层上最多有2i-1个结点（i》1）。

性质2在一棵深度为k的二叉树中，最多有2k-1个结点，最少有k个结点。

性质3在一棵二叉树中，如果叶子结点的个数为n0,度为2的结点个数为n2,则

n o= n2 + 1。

性质4具有n个结点的完全二叉树的深度为ll log 2 n 1 o

性质5对一棵具有n个结点的完全二叉树中的结点从1开始按层序编号，则对于任意的编号为i （1

< i w n）的结点（简称为结点i），有：

⑴如果i> 1，则结点i的双亲的编号为||]/2 ；否则结点i是根结点，无双亲；

⑵如果2i w n,则结点i的左孩子的编号为2i ;否则结点i无左孩子；

⑶ 如果2i + 1w n,则结点i的右孩子的编号为2i + 1 ;否则结点i无右孩子。

二叉树的存储

包括：二叉树的顺序存储和二叉树的链式存储。

二叉链表的存储结构定义如下：

struct BiNode

{

ElemType data;

BiNode *lchild, *rchild;

} *root; //root表示二叉链表的头指针

struct TriNode

{

ElemType data;

TriNode *lchild, *rchild, *pare nt; // pare nt 指向该结点的双亲

} *root; //三叉链表的头指针

遍历的含义

所谓遍历就是无重复无遗漏地访问。二叉树的遍历是指从根结点出发，按照某种次序访问二叉树中的所有结点，使得每个结点被访问一次且仅被访问一次。

二叉树的遍历次序定义

前序遍历（或称前根遍历、先序遍历）

若二叉树为空，则空操作返回；否则

⑴访问根结点；

⑵ 前序遍历根结点的左子树；

⑶前序遍历根结点的右子树。