什么是数据结构

研究非数值的程序设计问题中的操作对象，以及它们之间的关系和操作等相关问题的学科。
数据结构是相互之间存在一种或者多种特定关系的数据元素的集合。

什么是数据

描述客观事物的符号，是计算机中可以操作的对象，是被计算机识别，并输入给计算机处理的符号集合。

什么是数据元素（记录）

组成数据的、有一定意义的基本单位，在计算机中通常作为整体处理，也被称为记录。

什么是数据项

数据不可分割的最小单元，数据处理的最小单位是数据项。

什么是数据对象

性质相同的数据集合，是数据的子集。

逻辑结构

有序表属于逻辑结构。

集合结构

  • 数据结构中的数据元素同属一个集合。
  • 数据元素互相之间没有其他关系。

线性结构

数据元素之间是一对一的关系。

树形结构

数据之间存在一种一对多的层次关系。

图形结构

数据元素是多对多的关系。

物理结构

又叫存储结构，是指数据的逻辑结构在计算机中的存储形式。栈与数据的存储结构无关。

顺序存储结构

把数据元素存放在地址连续的存储单元里。

链式存储结构

把数据元素存放在任意的存储单元里。

抽象数据类型

计算机中，内存空间是有限的，不同的类型的数据分配的内存空间大小不同。数据类型是指一组相同的值的集合及定义在此集合中的一些操作的总称。在 C 语言中，按照值的不同，数据类型分为两类：

  • 原子型：不可再分解的基本类型，包括整型、实型、字符型等。
  • 结构型：由若干类型组合而成，是可以再分解的。例如，整型数值是由若干个整型数据组成的。

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

image.png
（抽象数据类型的标准模式）

记录程序执行时间

  1. #include <stdio.h>
  2. #include <time.h>
  4. void myFunction();
  6. int main() {
  7.     clock_t start, stop;
  8.     double duration;  // 记录被测函数运行时间，以秒为单位。
  9.     start = clock(); // 不在测试内的准备工作写在 clock() 调用之前
  10.     myFunction();
  11.     stop = clock();
  12.     duration = ((double)(start - stop))/CLK_TCK;
  13.     // 其他不在测试范围的处理写在后面，例如输出 duration 的值
  14.     return 0;
  15. }
  17. void myFunction() {
  18.     // code
  19. };

clock()：捕捉从程序开始运行到 clock() 被带调用时所耗费的时间。这个时间的单位是 clock tick，即“时间打点”。常量 CLK_TCK：时间每秒所走的时钟打点数。

衡量算法质量的指标

正确性、易读性、强壮性、高效性