线性表

顺序表的应用

顺序表的定义

1
2
3
4
5
6
#define Max_size 100
typedef int ElemType // 数据类型，根据题意自行设定
typedef struct sqlist{  // 定义结构体名称
    ElemType data[Max_size];
    int length;
}Sqlist;    // 线性表名称

单链表的应用

单链表的定义

1
2
3
4
5
#define int ElemType;
typedef struct LNode{
    ElemType data;   // 当前所指节点的元素值
    struct LNode *next;   // 指向后继节点
}LNode, *Linklist;  //  节点 / 链表

基本操作

  1. 创建节点
    1
    2
    3
    4
    LNode *p;
    p = (LNode*)malloc(sizeof(LNode)); // 函数malloc分配一个类型为LNode的结点变量的空间
    p -> data = x; // 结点p的元素值为x
    p -> next = NULL;
  2. 赋值操作
  • $P = Q$ :将$P$的值赋给$Q$，此时两者同时指向一个结点
  • $P = Q \rightarrow next$ :将$P$赋值给$Q$的直接后继节点
  • $P = P \rightarrow next$ : 将指针$P$向后移动一个位置

  1. 在指针$P$后插入指针$Q$

    1
    2
    Q -> next = P -> next;
    P -> next = Q;

  2. 删除指针$P$的后继节点$Q$

    1
    2
    3
    Q = P -> next;
    P -> next = Q -> next;
    <font color = red>free(Q);</font>

二叉树（Binary Tree）

二叉树的结构体定义

1
2
3
4
5
#define int ElemType 
typedef struct BTNode{
    ElemType data;
    struct BTNode *Lchild, *Rchild; 
}TreeNode;

遍历二叉树

  1. 先序遍历(根 - 左 - 右)
    1
    2
    3
    4
    5
    6
    7
    void preOrderTraversal(TreeNode *root){
        if(root != null){
            cout << root -> data; 
            preOrderTraversal(root -> Lchild);
            pretOrderTraversal(root -> Rchild);
        }
    }
  2. 中序遍历(左 - 根 - 右)
    1
    2
    3
    4
    5
    6
    7
    void inOrderTraversal(TreeNode *root){
        if(root != null){
            inOrderTraversal(root -> Lchild);
            cout << root -> data; 
            inOrderTraversal(root -> Rchild);
        }
    }
  3. 后序遍历(左 - 右 - 根)
    1
    2
    3
    4
    5
    6
    7
    void postOrderTraversal(TreeNode *root){
        if(root != null){
            postOrderTraversal(root -> Lchild);
            postOrderTraversal(root -> Rchild);
            cout << root -> data;
        }
    }

    递归求二叉树深度

  • 深度(最大深度)
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    int DepthTree(TreeNode *root){
        if(root == null)
            return 0;
        int lH = DepthTree(root -> Lchild);
        int rH = DepthTree(root -> Rchild);
        if(lH > rH)
            return lH + 1;
        else
            return rH + 1;
    }
  • 最小深度(根节点到最近叶节点的最短路径上的节点数)
    1
    2
    3
    4
    5
    6
    7
    int minDepth(TreeNode *root){
        if(root == null)
            return 0;
        int lH = minDepth(root -> Lchild);
        int rH = minDepth(root -> Rchild);
        return min(lH, rH) + 1;
    }

    二叉树的最大宽度

        宽度: 各层节点的个数
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    int TreeWidth(TreeNode *root){
        if(root == null)
            return 0;
        int width = 0, maxWidth = 0;
        queue<BTnode*> Q;
        Q.push(root);
        while(!Q.empty()){
            width = Q.size();
            maxWidth = max(maxWidth, width);
            for(int i = 0; i < width; i++){
                BTnode *p = Q.front();
                Q.pop();
                if(p -> Lchild != null)
                    Q.push(p -> Lchild);
                if(p -> Rchild != null)
                    Q.push(p -> Rchild);
            }
        }
        return maxWidth;
    }

    图(Graph)

    结构体定义(实际题一般会给出)

  • 邻接表(过于复杂，没考过)
  • 邻接矩阵
    1
    2
    3
    4
    5
    6
    7
    8
    #define Max_Vertex 10
    #define ElemType int
    bool visited[Max_Vertex];
    typedef struct{
        ElemType arc[Max_Vertex][Max_Vertex]; // 邻接矩阵
        int numVertex, numEdge;
        int GraphType; // 图的类型(0无向，1有向)
    }Graph;

深度优先遍历(邻接矩阵)

1
2
3
4
5
6
7
8
9
10
11
12
void DFS(Grapg G, int i){    
    visited[i] = true;
    cout << i;
    for(int j = 0; j < G.numVertex; j++)
        if(G.arc[i][j] > 0 && !visited[j])
            DFS(G, j);
}
for(int i = 0; i < G.numVertex; i++)
    visited[i] = false;
for(int i = 0; i < G.numVertex; i++)
    if(!visited[i])
        DFS(G, i);

广度优先遍历(邻接矩阵)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
queue<ElemType> Q;
void BFS(Graph G, int v){
    while(!Q.empty()){
        ElemType w = Q.front(); // 访问队首元素
        cout << i;
        Q.pop();
        for(int i = 0; i < G.numVertex; i++)
            if(!visited[i]){
                Q.push(i);
                visited[i] = true;
            }
    }
}
for(int i = 0; i < G.numVertex; i++)
    visited[i] = false;
for(int i = 0; i < G.numVertex; i++)
    if(!visited[i]){
        Q.push(i);
        BFS(G, i);
    }