数据结构与算法

BackTracking（DFS + BoundingFunction） #include <iostream> using namespace std; int n = 5; int x[6] = {0,1}; int G[6][6] = { {0,0,0,0,0,0}, {0,0,1,1,0,1}, {0,1,0,1,1,1}, {0,1,1,0,1,0}, {0,0,1,1,0,1}, {0,1,1,0,1,0} }; void NextVetex(int k){ do { x[k] = (x[k] + 1) % (n + 1); if(x[k] == 0){ return; } // 确保和前一个节点联通 if(G[x[k - 1]][x[k]] != 0){ int j = 1; // 确保节点不会重复 for(; j < k; ++j){ if(x[j] == x[k]){ break; } } if(j == k){ // 如果不是最后一个节点 // 或者是最后一个节点，并且最后一个节点和第一个节点是联通的 if((k < n) || (k == n && G[x[n]][x[1]] !...

state space tree Back Tracking (DFS) brute force recursion Branch and Bound (BFS) 算法一： #include <iostream>using namespace std; void permutation(char S[], int k){ static int A[10] = {0}; static char res[10] = {0}; if(S[k] == '\0'){ res[k] = '\0'; printf("%s\n", res); } else{ for(int i = 0; S[i] != '\0'; ++i){ if(A[i] == 0){ A[i] = 1; res[k] = S[i]; permutation(S, k+1); A[i] = 0; } } } } int main() { char S[] = "ABC"; permutation(S, 0); return 0; } output:...

#include <iostream> void shellSort(int A[], int n){ int gap, i, j, temp; for(gap = n/2; gap >= 1; gap /= 2){ for(i = gap; i < n; ++i){ temp = A[i]; j = i - gap; while(j >= 0 && A[j] > temp){ A[j+gap] = A[j]; j = j - gap; } A[j + gap] = temp; } } } int main() { int A[] = {8, 3, 7, 4, 9, 2, 6, 5, 1, 11, 10}; int n = 11; shellSort(A, n); for(int i = 0; i < n; ++i){ std::cout<<A[i] << " "; } return 0; }

#include <iostream> void Merge(int A[], int l, int mid, int h){ int i, j, k; i = l; j = mid + 1; k = l; int B[h+1]; while(i <= mid && j <= h){ if(A[i] < A[j]){ B[k++] = A[i++]; } else{ B[k++] = A[j++]; } } for(; i <= mid; i++){ B[k++] = A[i]; } for(; j <= h; j++){ B[k++] = A[j]; } for(i = l; i <= h; i++){ A[i] = B[i]; } } // 迭代 void IMergeSort(int A[], int n) { int p, i, l, mid, h; for(p = 2; p <= n; p = p * 2){ for(i = 0; i + p - 1 < n; i = i + p){ l = i; h = i + p -1; mid = (l + h) / 2; Merge(A, l, mid, h); } if(i < n){ l = i; h = n-1; mid = (l+h)/2; Merge(A,l,mid,h); } for(int i = 0; i < n; ++i){ std::cout<<A[i] << " "; } std::cout << "\n"; } if(p/2 < n){ Merge(A, 0, p/2-1, n-1); } } // 递归 void MergeSort(int A[], int l, int h){ int mid; if(l < h){ mid = (l + h) / 2; MergeSort(A, l, mid); MergeSort(A, mid+1, h); Merge(A, l, mid, h); } } int main() { int A[] = {8, 3, 7, 4, 9, 2, 6, 5, 1, 11, 10}; int n = 11; IMergeSort(A, n); for(int i = 0; i < n; ++i){ std::cout<<A[i] << " "; } return 0; } 输出：...

先序遍历 template<typename T> void PreOrder(BinaryTreeNode<T>* root){ stack<BinaryTreeNode<T>*> aStack; BinaryTreeNode<T>* pointer = root; aStack.push(nullptr); // 栈底监视哨 while(pointer){ // 或者 !aStack.empty() Visit(pointer); // 访问当前结点 if(pointer->rightchild() != nullptr){ // 右孩子入栈 aStack.push(pointer->rightchild()); } if(pointer->leftchild() != nullptr){ // 左路下降 pointer = pointer->leftchild(); }else{ // 左子树访问完毕，转向访问右子树 pointer = aStack.top(); aStack.pop(); } } } 中序遍历 template<typename T> void InOrder(BinaryTreeNode<T>* root){ stack<BinaryTreeNode<T>*> aStack; BinaryTreeNode<T>* pointer = root; while(!aStack.empty() || pointer){ if(pointer){ // Visit(pointer); // 前序访问点 aStack....