文件名称：C C++算法实例.c
文件大小：20KB
文件格式：NONE
更新时间：2012-04-22 03:53:48
数据结构
C C++算法实例.c 一、数论算法 1．求两数的最大公约数 2．求两数的最小公倍数 3．素数的求法 二、图论算法 1．最小生成树 A.Prim算法： B.Kruskal算法：(贪心) 2.最短路径 A.标号法求解单源点最短路径： B.Floyed算法求解所有顶点对之间的最短路径： C. Dijkstra 算法： 3.计算图的传递闭包 4.无向图的连通分量 A.深度优先 B 宽度优先（种子染色法） 5．关键路径 6．拓扑排序 7.回路问题 9．判断图中是否有负权回路 Bellman-ford 算法 10．第n最短路径问题 三、背包问题 1．0-1背包： 每个背包只能使用一次或有限次(可转化为一次)： 2．可重复背包 四、排序算法 A.快速排序： B.插入排序： C.选择排序： D.冒泡排序 E.堆排序： F. 归并排序 G.基数排序 五、高精度计算 1．高精度加法 2．高精度减法 3．高精度乘以低精度 4．高精度乘以高精度 5．高精度除以低精度 6．高精度除以高精度 六、 树的遍历 1．已知前序中序求后序 2．已知中序后序求前序 3．已知前序后序求中序的一种 七 进制转换 1.任意正整数进制间的互化 除n取余 2.实数任意正整数进制间的互化 乘n取整 3.负数进制： 设计一个程序，读入一个十进制数的基数和一个负进制数的基数，并将此十进制数转换为此负 进制下的数：-R∈{-2，-3，-4,....-20} 八 全排列与组合的生成 1.排列的生成：（1..n） 2.组合的生成(1..n中选取k个数的所有方案) 九.查找算法 1.折半查找 2.树形查找 十、贪心 *会议问题 （1） n个活动每个活动有一个开始时间和一个结束时间，任一时刻仅一项活动进行，求满足活动数最多的情况。 解：按每项活动的结束时间进行排序，排在前面的优先满足。 （2）会议室空闲时间最少。 （3）每个客户有一个愿付的租金，求最大利润。 （4）共R间会议室，第i个客户需使用i间会议室，费用相同，求最大利润。 十一、回溯法框架 1. n皇后问题 2.Hanoi Tower 汉诺塔 十二、DFS框架 NOIP2001 数的划分 十三、BFS框架 IOI94 房间问题 十五、数据结构相关算法 1．链表的定位函数 2．单链表的插入操作 3．单链表的删除操作 4．双链表的插入操作（插入新结点q） 5．双链表的删除操作