数据结构 | 第1章 绪论

内容纲要

@[toc]

引言

为了编写出“好”的程序,必须分析待处理的对象的特性各处理对象之间的关系,是“数据结构”形成和发展的背景。

什么是数据结构

  • 计算机解决具体问题的大致步骤
    1. 从具体问题抽象出适当数学模型
    2. 设计求解算法
    3. 编写程序
    4. 测试调整得到最终结果

计算机处理的对象之间通常存在一种最简单的线性关系,这类数学模型称为线性数据结构
“树”是某些非数值计算问题的数学模型,也是一种数据结构。
类似交通、道路问题的数学模型是一种“图”的数据结构。

因此,数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象及它们之间的关系和操作等的学科。同时,数据结构是实现编译程序、操作系统、数据库系统及其他系统程序和大型应用程序重要基础

基本概念术语

  1. 数据(data element)是所有能输入到计算机中被计算机程序处理的符号的总称。如,数值分析方法解代数方程的处理对象是整数和实数编译程序或文字处理程序的处理对象是字符串

  2. 数据元素是数据的基本单位,在计算机程序中通常作为一个整体考虑和处理。其中,数据项是数据的不可分割的最小单位

  3. 数据对象性质相同的数据元素的集合,是数据的一个子集

  4. 数据结构相互之间存在一种或多种特定关系的数据元素的集合

    数据结构的形式定义为:数据结构是一个二元组 Data_Structure = (D, S)
    其中:D是数据元素的有限集,S是D上关系的有限集

  5. 数学模型结构定义中的“关系”描述的是数据元素之间的的逻辑关系,称为数据的逻辑结构

  6. 数据结构在计算机中的表示(映像)称为数据的物理结构或存储结构

  7. 计算机中,用一个由若干位组合形成的一个位串表示一个数据元素,称这个位串为元素或结点

  8. 当数据元素由若干数据项组成时,位串中对应于各个数据项的子位串称为数据域

  9. 数据元素之间的关系有两种表示方法:顺序映像非顺序映像,并得到两种存储结构:顺序存储结构链式存储结构。顺序映像的特点是借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系;非顺序映像的特点是借助元素存储地址的指针表示数据元素之间的逻辑关系
    任何一个算法的设计取决于选定的逻辑结构,算法的实现依赖于采用的存储结构

  10. 数据类型是一个值的集合和定义在值集上的一组操作的总称。如,C语言中的整型变量,其值集为某个区间上的整数,操作为加减乘除和取模等运算

    从硬件角度看,数据类型是作为解释计算机内存中信息含义的一种手段;从用户来说,其实现了信息的屏蔽,将一切用户不必了解的细节都封装在类型中

  11. 抽象数据类型(Abstract Data Type, ADT)是一个数学模型及定义在其上的一组操作

抽象数据类型的表示与实现

  • 形式定义
    抽象数据类型可用(D, S, P)三元组表示,
    其中:D是数据对象;S是D上的关系集;P是对D的基本操作集

  • 定义格式

    // 数据对象和数据关系的定义用伪代码描述
    ADT 抽象数据类型名
    {
            数据对象: <数据对象的定义>
            数据关系: <数据关系的定义>
            基本操作: <基本操作的定义>
    }
    ADT 抽象数据类型名
  • 定义举例:Circle的定义

    ADT 抽象数据类型名
    {
            Data
                数据对象的定义
                数据元素之间逻辑关系的定义
            Operation
                操作1
                    初始条件
                    操作结果描述
                操作2
                    ...
                操作n
    }
    ADT 抽象数据类型名
    ADT Circle
    {
            数据对象:D = { r, x, y | r, x, y均为实数 }
            数据关系:R = { <r, x, y> | r为半径,<x, y>为圆心坐标 }
            基本操作:
            Circle(&C, r, x, y)
                操作结果:构造一个圆
            double Area(C)
                初始条件:圆已存在
                操作结果:计算面积
            double Circumference(C)
                初始条件:圆已存在
                操作结果:计算周长
    }
    ADT Circle
  • 概念小结

算法和算法分析

什么是算法

  • 算法是对特定问题求解步骤的一种描述,是指令的有限序列

算法的特性

  1. 有穷性
  2. 确定性
  3. 可行性
  4. 输入
  5. 输出

算法设计的要求

  1. 正确性
  2. 可读性
  3. 健壮性
  4. 高效性

    健壮性:

    • 输入非法数据时,算法恰当的作出反应或进行处理,而不是产生莫名其妙的输出结果
    • 处理出错的方法,不应是中断程序的执行,应是返回一个表示错误或错误性质的值,以便在更高的抽象层次上处理

算法效率的度量

  • 度量方法
    1. 事后统计方法
    2. 事前分析估算方法

算法所耗费的时间定义为该算法中每条语句的频度之和频度是该语句重复执行的次数。
算法运行时间 = ∑每条语句的执行次数(语句频度) × 该语句执行一次所需时间

  • 示例,两个n × n矩阵相乘算法:
    // 时间消耗为T(n) = 2n^3 + 3n^2 + 2n + 1
    for (i = 1; i <= n; i++) // n + 1次
    for (j = 1; i <= n; j++) // n(n + 1)次
    {
        c[i][j] = 0;    // n * n次
        for (k = 0; k < n; k++)  // n * n * (n + 1)次
            c[i][j] = c[i][j] + a[i][k] * b[k][j];  // n * n * n次
    }

算法的时间复杂度

  • 算法中基本语句重复执行的次数问题规模n的某个函数f(n),算法的时间量度记作:T(n) = O(f(n))

    n越大算法的执行时间越长

    • 排序:n为记录数
    • 矩阵:n为矩阵的阶数
    • 多项式:n为多项式的项数
    • 集合:n为元素个数
    • 树:n为树的节点个数
    • 图:n为图的顶点数或边数
  • 分析的基本方法

    1. 找出语句频度最大的那条语句作为基本语句
    2. 计算基本语句的频度得到问题规模n的某个函数f(n)
    3. 取其数量级符号"O"表示
      // T(n) = O(n^2)
      x = y = 0;
      for (int k = 0; k < n; k++)
      x++;
      for (int i = 0; i < n; i++)
      for (int j = 0; j < n; j++)  // f(n) = n(n + 1)
      y++;
  • 对于复杂的算法,可以将其分成几个容易估算的部分,然后利用加法法则和乘法法则,计算时间复杂度:

    1. 加法法则
      T(n) = T1(n) + T2(n) = O(f(n)) + O(g(n)) = O(max(f(n), g(n)))
    2. 乘法法则
      T(n) = T1(n) × T2(n) = O(f(n)) × O(g(n)) = O(f(n) × g(n))
  • 时间复杂度T(n)按数量级递增顺序:

常数阶对数阶线性阶线性对数阶平方阶...K次方阶指数阶
O(1)O(log2(n))O(n)O(nlog2(n))O(n^2)O(n^k)O(2^n)

算法的空间复杂度

  • 算法所需存储空间的度量,记作:S(n) = O(f(n)),n为问题的规模

示例:将一维数组a中的n个数逆序存放到原数组中

// 算法1 S(n) = O(1)
for (i = 0; i < n / 2; i++)
{
    t = a[i];
    a[i] = a[n - i - 1];
    a[n - i - 1] = t;
}
// 算法2 S(n) = O(n)
for (i = 0; i < n; i++)
    b[i] = a[n - i - 1];
for (i = 0; i < n; i++)
    a[i] = b[i];

留下评论

您的电子邮箱地址不会被公开。