第一章 绪论

1.2 基本概念和术语

  1. 数据是客观事物的符号表示，是所有能输入到计算机中并被计算机程序处理的符号的总称

  2. 数据元素是数据的基本单位

  3. 数据项，是组成数据元素的、有独立含义的、不可分割的最小单位

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

1.2.2 数据结构

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

  2. 数据结构包含逻辑结构和存储结构两个层次

  3. 逻辑结构

    1. 数据的逻辑结构是从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的

    2. 数据的逻辑结构有两个要素：一是元素；二是关系

    3. 通常有四类基本结构:集合结构，线性结构，树结构，图结构（网状结构）

    4. 其中集合结构，树结构，图结构都属于非线性结构

    5. 线性结构包括：线性表、栈和队列、字符串、数组、广义表

    6. 非线性结构包括：树、二叉树、有向图、无向图

    存储结构

    1. 数据对象在计算机中的存储表示称为数据的存储结构，也称为物理结构

    2. 数据元素在计算机中有两种基本的存储结构，分别是顺序存储结构和链式存储结构

    3. 顺序存储结构：顺序存储结构是借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系，通常借助程序设计语言的数组类型来描述

    4. 顺序存储结构要求所有的元素依次存放在一片连续的存储空间中，链式存储结构，无需占用一整块存储空间

1.2.3 数据类型和抽象数据类型

  1. 数据类型

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

  2. 抽象数据类型

    一般指由用户定义的，表示应用问题的数学模型，以及定义在这个模型上的一组操作的总称，具体包括三部分：数据对象、数据对象上关系的集合以及对数据对象的基本操作的集合

1.4 算法和算法分析

1.4.1 算法的定义及特性

  1. 算法是为了解决某类问题而规定的一个有限长的操作序列

  2. 一个算法必须满足以下五个重要特性：

    （1）有穷性：有穷步、有穷时间
    （2）确定性：确切对规定，不会产生二义性
    （3）可行性：已经实现的基本操作运算执行有限次
    （4）输入：零个或多个输入
    （5）输出：一个或多个输出

1.4.2 评价算法优劣的基本标准

（1）：正确性
（2）：可读性
（3）：健壮性
（4）：高效性

1.4.3 算法的时间复杂度

  1. 衡量算法效率的方法主要有两类：事后统计法和事前分析估算法
  2. 问题规模是算法求解问题输入量的多少，是问题大小的本质表示，一般用整数n表示
  3. 一个算法的执行时间大致上等于其所有语句执行时间的总和，而语句的执行时间则为该条语句的重复执行次数和执行一次所需时间的乘积
  4. 一条语句的重复执行次数称为语句频度

第二章 线性表

线性结构的基本特点是除第一个元素无直接前驱，最后一个元素无直接后驱之外，其他每个数据元素都有一个前驱和后继。线性表是最基本且最常用的一种线性结构

2.1 线性表的定义和特点

2.2 案例引入

2.4 线性表的顺序表示和实现

2.4.1 线性表的顺序存储表示

  1. 线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素，这种表示也称作线性表的顺序存储结构或顺序映像。通常，称这种存储结构的线性表为顺序表。其特点是，逻辑上相邻的数据元素，其物理次序也是相邻的。
  2. 线性表的顺序存储结构是一种随机存取的存储结构
  3. 通常用数组来描述数据结构中的顺序存储结构