数据结构

发布于 20 天前  16 次阅读 本文共27658个字


No.1 时空复杂度

时间复杂度

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

循环 N 次,而 i = i * 2 ,所以
2^{T(n)} \leq n

T(n) \leq log_2n = O(log_2n)
所以

时间复杂度
O(log_2n)

空间复杂度

是对一个算法在运行过程中临时占用的存储空间大小的量度

No.2 递归

递归模型

递归出口递归体组成

① 对原问题f(s)进行分析,假设出合理的“较小问题”f(s') ;
② 假设f(s')是可解的,在此基础上确定f(s)的解,即给出f(s)与f(s')之间的关系;
③ 确定一个特定情况(如f(1)或f(0))的解,由此作为递归出口.

1. 遍历所有节点(中序、先序、后序)

//
// Created by Miku on 2020/6/21.
//

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <malloc.h>
#include <time.h>

#define TElemType int

typedef struct BiTNode{
    TElemType data;
    struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;

void CreateBiTree(BiTree *T){
    *T=(BiTNode*)malloc(sizeof(BiTNode));
    (*T)->data=1;
    (*T)->lchild=(BiTNode*)malloc(sizeof(BiTNode));
    (*T)->rchild=(BiTNode*)malloc(sizeof(BiTNode));

    (*T)->lchild->data=2;
    (*T)->lchild->lchild=(BiTNode*)malloc(sizeof(BiTNode));
    (*T)->lchild->rchild=(BiTNode*)malloc(sizeof(BiTNode));
    (*T)->lchild->rchild->data=5;
    (*T)->lchild->rchild->lchild=NULL;
    (*T)->lchild->rchild->rchild=NULL;
    (*T)->rchild->data=3;
    (*T)->rchild->lchild=(BiTNode*)malloc(sizeof(BiTNode));
    (*T)->rchild->lchild->data=6;
    (*T)->rchild->lchild->lchild=NULL;
    (*T)->rchild->lchild->rchild=NULL;
    (*T)->rchild->rchild=(BiTNode*)malloc(sizeof(BiTNode));
    (*T)->rchild->rchild->data=7;
    (*T)->rchild->rchild->lchild=NULL;
    (*T)->rchild->rchild->rchild=NULL;
    (*T)->lchild->lchild->data=4;
    (*T)->lchild->lchild->lchild=NULL;
    (*T)->lchild->lchild->rchild=NULL;
}

void displayElem(BiTNode* elem){
    printf("%d ",elem->data);
}

void PreOrderTraverse(BiTree T){
    if (T) {
        displayElem(T);
        PreOrderTraverse(T->lchild);
        PreOrderTraverse(T->rchild);
    }

    return;
}

void CenterOrderTraverse(BiTree T){
    if(T){
        CenterOrderTraverse(T->lchild);
        printf("%d ", T->data);
        CenterOrderTraverse(T->rchild);
    }
    return;
}

void AfterOrderTraverse(BiTree T){
    if (T){
        AfterOrderTraverse(T->lchild);
        CenterOrderTraverse(T->rchild);
        printf("%d ", T->data);
    }
    return;
}

int main() {
    BiTree Tree;
    CreateBiTree(&Tree);
    printf("先序遍历\n");
    PreOrderTraverse(Tree);
    printf("\n中序遍历\n");
    CenterOrderTraverse(Tree);
    printf("\n后序遍历\n");
    AfterOrderTraverse(Tree);
}

2. 二叉树所有节点个数

f(b) = 0 \ \ \ \ \ b = NULL\
f(b) = f(b->lchild) + f(b->rchild) + 1 \ \ \ \ \ \ b\neq NULL

代码承接上树,下面直接列算法

// 计算个数
int CountNode(BiTree T){
    // 如果没有节点
    if (T == NULL){
        return 0;
    } else{
        return CountNode(T->lchild) + CountNode(T->rchild) + 1;
    }
}

int main(){
        printf("\n节点个数: %d", CountNode(Tree));
}

3. 设计求f(n)=1+2+...+n的递归算法

f(n) = 1; \ \ n = 1\
f(n) = n + f(n - 1) ; \ \ n > 1;

代码承接上树,下面直接列算法

// 求解f(n)
int CalculateN(int n){
    if (n == 1)
        return 1;
    else{
        return CalculateN(n - 1) + n;
    }
}
int main() {
      printf("f(n)= %d", CalculateN(6));
}

4. 反转字符串

编写一个函数,其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。

不要给另外的数组分配额外的空间,你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。

分析

  • 原地修改
  • ASCII 码表均为

思路

// 颠倒字符串
void reverseString(char* s, int sSize){
    // O(1)
    char temp;
    // 前后交换
    for (int i = 0; i < sSize / 2; ++i) {
        temp = s[i];
        s[i] = s[sSize - 1 - i];
        s[sSize - 1 - i] = temp;
    }
    for (int j = 0; j < sSize; ++j) {
        printf("%c", s[j]);
    }
}
int main() {
    char s[] = {'a', 'b', 'c', 'd', 'e', 'f', 'g'};
    reverseString(s, 7);
}

5. 两两交换链表中的节点

给定一个链表,两两交换其中相邻的节点,并返回交换后的链表。

你不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。

示例:

给定 1->2->3->4, 你应该返回 2->1->4->3.

思路

  • 1 -> 2 -> 3 -> 4
  • 4 - > 3
  • 1 -> 4 -> 3
  • 2 -> 1 -> 4 -> 3
struct ListNode {
         int val;
         struct ListNode *next;
};

struct ListNode* swapPairs(struct ListNode* head){
    // 递归结束的条件
    if(head==NULL)
    {
        return NULL;
    }
    // 递归结束的条件
    if(head->next==NULL)
    {
        return head;
    }
    // 设双指针,分别指向头和头的下一个
    struct ListNode* pr=head;
    struct ListNode* ps=head->next;
    // 递归得出 head->next->next,再执行 head->next = head
    pr->next=swapPairs(ps->next);
    ps->next=pr;
    return ps;
}

No.3 线性结构

一般线性表

逻辑结构

具有相同特性的数据元素的一个有限序列。不是集合

存储结构 - 顺序表

typedef struct{
    ElemType elem[MaxSize];  // 存放顺序表元素
    int Length;   // 存储顺序表的长度
}SqList;

存储结构 - 链表

typedef struct {
    ElemType data;
    structNode *next;  // 指向后继结点
}LinkList;

存储结构 - 双链表

typedef struct DNode{
    ElemType data;
    struct DNode *prior;   // 指向前驱结点
    struct DNode *next;  // 指向后继结点
}DLinkList;  

No.4 单链表算法实现

单链表头插入法

 void CreateListF(LinkList *&L,ElemType a[],int n)
  {       LinkList *s;int i;
          L=(LinkList *)malloc(sizeof(LinkList));  /*创建头结点*/
          L->next=NULL;
          for (i=0;i<n;i++)
          {      s=(LinkList *)malloc(sizeof(LinkList));
                      /*创建新结点*/
                  s->data=a[i]; s->next=L->next;        
                      /*将*s插在原开始结点之前,头结点之后*/
                  L->next=s;
           }
  }

单链表尾插入法

需要新增一个尾巴进行插入

void CreateListR(LinkList *&L,ElemType a[],int n)
  {    LinkList *s,*r;int i;
        L=(LinkList *)malloc(sizeof(LinkList));     
            /*创建头结点*/
        L->next=NULL;
        r=L;    /*r始终指向终端结点,开始时指向头结点*/
        for (i=0;i<n;i++)
        {    s=(LinkList *)malloc(sizeof(LinkList));
               /*创建新结点*/
              s->data=a[i];r->next=s;  /*将*s插入*r之后*/
              r=s;
        }
        r->next=NULL;   /*终端结点next域置为NULL*/
  }

1. 拆分线性表

设C={a1,b1,a2,b2,…,an,bn}为一线性表,采用带头结点的hc单链表存放,编写一个算法,将其拆分为两个线性表,使得:

​ A={a1,a2,…,an},B={b1,b2,…,bn}

void fun(LinkList *hc, LinkList *&ha, Linklist *&hb){
    LinkList *p = hc->next, *ra, *rb;
    ha = hc; // ha的头结点利用hc的头结点
    ra = ha; // ra 始终指向 ha的末尾结点
    hb = (LinkList)*malloc(sizeof(LinkList));  // 创建hb头结点
    rb = hb; // rb 始终指向hb的末尾结点
    while(p != NULL){
        ra->next = p;
        ra = p; // 将 *p 链到 ha 单链表末尾
        p = p->next;
        rb->next = p;
        rb = p;  // 将 *p 链到 hb 单链表末尾
        p = p->next;
    }
    ra->next=rb->next=NULL; /*两个尾结点的next域置空*/
}

2. 删除单链表元素

已知线性表元素递增有序,并以带头结点的单链表作存储结构,设计一个高效算法,删除表中所有值大于mink且小于maxk的元素(若表中存在这样的元素)。并分析所写算法的时间复杂度。

void delnode(SNode *h, ElemType maxk, ElemType mink){
    SNode *p, *pre;
    if(mark >= mink){
        pre = h;
        p = pre->next;
        while(p!= NULL && p->data <= mink){
            pre = p;
            p = p->next;
        }
        while(p != NULL && p->data < min){  // 删除 p
            pre->next = p->next;
            free(p);  // 释放内存
            p = pre->next;
        }
    }
}

No.5 双链表基本算法实现

重点:插入和删除结点的算法

typedef struct line{
    struct line * prior;  // 指向直接前驱
    int data;
    struct line * next;  // 指向直接后驱
}line;

插入操作

line* insertLine(line * head, int data, int add){
    // 新建数据域为data的结点
    line * temp = (line*)malloc(sizeof(line));
    temp->data = data;
    temp->prior = NULL;
    temp->next = NULL;
    // 插入到链表头,要特殊考虑
    if(add == 1){
        temp->next = head;
        head->prior = temp;
        head = temp;
    }
    else{
        line* body = head;
        // 找到要插入位置的前一个结点
        for(int i = 1; i < add - 1; i++){
            body = body->next;
        }
        // 判断条件为真,说明插入为真为链表尾
        if(body->next == NULL){
            body->next = temp;
            temp->prior = body;
            temp->next = NULL;
        }
        else{
            body->next->prior = temp;
            temp->next = body->next;
            body->next = temp;
            temp->prior = body;
        }
    }
    return head;
}

删除操作

// 删除结点的函数,data为要删除结点的数据域的值
line *delLine(line *head, int data){
    line * temp = head;
    // 遍历链表
    while(temp){
        // 判断当前结点数据域的值与data是否相等
        if(temp->data == data){
            temp->prior->next = temp->next;
            temp->next->prior = temp->prior;
            free(temp);
            return head;
        }
        temp = temp->next;
    }
    printf("链表中无该数据元素");
    return head;
}

No.6 循环链表基本运算的实现

重点:判断最后一个结点

void display_link_list(node * head){
    if(head == NULL){
        printf("this list is empty!\n");
    }
    else{
        node *ptr = head->next;
        while(ptr->next != head){
            ptr = ptr->next;
        }
        printf("最后一个结点为: %5d", ptr->data);
    }
}

1. 存储方式 x 时间

某线性表最常用的操作是在最后一个结点之后插入一个结点或删除第一个结点,故采用 存储方式最节省运算时间。

A. 单链表 B. 仅有头结点的单循环链表
C. 双链表 D. 仅有尾指针的单循环链表

盲猜一个D,因为插入直接 +,删除直接删就行,都是 O(1)

2. 设计算法

设计一个算法在单链表中查找元素值为e的结点序号的算法LocateElem(L,e)。

int LocateElem(LinkList *L, ElemType e){
    int n = 1;
    LinkList *p = L->next;
    // 循环查找
    while(p != NULL && p->data != e){
        p = p->next;
        n++;
    }
    if(p == NULL) return 0;  // 未找到
    else
        return n;
}

No.7 栈

特性

  • 先进后出
  • 逻辑结构:先进后出表

进栈,出栈

# 商业转载请联系作者获得授权,非商业转载请注明出处。
# For commercial use, please contact the author for authorization. For non-commercial use, please indicate the source.
# 协议(License):署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0)
# 作者(Author):小喵钓鱼
# 链接(URL):https://www.lovelycat.top/index.php/2020/06/04/%e6%95%b0%e6%8d%ae%e7%bb%93%e6%9e%84-%e6%b5%81%e7%a8%8b/
# 来源(Source):喵之宫

// 实现链栈
typedef struct lineStack {
    int data;
    struct lineStack* next;
} lineStack;

// 进栈
lineStack* push(lineStack* stack, int a) {
    lineStack* line = (lineStack*)malloc(sizeof(lineStack));
    line->data = a;
    line->next = stack;
    stack = line;
    return stack;
}

// 出栈
lineStack* pop(lineStack* stack) {
    if (stack)
    {
        lineStack* p = stack;
        stack = stack->next;
        printf("弹栈元素: %d", p->data);
        if (stack)
        {
            printf("栈顶元素: %d\n", stack->data);
        }
        else {
            printf("栈已空");
        }
        free(p);
    }
    else {
        printf("栈内没有元素");
        return stack;
    }
    return stack;
}

1. 判断进栈,出栈序列

已知一个栈的进栈序列是1,2,3,…,n,其输出序列是p1,p2,…,pn,若p1=n,则pi的值 。
(A) i (B) n-i
(C) n-i+1 (D) 不确定

C

2. Again

设n个元素进栈序列是1,2,3,…,n,其输出序列是p1,p2,…,pn,若p1=3,则p2的值 。

(A) 一定是2 (B) 一定是1
(C) 不可能是1 (D) 以上都不对

一定不可能是 1!!

C

存储结构

顺序栈

typedef struct
{
    ElemType elem[MaxSize];
    int top;  // 栈指针
}sqlStack;

顺序栈四要素

  • 栈空条件 s.top == -1
  • 栈满条件 s.top == MaxSize - 1
  • 进栈 top++; s.data[s.top] = e
  • 出栈 e = s.data[s.top]; s.top--

链栈

typedef struct linknode{
    ElemType data;  // 数据域
    struct Linknode next;  // 指针域
}LiStack;

带头结点的单链表

  • 栈满条件 s->next == NULL
  • 栈空条件 head->next == NULL

No.8 队列

特性

  • 先进先出

进队、出队

# 商业转载请联系作者获得授权,非商业转载请注明出处。
# For commercial use, please contact the author for authorization. For non-commercial use, please indicate the source.
# 协议(License):署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0)
# 作者(Author):小喵钓鱼
# 链接(URL):https://www.lovelycat.top/index.php/2020/06/04/%e6%95%b0%e6%8d%ae%e7%bb%93%e6%9e%84-%e6%b5%81%e7%a8%8b/
# 来源(Source):喵之宫

#define MaxSize 10
// 实现队列 牺牲掉数组中的一个存储空间 来判断是否满
typedef struct QNode {
    int a[MaxSize];
    // 队尾指针
    int rear;
    // 队头指针
    int front;
}QNode;

QNode * InitQueue() {
    // 初始化队列
    QNode * queue = (QNode*)malloc(sizeof(QNode));
    queue->rear = queue->front = 0;
    return queue;
}

QNode * enQueue(QNode* queue, int data) {
    // 先判断
    if (isFull(queue) == 0)
    {
        printf("空间已经满了,添加失败\n");
    }
    else {
        queue->a[queue->rear % MaxSize] = data;
        queue->rear++;
        printf("添加成功\n");
    }
    return queue;
}

QNode* deQueue(QNode* queue, int *e) {
    if (isEmpty(queue) == 0)
    {
        printf("队列是空的,删除失败\n");
    }
    else {
        *e = queue->a[queue->front];
        queue->front = (queue->front + 1) % MaxSize;
        printf("删除成功\n");
    }
    return queue;
}

存储结构

顺序队

typedef struct{
    ElemType data[MaxSize];
    int front, read;  // 队头,队尾
}SqQueue;

四要素

  • 队空 q.front == q.rear
  • 队满 (q.rear + 1) % MaxSize == q.front
  • 进队 q.rear = (q.rear + 1) % MaxSize; q.data[q.rear] = e
  • 出队 q.front = (q.front + 1) % MaxSize; e = q.data[q.front];

链队

struct qnode 
{
    ElemType data;
    struct qnode * next;
}QNode;   // 数据结点

typedef struct 
{
    QNode *front;
    QNode *rear;  
}LiQueue;  // 头结点

No.9 串

1. 串的定义

存储结构

严格来说,串的存储结构是一种线性存储结构,串结构只用于存储字符类型的数据

子串

假设有两个串 a 和 b,如果 a 中可以找到几个连续字符组成的串与 b 完全相同,则称 a 是 b 的主串,b 是 a 的子串。

子串在主串中的位置,指的是子串首个字符在主串中的位置。

空串

存储 0 个字符的串,例如 S = ""(双引号紧挨着);

空格串

只包含空格字符的串,例如 S = " "(双引号包含 5 个空格);

串相等

2. 顺序串

采用"固定长度的顺序存储结构"来存储字符串,且申请的数组空间长度至少比字符串长度大1,因为最后一位存储字符串的结束标志"\0"。

char str[19]="data.biancheng.net";

3. 链串

使用链表结构存储字符串

#define linkNum 3//全局设置链表中节点存储数据的个数
typedef struct Link {
    char a[linkNum]; //数据域可存放 linkNum 个数据
    struct Link * next; //代表指针域,指向直接后继元素
}link; // nk为节点名,每个节点都是一个 link 结构体

4. 模式匹配算法

不作要求

No.10 数组和稀疏矩阵

数组的定义

相同类型数据元素、有限序列

  • 一维数组,指的是存储不可再分数据元素的数组
  • 二维数组,指的存储一维数组的一维数组
  • n 维数组,指的是存储 n-1 维数组的一维数组;
  • 无论数组的维数是多少,数组中的数据类型都必须一致。

=> 一维数组结构是线性表的基本表现形式,而 n 维数组可理解为是对线性存储结构的一种扩展。

存储结构

以数组A[c1..d1,c2..d2] 为例

  • 以行序为主序(先列后行):按照行号从小到大的顺序,依次存储每一列的元素
LOC(ai,j)=LOC(ac1,c2)+[(i-c1)*(d2-c2+1)+(j-c2)]*k 
  • 以列序为主序 (先行后序):按照列号从小到大的顺序,依次存储每一行的元素。
LOC(ai,j)=LOC(ac1,c2)+[(j-c2)*(d1-c1+1)+(i-c1)]*k 

特殊矩阵的压缩存储

对称矩阵

数据元素沿主对角线相应相等,这类矩阵即对称矩阵

对称矩阵示意图

结合数据结构压缩存储的思想,以使用一维数组存储对称矩阵。由于矩阵沿着对角线两侧数据相等,因此数组只用存储对角一侧(包括对角线)的数据即可

对称矩阵的实现过程是,若存储下三角中的元素,只需将各元素所在的行标 i·和列标j 代入下面的公式:
k = \frac{i *(i -1)}{2} + j - 1
存储上三角的元素要将各元素的行标 i 和列标 j 代入另一个公式:
k = \frac{j *(j -1)}{2} + i - 1
最终求得的 k 值即为该元素存储到数组中的位置(矩阵中元素的行标和列标都从 1 开始)。

例如,在数组 skr[6] 中存储上图中的对称矩阵,则矩阵的压缩存储状态如图 3 所示(存储上三角和下三角的结果相同):

对称矩阵的压缩存储示意图

再从上数组中提取矩阵中位于(3, 1)的元素,由于该元素位于下三角,需要用下三角公式获取元素在数组中的位置即
k = \frac{i * (i - 1)}{2} + j - 1 = 3 + 1 - 1 = 3
结合上skr数组,数组下标为3的位置存储的元素为3

上下三角矩阵

上(下)三角矩阵

  • 上三角矩阵。主对角线下的数据元素全部相同的矩阵
  • 下三角矩阵。主对角线上的数据元素全部相同的矩阵

压缩方式

上(下)三角矩阵采用对称矩阵的方式存储上(下)三角的数据(元素0不用存储)

上(下)三角矩阵存储元素和提取元素的过程和对称矩阵相同。

稀疏矩阵

稀疏矩阵示意图

如果矩阵中,分布大量的元素0,即非0元素非常少,这类矩阵成为稀疏矩阵

压缩方法

只存储矩阵中的非 0 元素,与前面的存储方法不同的是,稀疏矩阵非0元素的存储同时存储该元素所在矩阵中的行标和列标

例如上图中的稀疏矩阵,需存储以下信息

  • (1,1,1):数据元素为 1,在矩阵中的位置为 (1,1);
  • (3,3,1):数据元素为 3,在矩阵中的位置为 (3,1);
  • (5,2,3):数据元素为 5,在矩阵中的位置为 (2,3);
  • 除此之外,还要存储矩阵的行数 3 和列数 3;

压缩存储结构

以下存储结构,均来自网上,有印象即可

  • 三元组顺序表

由于稀疏矩阵中非 0 元素有多个,因此需要建立 triple 数组存储各个元素的三元组。除此之外,考虑到还要存储矩阵的总行数和总列数,因此可以采用以下结构表示整个稀疏矩阵:

//三元组结构体
typedef struct {
    int i,j;//行标i,列标j
    int data;//元素值
}triple;

#define number 20
//矩阵的结构表示
typedef struct {
    triple data[number];//存储该矩阵中所有非0元素的三元组
    int n,m,num;//n和m分别记录矩阵的行数和列数,num记录矩阵中所有的非0元素的个数
}TSMatrix;

可以看到,TSMatrix 是一个结构体,其包含一个三元组数组,以及用于存储矩阵总行数、总列数和非 0 元素个数的变量。

  • 行逻辑链接的顺序表
typedef struct
{
    int i,j;//行,列
    ElemType e;//元素值
}Triple;
typedef struct
{
    Triple  data[MAXSIZE+1];
    int rpos[MAXRC+1];//每行第一个非零元素在data数组中的位置
    int mu,nu,tu;//行数,列数,元素个数
}RLSMatrix;
  • 十字链表

    img

各个节点的存储结构

十字链表的节点结构

typedef struct OLNode
{
    int i, j, e; //矩阵三元组i代表行 j代表列 e代表当前位置的数据
    struct OLNode *right, *down; //指针域 右指针 下指针
}OLNode, *OLink;
typedef struct
{
    OLink *rhead, *chead; //行和列链表头指针
    int mu, nu, tu;  //矩阵的行数,列数和非零元的个数
}CrossList;

广义表

列表,是一种线性存储结构

  • 一个广义表中所含元素的个数称为它的长度.

    GL=(a,(a),(a,b,c,d),()) => 长度为4。

  • 一个广义表中括号嵌套的最大次数为它的深度.

    GL=(a,(a),(a,b,c,d),()) => 深度为2。

  • 表的第一个元素a1为广义表GL的表头,其余部分(a2,…,ai,ai+1,…,an)为GL的表尾.

    • GL=(a,(a),(a,b,c,d),()) => 表头为a,表尾为((a),(a,b,c,d),())

存储结构

typedef struct GLNode{
    int tag;//标志域
    union{
        char atom;//原子结点的值域
        struct{
            struct GLNode * hp,*tp;
        }ptr;//子表结点的指针域,hp指向表头;tp指向表尾
    };
}*Glist;

No.11 树

1. 树的定义

2. 树的表示方法(逻辑表示方法)

  • 树形表示法
  • 文氏图表示法
  • 凹入表示法

    img

  • 括号表示法

3. 树的遍历

  • 先根遍历算法

没找到

  • 后根遍历算法

没找到

4. 树和二叉树的相互转换

树 => 二叉树

  • 加线。在所有兄弟结点之间加一条连线。
  • 去线。树中的每个结点,只保留它与第一个孩子结点的连线,删除它与其他孩子结点之间的连线。
  • 层次调整。以树的根结点为轴心,将整棵树顺时针旋转一定角度,使之层次分明。(注意,第一个孩子是结点的左孩子,兄弟转换过来的孩子是结点的右孩子)

    img

口诀:兄弟相连,长兄为父,孩子靠左。

核心:左孩子,右兄弟

二叉树 => 树

是树转换为二叉树的逆过程,还原结点A的孩子,结点A的左孩子开始,一直向右走,这些结点都是结点A的孩子,遇见顺序就是它们作为结点A孩子的顺序。

  • 加线。若某结点X的左孩子结点存在,则将这个左孩子的右孩子结点、右孩子的右孩子结点、右孩子的右孩子结点...都视为结点X的孩子。将结点X与这些右孩子结点用线连接起来
  • 去线。 删除原来二叉树中所结点与其右孩子结点的连线
  • 层次调整

    img

5. 二叉树的定义

  • 根。
  • 完全二叉树

    如果二叉树中除去最后一层节点为满二叉树,且最后一层的结点依次从左到右分布,则此二叉树被称为完全二叉树。

    完全二叉树示意图

  • 满二叉树

    如果二叉树中除了叶子结点,每个结点的度都为 2,则此二叉树称为满二叉树。

    满二叉树示意图

6. 二叉树的性质

  • 非空二叉树上叶结点树等于双分支结点树 + 1,即
    n_0 = n_2 +1

  • 非空二叉树第 i层上至多有
    2^{i-1}
    个结点

  • 高度为 h的二叉树至多有
    2^h - 1 \ \ (h \geq 1)
    个结点

  • 具有n个(n>0)结点的完全二叉树的高度为log2n+1log2n+1

  • 完全二叉树的性质 。

7. 例题

e-1

将一棵有99个结点的完全二叉树从根这一层开始,每一层从左到右依次对结点进行编号,根结点的编号为1,则编号为49的结点的右孩子编号为 。

A.98 B.99 C.50 D.不存在

对于任意一个完全二叉树来说,如果将含有的结点按照层次从左到右依次标号(如图 3a)),对于任意一个结点 i ,完全二叉树还有以下几个结论成立:

  1. 当 i>1 时,父亲结点为结点 [i/2] 。(i=1 时,表示的是根结点,无父亲结点)
  2. 如果 2i>n(总结点的个数) ,则结点 i 肯定没有左孩子(为叶子结点);否则其左孩子是结点 2i 。
  3. 如果 2i+1>n ,则结点 i 肯定没有右孩子;否则右孩子是结点 2i+1 。

所以,这题,选 B => 2 * 49 + 1

e - 2

深度为5的二叉树至多有 个结点。

A.16 B.32 C.31 D.10

相同满度时满二叉树结点最多,h=5的满二叉树结点个数=25-1=31。C。

8. 二叉树存储结构

顺式存储结构

使用顺序表(数组)来存储二叉树

!!!! 顺序存储只适用于完全二叉树,也就意味着,我们想顺序存储普通二叉树,需要提前将普通二叉树转化为完全二叉树

普通二叉树转化为完全二叉树

只需给二叉树额外添加一些节点,将其"拼凑"成完全二叉树即可

img

完全二叉树的顺序存储,仅需从根节点开始,按照层次依次将树中节点存储到数组即可

img

存储状态

img

同样,存储由普通二叉树转化来的完全二叉树也是如此。

img

链式存储结构

 typedef struct node 
    {   ElemType data;      /*数据元素*/
    struct node *lchild;      /*指向左孩子*/
    struct node *rchild;      /*指向右孩子*/
    } BTNode;

二叉树的遍历

  • 先序遍历
  • 中序遍历
  • 后序遍历
  • 层次遍历(通常借助队列来实现)
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#include<math.h>
/*
实验题目:编写程序实现二叉树的先序遍历、中序遍历和后续遍历的递归算法,
以及层次遍历的算法。
*/

#define TElemType int
typedef struct node {
    TElemType data;
    struct node* lchild, * rchild;
}BSTNode, *BSTTree;


BSTNode CreatBST(BSTTree *T) {
    *T = (BSTNode*)malloc(sizeof(BSTNode));
    (*T)->data = 1;
    (*T)->lchild = (BSTNode*)malloc(sizeof(BSTNode));
    (*T)->rchild = (BSTNode*)malloc(sizeof(BSTNode));

    (*T)->lchild->data = 2;
    (*T)->lchild->lchild = (BSTNode*)malloc(sizeof(BSTNode));
    (*T)->lchild->rchild = (BSTNode*)malloc(sizeof(BSTNode));
    (*T)->lchild->rchild->data = 5;
    (*T)->lchild->rchild->lchild = NULL;
    (*T)->lchild->rchild->rchild = NULL;
    (*T)->rchild->data = 3;
    (*T)->rchild->lchild = (BSTNode*)malloc(sizeof(BSTNode));
    (*T)->rchild->lchild->data = 6;
    (*T)->rchild->lchild->lchild = NULL;
    (*T)->rchild->lchild->rchild = NULL;
    (*T)->rchild->rchild = (BSTNode*)malloc(sizeof(BSTNode));
    (*T)->rchild->rchild->data = 7;
    (*T)->rchild->rchild->lchild = NULL;
    (*T)->rchild->rchild->rchild = NULL;
    (*T)->lchild->lchild->data = 4;
    (*T)->lchild->lchild->lchild = NULL;
    (*T)->lchild->lchild->rchild = NULL;
}

// 层次遍历
int** levelOrder(struct node* root, int* returnSize, int** returnColumnSizes) {
    if (!root)
    {
        *returnSize = 0;
        return 0;
    }
    int** result = (int**)malloc(sizeof(int*) * 2000);
    int i = 0;
    struct node* p = root;
    struct node* queue[2000]; int front = 0, rear = 0;
    queue[rear++] = p;
    *returnColumnSizes = (int*)malloc(sizeof(int) * 2000);
    while (front != rear)
    {
        int size = rear - front;
        result[i] = (int*)malloc(sizeof(int) * size);
        (*returnColumnSizes)[i] = size;
        for (int j = 0; j < size; ++j)
        {
            p = queue[front];
            front = (front + 1) % 2000;
            if (p->lchild)
            {
                queue[rear] = p->lchild;
                rear = (rear + 1) % 2000;
            }
            if (p->rchild)
            {
                queue[rear] = p->rchild;
                rear = (rear + 1) % 2000;
            }
            result[i][j] = p->data;
        }
        ++i;
    }
    *returnSize = i;
    return result;
}

// 输出层次遍历
void disLevel(int** result) {
    printf("[\n");
    for (int i = 0; i < 3; i++)
    {
        printf("  [");
        for (int j = 0; j < pow(2, i); j++)
        {
            printf("%d ", result[i][j]);
        }
        printf("],\n");
    }
    printf("]");
}

// 先序
void BeforeOrderTree(BSTNode* root) {
    if (root == NULL)
    {
        return;
    }
    printf("%d ", root->data);
    if (root->lchild != NULL)
    {
        BeforeOrderTree(root->lchild);
    }
    if (root->rchild != NULL) {
        BeforeOrderTree(root->rchild);
    }
}

void AfterOrderTree(BSTNode* root) {
    if (root == NULL)
    {
        return;
    }
    if (root->lchild != NULL)
    {
        BeforeOrderTree(root->lchild);
    }
    if (root->rchild != NULL) {
        BeforeOrderTree(root->rchild);
    }
    printf("%d ", root->data);
}

// 中序遍历
void CenterOrderTree(BSTNode* root) {
    if (root == NULL)
    {
        return;
    }
    if (root->lchild != NULL)
    {
        BeforeOrderTree(root->lchild);
    }
    printf("%d ", root->data);
    if (root->rchild != NULL) {
        BeforeOrderTree(root->rchild);
    }
}

int main() {
    BSTTree tree;
    CreatBST(&tree);
    printf("先序遍历: \n");
    BeforeOrderTree(tree);
    printf("\n后序遍历: \n");
    AfterOrderTree(tree);
    printf("\n中序遍历: \n");
    CenterOrderTree(tree);
    printf("\n层次遍历: \n");
    int** result = (int**)malloc(sizeof(int*) * 2000);
    int* returnSize = (int*)malloc(sizeof(int*) * 2000);
    result = levelOrder(tree, returnSize, result);
    disLevel(result);
    return 0;
}

9. 例题

D-1

假设二叉树采用二叉链存储结构存储,试设计一个算法,输出一棵给定二叉树的所有叶子结点。

输出一棵二叉树的所有叶子结点的递归模型f()如下:

  • f(b):不做任何事件   若b=NULL
  • f(b):输出b结点的data域 若b为叶子结点
  • f(b):f(b->lchild);f(b->rchild) 其他情况
void OutPutLeaf(BTNode *b){
     if (b!=NULL) 
          { 
                if (b->lchild==NULL && b->rchild==NULL) 
             printf("%c ",b->data);
        DispLeaf(b->lchild);
        DispLeaf(b->rchild);
   }
}

D-2

试设计判断两棵二叉树是否相似的算法,

所谓二叉树t1和t2是相似的指的是t1和t2都是空的二叉树;或者t1和t2的根结点是相似的,t1的左子树和t2的左子树是相似的且t1的右子树与t2的右子树是相似的。

本题的递归模型如下:
true 若t1=t2=NULL
f(t1,t2)= false 若t1、t2之一为NULL,另一不为NULL
f(t1->lchild,t2->lchild) && f(t1->rchild,t2->rchild)
其他情况
对应的算法如下:

 int like(BTNode *b1, BTNode *b2)
    { 
        int like1, like2;
        if (b1==NULL && b2==NULL) 
                   return 1;
        else if (b1==NULL || b2==NULL) 
                   return 0;
        else
        {       like1=like(b1->lchild, b2->lchild);
                    like2=like(b1->rchild, b2->rchild);
                    return (like1 & like2);
    }
}

D-3

设计一个算法求二叉树的所有结点个数。

对应的算法如下:

  int nodenum(BTNode *bt)
     {
             if (bt!=NULL)
                 return(nodenum(bt->lchild)+nodenum(bt->lchild)+1);
             else
                return(0);
    }

D-4

设计一个算法释放一棵二叉树bt的所有结点。

void release(BSTNode *&bt)
{
       if (bt!=NULL)
       {      release(bt->lchild);
              release(bt->rchild);  
              free(bt);
       }
}

10. 线索二叉树

  • 共有2n-(n-1)=n+1个空链域 => 线索化

  • 线索化与某种遍历方式有关

11. 哈夫曼树

  • 路径:在一棵树中,一个结点到另一个结点之间的通路,称为路径。下图中,从根结点到结点 a 之间的通路就是一条路径。

  • 路径长度:在一条路径中,每经过一个结点,路径长度都要加 1 。例如在一棵树中,规定根结点所在层数为1层,那么从根结点到第 i 层结点的路径长度为 i - 1 。下图中从根结点到结点 c 的路径长度为 3。

  • 结点的权:给每一个结点赋予一个新的数值,被称为这个结点的权。例如,下图中结点 a 的权为 7,结点 b 的权为 5。

  • 结点的带权路径长度:指的是从根结点到该结点之间的路径长度与该结点的权的乘积。例如,下图 中结点 b 的带权路径长度为 2 * 5 = 10 。

  • 树的带权路径长度为树中所有叶子结点的带权路径长度之和。通常记作 “WPL” 。例如下图中所示的这颗树的带权路径长度为:

WPL = 7 * 1 + 5 * 2 + 2 * 3 + 4 * 3

img

什么是哈弗曼树

当用 n 个结点(都做叶子结点且都有各自的权值)试图构建一棵树时,如果构建的这棵树的带权路径长度最小,称这棵树为“最优二叉树”,有时也叫“赫夫曼树”或者“哈夫曼树”。

哈弗曼树的构造过程

对于给定的有各自权值的 n 个结点,构建哈夫曼树有一个行之有效的办法:

  1. 在 n 个权值中选出两个最小的权值,对应的两个结点组成一个新的二叉树,且新二叉树的根结点的权值为左右孩子权值的和;
  2. 在原有的 n 个权值中删除那两个最小的权值,同时将新的权值加入到 n–2 个权值的行列中,以此类推;
  3. 重复 1 和 2 ,直到所以的结点构建成了一棵二叉树为止,这棵树就是哈夫曼树。

    img

    上图中,(A)给定了四个结点a,b,c,d,权值分别为7,5,2,4;第一步如(B)所示,找出现有权值中最小的两个,2 和 4 ,相应的结点 c 和 d 构建一个新的二叉树,树根的权值为 2 + 4 = 6,同时将原有权值中的 2 和 4 删掉,将新的权值 6 加入;进入(C),重复之前的步骤。直到(D)中,所有的结点构建成了一个全新的二叉树,这就是哈夫曼树。

哈夫曼树编码的构造过程

哈夫曼树是二叉树,根节点分支下来左0右1,每个字母的编码就从根节点往叶结点读这样

No.12 图

1. 图的基本概念

  • 顶点的度、入度、出度

emmmmmmmmmmmm

  • 完全图

    若图中各个顶点都与除自身外的其他顶点有关系,这样的无向图称为完全图(如图 a))。同时,满足此条件的有向图则称为有向完全图(图 b))。

    完全图示意图

具有 n 个顶点的完全图,图中边的数量为 n(n-1)/2;而对于具有 n 个顶点的有向完全图,图中弧的数量为 n(n-1)。

  • 子图

    指的是由图中一部分顶点和边构成的图,称为原图的子图。

  • 路径和路径长度

  • 连通、连通图和连通分量

    • 图中从一个顶点到达另一顶点,若存在至少一条路径,则称这两个顶点是连通着的。
    • 无向图中,如果任意两个顶点之间都能够连通,则称此无向图为连通图。
    • 若无向图不是连通图,但图中存储某个子图符合连通图的性质,则称该子图为连通分量。

    如下图所示,虽然下图 中的无向图不是连通图,但可以将其分解为 3 个"最大子图",它们都满足连通图的性质,因此都是连通分量。

    0

连通分量的提出是以"整个无向图不是连通图"为前提的,因为如果无向图是连通图,则其无法分解出多个最大连通子图,因为图中所有的顶点之间都是连通的。

  • 强连通图和强连通分量
    • 有向图中,若任意两个顶点 Vi 和 Vj,满足从 Vi 到 Vj 以及从 Vj 到 Vi 都连通,也就是都含有至少一条通路,则称此有向图为强连通图。如下图 所示就是一个强连通图。

    强连通图

    • 与此同时,若有向图本身不是强连通图,但其包含的最大连通子图具有强连通图的性质,则称该子图为强连通分量。

    强连通分量

  • 权和网

    在某些实际场景中,图中的每条边(或弧)会赋予一个实数来表示一定的含义,这种与边(或弧)相匹配的实数被称为"权",而带权的图通常称为网。如下图所示,就是一个网结构:

    带权的图存储结构

2. 图的存储结构

掌握两种存储方法的优缺点,同一种功能在不同存储结构上的实现算法。

邻接矩阵存储方法

#define MAXV <最大顶点个数>
typedef struct
{
    int no;
    Info Type info;  // 顶点其他信息
} VertexType;


typedef struct  // 图的定义
{
    int edges[MAXV][MAXV];  // 邻接矩阵
    int n , e;;  // 顶点数,边数
    VertexType vexs[MAXV]; // 存放顶点信息
} MGraph;

邻接表存储方法

typedef struct ANode
{
    int adjvex;  // 该边的终点编号
    struct ANode *nextarc;  // 指向下一条边的指针
    InfoType info;  // 该边的权值等信息
} ArcNode;

// 头节点类型
typedef struct Vnode
{
    Vertex data;  // 顶点信息
    ArcNode *firstarc;  // 指向第一条边
} VNode;

typedef struct {
    VNode adjlist[MAXV];  // 邻接表
    int n, e;  // 图中定点数,边数
}ALGraph;

// G->adjlist[i].firstarc;  边的信息

3. 图遍历

深度优先搜索遍历 DFS

离初始点越远越优先访问。

  1. 从某个初始顶点 v 出发,首访问初始顶点v
  2. 选择一个与顶点v相邻且没有被访问过的顶点w,再从w出发进行深度优先搜索。

ps. 如何确定一个顶点是否被访问过,设置一个 visited[] 全局数组

visited[i] = 0 表示顶点i没有访问,visited[i] = 1表示顶点i已经访问过

void DFS(ALGraph *G, int v)
{
    ArcNode *p;
    int w;
    visited[v] = 1;
    printf("%d", v);  // 输出被访问顶点的编号
    p = G->adjlist[v].firstarc;  // p指向顶点v的第一条边的边头节点
    while(p != NULL)
    {
        w = p->adjvex;
        if(visited[w] == 0)
            DFS(G, w);  // 若w未被访问,递归访问它
        p = p->nextarc;  // p指向顶点v的下一条边的变头节点
    }
}

广度优先搜索遍历 BFS

离初始点越近越优先访问。

typedef struct  // 图的定义
{
    int edges[MAXV][MAXV];  // 邻接矩阵
    int n , e;;  // 顶点数,边数
    VertexType vexs[MAXV]; // 存放顶点信息
} MGraph;

void BFS(ALGraph *G, int v)
{
        ArchNode *p;
    int w, i;
    int queue[MAXV], front = 0; rear = 0;
    int visited[MAXV];
    for(i = 0; i < G->n; i++){
        visited[i] = 0;
    }
    printf("%2d", v);
    visited[v] = 1; 
    rear = (rear +1) % MAXV;
    queue[rear] = v;  // 进队
    // 队列不空循环
    while(front != rear)
    {
        front = (front + 1) % MAXV;
        w = queue[front];  // 出队并赋w
        p = G->adjlist[w].firstarc;  // 找w的第一个的邻接点
        while(p != NULL)
        {
            if(visited[p->adjvex] == 0)
            {
                printf("%2d", p->adjvex);  // 访问之
                visited[p->adjvex] = 1;
                rear = (rear +1) % MAXV;  // 相邻顶点进队
                queue[rear] = p->adjvex;
            }
            p = p->nextarc;  // 找出下一个邻接顶点
        }
    }
}

4. 例题

G-1

试以邻接表为存储结构,分别写出基于DFS和BPS遍历的算法来判别顶点i和顶点j(i≠j)之间是否有路径。

先置全局变量visited[]为0,然后从顶点i开始进行某种遍历,遍历之后,若visited[j]=0,说明顶点i与顶点j之间没有路径;否则说明它们之间存在路径。

基于DFS遍历的算法

int visited[MaxVertexNum];
int DFSTrave(ALGraph *G,int i,int j)
{      int k;
        for (k=0;k<G->n;k++)   visited[k]=0;
        DFS(G,i);  //从顶点i开始进行深度优先遍历
        if (visited[j]==0)  return 0;
        else   return 1;
}

基于BFS遍历的算法

int visited[MaxVertexNum];
int DFSTrave(ALGraph *G,int i,int j)
{      int k;
        for (k=0;k<G->n;k++)   visited[k]=0;
        BFS(G,i);  //从顶点i开始进行广度优先遍历
        if (visited[j]==0)   return 0;
        else   return 1;
} 

5. 最小生成树

普里姆算法

普里姆算法在找最小生成树时,将顶点分为两类,一类是在查找的过程中已经包含在树中的(假设为 A 类),剩下的是另一类(假设为 B 类)。

对于给定的连通网,起始状态全部顶点都归为 B 类。在找最小生成树时,选定任意一个顶点作为起始点,并将之从 B 类移至 A 类;然后找出 B 类中到 A 类中的顶点之间权值最小的顶点,将之从 B 类移至 A 类,如此重复,直到 B 类中没有顶点为止。所走过的顶点和边就是该连通图的最小生成树。

例如,通过普里姆算法查找下图中的最小生成树的步骤为:

img

假如从顶点A出发,顶点 B、C、D 到顶点 A 的权值分别为 2、4、2,所以,对于顶点 A 来说,顶点 B 和顶点 D 到 A 的权值最小,假设先找到的顶点 B:

img

继续分析顶点 C 和 D,顶点 C 到 B 的权值为 3,到 A 的权值为 4;顶点 D 到 A 的权值为 2,到 B 的权值为无穷大(如果之间没有直接通路,设定权值为无穷大)。所以顶点 D 到 A 的权值最小:

img

最后,只剩下顶点 C,到 A 的权值为 4,到 B 的权值和到 D 的权值一样大,为 3。所以该连通图有两个最小生成树:

img

#define MAXV <最大顶点个数>
typedef struct
{
    int no;
    Info Type info;  // 顶点其他信息
} VertexType;


typedef struct  // 图的定义
{
    int edges[MAXV][MAXV];  // 邻接矩阵
    int n , e;;  // 顶点数,边数
    VertexType vexs[MAXV]; // 存放顶点信息
} MGraph;

#define INF 32767
void Prim(MGraph, g, int v)
{
    int lowcost[MAXV];
    int min;
    int closet[MAXV], i, j, k;
    for(i = 0; i < g.n ; i++){
        lowcost[i] = g.edges[v][i];
        closet[i] = v;
    }
    // 输出 n - 1条边
    for(i = 1; i < g.n; i++)
    {
        min = INF;
        for(j = 0; j< g.n; j++){  // 在 V-U 中找出离U最近的顶点k
            if(lowcost[j] != 0 && lowcost[j] < min)
            {
                min = lowcost[j];
                k = j;  // k 记录最近顶点编号
            }
            printf("边(%d, %d)权为: %d\n", closest[k], k, min);
            lowcost[k] = 0;
        }
        for(j = 0; j < g.n; j++)
        {
            if(lowcost[j] != 0 && g.edges[k][j] < lowcost[j])
            {
                lowcost[j] = g.edges[k][j];
                closet[j] = k;
            }
        }
    }
}

局部最优 + 调整 = 全局最优

贪心算法思想 最优结果


Prim()算法中有两重 for循环,所以时间复杂度为O(n^2)

克鲁斯卡尔算法

具体思路: 所有边按照权值的大小进行升序排序,然后从小到大一一判断,条件为:如果这个边不会与之前选择的所有边组成回路,就可以作为最小生成树的一部分;反之,舍去。直到具有 n 个顶点的连通网筛选出来 n-1 条边为止。筛选出来的边和所有的顶点构成此连通网的最小生成树。

判断是否会产生回路的方法

在初始状态下给每个顶点赋予不同的标记,对于遍历过程的每条边,其都有两个顶点,判断这两个顶点的标记是否一致,如果一致,说明它们本身就处在一棵树中,如果继续连接就会产生回路;如果不一致,说明它们之间还没有任何关系,可以连接。

假设遍历到一条由顶点 A 和 B 构成的边,而顶点 A 和顶点 B 标记不同,此时不仅需要将顶点 A 的标记更新为顶点 B 的标记,还需要更改所有和顶点 A 标记相同的顶点的标记,全部改为顶点 B 的标记。

例如,使用克鲁斯卡尔算法找下图的最小生成树的过程为:

img

首先,在初始状态下,对各顶点赋予不同的标记(用颜色区别),如下图所示:

img

对所有边按照权值的大小进行排序,按照从小到大的顺序进行判断,首先是(1,3),由于顶点 1 和顶点 3 标记不同,所以可以构成生成树的一部分,遍历所有顶点,将与顶点 3 标记相同的全部更改为顶点 1 的标记,如下图所示:

img

其次是(4,6)边,两顶点标记不同,所以可以构成生成树的一部分,更新所有顶点的标记为:

img

其次是(2,5)边,两顶点标记不同,可以构成生成树的一部分,更新所有顶点的标记为:

img

然后最小的是(3,6)边,两者标记不同,可以连接,遍历所有顶点,将与顶点 6 标记相同的所有顶点的标记更改为顶点 1 的标记:

img

继续选择权值最小的边,此时会发现,权值为 5 的边有 3 个,其中(1,4)和(3,4)各自两顶点的标记一样,如果连接会产生回路,所以舍去,而(2,3)标记不一样,可以选择,将所有与顶点 2 标记相同的顶点的标记全部改为同顶点 3 相同的标记:

img

当选取的边的数量相比与顶点的数量小 1 时,说明最小生成树已经生成。所以最终采用克鲁斯卡尔算法得到的最小生成树为上图所示。

6. 最短路径

狄克斯特拉算法

迪杰斯特拉算法计算的是从网中一个顶点到其它顶点之间的最短路径问题。

img

如上图所示是一个有向网,在计算 V0 到其它所有顶点之间的最小路径时,迪杰斯特拉算法的计算方式为:

从 V0 出发,由于可以直接到达 V2 和 V5 ,而其它顶点和 V0 之间没有弧的存在,所以之间的距离设定为无穷大,可以得到下面这个表格:

img

从表格中可以看到,V0 到 V2 的距离最近,所以迪杰斯特拉算法设定 V0-V2 为 V0 到 V2 之间的最短路径,最短路径的权值和为 10。
已经判断 V0-V2 是最短路径,所以以 V2 为起始点,判断 V2 到除了 V0 以外的其余各点之间的距离,如果对应的权值比前一张表格中记录的数值小,就说明网中有一条更短的路径,直接更新表格;反之表格中的数据不变。可以得到下面这个表格:例如,表格中 V0 到 V3 的距离,发现当通过 V2 到达 V3 的距离比之前的 ∞ 要小,所以更新表格。

img

更新后确定从 V0 到 V3 的最短路径为 V0-V4-V3,权值为 50。然后从 V3 出发,继续判断:

img

对于 V5 来说,通过 V0-V4-V3-V5 的路径要比之前的权值 90 还要小,所以更新表格,更新后可以看到,V0-V5 的距离此时最短,可以确定 V0 到 V5 的最短路径为 60。
最后确定 V0-V1 的最短路径,由于从 V0 无法到达 V1 ,最终设定 V0 到 V1 的最短路径为。

void Dijkstra(MGraph g, int v)
{
    int dist[MAXV], path[MAXV];
    int s[MAXV];

    // 最小距离
    int mindis, i, j, u;

    for(i = 0; i< g.n; i++)
    {
        dist[i] = g.edges[v][i];  // 距离初始化
        s[i] = 0;  // s[] 置空
        if(g.edges[v][i] < INF)  // 路径初始化
            path[i] = v;  // 顶点 v 到 i 有边时
        else
            path[i] = -1;  // 顶点 v 到 i 没边时
    }
    // 循环 n - 1次
    for(i = 0; i < g.n; i++)
    {
        mindis = INF;

        for(j = 0; j < g.n; j++)
        {
            if(s[j] == 0 && dist[j] < mindis)
            {
                u = j;
                mindis = dist[j];
            }
        }
        s[u] = 1;  // 顶点u加入S中
        for(j = 0; j < g.n; j++)  // 
        {
            if(s[j] == 0)
            {
                if(e.edges[u][j] < INF && dist[u]+ g.edges[u][j] < dist[j])
                {
                    dist[j] = dist[u] + g.edges[u][j];
                    path[j] = u;
                }
            }
        }
        Dispath(dist, path, s, g.n, v);  // 输出最短路径
    }
}

算法的时间复杂度为 O(elog2e)


弗洛伊德算法

核心思想

对于网中的任意两个顶点(例如顶点 A 到顶点 B)来说,之间的最短路径不外乎有 2 种情况:

  1. 直接从顶点 A 到顶点 B 的弧的权值为顶点 A 到顶点 B 的最短路径;
  2. 从顶点 A 开始,经过若干个顶点,最终达到顶点 B,期间经过的弧的权值和为顶点 A 到顶点 B 的最短路径。

    所以,弗洛伊德算法的核心为:对于从顶点 A 到顶点 B 的最短路径,拿出网中所有的顶点进行如下判断:

Dis(A,K)+ Dis(K,B)< Dis(A,B)
// 其中,K 表示网中所有的顶点;Dis(A,B) 表示顶点 A 到顶点 B 的距离。

实例

img
图 1 带权图

例如,在使用弗洛伊德算法计算图 1 中的任意两个顶点之间的最短路径时,具体实施步骤为:

img

依次遍历所有的顶点,假设从 V0 开始,将 V0 作为中间点,看每对顶点之间的距离值是否会更小。最终 V0 对于每对顶点之间的距离没有任何改善。

例如,(V0,V3)权值为无穷大,而(V0,V2)+(V2,V3)= 60,比之前的值小,相比而言后者的路径更短;同理 (V1,V3)也是如此。

更新的表格为:

img

以 V3 作为中间顶点遍历各队顶点,更新后的表格为:

img

以 V4 作为中间顶点遍历各队顶点,更新后的表格为:

img

而对于顶点 V5 来说,和顶点 V0 和 V1 相类似,所不同的是,V5 只有入度,没有出度,所以对各队顶点的距离不会产生影响。最终采用弗洛伊德算法求得的各个顶点之间的最短路径如上图所示。

7. 拓扑排序和关键路径

拓扑排序算法

待写

求关键路径的过程

待写

No.13 其他

1. 查找

线性表的查找

在顺序表上进行。方法有:
■ 顺序查找 (过程和算法)

从表中的最后一个数据元素开始,逐个同记录的关键字做比较,如果匹配成功,则查找成功;反之,如果直到表中第一个关键字查找完也没有成功匹配,则查找失败。

//查找表查找的功能函数,其中key为关键字
int Search_seq(SSTable *st,keyType key){
    st->elem[0].key=key;//将关键字作为一个数据元素存放到查找表的第一个位置,起监视哨的作用
    int i=st->length;
    //从查找表的最后一个数据元素依次遍历,一直遍历到数组下标为0
    while (st->elem[i].key!=key) {
        i--;
    }
    //如果 i=0,说明查找失败;反之,返回的是含有关键字key的数据元素在查找表中的位置
    return i;
}
  • 二分查找 (过程和算法)

在做查找的过程中,如果 low 指针和 high 指针的中间位置在计算时位于两个关键字中间,即求得 mid 的位置不是整数,需要统一做取整操作

void BinInsertSort(RecType R[], int n){
    int i, j, low, high, mid;
    RecType tmp;
    for(i = 1; i < n; i++){
        if(R[i].key < R[i-1].key){  // 反序时
            temp = R[i];  // 将 R[i]保存在 tmp中
            low = 0;
            high = i - 1; 
            // 在R[low..high]中查找插入的位置
            while(low <= high)
            {
                mid = (low + high) / 2;  // 取中间位置
                if(temp.key < R[mid].key)  // 插入点在左半区
                    high = mid - 1;
                else
                    low = mid + 1; // 插入点在右半区
            }  // 找位置high
            for(j = i - 1; j >= high + 1; j--){  
                R[j + 1] = R[j];
            }
            R[high + 1] = temp;  // 插入 tmp
        }
    }
}
  • 分块查找 (过程)

    img

  1. 分块有序指的是第二个子表中所有关键字都要大于第一个子表中的最大关键字,第三个子表的所有关键字都要大于第二个子表中的最大关键字,依次类推。

过程

假设要查找关键字 38 的具体位置。首先将 38 依次和索引表中各最大关键字进行比较,因为 22 < 38 < 48,所以可以确定 38 如果存在,肯定在第二个子表中。

由于索引表中显示第二子表的起始位置在查找表的第 7 的位置上,所以从该位置开始进行顺序查找,一直查找到该子表最后一个关键字(一般将查找表进行等分,具体子表个数根据实际情况而定)。结果在第 10 的位置上确定该关键字即为所找。

树表的查找

二叉排序树

  • 定义

二叉排序树要么是空二叉树

要么具有如下特点:

  • 二叉排序树中,如果其根结点有左子树,那么左子树上所有结点的值都小于根结点的值;
  • 二叉排序树中,如果其根结点有右子树,那么右子树上所有结点的值都大小根结点的值;
  • 二叉排序树的左右子树也要求都是二叉排序树;

  • 查找(过程和算法)

二叉排序树中查找某关键字时,查找过程类似于次优二叉树,在二叉排序树不为空树的前提下,首先将被查找值同树的根结点进行比较,会有 3 种不同的结果:

  • 如果相等,查找成功;
  • 如果比较结果为根结点的关键字值较大,则说明该关键字可能存在其左子树中;
  • 如果比较结果为根结点的关键字值较小,则说明该关键字可能存在其右子树中;
BiTree SearchBST(BiTree T,KeyType key){
    //如果递归过程中 T 为空,则查找结果,返回NULL;或者查找成功,返回指向该关键字的指针
    if (!T || key==T->data) {
        return T;
    }else if(key<T->data){
        //递归遍历其左孩子
        return SearchBST(T->lchild, key);
    }else{
        //递归遍历其右孩子
        return SearchBST(T->rchild, key);
    }
}

性质:二叉排序树的中序序列是一个有序序列

  • 插入、删除(过程)

    img

  • 在上图 的二叉排序树中做查找关键字 1 的操作,当查找到关键字 3 所在的叶子结点时,判断出表中没有该关键字,此时关键字 1 的插入位置为关键字 3 的左孩子。

  • 假设原二叉排序树为空树,在对动态查找表 {3,5,7,2,1} 做查找以及插入操作时,可以构建出一个含有表中所有关键字的二叉排序树

    img

删除

假设要删除的为结点 p,则对于二叉排序树来说,需要根据结点 p 所在不同的位置作不同的操作,有以下 3 种可能:
1、结点 p 为叶子结点,此时只需要删除该结点,并修改其双亲结点的指针即可;2、结点 p 只有左子树或者只有右子树,此时只需要将其左子树或者右子树直接变为结点 p 双亲结点的左子树即可;3、结点 p 左右子树都有,此时有两种处理方式:

img
图 3 二叉排序树中删除结点(1)

2)用结点 p 的直接前驱(或直接后继)来代替结点 p,同时在二叉排序树中对其直接前驱(或直接后继)做删除操作。如图 4 为使用直接前驱代替结点 p:

img
图 4 二叉排序树中删除结点(2)

图 4 中,在对左图进行中序遍历时,得到的结点 p 的直接前驱结点为结点 s,所以直接用结点 s 覆盖结点 p,由于结点 s 还有左孩子,根据第 2 条规则,直接将其变为双亲结点的右孩子。

平衡二叉树

定义
  • 每棵子树中的左子树和右子树的深度差不能超过 1;
  • 二叉树中每棵子树都要求是平衡二叉树;

其实就是在二叉树的基础上,若树中每棵子树都满足其左子树和右子树的深度差都不超过 1,则这棵二叉树就是平衡二叉树。

img

查找(过程与算法)
调整(过程)

哈希表查找

哈希函数

主要有除留余数法

=> 若已知整个哈希表的最大长度 m,可以取一个不大于 m 的数 p,然后对该关键字 key 做取余运算,即:H(key)= key % p

哈希冲突解决方法

主要有线性探查法、拉链法

2. 内排序

插入排序

直接插入排序

将数据按照一定的顺序一个一个的插入到有序的表中,最终得到的序列就是已经排序好的数据。

void InsertSort(int a[], int n)
{
    for(int i= 1; i<n; i++){
        if(a[i] < a[i-1]){//若第 i 个元素大于 i-1 元素则直接插入;反之,需要找到适当的插入位置后在插入。
            int j= i-1;
            int x = a[i];
            while(j>-1 && x < a[j]){  //采用顺序查找方式找到插入的位置,在查找的同时,将数组中的元素进行后移操作,给插入元素腾出空间
                a[j+1] = a[j];
                j--;
            }
            a[j+1] = x;      //插入到正确位置
        }
        print(a,n,i);//打印每次排序后的结果
    }
希尔排序

先将整个记录表分割成若干部分,分别进行直接插入排序,然后再对整个记录表进行一次直接插入排序。

交换排序

冒泡排序

将无序表中的所有记录,通过两两比较关键字,得出升序序列或者降序序列。

快速排序

通过一次排序将整个无序表分成相互独立的两部分,其中一部分中的数据都比另一部分中包含的数据的值小,然后继续沿用此方法分别对两部分进行同样的操作,直到每一个小部分不可再分,所得到的整个序列就成为了有序序列。

int c = 0;
// 快排
int Partition(SqList *s, int low, int high) {
    c++;
    printf("第 %d 次排序前: ", c);
    display(*s);
    int privotkey = s->head[low];
    // 直到两指针相遇
    while (low < high) {
        // high指针左移,直到遇到比 privotkey值小的记录
        while (low < high && s->head[high] >= privotkey) {
            high--;
        }
        if (low < high)
        {
            s->head[low] = s->head[high];
        }
        // low 指针右移,直到遇到比 privotkey 值大的
        while (low < high && s->head[low] <= privotkey)
        {
            low++;
        }
        if (low < high)
        {
            s->head[high] = s->head[low];
        }
    }
    s->head[low] = privotkey;
    printf("第 %d 次排序后: ", c);
    display(*s);
    return low;
}

void QSort(SqList *s, int low, int high)
{
    if (low < high)
    {
        // 找到支点的位置
        int privotloc = Partition(s, low, high);
        // 对支点左侧的子表进行排序
        QSort(s, low, privotloc - 1);
        // 对支点右侧的子表进行排序
        QSort(s, privotloc + 1, high);
    }
}



void QuickSort(SqList *s) {
    QSort(s, 0, s->length - 1);
}

选择排序

直接选择排序

于具有 n 个记录的无序表遍历 n-1 次,第 i 次从无序表中第 i 个记录开始,找出后序关键字中最小的记录,然后放置在第 i 的位置上。

堆排序

堆的含义:

在含有 n 个元素的序列中,如果序列中的元素满足下面其中一种关系时,此序列可以称之为堆

  • ki ≤ k2i 且 ki ≤ k2i+1(在 n 个记录的范围内,第 i 个关键字的值小于第 2i 个关键字,同时也小于第 2i+1 个关键字)
  • ki ≥ k2i 且 ki ≥ k2i+1(在 n 个记录的范围内,第 i 个关键字的值大于第 2i 个关键字,同时也大于第 2i+1 个关键字)

通过将无序表转化为堆,可以直接找到表中最大值或者最小值,然后将其提取出来,令剩余的记录再重建一个堆,取出次大值或者次小值,如此反复执行就可以得到一个有序序列

归并排序

先将所有的记录完全分开,然后两两合并,在合并的过程中将其排好序,最终能够得到一个完整的有序表。

基数排序

xxxxxxxxxxx

3. 例题

在待排序的元素序列基本有序的前提下,效率最高的排序方法是 。
  A. 插入排序 B. 选择排序
  C. 快速排序 D. 归并排序

插入排序是将待排序的记录插入到前面已排好序的子区间中,即考虑已排好序的子区间。本题答案为A。


快速排序在最坏情况下时间复杂度是O(n2),比 的性能差。
  A. 堆排序 B. 冒泡排序
  C. 直接选择排序 D. 直接插入排序

冒泡最坏也是 O(n2),直接选择,也是O(n2),直接插入也差不多,排除法得A,那为什么选A呢。堆排序最坏的情况其为 O(nlog2n)

A。

4. 强调各种排序方法的比较

  • 是否需要比较
  • 排序方法的区别
  • 时间复杂度
  • 空间复杂度

粉色的花瓣,美丽地缠绕在身上。依在风里。