数据结构基础概念

1、第一章 绪论程序设计的一般过程是“问题想法算法程序” ，其实质是数据表示和数据处理。数据结构是研究非数值问题中计算机的操作对象以及它们之间关系和操作的学科。数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。数据项是数据的最小单位，数据元素是讨论数据结构时涉及的最小数据单位。从逻辑关系上讲， 数据结构主要分为集合， 线性结构，树结构，图结构。数据的内存结构主要有顺序存储结构，链接存储结构两种基本方法，不论哪种存储结构，都要存储两方面的内容 :数据元素和数据元素之间的关系。算法具有五个特性分别是有零个或多个输入，有一个或多个输出，有穷性，确定性，可行性。算法的描述方法通常有自

2、然语言，程序设计语言，流 程图和伪代码，其中伪代码被称为算法语言。在一般情况下，一个算法的时间复杂度是问题规模的 函数。顺序存储结构中数据元素之间的逻辑关系是由存储位 置表示的，链接存储结构中的数据元素之间的逻辑关 系是由指针表示的。可以用抽象数据类型定义一个完整的数据元素。算法指的是对特定问题求解步骤的一种描述，是指令 的有限序列。算法分析的目的是分析算法的效率以求改进，算法分 析的两个主要方面是数据复杂性和程序复杂性。时间复杂度要通过算法中基本语句执行次数的数量级 来确定。逻辑结构与数据元素本身的内容和形式无关。顺序存储结构的特点是用元素在存储器中的相对位置来表示数据元素之间的逻辑关系，链

3、接存储结构的特点是用指示元素存储地址的指针表示数据元素之间的逻辑关系。算法在发生非法操作时可以做出处理的特性称为健壮性。常见的算法时间复杂度用大O 记号表示为：常数阶0(1),对数阶O(log2n),线性阶O(n),平方阶O(nA2), 指数阶0(2An)第二章 线性表对顺序表和单链表的比较要考虑时间性能和空间性能两个方面。作为一般规律，若线性表需频繁查找却很少进行插入和是删除操作，或其操作和“数据元素在线性表中的位置”密切相关时，宜采用顺序表作为存储结构；若线性表需频繁进行插入和删除操作，则宜采用单链表作为存储结构；当线性表元素个数变化较大或者未知时，最好使用单链表实现；若用户事先知道线性表

4、的大致长度， 使用顺序表的空间效率会更高。对于顺序表，在等概率情况下，插入和删除一个元素平均需移表长的一半个元素，具体移动元素的个数与表长和该元素在表中的位置有关。单链表中设头结点的作用是为了方便运算。一个具有 n 个结点的单链表，在指针 p 所指结点后插入一个新结点的时间复杂度为 O（ 1） ；在给定值为 x的结点后插入一个新结点的时间复杂度为 O （ n） 。可有一个尾指针唯一确定的链表有循环单链表，循环双链表，双链表。线性表的顺序存储是一种随机存取的存储结构，线性表的链接存储结构是一种顺序存取的存储结构。线性表采用链接存储时，其地址连续与否都可以。单循环链表的主要优点是从表中任一结点出发

5、都能扫描到整个链表。链表不具有的特点是可随机访问任一元素。若某线性表中最常用的操作是去取第 i 个元素和找第 i个元素的前趋，则采用顺序表存储节省时间。若链表中最常用的操作在最后一个结点之后插入一个结点和删除一个结点，则采用带尾指针的单循环链表存储方法最节省时间。若链表最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点，则采用循环双链表存储方法最节省时间。对于 n 个元素组成的线性表，建立一个有序单链表的时间复杂度是O (nA2).使用双链表存储线性表，其优点是可以更方便数据的插入和删除。顺序表的逻辑顺序和存储顺序一致，链表的逻辑顺序和存储顺序不一定一致。第三章 栈和队列栈是限定仅

6、在表尾进行插入和删除操作的线性表。栈中元素除了具有线性关系外， 还具有后进先出的特性。栈的顺序存储结构称为顺序栈，顺序栈本质上是顺序表的简化。通常把数组中下标为 0 的一端作为栈底，同时附设指针 top 指示栈顶元素在数组中的位置。实现顺序栈基本操作的算法的时间复杂度均为 O(1)栈的链接存储结构称为链栈，通常用单链表表示，并且不用附加头结点。链栈的插入和删除操作只需处理栈顶即开始结点的情况，其时间复杂度均为 O ( 1) 。队列时只允许在一端进行插入操作，而另一端进行删除操作的线性表。 队列中的元素除了具有线性关系外，还具有先进先出特性。顺序队列会出现假溢出问题，解决的办法是用首尾相接的顺序

7、存储结构，称为循环队列。在循环队列中， 凡是涉及队头及队尾指针的修改都需要将其求模。在循环队列中， 队空的判断条件是： 队头指针 = 队尾指针；再浪费一个存储单元的情况下，队满的判定条件是（队尾指针 +1） %数组长度=队头指针队列的链接存储结构称为链队列。链队列通常附设头结点，并设置队头指针指向头结点，队尾指针指向终端结点。链队列基本操作的实现本质上也是单链表操作的简化，插入只考虑在练队列的尾部进行，删除只考虑在链队列的头部进行，其时间复杂度均为 O（1） 。栈结构通常采用的两种存储结构是顺序存储结构和链接存储 （顺序栈和链栈） ， 其判定栈空的条件分别是栈顶指针 top=-1 和 top=

8、null ，其判定栈满的条件分别是栈顶指针 top 等于数组的长度和内存无可用空间。栈可作为实现递归函数调用的一种数据结构。栈和队列是两种特殊的线性表，栈的操作特性是后进先出，队列的操作特性是先进先出，栈和队列的主要区别在于对插入和删除操作限定的位置不同。循环队列是为了克服假溢出。数组 Q【 n 】用来表示一个循环队列， front 为队头元素的前一个位置， rear 为队尾元素的位置，计算队列中元素个数的计算公式为( rear-front+n) %n用循环链表表示的队列中，出队即是删除开始结点，这只需修改相应指针；入队即是在终端结点的后面插入一个结点，这需要从头指针开始查找终端结点的地址。设

9、计一个判别表达式中左右括号是否配对的算法，采用栈数据结构最佳。在解决计算机主机与打印机之间速度不匹配问题时通 常设置一个打印缓冲区，该缓冲区应该是一个队列结 构。栈和队列的主要区别在于插入删除运算的限定不一样。在栈满的情况下不能做进栈操作， 否则将产生 “上溢” 。对于栈和队列，无论它们采用顺序存储结构还是链接存储结构，进行插入和删除操作的时间复杂度都是O(1)。第四章 字符串和多维数组字符串是由 0 个或多个字符组成的有限序列。 只包含空格串的称为空格串，长度为 0 的称为空串。字符串的比较是通过组成串的字符之间的比较来进行的， 而字符见的大小关系是字符编码之间的大小关系。字符串有顺序存储结

10、构和链接存储结构， 在大多数语言中， 串的存储和基本操作的实现都是采用顺序存储给定主串 S 和模式 T ， 在主串 S 中寻找模式 T 的过程称为模式匹配。 BF 算法是一种带回溯的匹配算法， KMP 算法是一种不带回溯的算法数组是有类型相同的数据元素构成的有序集合， 其特点是结构中的元素本身可以具有某种结构，但属于同一数据类型。比如：一维数组可以看作一个线性表， 二维数组可以看作是线性表的线性表，以此类推，所以数组是线性表的推广。在数组中通常只有两种操： 存取和修改， 他们本质上只对应一种操作寻址由于数组一般不做插入和删除操作， 因此， 数组通常采用顺序存储结构。采用顺序存储结构存储二维数组

11、需要将二维数组映射到一维结构，常用的映射方法有两种：按行优先和按列优先。矩阵压缩存储的基本思想是： 为多个值相同的元素只分配一个存储空间；对0 元素不分配存储空间。对称矩阵压缩存储的基本方法是将下三角的元素按行优先存储到一维数组SA 中，下三角的元素aij (i>j) 在数组 SA 中的下标 k与 i、 j 的关系是 k=i* ( i+1 ) /2+j-1.下三角矩阵的压缩存储方法是将下三角中的元素按行存储非零元素表示为三元组（行号、列号、非零元素） 。将稀疏矩阵的非零元素对应的三元组所构成的集合， 按行优先的顺序排列成一个线性表，称为三元组表。三元组表有两种存储结构：顺序存储结构（三元

12、组顺序表）和链接存储结构（称为十字链表）字符串是一种特殊的线性表， 其特殊性体现在数据元素的类型是一个字符。数组通常只有两种运算： 存取和修改， 这决定了数组通常采用顺序存储结构来实现存储。设有两个串p和q,求q在p中首次出现的位置的运算称作模式匹配。将数组称为随机存取结构是因为对数组任一元素的存取时间是相等的数组是一种线型结构数组是一种定长的线型结构数组的基本操作有存取、修改、检索和排序等，没有插入和删除操作。对特殊矩阵采用压缩存储的目的主要是为了减少不必要的存储 空间。使用三元组存储稀疏矩阵的元素，有时并不能节省存储空间。稀疏矩阵压缩存储后，必会失去随机存取功能。树是 n（ n>=0

13、 ）个结点的有限集合。任意一颗非空数满足：1 .有且仅有一个特定的称为根的结点；2 .当 n>1 时，除根节点之外的其余结点被分成 m （ m>0 ）个互不相交的有限集合T1,T2,Tm,其中每个集合又是一颗树，并称为这个根结点的字数。树的存储结构有双亲表示法、孩子表示法、孩子双亲表示法、孩子兄弟表示法。二叉树的遍历方式： 前序遍历、 中序遍历、 后序遍历和层序遍历、二叉树有 5 中形态。树是 n（ n>=0 ）结点的有限集合，在一棵非空树中，有且仅有一个根结点，其余的借点分成 m（ m>0 ）个互不相交的集合，每个集合都是根结点的子树。树中某结点的个数称为该结点的度，

14、子树的根结点称为该结点的孩子，该结点称为其子树根结点的双亲。一颗二叉树的第i （i>=1）层最多有2人（i-1）个结点；一 棵树有n （n>0）个结点的满二叉树共有（n+1） /2个 叶子结点和（ n-1） /2 个非终端结点。设二叉树有 n 个结点，则其深度最多是n ，最少是【 log2n】 +1如果T 是由有序树T 转化而来的二叉树，那么 T 中结点的前序序列就是T 中结点的前序序列， T 中结点的后序序列就是T 中结点的中序序列。在二叉树的前序遍历序列中，任意一个结点均处在其子女的前面。由树转换成二叉树，其根结点的右子树总是空的。对于一棵具有n 个结点的树，其所有结点的度之和

15、为n-1.前序遍历和中序遍历结果相同的二叉树是根结点无左孩子的二叉树。第六章 图在无向图中，对于任意顶点 Vi 和 Vj ，若存在（ Vi ，Vj ） ， 则称顶点 Vi 和 Vj 互为邻接点。 在有向图中， 对 于任意顶点 Vi 和 Vj ，若存在弧 Vi ， Vj ，则称顶点Vj 是 Vi 的邻接点。含有 n 个顶点的无向完全图共有n* （n-1） /2 条边；含有n个顶点的有向完全图共有n* （n-1）条边。在无向图中，顶点 v 的度是指依附于该顶点的边的个数；在有向图中，顶点 v 的入度是指以该顶点为弧头的弧的个数，顶点 v 的出度是指以该顶点为弧尾的弧的个数。在图中，权通常是指对边赋

16、予的有意义的数量值，边上带权的图称为网或网图。在无向图G=(V,E)中，顶点Vp到Vq之间的路径是一 个顶点序列 Vp=Vi0 , Vi, Vim=Vq，其九(Vij-1 ,Vij) WE (l<=j<=m)；如果 G 是有向图，则 <Vij-1,Vij> C E(1<=j<=m).路径上边的数目称为路径长度。第一个 顶点和最后一个顶点相同的路径称为回路。在无向图中，若任意顶点 Vi和Vj (i wj )之间有路 径，则称该图是连通图，非连通图的极大连通子图称为连通分量；在有向图中，对任意顶点Vi和Vj (i wj ) ，若从顶点 Vi 到 Vj 和顶点 V

17、j 到 Vi 均有路径，则 称该有向图为强连通图，非强连通图的极大强连通子图称为强连通分量。连通图G的生成树是包含G中全部顶点的一个极小连 通子图。图的生成树可以在遍历过程中得到。图的遍历通常有深度优先遍历和广度优先遍历两种方式。图的深度优先遍历是以递归方式进行的，需用栈记载遍历路线；图的广度优先遍历是以层次方式进行的，需用队列保存已访问的顶点。为了在图的遍历过程中区分顶点是否已被访问，设置一个访问标志数组visitedn, 其初值为未被访问标志“ 0” ，如果某个顶点已被访问，则将该顶点的访问标志置为“ 1”图的存储结构有邻接矩阵，邻接表，十字链表，邻接多重表等。图的邻接矩阵存储用一个一维数组存储图中顶点的信息，用一个二维数组存储图中边的信息(邻接矩阵) ；图的邻接表存储由边表和顶点表组成，图中每个顶点的所有邻接点构成一个边表，所有边表的头指针和存储顶点信息的一维数组构成顶点表。最小生成树是无向连通网中代价最小的生成树。最小生成树具有MST14质，Prim算法和Kruskal算法是两 个利用MST4质构造最小生成树的经典算法。Prim算法的时间复杂度为 O (nA2),适用于求稠密网的最小生成树； Kruskal 算法的时间复杂度为 O(elog2e