[Web]北京交大925数据结构复习笔记

——By ZNing

2017数据结构考试大纲

1、绪论

  1. 掌握相关的基本概念，如数据结构、逻辑结构、存储结构、数据类型、抽象数据类型等；
  2. 掌握算法设计的原则，掌握计算语句频度和估算算法时间复杂度和空间复杂度的方法；
  3. 了解使用类C语言描述算法的方法。

2、线性表

  1. 掌握线性表的逻辑结构和存储结构；
  2. 掌握线性表在顺序结构和链式结构上实现基本操作的方法；
  3. 理解线性表两种存储结构的不同特点及其适用场合，会针对需求选用合适的存储结构解决实际问题；
  4. 了解一元多项式的表示方法和基本运算的实现方法。

3、栈和队列

  1. 了解栈和队列的特点；
  2. 掌握在两种存储结构上栈的基本操作的实现；
  3. 掌握栈的各种应用，理解递归算法执行过程中栈状态的变化过程；
  4. 掌握循环队列和链队列的基本运算；
  5. 会应用队列结构解决实际问题。

4、串

  1. 掌握串的基本运算的定义，了解利用基本运算来实现串的其它运算的方法；
  2. 了解在顺序存储结构和在堆存储结构以及块链存储结构上实现串的各种操作的方法；
  3. 理解KMP算法，掌握NEXT函数和改进NEXT函数的定义和计算。

5、数组和广义表

  1. 掌握数组在以行为主和以列为主的存储结构中的地址计算方法；
  2. 掌握矩阵压缩存储时的下标变换方法，了解以三元组表示稀疏矩阵的方法；
  3. 理解广义表的定义及其存储结构，理解广义表的头尾和子表两种分析方法。

6、树和二叉树

  1. 熟练掌握二叉树的结构特点和性质，掌握二叉树各种存储结构及构建方法；
  2. 掌握按先序、中序、后序和层次次序遍历二叉树的算法，理解二叉树的线索化实质和方法；
  3. 利用二叉树的遍历求解实际问题；
  4. 掌握树的各种存储结构及其特点，掌握树的各种运算的实现算法；
  5. 掌握建立最优二叉树和哈夫曼编码的方法。

7、图

  1. 熟练掌握图的基本概念，会构建各种图的存储结构；
  2. 掌握深度优先搜索遍历图和广度优先搜索遍历图的算法；
  3. 灵活运用图的遍历算法求解各种路径问题，包括最小生成树﹑最短路径﹑拓扑排序﹑关键路径等。

8、查找

  1. 熟练掌握各种静态查找和动态查找算法，会计算查找成功时和失败时的平均查找长度；
  2. 掌握二叉排序树的建立、插入和删除过程，掌握二叉平衡树的建立和旋转平衡方法；
  3. 掌握B-树的建立、插入和删除结点的过程；
  4. 熟练掌握哈希表的构造方法和处理冲突的方法。

9、排序

  1. 掌握各种排序算法，包括插入类、交换类、选择类、归并类排序及基数排序；
  2. 能够对各种排序方法进行比较分析，如稳定性、时间和空间性能等，了解各种排序方法的特点和不同并灵活应用；
  3. 理解外部排序的主要思想和过程。

第一章 绪论

一、考纲要求

  1. 掌握相关的基本概念，如数据结构、逻辑结构、存储结构、数据类型、抽象数据类型等；
  2. 掌握算法设计的原则，掌握计算语句频度和估算算法时间复杂度和空间复杂度的方法；
  3. 了解使用类C语言描述算法的方法。

二、基本知识

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

2. 数据项是数据不可分割的最小单位

3. 数据结构及其形式定义

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

数据元素之间的逻辑结构有四种基本类型：

  1. 集合
  2. 线性结构
  3. 树形结构
  4. 图状结构或网状结构

4. 关于逻辑结构域存储结构的关系及存储结构的分类的几个定义

  1. 结构定义中的“关系”描述的是数据元素之间的逻辑关系，又称逻辑结构（抽象的，与现实无关）；
  2. 数据结构在计算机中的表示成为数据的物理结构（存储结构）；

  3. 数据元素之间的关系在计算机中有两种不同的表示方法：

    1. 顺序映像（顺序存储结构），物理结构位置相邻
    2. 非顺序映像（链式存储结构），指针表示关系

    （此处需要有图）

5. 数据类型与抽象数据类型

数据类型指的是一个值的集合和定义在该值集上的一组操作的总称。在C语言中数据类型有：基本数据类型和构造类型。

数据结构不同于数据类型，也不同于数据对象，它不仅要描述数据类型的数据对象，而且要描述数据对象各元素之间的相互关系。

抽象数据类型（ADT）细分为院子类型、固定聚合、可变聚合类型。

ADT的一般定义形式是：

    ADT <抽象数据类型名>{
        数据对象：<数据对象的定义>
        数据关系：<数据关系的定义>
        基本操作：<基本操作的定义>
    } ADT <抽象数据类型名>
  1. 其中数据对象和数据关系的定义用伪码描述。

  2. 基本操作的定义是：

        <基本操作名>(<参数表>)
    初始条件:<初始条件描述>
    操作结果:<操作结果描述>

    初始条件：描述操作执行之前数据结构和参数应满足的条件；若不满足，则操作失败，返回相应的出错信息。

    操作结果：描述操作正常完成之后，数据结构的变化状况和应返回的结果。

6. 算法的概念

算法是对特定问题求解步骤的一种描述，它是指令的优先序列，其中每一条指令表示一个或多个操作。

7. 算法的五个特性

  1. 有穷性
  2. 确定性
  3. 可行性
  4. 输入（0个或多个）
  5. 输出（0个或多个）

8. 算法的设计要求

  1. 正确性
  2. 可读性
  3. 健壮性
  4. 效率与低存储量（正确性的四个层次(？)，通常要求达到C层）

9. 算法的时间复杂度

常见有：O(\(1\)), O(\(n\)), O(\(n^2\)), O(\(log^2n\)), O(\(nlog^2n\)), O(\(2^n\))

语句频度，用归纳法计算。

10. 算法的空间复杂度（一般不作要求）

第二章 线性表

一、考纲要求

  1. 掌握线性表的逻辑结构和存储结构；
  2. 掌握线性表在顺序结构和链式结构上实现基本操作的方法；
  3. 理解线性表两种存储结构的不同特点及其适用场合，会针对需求选用合适的存储结构解决实际问题；
  4. 了解一元多项式的表示方法和基本运算的实现方法。

二、基本知识

1. 线性表及其特点

线性表是n个数据元素的有效序列。线性结构特点简言之：“第一个”、“最后一个”、“前驱”、“后继”

完整说法：

  1. 存在一个唯一的被称为“第一个”的数据元素；
  2. 存在一个唯一的被称为“最后一个”的数据元素；
  3. 除第一个元素外，每个元素均有唯一的直接前驱；
  4. 除最后一个元素外，每个元素均有唯一一个直接后继。

2. 顺序表——线性表的顺序存储结构

  1. 特点
    1. 逻辑上相邻的元素在物理位置上相邻
    2. 随机访问

  2. 类型定义：简言之：“数组+长度”。

    完整说法：

        const int MAXSIZE = 线性表最大长度;
    typedef struct {
        DataType elem[MAXSIZE]；
        int length;
    }

    注：

    1. SqList为类型名，可换用其他写法；
    2. DataType是数据元素的类型，根据需要确定;
    3. MAXSIZE根据需要确定，如const int MAXSIZE = 64;
    4. 课本上的SqList类型可在需要时增加存储空间，在上面这种定义下不可以。这样做避免对台内存分配，明显减少算法的复杂程度。容易理解。
    5. 课本上的SqList类型定义中listsize表示已经分配的空间大小（容纳数据元素的个数）。当插入元素而遇到L.length=L.listsize时，用realloc(L.elem,L.listsize+增量)重新分配内存，而realloc()函数则在必要的时候自动复制原来的元素到新分配的空间之中。

  3. 基本形态

    1. 顺序表空：条件L.length==0，不允许删除操作；
    2. 顺序表满：条件L.length==MAXSIZE，不允许插入操作；
    3. 不空不满：可以插入删除

  4. 遍历算法

    顺序访问所有元素：

        for(i = 0; i < L.length; i++){
        visit(L.elem[i]);
    }

    查找元素x：

        for(i = 0; i < L.length; i++){
        if(L.elem[i] == X)
            break;
        if(i < L.length)
            Found;
        else
            Not Found;
    }

  5. 插入算法

    1. 前提：表不满
    2. 合法范围：i>=1&&i<=L.length+1
    3. 步骤：
      1. 第i至最后所有元素后移一个元素
      2. 在第i个位置插入元素x
      3. 表长增加1

    4. 算法

          bool ListInsert(SqList& L, int i, DataType x)
    {
        if(L.length == MAXSIZE || i<i || i>L.length+1) return ERROR;//失败
        //元素后移
        for(j = L.length-1; j >=i-1 ; j--){//这里j为下标，从.length-1到i-1
            L.elem[j+1]=L.elem[j];//若作为位序，有如何修改？
        }
        //插入x，表长增加1
        L.elem[i-1]=x;
        L.length++;
        return OK;
    }

  6. 删除算法

    1. 前提：表非空
    2. 合法范围：i>=1&&i<=L.length
    3. 步骤：
      1. 取出第i个元素
      2. 第i个元素之后的元素向前移动一个位置
      3. 表长减少1

    4. 算法

          bool ListDelete(SqList& L, int i, DataType& x)
    {
        if(L.length == MAXSIZE || i<i || i>L.length+1) return ERROR;//失败
        x=L.elem[i-1];
        for(j = 0; j < L.length; j++){
            L.elem[j-1]=L.elem[j];
        }
        L.length--;
        return OK;//成功
    }

  7. 算法分析

插入 删除
基本操作 移动元素 移动元素
平均移动次数 \(\frac{1}{n+1}\sum_{i=1}^{n+1}(n-i+1)=\frac{n}{2}\) \(\frac{1}{n}\sum_{i=1}^{n}(n-i)=\frac{n-1}{2}\)
时间复杂度 O(n) O(n)
尾端操作 插入第n+1个元素，不移动 删除第n个元素，不移动
  1. 其他算法（函数）
    1. InitList(&L),ClearList(&L): L.length=0;
    2. ListEmpty(L): return L.length==0;
    3. ListLength(L): return L.length;
    4. GetElem(L, i, &e): e=L.elem[i-1];

3. 单链表——线性表的链式存储结构之一

  1. 概念 线性聊表、单链表、结点；数据域、指针域；头结点、头指针
  2. 特点 用指针表示数据之间的逻辑关系（逻辑相邻的元素物理位置不一定相邻）。

  3. 类型定义
    简言之，“数据+指针”

    完整描述：(此处应有图)

        const int MAXSIZE = 线性表最大长度;
    typedef struct LNode {
        DataType data；
        struct LNode *next;
    } LNode, *LinkList;

    1. 基本形态

      带头结点的单聊表的基本形态有：

      1. 单链表空：条件 L->next==0
      2. 单链表不空：条件 L->next!=0

    2. 遍历算法

      1. 顺序访问所有元素：借助指针“顺藤摸瓜”，沿着链表访问节点

          void PrintLinkList(LinkList L)
  {
      p=L->next; //注意起始位置的考虑
      while(p!=NULL){ //判断表位，另外p!=0或均可
          print(p->data);//访问，可以换成各种操作，例如print
          p=p->next;//指针沿着链表向后移动
      }
  }

      2. 查找元素x

        方法一：

            //在单链表L中查找元素x
    //若找到，返回指向该节点的指针，否则返回空指针
    LinkList Find(LinkList L, DataType x)
    {
        p = L->next;
        while(p!=NULL){
            if(p->data == x) return p; //找到x
            p = p->next;
        }
        return NULL; //未找到x
    }

        函数体内的另一种写法：

            p = L->next;
    while(p && p->data!=x)
        p = p->next;

    if(p && p->data==x)
        return p; //找到x
    else
        return NULL; //未找到x

        函数体内的第三种写法：

            p = L->next;
    while(p && p->data!=x)
        p = p->next;

    return p; //找到x，为什么可以直接写？

        方法二：

            //在单链表L中查找元素x
    //若找到，返回该元素的位序，否则返回-1
    int Find(LinkList L, DataType x)
    {
        p = L->next; j = 1；
        while(p!=NULL){
            if(p->data == x) return j; //找到x
            p = p->next;
            j++;//计数器随指针改变
        }
        return -1; //未找到x
    }

      3. 查找第i个元素

            LinkList GetElem(LinkList L, int i)
    {
        p = L->next;
        j = 1;
        while(p && j<i){
            p = p->next;
            j++;
        }
        if(p && j==i)
            return p;
        else
            return -1; //未找到x
    }

      4. 查找第i-1个元素

            p=L; j=0;
    while(o && j<i-1){
        p = p -> next; j++;
    }
    if (p && j==i-1)
        return p;
    else
        return -1;

    3. 插入算法(此处应有图)

      技巧：画图辅助分析

      思路：先查找第i-1个元素；若找到，在其后插入新节点

         bool ListInsert(LinkList &L, int i, DataType x){
    //查找第i-1个元素p
    p=L; j=0;
    while(p && j<i-1){
        p = p -> next; j++;
    }
    //若找到，在p后插入x
    if (p && j == i-1)
    {
        s = (LinkList)malloc(sizeof(LNode));
        s->data = x;
        s->next = p->next;//①
        p->next = s;//②
        return TRUE;//插入成功
    }
    else
        return FALSE;//插入失败
}

      注意：

      1. 要让p指向第i-1个而不是第i个元素（否则，不容易找到前驱以便插入）；
      2. 能够插入的条件：p && j == i-1，即使第i个元素不存在，只要存在第i-1个元素，仍然可以插入第i个元素；

      3. 新建节点时需要动态分配内存；

        s=(LinkList)malloc(sizeof(LNode)); 若检查是否分配成功，可用if(s==NULL) exit(1); //分配失败则终止程序；

      4. 完成插入的步骤：①②。技巧：先修改新节点的指针域。

    4. 删除算法(此处应有图)

      思路：先查找第i-1个元素，若找到且其后存在第i个元素，则用x返回数据，并删除之。

      bool ListDelete(LinkList &L, int i, int &x)
{
    //查找第i-1个元素p
    p = L; j = 0;
    while(p && j<i-1){
        p = p->next; j++;
    }
    //如存在第i个元素，则用x返回数据，并删除之
    if(p && j==i-1 && p->next){
        s = p-> next; //①
        p->next=s->next; //②
        x=s->data;
        free(s);
        return TRUE;
    }
    else
        return FALSE;
}

      注意：

      1. 要求p找到第i-1个而非第i个元素。为什么？

      2. 能够进行删除的条件：p && j==i-1 && p->next。条件中的p->next就是要保证第i个元素存在，否则无法删除。若写成p->next && j==i-1也不妥，因为此时，即循环结束时，可能有p==NULL，所以必须先确定p不空。

        技巧：讲条件中的“大前提”放在前面。

        该条件也不可以写成p->next && p && j==i-1，因为先有p!=0才有p->next，上式颠倒了这一关系。

      3. 释放节点的方法：free(s);

      4. 完成删除的步骤：①②

    5. 建立链表的两种方法

      思路：建立空表（头结点），来依次插入数据节点（每次插入表尾得(\(a_{1},a_{2},\dots,a_{n}\))，每次插入表头得(\(a_{n},\dots,a_{2},a_{1}\))）。

      1. 顺序建表

        void CreateLinkList(LinkList &L, int n){
    //建立空表
    L = (LinkList)malloc(sizeof(LNode));
    L->next = NULL; //空表
    p = L; //用p指向表尾
    //插入元素
    for (int i = 0; i < n; ++i)
    {
        scanf(x);
        s = (LinkList) malloc(sizeof(LNode));
        s->data = x;
        //插入表尾
        s->next = p->next;
        p->next = s;
        p = s; //新的表尾
    }
}

      2. 逆序建表

        void CreateLinkList(LinkList &L, int n){
    //建立空表
    L = (LinkList)malloc(sizeof(LNode));
    L->next = NULL; //空表
    //插入元素
    for (int i = 0; i < n; ++i)
    {
        scanf(x);
        s = (LinkList) malloc(sizeof(LNode));
        s->data = x;
        //插入表头
        s->next = L->next;
        L->next = s;
    }
}

4. 循环链表

  1. 特点：最后一个结点的指针指向头结点

  2. 类型定义：同单列表

  3. 基本形态(此处应有图)：空表：L->next == L 非空表：图

  4. 与单链表的联系：判断表尾的方法不同：单链表用 p==NULL，循环链表用p==L，其余操作相同。

5. 双向循环链表

  1. 特点：一个节点包含指向后继next和指向前驱prior两个指针，两个方向又分别构成循环链表。

  2. 类型定义

    typedef struct DuLNode {
    DataType data;
    struct DuLNode *prior, *next; //两个指针
} DuLNode， *DuLinkList;

  3. 基本形态(此处应有图)

    空表：用后向指针判断L-<next==L，或者用前向指针判断L-prior==L
    非空表：图

  4. 与单链表和循环链表的联系

    1. 最大不同：前驱容易求得，可以向前遍历；
    2. 判断表尾的方法与循环链表相同：p==L；
    3. 插入和删除时需要修改两个方向的指针。

  5. 插入删除的相关操作

p之后插入s p之前插入s 删除p之后继承s 删除p
s->next = p->next;
p->next = s;
s->prior = p;
s->next->prior = s;		 s->prior = p->prior;
p->prior = s;
s->next = p;
s->prior->next = s;		 s = p->next;
p->next = s->next;
s->next->prior = p;		 p->prior->next = p->next;
p->next->prior = p->prior;

6. 顺序表与单链表的比较

顺序表 单链表
以地址相邻表示关系 用指针表示关系
随机访问，取元素O(1) 顺序访问，取元素O(n)
插入、删除需要移动元素 时间复杂度：O(n) 插入、删除不用移动元素（用于查找位置） 时间复杂度：O(n)

第三章 栈和队列

一、考纲要求

  1. 了解栈和队列的特点；
  2. 掌握在两种存储结构上栈的基本操作的实现；
  3. 掌握栈的各种应用，理解递归算法执行过程中栈状态的变化过程；
  4. 掌握循环队列和链队列的基本运算；
  5. 会应用队列结构解决实际问题。

二、基本知识

1. 栈

  1. 几个概念：

    栈、栈顶、栈底、空栈、后进先出（LIFO）、入栈（Push）、出栈（Pop）

    链栈：栈的链式存储结构；顺序栈：栈的顺序存储结构。

2. 链栈

  1. 存储结构(此处应有图)：用不带头结点的单链表实现
  2. 类型定义：同单链表

  3. 基本形态(此处应有图)：

    1. 栈空：条件：S==NULL
    2. 栈非空
    3. 栈满

  4. 基本算法

    1. 入栈 Push

      bool Push(LinkList &s, DataType x){
    //新建节点
    p=(LinkList) malloc(sizeof(LNode));
    if(!p) return FALSE;//失败
    p->data = x;
    //插入栈顶
    p->next = s;
    s = p;
    return TRUE;
}

    2. 出栈 Pop

      bool Pop(LinkList &s, DataType &x){
    if (s==NULL) return FALSE;
    //删除栈顶元素
    p = s;
    s = s->next;
    x = p->data;
    free(p);
    return TRUE;
}

    3. 栈顶元素

      前提：栈非空。 

      bool Top(LinkList &s, DataType &x){
    if(s==NULL) return FALSE; //栈空
    x = s->data;
    return TRUE;
}

3. 顺序栈

  1. 存储结构

    类似于顺序表，插入和删除操作固定于结尾。

  2. 类型定义

    简言之：“数组 + 长度”

    具体定义：

    const int MAXSIZE = 栈的最大容量;
typedef struct 
{
    DataType elem[MAXSIZE];
    int top;
} SqStack;

  3. 基本形态

    1. 栈空：条件：s.top == 0;
    2. 栈满：条件：s.top == MAXSIZE;
    3. 栈不空不满

  4. 基本算法

    1. 入栈 Push(&s, x)

      bool Push(SqStack &s, DataType x){
    if(s.top == MAXSIZE) return TRUE;//栈满
    s.elem[top] = x;//或者以下这两句替换为s.elem[top++] = x;
    top++;
    return TRUE;
}

    2. 出栈 Pop(&s, &x)

      bool Pop(SqStack &s, DataType &x){
    if(s.top==0) return FALSE;
    top--; //或者以下这两句替换为x = s.elem[--top];
    x = s.elem[top];
    return TRUE;
}

    3. 栈顶元素

      前提：栈非空, 即是s.elem[top-1]

4. 队列

  1. 几个概念：

    队列、队头、队尾、空队列、先进先出（FIFO）

    链队列：队列的链式存储结构； 循环队列：队列的顺序存储结构之一。

5. 链队列

  1. 存储结构：简言之”单链表+尾指针“

  2. 类型定义

    typedef struct 
{

    LinkList front;
    LinkList rear;
} LinkQueue;

  3. 基本形态

    队列空：Q.front=Q.rear

    非空队列

    （此处应有图）

  4. 基本算法

    1. 入队列

      插入队尾，注意保持Q.rear指向队尾。（课本P62）

    2. 出队列

      删除队头元素。特别注意：如果队列中只有一个元素，则队头也同时是队尾，删除队头元素后也需要修改队尾指针。（课本P62）

6. 循环队列

  1. 存储结构：简言之”数组+头、尾位置“

  2. 类型定义

    const int MAXSIZE = 队列的最大容量;
typedef struct 
{
    DataType elem[MAXSIZE];
    int front, rear; //队头、队尾位置
} SqQueue;

  3. 基本形态

    通常少用一个元素区分队列空和队列满，也可以加一标志。约定front指向队头元素的位置，rear指向队尾的下一个位置，队列内容为[front, rear)。

    1. 队列空

      条件：Q.front==Q.rear

      不能出队列

    2. 队列满

      条件：(Q,rear+1)%MAXSIZE==Q.front(少于一个元素时)

      不能入队列

    3. 队列不空也不满

      （此处应有图）

    4. 加一标志区分队列空和队列满的情况

      可以用满所有空间，队列空和队列满时都有Q.front==Q.rear，再用标志区分。

      队列空：Q.front==Q.rear && Q.tag==0;

      队列满：Q.front==Q.rear && Q.tag==1;

  4. 基本算法

    1. 入队列

      前提：队列不满。

      bool EnQueue(SqQueue &Q, DataType x){
    if((Q.rear+1)%MAXSIZE==Q.front)  return FALSE; // 队列满
    //入队列
    Q.elem[Q.rear]=x;
    Q.rear=(Q.rear+1)%MAXSIZE;
    return TRUE;
}

    2. 出队列

      前提：队列非空。

      bool DeQueue(SqQueue &Q, DataType &x){
    if (Q.front==Q.rear) return FALSE; //队列空
    //出队列
    x = Q.elem[Q.front];
    Q.front = (Q.front+1)%MAXSIZE;
    return TRUE;
}

    3. 队列中元素个数

      结论：(Q.rear-Q.front+MAXSIZE)%MAXSIZE;

      注：Q.rear-Q.front可能小于0，需要加上MAXSIZE

      int QueueLength(SqQueue Q){
    return (Q.rear-Q.front+MAXSIZE)%MAXSIZE;
}

    4. 用标志区分队列空和满

      用标志区分队列空和满时，队列初始化、入队列、出队列和队列长度的算法如下：

      队列初始化：

      void InitQueue(SqQueue &Q){
    Q.front = Q.rear = 0;
    Q.tag = 0;
}

      入队列：

      bool EnQueue(SqQueue &Q, DataType x){
    if (Q.front == Q.rear && Q.tag) return FALSE;
    Q.elem[Q.rear] = x;
    Q.rear = (Q.rear+1)%MAXSIZE;
    if (Q.tag == 0)
        Q.tag = 1;//队列非空
    return TRUE;
}

      出队列：

      bool DeQueue(SqQueue &Q, DataType &x){
    if (Q.front == Q.rear && Q.tag == 0) return FALSE;
    x = Q.elem[Q.front];
    Q.front = (Q.front+1)%MAXSIZE;
    if (Q.front == Q.rear)
        Q.tag = 0; //队列空
    return TRUE;
}

      队列长度：

      int QueueLength(SqQueue Q){
    if (Q.front == Q.rear && Q.tag == 1)
        return MAXSIZE;//队列满
    else
        return (Q.rear-Q.front+MAXSIZE)%MAXSIZE;//队列不满（包含队列空）
}

7. 栈和队列比较

都是线性结构，栈的操作LIFO（后进先出），队列操作FIFO（先进先出）。

8. 简化的栈和队列结构

在算法中使用栈和队列时可以采用简化的形式。

简化栈 简化队列
结构 “s[]+top" 结构 “q[]+front+rear"
初始化 top=0; 初始化 front=rear=0;
入栈 s[top++]=x; 入队列 q[rear]=x; rear=(rear+1)%MAXSIZE;
出栈 x=s[—top]; 出队列 x=q[front]; front=(front+1)%MAXSIZE;
栈顶 s[top-1]; 队列头 q[front];
栈空 top==0 队列空 front==rear;

说明：只要栈(队列)的容量足够大，算法中可以省去检查栈(队列)满的情况。

9. 栈和队列的应用

  1. 表达式求值

    参见课本P53

  2. 括号匹配

    例：检查表达式中的括号是否正确匹配，如{()[]}正确，([)]}错误。

    分析：每个左括号都“期待”对应的右括号，匹配成功则可以消去。

    思路：遇到左括号则入栈，遇到右括号则与栈顶括号相比较，如果匹配则消去，否则匹配失败。当然，如果栈中没有括号可以匹配，或者最后栈中还有未匹配的左括号，也都是匹配错误（失败）。

    //检查表达式中的括号是否正确匹配
bool MatchBrackets()
{
    const int MAXSIZE = 1024;//栈的最大容量
    char s[MAXSIZE];//简化的栈结构
    int top;//栈顶
    //栈初始化
    top = 0;
    //检查括号是否匹配
    ch = getchar();
    while(ch!=EOF){
        switch(ch){
            case '(','[','{':
                s[top++]=ch;//所有左括号入栈
                break;
            case ')':
                if(top==0 || s[--top]!='(') return FALSE;//栈空、右括号和左括号匹配失效等条件
            case ']':
                if(top==0 || s[--top]!='[') return FALSE;
            case '}':
                if(top==0 || s[--top]!='{') return FALSE;
        }
        ch = getchar();//取下一个字符
    }
    if(top == 0)
        return TRUE;//完全匹配
    else
        return FALSE;//有残留的左括号在栈中，匹配失败
}

  3. 地柜程序的非递归化

    将递归程序转化为非递归程序时常使用栈来实现。

  4. 作业排队

    如操作系统中的作业调度中的作业排队，打印机的打印作业也排成队列。

  5. 按层次遍历二叉树

    //按层次遍历二叉树
void LevelOrder(BinTree bt, VisitFunc visit)
{
    const int MAXSIZE = 1024; //队列容量（足够大即可）
    BinTree q[MAXSIZE];//简化的队列结构
    int front,rear;//队头，队尾
    if(!bt) return ;
    //初始化队列，根节点入队列
    front = rear = 0;
    q[rear] = bt;
    rear = (rear+1)%MAXSIZE;
    //队列不空，则去除队头访问并将其左右孩子入队列
    while(front != rear){
        p = q[front];
        front = (front+1)%MAXSIZE;
        if (p)
        {
            visit(p->data);//访问节点
            q[rear] = p->lchild;
            rear = (rear+1)%MAXSIZE;
            q[rear] = p->rchild;
            rear = (rear+1)%MAXSIZE;
        }
    }
}

第四章 串

一、考纲要求

  1. 掌握串的基本运算的定义，了解利用基本运算来实现串的其它运算的方法；
  2. 了解在顺序存储结构和在堆存储结构以及块链存储结构上实现串的各种操作的方法；
  3. 理解KMP算法，掌握NEXT函数和改进NEXT函数的定义和计算。

二、基本知识

1. 概念

串、空串、空格串、串的长度；子串、子串在主串中的位置、主串；串相等

1. 串的基本操作

操作 描述
Assign(s, t), Create(s, cs) Assign(s, t) 将变量t赋值给s, Create(s, cs)根据字串创建变量s。
Equal(s, t), Length(s) Equal(s, t) 判断串相等, Length(s)求串长度，如Length(“”)=0
Concat(s, t) Concat(s, t) 串连接。如Concat(“ab”,”cd”)==“abcd"
Substr(s, pos, len) Substr(s, pos, len) 取子串，pos为开始位置，len为子串长度
Index(s, t) Index(s, t) 求子串t在主串s中的位置。如Index(“abc”,”ab”)=1, Index(“a bc”,”bc”)=3
Replace(s, t, v) Replace(s, t, v) 把串s中的字串t替换成v。如Replace(“aaa”,”aa”,”a”)=“aa”
Delete(s, pos, len) Delete(s, pos, len) 删除串s的一部分

1. 串的存储结构

结构 描述
定长顺序串 最大长度固定，超过最大长度则做截断处理
堆分配存储表示 串的长度几乎没有限制
块链存储表示 块内存储空间连续，块间不连续

第五章 数组和广义表

一、考纲要求

  1. 掌握数组在以行为主和以列为主的存储结构中的地址计算方法；
  2. 掌握矩阵压缩存储时的下标变换方法，了解以三元组表示稀疏矩阵的方法；
  3. 理解广义表的定义及其存储结构，理解广义表的头尾和子表两种分析方法。

二、基本知识

1. 数组的定义

  1. 数组：由一组类型相同、下标不同的变量构成。
  2. 特点：各个元素具有同一类型、下标具有固定上界和下界、基本操作简单（初始化、销毁、修改、存取）。
  3. N维数组：n个下标，每个元素收到n个关系约束；一个n维数组可以看成是由若干个n-1维数组成的线性表。

2. 数组的顺序存储

计算机存储结构是一维的，而数组一般是多维的，那么就要进行一维化：事先约定按某种次序将数组元素排成一列序列，然后将这个线性表存入存储器中。

例如：二维数组可以规定按行存储，也可以规定按列存储。C中采用行优先顺序。

利用一维线性存储的特性，可以计算数组元素的地址计算公式：

\(Loc(j_1, j_2, j_3,\dots, j_n)=Loc(0,0,\dots,0)\)+ 其中\(C_n=L, C_{i-1}=b_i*c_i,1<i\le n\)

N维数组的顺序存储表示：

    #define MAX_ARRAY_DIM 8 //假设最大维数为8
    typedef struct
    {
        ElemType *base; //数组元素及地址
        int dim; //数组维度
        int *bound; //数组各维长度信息保存区基址
        int *constants; //数组映像函数常量的基址
    } Array;

3. 矩阵的压缩存储

为了节省数组元素的存储空间，所谓的压缩存储就是为多个值相同的元素只分配一个存储空间：对0元素不分配空间。若值相同的元素或0元素在矩阵中的分布有一定规律，则称此类矩阵为特殊矩阵；反之，称为系数矩阵（非0元素少）。

那么在稀疏矩阵中如何存储那些非0元素，稀疏矩阵的表示方法：

  1. 三元组：\((i, j, a_{ij})\)

  2. 十字链表：

    （此处应有图）

    down: 同一列中下一非零元素的指针

    right: 同一行中下一非零元素的指针

    每行非零元素链接成带表头结点的循环链表：每列非零元素也链接成带表头结点的循环链表。

  3. 三元组矩阵表：失去时机存储功能

  4. 带辅助向量的三元组表示：增加两个辅助向量。

    记录每行非0元素个数，用NUM(i)表示：每行第一个非0元素在压缩后的三元组中的行号，用POS(i)表示。示例：

    对于稀疏矩阵：

    00 12 09 00 00 00
    00 00 00 00 00 00
    -3 00 00 00 14 00
    00 00 24 00 00 00
    00 18 00 00 00 00

    辅助向量表：

    i 1 2 3 4 5 6
    NUM(i) 2 0 2 1 1 2
    POS(i) 1 3 3 5 6 7

    POS(i)=POS(i-1)+NUM(i-1)

    三元组矩阵表：

    i j v
    6 6 8
    1 2 12
    1 3 9
    3 1 -3
    3 5 14
    4 3 24
    5 2 18
    6 1 15
    6 4 -7

    稀疏矩阵的转置实现方法：压缩转置和快速转置。（以三元组表的形式表示稀疏矩阵）

    压缩转置：反复扫描原表序列，从j=1-n依次进行转置。

    快速转置：生成矩阵三元组表的按列优先的辅助向量，然后实现快速转置。该辅助矩阵中num行记录第col列的非零个数，第一个cpos默认为1，之后的cpos为前一项的col和num之和。

    col 1 2 3 4 5 6
    num[col] 2 2 2 1 1 0
    cops[col] 1 3 5 7 8 8

    利用上面的辅助向量进行转置：遍历非零元素，通过元素的col列查找到相应的cpos[col]即其在转置矩阵中的位置为cpos[col]，将该元素与三元矩阵相应的第cpos[col]交换后将矩阵表中的cpos[col]++和num[col]--

    两个算法的比较：记矩阵中列数为n，非零元素为t，m为总行数，则压缩转置时间复杂度为O(m*t)，快速转置则为O(n+t)。快速转置增设辅助向量，空间换取时间。

4. 广义表的定义

  1. 广义表：元素的值非原子类型，可以再分解，表中元素也可是一个线性表；所有数据元素仍然属于同一数据类型。

  2. 广义表定义：广义表是线性表的推广，也称为列表。记为LS=(a1,a2,...,an)；其中表名为LS，表头为a1，表尾包括了从a2到an。

  3. 约定：① 用小写字母表表示原子类型，用大写字母表示列表；② 第一个元素是表头，而其余元素则组成表尾。

    广义表中元素既可以是原子类型，也可以是列表；当每个元素都为原子且类型相同时，就是线性表。

  4. 特点：

    1. 次序性：每个元素都有一个直接前驱和一个直接后继，首尾有点特殊性
    2. 有长度：表中元素个数
    3. 有深度：表中括号重复
    4. 可递归：自己作为自己的字表
    5. 可共享

5. 广义表的存储结构

通常用链式结构，每个元素用一个结点表示。

  1. 原子节点：表示原子，可设2个域或三个域。例如(tag=0, value)或(tag=0, atom, tp)，其中tp是指向表尾的指针域。

  2. 表结点：表示列表，若表不空，可以分解为表头和表尾。三个域：tag=1，表头指针（指向表头元素），表尾指针（指向表尾列表）。

6. 总结

  1. 数组可以视为一种广义线性表
  2. 数组的存储有行/低地址优先和列/高地址优先两种不同的顺序
  3. 对于稀疏矩阵，有较好的亚索存储和运算方法
  4. 广义表是线性表的推广，也是一种线性结构
  5. 任何一个非空表，表头可能是原子，也可能是列表，但是表尾一定是列表

第六章 树和二叉树

一、考纲要求

  1. 熟练掌握二叉树的结构特点和性质，掌握二叉树各种存储结构及构建方法；
  2. 掌握按先序、中序、后序和层次次序遍历二叉树的算法，理解二叉树的线索化实质和方法；
  3. 利用二叉树的遍历求解实际问题；
  4. 掌握树的各种存储结构及其特点，掌握树的各种运算的实现算法；
  5. 掌握建立最优二叉树和哈夫曼编码的方法。

二、基本知识

1. 树及其有关概念

树、根、子树；结点、结点的度、叶子（终端节点）、分支节点（非终端节点）、内部结点、树的度；孩子、双亲、兄弟、祖先、子孙、堂兄弟；层次（根所在层为第1层）、深度、高度；有序树、无序树（其中二叉树是有序树）；森林

2. 二叉树

二叉树（二叉树与度为2的树不同，二叉树的度可能是0、1、2）；

左孩子、右孩子。

二叉树的五种基本形态。

3. 二叉树的性质

  1. 二叉树的第i层上至多有\(2^{i-1}\)个结点

  2. 深度为k的二叉树至多有\(2^k-1\)个结点

    满二叉树：深度为k，有\(2^k-1\)个结点。
    完全二叉树：给满二叉树的结点编号，从上至下，从左至右，n个结点的完全二叉树中结点在对应满二叉树中的编号正好是从1到n。

  3. 叶子结点\(n_{0}\)，度为2的结点为\(n_{2}\)，则\(n_{0}=n_{2}+1\)

    考虑结点个数：\(n=n_{0}+n_{1}n_{2}\) 考虑分支个数：\(n-1=2n_{2}+n_{1}\) 可得\(n_{0}=n_{2}+1\)

  4. n个结点的完全二叉树深度为\(\lfloor logn \rfloor +1\)

  5. n个结点的完全二叉树，结点按层次编号

    有：i的双亲是\(\lfloor\frac{n}{2}\rfloor\)，如果\(i=1\)时为根（无双亲）；i的左孩子是\(2i\)，如果\(2i>n\)，则无左孩子；i的右孩子是\(2i+1\)，如果\(2i+1>n\)则无右孩子。

4. 二叉树的存储结构

  1. 顺序存储结构：用数组，编号i的结点存放在[i-1]处，适合于存储完全二叉树。

  2. 链式存储结构

    二叉链表：

    typedef struct BTNode
{
    DataType data;
    struct BTNode *lchild, *rchild;
} BTNode, *BinTree;

    三叉链表：

    typedef struct BTNode
{
    DataType data;
    struct BTNode *lchild, *rchild, *parent;
} BTNode, *BinTree;

    （此处应有图）

5. 二叉树的五种基本形态

（此处应有图）

  1. 空树：bt==NULL
  2. 左右子树均空：bt->lchild == NULL && bt->rchild == NULL
  3. 右子树为空：bt->rchild == NULL
  4. 左子树为空：bt->lchild == NULL
  5. 左右子树均非空、前两种常作为递归结束条件，后三者常需要递归。

6. 遍历二叉树

  1. 常见有四种遍历方式

    按层次遍历：先序遍历（DLR）、中序遍历（LDR）、后序遍历（LRD）。“从上至下，从左至右”，利用队列。

  2. 先序遍历算法

    void PreOrder(BinTree bt){
    if (bt)
    {
        visit(bt->data);
        PreOrder(bt->lchild);
        PreOrder(bt->rchild);
    }
}

  3. 中序遍历算法

    void InOrder(BinTree bt){
    if (bt)
    {
        InOrder(bt->lchild);
        visit(bt->data);
        InOrder(bt->rchild);
    }
}

  4. 后序遍历算法

    void PostOrder(BinTree bt){
    if (bt)
    {
        PostOrder(bt->lchild);
        PostOrder(bt->rchild);
        visit(bt->data);
    }
}

  5. 按层次遍历

    思路：利用一个队列，首先将根（头指针）入队列，以后若队列不空则取队头元素p，如果p不空，则访问之，然后将其左右子树入队列，如此循环直到队列为空。

    void LevelOrder(BinTree bt){
    //队列初始化为空
    InitQueue(Q);
    //根入队列
    EnQueue(Q, bt);
    //队列不空则继续遍历
    while(!QueueEmpty(Q)){
        DeQueue(Q, p);
        if(p!=NULL){
            visit(p->data);
            //左右子树入队列
            EnQueue(Q, p->lchild);
            EnQueue(Q, p->rchild);
        }
    }
}

若队列表示为“数组q[]+头尾front, rear”有：

    void LevelOrder(BinTree bt){
        const int MAXSIZE = 1024;
        BinTree q[MAXSIZE];
        int front, rear;
        //队列初始化为空
        front = rear = 0;
        //根入队列
        q[rear] = bt;
        rear = (rear+1) % MAXSIZE;
        //队列不空则循环
        while(front!=rear){
            p = q[front];
            front = (front+1) % MAXSIZE;
            if (p)
            {
                visit(p->data);
                //左右子树入队列
                q[rear] = p->lchild;
                rear = (rear+1) % MAXSIZE;
                q[rear] = p->rchild;
                rear = (rear+1) % MAXSIZE;
            }
        }
    }

  1. 非递归遍历二叉树

    一般借助栈实现，设想一指针沿二叉树中序顺序移动，每当向上层移动时就要出栈。

    1. 中序非递归遍历

      指针p从根开始，首先沿着左子树向下移动，同时入栈保存；当到达空子树后需要退栈访问节点，然后移动到右子树上去。

      void InOrder(BinTree bt, VisitFunc visit){
    InitStack(S);
    p = bt;
    while(p || !StackEmpty(S)){
        if (p)
        {
            Push(S, p);
            p = p->lchild;
        }
        else
        {
            Pop(S, p);
            visit(p);//中序访问节点的位置
            p = p->rchild;
        }
    }
}

    2. 先序非递归遍历

      按照中序遍历的顺序，将访问结点的位置放在第一次指向该结点时。

      void PreOrder(BinTree bt, VisitFunc visit){
    InitStack(S);
    p = bt;
    while(p || !StackEmpty(S)){
        if (p)
        {
            visit(p); //先序访问结点的位置
            Push(S, p);
            p = p->lchild;
        }
        else
        {
            Pop(S, p);
            p = p->rchild;
        }
    }
}

      或者，由于访问过的结点便可以弃之不用，只要能访问其左右子树即可，写出如下算法。

      void PreOrder(BinTree bt, VisitFunc visit){
    InitStack(S);
    Push(S, bt);
    while(!StackEmpty(S)){
        Push(S, p);
        if (p)
        {
            visit(p); 
            Push(S, p->rchild); //先进栈，后访问，所以这里先让右子树进栈
            Push(S, p->lchild);
        }
    }
}

    3. 后序非递归遍历

      后序遍历时，分别从左子树和右子树共两次返回根节点，只有从右子树返回时才访问根节点，所以增加一个栈标记到达结点的次序。

      void PostOrder(BinTree bt, VisitFunc visit){
    InitStack(S);
    InitStack(tag);
    p = bt;
    while(p||!StackEmpty(S)){
        if (p)
        {
            Push(s, p);
            Push(tag, 1);//第一次入栈
        }
        else
        {
            Pop(S, p);
            Pop(tag, f);
            if(f==1){
                //从左子树返回，二次入栈，然后p转右子树
                Push(S, p);
                Push(tag, 2);
                p = p->rchild;
            }
            else
            {
                //从右子树返回（二次出栈），访问根节点，p转上层
                visit(p);
                p = NULL; // 必须的，使下一步继续推栈
            }
        }
    }
}

      注：后序非递归遍历的过程中，栈中保留的是当前结点的所有祖先。这是和先序及中序遍历不同的。在某些和祖先有关的算法中，此算法很有价值。

7.三叉链表的遍历算法

    //中序遍历三叉链表存储的二叉树
    void InOrder(BinTree bt, VisitFunc visit){
        if (bt == NULL)  return ; //空树，以下考虑非空树
        //找到遍历的七点
        p = bt; //注意：这里p!=NULL
        while(p->lchild) p = p->lchild;
        //开始遍历
        while(p){
            //访问结点
            visit(p);
            //p转下一个结点
            if(p->rchild){ // 右子树不空，下一个在右子树
                p = p->rchild;
                while(p->lchild) p = p->lchild; // 转右子树的最左下结点
            }
            else
            { // 右子树为空，下一个在上层
                f = p->parent;
                while(p == f->rchild){ // 若p是右子树则一直上溯
                    p = f;
                    f = f->parent;
                }
            }
        }
    }

7. 遍历二叉树的应用

  1. 写出遍历序列（前、中、后序）（此处应有图）
  2. 根据遍历序列画出二叉树
  3. 编写算法

8. 线索二叉树

  1. 线索

    n个结点的二叉链表中有n+1个空指针，可以利用其指向前驱或后继界定啊，叫线索，同时需附加一个标志，区分是子树还是线索。

    （此处应有图）

    lchild 有左子树，则指向左子树，标志ltag==0；没有左子树，可作为前驱线索，标志ltag==1

    rchild 有右子树，则指向右子树，标志rtag==0；没有右子树，课作为后继线索，标志rtag==1

  2. 线索化二叉树

    利用空指针作为线索指向前驱或后继。左边空指针可以作为前驱线索，右边空指针可以做为后继线索，可以全线索化或部分线索化。

    前驱、后继线索 前驱线索 后继线索
    中序线索化 中序全线索 中序前驱线索 中序后继线索
    前序线索化 前序全线索 前序前驱线索 前序后继线索
    后序线索化 后序全线索 后序前驱线索 后序后继线索

  3. 画出线索二叉树

    思路：先写出遍历序列，再画线索。
    步骤：

    1. 标出必要的空指针（前驱->左指针；后继：->右指针。要点：不要多标，也不要少标）
    2. 写出对应的遍历序列（前序、中序或后序）
    3. 对照遍历结果画线索。

    （此处应有例子）

  4. 遍历线索二叉树

    反复利用孩子和线索进行遍历，可以避免递归。

9. 树和森林

  1. 树的存储结构

    双亲表示法、孩子表示法、孩子兄弟表示法。

  2. 树与二叉树的转换

    树 对应的二叉树
    根 根
    第一个孩子 左孩子
    下一个兄弟 右孩子

    特点：由树转化成的二叉树，根节点没有有孩子

    （此处应有例子）

  3. 森林与二叉树的转换

    森林中第1棵树的根作为对应的二叉树的根；其他的树看做第1棵树的兄弟；森林中的树转换成对应的二叉树。则森林转换成对应的二叉树。

    例：将森林转换成对应的二叉树。课本 P138

  4. 树的遍历

    树的结构：①根 ②根的子树
    先根遍历：①②。例：ABCDEFGHIJK
    后根遍历：②①。例：CEDFBHGJKIA

  5. 遍历森林

    森林的结构：①第一棵树的根 ②第一棵树的子树森林 ③其余树（除第1棵树外）组成的森林。
    先序遍历：①②③。例：ABCDEFGHIJ
    中序遍历：②①③。例：BDCEAGFIJH
    注：先序遍历森林，相当于依次先根遍历每一棵树；中根遍历森林相当于后根遍历每一棵树。

    （此处应有图）

    树 森林 二叉树
    先根遍历 先序遍历 先序遍历
    后根遍历 中序遍历 中序遍历

10. 赫夫曼树及其应用

  1. 最优二叉树（赫夫曼/哈夫曼树）

    树的带权路径长度：所有叶子结点的带权路径长度之和：\(\sum_{k=1}^{n}w_kl_k\)，其中，路径长度\(l_k\)按照分支数目计算。

  2. 构造赫夫曼树

    算法：课本 P145
    简单说：“每次取连个最小的树组成二叉树”

  3. 赫夫曼码（前缀码）

    向左分支为0，向右分支为1，从根到叶子的路径构成叶子的前缀编码。

（此处应有例题）

第七章 图

一、考纲要求

  1. 熟练掌握图的基本概念，会构建各种图的存储结构；
  2. 掌握深度优先搜索遍历图和广度优先搜索遍历图的算法；
  3. 灵活运用图的遍历算法求解各种路径问题，包括最小生成树﹑最短路径﹑拓扑排序﹑关键路径等。

二、基本知识

1. 图的有关概念

图、顶点、弧、弧头、弧尾；
有向图（顶点集+弧集）（\(0\le e\le n(n-1)\)）、无向图（顶点集+边集）；
稀疏图（\(e<nlogn\)）、稠密图；
完全图（\(e=n(n-1)/2\)）、有向完全图；
网、有向网、无向网；
子图、邻接点、顶点的度、入度、出度；
路径、路径长度（经过边或弧的数目）、简单路径、回路（环）、简单回路（简单环）；
连通图、连通分量、强连通分量

2. 图的存储结构

  1. 图的存储结构

    常见的存储结构有：邻接矩阵、邻接表、逆邻接表、十字链表、邻接多重表

    邻接多重表只适用于存储无向图，其他存储结构可以存储无向图和有向图。

  2. 邻接矩阵

    简言之，“数组（顶点）+二维数组（弧）+个数”

    const int MAX_VERTEX = 最大顶点个数;
typedef struct Graph //图
{
    VertexType vexs[MAX_VERTEX]; //顶点向量
    ArcType arcs[MAX_VERTEX][MAX_VERTEX]; //邻接矩阵
    int vexnum, arcnum; //顶点和弧的个数
};

    图：有边（弧）为1；否则为0.网：有边（弧）为权值；否则为\(\infty\)。存储空间个数为\(n^2\)，与边的数目无关。无向图的邻接矩阵是对称的。

A 0 1 1 0 0
B 0 0 1 1 0
C 0 0 0 1 0
D 1 0 0 0 0
E 1 0 0 1 0

  1. 邻接表

    简言之，“数组（弧尾顶点）+链表（邻接点）+个数”

    typedef struct ArcNode
{
    int adjvex; //邻接点
    struct ArcNode *nextarc; //下一个邻接点
} ArcNode;

typedef struct VexNode
{
    VertexType data; //顶点信息
    ArcNode *firstarc; //第一个邻接点
} VexNode;

const int MAX_VERTEX = 最大顶点个数;

typedef struct Graph
{
    VexNode vexs[MAX_VERTEX]; //顶点向量
    int vexnum, arcnum; //顶点和弧的个数
} Graph;

    边（弧）多则需要存储空间多。

    （此处应有图）

  2. 逆邻接表

    简言之，“数组（弧头顶点）+链表（逆邻接点）+个数”。类型定义类似邻接表。

    （此处应有图）

  3. 十字链表

    简言之，“数组（弧尾顶点）+链表（邻接点）+个数”。边可以看做两条弧。

    typedef struct ArcNode //弧结点
{
    int vtail, vhead; //弧尾和弧头顶点编号
    struct ArcNode *nexttail, *nexthead; //指向同弧尾和同弧头的弧结点
} ArcNode;

typedef struct VexNode //顶点结点
{
    VertexType data; //顶点信息
    ArcNode *firstin, *firstout; //指向第一条入弧和第一条出弧
} VexNode;

const int MAX_VERTEX = 最大顶点个数;

typedef struct Graph //图
{
    VexNode vexs[MAX_VERTEX]; //顶点向量
    int vexnum, arcnum; //顶点和弧的个数
} Graph;

    弧结点中包含两个指针分别指向同一弧头的下一个弧和同一个弧尾的下一个弧。顶点结点则指向第一个同弧头和弧尾的弧。十字链表相当于邻接表和逆邻接表的结合。

    技巧：把弧结点按行排列整齐，然后画链表。同弧尾的弧组成链表，同弧头的弧组成链表。

  4. 邻接多重表

    简言之，“数组（顶点）+边结点”。

    typedef struct EdgeNode
{ //边结点
    int vexi, vexj; // 边的两个顶点
    struct EdgeNode *nexti, *nextj; //两个顶点所依附的下一条边
} EdgeNode;

typedef struct VexNode
{ //顶点结点
    VertexType data; // 顶点信息
    EdgeNode *firstedge; // 指向第一条边
} VexNode;

const int MAX_VERTEX = 最大顶点个数;

typedef struct  Graph
{ // 图
    VexNode vexs[MAX_VERTEX]; // 顶点向量
    int vexnum,edgenum; // 顶点和边的个数
} Graph;

    只适合存储无向量图，不能存储有向图。

    （此处应有图）

    技巧：把边结点按列排整齐，然后画链表。相同顶点组成链表，这里没有起点和终点的区别。

3. 图的遍历

  1. 深度优先搜索

    1. 遍历方法

      从图中某个顶点出发，访问此顶点，然后依次从其未被访问的邻接点出发深度优先遍历图；若图中尚有顶点未被访问，则另选图中一个未被访问的顶点作为起始点，重复上述过程，直到图中所有顶点都被访问为止。

    2. 分析方法

      方法：画一棵“深度优先搜索树”

      （例）

    3. 算法

      void DFSTraverse(Graph G){
    visited[0 ... G.vexnum-1] = FALSE; // 初始化访问标志为未访问（FALSE）
    for (int v = 0; v < G.vexnum; ++v)
    {
        if(!visited[v])
            DFS(G,v); // 从未被访问的顶点开始DFS
    }
}

void DFS(Graph G, int v){
    visit(v);
    visited[v]=TRUE; // 访问顶点v并做标记
    for (w = FirstAdjVex(G, v); w >= 0; w=NextAdjVex(G,v,w))
    {
        if (!visited[w])
            DFS(G, w); // 分别从每个未访问的邻接点开始DFS
    }
}

      其中的FirstAdjVex(G, v)表示图G中顶点v的第一个邻接点，NextAdjVex(G,v,w)表示图G中顶点v的邻接点w之后v的下一个邻接点。深度优先搜索算法有广泛的应用，以上算法是这些应用的基础。

  2. 广度优先搜索

    1. 遍历方法

      从图中某顶点出发，访问此顶点之后依次访问其各个未被访问的邻接点，然后从这些邻接点出发一次访问他们的邻接点，并使“先被访问的顶点的邻接点”要先于“后被访问的顶点的邻接点”被访问，直至所有已被访问的顶点的邻接点都被访问。若图中尚有顶点未被访问，则另选图中未被访问的顶点作为起始点，重复以上过程，直到图中所有顶点都被访问为止。广度优先搜索从某顶点出发，要依次访问路径长度为1、2、... 的顶点。

    2. 分析方法

      方法：画一棵“广度优先搜索树”

      （例）

    3. 算法

      利用队列（类似按层遍历二叉树）：

      void BFSTraverse(Graph G){
    visited [0 ... G.vexnum-1] = FALSE; //
    InitQueue(Q);
    for (int v = 0; v < G.vexnum; ++v)
    {
        if (!visited[v])
        {
            //
            visit(v);
            visited[v] = TRUE;
            EnQueue(Q, v);
            while(!QueueEmpty(Q)){
                DeQueue(Q, u);
                for (w = FirstAdjVex(G, v); w >= 0; w=NextAdjVex(G,v,w))
                {
                    if (!visited[w])
                    {
                        visit(w);
                        visited[w] = TRUE;
                        EnQueue(Q, w);
                    }
                }
            }
        }
    }
}

  3. 时间复杂度分析

    观察搜索树可以看出，无论是深度优先搜索还是广度优先搜索，其搜索过程就是对每个顶点求所有邻接点的过程。当用邻接表存储图时，其时间复杂度为\(O(n+e)\)；当采用邻接矩阵作为存储结构时，时间复杂度是\(O(n^2)\)（因为求一个顶点的所有邻接点就是搜索邻接矩阵的一行中的n个树，而顶点的个数为n，总共就是\(n^2\)）

4. 最小生成树

  1. 最小生成树及MST性质

    概念：最小生成树、MST性质

    注意：同一个连通网的最小生成树可能是不唯一的，但其代价都是最小（唯一的）。

  2. 克鲁斯卡尔算法

    一句话，“不构成环的情况下，每次选取最小边”

    （此处应有图）

  3. 普利姆算法

    记V是连通的顶点集，U是求得生成树的顶点集，TE是求的生成树的边集。

    普利姆算法：

    1. 开始时，\(U={v_0},TE=\Phi\)；
    2. 计算U到其余顶点V-U的最小代价，将该顶点纳入，边纳入TE；
    3. 重复上一步直到U=v。

    （例）

  4. 两种算法的比较

算法 普利姆算法 克鲁斯卡尔算法
时间复杂度 \(O(n^2)\) \(O(eloge)\)
特点 只与顶点个数n有关，与边的数目e无关，适用于稠密图 只与边的数目e有关，与顶点个数n无关，适用于稀疏图

5. 拓扑排序

有向无环图（DAG）、AOV网、拓扑排序

拓扑排序，一句话“每次删除入度为0的顶点并输入之”。

（例）

注意：拓扑排序的结果不一定是唯一的。如：ACBDE也是以上DAG图的拓扑有序序列。

6. 关键路径

  1. AOE网、关键路径

    AOE网（活动在边上），边代表活动或任务，顶点代表事件。事件i发生后，其后继活动a(i,*)都可以开始；只有所有先导活动a(*,j)都结束后，事件j才发生。

    （图）

  2. 关键路径算法

    问题：

    1. 整个工程完工需要多长时间？
    2. 哪些活动影响工程进度？或求关键路径。

    事件（顶点）i：最早发生时间ve(i)，最晚发生时间vl(i)；

    活动（边）a(i, j)：最早开始时间e(i, j)，最晚开始时间l(i, j)。

    于是，整个工程完工的时间就是终点的最早发生时间；关键路径就是路径长度最长的路径。

    求关键路径的算法：

    1. 按拓扑有序排列顶点：对顶点拓扑排序
    2. 计算ve(j)：ve(1)=0, ve(j) = max{ve(*)+a(*, j)}，其中*为任意前驱事件；
    3. 计算vl(i)：vl(n)=ve(n), vl(i) = min{vl(*)-a(i, *)}，其中*为任意后继事件；
    4. 计算e(i, j)和l(i, j)：e(i, j)=ve(i), l(i, j)=vl(j)-a(i, j)
    5. 结论：工程总用时ve(n)，关键活动是e(i, j)=l(i, l)的活动a(i, j)。

    说明：

    1. 若只求工程的总用时只要进行步骤i-ii即可求得。
    2. 如何理解计算ve(j)和vl(i)的公式：事件j在所有前驱活动都完成后发生，所以其最早发生时间ve(j)=max{ve(*)+a(*,j)}，即取决于最慢的前驱活动。另一方面，事件i发生后所有后继活动都可以开始了，所以其最晚发生时间vl(i)=min{vl(*)-a(i, *)}，即不耽误最慢的后继活动。

    （例）

7. 最短路径

  1. 迪杰斯特拉算法

    求一个顶点到其他各项顶点的最短路径。

    算法：

    1. 初始化：用起点v到该顶点w的直接边（弧）初始化最短路径，否则设为\(\infty\)；
    2. 从未求得最短路径的终点中选择路径长度最小的终点u：即求得v到u的最短路径；
    3. 修改最短路径：计算u的邻接点的最短路径，若\((v,\dots,u)+(u,w)<(v,\dots,w)\)，则以\((v,\dots,u,w)\)代替。
    4. 重复ii-iii，直到求得v到其余所有顶点的最短路径。

    特点：总是按照从小到大的顺序求得最短路径。

    （例）

  2. 弗洛伊德算法

    求每对顶点之间的最短路径。

    依次计算\(A^{(0)},A^{(1)},\dots A^{(n)},\)。\(A^{(0)}\)为邻接矩阵，计算\(A^{(k)}\)的技巧。第k行、第k列、对角线的元素保持不变，对其余元素，考察A(i, j)与A(i, k)+A(k, j)（“行+列”，即第k列i“行”元素加上第k行j“列”元素）。如果后者更小则替换A(i, j)，同时求改路径。

    （图）

    技巧：当不变行或不变列（即第k行、第k列）某元素为\(\infty\)时，其所在的列或行元素也不变。例如：计算\(A^{(1)}\)时，\(A(2,1)=A(3,1)=\infty\)，所以第2、3行都不变，而A(1,4)=\(\infty\)，所以第4列也不变。这样，只剩下A(4,2)和A(4,3)需要计算了。

8. 动态存储结构

  1. 了解伙伴算法、了解边界标识法
    1. 动态存储管理研究的基本问题：系统如何按用户的要求分配内存；当用户使用完毕，系统如何回收内存。
    2. “占用块”：分配给用户使用的地址连续的内存区。
    3. “空闲块”：未曾分配的地址连续的内存区，也称“可利用空间块”
    4. 可利用空间表：把可利用空间表看做是一个“存储池”，它有以下三种不同的结构形式：
      1. 系统运行期间所有用户请求分配的存储量大小相同；
      2. 系统运行期间用户请求分配的存储量有几种大小的规格；
      3. 系统在运行期间分配给用户的内存块大小不固定。

第八章 查找

一、考纲要求

  1. 熟练掌握各种静态查找和动态查找算法，会计算查找成功时和失败时的平均查找长度；
  2. 掌握二叉排序树的建立、插入和删除过程，掌握二叉平衡树的建立和旋转平衡方法；
  3. 掌握B-树的建立、插入和删除结点的过程；
  4. 熟练掌握哈希表的构造方法和处理冲突的方法。

二、基本知识

1. 查找的有关概念

查找表、静态查找表（只进行“查找”）、动态查找表（可“查找”、“插入”、“删除”）、关键词、平均查找长度

\(ASL=\sum_{i=1}^{n}p_i c_i\)

其中 ,\(p_i\)第i个关键字出现的概率，\(c_i\)比较的关键字的个数。

静态查找表：顺序查找表、折半查找表、静态树表、次优查找树、索引顺序表。

动态查找表：二叉排序树、平衡二叉树（AVL树）、B-树、B+树、键树、哈希表。

2. 顺序查找

  1. 思路：按顺序逐个比较，直到找到或找不到

  2. 算法：程序，灵活运用

    例如，在数组a的前n个元素中查找x

    int Search(int a[], int n, int x){
    for (int i = n-1; i >= 0; i--)
    {
        if (a[i]==x)
            return i;
        return -1; //-1表示找不到
    }
}

    编程技巧：所有执行路径都要有正确的返回值，不要忘记最后那个return语句。

    应试技巧：题目要求不明确时，按照方便的方法做，用适当的注释说明。

  3. 分析

    顺序查找特点：思路简单（逐个比较）、适用面广（对查找表没有特殊要求）

    1. 平均查找长度

      一般在等概率情况下，查找成功时，平均查找长度：\(ASL=\frac{1+2+\dots+n}{n}=\frac{n+1}{2}\)。思路：假设对每个元素进行1次查找，共进行n次查找，计算出进行比较的关键字的个数，然后除以查找次数n，就求得平均查找长度。

      例：10个元素的表等概率情况下查找成功时的平均查找长度\(ASL=\frac{1+2+\dots+10}{10}=5.5\)

    2. 判定树

      判定树是一种描述查找中比较过程的直观形式，每个关键词所在层次就是其查找长度，有利于分析查找过程。顺序查找的判定树是一颗深度为n的单分支的树。课本上顺序查找从\(a_n\)开始，当然也可以从\(a_1\)开始。

    3. 时间复杂度

      从平均查找长度看顺序查找的时间复杂度是O(n)。

3. 折半查找

  1. 思路

    待查找的表必须是有序的，先从中间开始比较，比较一次至少抛弃一般元素，逐渐缩小范围，知道查找成功或失败。

  2. 算法

    要熟练掌握该算法。设a[]升序有序，有以下算法：

    int BinarySearch(DataType a[], int n, DataType x){
    low = 0;
    high = n-1;
    while(low <= high){
        mid = (low+high)/2; //折半
        if(a[mid]==x)
            return mid; //找到
        else if (x<a[mid])
            high=mid-1;//x位于低半区[low...mid-1]
        else
            low=mid+1;//x位于高半区[mid+1...high]
    }
    return -1;//-1表示未找到
}

    或者有递归版本：

    int BinarySearch(DataType a[], int low, int high, DataType x){
    if (low>high)
        return -1;//查找失败
    mid = (low+high)/2;//折半
    if (a[mid]==x)
        return mid;//找到
    else if(x<a[mid])
        return BinarySearch(a, low, mid-1, x);
    else
        return BinarySearch(a, mid+1, high, x);
}

    另外，程序可有多种写法。

    （例）

  3. 分析

    特点：速度很快，要求查找表是有序的，而且随机访问（以便计算折半的下标）。所以，链表不能进行折半查找（但可以采用二叉排序树等形式进行快速的查找）。

    1. 判定树

      折半查找的判定树类似于完全二叉树，叶子结点所在层次之差最多为1，其深度为\(\lfloor logn\rfloor+1\)。查找过程就是走了一条从根到该结点的路径。

      （例）

    2. 平均查找长度

      结论：等概率查找成功时的平均查找长度：\(ASL_{bs}=\frac{1}{n} \sum_{j=1}^{h}j2^{j-1}=\frac{n+1}{n}log(n+1)-1\thickapprox^{n>50}log(n+1)-1\)

      分析方法：对等概率情况，假设查找n次，且每个查找1次，共比较关键字c次，则平均\(\frac{c}{n}\)次。

      例：表长为n=10，平均查找长度如下：\(ASL=\frac{3+2+3+4+1+3+4+2+3+4}{10}=\frac{29}{10}=2.9\)

    3. 时间复杂度

      结论：O(logn)，根据平均查找长度计算。

      有时对需要反复查找的数据预先排序，再折半查找也是划算的。比如有1000个数据，顺序查找100次，平均比较约\(100\times500=50000\)次；快排大约比较\(1.44nlogn=1。44\times1000\times10=14400\)，100次折半查找比较不超过\(100\times9\times2=1800\)次（考虑到同一关键字的两次比较），排序后折半查找合计比较不超过大约16200次。

4. 索引顺序表

分块，块间有序+块内无序，对应索引表有序+顺序表（无序）。索引顺序表的查找性能介于顺序查找与折半查找之间。

分块的最佳长度是是多少？

规定条件：每块的大小相同，对块索引表和块内查找均采用顺序查找。设表长为n，等分成b块，采用顺序查找确定块需要比较\(\frac{b+1}{2}\)次，块内顺序查找比较\(\frac{\frac{n}{b+1}}{2}\)次，总共\(C(b)=\frac{b+1}{2}+\frac{\frac{n}{b+1}}{2}\)，要使C(b)最小，有\(b=\sqrt{n}\)。

5. 二叉树排序

  1. 二叉排序树

    二叉排序树或为空树；或者是这样一棵二叉树，若左子树不空，则左子树上所有结点均小于根节点，若右子树不空，则右子树上所有结点均大于根节点，其左、右子树也是二叉排序树。

    技巧：如果中序遍历二叉树，得到的结果将从小到大有序。手工判别二叉排序树的方法之一。

    （例）

  2. 查找

    思路：

    1. 若二叉树为空，则找不到
    2. 先与根比较，相等则找到，否则若小于根则在左子树上继续查找，否则在右子树上继续查找。

    递归算法：

    BstTree BstSearch(BstTree bst, DataType x){
    if (bst==NULL)
        return NULL;
    else if (bst->data==x)
        return bst;
    else if (x<bst->data)
        return BstSearch(bst->lchild, x);
    else
        return BstSearch(bst->rchild, x);

}

    非递归算法：

    BstTree BstSearch(BstTree bst, DataType x){
    p = bst;
    while(p){
        if (p->data==x)
            return p;
        else if (x<p->data)
            p = p->lchild;
        else
            p = p->rchild;
    }
    return NULL;//没有找到
}

  3. 插入

    思路：先查找，若找不到则插入结点作为最后访问的叶子结点的孩子。新插入的结点总是叶子。

  4. 建立

    经过一系列插入操作可以建立二叉排序树。

    给定关键词序列，建立二叉排序树。方法：

    1. 开始二叉树为空
    2. 对每一个关键字，先进行查找，如果已存在，则不作任何处理，否则插入。

    一句话：“从空树开始，每次插入一个关键字”。

    （例）

  5. 删除

    1. 叶子：直接删除即可。（图）
    2. 左子树或右子树为空：“移花接木”：将左子树或右子树接到双亲上。（图）
    3. 左右子树都不空：“偷梁换柱”：借左子树上最大的结点替换被删除的结点，然后删除左子树最大结点，（或者借用右子树上最小结点然后删除之亦可）（图）

  6. 分析

    判定树和二叉排序树相同。结点的层次等于查找时比较关键字的个数。

    （图）

    若按照关键字有序的顺序插入结点建立二叉排序树，将得到一棵单支树，对其进行查找也退化为顺序查找，平均查找长度为\(\frac{1+n}{2}\)。一般的，如果在任一关键字k之后插入二叉排序树的关键字都大于或都小于k，则该二叉排序树是单分支的，深度是n，查找效率和顺序查找相同。

6. 平衡二叉树

  1. 平衡因子和平衡二叉树（AVL）

    平衡因子：左子树深度-右子树深度。平衡二叉树中各个结点的平衡因子只能是0、1、-1.

  2. 构造平衡二叉排序树

    思路：按照建立二叉排序树的方法逐个插入结点，失去平衡时作调整。

    失去平衡时的调整方法：

    1. 确定三个代表性结点。（A是失去平衡的最小子树的根；B是A的孩子；C是B的孩子，也是新插入结点的子树）。关键是找到失去平衡的最小子树。
    2. 根据三个代表性结点的相对位置（C和A的相对位置）判断是哪种类型（LL、LR、RL、RR）
    3. 平衡化。“先摆好三个代表性结点（居中者为根），再接好其余子树（根据大小）”

    （图）*（例）

  3. 分析

    1. 查找（同二叉排序树）

    2. 平均查找长度ASL

      结论：平均查找性能O(log n)

      为求得n个结点的平衡二叉树的最大高度，考虑高度为h的平衡二叉树的最少结点数。

      \(N_{h}=\lbrace{0,h=0\\1,}\)

      部分结果如下，\(F_h\)表示斐波那契数列第h项。

      （表）

      观察可以得出\(N_h=F_{h+2}-1,h\geq0\)，解得\(h=log_\varphi(\sqrt{5}(n+1))-2\approx1.44log(n+1)-0.328\).其中\(\varphi=(\frac{\sqrt{5}+1}{2})\)。

    3. 时间复杂度

      一次查找经过根到某结点的路径，所以查找的时间复杂度是O(logn)

7. B-树与B+树

  1. B-树：一棵m阶B-树，或为空树，或满足：

    1. 每个结点至多有m棵子树；
    2. 若根结点不是叶子，则至少有两棵子树；
    3. 除根之外的所有非终端结点至少有\(\lceil \frac{m}{2} \rceil\)棵子树；
    4. 所有非终端结点包含n个关键字和n+1棵子树：\((n, A_0,K_1,A_1,\dots,K_n,A_n)\)，其中关键字满足\(A_0 <K_1 <A_1 <\dots <K_n <A_n\)，关键字的个数\(\lceil \frac{m}{2} \rceil-1 \leq n\leq m-1\)。
    5. 所有叶子在同一层，不含信息，表示查找失败。

  2. B+树

    B+树和B-树的差异：n棵子树的结点中含有n个关键字；所有叶子结点中包含了全部关键字，且按大小顺序排列；所有非终端结点都是索引。

    对B+树既可以进行顺序查找又可以进行随机查找。

8. 键树

又叫数字查找树。常见的两种存储结构：孩子兄弟链表，多重链表。

9. 哈希表

  1. 哈希表（散列表、杂凑表）

    根据设定的哈希函数和处理冲突的方法，将一组关键字映像到一个有限的连续的地址集上，并以关键字在地址集中的象作为记录在表中的存储位置，这种表称为哈希表，又叫做散列表、杂凑表。

  2. 哈希函数

    常用除留余数法：H(key)=key MOD p

  3. 冲突

    什么是冲突？\(H(key_1)=H(key_2)\)，且\(key_1\neq key_2\)，称冲突。

    处理冲突的方法：当\(H(key)\)处已有记录，出现冲突，如何处理？

    1. 开放定址法

      试用\(H(key)\oplus d_i\)，常见以下三种：

      1. 线形探测再散列：试用\(H(key)\oplus 1, H(key)\oplus 2,\dots\)
      2. 二次探测再散列：试用\(H(key)\oplus 1^2, H(key)\oplus -1^2, H(key)\oplus 2^2, H(key)\oplus -2^2,\dots\)
      3. 伪随机探测再散列：试用\(H(key)\oplus f(1), H(key)\oplus f(2),\dots\)

    2. 再哈希法

      \(H_1(key)\)冲突，试用\(H_2(key), H_3(key), \dots\)

    3. 链地址法

      发生冲突的记录链成单链表。

    4. 建立公共溢出区

      所有冲突记录存储溢出区。

  4. 装填因子

    \(\alpha=\frac{n}{m}\)，n个记录，m个地址空间。哈希表的平均查找长度与记录个数n不直接相关，而是取决于装填因子和处理冲突的方法。

  5. 举例

    （例）

第九章 排序

一、考纲要求

  1. 掌握各种排序算法，包括插入类、交换类、选择类、归并类排序及基数排序；
  2. 能够对各种排序方法进行比较分析，如稳定性、时间和空间性能等，了解各种排序方法的特点和不同并灵活应用；
  3. 理解外部排序的主要思想和过程。

二、基本知识

1. 排序的有关概念

排序：按关键字大小顺序排列数据。

排序方法：内部排序、外部排序；简单的排序方法\(O(n^2)\)、先进的排序方法\(O(nlogn)\)、基数排序\(O(dn)\)；插入排序、交换排序、选择排序、归并排序、计数排序。

排序方法的稳定性：取决于该方法采取的策略，不是由一次具体的排序结果决定的。但是通过列举不稳定的排序实例可以说明该排序算法的不稳定性。

2. 直接插入排序

  1. 思路

    将待排序记录插入已排好的记录中，不断扩大有序序列。一句话：将待排序记录插入有序序列，重复n-1次。

    （例）

  2. 分析

    比较 移动
    记录顺序有序时 n-1 0 最好
    记录逆序有序时 \(\frac{(n+2)(n-1)}{2}\) \(\frac{(n+4)(n-1)}{2}\) 最坏

3. 折半插入排序

  1. 思路

    在直接插入排序中，查找插入位置时采用折半查找的方法。

  2. 程序

    void BinInsertSort(T a[], int n){
    for (int i = 0; i < n; ++i)
    {
        // 在a[0...i-1]中折半查找插入位置使a[high]<=a[i]<a[high+1...i-1]
        low = 0;
        high = i-1;
        while(low<=high){
            m = (low+high)/2;
            if (a[u]<a[m])
                high = m-1;
            else
                low = m+1;
        }
        // 向后移动元素a[high+1...i-1]，在a[high+1]处插入a[i]
        x=a[i];
        for (int j = i-1; j > high; ++j)
        {
            a[j+1] = a[j];          
        }
        a[high+1] = x;// 完成插入
    }
}

  3. 分析

    时间复杂度\(O(n^2)\)，比直接插入排序减少了比较次数，折半插入排序是稳定的排序算法。

4. 希尔排序（缩小增量排序）

  1. 思路

    先将待排序分割成若干个子序列，分别进行直接插入排序，基本有序后再对整个序列进行直接插入排序。

    步骤：

    1. 分成子序列（按照增量dk）；
    2. 对子序列排序（直接插入排序）；
    3. 缩小增量，重复以上步骤，直到增量dk=1.

    增量序列中最后一个增量一定是1，入：...,9,5,3,2,1和...13,4,1。如没有明确说明增量序列可以选择...,3,2,1或...,5,3,2,1

    （例）

  2. 程序

    void ShellSort(T a[], int n){
    dk = n/2;
    while(dk >= 1){
        // 一趟希尔排序，对dk个序列分别进行插入排序
        for (int i = dk; i < n; ++i)
        {
            x = a[i];
            for (int j = i-dk; j >= 0 && x < a[j]; j-=dk)
                a[j+dk] = a[j];
            a[j+dk] = x;
        }
        // 缩小增量
        dk = dk/2;
    }
}

5. 冒泡排序

  1. 思路

    一句话：“依次比较相邻元素，‘逆序’则交换，重复n-1次”。

  2. 程序

    请参考BubbleSort

  3. 分析

    比较和交换总是发生在相邻元素之间，是稳定的排序算法。时间复杂度为\(O(n^2)\)。

6. 快速排序

  1. 思路

    一趟排序把记录分割成独立的两部分，一部分关键字均比另一部分小，然后再分别对两部分快排。

    （例）

  2. 程序

    void QuickSort(T a[], int low, int high){
    if(low < high){
        // 划分
        pivot = a[low];
        i = low;
        j = high;
        while(i < j){
            while(i < j && a[j] >= pivot)
                j--;
            a[i] = a[j];
            while(i < j && a[i] <= pivot)
                i++;
            a[j]=a[i];

        }
        a[i] = pivot;
        // 对子序列快排
        QuickSort(a, low, i-1);
        QuickSort(a, i+1, high);
    }   
}

  3. 分析

平均情况下，时间复杂度\(O(nlogn)\)。记录本来有序时为最坏情况，时间复杂度为\(O(n^2)\)。空间复杂度（考虑递归调用的最大深度）在平均情况下为\(O(logn)\)，在最坏情况下为\(O(n)\)。快速排序是不稳定的。

7. 简单选择排序

  1. 思路

    第i趟排序过程是在剩余的待排记录中选一个最小（大）的，放在第i个位置。一句话，“在待排记录中选取最小的，交换到合适位置，重复n-1次”。

    （例）

  2. 程序

    void SelectionSort(T a[], int n){
    for (int i = 0; i < n-1; ++i)
    {
        k = i;
        for (int j = i+1; j < n; ++j)
        {
            if(a[j] < a[k])
                k = j; // 最小记录
        }
        if (k != i)
        {
            int temp;
            temp = a[i];
            a[i] = a[k];
            a[k] = temp;
        }
    }
}

  3. 分析

8. 堆排序

  1. 堆及其特点

    堆、小顶堆、大顶堆

    序列\({K_1,K_2,\dots,K_n}\)满足\(K_i\leq K_{2i},K_i\leq K_{2i+1}\)，称为小顶堆；若满足\(K_i\geq K_{2i},K_i\geq K_{2i+1}\)，称为大顶堆，其中\(i=1,2,\dots,\frac{n}{2}\)

    特点：小顶堆的堆顶（第一个元素）为最小元素，大顶堆的堆顶为最大元素。

  2. 判断序列是否构成堆

    方法：用\(K_i\)作为编号为i的结点，画一棵完全二叉树，比较双亲和孩子容易判断是否构成堆。

    （例）

  3. 建立堆

    一句话，“‘小堆’变‘大堆’，从\(\lfloor \frac{n}{2} \rfloor \)变到1”。第\(\lfloor \frac{n}{2} \rfloor \)个是最后一个分支结点。

    （例）

  4. 堆排序

    思路：（图）

    （例）

9. 归并排序

  1. 思路

    归并：两个或多个有序表合并成一个有序表。

  2. 程序

    归并排序：

    void MergeSort(T a[], int low, int high){
    if (low >= high)
        return ;
    else
    {
        mid = (low + high)/2;
        MergeSort(a, low, mid);
        MergeSort(a, mid+1, high);
        Merge(a, low, mid, high);
    }
}

    自顶向上的归并排序：

    void MergeSort(T a[], int n){
    t = 1;
    while(t < n){
        s = t;
        t = s*2;
        for (int i = 0; i+t < n; i+=t)
            Merge(a, i, i+s-1, i+t-1);
        if(i+s < n)
            Merge(a, i, i+s-1, n-1);
    }
}

    附：Merge(),将有序序列a[low..mid]和a[mid+1...high]归并到a[low...high]。

    void Merge(T a[], int low, int mid, int high){
    // 归并到b[]
    i = low;
    j = mid + 1;
    k = low;
    while(i <= mid && j <= high){
        if (a[i] <= a[j])
        {
            b[k] = a[i];
            i++;
        }
        else
        {
            b[k]=a[j];
            j++;
        }
        k++;
    }
    // 归并剩余元素
    while(i <= mid)
        b[k++] = a[i++];
    while(j <= high)
        b[k++] = a[j++];
    //从b[]复制回a[]
    a[low...high] = b[low...high];
}

  3. 分析

    时间复杂度\(O(nlogn)\)。需要空间多，空间复杂度\(O(n)\)。归并排序是稳定的排序。

10. 基数排序

  1. 思路

    1. 多关键字排序

      最高位有限（马上到！）、最低位有限（LSD）

    2. 链式基数排序

      链式基数排序采用“分配”和“收集”策略。

      （例）

  2. 分析

    对n个数据进行基数排序，每个数据基数为rd，有d位数字。那么，一趟分配和收集用时n+rd（分配用n，收集用rd），共需d趟，总的时间复杂度为\(O(d(n+rd))\)。

11. 各种排序比较

（表）

12. 外部排序

  1. 外部排序三种方式
  2. 外部排序主要思想与过程
  3. 构建最大败子树


« 个人设想的毕业设计思路
创建网站咯~ »

Copyright © 2015 Powered by MWeb,  Theme used GitHub CSS.

TOP