数据结构与算法

发表于 | 分类于 |

对数据结构算法的学习整理

二叉树

后序遍历的应用

  • 计算二叉树节点的个数
1
2
3
4
int treeSIze(Node* tree) {
    if (tree == null) return 0;
    else return 1 + treeSize(tree -> left) + treeSize(tree -> right)
}
  • 计算二叉树节点的深度
1
2
3
4
5
6
7
8
int height(Node*tree) {
    if (tree == null) return 0;
    else {
            int i = height(tree -> left);
            int j = height(tree -> right);
            return (i < j) ? j + 1 : i + 1;
        }
    }

前序遍历的应用

  • 判断二叉树是否相等
1
2
3
4
5
6
7
// 核心代码
if (a == null&&b == null) return true;
if (a != null&&b != null&&a -> data == b -> data
        &&equal(a -> left, b -> left)
        &&equal(a -> right, b -> tight))
        return true;
else return false;

遍历的非递归算法

  • 前序遍历
    左子树优先遍历，在访问左子树之前，把该节点的右子树压进栈里面
1
2
3
4
5
6
7
8
while (p != null) {
    cout << p -> data << endl;
    if (p -> right) stack.push(p -> right)
    if (p -> left) p = p -> left;
    else {
        p = stack.top();
    }
}
  • 中序遍历
    一直往左子树的链走并进栈，知道左子树为空，出栈，访问节点，并将右子树进栈，沿着右子树遍历下去
1
2
3
4
5
6
7
8
9
10
11
do {
    while (p) {
        stack.push(p);
        p = p -> left;
    }
    if (!s.empty()) {
        cout << p -> data << endl;
        s.pop();
        p = p -> right;
    }
} while (p||!stack.empty());

根据遍历序列唯一确定二叉树

  • 根据前序遍历和中序遍历确定二叉树
    根节点就是前序遍历的第一个节点，然后由此将中序遍历的节点分成了两部分，这两部分分别是左子树和右子树，然后再通过前序遍历的下一个节点，判断出左子树的根节点是哪一个，依次类推。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    // 找到目标元素在中序遍历序列中的位置
    int position (int i) {
        for (size_t j = 0; j < num; j++) {
            if (Inorder[j] == i) return j;
        }
    }
        void PreMidcreate(Nodeptr& ptr, int prePtr, int inPtr, int len) {
            if (len <= 0) {
                ptr = null;
                return;
            }
            ptr = new Node;
            ptr -> val = Preorder[prePtr];
            int m = position(Preorder[prePtr]);
            PreMidcreate(ptr -> left, prePtr + 1, inPtr, m - inPtr);
            PreMidcreate(ptr -> right, prePtr + 1 + m - inPtr, m + 1, len - 1 - (m - inPtr));
        }

    ptr是指向根节点的指针
    ptePtr是当前先序遍历序列的第一个节点的位置
    inPtr是当前后续遍历序列的第一个节点的位置
    len是长度

  • 根据后序遍历和中序遍历确定二叉树
    后序遍历序列中最后一个元素就是根节点，然后在中序遍历的序列中找到它的位置，并且区分为左子树右子树，然后回到后序遍历的序列中，再一堆左子树的序列中找到最后面的一个，这就是子数的根节点，依次类推：
    中序序列 HLDBEKAFCG
    后序序列 LHDKEBFGCA

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    // postPtr 注意是后序遍历的序列的尾元素的位置
    void PostMidcreate(Nodeptr& ptr, int postPtr, int inPtr, int len) {
        if (len <= 0) {
            ptr = null;
            return;
        }
        ptr = new Node;
        ptr -> val = Postorder[postPtr];
        int m = position(Postorder[postPtr]);
        PostMidcreate(ptr -> left, postPtr - 1 - (len - 1 - (m - inptr), inptr, m - inptr), inPtr, m - inPtr);
        PostMidcreate(ptr -> right, postPtr - 1, m + 1, len - 1 - (m - inPtr));
    }

  • 在后序序列LHDKEBFGCA中最后出现的元素为A，HLDBEK|A|FCG

  • 在后序序列LHDKEB中最后出现的元素为B，HLD|B|EK|A|FCG
  • 在后序序列LHD中最后出现的元素为D，HL|D|B|EK|A|FCG
  • 在后序序列LH中最后出现的元素为H，H|L|D|B|EK|A|FCG
  • 在后序序列KE中最后出现的元素为E，H|L|D|B|E|K|A|FCG
  • 在后序序列FGC中最后出现的元素为C，H|L|D|B|E|K|A|F|C|G

  • 所有元素都已经定位，二叉树求解完成。

            A
    /     \
    B       C
/ \     /  \
D  E     F   G
/    \
H      K                    
\                         
L

二叉树的计数

$$\sum_{i=0}^{n-1} bk*b{n-k-1}$$

森林与二叉树

  • 森林与二叉树有一一对应的关系
  • 对所有的多叉树采用子女-兄弟表示方法(兄弟是右孩子,子女是左孩子),将所有的多叉树转变成二叉树,再将其的连成右孩子链,形成森林

  • 森林的深度优先遍历(转换成二叉树之后分别对应先序遍历和后序遍历)

    • 先根次序遍历
      访问根节点 -> 遍历第一颗树 -> 遍历其他的树

    • 后根次序遍历
      遍历第一棵树 -> 访问根节点 -> 遍历其他的树

      • 后根次序遍历求二叉树的深度
      1
      2
      3
      4
      5
      6
      int findDepth(node* t) {
          if (t == null) return 0;
              int firstChild = find(t -> firthChild) + 1;
              int nextSibling = find(t -> nextSibling);
              return (firstChild > nextSibling) ? firstChild : nextSibling;
      }

  • 森林的广度优先遍历(使用队列,在最开始的时候加入所有根节点)

堆

实现支持插入操作,能方便的从中取出最大或者最小关键码的记录的优先级队列就是堆，是一个完全二叉树（分为最大堆和最小堆）

  • 堆的存储
    堆一般存储在数组当中通过下标表示父子关系，父节点：（i-1）/2，左右子节点：2i+1/2i+2

  • 复制构造函数
    将数组第一个元素看成堆顶，下一个元素往堆当中添加，执行重排算法（相当于一个个的执行插入算法

1
2
3
4
5
6
7
8
9
10
minHeap(int a[], int n) {
    size = n;
    heap = new int[size];
    for (int i = 0; i < n; i++) heap[i] = a[i];
    int currentPos = (size - 2) / 2; // 最后的分支节点
    while (currentPos > 0) { // 0就是根节点
        siftDown(currentPos, size - 1);
        currentPos -- ;// 向前换一个分支节点
    }
}
  • 重排算法
    siftDown是自上而下的调整方法,对每一个替换的元素最终位置的确定,用一个循环,使他与序列进行比较
1
2
3
4
5
6
7
8
9
10
11
12
13
14
void siftDown (int start, int size) {
    int i = start, int j = 2 * i + 1 ; //分别是父亲与孩子的关系
    int temp = heap[i];
    while (j <= m) {
        if (j < m&&heap[i] > heap[i + 1]) j++; // 找到孩子当中较大的那一个
        if (temp < heap[j]) break;
        else {
            heap[i] = heap[j];
            i = j; 
            j = j * 2 + 1; // 如果仍旧比较大的话 就下移
        }
        heap[i] = temp; //　退出循环的时候ｉ已经指向了对应的位置
    }
}
  • 插入算法
    往堆的最末尾插入，数组末尾、二叉树叶子节点，执行重排算法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void insert(const int x) {
    heap[size] = x;
    siftUp(size);
    size++;
}
void sift(int start) {
    int j = start, i = (j - 1) / 2; // 同样找到兄弟和父亲的节点
    while (j > 0) {
        if (heap[i] < temp) break;
        else {
            heap[j] = heap[i];
            j = i;
            i = (i - 1) / 2;
        }
        heap[j] = temp;
    }
}
  • 删除算法
    将完全二叉树的0号元素取走之后,用堆的最后一个节点填补, 将根节点分别与左右儿子的大小进行比较，不断替换
1
2
3
4
5
6
void removeMin(int & x) {
    x = heap[0];
    heap[0] = heap[size - 1];
    size--;
    siftDown(0, size - 1);
}

Huffman树

带权路径长度最小的扩充二叉树(带权值的二叉树)不一定是完全二叉树

  • 哈弗曼编码

    • input
      10
      S S U U U S U L U U

    • output
      U 6 1
      S 3 01
      L 1 00

      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 "iostream"
      #include "stack"
      #include "algorithm"
      #include "string"
      #include "memory.h"
      using namespace std;
      struct Node
      {
          int frequency;// 该字符的频数
          char val;
          string code;    // 哈弗曼编码
          Node* left;
          Node* right;
          Node(int fre, int index) {  // 以频树和字符来创建节点
              frequency = fre;
              val = index + 'A';
              left = NULL;
              right = NULL;
          }
      } * nodeptr[26];
      bool compare(Node* a, Node* b) {
          return a -> frequency > b -> frequency;
      }
      void set_code(Node* root) { // 从上往下操作获得哈弗曼编码
          if (root -> left) {
              root -> left -> code = root -> code + '0';
              set_code(root -> left);
          }
          if (root -> right) {
              root -> right ->code = root -> code + '1';
              set_code(root -> right);
          }
      }
      int main() {
          int num;
          cin >> num;
          int freOfAlp[26];
          memset(freOfAlp, 0, sizeof(freOfAlp));
          int count = 0;
          while (num--) {
              char temp;
              cin >> temp;
              if (freOfAlp[temp - 'A'] == 0) {
                  count++;    // 统计字符的数量
              }
              freOfAlp[temp - 'A']++;
          }
          int index = 0;
          for (int i = 0; i < 26; i++) {
              if (freOfAlp[i] != 0) {
                  nodeptr[index++] = new Node(freOfAlp[i], i);    // 将所有的字符都存在一个数组里面
              }
          }
          stack<Node*> s;
          while (count != 1) {
              sort(nodeptr, nodeptr + count, compare);    // 先进行排序
              if (nodeptr[count - 1] -> left == NULL&&nodeptr[count - 1] -> right == NULL)
                  s.push(nodeptr[count - 1]);
              if (nodeptr[count - 2] -> left == NULL&&nodeptr[count - 2] -> right == NULL)
                  s.push(nodeptr[count - 2]);
              // 将未被处理的节点存进栈中,是按顺序的
              Node* father = new Node(nodeptr[count - 1] -> frequency + nodeptr[count - 2] -> frequency, 0);
              father -> left = nodeptr[count - 1];
              father -> right = nodeptr[count - 2];
              nodeptr[count - 2] = father;    // 创建父亲节点 并存放到队列里面
              count --;
          }
          set_code(nodeptr[0]);   // 获取哈弗曼编码
          while(!s.empty()) {
              cout << s.top() -> val << " " << s.top() -> frequency << " " << s.top() -> code << endl;
              s.pop();    //将栈中的队列一一输出
          }
      }

搜索

折半搜索

  • 迭代算法

    1
    2
    3
    4
    5
    6
    7
    8
    9
    int BinarySearch(int x) {
        int high = size - 1, low = 0, mid;
        while (low <= high) {
            mid = (low + high) / 2;
            if (x > Element[mid].key) low = mid + 1;
            else if (x < Element[mid].key) high = mid - 1;
            else return mid + 1
        }
    }

  • 递归算法

    1
    2
    3
    4
    5
    6
    7
    8
    9
    int BinarySearch(int x, int high, int low) {
        int mid = 0;
        if (low <= high) {
            mid = (low + high) / 2;
            if (x > Element[mid - 1].key) mid = BinarySearch(x, high, mid+1)
            else if (x < Element[mid-1].key) mid = BinarySearch(x, mid-1, low);
        }
        return mid;
    }

二叉搜索树

  • 插入

    1
    2
    3
    4
    5
    6
    7
    8
    bool insert(int x, Node*& ptr) {
        if (ptr == null) {
            ptr = new Node(x);
            return true;
        } else if (x < ptr -> data) insert(x, ptr -> left);
        else if ( x > ptr -> data) insert(x, ptr -> right);
        else return false;  // 已经存在此元素
    }

  • 删除
    删除的步骤首先应该先找到目标节点,删除之后再对树进行调整

    • 叶节点, 没有操作
    • 子树有一个为空的,用非空子树的节点进行替代

    • 子树都是非空的,则寻找右子树中序遍历下的第一个节点进行替代,递归进行操作

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      bool remove(int x, Node* & ptr) {
          Node* temp;
          if (ptr) {
              if (x < ptr -> data) remove(x, ptr -> left);
              else if (x > ptr -> data) remove(x, ptr -> right);  // 执行到这一步找到了节点
              else if (ptr -> left&&ptr -> right) {
                  temp = ptr -> right;
                  while (temp -> left) temp = temp -> left;
                  ptr -> data = temp -> data;
                  remove(ptr -> data, ptr -> right);
              }
              else {
                  temp = ptr;
                  if (ptr -> right) ptr = ptr -> right;
                  else ptr = ptr -> left;
                  delete temp;
                  return true;
              }
          }
      }

图论

Floyd最短路径算法

  • 核心代码
    通过A这个矩阵记录两点之间最短路径的距离，path矩阵记录的是最短路径经过的两点之间的前驱动。后面通过循环列出最短的路径上的各个点

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    for (size_t k = 0; k < numOfVertex; k++) {
        for (size_t i = 0; i < numOfVertex; i++) {
            for (size_t j = 0; j < numOfVertex; j++) {
                if (A[i][j] > A[i][k] + A[k][j]) {
                    A[i][j] = A[i][k] + A[k][j];
                    path[i][j] = path[i][k];
                }
            }
        }
    }
    void showPath(int source, int desk) {
    cout << source << " ";
    int temp = path[source][desk];
    while (temp != desk) {
        cout << temp << " ";
        temp = path[temp][desk];
    }
    cout << desk << endl;
    }
    • 完整代码实例
      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 "iostream"
      #include "memory.h"
      #include "stack"
      using namespace std;
      int edge[1000][1000];
      int path[1000][1000];
      int A[1000][1000];
      int start, end;
      int numOfVertex, numOfEdge;
      void create() {
      cin >> numOfVertex >> numOfEdge;
      cin >> start >> end;
      for (size_t i = 0; i < numOfVertex; i++) {
          for (size_t j = 0; j < numOfVertex; j++) {
              edge[i][j] = 999;
              A[i][j] = 999;
          }
      }
      for (int i = 0; i < numOfVertex; i++) edge[i][i] = 0;
      for (size_t i = 0; i < numOfEdge; i++) {
          int j, k;
          cin >> j >> k;
          edge[j][k] = 1;
          edge[k][j] = 1;
      }
      }
      void Floyd() {
      for (size_t i = 0; i < numOfVertex; i++) {
          for (size_t j = 0; j < numOfVertex; j++) {
              A[i][j] = edge[i][j];
              path[i][j] = j;
          }
      }
      for (size_t k = 0; k < numOfVertex; k++) {
          for (size_t i = 0; i < numOfVertex; i++) {
              for (size_t j = 0; j < numOfVertex; j++) {
                  if (A[i][j] > A[i][k] + A[k][j]) {
                      A[i][j] = A[i][k] + A[k][j];
                      path[i][j] = path[i][k];
                  }
              }
          }
      }
      }
      void showPath(int source, int desk) {
      cout << source << " ";
      int temp = path[source][desk];
      while (temp != desk) {
          cout << temp << " ";
          temp = path[temp][desk];
      }
      cout << desk << endl;
      }
      void display() {
      for (size_t i = 0; i < numOfVertex; i++) {
          for (size_t j = 0; j < numOfVertex; j++) {
              if (A[i][j] != 999) {
                  cout << "路径" << i << " " << j << " = "<< A[i][j] << " ";
              }
          }
      }
      }
      int main(int argc, char const *argv[]) {
          create();
          Floyd();
          display();
          showPath(0, 1);
          return 0;
      }

最小生成树prim算法

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
void showShortestPath(int n) {
    int i, j, k, minLongestPath = 0;
    int tempShortestPath = MAXINT;
    for (i = 0; i < n; i ++) {
        lowestPath[i] = edges[0][i];
        nearestVertex[i] = 0;
    }
// 初始选择序号为0的点添加进最小生成树当中
// lowestPath 表示当前访问第i个节点的最短边的长度
// nearestVertex 表示节点有没有存放进最小生成树中(-1/非0,非0表示节点最短,颗得到边)
    nearestVertex[0] = -1;  // 存进树中
    lowestPath[0] = 0;
    for (i = 0; i < n; i ++) {
        tempShortestPath = MAXINT;
        k = -1;
            //  这个循环是寻找当前储存的最短的边
            //在未纳入路径顶点里面找到离已经纳入路径的顶点最近的顶点，做出标记
        for (j = 0; j < n; j ++) {
            if (nearestVertex[j] != -1 && lowestPath[j] < tempShortestPath) {
                tempShortestPath = lowestPath[j];
                k = j;
            }
        }
        // 最短边的序号为k
        if (k != -1) {
            nearestVertex[k] = -1;
            //  这里只是更新一下查找的最短边的长度
            if (minLongestPath < tempShortestPath)
                minLongestPath = tempShortestPath;
            // 新的节点加入到生成树当中,可能会缩短访问那些未被添加的节点,更新lowestPath
            for (j = 0; j < n; j ++) {
                //在新的顶点加入到路径之后，对路径内与路径外顶点之间的最短距离进行更新,
                //并更新对应最靠近的顶点的关系
                if (nearestVertex[j] != -1 && edges[k][j] < lowestPath[j]) {
                    lowestPath[j] = edges[k][j];
                    nearestVertex[j] = k;
                }
            }
        }
    }
    printf("%d\n", minLongestPath);
}

拓扑排序

算法思路:先将入度为零的节点加入队列中,然后删除该点和所有的边,之后按照这样的步骤,输出的序列就是拓扑排序的序列

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
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; i++)
    v[i].clear();
s.clear();
memset(inDegree, 0, sizeof(inDegree));

while (m--){
    scanf("%d %d", &a, &b);
    v[a].push_back(b);
    inDegree[b]++;
}

for (int i = 1; i <= n; i++){
    if (inDegree[i] == 0){
        s.insert(i);
    }
}

int tmp;
while (!s.empty()){
    tmp = *s.begin();
    s.erase(s.begin());
    
    printf("%d ", tmp);
    
    int size = v[tmp].size();
    for (int i = 0; i < size; i++){
        inDegree[v[tmp][i]]--;
        if (inDegree[v[tmp][i]] == 0){
            s.insert(v[tmp][i]);
        }
    }     
}

排序算法

希尔排序

属于插入排序,先取一个较大的gap之后,将元素按照gap分成若干个含有较少元素的组,直接进行插入排序,在逐步缩小组别,在原有的排序基础上再进行插入排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int i, j, gap = right - left + 1;   // left为未经过排序的序列的左端点
int temp;
do {
    gap = gap / 3 + 1;
    for (i = left + gap; i <= right; i++)
        if (Array[i] < Array[i - gap]) { // 后面的元素比前面的元素小,因此要进行换位
            temp = Array[i];
            j = i - gap;
            do {    // 不断的进行移位和替换
                Array[i] = Array[j];
                j = i;
            } while (j >= left&&temp < Array[j]);
            Array[i] = temp;
        } 
} while (gap > 1);

快速排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void QuitSort(int left, int right) {
    if (left < right) {
        int position = Partition(left, right);
        // 对划分后的两个子区间按照基准元素进行排序
        QuitSort(left, position - 1);
        QuitSort(position + 1, right);
    }
}
int Partition(int low, int high) {
    int element = Array[low];
    int position = low;
    // 去第一个点为基准点
    for (int i = low + 1; i <= high; i++) {
        if (Array[i] < element) {
            position++; // 这个位置就是要交换的位置
            if (position != i) swap(Array[i], Array[position])
        }
    }
    Array[low] = Array[position];
    Array[position] = element;
    //再将基准元素放回到它应该在的位置
}

归并排序

两路归并的基本思路是现将L1的内容复制到辅助数组L2中,在L2中有指针S1(前一个已排序的序列的起始点), S2(后一个已排序的序列的起始点),二者之间进行同时的对比,然后通过t指针(L1中的存放指针)来将L2中的元素写进L1中

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void paritition(int left, int right) {
    if (left >= right) return;
    int mid = (left + right) / 2;
    paritition(left, mid);
    paritition(mid + 1, right);
    merge(left, mid, right);
}
void merge(int left, int mid, int right) {
    for (int i = left; i <= right; i++) {
        L2[i] = L1[i];
    }
    int s1 = left, s2 = mid + 1, t = left;
    while (s1 <= mid&&s2 <= right) {    // 当两个序列都存在元素的时候
        if (L2[s1] <= L2[s2]) L1[t++] = L2[s1++];
        else L1[t++] = L2[s2++];
    }
    while (s1 <= mid) L1[t++] = L2[s1++];
    while (s2 <= mid) L1[t++] = L2[s2++];
    // 存放还没有存进去的元素
}

复杂度分析