#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....
一、相关概念 结点：根节、叶节点、分支结点、兄弟结点、父子结点 边、路径 结点深度、高度、层数 根节点为第 0 层 深度指从根节点到该节点的边的数量 高度指从此节点到叶节点的结点数量 满二叉树、完全二叉树 满二叉树指除了度为 0 的叶节点就是度为 2 的分支节点 完全二叉树指只有最下面的两层度是小于 2 的，且最下面的结点都集中在左侧 扩充二叉树 二叉树性质
模式串 next 向量计算： 字符串比较 int mystrcmp(const char* str1, const char* str2){ int i = 0; while(str1[i] == str2[i] && str1[i] != '\0'){ i++; } return str1[i] - str2[i]; }