|
|
|
|
|
|
|
|
|
在数据结构中，线性结构通常称为线性表，它是最简单、最常见的一种数据结构。通常线性表是由n个相同数据类型的节点组成的有限序列。其特点是在数据元素的非空有限集合中，存在唯一的一个被称为"第一个"的数据元素；存在唯一的一个被称为"最后一个"的数据元素；除第一个之外，集合中的每个数据元素均有且仅有一个前驱；除最后一个之外，集合中的每个数据元素均有且仅有一个后继。
|
|
|
|
一个由n个节点e0, e1,…, en-1组成的线性表记为（e0, e1, …, en-1）。线性表的节点个数称为线性表的长度，长度为0的线性表称为空的线性表，简称空表。对于非空线性表，e0是线性表的第一节点，en-1是线性表的最后一个节点。线性表的节点构成了一个序列，对序列中两个相邻节点ei和ei+1，称前者为后者的前驱节点，后者是前者的后继节点。
|
|
|
|
|
|
线性表最重要的性质是线性表中节点的相对位置是确定的。线性表的节点也称为表元，
或称为记录，要求线性表的节点一定是同一类型的数据。线性表的节点可由若干个成分组成，其中唯一标识表元的成分称为关键字，简称键。
|
|
|
|
|
|
|
|
.Initiate（L）：初始化操作，对线性表中的各个元素的初始值进行初始化。
|
|
|
|
.Length（L）：求长度函数，线性表的长度就是线性表中元素的个数。
|
|
|
|
.Get（L, i）：取元素函数，取线性表中的一个元素。
|
|
|
|
.Prior（L, elm）：求前驱函数，给定一个线性表元素，求出其前一个元素。
|
|
|
|
.Next（L, elm）：求后继函数，给定一个线性表元素，求出其后一个元素。
|
|
|
|
.Locate（L, x）：定位函数，根据给定的值，在线性表中找到并返回其位置。
|
|
|
|
.Insert（L, i, b）：插入操作，给定一个元素后，将其插在线性表的某个位置。
|
|
|
|
.Delete（L, i）：删除操作，删除给定位置或值的元素。
|
|
|
|
|
|
有多种存储方式能将线性表存储在计算机内，其中最常用的是顺序存储和链式存储。根据存储方式的不同，其上述基本操作的实现也不一样。
|
|
|
|
（1）顺序存储：顺序存储是最简单的存储方式，其特点是逻辑关系上相邻的两个元素在物理位置上也相邻。通常使用一个足够大的数组，从数组的第一个元素开始，将线性表的节点依次存储在数组中。顺序存储方式的优点是能直接访问线性表中的任意节点。线性表的第i个元素a［i］的存储位置可以使用以下公式求得：Loc（ai）=Loc（aI）+（i-1）×1。式中Loc（ai）是线性表的第一个元素a1的存储位置，通常称作线性表的起始位置或基地址。顺序存储的缺点是：线性表的大小固定，浪费大量的存储空间，不利于节点的增加和减少；执行线性表的插入和删除操作要移动其他元素，不够方便。
|
|
|
|
（2）链式存储：链式存储是用链表来存储线性表。其特点是：每个链表都有一个头指针，整个链表的存取必须从头指针开始，头指针指向第一个数据元素的位置，最后的节点指针为空。当链表为空时，头指针为空值。当链表非空时，头指针指向第一个节点。链式存储的缺点是：由于要存储地址指针，所以浪费空间；直接访问节点不方便。
|
|
|
|
链式存储有单链表（线性链表）、循环链表、双向链表。
|
|
|
|
.单链表从链表的第一个表元开始，将线性表的节点依次存储在链表的各表元中。链表的每个表元除要存储线性表节点信息外，还要存储其后继节点的指针。
|
|
|
|
.循环链表是单链表的变形，其特点是表中最后一个节点的指针域指向头节点，整个链表形成一个环。因此，从表中的任意一个节点出发都可以找到表中的其他节点。循环链表中，从头指针开始遍历的结束条件不是节点的指针是否为空，而是是否等于头指针。为简化操作，循环链表中往往加入表头节点。
|
|
|
|
.双向链表的节点中有两个指针域，一个指向直接后继，另一个指向直接前驱，克服了单链表的单向性缺点。
|
|
|
|
|
|
|
|
队列（Queue）是一种先进先出（FIFO）的线性表，队列是只允许在一端进行插入操作，另一端进行删除操作的线性表。允许删除的那一端称为队首（Front），允许插入的那一端称为队尾（Rear）。通常称队列的节点的插入为进队，队列的节点的删除为出队。若有队列Q=（q0, q1, …, qn-1），则q0称为队首节点，qn-1称为队尾节点。
|
|
|
|
|
|
可以用顺序存储线性表来表示队列，也可以用链表来实现，用链表实现的队列称为链队列。
|
|
|
|
|
|
优先级队列是一种不同于先进先出队列的另一种队列，每次出队的是队列中最高优先级的元素。
|
|
|
|
|
|
|
|
栈（Stack）是限定仅在表尾进行插入或删除操作的线性表。表尾端称为栈顶（Top），表头端称为栈底（Bottom）。故栈是后进先出（LIFO）的线性表。
|
|
|
|
若有桟S=（S0, S1, …, Sn-1），则S0称为栈底节点，Sn-1称为栈顶节点。通常称桟的节点的插入为进栈（Push），栈的节点的删除为出栈（Pop）。
|
|
|
|
|
|
|
|
.顺序栈即栈的顺序存储结构，是利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时设指针top指示栈顶元素的当前位置。
|
|
|
|
.链栈即栈的链式存储结构，链表的第一个元素是栈顶元素，链表的末尾是栈底节点，链表的头指针就是栈顶指针，栈顶指针为空则是空栈。
|
|
|
|
|
|
|
n个元素的序列{k1, k2, …, kn｝当且仅当满足以下的关系式时才称之为堆： 或 ，并相应地称为小顶堆或大顶堆。
|
|
|
|
|
|
判断堆的办法是把序列看成一棵完全二叉树，若树中所有非终端节点的值均不大于（或不小于）其左右孩子的节点的值，则该序列为堆。
|
|
|
|
|
|
堆的典型应用是堆排序。堆排序首先要根据待排序记录的关键字建立初始堆，其方法是：将待排序的关键字按层序遍历方式分放到一棵完全二叉树的各个节点中，显然所有i>［n/2］的节点ki都没有子节点，以这样的ki为根的子树已经是堆，因此初始堆可从完全二叉树的第（i=［n/2］）个节点开始，通过调整，逐步使以k[n/2]， k［n/2]-1, …, k2, k1为根的子树满足堆的定义。
|
|
|
|
|
|
|
|
数组是最常用的数据结构之一，在程序中，数组常用来实现顺序存储的线性表。数组由固定个数的元素组成，全部元素的类型相同，元素依次顺序存储。每个元素对应一个下标，数组元素按数组名和元素的下标引用，引用数组元素的下标个数称为数组的维数。
|
|
|
|
在C语言中，n个元素的数组中，第一个元素的下标为0，最后一个元素的下标为n-1。
|
|
|
|
|
|
（1）静态数组是指数组的存储空间分配是在使用之前进行，在程序运行中不能改变，不利于数组的扩展。
|
|
|
|
（2）动态数组是在程序执行中进行数组存储空间的分配。
|
|
|
|
动态数组一般采用链式存储结构，而静态数组一般采用顺序存储结构。
|
|
|
|
数组元素可以是任意类型，当元素本身又是数组时，就构成了多维数组。多维数组是一维数组的推广，最常用的是二维数组。在C语言中，数组元素按行优先顺序存放。
|
|
|
|
一般用多维数组表示矩阵，矩阵的类型有对称矩阵、三角矩阵（下三角矩阵或上三角矩阵）和对角矩阵。
|
|
|
|
稀疏矩阵的存储：用顺序存储结构的三元数组对稀疏矩阵进行存储，分别记录行、列和值。
|
|
|
|
|
|
|
|
树型结构是一类重要的非线性数据结构，其中以树和二叉树最为常用。
|
|
|
|
树是由一个或多个节点组成的有限集T，它满足以下两个条件：有一个特定的节点称为根节点；其余的节点分成m个互不相交的有限集T1, T2, …, Tm，其中每个集又都是一棵树，称T1, T2, …, Tm为根节点的子树。
|
|
|
|
可见树的定义是递归的，即一棵树由子树构成，子树又由更小的子树构成。
|
|
|
|
|
|
|
|
|
|
|
|
若将树中节点的各子树看成是从左到右具有次序的，即不能交换，则称该树为有序树，否则称为无序树。
|
|
|
|
|
|
在应用树结构时，常要求按某种次序获得树中全部节点的信息，这可通过树的遍历操作来实现，常用的遍历方法如下。
|
|
|
|
.前序：先访问根节点，然后从左到右遍历根节点的各棵子树。
|
|
|
|
.后序：先从左到右遍历根节点的各棵子树，然后访问根节点。
|
|
|
|
.层序：先访问处于1层上的节点，然后从左到右依次访问处于2层、3层上的节点，即从上到下、从左到右逐层访问树中各层上的节点。
|
|
|
|
|
|
|
|
二叉树是n个节点的有限集合，它或者是空树，或者是由一个根节点及两棵不相交的、分别称为左子树和右子树的树所组成。
|
|
|
|
|
|
二叉树的节点的子树要区分左子树和右子树，即使在节点只有一棵子树的情况下也要明确指出该子树是左子树还是右子树；另外，二叉树的节点的最大度为2，而树中不限制节点的度数。
|
|
|
|
|
|
.在二叉树的第i层至多有2i-1个节点（根节点为1层）。
|
|
|
|
|
|
.对任何一棵二叉树T，如果其终端节点数为n0，度为2的节点数为n2，则n0=n2+1。
|
|
|
|
.具有n个节点的完全二叉树的深度为［log2n」+1。
|
|
|
|
|
|
|
|
.完全二叉树：除了最外层，其余层上的节点数目都达到最大值，而第h层上的节点集中存放在左子树中。
|
|
|
|
.平衡二叉树（AVL树）：二叉排序树的一种，其检索效率介于最优二叉树（Huffman树）和一般二叉排序树之间，要求任何一个节点的左右子树的高度差都不大于1。
|
|
|
|
.二叉查找树：又称二叉排序树，左子树的值都小于根节点的值，而右子树的值都大于根节点的值，同时左、右子树都是查找树。
|
|
|
|
|
|
二叉树的遍历是非常重要的操作，有前序、中序、后序和层序遍历，要求熟练掌握。
|
|
|
|
|
|
二叉树因具有递归性质，因此能很方便地用递归实现遍历，借助栈同样可以用非递归方式实现遍历。注意体会栈的使用，在此采用不带头节点的单链表作为栈的存储结构，Stop是栈顶指针，注意出栈／入栈操作。
|
|
|
|
|
|
|
|
|
|
|
|
Huffman树又称为最优二叉树，是一类带权路径长度最短的树。Huffman树是指权值为w1, w2, …, wn的n个叶子节点的二叉树中带权路径长度最小的二叉树。
|
|
|
|
|
|
（1）路径是指从树中一个节点到另一个节点之间的分支构成的这两个节点之间的路径，路径上的分支数目就称为路径长度。
|
|
|
|
（2）树的路径长度是从树根到每一个叶子之间的路径长度之和。
|
|
|
（3）节点的带权路径长度为从该节点到树根之间的路径长度与该节点权的乘积。树的路径长度为树中所有节点的带权路径长度之和，记为 ，其中n为带权叶子节点数目；wk为叶子节点的权值；1k为叶子节点到根的路径长度。
|
|
|
|
|
|
|
|
（2）选两个权值最小的节点构造一棵新的二叉树，新的二叉树的根节点的权值就是两个子节点权值之和。
|
|
|
|
（3）从n个节点中删除刚才使用的两个节点，同时将新产生的二叉树的根节点放在节点集合中。
|
|
|
|
（4）重复步骤（2）、步骤（3），直到只有一棵树为止。
|
|
|
|
|
|
Huffman树的应用是Huffman编码，在编码过程中要考虑两个问题，一是数据的最小冗余编码问题，二是译码的唯一性问题。在实际应用中，各个编码字符的出现频率不同，希望用最短的编码来表示出现频率大的字符，而用较长的编码表示出现频率较小的字符，从而使整个编码序列的总长度最小，这就是最小冗余编码问题。Huffman编码就解决了这个问题，根据权值或概率的大小来构建Huffman树，然后左分支用0表示，而右分支用1表示，这样就形成了编码序列。
|
|
|
|
|
|
图是一种较线性表和树更为复杂的数据结构。在图形结构中，节点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关。
|
|
|
