数据结构笔记

发表于 更新于 Disqus：

数据结构

链表

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
#include <iostream>
struct Node
{
    Node(double a, int b, Node* c) : coef(a), expn(b), next(c) {}
    double coef;
    int expn;
    Node* next;
};
void Create(Node*& head)
{
    int num; std::cin >> num;//每个链表中数字的个数
    double coef;
    int expn;
    for (int i = 0; i < num / 2; i++)
    {
        std::cin >> coef >> expn;
        Node* new_node = new Node(coef, expn, NULL);
        if (head != NULL)
            new_node->next = head;
        head = new_node;
    }
}
void Add(Node*& head1, Node*& head2)
{
    while (head2 != NULL)
    {
        Node* ptr1 = head1;
        while (ptr1 != NULL)
        {
            if (head2->expn == ptr1->expn)
            {
                ptr1->coef = ptr1->coef + head2->coef;
                break;
            }
            else
                ptr1 = ptr1->next;
        }
        if (ptr1 == NULL)
        {
            Node* new_node = new Node(head2->coef, head2->expn, head1);
            head1 = new_node;
        }
        head2 = head2->next;
    }
}
int main()
{
    Node* x1 = NULL, * x2 = NULL;
    Create(x1); Create(x2);
    Add(x1, x2);
    return 0;
}

树

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
#include <iostream>
#include <stack>
using namespace std;
struct tree
{
    tree(char a, tree *b, tree *c) : data(a), left(b), right(c) {}
    char data;
    tree *left;
    tree *right;
};
void Creat(tree *&root)
{
    char c;
    cin >> c;
    if (c != '#')
    {
        root = new tree(c, NULL, NULL);
        Creat(root->left);
        Creat(root->right);
    }
}
void PreOrder(tree *root)
{
    stack<tree *> stack;
    while (root != NULL || !stack.empty())
    {
        if (root != NULL)
        {
            //此处输出是前序遍历
            cout << root->data << " ";
            stack.push(root);
            root = root->left;
        }
        else
        {
            root = stack.top();
            //此处输出是中序遍历
            // cout<<root->data<<" ";
            root = root->right;
            stack.pop();
        }
    }
}
int main()
{
    tree *root = NULL;
    Creat(root);
    PreOrder(root);
    return 0;
}

树的非递归前序遍历

  1. 创建一个栈
    1. 只要节点不为空或者栈不为空
      1. 如果节点为空
        1. 打印
        2. 入栈
        3. 左走
      2. 如果节点不为空
        1. 取栈首
        2. 右走
        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
#include <iostream>
#include <queue>
#define MAX_VERTEX_NUM 20
using namespace std;
struct Graph
{
    char vertex[MAX_VERTEX_NUM];
    bool visited[MAX_VERTEX_NUM];
    int edge[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
    int vertex_num, edge_num;
};
void Create(Graph* G)
{
    cin >> G->vertex_num;
    cin >> G->edge_num;
    for (int i = 0; i < G->vertex_num; i++)
    {
        cin >> G->vertex[i];
        G->visited[i] = false;
    }
    for (int i = 0; i < G->vertex_num; i++)
        for (int j = 0; j < G->vertex_num; j++)
            G->edge[i][j] = 0;
    int v1, v2;
    for (int k = 0; k < G->edge_num; k++)
    {
        cin >> v1 >> v2;
        G->edge[v1][v2] = 1;
        G->edge[v2][v1] = 1;
    }
}
void DFS(Graph* G, int i)
{
    cout << G->vertex[i] << " ";
    G->visited[i] = true;
    for (int j = 0; j < G->vertex_num; j++)
        if (G->edge[i][j] == 1 && !G->visited[j])
            DFS(G, j);
}
void visit(queue<int>& queue, int i, Graph* G)
{
    G->visited[i] = true;
    queue.push(i);
}
void BFS(Graph* G)
{
    queue<int> queue;
    for (int i = 0; i < G->vertex_num; i++)
        if (!G->visited[i])//这个模块起名为访问列吧
        {
            visit(queue, i, G);//每列入队
            while (!queue.empty())//行入队后检查队是否为空，队首作为行的检测依据
            {
                for (int j = 0; j < G->vertex_num; j++)
                    if (G->edge[queue.front()][j] == 1 && !G->visited[j])//这个模块起名为访问行
                        visit(queue, j, G);//每行入队
                cout << G->vertex[queue.front()] << " ";
                queue.pop();
            }
        }
}
int main()
{
    //测试数据：9 15  A B C D E F G H I 0 1 0 5 1 2 1 8 1 6 2 3 2 8 3 4 3 7 3 6 3 8 4 5 4 7 5 6 6 7
    Graph G;
    Create(&G);
    //每次只能选择一个运行
    //DFS(&G, 0);
    BFS(&G);
    return 0;
}

邻接矩阵的广度遍历

  1. 创建队列
  2. 遍历 i (列)所有节点，对于未访问的节点进行下述操作
    1. 打印 i 处节点并设置为访问过
    2. 将数字 i 入队
    3. 队列不为空时执行如下操作
      1. 将队首元素赋值给 i
      2. 遍历 j (行)所有节点，当 i 和 j 有关系且 j 处节点未访问时执行如下操作
        1. 打印 j 处节点并设置为访问过
        2. 将数字 j 入队
      3. 队首出队

邻接矩阵的深度遍历

  1. 遍历 i (列)所有节点，未访问节点进入 DFS(G,i)
  2. DFS 函数：
    1. 打印进入 DFS 的节点并设置为访问
    2. 遍历 j (行)所有节点，当 i 和 j 有关系且未访问的节点进入 DFS(G,j)

邻接表

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
#include <iostream>
#include <list>
#include <vector>
#include <stack>
#include <queue>
using namespace std;
struct Vertex
{
    char data;
    bool visited;
    list<Vertex*> edge;
};
void Creat(vector<Vertex>& G)
{
    int vertex_num; cin >> vertex_num;
    int edge_num; cin >> edge_num;

    Vertex temp;
    for (int i = 0; i < vertex_num; i++)
    {
        cin >> temp.data;
        temp.visited = false;
        G.push_back(temp);
    }

    int v1, v2;
    for (int i = 0; i < 2 * edge_num; i++)
    {
        cin >> v1 >> v2;
        G[v1].edge.push_back(&G[v2]);
    }
}
Vertex* next_vertex(Vertex* vertex)
{
    for (auto iiter = vertex->edge.begin(); iiter != vertex->edge.end(); iiter++)
        if ((*iiter)->visited == false)
        {
            (*iiter)->visited = true;
            return *iiter;
        }
}
void DFS(Vertex* vertex)
{
    if (vertex != NULL)
    {
        cout << vertex->data << " ";
        vertex->visited = true;
        DFS(next_vertex(vertex));
        DFS(next_vertex(vertex));
    }
}
void get_level(queue<Vertex*>& queue, Vertex* vertex)
{
    for (auto iiter = vertex->edge.begin(); iiter != vertex->edge.end(); iiter++)
        if ((*iiter)->visited == false)
        {
            (*iiter)->visited = true;
            queue.push((*iiter));
        }
}
void BFS(Vertex* vertex)
{
    queue<Vertex*> queue;
    queue.push(vertex);
    while (!queue.empty())
    {
        cout << queue.front()->data << " ";
        queue.front()->visited = true;
        get_level(queue, queue.front());
        queue.pop();
    }
}
int main()
{
    // 9 15 A B C D E F G H I 0 1 0 5 1 0 1 2 1 6 1 8 2 1 2 3 2 8 3 2 3 4 3 6 3 7 3 8 4 3 4 5 4 7 5 0 5 4 5 6 6 1 6 3 6 5 6 7 7 3 7 4 7 6 8 1 8 2 8 3
    vector<Vertex> G;
    Creat(G);
    //每次只能运行一个
    //DFS(&G[0]);
    BFS(&G[0]);
    return 0;
}

邻接表的深度遍历

·只要顶点不为空，打印顶点并设置为访问过；将下一个顶点进入该函数

邻接表的广度遍历

  1. 创建队列
  2. 第一个顶点入队
  3. 队不为空，执行下述操作
    1. 取队首顶点
    2. 打印队首顶点并设置为访问过
    3. 获得下一层顶点
    4. 队首出队

next_node

查链表，找到未访问顶点；设置为访问，返回该顶点

get_level

查链表，找到未访问顶点；设置为访问，将该顶点入队

排序

快排

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
using namespace std;
void sort(int arry[], int begin, int end)
{
    if (begin < end)
    {
        int sbit = begin;
        int pivot = arry[end];
        for (int j = begin; j < end; j++)
            if (arry[j] < pivot)
              {swap(arry[j], arry[sbit]); sbit++;}
              //每个数字与pivot比较，较小的与sbit交换
              //将pivot与sbit交换
        swap(arry[sbit], arry[end]);
        sort(arry, begin, sbit - 1);
        sort(arry, sbit + 1, end);
    }
}
int main()
{
    int arry[8] = { 27, 13, 65, 8, 45, 3, 81, 72 };
    sort(arry, 0, 7);
    return 0;
}

堆排

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
#include <iostream>
using namespace std;
void max_heap(int arry[], int begin, int end)
{
    int root = begin;
    int left = root * 2 + 1;
    int right = root * 2 + 2;
    while (left <= end)
    {
        if (arry[left] < arry[right] && right <= end) left++;
        if (arry[left] < arry[root]) return;
        else
        {
            swap(arry[left], arry[root]);
            root = left;
            left = root * 2 + 1;
            right = root * 2 + 2;
        }
    }
}
void sort(int arry[], int end)
{
    for (int i = end / 2; i >= 0; i--)
        max_heap(arry, i, end);
    for (int i = end; i > 0; i--)
    {
        swap(arry[0], arry[i]);
        max_heap(arry, 0, i-1 );
    }
}
int main()
{
    int arry[11] = { 5, 8, 1, 4, 2, 3, 9, 10, 7, 14, 16 };
    sort(arry, 10);
    return 0;
}
  1. 堆排序
  2. 得最大堆的方法：
    1. 范围：从 非叶子节点 到 根节点
    2. 调整对象：循环因子 到 表
  3. 排序的方法：
    1. 范围：从 表尾 到 根节点前
    2. 调整对象：无序首 到 无序尾
  4. 维持堆的方法：