数据结构-顺序存储与算法分析

需积分: 9 0 下载量 132 浏览量 更新于2024-08-22 收藏 705KB PPT 举报
"顺序存储结构的算法-严蔚敏数据结构ppt" 在计算机科学中,数据结构是关于数据的组织方式的关键概念,它涉及到如何高效地存储和访问数据。在这个背景下,严蔚敏教授的数据结构课程是深入理解这一主题的重要资源。在提供的描述中,提到了一个创建二叉树的算法——`CreateBiTree`,这是数据结构中的一个常见操作,特别是对于理解和操作树形数据结构至关重要。 1. **数据结构**: 数据结构是组织数据的方式,它可以是简单的线性结构如数组或链表,也可以是更复杂的非线性结构如树、图等。在上述例子中,电话号码查询系统和图书馆书目检索系统都是数据结构问题,因为它们涉及如何有效地存储和检索信息。数据结构的选择直接影响到程序的性能和复杂性。 2. **二叉树**: 二叉树是数据结构中的一种特殊类型,每个节点最多有两个子节点,通常分为左子节点和右子节点。在提供的代码中,`CreateBiTree` 函数用于动态创建一个二叉树。函数通过递归读取字符并分配节点来构建树,`T->data=ch` 分配当前节点的值,`CreateBiTree(T->lchild)` 和 `CreateBiTree(T->rchildd)` 分别递归创建左子树和右子树。 3. **算法**: 算法是一系列解决问题或执行任务的明确指令。在数据结构中,算法常用于操作数据结构,如插入、删除、查找等。在 `CreateBiTree` 示例中,算法设计要求在内存中构建一棵二叉树,同时考虑到存储空间的需求和效率。 4. **算法效率的度量**: 在 `1.4.3` 部分提到,算法效率通常通过时间复杂度和空间复杂度来衡量。时间复杂度描述了算法执行所需的时间与输入大小的关系,而空间复杂度则关注算法在运行过程中占用的内存空间。 5. **抽象数据类型(ADT)**: ADT 是一种高级编程概念,它定义了一组操作以及这些操作如何作用于一组数据。例如,二叉树是一个ADT,它包含插入、删除和查找等操作。ADT 的实现可以是具体的,如顺序存储或链式存储。 6. **顺序存储结构**: 在数据结构中,顺序存储结构是指数据元素在内存中按照它们在逻辑上的顺序连续存储。常见的顺序存储结构有数组和线性表。对于二叉树,顺序存储通常用于完全二叉树,可以通过数组来实现,但通常我们使用链接结构(即链表)来表示二叉树,因为它允许更灵活的插入和删除操作。 这段摘要涵盖了数据结构的基本概念,包括数据结构的定义、二叉树的创建算法、算法效率的考量以及抽象数据类型。这些知识点在软件开发中非常重要,因为它们直接影响到程序的性能和可维护性。