![)13G19@$7[KM7Q0YUS}0H.png](https://cdn.nlark.com/yuque/0/2022/png/25668369/1641563412445-ffb36ff2-e459-4503-b2cb-1609c1f20c1e.png#clientId=u3289bad1-2f85-4&crop=0&crop=0&crop=1&crop=1&from=paste&height=500&id=ud52843e6&margin=%5Bobject%20Object%5D&name=%2913G19%40%60%247%5B%60KM7Q0YUS%7D0H.png&originHeight=713&originWidth=1032&originalType=binary&ratio=1&rotation=0&showTitle=false&size=86418&status=done&style=none&taskId=u051b28f5-63bb-4163-8a94-eb51ef55633&title=&width=723)

1.1 基本概念和术语

  • 数据是对客观事物的符号表示；
  • 数据元素是数据的基本单位；
  • 数据项是数据的不可分割的最小单位，一个数据元素可由若干个数据项组成；
  • 数据对象是性质相同的数据元素的集合，是数据的一个子集；
  • 数据结构是相互之间存在的一种或多种特定关系的数据元素的集合

1.1.1 数据的逻辑结构

数据结构按逻辑结构可分为两大类：线性结构和非线性结构，也可细分为四类基本结构：集合、线性结构、树形结构、图状结构。

Z93RE4W$DW@TYW{0I)$OP1L.png

数据结构的形式定义为：数据结构是一个二元组

笔记一 绪论和抽象数据类型 - 图2%0A#card=math&code=Data%5C%20Structure%20%3D%20%28D%2C%20S%29%0A&id=lJdoC)

其中D是数据元素的有限集，S是D上关系的有限集。

1.1.2 数据的存储结构

数据结构在计算机中的表示（又称映像）称为数据的物理结构，又称存储结构，它包括数据元素的表示和关系的表示。

数据元素之间的关系在计算机中有两种不同的表示方法：顺序映像和非顺序映像，由此得到两种不同的存储结构：顺序存储结构和链式存储结构。

  • 顺序映像的特点是借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系
  • 非顺序映像的特点是借助指示元素存储地址的指针表示数据元素之间的逻辑关系

数据类型是一个值的集合和定义在这个值集上的一组操作的总称。

1.2 抽象数据类型

抽象数据类型（Abstract Data Type，ADT）是指一个数学模型以及定义在该模型上的一组操作。

  • 原子类型：属原子类型的变量的值是不可分解的
  • 固定聚合类型：属该类型的变量的值由确定数目的成分按某种结构组成
  • 可变聚合类型：构成可变聚合类型“值”的成分的数目不确定

抽象数据类型可用以下三元组表示：

笔记一 绪论和抽象数据类型 - 图3%0A#card=math&code=%28D%2CS%2CP%29%0A&id=dsMLS)

其中，D是数据对象，S是D上的关系集，P是对D的基本操作集。

  1. ADT 抽象数据类型名 {
  2.     数据对象：<数据对象的定义>
  3.     数据关系：<数据关系的定义>
  4.     基本操作：<基本操作的定义>
  5. } ADT 抽象数据类型名
  7. 基本操作名（参数表）
  8.     初始条件：<初始条件描述>
  9.     操作结果：<操作结果描述>

基本操作有两种参数：赋值参数只为操作提供输入值；引用参数以&开头，除提供输入值外还将返回操作结果。

（1）预定义常量和类型

  1. #define TRUE 1
  2. #define FALSE 0
  3. #define OK 1
  4. #define ERROR 0
  5. #define INFEASIBLE -1
  6. #define OVERFLOW -2
  7. // Status是函数的类型，其值是函数结果状态代码
  8. typedef int Status

（2）数据结构的表示（存储结构）用类型定义（typedef）描述，数据元素类型约定为ElemType，由用户在使用该数据类型时自行定义

（3）基本操作的算法都用以下形式的函数描述

  1. 函数类型 函数名（函数参数表）{
  2.     // 算法说明
  3.     语句序列
  4. } // 函数名

（4）赋值语句

  1. 简单赋值 变量名 = 表达式;
  2. 串联赋值 变量名 1 = 变量名2 = … = 变量名k = 表达式;
  3. 成组赋值 （变量名1, …, 变量名k）= （表达式1, …, 表达式k）;
  4.          结构名 = 结构名;
  5.          结构名 = （值1, …, 值k）;
  6.          变量名[] = 表达式;
  7.          变量名[起始下标, …, 终止下标] = 变量名[起始下标, …, 终止下标];
  8. 交换赋值 变量名<->变量名;
  9. 条件赋值 变量名 = 条件表达式 ? 表达式T : 表达式F;

（5）选择语句

  1. 条件语句1 if（表达式）语句;
  2. 条件语句1 if（表达式）语句;
  3.           else（表达式）语句;
  4. 开关语句1 switch（表达式）{
  5.           case 值1: 语句序列1; break;
  6.           ……
  7.           case 值n: 语句序列n; break;
  8.           default: 语句序列n+1;
  9.           }
  10. 开关语句1 switch（表达式）{
  11.           case 条件1: 语句序列1; break;
  12.           ……
  13.           case 条件n: 语句序列n; break;
  14.           default: 语句序列n+1;
  15.           }

（6）循环语句

  1. for语句         for(赋初值表达式序列; 条件; 修改表达式序列)语句;
  2. while语句     while(条件)语句;
  3. do-while语句 do {
  4.                 语句序列;
  5.              }while(条件);

（7）结束语句

  1. 函数结束语句 return 表达式;
  2.              return;
  3. case结束语句 break;
  4. 异常结束语句 exit(异常代码);

（8）输入和输出语句

  1. 输入语句 scanf([格式串], 变量1, …, 变量n);
  2. 输出语句 printf([格式串], 表达式1, …, 表达式n);
  3. // 通常省略格式串

（9）注释

  1. 单行注释 // 文字序列

（10）基本函数

  1. 求最大值        max(表达式1, …, 表达式n);
  2. 求最小值        min(表达式1, …, 表达式n);
  3. 求绝对值        abs(表达式);
  4. 求不足整数值 floor(表达式);
  5. 求进位整数值 ceil(表达式);
  6. 判定文件结束 eof(文件变量)或eof
  7. 判定行结束    eoln(文件变量)或eoln

（11）逻辑运算

  1. 与运算 && : 对于A&&B,当A的值为0时,不再对B求值
  2. 或运算 || : 对于A||B,当A的值为非0时,不再对B求值

1.3 算法和算法分析

1.3.1 算法

算法是对特定问题求解步骤的一种描述。

算法的5个重要特性：

  • 有穷性：算法在有穷步后结束，每一步在有穷时间内完成
  • 确定性：算法中每一条指令有确切含义
  • 可行性：可以通过已经实现的基本运算执行有限次实现
  • 输入：有零个或多个输入
  • 输出：有零个或多个输出

算法设计应达到：

  • 正确性
  • 可读性
  • 健壮性
  • 效率与低存储量需求

1.3.2 算法分析

时间复杂度：笔记一 绪论和抽象数据类型 - 图4%20%3D%20O(f(n))#card=math&code=T%28n%29%20%3D%20O%28f%28n%29%29&id=GwBef)
空间复杂度：笔记一 绪论和抽象数据类型 - 图5%20%3D%20O(f(n))#card=math&code=S%28n%29%20%3D%20O%28f%28n%29%29&id=VlNzK)

时间复杂度估计：内层循环时间复杂度笔记一 绪论和抽象数据类型 - 图6外层循环时间复杂度

算法原地工作是指算法所需的辅助空间为常量，即笔记一 绪论和抽象数据类型 - 图7.

循环主体中的变量参与循环条件的判断

例一：

  1. int i = 1;
  2. while (i <= n)
  3.     i = i * 2;

分析：i 乘以 2 的次数正是主体语句的执行次数 t，则笔记一 绪论和抽象数据类型 - 图8，笔记一 绪论和抽象数据类型 - 图9，因此时间复杂度为笔记一 绪论和抽象数据类型 - 图10

例二：

  1. int y = 5;
  2. while ((y + 1) * (y + 1) < n)
  3.     y ++;

分析：y + 1 的次数恰好与笔记一 绪论和抽象数据类型 - 图11成正比，记笔记一 绪论和抽象数据类型 - 图12，由笔记一 绪论和抽象数据类型 - 图13，得笔记一 绪论和抽象数据类型 - 图14，则笔记一 绪论和抽象数据类型 - 图15

循环主体中的变量与循环条件无关

例一：求整数n的阶乘的时间复杂度

  1. int fact(int n) {
  2.     if (n <= 1)    return 1;
  3.     return n * fact(n - 1);
  4. }

分析：递归程序一般使用公式进行递推，笔记一 绪论和抽象数据类型 - 图16，则笔记一 绪论和抽象数据类型 - 图17

例二：多重嵌套循环

有几层循环，时间复杂度就是n的几次方

[1]《数据结构（C语言版）》 严蔚敏 吴伟民