acm数据结构总结

《acm数据结构总结》由会员分享，可在线阅读，更多相关《acm数据结构总结（21页珍藏版）》请在装配图网上搜索。

1、Pku acm 3253 Fence Repair 数据结构题目总结(一) -哈夫曼数这是一个哈夫曼数的简单例子，算法很简单，但提交了很多次才ac，但每一个版本都有很多收获。1.利用Java的集合类以及排序的方法，简单的实现其中的排序，将所有的num添加到集合中，然后排序，提取第1.2个元素，然后相加，删除这两个元素，添加这两个元素的和，然后排序，直到集合的元素个数给1.另外，在该程序中使用了jdk1.5支持的输入，大大简化了输入：Scanner cin = new Scanner(System.in);int count = cin.nextInt();核心的代码如下：Collections

2、.sort(array);int sum=0,a,b;while(array.size()!=1)a = array.get(0);b = array.get(1);array.add(a+b);array.remove(0);array.remove(1);/注意这里不是1，因为删除一个后集合原来的第1个元素变为了第0个元素sum += a+b;Collections.sort(array);System.out.println(sum);但是这个实现虽然简单，但超时，运行需要2s多，而题目要求1s2.为了避免排序，采用空间换时间的策略.想法是这样的：建立一个数组length，该数组的第i个

3、元素表示：集合中有该元素的个数，然后从小到大选出最小的a和b，将lengtha-,lengthb-,lengtha+b+,直到数组中没有非零元素.核心代码如下： scanf(%d,&n); for(i=1;i=n;i+) scanf(%d,&temp); lengthtemp+; for(i=1;in;i+) while(!lengthj) j+; a=j; lengthj-; while(!lengthj) j+; b=j; lengthj-; lengtha+b+; sum += a+b; 结果运行中错误，原因是数组开的不够大，题目要求有20000个数字，每个数字最大为50000，如果要满

4、足题目要求length长度为50000*20000，无法开如此大的数组.3.由于数组中有大量的插入和删除的操作，准备采用链表存储，输入的结果是一个由小到大排列的链表，然后删除前两个数字，插入两个数字的和，按顺序插入到链表中.核心代码如下：但是依然超时.for(i=1;idata); p_head=head;/插入前链表为空 if(head-next=NULL) p_head-next=p_insert;p_insert-next=NULL; else /查找该插入的地方 while(p_head-datadata&p_head-next!=NULL) p_temp=p_head; p_head

5、=p_head-next; /不是插入到链表结尾 if(p_head-data=p_insert-data) p_temp-next=p_insert; p_insert-next=p_head; /插入到链表结尾 else p_head-next=p_insert; p_insert-next=NULL; /依此删除前两个数字，并插入两个数字的和 for(i=1;inext; struct LNode* b=head-next-next; struct LNode* c=(struct LNode*)malloc(sizeof(struct LNode); sum+=a-data+b-dat

6、a; c-data=a-data+b-data; head-next=b-next; free(a); free(b); p_head=head; /查找该插入的地方 while(p_head-datadata&p_head-next!=NULL) p_temp=p_head; p_head=p_head-next; /不是插入到链表结尾 if(p_head-data=c-data) p_temp-next=c; c-next=p_head; /插入到链表结尾 else p_head-next=c; c-next=NULL; printf(%dn,sum);4.利用qsort利用数组实现.vo

7、id qsort( void *base, size_t num, size_t width, int (_cdecl *compare )输入后排序,然后插入两个数字的和，按顺序插入到数组中.核心代码如下:插入时的排序语句可以用qsort(array,n,sizeof(int),comp);代替，但效率一定会低，因为所有元素排序效率会很低，因为只有一个元素是没有排序的终于ac了!带有详细注释的代码可以从 for(i=0;in;i+) scanf(%d,&arrayi); /对原始数列排序 qsort(array,n,sizeof(int),comp); /插入两个元素的和 for(i=1;i

8、n;i+) arrayi+=arrayi-1; sum+=arrayi;temp=arrayi; for(j=i+1;jarrayj) arrayj-1=arrayj; else break; arrayj-1=temp; printf(%I64dn,sum);Pku acm 1861 NetWork 数据结构题目总结(二) -最小生成树：prim算法&Kruskal算法典型的最小生成树算法，题目给出图的顶点以及所有边的权值要求输出最小生成树对应的边，我分别用prim算法和Kruskal算法实现，结果prim算法47ms，4364K ，Kruskal算法204ms，4148K，下面分别详细讲述

9、：对于图，其生成树中的边也带权，将生成树各边的权值总和称为生成树的权，并将权值最小的生成树称为最小生成树（Minimun Spanning Tree），简称为MST。有两种非常典型的算法：Prim算法和kruskal算法，这两种算法都采用了贪心策略。1. prim算法： prim算法的基本思想是：(1) 在图G=(V,E)（V表示顶点，E表示边）中，从集合V中任取一个顶点（例如取顶点v0）放入集合U中，这时U=v0，集合T(E)为空。(2) 从v0出发寻找与U中顶点相邻（另一顶点在V中）权值最小的边的另一顶点v1，并使v1加入U。即U=v0,v1，同时将该边加入集合T(E)中。(3) 重复(2

10、)，直到U = V为止。这时T(E)中有n-1条边，T=(U,T(E)就是一棵最小生成树。在本例中，数组origin存放原始数据，max_distance存放矩阵中的最大值，result存放最小生成树的最大边，opt存放节点和最小生成树之间的最小距离,linei存放节点i和生成树连接的另一节点，flag判断是否已经加入到最小生成树中，首先将1号顶点加入最小生成树中，flag1为true，其他为false，opti的值为origin1i的值 ，linei全为1 ，然后选择不在最小生成树中的最小边i，然后加入到最小生成树中，另外更新opti,flagi,linei,如此反复，直到取到v-1条边为止

11、。带有详细注释的代码可以从2. 并查集+Kruskal算法：并查集最经典的应用其实就是Kruskal算法，在算法导论21章：用于不相交的集合有详细讲述。这里使用了路径压缩，按秩合并的思想，详见算法导论。Kruskal算法每次选择n-1条边，所使用的贪婪准则是：从剩下的边中选择一条不会产生环路的具有最小耗费的边加入已选择的边的集合中。注意到所选取的边若产生环路则不可能形成一棵生成树。Kruskal算法分e步，其中e是图中边的数目。按耗费递增的顺序来考虑这e条边，每次考虑一条边。当考虑某条边时，若将其加入到已选边的集合中会出现环路，则将其抛弃，否则，将它选入。在本例中，flagi存放第i条边是否还

12、有必要考虑，如果该边会产生回路或者已经在最小生成树中就不考虑了，start,end,weight分别存放图中边的起点，终点和权值，对每个顶点初始化，每个顶点单独成为一个集合，然后将所有边按权值排序，取最小的边，该边如果不在同一个集合中，合并，并将结果存入start_s&start_e中，并记录当前加入最小生成树的最大边权值，边数count+，并置该边为不考虑。值得一提的是，该实现中对边按权值的排序采用了计数排序，其时间复杂度为O(n)。带有详细注释的代码可以从Pku acm 2485 Highways数据结构题目总结(三) -最小生成树：prim算法典型的最小生成树算法，题目给出图的邻接矩阵，

13、要求输出最小生成树对应的权值和，本例用prim算法实现。对于图，其生成树中的边也带权，将生成树各边的权值总和称为生成树的权，并将权值最小的生成树称为最小生成树（Minimun Spanning Tree），简称为MST。有两种非常典型的算法：Prim算法和kruskal算法，这两种算法都采用了贪心策略。prim算法的基本思想是：(1) 在图G=(V,E)（V表示顶点，E表示边）中，从集合V中任取一个顶点（例如取顶点v0）放入集合U中，这时U=v0，集合T(E)为空。(2) 从v0出发寻找与U中顶点相邻（另一顶点在V中）权值最小的边的另一顶点v1，并使v1加入U。即U=v0,v1，同时将该边加入

14、集合T(E)中。(3) 重复(2)，直到U = V为止。这时T(E)中有n-1条边，T=(U,T(E)就是一棵最小生成树。在本例中，数组origin存放原始数据，max_distance存放矩阵中的最大值，result存放最小生成树的最大边，opt存放节点和最小生成树之间的最小距离, flag判断是否已经加入到最小生成树中，首先将1号顶点加入最小生成树中，flag1为true，其他为false，opti的值为origin1i的值，然后选择不在最小生成树中的最小边i，然后加入到最小生成树中，另外更新opti,flagi。如此反复，直到取到v-1条边为止。带有详细注释的代码可以从Pku acm 1

15、258 Agri-Net数据结构题目总结(四) -最小生成树：prim算法典型的最小生成树算法，题目给出图的邻接矩阵，要求输出最小生成树对应的权值和，本例用prim算法实现。对于图，其生成树中的边也带权，将生成树各边的权值总和称为生成树的权，并将权值最小的生成树称为最小生成树（Minimun Spanning Tree），简称为MST。有两种非常典型的算法：Prim算法和kruskal算法，这两种算法都采用了贪心策略。Prim算法的基本思想是：(1) 在图G=(V,E)（V表示顶点，E表示边）中，从集合V中任取一个顶点（例如取顶点v0）放入集合U中，这时U=v0，集合T(E)为空。(2) 从v

16、0出发寻找与U中顶点相邻（另一顶点在V中）权值最小的边的另一顶点v1，并使v1加入U。即U=v0,v1，同时将该边加入集合T(E)中。(3) 重复(2)，直到U = V为止。这时T(E)中有n-1条边，T=(U,T(E)就是一棵最小生成树。在本例中，数组origin存放原始数据，max_distance存放矩阵中的最大值，sum存放最小生成树的sum，opt存放节点和最小生成树之间的最小距离,flag判断是否已经加入到最小生成树中，首先将1号顶点加入最小生成树中，flag1为true，其他为false，opti的值为origin1i的值，然后选择不在最小生成树中的最小边i，然后加入到最小生成树

17、中，另外更新opti,flagi。如此反复，直到取到v-1条边为止。带有详细注释的代码可以从Pku acm 3278 Catch That Cow数据结构题目总结(五) -树的BFS题目给出两个数a b，求由a经过加一，减一或乘二经过最小的步数n到b，输出n，例如：对于a=5，b=17 有：5-10-9-18-17, n=4.想到用数的BFS(广度优先遍历)，建立一颗根为5的树，不断BFS，当出现17时结束即可。由于题目要求的数据很大，而且BFS过程中会出现很多重复的元素，所以过程中要不断剪枝，才能不至于超时。在该实现中，建立了先进先出的队列来存储新生成的节点，每一个node包含一个值和一个深

18、度depth，对节点的剪枝首先采取了一下方式：将出现过的节点放在一个ArrayList中，然后每一个node入队时判断是不是已经在ArrayList中了，如果在了就不加入了，当出现大量的需要剪枝的元素时，这种方式效率会很低，因为每次都要遍历存放处理过的元素的ArrayList，还是用惯用的“空间换时间”的方法，建立bool型flagi存放i是否已经在队列中出现过，如果出现过就剪枝，这样，每次判断元素是否出现过时间复杂度就由O(n)降到O(1)。另外：如果输入一大一小的数，有题意结果即为两数之差，这样的判断会很大程度上提高效率，时间由5391ms降到4141ms。带有详细注释的代码可以从Pku

19、acm 2253 Frogger数据结构题目总结(六)单源最短路径：Dijkstra算法单源最短路径问题和Dijkstra算法：单源最短路径问题描述：给定一个带权有向图 G=(V,E) ，其中每条边的权是一个非负实数。另外，还给定 V 中的一个项点，称为源。现在我们要计算从源到所有其他各项点的最短路径长度。这里的长度是指路上各边权之和。这个问题通常称为单源最短路径问题。Dijkstra算法基本思想：Dijkstra算法是解单源最短路径问题的一个贪心算法。其基本思想是，设置一个基点集合 S ，并不断地作贪心选择来扩充这个集合。一个项点属于集合 S 当且仅当从源到该项点的最短路径长度已知。初始时，

20、S中仅含有源。设 u 是 G 的某一个项点，我们把从源到 u 且中间只有经过 S 中项点的路称为从源到 u 的特殊路径，并且数组 dist 来记录当前每个项点所对应的最短特殊路径长度。Dijkstra算法每次从 V-S 中取出具有最短特殊路径长度的项点 u ，将 u 添加到 S 中，同时对数组 dist 作必要的修改。本题给出直角坐标系中的几个点求一个点到另一个点(可以借助其它点)的走法中最大跳最小的走法，输出最大的跳。可以用Dijkstra算法解决，只是贪心准则是在每一跳中取最近的一跳，直到跳到终点节点。将第0个点作为起点，第1个点作为终点，不断根据贪心准则扩大起点的集合，直到扩展到终点。从

21、代码上可以看出Dijkstra算法和prim算法是及其相似的，深刻理解了算法导论的说法。带有详细注释的代码可以从Pku acm 1062 昂贵的聘礼 数据结构题目总结(七)单源最短路径：Dijkstra算法题目：基本思想：增加一个起点S, 若某物品Ai的价格为Pi, 添一条权值为Pi的边S-Ai若物品Aj可以用Ai加优惠价Qi换得,加权值为Qi的边Aj-Ai，对于题目中提到的等级限制也是该题的一个难点，假如酋长的rank=10，等级限制M=5，那么可以参与交易的等级有以下6种可能：5-10 6-11 7-12 8-13 9-14 10-15用一个循环就是分别处理这M+1种可能即可。假如正在处理

22、8-13的循环，就遍历每一个物品的主人，如果其rank不在8-13中就将该主人的所有交换都设为无穷大，循环每一个可能求出S到A1的单源最短路径，取所有循环的最小值即是要求的结果。最短路(dijkstra)的时间复杂度是O(n2),枚举M+1次,总的时间复杂度是O(n2*M).带有详细注释的代码可以从Pku acm 1125 Stockbroker Grapevine 数据结构题目总结(八)- 弗洛伊德(floyd)算法有向图中每一对顶点间的最短路径问题，典型的弗洛伊德算法。问题描述：已知一个含有n个顶点的各边权值均大于0的带权有向图，对每对顶点vi！=vj，要求求出每一对顶点之间的最短路径和最

23、短路径长度。 解决方案：弗洛伊德(floyd)算法321对于这样一个例子： 4 2 2 5 2 6A0ij=costij:A0123A1123104510452206220min(6,2+5)322032min(2,2+4)0A2123A3123104min(5,4+6)10min(4,5+2)522062min(2,6+2)063min(2,2+2)203220核心的c代码如下：for(int k=1;k=n;k+) /生成A0,A1,A2.的循环for(int i=1;i=n;i+) /行for(int j=1;j=n;j+) /列/如果是i=k|j=k|i=j就保持不变，否则取最小值ar

24、rayij=(i=k|j=k|i=j)?arrayij:(arrayijranky) py=x; else if(rankxranky) py=x; else if(rankxranky) px=y; else if(rankx=ranky) px=y; ranky+; 本题大意：给出n个bug，m个关系，例如n=3,m=31 22 31 3表示1和2不在一个集合，2和3不在一个集合，1和3不在一个集合，问是否矛盾。具体实现：opp存储该集合中元素的对方，首先对每个成员初始化，然后对每组关系a和b，合并a和b的对方，最后判断矛盾否即可。带有详细注释的代码可以在 by 苏强 neuq & jlu 做最优秀的自己2008-3-17