MENU

Catalog

算法与数据结构课程笔记

February 27, 2020 • 学习

新学期要学习算法与数据结构的课程,在此开篇,用于记录一些学习内容,以备考试。

内容一般不包括实际代码,算法采用文字或类 C 进行描述

本文已基本完成,如有错误欢迎在下方留言指出,谢谢。

如何理解数据结构?

数据结构需要分为两个层次去理解:

逻辑结构——从具体问题抽象出的数学模型
存储结构——数据元素及其关系在计算机中的存储方式

逻辑结构

分为四类基本的逻辑结构,集合、线性、树、图。

graph TD
    A[数据的逻辑结构] -->B(线性结构)
    A[数据的逻辑结构] -->C(非线性结构)
    B --> D(线性表)
    D --> E(一般线性表)
    D --> F(特殊线性表)
    D --> G(线性表推广)
    E --> H(线性表)
    F --> I(栈)
    F --> J(队列)
    F --> K(字符串)
    G --> L(数组)
    G --> M(广义表)
    C --> N(树结构)
    C --> O(图结构)
    N --> P(树)
    N --> Q(二叉树)
    O --> R(有向图)
    O --> S(无向图)

存储结构

分为两种:顺序存储结构、链式存储结构。

顺序存储结构例子:数组

链式存储结构例子:链表(每一个元素都会存储自身数据以及其他数据的地址)

抽象数据类型(ADT)

可以由三元组来表示 $ \text{ADT}= (D,R,P) $

$ D $ 表示数据对象

$ R $ 表示 D 上的关系集合

$ P $ 表示 D 上的数据操作

定义方式:

ADT抽象数据类型名{
    数据对象:(数据元素集合)
    数据关系:(数据关系二元组结合)
    基本操作:(操作函数的罗列)
};ADT抽象数据类型名;

算法

算法是一个有穷的指令集,是一个用来完成特定任务规定的一个运算序列。

算法评价

评价维度:正确性,可读性,健壮性,高效性

算法效率

时间复杂度,用该算法执行消耗的时间来进行度量,可采取事后统计或事前分析估计。

事后统计

利用计算机内的计时功能,但由于计算机运行消耗时间由:算法选用策略、问题规模、程序语言、编译器生产的机器代码质量、指令执行速度,五个方面来共同决定

事前分析估计

针对算法中语句执行次数进行估计,而不是真实的运行时间。

算法的规模:求解问题的输入量,用$ n $来表示。而决定算法规模$ n $复杂性的函数用$ f(n) $来表示,一般是算法中最大的语句频度。

时间复杂度:是算法的执行时间,也是$ n $的函数,用$ T(n) $来表示

当问题规模$ n \rightarrow \infty $时,$ T(n) $的数量级的增长率和$ f(n) $的增长率相同,因此可以说:

$$ T(n) = O(f(n)) $$

所以,算法的时间复杂度通常是由最深嵌套层内的语句的频度决定的。

算法的时间复杂度有如下几种类型:

类型表示
常数阶$ O(1) $
对数阶$ O(log_2(n)) $
线性阶$ O(n) $
线性对数阶$ O(n log_2(n)) $
平方阶$ O(n^2) $
立方阶$ O(n^3) $
$ K $次方阶$ O(n^K) $
指数阶$ O(2^n) $
分析实例

例子一:

for( i = 1; i <= n; i++){
    for( j = 1; j <= n; j++){
        c[i][j] = 0;
        for( k = 1; k <= n; k++){
            c[i][j] = c[i][j] + a[i][k] * b[l][j];
        }
    }
}

$$ T(n) = \sum_{i = 1}^n \sum_{j = 1}^n \sum_{k = 1}^n (1) = n^3 = O(n^3) $$

例子二:

for( i = 1; i <= n; i++){
    for( j = 1; j <= i; j++){
        for( k = 1; k <= j; k++){
            x = x + 1;
        }
    }
}

$$ T(n) = \sum_{i = 1}^n \sum_{j = 1}^i \sum_{k = 1}^j (1) = \frac{n(n+1)(n+2)}{6} $$

$$ T(n) = O(n^3) \text{(最高次依旧是)} n^3 $$

例子三:

i = 1;
while(i<=n){
    i = i * 2;
}

$$ 2 ^{f(n)-1} \leq n \Rightarrow f(n) \leq log_2n + 1 $$

取最大值

$$ f(n) = log_2n $$

$$ T(n) = O(log_2n) $$

$T(n)$总结

当时间复杂度大于立方阶 $ O(n^3) $ 之后,一旦进入指数阶,算法所需时间将与方阶非常悬殊。应当在设计算法时避免这类情况。

注:指数阶内算法时间复杂度: $ O(2^n) \lt O(n!) \lt O(n^n) $

算法的空间复杂度(非重点)

算法所需的存储空间的度量,记作:$ S(n) = O(f(n)) $

占据的空间包括:IO,指令,常数,变量等,以及辅助空间。

如果输入数据所占空间与算法无关,则无需考虑。

线性表

首先抛出问题,什么是线性表?

一个线性表是 n 个具有相同特性的数据元素的有限序列

在一系列数据元素中,如:

$$ a_1, a_2 \cdots a_{i-1}, a_i, a_{i+1} \cdots a_n $$

则有 $a_1$为线性表起点, $a_n$为线性表终点,可把$a_{i-1}$称为$a_i$ 的直接前趋,把$a_{i+1}$称为$a_i$ 的直接后继。$n$为表长,$n =0$ 可称为空表。

逻辑特性

对于一个非空线性表来说满足以下逻辑结构特性:

存在唯一一个被称为“第一个”的数据元素

存在唯一一个被称为“最后一个”的数据元素

除第一个之外,结构中的每一个数据元素均只有一个前趋

除最后一个之外,结构中的每一个数据元素均只有一个后继

线性表特性:

同一性:由同类数据元素组成

有穷性:由有限个数据元素组成

有序性:相邻元素之间存在序偶关系

线性表是一种比较常见的数据结构,如矩阵、数组,字符串、堆栈,队列都符合线性表特性。

抽象数据类型定义

数据对象:$ D = \{ a_i | a\in{ElemSet}, i =1,2,\cdots,n,n \geq 0 \} $,

数据关系:$ R = \{<a_{i-1},a_i> | a_{i-1},a_i \in D, i = 2, \cdots , n \} $

基本操作

初始化线性表,销毁线性表,清空线性表,求线性表的长度,判断是否为空,获取线性表中某个数据元素内容,检索值为 e 的数据元素,在线性表中插入元素,在线性表中删除元素,获取前趋元素,获取后继元素。

补充:C 语言的内存操作函数

stdlib.h中:

malloc(m);开辟 m 字节长度的地址空间,并返回首地址;

sizeof(x)计算变量 x 的长度;

free(p)释放指针 p 所指的变量内存空间(彻底删除);

new 类型名 T (初值列表)申请用于存放 T 类型对象的内存空间,并根据初值列表赋初值,如失败返回NULL

delete p释放指针 p 指向的内存,和new一起使用;

线性表的存储

顺序存储

顺序存储,每一个元素在内存中连续相邻,可称为顺序表,如数组。

这种方式可称为随机存取结构,即可以随时读取线性表中的任何一个元素。

$$ Loc(a_i)=Loc(a_1)+(i-1)*k $$

C 语言描述

##define MAXSIZE 100
typedef struct{
    ElemType *elem;
    int length
}SqList;
SqList L;

那么在连续内存中,前一部分均为元素,末尾内存区域存储表长。

顺序表基本操作

本节描述,基于以下定义:

##define MAXSIZE 100
typedef struct{
    ElemType *elem;
    int length
}SqList;
SqList L;
构造
Status InitList_Sq(SqList &L){
    L.elem = new ElemType[MAXSIZE];
    if(!L.elem){
        exit(OVERFLOW);
    }
    L.length = 0;
    return OK;
}
释放
void DestoryList(SqList &L){
    if(L.elem){
        delete(L.elem);
    }
}
清空
void ClearList(SqList &L){
    L.lenth = 0;
}
顺序表长度
int GetLength(SqList L){
    return L.length; 
}
是否为空
int IsEmpty(SqList L){
    if (L.length == 0)
        return 1;
    else
        return 0;
}
元素查找
//获取相应位置的元素内容
int GetElem(SqList L, int i, ElemType &e){
    if (i<1 || i>L.length)
        return ERROR;
    e = L.elem[i-1];
    return OK;
}
//根据指定数据进行查找,返回位置。时间复杂度为O(n)
int LocateElem(SqList L, ElemType e){
    for (int i = 0; i < L.length; i++){
            if (L.elem[i] == e){
                return i + 1;
            }  
    }
    return 0;
}
元素插入

算法描述如下:

1.将 $ a_i \sim a_n $ 顺序向下移动,为新元素让出位置。

2.将 $x$ 置入空出的第 $i$个位置

3.表长自增

Status ListInsert_Sq(SqList &L, int i, ElemType e){
    if(i < 1 || i > L.length + 1){
        return ERROR;
    }
    if(L.length == MAXSIZE){
        return ERROR;
    }
    for(j = L.length; j >= i; j--){
        L.elem[j+1] = L.elem[j];
    }
    L.elem[i-1] = e;
    L.length++;
    return OK;
}

在这个插入代码中,时间开销主要在移动元素的操作,需要遍历一部分元素,若插入在表尾,执行速度较快,反之几乎需要遍历所有元素。则平均移动次数为

$$ AMN = \frac{1}{n+1}\sum^{n+1}_{i = 1}(n-i+1) \\ = \frac{1}{n+1}(n+\cdots+1+0) \\ = \frac{1}{n+1}\frac{n(n+1)}{2} \\ = \frac n2 $$

删除元素

如果能理解插入元素,那么删除元素就比较好理解了。

Status ListDelete_Sq(SqList &L, int i, ElemType e){
    if(i < 1 || i > L.length){
        return ERROR;
    }
    e = L.elem[i-1];
    for(j = i; j <= L.length; j++){
        L.elem[j-1] = L.elem[j];
    }
    --L.length;
    return OK;
}

$$ AMN = \frac{1}{n}\sum^{n}_{i = 1}(n-i) \\ = \frac{1}{n}\frac{n(n-1)}{2} \\ = \frac{n-1}2 $$

空间复杂度:

$$ S(n) = O(1) \\ \text{没有占用辅助空间} $$

顺序表优缺点
  • 优点

    • 存储密度大
    • 可以随机存取表中的任意元素
  • 缺点

    • 在插入、删除某一元素,需要大量移动元素。
    • 浪费存储空间(申请了内存但不一定全部使用)
    • 属于静态存储形式,数据元素的个数不可以自由扩充。

链式存储

1.用一组任意的存储单元存放线性表的数据元素(这组内存单元可以连续,也可以不连续)

2.为表示数据元素之间的逻辑关系,还需要有存储一个指示后继的信息——指针

3.由数据域和指针域构成的数据元素的存储映像,成为节点(node)。

C 语言描述

typedef struct LNode{
    ElemType data; //数据域
    struct LNode *next; //指针域
}LNode, *LinkList;
//*LinkList为LNode类型的指针
术语
术语解释
结点数据元素的存储映像,由数据域和指针域两部分组成
链表n 个结点由指针链组成一个链表他是线性表的链式存储映像,成为线性表的链式存储结构。
单链表结点只有一个指针域的链表,称为单链表或线性链表。
双链表结点有两个指针域的链表。
循环链表首尾相接的链表
头指针指向链表中第一个结点的指针
首元结点指链表中存储第一个数据元素$a_1$的一个结点,数据域内只放空表标志和表长等信息。

无头结点时,初始指针指向第一个元素地址。可以引入头结点来存储一些信息。如:当头结点的指针域为空时表示空表。以便首元结点处理,以及统一空表非空表的处理。

头结点的数据域可以为空,也可以存放线性表的长度等附加信息,但此结点不能计入链表长度值。

结点在存储器中的位置是任意的,即逻辑上相邻的数据元素在物理上不一定相邻。

但在访问时只能通过头指针进入链表,并通过向后遍历的方式进行寻找。

这种方法也成为顺序存取法

优缺点
  • 优点

    • 元素个数可以随意扩充
    • 插入删除等操作无需移动数据,只需修改指针域即可
  • 缺点

    • 存储密度较小,需要额外存储指针域
    • 存取效率不高,顺序存取,存取时必须从第一个结点开始向后遍历。
基本操作

本节描述,基于以下定义:

typedef struct LNode{
    ElemType data; //数据域
    struct LNode *next; //指针域
}LNode, *LinkList;
//*LinkList为LNode类型的指针
构造

1.生成新结点为头结点,用头指针 L 指向头结点

2.头结点的指针域置空

Stutus InitList_L(LinkList &L){
    L = new LNode;
    L->next = NULL;
    return OK;
}
释放

基本思想就是从头向后遍历。

Status DestoryList_L(LinkList &L){
    LinkList p;
    while(L){
        p = L;
        L = L->next;
        delete p;
    }
    return OK;
}
清空
Status Clearist(LinkList &L){
    LinkList p,q;
    p = L->next;
    while(){
        q = p;
        p = p->next;
        delete q;
    }
    L->next = NULL;
    return OK;
}
求表长
int ListLength_L(LinkList L){
    LinkList p;
    p = L->next;
    i = 0;
    while(p){
        i++;
        p = p->next;
    }
    return i;
}
判断空
int ListEmpty(LinkList L){
    if(L->next){
        return 0;
    }else{
        return 1;
    }
}
元素查找
//按位置查找
Stutus GetElem_L(LinkList L,int i, ElemType &e){
    p = L->next;
    j = 1;
    while(p && j < i){
        p = p->next;
        ++j;
    }
    if(!p || j>i){
        return ERROR;
    }
    e = p->data;
    return OK;
}
//按值查找
LNode *LocateElem_L(LinkList L, ElemType e){
    p = L->next;
    while(p && p->data!=e){
        p = p->next;
    }
    return p;
}

$$ T(n) = O(n) $$

元素插入
//指定位置
Status ListInsert_L(LinkList &L, int i, ElemType e){
    p = L; j = 0;
    while( p && i < i-1 ){ //达到目标位置即退出循环
        p = p->next;
        ++j;
    }
    if(!p || j >i-1){
        return ERROR;
    }
    s = new LNode;
    s->data = e;
    s->next = p->next;
    p->next = s;
    return OK;
}
//前插法
void CreatList_F(LinkList &L, int n){
    L = new LNode;
    L->next = NULL; //初始化
    for(i=n;i>0;--i){
        cin >> p->data; 
        p->next = L->next; //插入到表头
        L->next = p;
    }
}
//尾插法
void CreatList_F(LinkList &L, int n){
    L = new LNode;
    L->next = NULL; //初始化
    r = L;
    for(i=n;i>0;--i){
        cin >> p->data; 
        p->next = NULL; //插入到表尾
        r->next = p;
        r = p;
    }
}

$$ T(n) = O(n) $$

元素删除
Status ListDelete_L(LinkList &L, int i, ElemType &e){
    p = L;
    j = 0;
    while(p->next && j <i-1){ //找到目标位置
        p = p->next; 
        j++;
    }
    if(!(p->next) || j>i-1){ //判断目标位置状态
        return ERROR;
    }
    q = p->next; //存取待删对象地址
    p->next = q->next; 
    e = q->data;
    delete q; //释放目标结点
    return OK;
}

$$ T(n) = O(n) $$

循环链表

表中的最后一个结点的指针域指向头结点,整个链表形成一个环。为了使操作实现方便,可以在循环单链表中设置头结点,这样空循环链表仅由一个自成循环的头结点表示。

合并
B->next = A->next;
p = B->next->next;
A->next = p;

双向链表

typedef struct DuLNode{
    ElemType data;
    struct DuLNode *prior;
    struct DuLNode *next;
}DuLNode, *DuLinkList;
插入
Status ListInsert_DuL(DuLinkList &L, int i, ElemType e){
    if(!(p=GetElemP_DuL(L,i))){
        return ERROR;
    }
    s = new DuLNode;
    s->data = e;
    s->prior = p->prior;
    s->next = p;
    p->prior = s;
    return OK;
}
删除
Status ListDelete_DuL(DuLinkList &L, int i, ElemType e){
    if(!(p=GetElemP_DuL(L,i))){
        return ERROR;
    }
    e = p->data;
    e->prior->next = p->next;
    p->next->prior = p->prior;
    delete p;
    return OK;
}

线性表应用(合并)

void union(List &La, List Lb){ //无序顺序表合并,相同元素合并。
    La_len = ListLength(La);
    Lb_len = ListLength(Lb);
    for(i=1;i<=Lb_len;i++){
        GetElem(Lb,i,e);
        if(!LocateElem(La,e)){
            ListInsert(&La,++La_len,e);
        }
    }
}

$$ T(n)=O(ListLength(L_a) \times ListLength(L_b)) $$

void MergeList_Sq( SqList La, SqList Lb, SqList &Lc ) {// 有序顺序表合并
    pa = La.elem;
    pb = Lb.elem;
    Lc.length = La.length + Lb.length;
    Lc.elem = new ElemType[Lc.length];
    pc = Lc.elem;
    pa_last = La.elem + La.length -1;
    pb_last = Lb.elem + Lb.length -1;
    while(pa<=pa_last && pb<=pb_last){
        if(*pa<=*pb){
            *pc++ = *pa++;
        }else{
            *pc++ = *pb++;
        }
  
    }
    while(pa<=pa_last){
        *pc++ = *pa++;
    }
    while(pb<=pb_last){
        *pc++ = *pb++;
    }
}

$$ T(n) = S(n) = O(ListLength(L_a) + ListLength(L_b)) $$

void MergeList_L(LinkList &La, LinkList &Lb, LinkList &Lc){// 有序链表合并
    pa = La->next;
    pb = Lb->next;
    pc = Lc = La; //用La头结点作为Lc新表的头结点
    while(pa && pb){
        if(pa->data<=pb->data){
            pc->next = pa;
            pc = pa;
            pa = pa->next; //pa后移
        }else{
            pc->next = pb;
            pc = pb;
            pb = pb->next; //pb后移
        }
    }
    pc->next = pa ? pa : pb; //任意一条表遍历完成后 剩余表直接加入Lc末尾
    delete Lb; //释放结点(重要)
}

栈和队列

栈和队列,可以视作一种限定性的线性表结构。

对于栈,他只可以在一端进行插入和删除操作。

对于队列,他只可以在一端进行插入,另一端进行删除。

栈只能在表的一端(栈顶-最后元素)进行插入和删除运算的线性表

相关概念有:栈顶,栈底,栈空,进栈,出栈。

进行运算时,符合后进先出准则

逻辑结构

  • 与线性表相同,为一对一关系
  • 受限的线性表,遵循先进后出(FILO)原则
  • 基本操作:入栈、出栈,读栈顶元素,建栈,判断栈满、栈空。

存储结构

顺序栈、链栈均可,常见使用顺序栈。

抽象数据类型定义

数据对象:

$
D = { a_i | ain{ElemSet}, i =1,2,cdots,n,n geq 0 }
$(类似线性表)

数据关系:

$R = \{ < a_{i-1}, a_i > | a_{i-1} , a_i \in D, i = 2, \cdots , n\}$,约定 a_n 为栈顶, a_1 为栈底

基本操作

InitStack(&S); //构造空栈
DestoryStack(&S);
ClearStack(&S);
StackEmpty(&S);
StackLength(&S);
GetTop(S, &S); //得到栈顶
Push(&S, e);
Pop(&S, e);    //出栈
StackTraverse(S); //遍历
顺序栈

利用一组地址连续的存储单元一次存放自栈顶的数据元素

我们首先要确定,数据哪一端作为栈底,一般使用第一个元素作为栈底。同时也要一个 top 指针来指示栈顶元素在数组中的位置。

栈空时出栈,则下溢。栈满时入栈,则上溢。

结构定义
##define STACK_INIT_SIZE 100 //存储空间初始分配量
##define STACKINCREMENT 10 //存储空间分配增量
typedef struct {
    SElemType *base;
    SElemType *top;
    int stacksize;
}SqStack;
构造-InitStack
Status InitStack(SqStack &S){//构造一个空栈S
 S.base=(SElemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType));
 if(!S.base){
     exit(OVERFLOW); //存储分配失败
 }
 S.top = S.base;
 S.stacksize = STACK_INIT_SIZE;
 return OK;
} //InitStack
得栈顶-GetTop
Status GetTop(SqStack S, SElemType &e){ 
    //若栈不空,则用e返回S的栈顶元素,并返回OK
    if (S.top == S.base){ // 空栈
        return ERROR;
    }
    e = *(S.top-1); //返回非空栈中栈顶元素
    return OK;
} //GetTop
Push 入栈
Status Push(SqStack &S, SElemType e) {//插入元素e为新的栈顶元素
    if(S.top-S.base>=S.stacksize){//栈满
        return ERROR;
    }
    *(S.top++) = e;
    return OK;
} //Push
Pop 出栈
Status Pop(Stack &S, ElemType &e){ 
    //栈不空,删除S的栈顶元素,用e返回其值,并返回OK;
    //否则返回ERROR
    if (S.top == S.base){ //空栈
         return ERROR;
    }
    e= *(--S.top); //返回非空栈中栈顶元素
    return OK;
} //Pop
链栈

为便于操作,采用带头结点的单链表实现栈。因为栈的插入和删除操作仅限制在表头位置进行,所以链表的表头指针就作为栈顶指针。

结构定义
typedef struct StackNode{
    SElemType data;
    struct StackNode *next;
}StackNode, *LinkStack;
初始化
Status InitStack(LinkStack &s){
    s=NULL;
    return ok;
}
入栈
Status Push(LinkStack &S, SElemType e)
{
    LinkStackNode *p;
    p=(LinkStack *)malloc(sizeof(StackNode));
    p->data=e;
    p->next= S;
    S=p;
    return OK;
}
出栈
Status Pop(LinkStack &S, SElemType &e)
{ 
    LinkStack *p;
    if(S==NULL) return ERROR;
    e=S->data;
    p=S;
    S=S->next;
    delete P;
    return OK;
}
顺序栈和链栈的对比
  • 时间性能

    • 相同,都是常数时间 0(1)。
  • 空间性能

    • 顺序栈:有元素个数的限制和空间浪费的问题
    • 链栈:没有栈满的问题,只有当内存没有可用空间时才会出现栈满,但是每个元素都需要一个指针域,从而产生了结构性开销。

应用/习题

数制转换

在数学中我们通常使用短除法,即:除$d$取余,在最后余数收集过程,符合先进后出的规则。则可有流程:首先将除得的余数进栈,然后余数再依次出栈。

void conversion (){
   InitStack(S); //构造空栈
   scanf("%d",N); //输入一个十进制数
   while(N){
       Push(S,N%8); //“余数”入栈
       N= N/8; //非零“商”继续运算
   }
   while (!StackEmpty(s)){//和“求余”所得相逆的顺序输出八进制的各位数
       Pop(S,e);
       prinft("%d",e); 
   }
} // conversion
表达式求值
  1. 设置两个工作栈

    1. 运算符栈 OPTR,运算符栈的栈底为表达式的起始符#。
    2. 操作数栈 OPND,操作数栈为空栈。
  2. 依次读入表达式中的每个字符

    1. 是操作数则进 OPND 栈;
    2. 是运算符,则和 OPTR 中的栈顶元素做比较再操作。

      1. 运算符优先级高于 OPTR 的栈顶元素,则运算符入栈;
      2. 运算符优先级低于 OPTR 中栈顶元素,则从 OPND 栈顶弹出两.操作数,与 OPTR 中的栈顶元素做运算,并将运算结果入 OPND
      3. 运算符优先级等于 OPTR 中栈顶元素,则 OPTR 的栈顶元素出栏
  3. 直至表达式求置完毕。
OperandType EvaluateExpression() {
    //设OPTR和OPND分别为运算符栈和运算数栈,OP为运算符集合。
    InitStack(OPTR);
    Push(OPTR, '#');
    InitStack(OPND);
    c = getchar();
    while (c != '#'|| GetTop(OPTR) != '#' ) {
        if(!In(c,OP)) {
            Push(OPND,c);
            c = getchar();
        } else {
            switch (Precede(GetTop(OPTR),c)) {
                case ' < ': Push(OPTR,c);
                c=getchar();
                break;
                case ' = ':
                                                        Pop(OPTR,x);
                c=getchar();
                break;
                case '>': Pop(OPTR, theta);
                Pop(OPND, b);
                Pop(OPND, a);
                Push(OPND, Operate(a, theta, b));
                break;
            }
        }
        //switch
    }
    return GetTop(OPND);
}
判断括号匹配

设计一个算法,判断一个表达式中括号是否匹配。若匹配,则返回 1;否则返回 0。

算法思路:扫描表达式,当遇到左括号时,将其进栈,遇到右括号时,判断栈顶是否为相匹配的左括号。若不是,则退出扫描过程,返回 0;否则栈顶元素出栈,直到扫描完整个表达式时,若栈为空,则返回 1。

int match(char * exps) {
    flag = 0;
    st.top = -1;
    while (exps[i] != ’\0’ && flag == 0) {
        switch (exps[i]) {
        case‘ (‘:
        case‘ [‘:
        case‘ {‘:
                st.data[++st.top] = exps[i];
                break;
                /* 各种左括号均进栈 */
            case‘)’:
                if (st.data[st.top] == ’ (‘) st.top--;
                else flag = 1;
                break;
            case‘]’:
                if (st.data[st.top] == ’ [‘) st.top--;
                else flag = 1;
                break;
            case‘
            }’:
            if (st.data[st.top] == ’ {‘) st.top--;
                else flag = 1;
                break;
            }
            i++;
        }
        If(flag == 0 && st.top == -1) return (1);
        /* 栈空且符号匹配,则返回1 */
        else return (0);
        /* 否则返回0 */
    }
    /* match */
进制转换例题

编写一个算法,将非负的十进制整数转换为其他进制的数输出,10 及其以上的数字从‘A’开始的字母表示。并给出完整的程序。

解题思路:先定义顺序栈的类型,并根据题意将 ElemType 设为 char 型;然后设计一个算法 trans 来完成数制的转换;最后在主函数中调用实现转换算法的函数。

算法 trans 的思路:先用“除基取余”法求得从低位到高位的值,同时采用顺序栈暂时存放每次得到的数,当商为 0 时,再从栈顶到栈底输出从高位到低位的数字。

##include "stdio.h"
##define StackSize 100
typedef char ElemType;
typedef struct {
    ElemType data[StackSize];
    int top;
}
SqStack;
int trans(int d,int b,char string[])  //string用于存放转换后的字符串 {
    SqStack st;
    char ch;
    int r,i=0;
    st.top=-1;
    // 栈初始化
    if (b<=1||b>36 || b==10)  // 2≤b≤36且不为10 {
        printf(" b is Error\n");
        return 0;
    }
    while(d!=0) {
        r=d%b;
        //求余数
        ch=r+(r<10?'0':'A'-10);
        // 将余数转换为相应的字符
        st.top++;
        st.data[st.top]=ch;
        // 进栈
        d/=b;
    }
    while (st.top!=-1) {
        string [i++]=st.data[st.top];
        //将出栈的字符放入字符数组string
        st.top--;
    }
    string [i]='\0';
    //加入字符串结束标志
    return  1;
}
void main() {
    char str[10];
    int d,b,t;
    printf("input d (d≥0)please:");
    // 输入待转换的整数
    scanf("%d",&d);
    printf ("input b (2≤b≤36) please:");
    // 输入待转换的进制
    scanf("%d",&b);
    t=trans(d,b,str);
    // 调用转换函数
    if (t==0) printf("Error!"); else printf("%s\n",str);
    // 输出转换结果字符串
}

递归和栈

调用前,系统完成:
(1)将实参,返回地址等传递给被调用函数
(2)为被调用函数的局部变量分配存储区
(3)将控制转移到被调用函数的入口
调用后,系统完成:
(1)保存被调用函数的计算结果
(2)释放被调用函数的数据区
(3)依照被调用函数保存的返回地址将控制转移到调用函数

队列

只允许在一端进行插入而在另一端进行删除的线性表

先进先出,队尾入,队头出

队头:允许插入的一端,队尾:允许删除的一端

抽象数据类型定义

数据对象:

$D=\{ a_i | a\in{ElemSet}, i =1,2,\cdots,n,n \geq 0 \}$,(类似线性表)

数据关系:

$$ R=\{<a_{i-1},a_i> | a_{i-1},a_i \in D, i = 2, \cdots , n\} $$

基本操作

InitQueue(&Q);
DestoryQueue(&Q); //销毁
ClearQueue(&Q); //清空
QueueEmpty(Q); //判断空
QueueLength(Q); 
GetHead(Q,&e); //读队头元素
EnQueue(&Q,e); //插入队列
DeQueue(&Q,&e); //处理队列

结构定义

##define M 100
Typedef struct{
    QElemType *base;
    int front; //头指针(偏移)
    int rear;  //尾指针(偏移)
}SqQueue;

循环队列

头指针向后移动时,会出现头部部分空间不被有效利用,出现假溢出的情况,此时可以使用循环队列。循环队列的本质就是当指针(偏移)达到尾部的时复位。

//入队
base[rear] = x;
rear = (rear + 1) % M;
//出队
base[front] = x;
front = (front + 1) % M;
循环队列判断队满
  1. 用另外一个标志来区别队空、队满
  2. 少用一个元素空间,则队空的时候 front == rear,队满时(rear + 1) % M == front
循环队列的初始化
Status InitQueue (SqQueue &Q){//操作结果:构造一个空队列Q
    Q.base =new QElemType[MAXQSIZE]
    if(!Q.base){
        exit(OVERFLOW);
    }
    Q.front=Q.rear=0;
    return OK;
}
求循环队列的长度
//初始条件:队列Q已存在。
//操作结果:返回Q的元素个数,即队列的长度。
int QueueLength (SqQueue Q){
 return (Q.rear - Q.front + MAXQSIZE) % MAXQSIZE;
}//多加一个MAXSIZE是为了保证正值
循环队列入队
//初始条件:队列Q已存在。
//操作结果:插入元素e为Q的新的队尾元素。
Status EnQueue(SqQueue &Q,QElemType e){
    if((Q.rear+1)% MAXQSIZE== Q.front){ //队列满
        return ERROR;
    }
    Q.base[Q.rear]=e;
    Q.rear=(Q.rear+1)%MAXQSIZE;
    return OK;
}
循环队列出队
//初始条件: Q为非空队列。
//操作结果:删除Q的队头元素,并用e返回其值。
Status DeQueue (SqQueue &Q,QElemType &e){
    if(Q.front==Q.rear){ //队列空
        return ERROR;
    }
    e = Q.base[Q.front];
    Q.front = (Q.front+ 1) % MAXQSIZE;
    return OK;
}

链队

存储结构
//结点表示:
typedef struct QNode{
    QelemType data;
    struct QNode *next;
}QNode, *QueuePtr;

//链队列表示:
typedef struct{
    QueuePtr front; //队头指针
    QueuePtr rear; //队尾指针
}LinkQueue;
链队的初始化
//操作结果:构造一一个空队列Q
Status InitQueue (LinkQueue &Q){ //构造一一个空队列Q
    Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode));
    if (!Q.front){ //存储分配失败
        exit(OVERFOLW);
    }
    Q.front->next = NULL;
    return OK;
}
销毁链队列
//初始条件:队列Q已存在。
//操作结果:队列Q被销毁,不再存在
Status DestroyQueue (LinkQueue &Q){
    while(Q.front){
        Q.rear = Q.front->next;
        free(Q.front);
        Q.front = Q.rear; 
    }
    return OK;
}
判断链队列是否为空
//初始条件:队列Q已存在。
//操作结果:若Q为空队列,则返回true,否则返回false;
Status QueueEmpty (LinkQueue Q){
    return (Q.front == Q.rear);
}
求链队列的队头元素
//初始条件: Q为非空队列
//操作结果:用e返回Q的对头元素;
Status GetHead (LinkQueue Q, QElemType &e){
    if(Q.front==Q.rear){
        return ERROR;
    }
    e = Q.front->next->data;
    return OK;
}
链队的入队
//初始条件:队列Q已存在。
//操作结果:插入元素e为Q的新的队尾元素。
Status EnQueue(LinkQueue &Q, QElemType e){
    //在当前队列的尾元素之后,插入元素e为新的队列尾元素
    QNode *p;
    p = new QNode;
    if (!p){ //存储分配失败
        exit(OVERFLOW);
    }
    p->data=e; 
    p->next= NULL;
    Q.rear->next=p;//修改尾结点的指针
    Q.rear = p; //移动队尾指针
  
}
链队的出队
//初始条件: Q为非空队列。
//操作结果:删除Q的队头元素,并用e返回其值。
Status DeQueue(LinkQueue &Q, QElemType &e){
    if(Q.front==Q.rear){//链队列空
        return ERROR; 
    }
    p = Q.front->next;
    e = p->data; //返回被删元素的值
    Q.front->next=p->next; //修改队头结点指针
    if(Q.rear==p){
        Q.rear=Q.front;
    }
    free(p); 
    return OK;
} // DeQueue

应用

杨辉三角(重点理解)

(1) i=2 时, 从 q 中取出队头 t=1,计算 s+t,得到 i=3 时的第 1 个数据 1,放在 q 的队尾;
(2)让 s=t,从 q 中取出队头 t=2,计算 s+t,得到 i=3 时的第 2 个数据 3,放在 q 的队尾;
(3)让 s=t,从 q 中取出队头 t=1,计算 s+t,得到 i=3 时的第 3 个数据 3,放在 q 的队尾;
(4)如此重复,直到第 i 行的数据处理完毕,全部出队,第 i+1 行的数据也全部计算出来并入队。

void yanghui (int N){ 
    InitQueue(&Q);
    EnterQueue(&Q, 1);
    EnterQueue(&Q, 1);//第一行元素入队
    s = 0;
    for(i= 1;i<= N; i++){
        printf("\n"); 
        EnterQueue(&Q, 0); //入队
        for(j=1;j<=i+ 2;j++)
        {
            DelQueue(&Q, &temp); //出队的数赋给temp
            EnterQueue(&Q,s+temp); 
            s=temp;
            if(j!=i+2){
                printf("%d ",s);
            }
        }
    }
}

性能对比

  • 时间性能

    • 循环队列和链队列的基本操作都需要常数时间 $O(1)$。
  • 空间性能

    • 循环队列:必须预先确定一个固定的长度,所以有存储元素个数的限制和空间浪费的问题。
    • 链队列:没有队列满的问题,只有当内存没有可用空间时才会出现队列满,但是每个元素都需要一个指针域,从而产生了结构性开销。

树 是 n 个节点的有限集 T 在任意一个非空树中,有且仅有一个特定的点,称为树的根。 当

$$ n \ge 1 $$

时,其余节点可分为$m$ 个互不相交的有限集

$$ T_1,T_2 \cdots T_m $$

其中每一个集合本身又是一棵树,成为根的子树。

特点

  • 非空树至少有一个节点——根。
  • 树中各子树是互不相交的集合:

    • 某结点不可同时属于两个子集
    • 两个子集的结点之间无关系

基本术语

术语解释
结点的度结点所拥有的子树的个数
树的度树中各结点度的最大值
叶子结点度为 0 的结点,也称为终端结点
分支结点度不为 0 的结点,也称为非终端结点。
孩子、双亲结点的子树的根称为这个结点的孩子这个结点称为它孩子结点的双亲;
兄弟具有同一个双亲的孩子结点互称为兄弟
祖先、子孙在树中,如果有一条路径从结点 x 到结点 y,那么 x 就称为 y 的祖先,而 y 称为 x 的子孙。
结点所在层数根结点的层数为 1;对其余任何结点,若某结点在第 k 层,则其孩子结点在第 k+1 层。
树的深度树中所有结点的最大层数,也称高度
有序树、无序树如果一棵树中结点的各子树从左到右是有次序的,称这棵树为有序树;反之,称为无序树。最左边的子树称为根的第一个孩子,最右边的最后一个孩子。
森林$m(m \gt 0)$棵互不相交的树的集合。
二叉树$n(n \gt 0)$个结点的有限集,其子树分为互不相交的两个集合,分别称为左子树和右子树,左子树和右子树也是二叉树。

二叉树特点

  • 每个结点至多有二棵子树(即不存在度大于 2 的结点) ;
  • 二叉树的子树有左、右之分,且其次序不能任意颠倒。

抽象数据类型定义(Tree)

数据对象: $D$是具有相同特性的数据元素的集合。
数据关系:
若$D$为空集,则称为空树;
若$D$中仅含一个数据元素,则关系 R 为空集;
若$D$中含多于一个数据元素,则$R=\{H\}$,$ H $是如下二元关系:
(1)在$D$中存在唯一-的称为根的数据元素$root$, 它在关系$H$下无前驱;
(2)当$n>1$时, 其余数据元素可分为$m(m>0)$个互不相交的(非空)有限集

$T_1, T_2 \cdots T_m$,其中每一个子集本身又是一棵符合本定义的树,称为根 $root$的子树,每一棵子树的根$x$都是根$root$的后继,即

$$ <root, xi> \in H, i=1,2, ... m。 $$

基本操作

InitTree(&T);
//操作结果:构造空树T。
  
CreateTree(&T, definition) ;
//初始条件: definition 给出树T的定义;
//操作结果:按definition 构造树T;

DestroyTree(&T);
//初始条件:树T存在。
//操作结果:销毁树T.

TreeDepth(T);
//初始条件:树T存在。
//操作结果:返回T的深度。

Root(T);
//初始条件:树T存在。
//操作结果:返回T的根。

Value(T,cur e);
//初始条件:树T存在,cure是T中某个结点。
//操作结果:返回cur_ e的值。

LeftChild(T, cur_ e);
//初始条件:树T存在,cure是T中某个结点。
//操作结果:若cur_ e是T的非叶子结点,则返回它的最左孩子,否则返回“空”。

RightSibling(T, cur_ e);
//初始条件:树T存在,cur_e是T中某个结点。
//操作结果:若cur_e有右兄弟,则返回它的右兄弟,否则返回“空”。

TraverseTree(T, visit());
//初始条件:树T存在,visit 是对结点操作的应用函数。
//操作结果:按某种次序对T的每个结点调用函数visit()一次且至多一次。一旦visit() 失败,则操作失败。

Assign(T, cur_e, value);
//初始条件:树T存在,cur_ e是T中某个结点。
//操作结果:结点cur_ e赋值为value.

ClearTree (&T);
//初始条件:树T存在.
//操作结果:将树T清为空树。

InsertChild(&T,,&p, i, c) ;
//初始条件:树T存在,p指向T中某个结点,1≤i≤p 所指结点的度+1,非空树c与T不相交。
//操作结果:插入c为T中p所指结点的第i棵子树。

DeleteChild(&T, &p, i);
//初始条件:树T存在,p指向T中某个结点,1≤i≤p指结点的度。
//操作结果:删除T中p所指结点的第i棵子树。

抽象数据类型定义(BinTree)

数据对象:$D$是具有相同特性的数据元素的集合。
数据关系:
若$D$为空集,则称为空二叉树;
若$D$中仅含一个数据元素,则关系 R 为空集;
若$D$中含多于一个数据元素,则$R=\{H\}$, $H$是如下二元关系:

  • 在$D$中存在唯一的称为根的数据元素 root, 它在关系 H 下无前驱
  • 当$n>1$时, 其余数据元素可分为 2 个互不相交的有限集 T, TR,TL 称为 root 的左子树,T 称为 root 的右子树, TL, TR 本身又是符合本定义的二叉树。

线性结构和树结构比较

线性结构树结构树结构
存在唯一的没有前驱的"首元素"存在唯一的没有前驱的"根结点"
存在唯一的没有后继的"尾元素”存在多个没有后继的"叶子”
其余元素均存在唯一的“前驱元素"和唯一的"后继元素"其余结点均存在唯一-的”前驱(双亲)结点"和多个"后继(孩子)结点"

二叉树的特殊类型

斜树

  • 所有结点都只有左子树的二叉树称为左斜树;
  • 所有结点都只有右子树的二义树称为右斜树;
  • 左斜树和右斜树统称为斜树。

满二叉树

深度为 k 且有 2k- 1 个结点的二叉树。

特点
  • 每一层 上的结点数都是最大结点数;
  • 所有的分支结点的度数都为 2;
  • 叶子结点都在同一层次上。

完全二叉树

若对满二叉树的结点从上到下从左至右进行编号,一棵深度为$K$的二叉树被认为是完全二叉树,当且仅当其该二叉树的每一个结点都与深度为$K$的满二又树的编号从$ 1 \text{~} n$一一对应。

特点

叶子结点只可能在层次最大的两层上出现;
前$K-1$层中的结点都是“满”的,且第$K$层的结点都集中在左边。

性质

  • 性质 $1$:二叉树的第$i$层上最多有 $2^{i-1}$ 个结点 $(i\ge 1)$
  • 性质 $2$:一棵深度为$K$的二叉树中,最多有 $2^{k-1}$ 个结点。
  • 性质 $3$:在一棵二叉树中,如果叶子结点数为$n_0$ 度为 $2$ 的结点数为$n_2$,则有:$ n_0=n_2+1$。
  • 性质 $4$:具有$n$个结点的完全二叉树的深度为$ log_2n + 1$
  • 性质 $5$:对一棵具有$n$个结点的完全二叉树中从 $1$ 开始按层序编号,则对于任意的序号为$i (1≤i≤n)$的结点(简称为结点$i$)

    • 1) 如果$i>1$,则结点$i$的双亲结点的序号为$i/2$;如果$i=1$,则结点$i$是根结点,无双亲结点。
    • 2)如果 $2i≤n$,则结点 $i$ 的左孩子的序号为 $2i$;如果 $2i>n$,则结点 $i$ 无左孩子。
    • 3)如果 $2i+1≤n$,则结点 $i$ 的右孩子的序号为 $2i+ 1$;如果 $2i+1>n$,则结点 $i$ 无右孩子。

存储

顺序存储结构

用一组地址连续的存储单元存储二又树中的数据元素。

  • 完全二叉树,只要从根起按层序存储即可。将完全二叉树上编号为$i$的结点元素存储在一维数组中下标为$i-1$ 的分量中。
  • 一般的二叉树,可对照完全二叉树的编号进行相应的存储,但在没有结点的分量中需填充空白字符(例如填充 $0$)。
##define MAX_TREE_SIZE 100 //最大结点数
typedef TElemType SqBiTree[MAX_TREE_SIZE];
SqBiTree bt;

可推出顺序存储结构中“双亲” 和“孩子” 的关系:假设bt. data[i]是完全
二叉树上的一个结点,

  1. 若 $2i<bt. nodeNum$,则bt. data[2i]是它的左孩子,否则它的左子树为
    空树;
  2. 若 $2i+1<bt. nodeNum$,则bt. data[2i+1]是它的右孩子,否则它的右子树为空树。

如果一般二叉树不是完全二叉树,如右斜树,使用顺序存储结构需要补充大量空节点,会出现大量的空间浪费。适合存储满二叉树和完全二叉树。

链式存储结构

二叉链表:结点除包括元素自身的信息外,还包括指向其左、右子树的指针。即结点要包括数据域,左子树指针域和右子树指针域。

typedef struct BiTNode {
    TElemType data;
    struct BiTNode *Ichild,*rchiId;
}BiTNode, *Bitree;

比较

在不同的存储结构中,实现二叉树的操作方法也不同,比如,在顺序存储中,查询双亲和孩子都比较容易,使用二叉链表查询孩子容易,但是查询双亲就要从根指针开始,在具体应用中采用什么存储结构,除根据二叉树的形态之外还应考虑需进行什么操作。

操作

遍历二叉树

遍历是树结构的一种常用的、重要的运算是树的其它运算的基础。

  • 按一定的规律, 走遍二叉树的每个结点, 使每个结点被访问一次,且只被访问一次。
  • 遍历方式

    • 按根、左子树、右子树三个部分进行访问;
    • 按层次访问;

非线性结构中每个数据元素可以有多个后继,为保证“遍历”成功就需要确定合适
的搜索路径。遍历的过程就是把非线性结构的二又树中的结点排成-个线性序列的过程。

按根、左子树、右子树三个部分进行访问

设 D 表示根结点,L 表示左子树,R 表示右子树则对这三个部分进行访问的组合共有 6 种,

$$ DLR、DRL、LDR、LRD、RDL、RLD $$

若限定先左后右,则只有$DLR、 LDR、 LRD$三种。分别称为先序遍历,中序遍历,后序遍历。

先序遍历

若二叉树为空,则空操作;否则

  • 访问根结点;
  • 先序遍历左子树;
  • 先序遍历右子树;
Status PreOrderTraverse(BiTree T, Status (*visit)(TElemType e)){
    if(T){
        visit(T->data); //cout << T->data;
        PreOrderTraverse(T->lchild, visit);
        PreOrderTraverse(T->rchild, visit);
    }//if
}//PreOrderTraverse
中序遍历

若二叉树为空,则空操作;否则

  • 中序遍历左子树
  • 访问根结点
  • 中序遍历右子树
Status InOrderTraverse(BiTree T, Status (*visit)(TElemType e)){
    if(T){
        InOrderTraverse(T->lchild, visit);
        visit(T->data); //cout << T->data;
        InOrderTraverse(T->rchild, visit);
    }//if
}//InOrderTraverse
后序遍历

若二叉树为空,则空操作;否则

  • 后序遍历左子树
  • 后序遍历右子树
  • 访问根结点
Status InOrderTraverse(BiTree T, Status (*visit)(TElemType e)){
    if(T){
        SufOrderTraverse(T->lchild, visit);
        SufOrderTraverse(T->rchild, visit);
        visit(T->data); //cout << T->data;
    }//if
}//InOrderTraverse

建立二叉链表

建立二叉链表
void CreateBiTree (BiTree &T) {
    cin >>ch;
    if(ch =="#") {
        T=NULL;
    }else {
        T = new Bi TNode ;
        T->data = ch;
        CreateBiTree(T->Lchild);
        CreateBiTree(T->Rchild);
    }//else
} // CreateBiTree

计算深度

从二叉树深度的定义可知,二叉树的深度应为其左、右子树深度的最大值加 1。由此,需先分别求得左、右子树的深度。

算法中“访问结点”的操作为:求得左、右子树深度的最大值,然后加 1

int depth(Bitree T){
    if(T==NULL){
        return 0;
    }else {
        h1= depth(T->Ichild);
        h2= depth(T->rchild);
        return max(h1,h2)+1;
    }
}

统计叶子节点

对二叉树“遍历”一遍,并在遍历过程中对“叶子结点计数”即可。

为了在遍历的同时进行计数,在算法的参数中设一个“计数器”。

这个遍历的次序可以随意,即先序或中序或后序均可

void CountLeaf (BiTree T, int& count){
    if(T){
        if ((!T->Lchild) && (!T ->Rchild)){
            count++;
        }
        CountLeaf(T->Lchild, count);
        CountLeaf(T- Rchild, count);
    }// if
} // CountLeaf

一般树的存储结构

双亲表示法

以一组连续的存储空间存放树的结点,每个结点中附设一个指针指示其双亲结点在这连续的存储空间中的位置。此处指针,不是地址指针,而是一维数组偏移。

##define MAX_TREE_SIZE = 100;
typedef struct PTNode { //结点结构
    TElemType data;
    int parent; //双亲位置域
}PTNode;

typedef struct{ //树结构
    PTNode nodes[MAX_TREE_SIZE];
    int r, n; //根的位置
}PTree;

这样一种表示方式,找双亲很容易,但找孩子很困难,需要遍历整个结构

孩子表示法

把每个结点的孩子排列起来,看成一个线性表,以单链表存储;令其头指针和结点的数据元素构成一个结点,并将所有这样的结点存放在一个地址连续的存储空间里。

##define MAX_TREE_SIZE = 100;
typedef struct CTNode {
//孩子结点
    int child;
    struct CTNode *next;
}*ChildPtr;
typedef struct {
    ElemType data; //结点的数据元素
    ChildPtr first child; //孩子链表头指针
}CTBox;

typedef struct
    CTBox nodes [MAX_TREE_SIZE];
    int n, r;
}CTree;

这样一种表示方式,找孩子很容易,但找双亲很困难,需要遍历整个结构

孩子兄弟法

用二叉链表作树的存储结构,链表中每个结点的两个指针域分别指向其第一个孩子结点和下个兄弟结点。

typedef struct CSNode {
    ElemType data;
    struct CSNode *firstchild, *nextsibling;
} CSNode, *CSTree;

森林转换成二叉树

使用树的二叉链表表示法:左子树为该结点的第一个孩子,右子树为其下一个兄弟。把森林中的第二棵树的根节点看成是第一棵树的根节点的兄弟,则同样可导出森林和二叉树的对应关系。

  1. 将各棵树分别转换成二叉树。
  2. 将每棵树的根结点用线相连。
  3. 以第一棵树根结点为二叉树的根,以孩子兄弟法构成二叉树型结构。

二叉树转换成森林

抹线:将二叉树中根结点与其右孩子连线,及沿右分支搜索到的所有右孩子间连线全部抹掉,使之变成孤立的二叉树。
还原:将孤立的二叉树还原成树。

树的遍历

  • 先根遍历:若树不空,则先访问根结点,然后依次从左到右先根遍历根的各棵子树。
  • 后根遍历:若树不空,则先依次从左到右后根遍历根的各棵子树然后访问根结点。

森林的遍历

  • 先序遍历

    • 访问森林中第一棵树的根结点;
    • 先序遍历第-棵树中的子树森林;
    • 先序遍历除去第一棵树之后剩余的树构成的森林。
  • 中序遍历

    • 中序遍历第一棵树中的子树森林;
    • 访问森林中第一棵树的根结点 ;
    • 中序遍历除去第一棵树之 后剩余的树构成的森林。

哈夫曼树

基本概念

  • 路径:从树中一个结点到另一个结点之间的分支。
  • 路径长度:路径上的分支数目称为路径长度。
  • 树的路径长度:从树根到每一结点的路径长度之和。
  • 结点的带权路径长度:结点赋予权值,从该结点到树根之间的路径长度与结点上的权值的乘积。
  • 树的带权路径长度(WPL):树中所有叶子结点的带权路径长度之和。

加权后路径长度最小的并非是完全二叉树,而是权大的叶子离根最近的二叉树。

特点

  1. 权值越大的叶子结点越靠近根结点,而权值越小的叶子结点越远离根结点。
  2. 只有度为 $0 (叶子结点)$ 和度为 $2 (分支结点)$的结点,不存在度为 1 的结点。

构造算法

  1. 根据给定的$n$个权值$w1, w2, .....$构造$n$棵只有根结点的二叉树,令初始权值为$w_j$
  2. 在森林中选取两棵根结点权值最小的树作左右子树构造一棵新的二叉树,置新二叉树根结点权值为其左右子树根结点权值之和;
  3. 在森林中删除这两棵树,同时将新得到的二叉树加入森林中;
  4. 重复上述两步,直到只含-棵树为止,这棵树即哈夫曼树。

哈夫曼编码

略部分内容,这部分我自己也不能全部理解。。。

typedef struct {
    unsigned int weight;
    unsigned int parent, lchild, rchild;
}HTNode, *HuffmanTree;//动态分配数组存储

void CreateHuffmanTree(HuffmanTree &HT, int *w, int n) {//w存放n个字符的权值
    m = 2*n-1; //结点个数(n2: n0-1 )
    HT = new HTNode[m+1]; //0号单元未用
    for(p=HT+1, i=1;p<=HT+n, ++p, ++w) *p={*w, 0, 0, 0};//初始化, 叶子结点占1~n
    for(i=n+1;i<= m;++i, ++p) *p={0,0,0,0]; //n+1~m的位置放置中间结点
    for(i=n+1;i<= m;++i) { //建哈夫曼树
        Select(HT, i-1, s1, s2) //在HT[1.. i-1]选择parent为0,且wei ght
        //最小两个结点,其序号分别为s1和s7r
        HT[s1].parent= i; HT[s2]. parent=i;
        HT[i门].lchild=s1; HT[i]. rchild=s2; 
        HT[i].weight= HT[s1].weight + HT[s2].weight;
    }
}

void CreateHuffmanCode (Huf fmanTree &HT, HuffmanCode &hc, int n) 1
    HC = new char *[n+1]; //分配n个字符串指针,放每个字符的编码
    cd = new char[n]; //分配求编码的工作空间
    for(i=1;i<=n;++i) { //逐个字符求哈夫曼
    start=n-1; //编码结束
    for (c=i,f=HT[i].parent; f!=O; c=f,f=HT[f].parent) [ //求编码
        if (HT[f].lchild==c) cd[--start]= "0";
        else cd[--start]= "1";
    }
    HC[i]=new char[n-start];//为第i个字符编码分配
    strcpy (HC[i], &cd[start]);//从cd复制编码到HC
    delete cd;
    }

图:$Graph=(V,E)$
$V$:顶点(数据元素)的有穷非空集合;
$E$:边的有穷集合

图的定义

术语解释
有向图每条边都是有方向的$$
无向图每条边都是无方向的$(V_1, V_4)$
子图$B$图的所有顶点和边都属于$A$图的顶点和边的一部分,则称$B$为$A$的子图。
完全图任意两个点都有一条边相连(无向完全图有$\frac{n(n-1)}{2}$条边,有向完全图有$n(n-1)$条边)
稀疏图有很少边或弧的图
稠密图有较多边或弧的图
边/弧被赋予值,则该值称为边/弧的权
边/弧带权的图。交通网
邻接两个顶点之间的关系存在$(V_i, V_j)$,则称$V_i$和$V_j$互为邻接点存在$$,则称$V_i$邻接到$V_j$,称$V_j$邻接于$V_i$
关联 (依附)边/弧与顶点之间的关系,存在$(V_i, V_j) \text{或}$则称该边/ 弧关联$V_i 和 V_j$
顶点的度与该顶点相关联的边的数目,记为$TD(V_1)$
入度(有向图)顶点$V_1$的入度是以$V_1$为点的有向边的条数记作$ID(V_1)$
出度(有向图)顶点$V_1$的出度是以$V_1$为点的有向边的条数记作$ID(V_1)$
路径顶点$V_1$到顶点$V_j$经历的顶点序列。
路径长度路径上 边/弧 的 数目/权值 之和
回路(环)第一个顶点和最后一个顶点相同的路径
简单路径除路径起点和终点可以相同外,其余顶点均不相同的路径。
简单回路(简单环)除路径起点和终点相同外,其余顶点均不相同的路径。
连通图在无(有)向图$G=( V, \{E\} )$中,若对任何两个顶点$v、u$都存在从$v$到$u$的路径,则称 G 是连通图(强连通图)
连通分量无向图 G 的极大连通子图称为$G$的连通分量
极大连通子图该子图是 G 连通子图,将$G$的任何不在该子图中的顶点加入,子图不再连通
强连通分量有向图 G 的极大强连通子图称为 G 的强连通分量。
极小连通子图该子图是 G 的连通子图,在该子图中删除任何一条边,子图不再连通。
生成树包含无向图 G 所有顶点的极小连通子图。
生成森林对非连通图,由各个连通分量的生成树的集合

存储结构

邻接矩阵

邻接矩阵用于描述图中各个顶点之间的临接关系

  • 对于一般图,邻接矩阵各个值可以用 1 来表示可达,对于网图,各个值可存储权值。
  • 无向图的邻接矩阵一定是一个对称矩阵。因此,在存放邻接矩阵时只需存放上(或下)三角矩阵
    的元素即可。
  • 对于无向图,邻接矩阵的第$i$行(或第$i$列)非零元素(或非$∞$元素)的个数正好是第$i$个顶点的度$TD(v_i)$。
  • 对于有向图,邻接矩阵的第$i$行(或第$i$列)非零元素(或非$∞$元素)的个数正好是第$i$个顶点的出度$OD(v_i)$ (或入度$ID(v_i)$)。
  • 用邻接矩阵方法存储图,很容易确定图中任意两个顶点之间是否有边相连;但是,要确定图中有多少条边,则必须按行、按列对每个元素进行检测,所花费的时间代价很大。
##define MaxVertexNum 100 //最大顶点数设为100
typedef char VertexType; //顶点类型设为字符型
typedef int EdgeType; //边的权值设为整型
typedef struct {
    VertexType vexs[MaxVertexNum]; //顶点表
    EdgeType edges[MaxVertexNum][MaxVertexNum];  //邻接矩阵,即边表
    int n,e; //顶点数和边数
}MGragh; //MGragh是以邻接矩阵存储的图类型

void CreateMGraph(MGragh *G){   
    int i,j,k,w;
    char ch;
    printf("请输入顶点数和边数(输入格式为:顶点数,边数):\n");
    scanf("%d,%d", &(G->n),&(G->e));         // 输入顶点数和边数
    printf("请输入顶点信息(输入格式为:顶点号<CR>):\n");
    for (i=0; i < G->n; i++){
        scanf("\n%c",&(G->vexs[i])); 
    }
    for (i=0;i<G->n;i++){   // 初始化邻接矩阵
        for (j=0;j<G->n;j++){
            G->edges[i][j] = 0; 
        }
    }
  
    printf("请输入每条边对应的两个顶点的序号:\n");
    for (k=0;k < G->e; k++)
    {
        scanf("\n%d,%d", &i,&j);    // 输入e条边
        G->edges[i][j] = 1; 
    }
}//CreateMGraph

邻接表

邻接表(Adjacency List)是图的一种顺序存储与链式存储相结合的存储方法。
对于图$G$中的每个顶点$v_i$,将所有邻接于$v_i$的顶点$v_j$链成一个单链表,这个单链表就称为顶点 vi 的邻接表,再将所有点的邻接表表头放到数组中,就构成了图的邻接表。

顶点表:顶点域 + 边表头指针

边表:邻接点域 + 指针域

##define MaxVerNum 100          // 最大顶点数为100
typedef struct node{               // 边表结点
    int adjvex;                  // 邻接点域
    struct node  * next;      // 指向下一个邻接点的指针域
}EdgeNode; 

typedef struct vnode{              // 顶点表结点
    VertexType vertex;          // 顶点域
    EdgeNode  *firstedge;      // 边表头指针
}VertexNode;

typedef VertexNode AdjList[MaxVertexNum];  // 邻接表类型

typedef struct{  
    AdjList adjlist;                // 邻接表
    int n,e;                     // 顶点数和边数
}ALGraph;             // 以邻接表方式存储的图类型

void CreateALGraph(ALGraph *G)
  {
    int i,j,k;
    EdgeNode *s;
    printf("请输入顶点数和边数:\n");
    scanf("%d,%d", &(G->n), &(G->e));  //读入顶点数和边数
    printf("请输入顶点信息:\n");
    for (i=0;i<G->n;i++)              // 建立有n个顶点的顶点表
    {
        scanf("\n%c",&(G->adjlist[i].vertex));  // 读入顶点信息
        G->adjlist[i].firstedge = NULL;      // 顶点的边表头指针设为空
    }
    printf("请输入边的信息(输入格式为:i,j):\n");
    for (k=0;k<G->e;k++)             // 建立边表
    {  
        scanf(“\n%d,%d”, &i, &j); 
        s = (EdgeNode*)malloc(sizeof(EdgeNode));  
        s->adjvex = j;                      // 邻接点序号为j 
        s->next = G->adjlist[i].firstedge;  
        G->adjlist[i].firstedge = s; 
    }
}

若无向图中有$n$个顶点、$e$条边,则它的邻接表需$n$个头结点和 $2e$ 个表结点。

有向图的邻接表:对每个顶点$v_i$建立-一个链接以$v_i$为出发顶点的弧的链表。

有向图的逆邻接表:对每个顶点$v_i$建立一个链接以$v_i$为头的弧的链表。

遍历

DFS 深度优先搜索

从图中某个顶点$v$出发,访问此顶点,然后依次从$v$的未被访问的邻接点出发深度优先遍历图,直至图中所有和$v$有路径相通的项点都被访问到:若此时图中尚有顶点未被访问,则另选图中一个未曾被访问的顶点作起始点,重复上述过程,直至图中所有顶点都被访问到为止。

//深度优先遍历以邻接表存储的图G :
void DFSTraverseAL(ALGraph *G)
{
    int i;
    for (i=0;i<G->n;i++)
        visited[i]=FALSE;            // 标志向量初始化
    for (i=0;i<G->n;i++)
        if (!visited[i]) DFSAL(G,i);   // vi未访问过,从vi开始搜索
}//DFSTraveseAL

void DFSAL(ALGraph *G,int i)
{// 以Vi为出发点对邻接表存储的图G进行DFS搜索
    EdgeNode *p;
    printf("visit vertex:V%c\n",G->adjlist[i].vertex); // 访问顶点Vi
    visited[i]=TRUE;             // 标记Vi已访问
    p=G->adjlist[i].firstedge;       // 取Vi边表的头指针
    while(p)                     // 依次搜索Vi的邻接点Vj
    {                   // 若Vj尚未访问,则以Vj为出发点向纵深搜索
        if (!visited[p->adjvex]) DFSAL(G,p->adjvex);
        p=p->next;                  // 找Vi的下一个邻接点
    }
}//DFSAL

BFS 广度优先搜索

从图中某顶点$v$出发,在访问了$v$之后依次访问$v$的各个未曾访问过的邻接点,然后分别从这些邻接点出发依次访问它们的邻接点,并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问,直至图中所有已被访问的顶点的邻接点都被访问到。若此时图中尚有顶点未被访问,则另选图中一个未曾被访问的顶点作起始点,重复上述过程,直至图中所有顶点都被访问到为止。

void  BFSTraverse(Graph G, Status(*Visit)(int v))
{// 按广度优先非递归遍历图G。使用辅助队列Q和访问标志数组visited
    for (v=0;v<G,vexnum;++v){
        visited[v]=FALSE       // 置空的国债队列Q
    }
    InitQueue(Q);         
    if (!visited[v])                 // v尚未访问
    {
        EnQucue(Q,v);              //v入队列
        while (!QueueEmpty(Q)) 
        { DeQueue(Q,u);        // 队头元素出队并置为u
         visited[u]=TRUE; visit(u);   // 访问u
         for(w=FistAdjVex(G,u); w; 
             w=NextAdjVex(G,u,w))
             if (!visited[w]) EnQueue(Q,w); 
        }//while
    }//if
}//BFSTraverse

最小生成树

连通图的一.次遍历所经过的边的集合及图中所有顶点的集合就构成了该图的一棵生成树。

对于有 n 个顶点的无向连通图,无论其生成树的形态如何,所有生成树中都有且仅有$n-1$条边。

如果无向连通图是一个网,那么,它的所有生成树中必有一棵边的权值总和最小的生成树,我们称这棵生成树为最小生成树。

$Prim$ 算法

假设$G= (V, E)$为一网图,其中$V$为网图中所有顶点的集合,E 为网图中所有带权边的集合。设置两个新的集合$U$和$T$,其中集合$U$用于存放$G$的最小生成树中的顶点,集合$T$存放$G$的最小生成树中的边。令集合$U$的初值为$U= \{u_1\} $(假设构造最小生成树时,从顶点$u_1$出发),集合$T$的初值为$T=\{\}$。

$Prim$算法的思想:从所有$u\in U$, $v \in V- U$的边中,选取具有最小权值的边$(u, v)$,将顶点 v 加入集合$U$中,将边$(u, v)$加入集合 T 中,如此不断重复,直到$U=V$时,最小生成树构造完毕,这时集合$T$中包含了最小生成树的所有边。

$Kruskal$ 算法

$Kruskal$算法是一种按照网中边的权值递增的顺序构造最小生成树的方法。设无向连通网为$G= (V,E)$,令$G$的最小生成树为$T$,其初态为$T= (V, \{\})$。

基本思想:按照边的权值由小到大的顺序,考察$G$的边集$E$中的各条边。若被考察的边的两个顶点属于$T$的两个不同的连通分量,则将此边作为最小生成树的边加入到$T$中,同时把两个连通分量连接为一个连通分量;若被考察边的两个顶点属于同个连通分量,则舍去此边,以免造成回路,如此重复,当$T$中的连通分量个数为 $1$ 时,此连通分量便为$G$的一棵最小生成树。

最短路径

$Dijkstra$ 算法

  1. 初始化:先找出从源点$V$到各终点$V_k$的直达路径$(V_o,V_k)$即通过一条弧到达的路径。
  2. 选择:从这些路径中找出一条长度最短的路径$(Vo,u)$ 。
  3. 更新:然后对其余各条路径进行适当调整:若在图中存在弧$(u,V_k)$ ,且$(V_o,U) + (u,V_k) < (V_o,V_k)$ ,则以路径$(V_o,U,V_k) $代替$(V_o,V_k) $。

在调整后的各条路径中,再找长度最短的路径,依此类推。

2.jpg

应用

对于有向无环图

$AOV$网:解决拓扑排序
用一个有向图表示一个工程的各子工程及其相互制约的关系,其中以顶点表示活动,弧表示活动之间的优先制约关系,称这种有向图为顶点表示活动的网,简称$AOV$网(Activity On Vertex network)。

$AOE$网:解决关键路径
用一个有向图表示一个工程的各子工程及其相互制约的关系,以弧表示活动,以顶点表示活动的开始或结束事件,称这种有向图为边表示活动的网,简称为$AOE$网(Activity On Edge) 。

对于$AOV$网:若从$i$到$j$有一条有向路径,则$i$是$j$的前驱;
$j$是$i$的后继。若$<i,j>$是网中有向边,则$i$是$j$的直接
前驱; $j$是$i$的直接后继。$AOV$网不允许有回路。

拓扑排序

在$AOV$网没有回路的前提下,我们将全部活动排列成一个线性序列,使得若 AOV 网中有弧$<i, j>$存在,则在这个序列中,$i $一定排在$j$的前面,具有这种性质的线性序列称为拓扑有序序列,相应的拓扑有序排序的算法称为拓扑排序。

方法:

  1. 在有向图选择一个无前驱的顶点且输出
  2. 从图中删除该顶点和所有以它为尾的弧
  3. 重复上述两步,直到全部顶点均输出。或图中不存在无前驱的顶点为止。

拓扑序列不一定是唯一的。

检测 AOV 网中是否存在环方法:
对有向图构造其顶点的拓扑有序序列,若网中所有顶点都在它的拓扑有序序列中,则该 AOV 网必定不存在环。

关键路径

把工程计划表示为边表示活动的网络,即 AOE 网,用顶点表示事件,弧表示活动,弧的权表示活动持续时间。

我们关心两个问题:

  1. 完成整项工程至少需要多少时间?
  2. 哪些活动是影响工程进度的关键?

关键路径需要定义四个描述量

解释
$V_e(Vj)$表示事件$V_j$最早发生时间
$V_l(V_j)$表示事件$V_j$最迟发生时间
$e(a_i)$表示活动$a_i$最早开始时间
$l(a_i)$表示活动$a_i$最迟开始时间

$$ l(i) - e(i) = t_{完成活动 a_i 的时间余量} $$

关键活动满足:$l(i) = e(i)$

由关键活动组成的路径称为,关键路径。

查找

查找是一个在计算机中十分重要的一种操作。

先以线性表为例介绍查找思想。

顺序查找

应用范围:

  • 顺序表或线性链表表示的静态查找表
  • 表内元素之间无序

本质上就是 for 语句遍历,为避免越界可以有所优化,将待查元素放于表头,则能保证一定找到。不会发生越界。

$ST.length$较大时,此改进能使进行一次查找所需的平均时间几乎减少一半。减少一次比较操作。

折半查找(对分查找)

顺序查找算法十分简单,逻辑次序无要求。但 ASL 太长,时间效率太低。折半查找的方式前提是有序

  • 设表长为 n, low、high 和 mid 分别指向待查元素所在这间的上界、下界和中点,key 为给定的要查找的值:
  • 初始时,令$low=1, high=n, mid=\frac{low+ high}2$
  • 让$k$与$mid$指向的记录比较

    • 若$key==R[mid].key$,查找成功
    • 若$key<R[mid].key$,则$high=mid-1$
    • 若$key> R[mid].key$,则$low=mid+1$
int Search_Bin(SSTable ST, KeyType key){ //循环法
    low = 1; 
    high = ST.length;
    while (low <= high) {
        mid = (low + high)/ 2;
        if (ST.R[mid].key == key){
            return mid;
        }else if(key < ST.R[mid].key){//缩小查找区间
            high=mid-1; //继续在前半区间进行查找
        }else{
            low=mid+1; //继续在后半区间进行查找
        }
    }
    return 0 ;
}

int Search_Bin(SSTable ST, keyType key, int low,int high){
    if(low>high){
        return 0;
    }
    mid = (low + high) / 2;
    if(key= =ST.elem[mid].key)
        return mid;
    else if(key <STelem[mid1.key]
        return Search_Bin(ST, key, low, mid-1);
    else
        return Search_Bin(ST, key, mid+1, high);
}

性能分析

$$ ASL \approx \log_2(n+1)-1 $$

分块查找

前提是表分成了几块,分块有序,但块内无顺序要求

方法:

  • 将表分成几块,且表或者有序,或者分块有序; 若$i< j$,则第 j 块中所有记录的关键字均大于第$i$块中最大关键字。
  • 建立"索引表"(每个结点含有最大关键字域和指向本
    块第一个结点的指针,且按关键字有序)。

查找过程:先确定待查记录所在块(顺序或折半查找),再在块内查找(顺序查找)

分析

  • 优点:插入和删除比较容易,无需进行大量移动。
  • 缺点:要增加一个索引表的存储空间并对初始索引表进行排序运算。
  • 适用情况:如果线性表既要快速查找又经常动态变化,则可采用分块查找。

树表查找

对于顺序表来说,为了维护表的有序性,在插入、删除操作较为频繁时,需要大量移动元素,效率十分低。故采用<u>动态生成树表</u>进行查询。

二叉排序树(Binary Sort Tree)又称为二叉搜索树、二叉查找树,
定义: 二叉排序树或是空树,或是满足如下性质的二叉树:

  1. 若其左子树非空,则左子树上所有结点的值均小于根结点的值。
  2. 若其右子树非空,则右子树上所有结点的值均大于等于根结点的值。
  3. 其左右子树本身又各是一棵二叉排序树。

二叉排序树的中序遍历输出为递增顺序。

若查找的关键字等于根结点,成功
否则

  • 若小于根结点,查其左子树
  • 若大于根结点,查其右子树

在左右子树上的操作类似

若二叉排序树为空,则查找失败,返回空指针。
若二叉排序树非空,将给定值 key 与根结点的关键字
T-> data.key进行比较:
① 若 key 等于T->data.key,则查找成功,返回根结点地址;
② 若 key 小于T->data.key,则进一步查找左子树;
③ 若 key 大于T->data.key,则进一步查找右子树。

BSTree SearchBST(BSTree T,KeyType key) {
    if(T||key==T->data.key){
        return T;
    }else if (key < T->data.key){
        return SearchBST(T->lchild.key);
    }
    else{
        return SearchBST(T->rchild.key);
    }
}

算法分析

一颗二叉排序树最大查询次数为树的高度

含有 n 个结点的二叉排序树的平均查找长度和树的形态有关

最好情况下:$ASL = \log_2{n}+1; O(\log_2{n})$

最差情况下:$ASL = \frac{n+1}{2}; O(n)$

要想达到最好效果,需要对二叉树做平衡化处理。

插入

  • 若二叉排序树为空,则插入结点作为根结点插入到空树中
  • 否则,继续在其左、右子树上查找。

    • 树中已有,不再插入。
    • 树中没有

      • 查找直至某个叶子结点的左子树或右子树为空为止,则插入结点应为该叶子结点的左孩子或右孩子。

生成

从空树出发,经过一系列查找插入操作。

一个无序序列可通过构造二叉排序树而变成一个有序序列。
构造树的过程就是对无序序列进行排序的过程。

插入的结点均为叶子结点,故无需移动其他结点。相当于在有序序列上插入记录而无需移动其他记录。
但是:关键字的输入顺序不同,建立的不同二叉排序树。

删除

从二叉排序树中删除一个结点, 不能把以该结点为根的子树者删除,只能删掉该结点,并且还应保证删除后所得的二叉树仍然满足二叉排序树的性质不变。

由于中序遍历二叉排序树可以得到一个递增有序的序列。那么,在二叉排序树中删去一个结点相当于删去有序序列中的一个结点。

  • 将因删除结点而断开的二叉链表重新链接起来
  • 防止重新链接后树的高度增加

平衡二叉树

查找效率和树的形态有关,故需要平衡化。

平衡二叉树(balanced binary tree)又称 AVL 树(Adelson-Velskii and Landis)。
一棵平衡二叉树或者是空树, 或者是具有下列性质的二叉排序树:

  1. 左子树与右子树的高度之差的绝对值小于等于 1;
  2. 左子树和右子树也是平衡二叉排序树。

为了方便起见,给每个结点附加一个数字,给出该结点左子树与右子树的高度差。这个数字称为结点的平衡因子(BF)
$ 平衡因子=结点左子树的高度-结点右子树的高度 $
根据平衡二叉树的定义,平衡二叉树上所有结点的平衡因子只能是-1、0 或 1。

平衡化

A: 失衡结点。不止一个失衡结点时,为最小失衡子树的根结点
B: A 结点的孩子,C 结点的双亲
C: 插入新结点的子树

调整原则:降低高度,保持二叉排序树性质。

散列表

基本思想:记录的存储位置和关键字之间存在对应关系

存在关系:$Loc(i) = Hash(key)$

查找效率非常高,达到$O(1)$,但空间效率低下。

术语

散列方法(杂凑法):选取某个函数,依该函数按关键字计算元素的存储位置,并按此存放;查找时,由同一个函数对给定值$k$计算地址,将 k 与地址单元中元素关键码进行比,确定查找是否成功。

散列函数(杂凑函数):散列方法中使用的转换函数。

散列表(杂凑表):按上述思想构造的表。

散列表构造

根据元素集合的特性构造
要求一: $n$个数据原仅占用$n$个地址,虽然散列查找是以空间换时间,但仍希望散列的地址空间尽量小。
要求二:无论用什么方法存储,目的都是尽量均匀地存放元素,以避免冲突。

直接定址法

$Hash(key) = akey + b (a、 b 为常数)$
优点:以关键码 key 的某个线性函数值为散列地址,不会产生冲突
缺点:要占用连续地址空间,空间效率低。

除留余数法

$Hash(key)= key \text{ } mod \text{ } p \text{ } \text{p 是一个整数}$
关键:如何选取合适的$p$

防冲突

开放定址法(开地址法)

$H_i = (Hash(key) + d_i) \text{ } mod \text{ } m \text{ } (1 \leq i \lt m)$

其基本思想:出现冲突时,去寻找下一个空的散列地址,只要散列表足够大,就一定能找到。

线性探测法

基于开放定址法,$d_i$为 $1、2、3、\cdots$

二次探测法

基于开放定址法,$d_i$为 $1^2,-1^2,2^2,-2^2,\cdots,q^2$

伪随机探测法

基于开放定址法,$d_i$为伪随机数

链地址法(拉链法)

基本思想:相同散列地址的记录链成一单链表,$m$个散列地址就设$m$个单链表,然后用一个数组将$m$个单链表的表头指针

优点:非同义词不会冲突,没有聚集的现象,即相同地址冲突时,因为开放定址过程中,会出现$mod$后再次出现冲突的情况。

性能分析

使用平均查找长度 ASL 来衡量查找算法,ASL 取决于

  • 散列函数
  • 处理冲突的方法
  • 散列表的装填因子$\alpha$

$$ \alpha = \frac{表中插入的记录数}{哈希表长度} $$

$\alpha$反映了发生冲突的可能性

$$ ASL \approx 1 + \frac{\alpha}{2} \text{(拉链法)}\\ ASL \approx \frac{1}{2}( 1 + \frac{1}{1-\alpha}) \text{(线性探测)}\\ ASL \approx -\frac{1}{\alpha}\ln(1-\alpha) \text{(随机探测)} $$

总结

  • 散列表技术具有很好的平均性能),优于一些传统的技术
  • 链地址法优于开地址法
  • 除留余数法作散列函数优于其它类型函数

排序

排序方法的分类:

  • 按数据存储介质:内部排序和外部排序
  • 按比较器个数:串行排序和并行排序
  • 按主要操作:比较排序和基数排序
  • 按辅助空间:原地排序和非原地排序
  • 按稳定性:稳定排序和非稳定排序
  • 按自然性:自然排序和非自然排序

直接插入排序(稳定)

每步将一个待排序的对象,按其关键码大小,插入到前面已经排好序的一组对象的适当位置上,直到对象全部插入为止。

void InsertSort( SqList &L ) {
    int i, j;
    for (i=2; i<=L.length; ++i) {
        if (L.r[i].key < L.r[i-1].key){ //若"<",需将L.r[i]插入有序子表
        L.r[0]=L.r[i]; // 复制为哨兵
            for (j=i-1; L.r[0].key<L.r[j].key; -j){
                L.r[j+1]=L.r[j]; // 记录后移
                L.r[j+ 1]=L.r[0];
                //插入到正确位置
            }
        }
    }
}

性能

平均比较次数:$\frac{1}{4} \cdot(n+2)(n-1)$

平均移动次数:$\frac{1}{4} \cdot(n+6)(n-1)$

折半插入排序(稳定)

void BInsertSort( SqList &L )
{
    for ( i = 2; i <= L.length; ++i )       /* 依次插入第2~第n个元素 */
    {
        L.r[0]    = L.r[i];               /* 当前插入元素存到“哨兵”位置 */
        low    = 1 : high = i - 1;     /* 采用二分查找法查找插入位置 */
        while ( low <= high )
        {
            mid = (low + high) / 2;
            if ( L.r[0].key < Lr[mid].key ){
                high = mid - 1;
            }else{
                low = mid + 1;
            } 
        } /* 循环结束,high+ 1则为插入位置 */
        for ( j = i - 1; j >= high + 1; --j ){
            L.r[j + 1] = Lr[); /* 移动元素 */
        }
        L.r[high + 1] = L.r[O]; /* 插入到正确位置 */
} /* BInsertSort */

希尔排序(不稳定)

void ShellSort(Sqlist &L, int dIta[], int t) {
    //按增量序列dIta[0..t- 1]对顺序表L作希尔排序。
    for (k=0; k<t; ++k) {
        ShellInsert(L, dlta[k]);
        //-趟增量为dlta[k]的插入排序
    }
}
//ShellSort
void ShellInsert(SqList &, int gk) {
    //对顺序表L进行一趟增量为dk的Shel排序, dk为步长因子
    for (i=dk+1; i<=L.length; ++i){
        if(r[j].key < r[i-dk].key) {
            r[0]=r[i];
            for (j=i-dk; j>0 &&(r[0].key<r[j].key); j=j-dk)
            r[j+dk]=r[j];
            r[j+ dk]=r[0];
        }
    }

}
  • $Hibbard$增量序列

    • $D_k=2^{k-1}$ 相邻元素互质
    • 最坏情况: $T_{worst}=O(n^\frac{3}{2})$
    • 猜想: $T_{avg}=O(n^{\frac{5}{4}})$
  • $Sedgewick$增量序列

    • ${1,5,19,41,109...}$
    • $ 9\times4^i - 9\times2^i + 1 $
    • $ 4^i-3\times2^i+1 $
    • 最坏情况: $T_{worst}=O(n^\frac43)$
    • 猜想:$T_{avg}=O(n^\frac76)$

冒泡排序

基于简单交换思想,不断将两个记录两两比较,按照前小后大的规则进行交换。

void bubble_sort(SqList &L){ //冒泡排序算法
    int m,i,j;
    RedType x;
    int flag = 1;
    for(m=1; m<=n-1 && flag = 1; m++) { //总共需m趟
        flag = 0;
        for(j=1;j<=n-m;j++){
            if(L.r[j].key> L.r[j+1].key){
                flag = 1;
                x=L.r[j]; 
                L.r[j]=L.r[j+1]; 
                L.r[j+1]=x; 
            }
        } //for
    }
}

优点:每趟结束时,不仅能挤出一个最大值到最后面位置,还能同时部分理顺其他元素;

一旦某一趟比较时不出现记录交换,说明已排好序了,就可以结束本算法。

算法评价

  • 最好情况(正序)

    • 比较次数:$n-1$
    • 移动次数:0
  • 最坏情况(逆序)

    • 比较次数:$\Sigma^{n-1}_{i=1}(n-i) = \frac12(n^2 - n)$
    • 移动次数:$3 \cdot \Sigma^{n-1}_{i=1}(n-i) = \frac32(n^2 - n)$

冒泡排序最好时间复杂度是$O(n)$
冒泡排序最坏时间复杂度为$O(n^2)$
冒泡排序平均时间复杂度为$O(n^2)$
冒泡排序算法中增加一个辅助空间 temp,辅助空间为$S(n)=O(1)$
冒泡排序是稳定

快速排序

通过一趟排序,将待排序记录分割成独立的两部分,其中一部分记录的关键字均比另一部分记录的关键字小, 则可分别对这两部分记录进行排序,以达到整个序列有序。

具体实现:选定一个中间数作为参考,所有元素与之比较,小的调到其左边,大的调到其右边。
(枢轴)中间数:可以是第一个数、最后一个数、最中间一个数、任选一个数等。

void QSort(SqList &L, int low, int high){ //对顺序表L快速排序
    if (low < high){ // 长度大于1
        pivotloc = Partition(L, low, high);
        //将L.r[low.high]-分为二,pivotloc为枢轴元素排好序的位置
        QSort(L, low, pivotloc-1); // 对低子表递归排序
        QSort(L, pivotloc+ 1, high); //对高子表递归排序
    }//endif 
} // QSort
int Partition(SqList & L,int low, int high) {
    L.r[Q] = L.r[low];
    pivotkey = L.r[low].key;
    while (1ow < high) {
        while (low < high && L.r[high].key >= pivotkey) --high;
        L.r[low] = L.r[high];
        while (low < high && L.r[low].key <= pivotkey) ++low;
        L.r[high] = L.r[low];
        L.r[low] = L.r[O];
        return low;
    }
}

算法评价

可以证明,平均计算时间是$O(nlog_2n)$。

  • Qsort( ): $O(log_2n)$
  • Partition( ): $O(n)$

由于程序中使用了递归,需要递归调用栈的支持,而栈的长度取决于递归调用的深度。(即使不用递归, 也需要用用户栈)

  • 在平均情况下:需要$O(logn)$的栈空间
  • 最坏情况下:栈空间可达$O(n)$。

快速排序是不稳定

输入数据次序越乱,所选划分元素值的随机性越好,排序速度越快,快速排序不是自然排序方法。

改变划分元素的选取方法,至多只能改变算法平均情况的下的世界性能,无法改变最坏情况下的时间性能。即最坏情况下,快速排序的时间复杂性总是$O(n^{2})$

简单选择排序

在待排序的数据中选出最大(小)的元素放在其最终的位置。

  1. 首先通过$n$次关键字比较,从$n$个记录中找出关键字最小的记录,将它与第一个记录交换
  2. 再通过$n-2$次比较,从剩余的$n-1$个记录中找出关键字次小的记录,将它与第二个记录交换
  3. 重复上述操作,共进行$n-1$趟排序后,排序结束
void SelectSort(SqList & K) {
    for (i = 1; i < L.length; ++i) {
        k = i;
        for (j = i + 1; j <= L.length; j++) {
            if (L.r[j.key < L.r[k].key) {
                k = j;
            }
        }
        if (k != i) {
            L.r[i], L.r[k] = L.k[i], L.r[k]; //! 非标准C写法 编者注
        }
    }
}
//不稳定

算法评价

  • 记录移动次数

    • 最好情况:$ 0$
    • 最坏情况: $3(n-1)$
  • 比较次数:无论待排序列处于什么状态,选择排序所需进行的"比较"次数都相同

    • $\Sigma^{n-1}_{i=1} = \frac{n}{2}(n-1)$

堆排序

堆的定义:

若有

$n$个元素的序列$\{a_1,a_2,\cdots\}$满足

$$ a_i \leq a_{2i}, a_i \leq a_{2i+1} $$

称为小根堆,反之大根堆。

从堆的定义可以看出,堆实质是满足如下性质的完全二叉树:二叉树中任一非叶子结点均小于(大于)它的孩子结点。

若在输出堆顶的最小值(最大值)后,使得剩余$n-1$个元素的序列重又建成一个堆,则得到$n$个元素的次小值(次大值)……如此反复,便能得到一个有序序列,这个过程称之为堆排序。

如何在输出堆顶元素后,调整剩余元素为一个新的堆?

  • 小根堆:

    1. 输出堆顶元素之后,以堆中最后一个元素替代之;
    2. 然后将根结点值与左、右子树的根结点值进行比较,并与其中小者进行
      交换;
    3. 重复上述操作,直至叶子结点,将得到新的堆,称这个从堆顶至叶子的
      调整过程为“筛选”

堆的建立

将初始无序的 R[1]到 R[n]建成一个小根堆,可用以下语句实现:

void HeapSort (elem R[]){ //对R[1]到R[n]进行堆排序
    int i;
    for(i= n/2;i>=1; i--)
        HeapAdjust(R,i,n); //建初始堆
    for(i=n; i>1; i--){ //进行n - 1趟排序
        Swap( R[1], R[i]); //根与最后一 个元素交换
           HeapAdjust(R, 1,i-1); //对R[1]到R[i -1]重新建堆
    }
} //HeapSort

实质上,堆排序就是利用完全二叉树中父结点单孩子结点它间的内在关系来排序的。

算法分析

  • 初始堆化时间不超过$O(n)$
  • 排序阶段(不含初始堆化)

    • 一次重新堆化时间不超过$O(\log{n})$
    • $n-1$次不超过$O(n \cdot \log{n})$

堆排序的时间主要耗费在建初始堆和调整建新堆时进行的反复筛选上。堆排序在最坏情况下,其时间复杂度也为$O(n\cdot log_2{n})$,这是堆排序的最大优点。无论待排序列中的记录是正序还是逆序排列,都不会使堆排序处于最好或最坏的状态。

另外,堆排序仅需一个记录大小供交换用的辅助存储空间。
然而堆排序是一种不稳定的排序方法,它不适用于待排序记录个数$n$较少的情况,但对于$n$较大的文件还是很有效的。

归并排序

基本思想是将两个或以上的有序子序列归并为一个有序序列。

关键问题:如何将两个有序序列合成一个有序序列?

这个问题之前的线性表章节中已经学习过了。

算法分析

时间效率:$O(n \cdot log(2n))$

空间效率:$O(n)$

是稳定排序

基数排序

基本思想:分配 + 收集。

也叫桶排序或箱排序:设置若干个箱子,将关键字为$k$的记录放入第$k$个箱
子,然后在按序号将非空的连接。

基数排序: 数字是有范围的,均由 0-9 这十个数字组成,则只需设置十个
箱子,相继按个、十、百..进行排序。

算法分析

时间效率:$O(k \cdot (n+m))$

$k$ 为关键字个数

$m$ 为关键字取值范围$m$个值

空间效率:$O(n+m)$

稳定性:稳定

总结

3.jpg

  1. 时间性能

    1. 按平均的时间性能来分,有三类排序方法:

      • 时间复杂度为$O(n\log{n})$的方法有:

        • 快速排序、堆排序和归并排序,其中以快速排序为最好;
      • 时间复杂度为$O(n^2)$的有:

        • 直接插入排序、冒泡排序和简单选择排序,其中以直接插入为最好,特别是对那些对关键字近似有序的记录序列尤为如此;
      • 时间复杂度为$O(n)$的排序方法只有:

        • 基数排序。
    2. 当待排记录序列按关键字顺序有序时,直接插入排序和冒泡排序比心到
      $O(n)$的时间复杂度;而对于快速排序而言,这是最不好的情况,此时的时间

    性能退化为$O(n^2)$,因此是应该尽量避免的情况。

    1. 简单选择排序、堆排序和归并排序的时间性能不随记录序列中关键字的
      分布而改变。
  2. 空间性能:指的是排序过程中所需的辅助空间大小

    • 所有的简单排序方法(包括:直接插入、冒泡和简单选择)和堆排序的空
      间复杂度为$O(1)$
    • 快速排序为$O(\log{n})$,为栈所需的辅助空间
    • 归并排序所需辅助空间最多,其空间复杂度为$O(n)$
    • 链式基数排序需附设队列首尾指针,则空间复杂度为$O(rd)$
  3. 排序方法的稳定性能

    • 稳定的排序方法指的是,对于两个关键字相等的记录,它们在序列中的相
      对位置,在排序之前和经过排序之后,没有改变。
    • 当对多关键字的记录序列进行 LSD 方法排序时,必须采用稳定的排序方法。
    • 对于不稳定的排序方法,只要能举出一个实例说明即可。
    • 快速排序和堆排序是不稳定的排序方法。
  4. 关于“排序方法的时间复杂度的下限”

    • 本章讨论的各种排序方法,除基数排序外,其它方法都是基于“比较关键
      字”进行排序的排序方法,可以证明,这类排序法可能达到的最快的时间

    复杂度为$O(n\log{n})$。
    (基数排序不是基于“比较关键字”的排序方法,所以它不受这个限制)。

    • 可以用一棵判定树来描述这类基于“比较关键字”进行排序的排序方法。
Last Modified: March 15, 2021
Archives QR Code
QR Code for this page
Tipping QR Code