cfla's blog

数据结构课程

发表于 更新于 分类于 阅读次数： Valine：

数据结构

1. 线性表

1.1 顺序实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <cstdlib>
using namespace std;
typedef int ElemType;
typedef int Status;

const int OK = 0;
const int ERROR = 1;
const int OVERFLOW = 2;

const int LIST_INIT_SIZE = 100;
const int LIST_INCREMENT = 10;

typedef struct 
{
    ElemType * elem;
    int length;
    int listsize;
}SqList;

// 初始化
Status InitList_Sq(SqList &L)
{
    L.elem = (ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType));
    if (!L.elem)
        exit(OVERFLOW);
    L.length = 0;
    L.listsize = LIST_INIT_SIZE;
}

// 插入
Status insert(SqList &L, int i, ElemType e)
{
    // 插入的合法范围为 1 <= i <= length + 1, 插入在length + 1时，需要另外申请空间，等价于append
    if (i < 1 || i > L.length + 1)
        return ERROR;

    // 若已满，重新分配空间
    if (L.length >= L.listsize) {
        ElemType * newbase = (ElemType *)realloc(L.elem, (L.listsize + LIST_INCREMENT) * sizeof (ElemType));
        if (!newbase)
            exit(OVERFLOW);
        L.elem = newbase;
        L.listsize += LIST_INCREMENT;
    }

    // 位移
    ElemType * pos = &(L.elem[i - 1]);
    for (ElemType * rear = &(L.elem[L.length - 1]); rear >= pos; rear--)
        *(rear + 1) = * rear;
    * pos = e;
    L.length++;
    return OK;
}

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

1.2 链式实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#include <cstdio>
#include <cstdlib>
using namespace std;

enum {OK, ERROR, OVERFLOW};

typedef int ElemType;
typedef int Status;

typedef struct LNode
{
    ElemType data;
    struct LNode * next;
}LNode, * LinkList;

Status GetElem_L(LinkList L, int i, ElemType &e)
{
    auto p = L->next;
    int j = 1;
    while (p && j < i) {
        p = p->next;
        j++;
    }
    if (!p || j > i)
        return ERROR;

    e = p->data;
    return OK;
}

Status ListInsert_L(LinkList &L, int i, ElemType e)
{
    auto p = L;
    int j = 0;      // 由于头节点的存在，计数器从0开始

    // 寻找第i - 1个结点，也就是待插入节点的前驱节点
    while (p && j < i - 1) {
        p = p->next;
        j++;
    }
    if (!p || j > i - 1)    // i超出表长+1(append), 或i为负数
        return ERROR;

    auto s = (LinkList)malloc(sizeof (LNode));
    s->data = e;
    s->next = p->next;
    p->next = s;
    return OK;
}

Status ListDelete_L(LinkList &L, int i, ElemType &e)
{
    auto p = L;     // 指向头节点
    int j = 0;      // 计数器

    // 找到待删除结点的前驱
    while (p->next && j < i - 1) {  // 这里的第一个测试条件是p->next是因为下面要引用p->next,如果测试条件是p的话，下面会报段错误
        p = p->next;
        j++;
    }

    // 待删除结点的位置超出表厂或者为负数
    if (!p->next || j > i - 1)
        return ERROR;
    
    auto q = p->next;
    p->next = q->next;
    e = q->data;
    free(q);
    return OK;
}

/**
 * @brief 头插法创建单链表
 * 
 * @param L 
 * @param n 
 * 
 * 输入 1 2 3 4 5
 * 建好的单链表为 5 -> 4 -> 3 -> 2 -> 1
 */
void CreateList_L(LinkList &L, int n)
{
    L = (LinkList)malloc(sizeof (LNode));   // 为头节点分配空间
    L->next = NULL;
    for (int i = 0; i < n; i++) {
        auto p = (LinkList)malloc(sizeof (LNode));  // 分配新节点
        scanf("%d", &p->data);
        p->next = L->next;          // 插入
        L->next = p;
    }
}

/**
 * @brief 尾插法创建单链表
 * 
 * @param L 
 * @param n 
 * 
 * 输入 1 2 3 4 5
 * 建好的单链表为 1 -> 2 -> 3 -> 4 -> 5
 */
void CreateList_L_tail(LinkList &L, int n)
{
    L = (LinkList)malloc(sizeof (LNode));
    auto r = L;
    for (int i = 0; i < n; i++) {
        auto p = (LinkList)malloc(sizeof (LNode));
        scanf("%d", &p->data);
        p->next = NULL;
        r->next = p;
        r = p;
    }
}

1.3 循环链表

  • 表中最后一个结点的指针域指向第一个节点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
typedef struct node
{
    int seqNumber;      // 存储每个人的编号
    int psd;            // 存储每个人的密码
    struct node * next;
}Node, * NodePtr;

typedef struct
{
    NodePtr rear;       // 存储循环链表的尾指针
    int length;
}CirLinkedList;

void InitList(CirLinkedList * L)
{
    L->rear = NULL;
    L->length = 0;
}

inline int empty(const CirLinkedList * L)
{
    return !(L->length);
}

void append(CirLinkedList * L, int sq, int psd)
{
    NodePtr p = (NodePtr)malloc(sizeof(Node));
    p->seqNumber = sq;
    p->psd = psd;
    
    if (empty(L)) {    // 不想单链表一样有头节点，因此插入第一个元素时需要特殊处理
        L->rear = p;
        p->next = p;
    }
    else {
        p->next = L->rear->next;
        L->rear->next = p;
        L->rear = p;
    }
    L->length++;
}

void CreateList(CirLinkedList * L)
{
    int cnt, psd;

    printf("请输入表长:");
    scanf("%d", &cnt);
    for (int i = 0; i < cnt; i++) {
        printf("请输入元素%d的密码:", i + 1);
        scanf("%d", &psd);
        append(L, i + 1, psd);
    }
}

void traverse(const CirLinkedList * L)
{
    if (empty(L)) return ;
    NodePtr p = (L->rear)->next;

    for (int i = 0; i < L->length + 1; i++) {
        printf("%4d ", p->seqNumber);
        p = p->next;
    }
    p = L->rear->next;
    printf("\n");
    for (int i = 0; i < L->length + 1; i++) {
        printf("%4d ", p->psd);
        p = p->next;
    }
    printf("\n");
}

void Remove(CirLinkedList * L, NodePtr *p)
{
    NodePtr prev = L->rear, t = *p;
    while (prev->next != (*p))
        prev = prev->next;
    prev->next = (*p)->next;
    *p = prev;
    if (t == L->rear) L->rear = prev;
    free(t);
    L->length--;
    if (L->length == 0)
        *p = NULL;
}
  • 不设头节点，存储尾指针，尾指针指向循环链表的最后一个结点，尾指针的next指向头节点

1.4 双向链表

1
2
3
4
5
typedef struct DuLNode
{
    ElemType data;
    struct DuLNode * prior, * next;
}DuLNode, * DuLinkList

2. 栈和队列

2.1 顺序栈

  • 空栈：S.base == S.Top
  • 栈长：S.Top - S.base
  • 栈满：S.top – S.base >= S.stacksize 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
// 顺序栈的课本典型实现
#include <cstdio>
#include <cstdlib>
using namespace std;

enum {OK, ERROR, OVERFLOW};

typedef int SElemType;
typedef int Status;

const int STACK_INIT_SIZE = 100;
const int STACK_INCREMENT = 10;

typedef struct
{
    SElemType * base;
    SElemType * top;
    int stacksize;
}SqStack;

Status InitStack(SqStack &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;
}

Status GetTop(SqStack S, SElemType &e)
{
    if (S.base == S.top)
        return ERROR;
    e = *(S.top - 1);
    return OK;
}

bool StackEmpty(SqStack S)
{
    if (S.top == S.base)
        return true;
    else
        return false;
}

Status Push(SqStack &S, SElemType e)
{
    // 处理栈满的情况 栈的有效范围是 0 ~ stacksize - 1
    if (S.top == S.base + S.stacksize) {    // S.base + S.stacksize 刚好是尾后指针
        S.base = (SElemType *)realloc(S.base, (S.stacksize + STACK_INCREMENT) * sizeof(SElemType));
        if (!S.base)
            exit(OVERFLOW);
        S.top = S.base + S.stacksize;
        S.stacksize += STACK_INCREMENT;
    }

    *(S.top++) = e;
    return OK;
}

Status Pop(SqStack &S, SElemType &e)
{
    if (S.top == S.base)
        return ERROR;
    e = *(--S.top);
    return OK;
}

int length(const SqStack S)
{
    return S.base - S.top;
}

2.2 链栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
typedef struct  SNode{
    ElemType data;
    struct SNode *next;
}SNode, *LinkStack;

Status Push(LinkStack &S, SElemType e)
{
    //插入元素e为新的栈顶元素
    p = (LinkStack)malloc(sizeof(SNode));
  if (!p)
        exit(OVERFLOW);
    p->data = e;
    p->next = S->next;
    S->next = p; //头插栈顶元素
  return OK;
}

status Pop(LinkStack &S, SElemType &e)
{
  //若栈不空，则删除栈顶元素，用e返回其值，并返回OK；
  //否则返回ERROR	
  if(S->next == NULL) 
        return ERROR;  //栈空
  p = S->next;
  e = p->data;
  S->next = p->next; 
  free(p); //删除栈顶元素
  return OK;
}

2.3 栈的应用

  • 数制转换
  • 括号匹配
  • 迷宫问题
  • 表达式求值

2.4 循环队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <cstdio>
#include <cstdlib>
using namespace std;

enum {OK, ERROR, OVERFLOW};

typedef int QElemType;
typedef int Status;

const int MaxQSize = 100;

typedef struct
{
    QElemType * base;
    int front;  // 队头元素的下标
    int rear;  // 队尾元素的下标
}SqQueue;
  • 判断队空：Q.front == Q.rear
  • 判断队满：(Q.rear + 1) % MaxQSize == Q.front 也可以用 变量记录当前队列长度
  • 求队长：(Q.rear - Q.front + MaxQSize) % MaxQSzie 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
Status InitQueue_Sq(SqQueue &Q)
{
    Q.base = (QElemType *)malloc(MaxQSize * sizeof (QElemType));
    if (!Q.base)
        exit (OVERFLOW);
    Q.front = Q.rear = 0;
    return OK;
}

Status EnQueue_Sq(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;
}

Status DeQueue_Sq(SqQueue &Q, QElemType &e)
{
    if (Q.rear == Q.front)
        return ERROR;
    e = Q.base[Q.front];
    Q.front = (Q.front + 1) % MaxQSize;
    return OK;
}

int length(const SqQueue Q)
{
    return (Q.rear - Q.front + MaxQSize) % MaxQSize;
}

2.5 链队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <cstdio>
#include <cstdlib>
using namespace std;

enum {OK, ERROR, OVERFLOW};

typedef int QElemType;
typedef int Status;

typedef struct QNode
{
    QElemType data;
    struct QNode * next;
}QNode, * QueuePtr;

typedef struct 
{
    QueuePtr front;
    QueuePtr rear;
}LinkQueue;

Status InitQueue(LinkQueue &Q)
{
    Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode));
    if (!Q.front)
        exit(OVERFLOW);
    Q.front->next = NULL;
    return OK;
}

Status EnQueue(LinkQueue &Q, QElemType e)
{
    auto p = (QueuePtr)malloc(sizeof(QNode));
    if (!p)
        exit (OVERFLOW);
    p->data = e;
    p->next = NULL;

    // 尾插入到rear
    Q.rear->next = p;
    Q.rear = p;
    return OK;
}

Status DeQueue(LinkQueue &Q, QElemType &e)
{
    if (Q.front == Q.rear)
        return ERROR;
    auto p = Q.front->next;
    e = p->data;
    Q.front->next = p->next;

    // 需要特判只有一个元素的时候，此时被释放的结点为rear,必须改变rear的指向，是指与front相同
    if (Q.rear == p)
        Q.rear = Q.front;
    free(p);
    return OK;
}

Status DestroyQueue(LinkQueue &Q)
{
    while (Q.front) {
        Q.rear = Q.front->next;
        free(Q.front);
        Q.front = Q.rear;
    }

    return OK;
}

3. 树

树的度：结点拥有的子树个数

叶子节点或终端结点：度为0的结点

层次：树的根为第一层，根的孩子为第二层

深度：树中结点的最大层次。

3.1 二叉树的性质

  1. 二叉树的第i层至多有2^i-1^ 个结点

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

  3. 对任何一棵二叉树，若它含有n~0~ 个叶子结点、n~2~ 个度（出度）为 2 的结点，则必存在关系式：n~0~ = n2+1。

    推论：适用于Huffman树

    对于有n~0~ 个结点的Huffman树，它的总结点数为n~0~ + n~2~ = 2n~0~ -1

  4. 具有n个结点的完全二叉树的深度为 floor(log2 n) + 1

    ceil()向上取整，floor向下取整

  5. 若对含 n 个结点的完全二叉树从上到下且从左至右进行 1 至 n 的编号，则对完全二叉树中任意一个编号为 i 的结点：

    1. 若 i = 1，则该结点是二叉树的根，无双亲，

      否则，编号为floor(i/2) 的结点为其双亲结点；

    2. 若 2i > n，则该结点无左孩子，

      否则，编号为 2i 的结点为其左孩子结点；

    3. 若 2i+1 > n，则该结点无右孩子结点，
      否则，编号为2i+1 的结点为其右孩子结点。

    4. 具有n个结点的完全二叉树有ceil(n/2)个叶子结点
    5. 完全二叉树最后一个非终端结点的编号为floor(n/2)

3.2 二叉树的链式存储

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
typedef char ElemType;
typedef struct Node
{
    ElemType val;
    struct Node *left = nullptr;
    struct Node *right = nullptr;
} *Tree, Node;
const int MaxNodeCnt = 100;

// 按先序遍历顺序创建二叉树
void CreateTree(Tree &T)
{
    char ch = getchar();
    if (ch == '#')
        T = nullptr;
    else {
        T = new Node;
        T->val = ch;
        CreateTree(T->left);
        CreateTree(T->right);
    }
}

3.3 二叉树的遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
void PreorderTraverse(const Tree T)
{
    if (T) {
        cout << T->val << " ";
        PreorderTraverse(T->left);
        PreorderTraverse(T->right);
    }
}

void InorderTraverse(const Tree T)
{
    if (T) {
        InorderTraverse(T->left);
        cout << T->val << " ";
        InorderTraverse(T->right);
    }
}

void PostorderTraverse(const Tree T)
{
    if (T) {
        PostorderTraverse(T->left);
        PostorderTraverse(T->right);
        cout << T->val << " ";
    }
}

// 层次遍历
void BFS(const Tree T)
{
    using myqueue::queue;
    if (!T) return ;
    queue<Tree> Q;
    Q.push(T);
    while (!Q.empty()) {
        Tree t = Q.front(); Q.pop();
        cout << t->val << " ";
        if (t->left) Q.push(t->left);
        if (t->right) Q.push(t->right);
    }
}

  • 先序遍历非递归思路：

    从二叉树根结点开始，沿左子树一直走到末端(左孩子为空)为止，在走的过程中，访问所遇结点，并依次把所遇结点进栈，当左子树为空时，从栈顶退出某结点，并将指针指向该结点的右孩子。如此重复，直到栈为空或指针为空止。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    void PreorderTraverseNonRec(const Tree T)
    {
        Tree cur = T;
        Tree stack[MaxNodeCnt];
        int top = 0;

        while (cur != nullptr || top != 0) {
            if (cur != nullptr) {  // 当未走到最左边的结点时，继续向左走，同时访问结点
                cout << cur->val << " ";
                stack[top++] = cur;
                cur = cur->left;
            }
            else {    // 访问右子树
                cur = stack[--top];
                cur = cur->right;
            }
        }
    }

  • 中序非递归思路

    从二叉树根结点开始，沿左子树一直走到末端(左孩子为空)为止，在走的过程中，把依次遇到的结点进栈待左子树为空时,从栈中退出结点并访问,然后再转向它的右子树。如此重复，直到栈空或指针为空止。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    void InorderTraverseNonRec(const Tree T)
    {
        Tree cur = T;
        Tree stack[MaxNodeCnt];
        int top = 0;

        while (cur != nullptr || top != 0) {
            if (cur != nullptr) {
                stack[top++] = cur;
                cur = cur->left;
            }
            else {
                cur = stack[--top];
                cout << cur->val << " ";
                cur = cur->right;
            }
        }
    }

  • 后序非递归思路

    利用栈来实现二叉树的后序遍历要比前序和中序遍历复杂得多，在后序遍历中，

    1. 当搜索指针指向某一个结点时，不能马上进行访问，而先要遍历左子树，所以此结点应先进栈保存，

    2. 当遍历完它的左子树后，再次回到该结点，还不能访问它，

    3. 还需先遍历其右子树,所以该结点还必须再次进栈，

    4. 只有等它的右子树遍历完后，再次退栈时，才能访问该结点。

    5. 为了区分同一结点的两次进栈，引入一个栈次数的标志，一个元素第一次进栈标志为0，第二次进标志为1，并将标志存入另一个栈中，当从标志栈中退出的元素为1时，访问结点。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    void PostorderTraverseNonRec(const Tree T)
    {
        Tree stack[MaxNodeCnt];
        int cnt[MaxNodeCnt], top = 0, tc;
        Tree cur = T, tt;

        while (cur != nullptr || top != 0) {
            if (cur) {
                stack[top] = cur;
                cnt[top++] = 0;
                cur = cur->left;
            }
            else {
                tt = stack[top - 1];
                tc = cnt[--top];
                if (tc) {
                    cout << tt->val << " ";
                    cur = nullptr;
                }
                else {
                    stack[top] = tt;
                    cnt[top++] = tc + 1;
                    cur = tt->right;
                }
            }
        } 
    }

3.4 二叉树遍历的应用

  • 求树的叶子节点个数
  • 求树的深度
  • 复制二叉树

3.5 线索化：

可以以线性的方式访问二叉树结构

3.5.1 中序线索树

对于中序线索树，我们约定：

它有两个存储左右子树标记的域，如果左子树的标记为0，那么它存储的是其左孩子，如果左子树的标记为1，那么它存储的是其中序遍历时的直接前驱.

如果右子树的标记为0，它存储的是其右孩子。如果右子树的标记为1，那么它存储的是中序遍历时的直接后继。

  • 求中序线索树的前驱：

    1
    2
    3
    4
    如果 左标记为1:
      直接返回其左孩子
    否则:
      返回其左子树的最右下的结点

  • 求中序线索树的后继：

    1
    2
    3
    4
    如果 右标记为1:
      返回其右孩子
    否则:
      返回其右子树的最左下的孩子

  • 遍历中序线索树

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    // 方法1

    // 正序遍历
    for (BiThrTree p = T->lchild; p != T; p = in_suss(p))
        visit(p);

    // 寻找后继的函数
    BiThrTree in_succ(BiThrTree p)
    {
        if (p->RTag == 1)
            return p->rchild;
        else {
            BiThrTree q;
            for (q = p->rchild; q->LTag == 0; q = q->lchild)
                ;  // 找到右子树的最左下的孩子
            return q;
        }
    }

    // 倒序遍历
    for (BiThrTree p = T->rchild; p != T; p = in_pre(p))
        visit(p);

    // 寻找前驱
    BiThrTree in_pre(BiThrTree p)
    {
        if (p->LTag == 1)
            return p->lchild;
        else {
            BiThrTree q;
            for (q = p->lchild; q->LTag == 0; q = q->rchild)
                ;
            return q;
        }
    }
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    // 方法2
    void InOrderTraverse_Thr(BiThrTree T, void (*Visit)(TElemType e)) 
    {
        p = T->lchild;           // p = first_node
      while (p != T) {     		// 空树或遍历结束时，p==T
            // case 1: 
          while (p->LTag==Link)
                p = p->lchild;    //第一个结点
          if(!Visit(p->data))
                return ERROR;
            
            // case 2:
          while (p->RTag==Thread && p->rchild!=T) {
            p = p->rchild;
              Visit(p->data);      // 访问后继结点
          }
          p = p->rchild;           // p进至其右子树根
        }
    }  // InOrderTraverse_Thr

  • 建立中序线索树

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    //全局变量
    BiTNode *Pre = new BiTNode;

    //中序线索化带头结点二叉树
    void InOrderThreading(BiTree &Thrt, BiTree T)
    {
      Thrt = new BiTNode; //建立头结点
      Thrt->LTag = 0;		//头结点有左孩子，若树非空，则其左孩子为树根
      Thrt->RTag = 1;		//头结点右孩子为右线索
      Thrt->right = Thrt; //初始化时右孩子指向自己
      if (!T)				//如果树为空则左孩子也指向自己
        Thrt->left = Thrt;
      else
      {
        Thrt->left = T;
        Pre = Thrt;
        InThreading(T);
            
            // 完成在线索化中未完成的那部分事情
        Pre->right = Thrt;		// 最后一个结点的后继指向头节点
        Pre->RTag = 1;
        Thrt->right = Pre;		// 头节点的右指针为最后一个结点
      }
    }

    //上一个算法，中序线索化
    void InThreading(BiTree &T)
    {
      if (T) //根节点非空
      {
        InThreading(T->left); //左子树线索化
        if (!T->left)		  // T的左孩子为空
        {
          T->LTag = 1;
          T->left = Pre;
        }
        else
          T->LTag = 0;
        if (!Pre->right) // T的右孩子为空
        {
          Pre->RTag = 1;
          Pre->right = T;
        }
        else
          Pre->RTag = 0;
        Pre = T;
        InThreading(T->right);
      }
    }

1.3 一般的树和森林的表示：

三种表示法：

  1. 父亲表示法（并查集的实现方法）

  2. 孩子表示法

  3. 孩子表示法（将一般的树或森林转换成二叉树）

    让二叉树结点的左孩子指向这个一般的树的第一个孩子，右孩子指向下一个兄弟

1.4 一般的树和森林的遍历：

二叉树：

  • 先序遍历
  • 中序遍历
  • 后序遍历

一般的树

  • 先根遍历（先遍历根，再从左到右依次遍历子树） 先序遍历
  • 后根遍历 （遍历一个树的根时，先左到右依次遍历该树的子树）中序遍历
  • 层次遍历 层次遍历

森林

  • 先序遍历（即从左到右对森林中的每一棵树进行先根遍历） 先序遍历
  • 中序遍历（从左到右对森立中的每一棵树进行后根遍历） 中序遍历

1.5 Huffman树

  • 路径长度l：路径上的分支数目
  • 树的带权路径长度WPL = 求和(k = 1, n) w~k~ l~k~

4. 图

4.1 术语

  • 弧：有向边

  • 网：弧或边带权的图成为有向网或无向网

  • 完全图，有向完全图，稀疏图，稠密图

    设图有n个结点，e条边

    含有e = n(n-1)/2条边的无向图成为完全图

    含有e = n(n-1) 条弧的有向图成为有向完全图

    若边或弧的个数e，e<nlogn 则成为稀疏图，否则成为稠密图

  • 结点的度 = 入度 + 出度

  • 简单路径：顶点不重复的路径

  • 简单回路：除起点终点，顶点不重复的回路

  • 图中任意两个顶点之间都有路径可以联通则成为连通图（有向图 / 无向图）

  • 无向图中，极大连通子图称为连通分量

  • 有向图中，任意两点都有路径可以连通，即为强连通图，否则，各强连通子图成为强连通分量

    有向图的底图连通即为弱连通图

  • 假设一个连通图有 n 个顶点和 e 条边，其中 n-1 条边和 n 个顶点构成一个极小连通子图，称该极小连通子图为此连通图的生成树

4.2 图的遍历

1
2
3
4
5
6
7
void DFS(Graph G, int v) {
  visited[v] = TRUE;
    VisitFunc(v);
    for(auto w : G.Adj)
    if (!visited[w])
          DFS(G, w);
}

4.3 最小生成树

  • Prim算法

    取图中任意一个顶点 v 作为生成树的根，之后往生成树上添加新的顶点 w。在待添加的顶点w 和已经在生成树上的顶点v之间必定存在一条边，并且该边的权值在所有连通顶点v 和 w 之间的边中取值最小。之后继续往生成树上添加顶点，直至生成树上含有 n个顶点为止。

  • Kruskal算法

    具体做法: 先构造一个只含 n 个顶点的子图 SG，然后从权值最小的边开始，若它的添加不使SG 中产生回路，则在 SG 上加上这条边，如此重复，直至加上 n-1 条边为止。

4.4 重连通图和关节点

  • 重连通图：若从一个连通图中删去任何一个顶点及其相关联的边，他仍为一个连通图的话，则该连通图为重（双）连通图。
  • 若连通图中的某个顶点和其相关联的边被删去之后，该连通图被分割成两个或两个以上的连通分量，则称此顶点为关节点。没有关节点的连通图即为重连通图
  • 如何判断关节点？
    • 若生成树的根结点，有两个或两个以上的分支，则此顶点(生成树的根)必为关节点；
    • 对生成树上的任意一个“顶点”，若其某棵子树的根或子树中的其它“顶点”没有和其祖先相通的回边，则该“顶点”必为关节点。

4.5 拓扑排序

  1. 从有向图中选取一个没有前驱的顶点，并输出之；
  2. 从有向图中删去此顶点以及所有以它为尾的弧；

重复上述两步，直至图空，或者图不空但找不到无前驱的顶点为止。

5. 查找

  • 评价指标 ASL

    ASL = 求和(i=1, n) C~i~ × P~i~

    C~i~查找到第i条记录时，K与关键字的比较次数

    P~i~ 查找第i条记录的概率

5.1 顺序查找表

  • 查找成功ASL = n(n+1)/2 * (1 / n) = n+1/2
  • 查找失败的ASL = n+1
  • 平均 = (3/4)(n+1)

5.2 折半查找

  • 折半查找判定树
  • 查找失败并不会多查找一次

课本上的典型实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int Search_Bin(SSTable ST, KeyType K)
{
  int low = 1, high = ST.length;
  int mid;
  while (low <= high) {
    mid = (low + high) / 2;
    if (K < ST[mid].key)
      high = mid - 1; //在左区间继续查找
    else if (K > ST[mid].key)
      low = mid + 1; //在右区间继续查找
    else return mid; //查找成功的出口
  }//while
  return 0; //查找失败的出口
}//Search_Bin

yxc的二分一般实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
bool check(int x) {/* ... */} // 检查x是否满足某种性质

// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用：
int bsearch_1(int l, int r)
{
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;    // check()判断mid是否满足性质
        else l = mid + 1;
    }
    return l;
}
// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用：
int bsearch_2(int l, int r)
{
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}

作者：yxc
链接：https://www.acwing.com/blog/content/277/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

5.3 分块索引

5.4 二叉排序树

  • 二叉排序树的中序遍历序列是一个有序序列
  • 和折半查找判定树类似，查找失败也不会增加比较次数

  • 二叉排序树的删除

    1. 设待删除的结点为p，若p的度为0，直接删除

    2. 若p的度为1，则直接用其孩子替换它

    3. 若p的度为2，方法1：

      将p的右孩子交给其中序前驱，p的左孩子交给其双亲，删除p

    4. 用p的中序前驱（后继）替换它，然后删除其中序前驱。

  • AVL树

    插入：四种旋转

    删除：

    • 要删除的结点为叶子结点，直接删除它，并自下而上调整AVL树。
    • 要删除的结点只有左孩子，用其左孩子替换该节点，并删除其左孩子。因为AVL树的性质，左右子树高度只差不超过1，因此左孩子一定是叶子结点，这种情况便转换为了第一种情况。
    • 要删除的结点只有右孩子，和只有左孩子的情况相同。
    • 要删除的结点既有左孩子，也有右孩子，此时只需寻找其中序遍历的前驱节点或后继结点，用它们替换该结点，在删除它的中序前驱结点或后继结点，而它的中序前驱后后继必定是叶子结点，该情况也转换为了第一种情况。

5.5 哈希表

构造哈希函数的方法：

  • 直接定址法
  • 数字分析法
  • 平方取中法
  • 折叠法
  • 除留余数法
  • 随机数法

处理冲突的方法：

  • 开放定址法

    1
    2
    3
    4
    5
    6
    Hi = (H(key) + di) mod m

     - i = 1, 2, 3, ..., k (k <= m - 1)
     - H(key) hash值
     - di 增量序列
     - m 哈希表的容量

    image-20221226123446806

    image-20221226123504750

  • 拉链法

    image-20221226123407144

  • 再哈希法

  • 建立公共溢出区法

    查找成功失败的ASL

    image-20221226122114871

6. 排序

  • 插入排序

    直接插入排序

    折半插入排序

    2路插入排序

    希尔排序

  • 交换排序

    冒泡排序

    快速排序

  • 选择排序

    选择排序

    堆排序

  • 归并排序

  • 基数排序