使用 C 与 python 实现。

学习目录：

数据结构与算法分析概念

数据：是对客观事物的符号表示，是可被计算机识别并加工处理的对象。

数据对象：是性质相同的数据元素的集合。

数据元素：是数据的基本单位，在程序中通常作为一个整体进行处理。

数据项：是组成数据元素的不可分割的最小单位。

以上四个术语的关系：数据（包含）数据对象（包含）数据元素（包含）数据项

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

数据元素相互之间的关系称为结构，有以下几种结构：集合、线性结构（一对一）、树形结构（一对多）、图状结构/网状结构（多对多），其中除线性结构外的其他结构，也属于非线性结构。

数据结构是一个二元组：Data_Structure = (D, S)，其中 D 是数据元素的有限集，S 是 D 上关系的有限集。

数据结构由四部分组成：数据元素、数据元素之间的逻辑关系、逻辑关系在计算机中的存储表示、所规定的操作

数据的存储表示和运算算法的描述构成了数据结构的实现。

数据结构在计算机中的表示称为存储结构。有两种存储结构：

顺序存储结构：将逻辑上相关的数据元素一次存储在地址连续的存储空间内。特点：借助元素在存储器中的相对位置来表示数据元素间的逻辑关系。
链式存储结构：数据元素可以存储在任意的存储空间中，可以是连续的存储空间，可以是不连续的存储空间。元素的存储位置不能体现逻辑关系，而是需要通过指示元素存储地址的指针表示数据元素之间的逻辑关系。

数据类型是性质相同的值的集合以及定义在该值集上的运算操作的集合。

抽象数据类型（ADT）是指一个数学模型以及定义在该模型上的一组操作。不论内部结构如何变化，只要数学特性不变，就不影响其外部使用。ADT 有两个特征：

数据封装：把数据和操纵数据的运算组合在一起的机制
信息隐蔽：数据的使用者只需知道运算的定义便可访问数据，无需了解数据的存储和实现细节

抽象数据类型可以用三元组表示：(D, S, P)。其中 D 表示数据对象、S 表示 D 上的关系集、P 表示对 D 的基本操作集

算法是对特定问题求解步骤的描述，有 5 个特性：输入、输出、可行性、确定性、有穷性

好的算法需要具备的特性：正确性、可读性、健壮性、高效性

算法复杂性是算法运行所需要的计算机资源的量，其中时间资源的量称为时间复杂度，空间资源的量称为空间复杂度。

复杂度与问题的规模、算法的输入、算法本身的函数有关，其中最主要因素是问题规模。

一个算法的时间花销与算法中语句的执行次数成正比。一个算法中语句执行次数为语句频度，记为T(n)，其中 n 为问题规模大小。若有一个函数f(n)，则算法渐进时间复杂度记为T(n) = O(f(n))

渐进表示法：

渐进上界记号：

$O(g(n)) = { f(n)|存在正常数c和n_0，使得对所有n \geq n_0有：0 \leq f(n) \leq cg(n) }$
渐进下界记号：

$\Omega(g(n)) = { f(n)|存在正常数c和n_0，使得对所有n \geq n_0有：0 \leq cg(n) \leq f(n) }$
紧渐近界记号：

$\Theta(g(n)) = { f(n)|存在正常数c_1,c_2和n_0，使得对所有n \geq n_0有：c_1g(n) \leq f(n) \leq c_2g(n) }$

常见的渐进时间复杂度（从小到大）:

$O(1)<O(\log_2n)<O(n)<O(n\log_2n)<O(n^2)<O(n^3)<O(2^n)$

线性表

线性表是零个或多个有限数据元素构成的线性序列。除第一个和最后一个元素，其他元素都有唯一一个直接前驱元素和直接后继元素。

抽象数据类型线性表定义：

数据对象：$D={a_i|a_i \in ElemSet, i = 1,2,…,n, n \geq 0 }$
数据关系：$R1={ <a_{i-1},a_i>|a_{i-1}, a_i \in D, i=2,…,n }$

线性存储分为顺序存储与链式存储。

顺序表

顺序表包含三个部分：

存储空间的起始位置
顺序表最大存储容量
顺序表当前长度

顺序表有两种创建方式：静态表、动态表

静态表：

#define MaxSize 50             // 最大长度
typedef int Elemtype
typedef struct {
    Elemtype data[MaxSize];    // 顺序表元素
    int length;                // 顺序表当前长度
}SqList;

动态表：

typedef int Elemtype
typedef struct {
    Elemtype *data;            // 数组指针
    int MaxSize, length;
}SqList;

动态表创建初始化：

#define InitSize 100
SqList L;
L.data = (Elemtype *)malloc(sizeof(Elemtype) * InitSize)

插入操作：

判断i是否正确
判断表长是否超过数组长度
从后向前到第i个位置，分别将这些元素都向后移动一位
将该元素插入位置i并表长加 1

bool ListInsert(SqList &L, int i, Elemtype e){
    if(i < 1 || i > L.length + 1)
        return false;
    if(L.length >= MaxSize)
        return false;
    for(int j = L.length; j >= i; j--)
        L.data[j] = L.data[j-1];
    L.data[i-1] = e;
    L.length++;
}

最好情况：在表尾插入，不用移元素。复杂度$O(1)$

最坏情况：在表头插入，要移 n 次元素。复杂度$O(n)$

平均情况：在表中间插入，平均移动元素次数为$\frac{n}{2}$

删除操作：

判断i是否正确
取删除元素
将删除元素后的所有元素都向前移动一位
修改表长

bool ListDelete(SqList &L, int i, Elemtype &e){
    if(i < 1 || i > L.length)
        return false;
    e = L.data[i-1];
    for(int j = i; j < L.length; j++)
        L.data[j-1] = L.data[i];
    L.length--;
    return true;
}

最好情况：删除表尾元素，复杂度$O(1)$

最坏情况：删除表头元素，复杂度$O(n)$

平均情况：删除表中间元素，平均移动元素次数$\frac{n-1}{2}$

链式表

链式表分为单链表、静态链表、循环链表、双链表。

链式存储的存储单元可连续也可不连续，每个结点包含数据域和指针域，数据域存储数据信息，指针域存储下一个结点的位置信息。

单链表定义：

typedef struct LNode {     // 单链表结点类型
    Elemtype data;         // 数据域
    struct LNode *next;    // 指针域
}LNode, *LinkList;         // 定义一个节点和链表

通常会用头指针标识一个单链表，如LinkList L;

头结点和头指针的区别：

不管带不带头结点，头指针始终指向链表的第一个结点
而头结点是带头结点链表中的第一个结点，通常不存信息。

设置头结点的作用：

统一第一个结点和其余结点的操作

统一空链表和非空链表的操作

头插法建立单链表：将新结点插到当前链表的表头

LinkList CreateList(LinkList &L) {
    LNode *s;
    int x;
    L = (LinkList)malloc(sizeof(LNode));
    L.next = NULL;
    scanf("%d", &x);
    while(x != 9999){
        s = (LNode)malloc(sizeof(LNode));
        s.data = L.next;
        L.next = s;
        scanf("%d", &x);
    }
    return L;
}

尾插法建立单链表：将新结点插到当前链表的表尾

LinkList CreateList(LinkList &L) {
    LNode *s, *r = L;   // r为表尾指针，指向表尾结点
    int x;
    L = (LinkList)malloc(sizeof(LNode));
    scanf("%d", &x);
    while(x != 9999) {
        s = (LNode *)malloc(sizeof(LNode));
        s.data = x;
        r.next = s;
        r = s;          // r指向新的表尾结点
        scanf("%d", &x);
    }
    r.next = NULL;
    return L;
}

按序号查找：从第一个结点，顺着 next 搜索到指定序号结点

LNode *GetElem(LinkList L, int i) {
    LNode *p = L.next;
    int j = 1;
    if(i == 0) return L;      // i为0时返回头结点
    if(i < 1) return NULL;
    while(p != NULL && j < i) {
        p = p.next;
        j++;
    }
    return p;
}

按值查找：从第一个结点，顺着 next 搜索到指定值的结点

LNode *LocateElem(LinkList L, Elemtype e) {
    LNode *p = L.next;
    while(p != NULL && p.data != e) {
        p = p.next;
    }
    return p;
}

重学数据结构与算法笔记

数据结构与算法分析概念

线性表

顺序表

链式表