数据结构基本概念Word格式文档下载.doc
《数据结构基本概念Word格式文档下载.doc》由会员分享，可在线阅读，更多相关《数据结构基本概念Word格式文档下载.doc（15页珍藏版）》请在冰点文库上搜索。
一个算法有零个或多个输入（即算法可以没有输入），这些输入通常取自于某个特定的对象集合。
⑵输出：
一个算法有一个或多个输出（即算法必须要有输出），通常输出与输入之间有着某种特定的关系。
⑶有穷性：
一个算法必须总是（对任何合法的输入）在执行有穷步之后结束，且每一步都在有穷时间内完成。
⑷确定性：
算法中的每一条指令必须有确切的含义，不存在二义性。
并且，在任何条件下，对于相同的输入只能得到相同的输出。
⑸可行性：
算法描述的操作可以通过已经实现的基本操作执行有限次来实现。
线性表的定义
线性表简称表，是零个或多个具有相同类型的数据元素的有限序列。
数据元素的个数称为线性表的长度，长度等于零时称为空表。
线性表的逻辑关系
在一个非空表L＝（a1，a2，……，an）中，任意一对相邻的数据元素ai-1和ai之间（1＜i≤n）存在序偶关系（ai-1，ai），且ai-1称为ai的前驱，ai称为ai-1的后继。
在这个序列中，a1无前驱，an无后继，其它每个元素有且仅有一个前驱和一个后继。
顺序表的存储结构定义
用MaxSize表示数组的长度，顺序表的存储结构定义如下：
#defineMaxSize100
typedefstruct
{
ElemTypedata[MaxSize];
//ElemType表示不确定的数据类型
intlength;
//length表示线性表的长度
}SeqList;
顺序表是随机存取结构
设顺序表的每个元素占用c个存储单元，则第i个元素的存储地址为：
LOC（ai）=LOC（a1）＋（i－1）×
c
顺序表的优缺点
顺序表利用了数组元素在物理位置上的邻接关系来表示线性表中数据元素之间的逻辑关系，这使得顺序表具有下列优点：
⑴无需为表示表中元素之间的逻辑关系而增加额外的存储空间；
⑵可以快速地存取表中任一位置的元素（即随机存取）。
同时，顺序表也具有下列缺点：
⑴插入和删除操作需移动大量元素。
在顺序表上做插入和删除操作，等概率情况下，平均要移动表中一半的元素。
⑵表的容量难以确定。
由于数组的长度必须事先确定，因此，当线性表的长度变化较大时，难以确定合适的存储规模。
⑶造成存储空间的“碎片”。
数组要求占用连续的存储空间，即使存储单元数超过所需的数目，如果不连续也不能使用，造成存储空间的“碎片”现象。
单链表的存储结构定义
单链表的存储结构定义如下：
StructNode
{ElemTypedata;
structNode*next;
}*first;
//first为单链表的头指针
双链表的存储结构定义
双链表存储结构定义如下：
structDulNode
ElemTypedata;
structDulNode*prior,*next;
//prior为前驱指针域，next为后继指针域
//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…xn"
Y="
y1y2…ym"
则当n=m且x1=y1，…，xn=ym时，称X=Y；
当下列条件之一成立时，称X＜Y：
⑴n＜m，且xi=yi（i=1，2，…，n）；
⑵存在某个k≤min（m，n），使得xi=yi（i=1，2，…，k-1），xk＜yk。
改进的模式匹配算法中next[j]的求法
用next[j]表示tj对应的k值（1≤j≤m），其定义如下：
0j=1
max{k|1≤k＜j且＂t1t2…tk-1＂=＂tj-k+1tj-k+2…tj-1＂}
1其它情况
next[j]=
数组的基本操作
数组是一个具有固定格式和数量的数据集合，在数组上一般不能做插入、删除元素的操作。
因此，在数组中通常只有两种操作：
⑴读取：
给定一组下标，读取相应的数组元素；
⑵修改：
给定一组下标，存储或修改相应的数组元素。
二维数组的寻址
按行优先，设二维数组的行下标与列下标的范围分别为［l1，h1］与［l2，h2］，则任一元素aij的存储地址可由下式确定：
LOC（aij）＝LOC（al1l2）＋（（i－l1）×
（h2－l2＋1）＋（j－l2））×
特殊矩阵的定义
特殊矩阵是指矩阵中有很多值相同的元素并且它们的分布有一定的规律。
矩阵压缩存储的基本思想
压缩存储的基本思想是：
⑴为多个值相同的元素只分配一个存储空间；
⑵对零元素不分配存储空间。
对称矩阵的压缩存储中：
下三角元素aij（i≥j）在一个数组SA中的下标为：
k=i×
（i-1）/2+j-1。
上三角中的元素aij（i＜j），则访问和它对应的下三角中的元素aji即可，即：
k=j×
（j-1）/2+i-1。
三角矩阵的压缩存储中：
下三角矩阵中任一元素aij在一个数组SA中的下标k与i、j的对应关系为：
k=
i×
（i-1）/2+j-1当i≥j
n×
（n＋1）/2当i＜j
上三角矩阵元素aij在SA中的下标为：
k=（i-1）×
（2n-i+2）/2+（j-i）。
稀疏矩阵的压缩存储方式
三元组顺序表和十字链表
三元组的定义
structelement
{
introw,col;
ElemTypeitem
};
广义表的定义
广义表是n（n≥0）个数据元素的有限序列。
表头
当广义表LS非空时，称第一个元素为LS的表头；
表尾
称广义表LS中除去表头后其余元素组成的广义表为LS的。
长度
广义表LS中的直接元素的个数称为LS的长度；
深度
广义表LS中括号的最大嵌套层数称为LS的深度。
树的定义
树是n（n≥0）个结点的有限集合。
当n＝0时，称为空树；
任意一棵非空树满足以下条件：
⑴有且仅有一个特定的称为根的结点；
⑵当n＞1时，除根结点之外的其余结点被分成m（m>
0）个互不相交的有限集合T1，T2，…，Tm，其中每个集合又是一棵树，并称为这个根结点的子树。
结点的度、树的度
某结点所拥有的子树的个数称为该结点的度；
树中各结点度的最大值称为该树的度。
叶子结点、分支结点
度为0的结点称为叶子结点，也称为终端结点；
度不为0的结点称为分支结点，也称为非终端结点。
孩子结点、双亲结点、兄弟结点
某结点的子树的根结点称为该结点的孩子结点；
反之，该结点称为其孩子结点的双亲
路径、路径长度
如果树的结点序列n1,n2,…,nk满足如下关系：
结点ni是结点ni+1的双亲（1≤i＜k），则把n1,n2,…,nk称为一条由n1至nk的路径；
路径上经过的边的个数称为路径长度。
祖先、子孙
如果从结点x到结点y有一条路径，那么x就称为y的祖先，而y称为x的子孙。
某结点子树中的任一结点都是该结点的子孙。
结点的层数、树的深度（高度）
规定根结点的层数为1，对其余任何结点，若某结点在第k层，则其孩子结点在第k+1层；
树中所有结点的最大层数称为树的深度，也称为树的高度。
二叉树的定义
二叉树是n（n≥0）个结点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。
二叉树的特点
二叉树的特点是：
⑴每个结点最多有两棵子树，所以二叉树中不存在度大于2的结点；
⑵子树的次序不能任意颠倒，某结点即使只有一棵子树也要区分是左子树还是右子树。
二叉树和树是两种树结构。
二叉树的基本形态
二叉树具有五种基本形态：
⑴空二叉树；
⑵只有一个根结点；
⑶根结点只有左子树；
⑷根结点只有右子树；
⑸根结点既有左子树又有右子树。
斜树
所有结点都只有左子树的二叉树称为左斜树；
所有结点都只有右子树的二叉树称为右斜树；
左斜树和右斜树统称为斜树。
斜树的特点：
①每一层只有一个结点，即只有度为1和度为0的结点并且只有一个叶子结点；
②斜树的结点个数与其深度相同。
满二叉树
在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上，这样的二叉树称为满二叉树。
满二叉树的特点：
①叶子结点都在最下一层；
②只有度为0和度为2的结点。
完全二叉树
对一棵具有n个结点的二叉树按层序编号，如果编号为i（1≤i≤n）的结点与同样深度的满二叉树中编号为i的结点在二叉树中的位置完全相同，则这棵二叉树称为完全二叉树。
完全二叉树的特点是：
①叶子结点只能出现在最下两层，且最下层的叶子结点都集中在左面连续的位置；
②如果有度为1的结点，只可能有一个，且该结点只有左孩子。
二叉树的基本性质
性质1二叉树的第i层上最多有2i-1个结点（i≥1）。
性质2在一棵深度为k的二叉树中，最多有2k-1个结点，最少有k个结点。
性质3在一棵二叉树中，如果叶子结点的个数为n0，度为2的结点个数为n2，则
n0＝n2＋1。
性质4具有n个结点的完全二叉树的深度为。
性质5对一棵具有n个结点的完全二叉树中的结点从1开始按层序编号，则对于任意的编号为i（1≤i≤n）的结点（简称为结点i），有：
⑴如果i＞1，则结点i的双亲的编号为；
否则结点i是根结点，无双亲；
⑵如果2i≤n，则结点i的左孩子的编号为2i；
否则结点i无左孩子；
⑶如果2i＋1≤n，则结点i的右孩子的编号为2i＋1；
否则结点i无右孩子。
二叉树的存储
包括：
二叉树的顺序存储和二叉树的链式存储。
二叉链表的存储结构定义如下：
structBiNode
BiNode*lchild,*rchild;
}*root;
//root表示二叉链表的头指针
structTriNode
TriNode*lchild,*rchild,*parent;
//parent指向该结点的双亲
//三叉链表的头指针
遍历的含义
所谓遍历就是无重复无遗漏地访问。
二叉树的遍历是指从根结点出发，按照某种次序访问二叉树中的所有结点，使得每个结点被访问一次且仅被访问一次。
二叉树的遍历次序定义
前序遍历（或称前根遍历、先序遍历）
若二叉树为空，则空操作返回；
否则
⑴访问根结点；
⑵前序遍历根结点的左子树；
⑶前序遍历根结点的右子树。
中序遍历（或称中根遍历）
⑴中序遍历根结点的左子树；
⑵访问根结点；
⑶中序遍历根结点的右子树。
后序遍历（或称后根遍历）
⑴后序遍历根结点的左子树；
⑵后序遍历根结点的右子树；
⑶访问根结点。
层序遍历
二叉树的层序遍历是从二叉树的第一层（根结点）开始，从上至下逐层遍历，在同一层中，则按从左到右的顺序对结点逐个访问。
线索二叉树的定义
在一个具有n个结点的二叉链表中，利用n+1个空指针域存放指向该结点在某种遍历序列中的前驱和后继结点的指针，这些指向前驱和后继结点的指针称为线索，加上线索的二叉树称为线索二叉树，相应地，加上线索的二叉链表称为线索链表。
线索二叉树的存储结构定义
线索链表中的结点定义如下：
enumflag{Child,Thread};
//枚举类型，枚举常量Child=0，Thread=1
structThrNode
//ElemType表示不确定的数据类型
ThrNode*lchild,*rchild;
flagltag,rtag;
}*root;
//root表示线索链表的头指针
树的存储结构
双亲表示法、孩子表示法、孩子兄弟表示法。
双亲表示法的存储结构定义如下：
#defineMaxSize100;
//树中最大结点个数
structPNode//数组元素的类型
//树中结点的数据信息，
intparent;
//该结点的双亲在数组中的下标
PNodeTree[MaxSize];
孩子表示法的存储结构定义如下：
structCTNode//孩子结点
intchild;
CTNode*next;
structCBNode//表头结点
CTNode*firstchild;
//指向孩子链表的头指针
孩子兄弟表示法又称为二叉链表表示法，存储结构定义如下：
structTNode
TNode*firstchild;
//firstchild指向该结点的第一个孩子
TNode*rightsib;
//rightsib指向该结点的右兄弟
树转换为二叉树
树转换为二叉树的方法是：
⑴加线——树中所有相邻兄弟结点之间加一条连线；
⑵去线——对树中的每个结点，只保留它与第一个孩子结点之间的连线，删去它与其它孩子结点之间的连线；
⑶层次调整——以根结点为轴心，将树顺时针转动一定的角度，使之层次分明。
森林转换为二叉树
森林转换为二叉树的方法如下：
⑴将森林中的每棵树转换成二叉树；
⑵从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树根结点的右孩子，当所有二叉树连起来后，所得到的二叉树就是由森林转换的二叉树。
二叉树转换为树或森林
树和森林转换为二叉树的过程是可逆的，将一棵二叉树还原为树或森林的方法如下：
⑴加线——若某结点x是其双亲y的左孩子，则把结点x的右孩子、右孩子的右孩子、……，都与结点y用线连起来；
⑵去线——删去原二叉树中所有的双亲结点与右孩子结点的连线；
⑶层次调整——整理由⑴、⑵两步所得到的树或森林，使之层次分明。
树的遍历序列与二叉树的遍历序列之间的对应关系
根据树与二叉树的转换关系以及树和二叉树遍历的操作定义可知，树的遍历序列与由树转化成的二叉树的遍历序列之间具有如下对应关系：
树的前序遍历序列等于二叉树的前序遍历序列，树的后序遍历序列等于二叉树的中序遍历序列。
哈夫曼树中叶子结点的权值
叶子结点的权值是指对叶子结点赋予的一个有意义的数值量。
二叉树的带权路径长度
设二叉树具有n个带权值的叶子结点，从根结点到各个叶子结点的路径长度与相应叶子结点权值的乘积之和称做二叉树的带权路径长度，记为：
WPL=
其中，wk为第k个叶子结点的权值；
lk为从根结点到第k个叶子结点的路径长度。
哈夫曼树定义
给定一组具有确定权值的叶子结点，可以构造出不同的二叉树，将其中带权路径长度最小的二叉树称为哈夫曼树，也称为最优二叉树。
哈夫曼算法的基本思想
哈夫曼算法的基本思想是：
⑴初始化：
由给定的n个权值{w1，w2，…，wn}构造n棵只有一个根结点的二叉树，从而得到一个二叉树集合F＝{T1，T2，…，Tn}；
⑵选取与合并：
在F中选取根结点的权值最小的两棵二叉树分别作为左、右子树构造一棵新的二叉树，这棵新二叉树的根结点的权值为其左、右子树根结点的权值之和；
⑶删除与加入：
在F中删除作为左、右子树的两棵二叉树，并将新建立的二叉树加入到F中；
⑷重复⑵、⑶两步，当集合F中只剩下一棵二叉树时，这棵二叉树便是哈夫曼树。
图的定义
图是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为：
G=（V，E）
其中，G表示一个图，V是图G中顶点的集合，E是图G中顶点之间边的集合。
无向图与有向图
若顶点vi和vj之间的边没有方向，则称这条边为无向边，用无序偶对（vi，vj）来表示；
若从顶点vi到vj的边有方向，则称这条边为有向边（也称为弧），用有序偶对<
vi,vj>
来表示，vi称为弧尾，vj称为弧头。
如果图的任意两个顶点之间的边都是无向边，则称该图为无向图，否则称该图为有向图。
简单图
若不存在顶点到其自身的边，且同一条边不重复出现，则称这样的图为简单图。
邻接、依附
在无向图中，对于任意两个顶点vi和vj，若存在边（vi，vj），则称顶点vi和vj互为邻接点，同时称边（vi，vj）依附于顶点vi和vj。
在有向图中，对于任意两个顶点vi和vj，若存在弧<
vi，vj>
，则称顶点vj是vi的邻接点，同时称弧<
依附于顶点vi和vj。
无向完全图、有向完全图
在无向图中，如果任意两个顶点之间都存在边，则称该图为无向完全图。
含有n个顶点的无向完全图有n×
（n-1）/2条边。
在有向图中，如果任意两顶点之间都存在方向互为相反的两条弧，则称该图为有向完全图。
含有n个顶点的有向完全图有n×
（n-1）条边。
稠密图、稀疏图
称边数很少的图为稀疏图，反之，称为稠密图。
顶点的度、入度、出度
在无向图中，顶点v的度是指依附于该顶点的边的个数，记为TD（v）。
在具有n个顶点e条边的无向图中，有下式成立：
在有向图中，顶点v的入度是指以该顶点为弧头的弧的个数，记为ID（v）；
顶点v的出度是指以该顶点为弧尾的弧的个数，记为OD（v）。
在具有n个顶点e条边的有向图中，有下式成立：
连通图、连通分量
在无向图中，若任意顶点vi和vj（i≠j）之间有路径，则称该图是连通图。
非连通图的极大连通子图称为连通分量。
强连通图、强连通分量
在有向图中，对任意顶点vi和vj（i≠j），若从顶点vi到vj和从顶点vj到vi均有路径，则称该有向图是强连通图。
非强连通图的极大强连通子图称为强连通分量。
邻接矩阵的存储结构定义
假设图G＝（V，E）有n个顶点，则邻接矩阵是一个n×
n的方阵，定义为：
1若（vi，vj）∈E或<
∈E
0否则
arc[i][j]＝
邻接矩阵的存储结构定义如下：
#defineMaxSize10
ElemTypevertex[MaxSize];
//存放图中顶点的信息，ElemType表示不确定的数据类型
intarc[MaxSize][MaxSize];
//存放图中边的信息
intvertexNum,arcNum;
//图的顶点数和边数
}MGraph;
邻接表的存储结构定义
邻接表是一种顺序存储与链接存储相结合的存储方法，具体方法为：
将顶点vi的所有邻接点链成一个单链表，称为顶点vi的边表（对于有向图则称为出边表），边表的头指针和顶点的数据信息采用顺序存储（称为顶点表）。
所以，在邻接表中存在两种结点：
顶点表结点和边表结点。
vertex
firstedge
adjvex
next
顶点表结点边表结点
邻接表表示的结点结构
其中，vertex：
数据域，存放顶点信息；
firstedge：
指针域，边表的头指针；
adjvex：
邻接点域，存
升级会员 