算法与设计总结

1、1、算法（algorithm)就是定义良好的计算过程，取一个或一组值作为输入，并产生一个或一组输出。也就是，算法是一系列的计算步骤，用来将输入数据转换成输出结果。2、插入排序的基本思想：将待排序表看作是左右两部分；其中左边为有序区，右边为无序区；整个排序过程就是将右边无序区中的元素逐个插入到左边的有序区中，以构成新的有序区。伪代码如下：void insert_sort(elementtype An+1) for (i=2; i<=n; i+) / i表示待插入元素的下标 temp=Ai; / 临时保存待插入元素，以腾出Ai的空间 j=i-1; /j指示当前空位置的前一个元素 while

2、(j>=1 && Aj.key>temp.key ) /搜索插入位置并腾空位 Aj+1 = Aj; j=j-1; Aj+1=temp; /插入元素 3、分治法在每一层递归上都有3个步骤：分解（Devide)：将原问题分解成一系列子问题；求解（Conquer) : 递归地求解各子问题，若子问题“足够小”（递归出口），则直接求解。合并（combine) ：合并子问题的解，以求解原问题的解。归并排序（merge sort）的操作：分解：分解数组为两个n/2规模的数组；求解：对两个子序列分别采用归并排序进行求解；合并：合并两个已排序子序列，得到排序结果。为了合并，引入一个函

3、数Merge(A,p,q,r), 其功能是：合并已排序子序列Ap.q和Aq+1.r，得到已排序子序列Ap.r。 merge(A,p,q,r) len1= q-p+1; len2=r-q; for(i=1; i<=len1; i+) Li=Ap+i-1; /复制到另外的数组中 for(i=1; i<=len2; i+) Ri=Aq+i; i1=1; i2=1; Llen1+1=; Rlen2+1=; /设置监视哨(先排完的数组先到无穷大) for (k=p; k<=r; k+) if (Li1<=Ri2) Ak=Li1; i1+; else Ak=Li2; i2+;时间性

4、能：分解：不费时间，求解：2T（n/2），合并：O(n) è2T（n/2）+ O(n) =>整个排序：O(nlogn)4、递归式代换法 求解的两个步骤：（1）猜测解的形式（2）用数学归纳法找出使得解真正有效的常数。递归树方法主方法 给出求解如下形式的递归式方法：T(n)=aT(n/b)+f(n)，其中，a>=1, b>1是常数，f(n)是渐近正的函数。描述了将规模为n的问题划分为a个子问题的算法的运行时间，每个子问题的规模为n/b。每个子问题的求解时间为T(n/b)，划分和合并的时间为f(n).5、堆排序：每一结点均不大于(或不小于）其左、右孩子结点的值。若序列(a

5、1,a2,an)是堆，则堆顶(完全二叉树的根)必为序列中的最小或最大值。将根最大的堆称为大根堆，根最小的堆称为小根堆。（1）如果初始序列是堆，则可通过反复执行如下操作而最终得到一个有序序列：筛选过程即输出根：即将根（第一个元素）与当前子序列中的最后一个元素交换。（2）调整堆：将输出根之后的子序列调整为堆。如果初始序列不是堆，则首先要将其先建成堆，然后再按（1）的方式来实现。void sift(elementtype A , int k,int m) /大根堆的堆排序/对数组中下标为1n中的元素中的序号不大于m的以k为根的子序列调整 finished=FALSE； i=k; j=2*k; /i指

6、示空位，j先指向左孩子结点 while (j<=m && !finished ) if (j<m && Aj.key<Aj+1.key) j=j+1; /让j指向左右孩子中的最大者 if (Ai.key>=Aj.key) finished=TRUE; /根最大 else temp= Ai; Ai=Aj; Aj=temp; /大的孩子结点值上移 i=j; j=2*j; /继续往下筛选 /算法时间复杂度O(nlog2 n)void heap_sort(elementtype A ,int n) for (i=n/2; i>=1, i-)

7、 sift(A,i,n); /建初始堆 for (i=n; i>=2; i-) println(A1); /输出根temp=A1; A1= Ai; Ai = temp; /元素交换 sift(A,1,i-1); /调整子序列为堆 6、快速排序基本思想：分治法将数据表划分为左右两部分，其中：左边的所有元素都小于右边的所有元素；然后，对左右两部分分别进行快速排序。void partition(elementtype An,int s,int t,int *cutpoint)/对数组A中下标为st的子表进行划分 x=As; /保存中间元素，腾出空位 i=s; j=t; while ( i!=j

8、 ) while ( i<j && Aj.key>x.key ) j-; if ( i<j ) Ai=Aj; i=i+1; while ( i<j && Ai.key<x.key ) i+; if ( i<j ) Aj=Ai; j=j-1; Ai = x; *cutpoint=i; void Quick_sort(elementtype An, int s, int t) /对数组A中下标从s到t的元素组成的子表快速排序 if (s<t ) partition(A,s,t,*i); /划分 Quicksort(A,s,*

9、i-1); /对前面子表快速排序 Quicksort(A,*i+1,t); /对后面子表快速排序 每次等分子表，时间复杂度T(n)=2T（n/2）+ O(n) => 整个排序为O(nlogn)7、计数排序对每个元素x, 确定出比x小的元素个数，由此而确定其在数组中的位置。void count_sort(A,B,k) for (i=0;i<=k;i+) Ci=0; /各元素的计数置0； for (i=0;i<length(A); i+) CAi+; / 计数:Ci包含等于i的元素个数 for (i=1;i<=k;i+) Ci=Ci+Ci-1; / Ci包含小于或等于i的元

10、素个数 for (i=length(A)-1; i>=0; i-)/依次将元素放置到B数组中 BCAi=Ai; CAi-; 8、基数排序 桶排序9、栈 队列 链表 二叉树栈 是只能在一端插入和删除元素的线性表。（后进先出，入栈push出栈pop）队列 是只能在一端插入，另一端删除元素的线性表。（先进先出）链 表 在链表中间某位置P插入时，s -> next = p -> next; p -> next = s; 二叉树T ：是n个结点组成的有限集合（n >= 0），n=0时为空二叉树，否则：其中有一个根结点，其余结点可以划分成两个互不相交的子集TL, TR，且TL

11、, TR也分别构成二叉树-左、右子树。10、散列表对给定的关键字key，用一个函数H(key)计算出元素地址，由此而得散列表（Hash表，哈希表），其中函数H(key)称为散列函数，此函数值称为散列地址。当k1k2，但H(k1)=H(k2) ，称这种现象为冲突现象，k1,k2为同义词。构造散列函数的基本方法：直接定址法、除留余数法、平方取中法、折叠法、数值分析法。处理冲突：开放地址法 Hi(k)=(H(k) + di ) % m，i=1,2,q q<=m拉链法（将同义词构成一个链表）再散列法 H(k)H1(k)H2(k) Hi(k)11、二叉查找树二叉查找树是一棵二叉树，或者为空，或者满

12、足以下条件： 1)若左子树不空，则左子树中所有结点的值小于根结点的值； 2)若右子树不空，则右子树中所有结点的值不小于根结点的值； 3)左右子树都为二叉查找树。按照左、中、右的次序遍历，所得到的中序序列是非降序列。二叉排序树的查找 bnode *bstsearch(bnode *T, elementtype x) /查找的非递归算法 p=T; while ( p != NULL ) if ( p -> data = = x ) return p; if ( x < p -> data ) p = p -> lchild; else p = p -> rchild;

13、 return NULL; bnode *bstsearch(bnode *T, elementtype x) /查找的递归算法 if ( T = NULL ) return null; if (T -> data = x ) return T; if (T -> data >x ) return *bstsearch(T->lchild,x); else return *bstsearch(T->rchild,x); void insert(bnode *&T, bnode *s) （二叉查找树的插入算法）/将s所指结点插入到以T为根指针的二叉查找树中

14、if ( T = NULL ) / T 为空时 T =s; / 新结点作为根结点 else if ( s->data < T->data ) insert( T -> lchild, s ); else insert( T -> rchild, s ); void create(bnode *&T) （二叉查找树的构造算法）/ 接受读入数据，从空树开始构造二叉查找树 T=NULL; cin>>x; while (x!=结束符) s=new bnode; s -> data=x; s -> lchild=NULL; s -> r

15、child=NULL; insert(T,s); cin>>x; 二叉查找树的平均查找长度为层数乘以该层节点数的和除以节点总数。12、平衡二叉树平衡二叉树是一棵二叉查找树，或者为空，或者满足以下条件： 1)左右子树高度差的绝对值不大于1； 2)左右子树都是平衡二叉树。平衡因子：左子树的高度减去右子树的高度，在平衡二叉树中，每个结点的平衡因子的值为-1，0或1。判断二叉树是否为平衡二叉树的算法：int DepthTree(BSTreeNode<T> *pbs) if (pbs=NULL) return 0; else int leftLength=DepthTree(pb

16、s->left); int rigthLength=DepthTree(pbs->right); return 1+(leftLength>rigthLength ? leftLength:rigthLength); bool isBalanceTree(BSTreeNode<T> *pbs) if (pbs=NULL) return true; int depthLeft=DepthTree(pbs->left); int depthRight=DepthTree(pbs->right); if (abs(depthLeft-depthRight)&

17、gt;1) return false; else return isBalanceTree(pbs->left) && isBalanceTree(pbs->right); /将每个节点都递归遍历，所有节点深度差都满足才返回true 13、红黑树它是许多“平衡的”查找树中的一种，最坏情况下，基本动态集合的操作时间为O(lgn)。一棵二叉查找树如果满足以下性质，则为一棵红黑树:每个结点或者是红的，或者是黑的。根结点是黑的。每个叶子结点(nil)是黑的。如果一个结点是红的，则它的两个孩子结点都是黑的。对每个结点，从该结点到其后代结点的所有路径上包含相同数目的黑结点。o

18、性质： 一棵有n个内结点的红黑树的高度至多为2lg(n+1).o 通常将结点数为n且高度为O(logn)的树称为平衡树。o 红黑树的平衡性质表明是一类平衡的二叉搜索树，即其渐进形态接近于满二叉搜索树。o 因此，最坏情况下，可用O(logn)的时间完成搜索运算。14、动态规划和分治法类似，是通过组合子问题的解而得到整个问题的解。所不同的是，动态规划法适用于子问题不是独立的情况，也就是各子问题包含公共的子问题。4个基本步骤：（1）描述最优解的解构（2）递归定义最优解的值（3）按照自底向上的方式计算最优解的值（4）由计算出的结果构造一个最优解矩阵连乘积A与B相乘的基本描述（假设能相乘:Ap*q与Bq

19、*r ）void multi(A,B,C) for (i=0; i<row(A); i+) /row表示行 col表示列 for (j=0; j<col(B); j+) Cij=0; for(k=0; k<col(A); k+) Cij=Cij+Aik*Bkj; /计算次数p*q*r1)矩阵连乘积的计算次序问题的最优解包含着其子问题的最优解-称这种性质为最优子结构性质。（可用动态规划求解）2)建立递归关系 3) 确定最优计算次序(穷举)矩阵列数序列 P=p0,p1,p2,pnvoid matrix_chain_order(P) n=len(p)-1;for (i=1; i&l

20、t;=n;i+) mi,i=0;/中心对角线置零for (L=2; L<=n;L+) /需要计算的几条斜对角线for (i=1; i<=n-L+1;i+)/每条对角线长度 j=i+L-1; mi,j=; for (k=i; k<=j-1; k+) q=mi,k+mk+1,j+ pi-1pkpj; if (q<mi,j) mi,j=q; si,j=k; 4) 构造最优解void matrix_chain_multiply(A,s,i,j) / 矩阵相连乘 if(i>j) x=matrix_chain_multiply(A,s,i,si,j); y=matrix_ch

21、ain_multiply(A,s,si,j+1,j); return matrix_multiply(X,Y); else return(Ai);动态规划算法的有效性依赖于两个重要性质：最优子结构性质；子问题重叠性质15、贪心算法逐步达到山顶（获得最优解）活动安排问题void greedy_activity_selector(s,f,A) / f中按照递增次序排列 n=length(e); / 求活动个数 A表示活动s开始时间f结束时间 n=1; last_selected=1; for(i=2; i<=n; i+) if (si>=flast_selected) A=A+i; l

22、ast_selected=i; 贪心算法与动态规划算法的主要区别：动态规划法中，每一步所作的选择往往依赖于相关子问题的解，因而只有在解出相关子问题后才能作出选择。贪心算法中，凭着当前的状态作出当前看来是最好的选择，即局部最优，然后再去求解给出这一选择之后所产生的相应的子问题。它们求解方向也有差异：自底向上；自顶向下；共同点：都具有最优子结构性质0-1背包问题void bag(int S1, int num, int k) if (k<=n) if (S1+wk=S) Bnum+1=k; print(B,num+1); /输出求解结果 else if (S1+wk<S) Bnum+1

23、=k; print(B,num+1);bag(S1+wk,num+1, k+1); /放入第k个物品再试探 else bag(S1,num,k+1); /不放第k个物品的试探 哈夫曼编码哈夫曼树的定义：给定一组数值w1，w2,wn，作为叶子结点的权值构造一棵二叉树。若二叉树满足WPL= 最小(其中Li为wi对应的叶子结点到根结点的路径长度)，则称此二叉树为最优二叉树，也称哈夫曼树，并称WPL为带权路径长度。哈夫曼树的构造规则：假设有n个权值，则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为 w1、w2、wn (1) 将w1、w2、，wn看成是有n 棵树的森林(每棵树仅有一个结点)； (2)

24、 在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和； (3)从森林中删除选取的两棵树，并将新树加入森林； (4)重复(2)、(3)步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树。编码方式：16、回溯法八皇后问题： Bool Ok(int a; int i, int j) / 检查在(i,j)上是否可以放置棋子 int j1, i1; Bool Ok1; j1=j; i1=i; Ok1=true; / 检查在第i行上是否可以放置 while (j1>1 && Ok1) j1-;Ok1=aj1!=i1;

25、 j1=j; i1=i; / 检查在对角线上是否可以放置 while (j1>1 && i1>1 && Ok1) j1-; i1-;Ok1=aj1!=i1; j1=j; i1=i; / 检查在另一对角线上是否可以放置 while (j1>1 && i1<n && Ok1) j1-; i1+; Ok1=aj1!=i1; return Ok1; void queen(int a; int j, int n) / 从第j列开始逐个试探,准备放置皇后 int i; if (j>n) print(a); / 输

26、出结果 else for (i=1; i<n; i+) if (Ok(a,i,j) / 检查在(i,j)上是否可以放置 aj=i; / 在(i,j)上放置一个棋子 queen(a,j+1,n); / 继续往后试探 17、图图的存储（图结构在计算机中的存储形式）1.邻接矩阵不带权值，假设图中有n个顶点，则采用n×n的矩阵A来表示（0、1表示能否相连）。带权值，网络的表示方法（n×n的矩阵，存储权值）2. 邻接表表示法 将邻接点构成链表 （或用逆邻接链表，表示相反连接关系）存储网络，在邻接表中的每个结点中增加一个存放对应边的权值的字段深度优先搜索遍历（Depth Firs

27、t Search)firstadj(G,v) ：返回v的第一个邻接点（号），或0（不存在时）。nextadj(G,v,w)：返回v的邻接点序列中处于邻接点w之后的邻接点（号），或0（不存在时）。void dfs_travel (graph G) /整个图的遍历 for (i=1; i<=n; i+) visitedi=FALSE; for (i=1; i<=n; i+) if(!visitedi) dfs(i); int numofGC(graph G) /计算图的连通分量 int i; int k=0; / k用于连通分量的计数 for (i=1; i<=n; i+) vi

28、sitedi=FALSE; for (i=1; i<=n; i+) if (visitedi=FALSE) k+; dfs(G,i); /用k来累计连通分量个数 return k ;广度优先搜索遍历（Breadth_first search)void bfs(int v0) /广度遍历基本算法 Queue Q; /定义队列Q（先进先出） visite(v0); visitedv0=TRUE; Q.append(v0); /append()入队 while(!Q.Empty() v=Q.Serve(); /serve()出队 w=firstadj(G,v); while(w!=0) if(!visitew) visite(w); visitedw=TRUE; Q.append(w); w=nextadj(G,v,w); void bfs_travel (graph G) /遍历整个图的算法 for(i=1;i<=n;