分治算法：简单的概括就是将暂时不能解决的大问题分成许多入门的子问题，
如果子问题还是不能解决的话则继续分成子问题，直到子问题小到
可以解决为止的规模，原问题即是子问题的合并。
PartOne:
用分治法打印数组a[L,……,R].分析:一个循环就可以了，但是分治算法来解决该怎么做呢？如果待打印的序列长度为 1，则可以直接打印;如果待打印的序列长度为 N，则可将其划分为两部分;第一部分是 1, 后N – 1 是另一个划分，以此类推，直到数组长度是 1.
void print(int a[], int L, int R) {if(L > R)return;else if(L == R){cout<<"a[L]"<<" ";}else{cout<<a[L]<<" ";print(a, L + 1, R);} }
PartTwo:假设存在一个函数divid(),可以将一个数组a[L,…,R]分成两部分，
元素a[L]为分界线，小于a[L]的元素在左边，大于啊a[L]的元素在右边函数声明如下：int divid(int a[], int L, int R);试用分治法，对数组a[L,…R]中元素进行快速排序分析:如果长度小于1，则默认有序， 如果序列长度大于1则用divid()函数
将其划分为3部分，左边是小于a[L]的部分，中间是a[L], 右边是大于
a[L]的部分。a[L]已经有序，则只需要对其左右两部分进行分支处理。
void Qsort() {int mid;if(L >= R)return;else{mid = divid(a, L, R);Qsort(a, L, mid);Qsort(a, mid + 1, R);} }PartThree;一颗二叉树存储在二叉链表中，用分治法打印所有的结点值，
根结点由 p 所指。分析：当树为空的时候，什么都不用做，问题直接解决。当树中结点树大于等于 1 的时候，把整棵树划分为根， 左子树，
右子树三部分。根结点直接打印，对左子树继续分治处理，
对右子树继续分治处理，最终打印整棵二叉树。
void printTree(BTNode *p) {if(p == NULL)return;else{cout<<p->data<<" ";printTree(p->lchild);printTree(p->rchild);} } PartFour：一个连通图G用邻接表存储，用分治法打印图中的所有定顶点值，假设从顶点 v 开始打印，则可将整个图分成 n 部分，接着和上一个例子很像可以把图分成，第一条边所达到的子图，第二条边所达到的子图……..第N条边达到的子图。V可以直接打印，然后对各个子图分别分治处理。为了防止出现回路现象，则可以设置一个数组visited[]标记已经走过的路。（深度优先搜索的分治解释）
void printGraph(AGraph *G, int v){ArcNode *p;visited[v] = 1;cout<<v<<" ";p = G->adjlist[v].firstarc;while(p != NULL){if(visited[p->adjvex] == 0){printGraph(G, p->adjvex);}p = p->nextarc;}} PartFive:已知二叉树的先序遍历序列和中序遍历序列，分别存储在a[L1,….,R1],
b[L2,…R2];两个数组中，用分治算法由这两个序列建立一颗二叉树，
存储在二叉链表存储的结构中。分析：如果为空序列，则什么也不用做。如果是长度大于 1，，则a[L1]位二叉树
的根结点，在b[]中找到a[L]，假设下标为k,则b[L2,…..k – 1]是其左子树上
的所有结点，b[k + 1, …. R2]是其右子树上的所有结点反应在 a[ ]中即
a[L1 + 1,… L1 + k – L2]与b[L2, …. , k-1]继续进行分治处理。最终可将树创建完毕。
BTNode* Create(int a[], int b[], int L1, int R1, int L2, int R2) {int k;if(L1 > R1)return NULL;else{s = (BTNode*)malloc(sizeof(BTNode));s->data = a[L1];for(k = L2; k < R2; ++k){if(a[L1] == b[K]){break;}}s->lchild = Create(a, b, L1 + 1, L1 + k – L2, L2, k – 1);s->lchild = Create(a, b, L1 + k – L2 + 1, R1, k + 1, R2);} }
版权声明：本文为博主原创文章，未经博主允许不得转载。
我没啥文化,,来求助大家了. 古代的,现在的. 都行
