第一章：绪论

1.1 什么是数据结构

介绍了三种类型数据结构：线性、树、图

1.2 基本概念和术语

• 数据：指能输入到计算机中并被计算机程序处理的符号的总称。
• 数据元素：数据的基本单位。
• 数据项：一个数据元素由若干个数据项组成，是数据不可分割的最小单位。
• 数据对象：性质相同的数据元素的集合，是数据的一个子集。
• 数据结构：是相互之间存在一种或多种特定关系的数据元素的集合，通常有以下4种，集合(同属）、线性结构（一对一）、树形结构（一对多）以及图状结构或网状结构（多对多）。
  形式定义：$Data_Structure = (D, S)$，D数据，S结构关系。
• 数据元素存储：顺序存储结构和链式存储结构。

• 数据类型：整型之类的，按照“值“的不同特性，分为原子类型（不可分即整型之类）和结构类型（可分即数组之类）。

• 抽象数据类型：ADT，是指一个数学模型以及定义在该模型上的一组操作。（有点像用类定义一个新的数据类型）也可分为原子类型、固定聚合类型（实数有实部和虚部固定两个）以及可变聚合类型（”值“的成分数目确定与不确定）

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

  以抽象数据类型Triplet的表示与实现为例

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

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

typedef int Status;//默认函数类型
typedef int ElemType;//数据元素类型
typedef ElemType* Triplet;

Status InitTriplet(Triplet& T, ElemType v1, ElemType v2, ElemType v3);
//构造三元组T,三个值分别为v1、v2和v3。
Status DestroyTriplet(Triplet& T);
//销毁三元组
Status Get(Triplet T, int i, ElemType& e);
//用e返回第i元的值
Status Put(Triplet& T, int i, ElemType e);
//改变第i元值为e
Status IsAscending(Triplet T);
//判断是否升序排列
Status IsDescending(Triplet T);
//判断是否降序排列
Status Max(Triplet T, ElemType& e);
//用e返回最大值
Status Min(Triplet T, ElemType& e);
//用e返回最小值
int main()
{
    Triplet T;
    InitTriplet(T, 1, 2, 3);
    ElemType e = 0;
    Get(T, 2, e);
    printf("e:%d\n", e);
    Put(T, 1, e);
    printf("T:%d %d %d\n", T[0],T[1],T[2]);
    printf("IsAscending:%d\n", IsAscending(T));
    printf("IsDescending:%d\n", IsDescending(T));
    Max(T, e);
    printf("Max:%d\n", e);
    Min(T, e);
    printf("Min:%d\n", e);
    system("pause");
    return 0;
}
Status InitTriplet(Triplet& T, ElemType v1, ElemType v2, ElemType v3)
{
    T = (ElemType*)malloc(3 * sizeof(ElemType));
    if (!T) exit(OVERFLOW);
    T[0] = v1; T[1] = v2; T[2] = v3;
    return OK;
}
Status DestroyTriplet(Triplet& T)
{
    free(T);
    T = NULL;
    return OK;
}
Status Get(Triplet T, int i, ElemType& e)
{
    if (i < 1 || i>3) return ERROR;
    e = T[i- 1];
    return OK;
}
Status Put(Triplet& T, int i, ElemType e)
{
    if (i < 1 || i>3) return ERROR;
    T[i - 1] = e;
    return OK;
}
Status IsAscending(Triplet T)
{
    if ((T[0] <= T[1]) && (T[1] <= T[2]))
        return TRUE;
    return FALSE;
}
Status IsDescending(Triplet T)
{
    if ((T[0] >= T[1]) && (T[1] >= T[2]))
        return TRUE;
    return FALSE;
}
Status Max(Triplet T, ElemType& e)
{
    e = (T[0] >= T[1]) ? ((T[0] >= T[2]) ? T[0] : T[2]) : ((T[1] >= T[2]) ? T[1] : T[2]);
    return OK;
}
Status Min(Triplet T, ElemType& e)
{
    e = (T[0] <= T[1]) ? ((T[0] <= T[2]) ? T[0] : T[2]) : ((T[1] <= T[2]) ? T[1] : T[2]);
    return OK;
}

1.4 算法与算法分析

• 算法：对特定问题求解步骤的一种描述。有穷性+确定性+可行性+输入+输出。有穷性指执行有穷步骤，每步有穷时；确定性指算法中每一条指令必须有确切的含义并且算法只有唯一的执行路径即相同输入只有相同输出。
• 算法设计的要求：正确性+可读性+健壮性+效率与低存储量需求。正确性指能满足问题需求；可读性指方便阅读与交流；健壮性指适应性好；效率指算法执行时间；存储量指算法执行过程所需存储空间。
• 算法效率的度量：
  • 事后统计的方法
    指利用计算机内部的计时功能测量编译时间，这样得到的是绝对时间，无法体现算法优劣。
  • 事前分析估算的方法
    一个特定算法“运行工作量”的大小只依赖于问题的规模，我们用大O阶方法来描述算法的时间复杂度，记作$T(n)=O(f(n))$。例如一个加法运算$O(1)$，一重循环$O(n)$,二重循环$O(n^2)$。
    空间复杂度：$S(n)=O(f(n))$。