Wx::

数据结构 - 前言

此系列文章将随《数据结构》 [1] 学习过程而记录其中经典(部分)算法;
此系列文章可能较长,在阅读过程中建议 打开目录 (点击左下角三横线小按钮即可显示目录);
持续更新至 2018.01 左右;


相关概念

此部分是基于此书而讲的有关数据结构、数据类型、算法等 描述方式 的阐述;
若非明确说明,则均与 C 语言中语法类似;


数据结构形式定义

数据结构是一个二元组:
Data_Structure = (D, S)

其中:
D:数据元素的有限集
S:D 上关系的有限集

例如:-brev-

“复数” 可取如下定义:
Complex = (C, R)

其中:
C 是含两个是熟的集合 {c1, c2};R = {P},而 P 是定义在集合 C 上的一种关系 {<c1, c2>},其中有序偶 <c1, c2> 表示 c1 是复数实部,c2 是虚部。

over


抽象数据类型

ADT 抽象数据类型名 {
    数据对象:<数据对象的定义>
    数据关系:<数据关系的定义>
    基本操作:<基本操作的定义>
}ADT 抽象数据类型名

其中:
<数据对象的定义> 和 <数据关系的定义>:

可见上述 “数据结构” 部分;

<基本操作定义>:

基本操作名(参数表)
    初始条件:<初始条件描述>
    操作结果:<操作结果描述>

其中:
基本操作有两种参数:

  1. 赋值参数:只为操作提供输入值;
  2. 引用参数:以 & 开头,除可提供输入值,还将返回操作结果;

初始条件:描述了操作执行之前数据结构和参数应满足的条件,如不满足,则操作失败,并返回相应出错信息;若为空,则可省略;

操作结果:说明了操作正常完成之后,数据结构的变化状况和应返回结果;


例如:-brev-

抽象数据类型三元组的定义:

ADT Triplet {
    数据对象:D = {e1, e2, e3|e1, e2, e3 ∈ ElemSet(定义了关系运算的某个集合)}
    数据关系:R1 = {<e1, e2>, <e2, e3>}
    基本操作:
      InitTriplet(&T, v1, v2, v3)
        操作结果:构造了三元组 T,元素 e1, e2 和 e3 分别被赋以参数 v1, v2 和 v3 的值;
      DestroyTriplet(&T)
        操作结果:三元组 T 被销毁;
      Get(T, i, &e)
        初始条件:三元组 T 已存在,1 ≤ i ≤ 3;
        操作结果:用 e 返回 T 的第 i 元的值;
}ADT Triplet

over

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

  1. 预定义常量和类型:

    //函数结果状态代码
    #define TRUE 1
    #define FALSE 0
    #define OK 1
    #define ERROR 0
    #define INFEASIBLE -1 // 无法执行
    #define OVERFLOW -2 // 溢出

    // Status 是函数的类型,其值是函数结果状态代码
    typedef int Status;

  2. 数据结构的表示(存储结构)用类型定义(typedef)描述。数据元素类型约定为 ElemType ,由用户在使用该数据类型时自行定义。

  3. 基本操作的算法:

    函数类型 函数名(参数表) {
        // 算法说明
    
        语句序列
    
    } // 函数名
    

    注:
        算法中使用的辅助变量可以不做变量说明,必要时对其作用给予释。
        一般而言,a、b、c、d、e 等用作数据元素名;i、j、k、l、m、n 等用作整型变量名;p、q、r 等用作指针变量名。
        当函数返回值为函数结果状态代码时,函数定义为 Status 类型。
        为便于描述,增加以 & 开头的引用参数。


  4. 赋值语句

    以下简写:
    “变量名”:var
    “表达式”:exp
    “结构名”:struct
    “条件”:condition

    • 简单:var = exp;
    • 串联:var_1 = var_2 = ··· = var_k = exp;
    • 成组:
      • (var_1, ..., var_k) = (exp_1, exp_2, ..., exp_k);
      • struct_1 = struct_2;
      • struct = (value_1, ..., value_k);
      • var[] = exp;
      • var[start..end] = var[start..end];
    • 交换:var_1 <-> var_2;
    • 条件:var = condition_exp ? exp_T : exp_F;

  5. 选择语句

    • 条件语句 1:

      if (exp) statement;
      
    • 条件语句 2

      if (exp) statement;
      else statement;
      
    • 开关语句 1

      switch (exp) {
          case value_1: statement_1; break;
          ...
          case value_n: statement_1; break;
          default: statement_n+1;
      }
      
    • 开关语句 2 (一般不用)

      switch {
          case condition_1: statement_1; break;
          ...
          case condition_n: statement_n; break;
          default: statement_n+1;
      }
      

  1. 循环语句(同 c 语言)

    • for:

      for (exp; condition; exp) statement;
      
    • while:

      while (condition) statement;
      
    • do-while:

      do {
          statement;
      }while (exp);
      

  1. 结束语句

    • 函数结束:return exp; or return;
    • case 结束:break;
    • 异常结束:exit( 异常代码 );

  2. 输入输出

    • 输入:scanf([format], var_1, ..., var_n);
    • 输出:printf([format], exp_1, ..., exp_n);

    注:通常省略格式串。

  3. 注释

    • 单行注释:// blablabla...

  4. 基本函数

    • 最大值:max(exp_1, ..., exp_n)
    • 最小值:min(exp_1, ..., exp_n)
    • 绝对值:abs(exp)
    • 不足整数值:floor(exp)
    • 进位整数值:ceil(exp)
    • 判定文件结束:eof(file_var) or eof
    • 判定行结束:eoln(file_var) or eoln

  5. 逻辑运算

    • 与:A && B
      当 A 的值为 0 是,不再对 B 求值;
    • 或:A || B
      当 A 非 0,不再对 B 求值;

例如:-brev-

抽象数据类型 Triplet 的表示和实现:

// ----- 采用动态分配的顺序存储结构 -----

typedef ElemType * Tripley;

// --- 基本操作的函数原型说明 ---

Status InitTriplet(Triplet &T, ElemType v1, ElemType v2, ElemType v3, )
    // 操作结果:构造了三元组 T,元素 e1,e2 和 e3 分别被赋以 v1,v2,v3 的值;

Status DestroyTriplet(Triplet &T);
    // 操作结果:三元组 T 被销毁;

Status Get(Triplet T, int i, ElemType &e);
    // 初始条件:三元组 T 已存在,1 ≤ i ≤ 3;
    // 操作结果:用 e 返回 T 的第 i 元的值;

...

// ----- 基本操作的实现 -----

Status InitTriplet(Triplet &T, ElemType v1, ElemType v2, ElemType v3) {
    // 构造三元组 T,依次置 T 的 3 个元素为 v1,v2,v3;
    T = (ElemType * )malloc(3 * sizeof(ElemType)); // 分配 3 个元素的存储空间
    if (!T) exit(OVERFLOW); // 分配存储空间失败
    T[0] = v1;
    T[1] = v2;
    T[2] = v3;
    return OK;
} // InitTriplet

Status DestroyTriplet (Triplet &T) {
    // 销毁三元组 T;
    free(T);
    T = NULL;
    return OK;
} // DestroyTriplet

Status Get (Triplet T, int i, ElemType &e) {
    // 1 ≤ i ≤ 3,用 e 返回 T 的第 i 元的值;
    if (i<1 || i>3) return ERROR;
    e = T[i-1];
    return OK;
} // Get

...

over


算法分析

  1. 时间复杂度
    T(n) = O(f(n))

  2. 空间复杂度
    S(n) = O(f(n))

具体内容不再详述...


代码默认约定

此系列文章中关于高级语言(主要为 C 语言)的具体实现中,均有以下 约定 ,即直接省略此部分:

#include <stdio.h>
#include <stdlib.h>
#include <Windows.h>

#define TRUE 1
#define FLASE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2

typedef int Status;

其他注意:

  • 以下算法的代码中:
    存在一些直接使用的但非 C 语言自带的函数,其均出自其所属数据结构类型(如线性表)的 「抽象数据类型定义」 部分(默认缩略显示)的代码中;
  • 包含未实现的函数的算法的绝大部分在其随后的算法中给予了具体实现,
    且在代码下方注明了包含具体实现的算法位置;
  • 代码中 星号(*) 可能与其之后的代码间存在不应该的空格,因排版问题,见谅;
  • 类似于「算法 2.3」命名的算法们均为 书上原有 算法;
    其 C 语言或其他语言的具体实现(默认缩略显示)才是个人所写,将在书上原有算法介绍完后逐步添加;
  • 如仍有关于任何的不太清楚的问题或建议,
    请尽情联系 toacme.w@gmail.com (or w98818@vip.qq.com)。


  1. 《数据结构》(C 语言版),严蔚敏 吴伟民 编著。 ↩︎

393

评论(0

评论 取消
验证码:
搜索