数据结构基础概念

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

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

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

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

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

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

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

8、1 和 top=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 中，下三角的元素 aiji>j 在数组 SA 中的下标 k 与 i、j 的关系是 k=i* i+1/2+j-1.下三角矩阵的压缩存储方法是将下三角中的元素按行存储非零 元素表示为三元组行号、列号、非零元素 。将稀疏矩阵的非零元素对应的三元组所构成的集合， 按行优先的顺序排列成一个 线性表，称为三元组表。三元组表有两种存储结构：顺序存储结构三元

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

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

14、为该结点的孩子，该结点称为其子树根结点的双亲。一颗二叉树的第i (i>=1)层最多有2A(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=ViO ,Vim=Vq ,其中，(Vij-1 ,Vij) E (1<=jv=m );如果 G 是有向图，那么<Vij-1,Vij > E(1<=j<=m).路径上边的数目称为路径长度。第一个 顶点和最后一个顶点相同的路径称为回路。在无向图中，假设任意顶点 Vi和Vj (i工j )之间有路 径，那么称该图是连通图，非连通图的极通子图称为连 通分量；在有向图中，对任意顶点 Vi和Vj (i工j ), 假设从顶点 Vi 到 Vj 和顶点 Vj 到 Vi 均有路径，那么称该 有

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