数据结构导论-概念

一、 概念

  • 数据： 所有被计算机存储、处理的对象。
  • 数据元素： 数据的基本单位，是运算的基本单位，尝尝又简称为元素。
  • 数据项： 数据元素常常还可以分为若干个数据项，数据的不可分割的最小标识单位。

二、数据结构分类

1. 逻辑结构

数据的逻辑结构：指数据元素之间的结构关系，与数据元素本身的形式，内容，相对位置，个数无关。
数据的四类逻辑结构
- 集合： 任意两个节点之间都没 有邻接关系，组织形式松散
- 线性结构： 节点按逻辑关系依次排列形成一条”锁链”
- 树形结构： 具有分支、层次特性，上层的节点可以和下层多个节点相邻接，但下层节点只能和上层的一个节点相邻接
- 图结构： 任何两个节点都可以相邻接，**最复杂 **

2. 存储结构

数据的存储结构：也称为存储结构，指数据结构在机内的表示，数据的逻辑结构在计算机的实现
存储结构的主要部分

  • 存储结点（每个存储结点存放一个数据元素）
  • 数据元素之间关联方式的表示

三、 存储结构种类

1. 顺序存储结构

将元素存储到一片连续的存储区，利用节点在存储器中的相对位置来表示数据元素的逻辑关系

  • 特点：
    a. 预先分配好长度，需要预估存储数据需要的存储量
    b. 插入和删除需要移动其他元素
    c. 存取快捷，是随机存储结构

2. 链式存储结构

是给节点附加一个指针字段，指出其后继节点的位置，即存放节点的存储单元为两部分：数组项和指针项，每个指针指向一个与本节点有逻辑关系的节点，用指针表示数据元素之间的逻辑关系

  • 特点：
    a. 动态分配，不需要预先确定内存分配
    b. 插入和删除不需要移动其他元素
    c. 非随机存储结构

3. 索引存储方式

借助索引表中的索引指示各存储结点的存储位置

4. 散列存储方式

用散列函数只是各结点的存储位置

四、 运算

运算是指某种逻辑结构上施加的操作，即对逻辑结构的加工。

线性表、栈和队列中的元素具有相同的逻辑结构（即线性结构），但有不同的运算集，它们是不同的数据结构。
运算的实现是指改运算的算法，一个算法规定了求解给定问题所需的处理步骤及其执行顺序，使得给定问题能在有限时间内被求解。

评价算法好坏的因为包括一下几个方面:

  • 1.正确性
  • 2.易读性
  • 3.健壮性
  • 4.时空性

时空性 通常考虑两个度量：

  • 1.时间复杂度：算法运行时需要的总步数，通常是问规模的函数

    常见的时间复杂度按数量级递增配列依次为：

      1. 常数O(1)
      1. 对数阶($\log_{2}n$)
      1. 线性阶O(n)
      1. 线性对数阶O(n$\log_{2}n$)
      1. 平方阶O($n^{2}$)
      1. 多项式阶O($n^{c}$)
      1. 指数阶O($C^{n}$)

我们将时间复杂度记为输入数据规模n的函数，若求解问题需要执行$n^{2}$次操作则，记作O($n^{2}$)

    1. 空间复杂度：算法执行时所占用的存储空间，通常是问题规模的函数

    空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度
    一个算法在执行期间所需要的存储空间量包括以下部分：

    • 程序代码所占用的空间
    • 输出数据所占用的空间
    • 辅助变量所占用的空间

估算算法空间复杂度时，一般只分析辅助变量所占用的空间