数据结构原理与分析--01343--18日下-复习资料.doc

"数据结构原理与分析" 本文档主要讨论了数据结构的原理与分析，涵盖了线性表、栈、队列、二叉树、图等数据结构的概念和操作。下面是本文档中的关键知识点： 1. 线性表：线性表是一个有限序列，具有 n 个数据元素。邻接表的存储结构类似于二叉树的深度优先遍历。 2. 栈：栈是一种后进先出（LIFO）的数据结构。对于栈操作数据的原则是后进先出。 3. 队列：队列是一种先进先出（FIFO）的数据结构。在一棵高度为 h 的完全二叉树中，所含结点个数不小于 2^h。 4. 二叉树：二叉树是一种特殊的树形结构。具有 n 个顶点的有向无环图最多可包含有向边的条数是 n(n-1)/2。某二叉树的前序和后序序列正好相反，则该二叉树一定是一个高度等于其结点数的二叉树。 5. 图：图是一种非线性数据结构。具有 n 个顶点的有向图最多可包含有向边的条数是 n(n-1)。在一棵高度为 h 的完全二叉树中，所含结点个数不小于 2^h。 6. 排序方法：排序方法中，从未排序序列中依次取出元素与已排序序列中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为插入排序。 7. 串：串是任意有限个字符构成的序列。 8. 查找方法：对有 n 个记录的表按记录键值有序建立二叉查找树，在这种情况下，其平均查找长度的量级为 O(n)。 9. 链表：设长度为 n 的链队列用单循环链表表示，假设只设头指针，则入队操作的时间复杂度为 O(n)。 10. 树的遍历：树的遍历方法有深度优先遍历和广度优先遍历两种。邻接表的存储结构以下图的深度优先遍历类似于二叉树的深度优先遍历。 11. 二叉树的性质：堆的形状是一棵完全二叉树。在一棵具有 n 个结点的二叉树中，所有结点的空子树个数等于 n+1。 12. 图的遍历：图的遍历方法有深度优先遍历和广度优先遍历两种。邻接表的存储结构以下图的广度优先遍历类似于二叉树的广度优先遍历。 13. 树的应用：树的应用有查找、排序、图遍历等方面。 14. 数据结构的分析：数据结构的分析包括时间复杂度和空间复杂度两个方面。 本文档涵盖了数据结构的基本概念、操作和应用，旨在帮助读者深入理解数据结构的原理与分析。