第二题，在线等，多谢达人，7天激骚感谢。考试遇到困难
- sunjianxi设字符a,b,c,d,e,f,g,h的使用频度分别为8,5,16,15,32,5,9,10.求哈夫曼编码和哈夫曼树，计算带权路径长度
本帖最后由 sunjianxi 于 2010-5-29 13:57 通过手机版编辑 - Eurydice数据结构啊
可惜全忘了 - sunjianxi第三题，请给出一个同时中找n个元素最大元素与最小元素的算法，n为偶数，你的算法多快给出选他的理由。
- mirokuneal100
/ \
37 63
/ \ / \
20 \ 31 e
/ \ \ / \
10 h 17 c d
/ \ / \
b f a g
a: 010
b: 0000
c: 100
d: 101
e: 11
f: 0001
g: 011
h: 001
带权长度：(8*3 + 5*4 + 16 *3 + 15 * 3+ 32*2 + 5* 4+ 9*3 + 10 * 3)/100 = 2.78
[本帖最后由 mirokuneal 于 2010-5-29 14:25 编辑] - sunjianxi还有一题。
- MASK123posted by wap
5楼你是神,以后我机考三级也上来找TG神人帮忙 - mirokuneal给个最简单的算法
设数组a存放这n个数复制内容到剪贴板复杂度为 O(n)代码:
[本帖最后由 mirokuneal 于 2010-5-29 16:27 编辑] - 7膜拜牛人
- mirokunealMB红黑树老子全忘了
等等我去查查去 - mirokunealMB我服了，LZ你要把for 里面的a统统写成 a左方括号i右方括号
- mirokuneala.无相图在这儿，不知道你能看清不
[本帖最后由 mirokuneal 于 2010-5-29 15:46 编辑] - MysterioJr太牛了。。。
现在考试增牛B。 - mirokunealb. 最小生成树
[本帖最后由 mirokuneal 于 2010-5-29 15:47 编辑] - mirokunealb Prim算法（摘自百度百科）
设图G =（V，E），其生成树的顶点集合为U。 ①、把v0放入U。 ②、在所有u∈U，v∈V-U的边(u，v)∈E中找一条最小权值的边，加入生成树。 ③、把②找到的边的v加入U集合。如果U集合已有n个元素，则结束，否则继续执行②。 其算法的时间复杂度为O(n^2)
[本帖最后由 mirokuneal 于 2010-5-29 15:48 编辑] - mirokuneald, Prim编程：
c++:复制内容到剪贴板代码:
#include <stdlib.h>
#include <vector>
using namespace std;
/*
*
*/
struct mstNode{
int i;
int j;
int weight;
};
int findNextVertex(const vector<int> & IN, const int ** v, vector<int> & OUT, vector<struct mstNode> & MST){
int min = 9999; //assume 9999 is the infinite
int nextVertex = -1;
int fromVertex = -1;
int ereasepos = -1;
for(size_t i = 0; i < IN.size(); i++){
for(size_t j = 0; j < OUT.size(); j++){
if(min > v[IN[i]][OUT[j]]){
min = v[IN[i]][OUT[j]];
nextVertex = OUT[j];
fromVertex = IN[i];
ereasepos = j;
}
}
}
struct mstNode temp;
temp.i = fromVertex;
temp.j = nextVertex;
temp.weight = v[temp.i][temp.j];
MST.push_back(temp);
OUT.erase(OUT.begin() + ereasepos); //erease the vertex;
return nextVertex;
}
void MST(int N, const int ** v){
vector<int> IN;
vector<int> OUT;
vector<struct mstNode> MST;
IN.push_back(0);
for(int i = 1; i < N; i++)
OUT.push_back(i);
while(OUT.size() > 0){
int nextVertex = findNextVertex(IN, v, OUT, MST);
IN.push_back(nextVertex);
}
//MST is the minimum spanning tree;
} - mirokunealLZ你是不是已经考试作弊被抓了:D
- mirokunealPRIM算法正确性可以这样写：
假设有另一种算法B给出最小生成树 MSTB， 是的MSTB的所有权重小于MST（PRIM算法的最小生成树）
同时，由于PRIM算法总是选择最小权重的节点加入集合，所以，对于加入第k个节点的权重， MST(k) <= MSTB(k)， k = 1, 2, 3 ... n
那么MST的总权重<= MSTB的总权重， 与假设矛盾，所以不存在这样的算法B
所以Prim算法最优
PRIM算法复杂度为O(n^2) ， 分析忘了。。。
[本帖最后由 mirokuneal 于 2010-5-29 15:27 编辑] - mirokuneal我看了看，红黑树插入删除有点儿复杂啊，lz你放弃吧
你们考试还真不简单 - taxijyl计算机专业的掩面飘过
MB的数据结构，看都看不懂 - mirokuneal他们的考试很难。。
竟然考红黑树，我看着百度，维基都要想半天。。。 - mirokuneal红黑树那道终于写出来了
LZ我知道已经晚了，你不是考完了就是被抓作弊了
再加上我上传空间用完了，红黑树那道题就不发了，或者明天补上吧，LZ别忘了祭扫，睡觉去了，困死。。。 - LoftyBoy兰州被抓了吧
- 农农楼主杯具了
- sowo数据结构这东西全忘了
- 半熟英雄数据结构杯具啊。
- sunjianxi我勒个去，朋友我欠你一个人情，在你的帮助下，顺利过关。没被抓，开卷的，老师一般不管。
- sunjianxi虽然考完，但是依旧谢谢你这种态度和精神。激骚不会忘：）
- mirokuneal恭喜恭喜
怪不得，这题闭卷真有点儿难。没事儿，我就当复习一下数据结构，你给我加点儿鸡骚就行了 - cgbox2006
这这。。。。。。TGFC还能帮你考试。。。针牛逼 - blood我他妈的彻底喷了
- ofanjx发现全忘，真不知道当年怎么过的。。。
- 农农将来考建造师的时候我考虑是不是也来tg求助下:D
- forester麻痹，以后考试我也来这找答案。。