数据结构基本概念

《数据结构基本概念》由会员分享，可在线阅读，更多相关《数据结构基本概念（27页珍藏版）》请在金锄头文库上搜索。

1、基本概念数据 数据是信息的载体，在计算机科学中是指所有能输入到计算机中并能被计算机程 序识别和处理的符号集合。数据元素数据元素也称为结点，是表示数据的基本单位，在计算机程序中通常作为一个整 体进行考虑和处理。数据项数据项是构成数据元素的不可分割的最小单位。数据对象数据对象是具有相同性质的数据元素的集合，是数据的子集。注意：在不产生混淆的情况下，将数据对象简称为数据。数据结构数据结构是指相互之间存在一定关系的数据元素的集合，即数据结构是一个二元 组 DataStrueture = (D,R),其中D是数据元素的集合，R是D上关系的集合。按照视点的不同，数据 结构分为逻辑结构和存储结构。数据的逻辑

2、结构数据的逻辑结构是指数据元素之间逻辑关系的整体。根据数据元素之间逻辑关系 的不同，数据结构分为四类： 集合：数据元素之间就是“属于同一个集合”，除此之外，没有任何关系；线性结构：数据元素之间存在着一对一的线性关系； 树结构：数据元素之间存在着一对多的层次关系；图结构：数据元素之间存在着多对多的任意关系。注意：数据结构分为两类：线性结构和非线性结构。数据的存储结构数据的存储结构又称为物理结构，是数据及其逻辑结构在计算机中的表示。通常 有两种存储结构：顺序存储结构和链接存储结构。顺序存储结构的基本思想是：用一组连续的存储单元依次存储数据元素，数据元 素之间的逻辑关系是由元素的存储位置来表示的。链

3、接存储结构的基本思想是：用一组任意的存储单元存储数据元素，数据元素之 间的逻辑关系是用指针来表示的。注意：存储结构除了存储数据元素之外，必须存储数据元素之间的逻辑关系。 抽象数据类型抽象数据类型是一个数据结构以及定义在该结构上的一组操作的总称。抽象数据 类型提供了使用和实现两个不同的视图，实现了封装和信息隐藏。算法的定义通俗地讲，算法是解决问题的方法，严格地说，算法是对特定问题求解步骤的一 种描述，是指令的有限序列。算法的特性 输入：一个算法有零个或多个输入（即算法可以没有输入），这些输入通常取 自于某个特定的对象集合。 输出：一个算法有一个或多个输出（即算法必须要有输出），通常输出与输入 之

4、间有着某种特定的关系。有穷性：一个算法必须总是（对任何合法的输入）在执行有穷步之后结束， 且每一步都在有穷时间内完成。确定性：算法中的每一条指令必须有确切的含义，不存在二义性。并且，在 任何条件下，对于相同的输入只能得到相同的输出。可行性：算法描述的操作可以通过已经实现的基本操作执行有限次来实现。线性表的定义 线性表简称表，是零个或多个具有相同类型的数据元素的有限序列。数据元素的 个数称为线性表的长度，长度等于零时称为空表。线性表的逻辑关系在一个非空表L=(al, a2, , an)中，任意一对相邻的数据元素aiT和ai之间(lViWn)存在序偶关系(ai-1, ai),且ai-1称为ai的前

5、驱，ai称为ai-1的后继。在这个序 列中，al无前驱，an无后继，其它每个元素有且仅有一个前驱和一个后继。顺序表的存储结构定义用MaxSize表示数组的长度，顺序表的存储结构定义如下：#define MaxSize 100typedef struetElemType dataMaxSize; / ElemType 表示不确定的数据类型int length; /length表示线性表的长度 SeqList;顺序表是随机存取结构设顺序表的每个元素占用e个存储单元，则第i个元素的存储地址为： LOC(ai)二 LOC(a1) + (i 1) Xe顺序表的优缺点顺序表利用了数组元素在物理位置上的邻接

6、关系来表示线性表中数据元素之间 的逻辑关系，这使得顺序表具有下列优点：无需为表示表中元素之间的逻辑关系而增加额外的存储空间； 可以快速地存取表中任一位置的元素(即随机存取)。同时，顺序表也具有下列缺点：插入和删除操作需移动大量元素。在顺序表上做插入和删除操作，等概率情 况下，平均要移动表中一半的元素。表的容量难以确定。由于数组的长度必须事先确定，因此，当线性表的长度变化较大时，难以确定合适的存储规模。 造成存储空间的“碎片”数组要求占用连续的存储空间，即使存储单元数超 过所需的数目，如果不连续也不能使用，造成存储空间的“碎片”现象。单链表的存储结构定义单链表的存储结构定义如下：Struet N

7、ode ElemType data; / ElemType表示不确定的数据类型struet Node *next; * firs t; /first为单链表的头指针双链表的存储结构定义双链表存储结构定义如下：struet DulNodeElemType data; / ElemType表示不确定的数据类型st rue t DulNode * prior, * nex t; / prior 为前驱扌旨针域，nex t 为后继扌旨针 域 * firs t; /first表示双链表的头指针栈的定义栈是限定仅在表尾进行插入和删除操作的线性表。允许插入和删除的一端称为栈 顶，另一端称为栈底，不含任何数据

8、元素的栈称为空栈。栈的操作特性栈的操作具有后进先出的特性。队列的定义队列是只允许在一端进行插入操作，而另一端进行删除操作的线性表。允许插入 的一端称为队尾，允许删除的一端称为队头。队列的操作特性队列的操作具有先进先出的特性。循环队列中解决队空队满的判断条件方法一：附设一个存储队列中元素个数的变量num,当num=O时队空，当 num二QueueSize 时为队满；方法二：修改队满条件，浪费一个元素空间，队满时数组中只有一个空闲单元； 即队空的条件是front二rear，队满的条件是（rear+1） % QueueSize二front，队列长度为（rear- front+QueueSize） %

9、 QueueSize。方法三：设置标志flag，当front二rear且flag=0时为队空，当front二rear 且flag=l时为队满。串的定义串是零个或多个字符组成的有限序列。空格串和空串的定义只包含空格的串称为空格串。串中所包含的字符个数称为串的长度，长度为0 的串称空串，记作 。串的比较串的比较是通过组成串的字符之间的比较来进行的。给定两个串：X二xlx2xnY二y1y2ym则当 n二m 且 xl二yl，xn=ym 时，称 X=Y；当下列条件之一成立时，称XVY：（1） nVm，且 xi=yi （i=1， 2，n）； 存在某个 kWmin（m，n），使得 xi=yi （i=1， 2

10、，k-1）， xkVyk。改进的模式匹配算法中nextj的求法用nextj表示tj对应的k值（lWjWm），其定义如下：数组的基本操作数组是一个具有固定格式和数量的数据集合，在数组上一般不能做插入、删除元 素的操作。因此，在数组中通常只有两种操作： 读取：给定一组下标，读取相应的数组元素；修改：给定一组下标，存储或修改相应的数组元素。二维数组的寻址按行优先，设二维数组的行下标与列下标的范围分别为ll,hl与l2,h2, 则任一元素aij的存储地址可由下式确定：LOC(aij)=LOC(all12) + (i 1l)X (h2 12 + l) + (j 12) Xc特殊矩阵的定义特殊矩阵是指矩阵

11、中有很多值相同的元素并且它们的分布有一定的规律。矩阵压缩存储的基本思想压缩存储的基本思想是： 为多个值相同的元素只分配一个存储空间； 对零 元素不分配存储空间。对称矩阵的压缩存储中：下三角元素aij (i三j)在一个数组SA中的下标 为：k = iX (i-l)/2 + j-1。上三角中的元素aij (iVj),则访问和它对应的下三角中的元素aji即可，即：k =j X (j-1)/2 + i-1。三角矩阵的压缩存储中：下三角矩阵中任一元素aij在一个数组SA中的 下标k与i、j的对应关系为：上三角矩阵兀素aij在SA中的下标为：k =(iT)X(2n-i+2)/2+(j-i)。稀疏矩阵的压缩

12、存储方式三元组顺序表和十字链表三元组的定义struet elementint row, eol;ElemType item；广义表的定义广义表是n (n0)个数据元素的有限序列。表头当广义表LS非空时，称第一个元素为LS的表头；表尾称广义表LS中除去表头后其余元素组成的广义表为LS的。长度广义表LS中的直接元素的个数称为LS的长度；深度广义表LS中括号的最大嵌套层数称为LS的深度。树的定义树是n (n0)个结点的有限集合。当n = 0时，称为空树；任意一棵非空树满 足以下条件：有且仅有一个特定的称为根的结点；当nl时，除根结点之外的其余结点被分成m (m0)个互不相交的有限集 合 T1, T2

13、,，Tm,其中每个集合又是一棵树，并称为这个根结点的子树。结点的度、树的度某结点所拥有的子树的个数称为该结点的度；树中各结点度的最大值称为该树的 度。k二iX(il)/2 + j-1 当 i三jnX (n+l)/2 当 iVj公众号【大学百科资料】整理，有超百科复习资料+海量网课资源5叶子结点、分支结点度为0的结点称为叶子结点，也称为终端结点；度不为0的结点称为分支结 点，也称为非终端结点。孩子结点、双亲结点、兄弟结点某结点的子树的根结点称为该结点的孩子结点；反之，该结点称为其孩子结点 的双亲路径、路径长度如果树的结点序列nl, n2,，nk满足如下关系：结点ni是结点ni+1的 双亲(lWi

14、Vk)，则把 nl, n2,，nk称为一条由nl至nk的路径；路径上经过的边的个数称为路径长度。祖先、子孙如果从结点x到结点y有一条路径，那么x就称为y的祖先，而y称为 x的子孙。注意：某结点子树中的任一结点都是该结点的子孙。结点的层数、树的深度（高度）规定根结点的层数为1，对其余任何结点，若某结点在第k层，则其孩子结点 在第k+1层；树中所有结点的最大层数称为树的深度，也称为树的高度。二叉树的定义二叉树是n （n0）个结点的有限集合，该集合或者为空集（称为空二叉树）， 或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。二叉树的特点二叉树的特点是：每个结点最多有两棵

15、子树，所以二叉树中不存在度大于2 的结点；子树的次序不能任意颠倒，某结点即使只有一棵子树也要区分是左子树还是右子树。 注意：二叉树和树是两种树结构。二叉树的基本形态二叉树具有五种基本形态：（1）空二叉树；只有一个根结点； 根结点只有 左子树；根结点只有右子树； 根结点既有左子树又有右子树。斜树所有结点都只有左子树的二叉树称为左斜树；所有结点都只有右子树的二叉树 称为右斜树；左斜树和右斜树统称为斜树。斜树的特点：每一层只有一个结点，即只有度为1和度为0的结点并且只 有一个叶子结点；斜树 的结点个数与其深度相同。满二叉树在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子都在 同一层上，这样的二叉树称为满二叉树。满二叉树