《数据结构》基本概念

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

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

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

3、顺序存储结构的基本思想是：用一组连续连续的存储单元依次依次存储数据元素，数据元素之间的逻辑关系是 由元素的存储位置来表示的。 链接存储结构的基本思想是：用一组任意任意的存储单元存储数据元素，数据元素之间的逻辑关系是用指 针来表示的。 注意：存储结构除了存储数据元素之外，必须存储数据元素之间的逻辑关系。 抽象数据类型抽象数据类型 抽象数据类型是一个数据结构以及定义在该结构上的一组操作的总称。抽象数据类型提供了使用和实 现两个不同的视图，实现了封装和信息隐藏。 算法的定义算法的定义 通俗地讲，算法是解决问题的方法，严格地说，算法是对特定问题求解步骤的一种描述，是指令的有 限序列。 算法的特性算法的

4、特性 输入：一个算法有零个或多个输入（即算法可以没有输入），这些输入通常取自于某个特定的对 象集合。 输出：一个算法有一个或多个输出（即算法必须要有输出），通常输出与输入之间有着某种特定 的关系。 2 有穷性：一个算法必须总是（对任何合法的输入）在执行有穷步之后结束，且每一步都在有穷时 间内完成。 确定性：算法中的每一条指令必须有确切的含义，不存在二义性。并且，在任何条件下，对于相 同的输入只能得到相同的输出。 可行性：算法描述的操作可以通过已经实现的基本操作执行有限次来实现。 线性表的定义线性表的定义 线性表简称表，是零个或多个具有相同类型的数据元素的有限序列。数据元素的个数称为线性表的长长

5、 度度，长度等于零时称为空表。 线性表的逻辑关系线性表的逻辑关系 在一个非空表 L(a1，a2，an)中，任意一对相邻的数据元素 ai-1和 ai之间（1in）存在序 偶关系（ai-1，ai），且 ai-1称为 ai的前驱，ai称为 ai-1的后继。在这个序列中，a1无前驱，an无后继，其 它每个元素有且仅有一个前驱和一个后继。 顺序表的存储结构定义顺序表的存储结构定义 用 MaxSize 表示数组的长度，顺序表的存储结构定义如下： #define MaxSize 100 typedef struct ElemType dataMaxSize; / ElemType 表示不确定的数据类型 in

6、t length; /length 表示线性表的长度 SeqList; 顺序表是随机存取结构顺序表是随机存取结构 设顺序表的每个元素占用 c 个存储单元，则第 i 个元素的存储地址为： LOC(ai)= LOC(a1)(i1)c 顺序表的优缺点顺序表的优缺点 顺序表利用了数组元素在物理位置上的邻接关系来表示线性表中数据元素之间的逻辑关系，这使得顺 序表具有下列优点： 无需为表示表中元素之间的逻辑关系而增加额外的存储空间； 可以快速地存取表中任一位置的元素（即随机存取）。 同时，顺序表也具有下列缺点： 插入和删除操作需移动大量元素。在顺序表上做插入和删除操作，等概率情况下，平均要移动表 中一半的

7、元素。 表的容量难以确定。由于数组的长度必须事先确定，因此，当线性表的长度变化较大时，难以确 定合适的存储规模。 造成存储空间的“碎片”。数组要求占用连续的存储空间，即使存储单元数超过所需的数目，如 果不连续也不能使用，造成存储空间的“碎片”现象。 单链表的存储结构定义单链表的存储结构定义 单链表的存储结构定义如下： Struct Node ElemType data; / ElemType 表示不确定的数据类型 struct Node *next; *first; /first 为单链表的头指针 双链表的存储结构定义双链表的存储结构定义 双链表存储结构定义如下： 3 struct DulNo

8、de ElemType data; / ElemType 表示不确定的数据类型 struct DulNode *prior, *next; / prior 为前驱指针域，next 为后继指针域 *first; /first 表示双链表的头指针 栈的定义栈的定义 栈栈是限定仅在表尾进行插入和删除操作的线性表。允许插入和删除的一端称为栈顶，另一端称为栈底， 不含任何数据元素的栈称为空栈。 栈的操作特性栈的操作特性 栈的操作具有后进先出后进先出的特性。 队列的定义队列的定义 队列队列是只允许在一端进行插入操作，而另一端进行删除操作的线性表。允许插入的一端称为队尾，允 许删除的一端称为队头。 队列的操

9、作特性队列的操作特性 队列的操作具有先进先出先进先出的特性。 循环队列中解决队空队满的判断条件循环队列中解决队空队满的判断条件 方法一：附设一个存储队列中元素个数的变量 num，当 num=0 时队空，当 num=QueueSize 时为队满； 方法二：修改队满条件，浪费一个元素空间，队满时数组中只有一个空闲单元；即队空的条件是 front=rear，队满的条件是(rear+1) % QueueSize=front，队列长度为(rear-front+QueueSize) % QueueSize。 方法三：设置标志 flag，当 front=rear 且 flag=0 时为队空，当 front=

10、rear 且 flag=1 时为队满。 串的定义串的定义 串串是零个或多个字符组成的有限序列。 空格串和空串的定义空格串和空串的定义 只包含空格的串称为空格串空格串。串中所包含的字符个数称为串的长度，长度为 0 的串称空串空串，记作 “ “。 串的比较串的比较 串的比较是通过组成串的字符之间的比较来进行的。 给定两个串： X=“x1x2xn“ Y=“y1y2ym“ 则当 n=m 且 x1=y1，xn=ym时，称 X=Y； 当下列条件之一成立时，称 XY： nm，且 xi=yi（i=1，2，n）； 存在某个 kmin(m，n)，使得 xi=yi（i=1，2，k-1），xkyk。 改进的模式匹配算

11、法中改进的模式匹配算法中 nextj的求法的求法 用 nextj表示 tj对应的 k 值（1jm），其定义如下： 数组的基本操作数组的基本操作 数组是一个具有固定格式和数量的数据集合，在数组上一般不能做插入、删除元素的操作。因此，在 数组中通常只有两种操作： 读取：给定一组下标，读取相应的数组元素； 0 j=1 max k | 1kj 且t1t2 tk -1 =tj-k+1tj-k+2 tj-1 1 其它情况 nextj= 4 修改：给定一组下标，存储或修改相应的数组元素。 二维数组的寻址二维数组的寻址 按行优先，设二维数组的行下标与列下标的范围分别为l1，h1与l2，h2，则任一元素 aij

12、的存储 地址可由下式确定： LOC(a ij)LOC(al1l2)(il1)(h2l21)(jl2)c 特殊矩阵的定义特殊矩阵的定义 特殊矩阵是指矩阵中有很多值相同的元素并且它们的分布有一定的规律。 矩阵压缩存储的基本思想矩阵压缩存储的基本思想 压缩存储的基本思想是： 为多个值相同的元素只分配一个存储空间； 对零元素不分配存储空间。 对称矩阵的压缩存储中：对称矩阵的压缩存储中：下三角元素 aij（ij）在一个数组 SA 中的下标为：k = i(i-1)/2 + j-1。上 三角中的元素 aij（ij），则访问和它对应的下三角中的元素 aji即可，即：k = j(j-1)/2 + i-1。 三角

13、矩阵的压缩存储中：三角矩阵的压缩存储中：下三角矩阵中任一元素 aij在一个数组 SA 中的下标 k 与 i、j 的对应关系为： 上三角矩阵元素 aij在 SA 中的下标为：k =(i-1)(2n-i+2)/2+(j-i)。 稀疏矩阵的压缩存储方式稀疏矩阵的压缩存储方式 三元组顺序表和十字链表 三元组的定义三元组的定义 struct element int row, col; ElemType item ; 广义表的定义广义表的定义 广义表广义表是 n（n0）个数据元素的有限序列。 表头表头 当广义表 LS 非空时，称第一个元素为 LS 的表头； 表尾表尾 称广义表 LS 中除去表头后其余元素组

14、成的广义表为 LS 的。 长度长度 广义表 LS 中的直接元素的个数称为 LS 的长度长度； 深度深度 广义表 LS 中括号的最大嵌套层数称为 LS 的深度深度。 树的定义树的定义 树树是 n（n0）个结点的有限集合。当 n0 时，称为空树；任意一棵非空树满足以下条件： 有且仅有一个特定的称为根根的结点； 当 n1 时，除根结点之外的其余结点被分成 m（m0）个互不相交互不相交的有限集合 T1，T2，Tm， 其中每个集合又是一棵树，并称为这个根结点的子树。 k= i(i-1)/2 + j-1 当 ij n(n1)/2 当 ij 5 结点的度、树的度结点的度、树的度 某结点所拥有的子树的个数称为

15、该结点的度；树中各结点度的最大值称为该树的度。 叶子结点、分支结点叶子结点、分支结点 度为 0 的结点称为叶子结点，也称为终端结点；度不为 0 的结点称为分支结点，也称为非终端结点。 孩子结点、双亲结点、兄弟结点孩子结点、双亲结点、兄弟结点 某结点的子树的根结点称为该结点的孩子结点；反之，该结点称为其孩子结点的双亲 路径、路径长度路径、路径长度 如果树的结点序列 n1, n2, , nk满足如下关系：结点 ni是结点 ni+1的双亲（1ik），则把 n1, n2, , nk称为一条由 n1至 nk的路径；路径上经过的边的个数称为路径长度。 祖先、子孙祖先、子孙 如果从结点 x 到结点 y 有一条路径，那么 x 就称为 y 的祖先，而 y 称为 x 的子孙。 注意：某结点子树中的任一结点都是该结点的子孙。 结点的层数、树的深度（高度）结点的层数、树的深度（高度） 规定根结点的层数为 1，对其余任何结点，若某结点在第 k 层，则其孩子结点在第 k+1 层；树中所有 结点的最大层数称为树的深度，也称为树的高度。 二叉树的定义二叉树的定义 二叉树二叉树是 n（n0）个结点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根结点和 两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。 二叉树的特点二叉树的特点 二叉树的特点是： 每个结点最多