#include int main(int argc, char* argv[]) { char a[] = "hello world!"; char *b; char c[3]; char *d = "world"; printf("sizeof a=%d\n", sizeof(a));…
(1)辗转相除法（欧几里得算法） 辗转相除法基本思想：两正整数的最大公约数等于较大的数对较小的数取模的结果与较小的数的最大公约数，即：$$gcd(a,b)=gcd(b, a\%b), a\geq{b}$$ #include using namespace std; // greatest common divisor // 仅用于计算两正整数的最大…
使用异或操作可以在不使用临时变量的情况下交换两变量的值。 异或操作符：^。 对于位操作：0^0=0, 1 ^ 1 = 0, 0 ^ 1 = 1 ^ 0 = 1。 对于一个变量a：a ^ a = 0； a ^ 0 = a。 #include void swap(int &a, int &b) { a = a ^ b; // a'…
(1) 寻找序列中第i小的元素 基本思想(递归划分)： 1) 使用快速排序中使用的方法对序列进行划分（最好使用随机版本），并返回划分位置（划分使得划分点左侧元素的值小于等于x，右侧的元素的值大于等于x）。 2) 若划分位置==i，则返回划分位置处的值；划分位置<i，从划分位置左侧继续划分；划分位置>i，从划分位置右侧继续划分。 3) 重…
（1）二叉树分类 一般二叉树，完全二叉树，满二叉树。 满二叉树：二叉树中除了叶节点以外的结点都有两个子节点，且叶节点位于同一层。 完全二叉树：当且仅当一颗深度为k、具有n个结点的二叉树的每个节点与深度为k的完全二叉树中编号从1~n的节点一一对应时，称该树为完全二叉树。 （2）二叉树的遍历方法 先序遍历：访问根节点->先序遍历左子树->先…
多少排序算法都是基于对序列中的元素进行比较操作来完成排序的，称这些排序算法为比较排序。如：快速排序（平均时间复杂度[latex]\Theta(n\lg{n})[/latex]，最坏时间复杂度[latex]\Omega(n\lg{n})[/latex]），随机快速排序（[latex]\Theta(n\lg{n})[/latex]），合并排序（[lat…
原始QuickSort算法： 算法平均复杂度：[latex]\Theta(n\lg{n})[/latex]（一般情况下） 算法在最坏情况下的复杂度：[latex]\Theta(n^2)[/latex](在输入序列为排列好的数的情况下) 在实际应用中，快速排序算法通常比归并排序算法快三倍左右。 // 数组划分子程序 int Partition(int…
斐波那契数列由以下的公式定义： $$!F_n=\begin{cases}0 & ,n=0 \\1 & ,n=1 \\F_{n-1} + F_{n-2} & ,n\geq2\end{cases}$$ 1. 递归法(最慢) 时间复杂度：$$T(n)=\Omega(\varphi^n)$$指数级。 // 输出斐波那契数列下标为n的…
问题描述：在有序数列中查找某个指定数。 #include #include using namespace std; // 二分查找(递归法) // （data[]中存储的是生序排列的数据, target为待查找数据） int BinarySearch(int *data, int start, int end, int target) { int…
#include #include using namespace std; // 插入排序 void InsertSort(vector &data) { for (int i=1; i!=data.size(); ++i) { int key = data[i]; // 暂存第i个元素的值。 int j = i-1; while (j&…