 |
 |
 |
 |
 |
 |
||
 |
 |
 |
 |
 |
| 5 | 1/1 | 返回列表 |
| 查看: 1274 | 回復(fù): 4 | ||
[求助]
求高手幫忙修改一段c++程序
|
|
下面是一段建立K-D樹的c++程序，其中程序中的數(shù)據(jù)要修改為用讀入txt文件中的數(shù)據(jù)來表示，且txt文件中的數(shù)據(jù)為三列，以空格分割。 main.cpp #include "3dtree.h" #include #include void main() { time_t tt = time(NULL); //建立樹 int nodes = 100000; kdTree t(nodes); //存儲數(shù)據(jù) t.store(1.0,1.0,1.0,0); t.store(1.0,2.0,1.0,1); t.store(2.0,4.0,5.0,2); t.store(3.0,1.0,2.0,3); t.store(4.0,6.0,2.0,4); t.store(1.0,5.0,8.0,5); //調(diào)整樹 t.treeBalance(); //尋找最近臨點 nNearestNodes nNN(3); nNN.setDistandIndx(4.3); nNN.setSearchPnt(2.0,4.0,5.0); cout << endl << "searching ..." << endl; t.locateNodes(&nNN,1); if(nNN.found) for(int i = 1; i <= nNN.found; i++) { cout < < "id of the nearest point: " << nNN.index->id < < endl < < "the dis: " < < nNN.dist2 << endl; cout < < "the coordinates of the point:"; cout < < nNN.index->pos[0] < < " " < < nNN.index->pos[1] < < " " < < nNN.index->pos[2] < < endl < < endl; } else cout << "Nothing found!" << endl << endl; cout<<"run time:"< system("pause"  ;} 3dtree.cpp #include "3dtree.h" kdTree::kdTree(const int nodes) { storedKDNodes = 0; maxNumOfNodes = nodes; kdNodes = new kdNode[maxNumOfNodes + 1]; if(!kdNodes) { cout<<"初始化kd樹時內(nèi)存溢出！"< } boundrayMin[0] = boundrayMin[1] = boundrayMin[2] = 1e8f; boundrayMax[0] = boundrayMax[1] = boundrayMax[2] = -1e8f; } kdTree::~kdTree() { delete [] kdNodes; } void kdTree::treeBalance() { if(storedKDNodes > 1) { kdNode **pa1 = new kdNode*[storedKDNodes + 1]; //組織好樹后的指針 kdNode **pa2 = new kdNode*[storedKDNodes + 1]; //原始元素的指針 for(int i =0; i <= storedKDNodes; i++) pa2 = &kdNodes; balancePartition(pa1, pa2, 1, 1, storedKDNodes); delete []pa2; //重新排列樹 //__w64 int d, j = 1; // According to the warning given when 'int ' is used int d, j = 1; //j位置元素已經(jīng)轉(zhuǎn)移走 int foo = 1; //fooNodes存儲的元素的最初位置 kdNode fooNodes = kdNodes[j]; for( int i = 1; i <= storedKDNodes; i++) { d = pa1[j] - kdNodes; pa1[j] = NULL; if(d != foo) kdNodes[j] = kdNodes[d]; else { kdNodes[j] = fooNodes; if(i < storedKDNodes) { for(; foo <= storedKDNodes; foo++) if(NULL != pa1[foo]) break; fooNodes = kdNodes[foo]; j = foo; } continue; } j = d; } delete []pa1; } halfStoredKDNodes = storedKDNodes/2 - 1; } void kdTree::locateNodes(nNearestNodes * const nNN,const int index)const { const kdNode *p = &kdNodes[index]; double dist1; if(index < halfStoredKDNodes) { dist1 = nNN->pos[p->plane] - p->pos[p->plane]; if(0.0 < dist1) { locateNodes(nNN, 2 * index + 1); if(nNN->dist2[0] > dist1 * dist1) locateNodes(nNN, 2 * index); } else { locateNodes(nNN, 2 * index); if(nNN->dist2[0] > dist1 * dist1) locateNodes(nNN, 2 * index + 1); }//if }//if // 計算距離 dist1 = p->pos[0] - nNN->pos[0]; double dist2 = dist1 * dist1; dist1 = p->pos[1] - nNN->pos[1]; dist2 += dist1 * dist1; dist1 = p->pos[2] - nNN->pos[2]; dist2 += dist1 * dist1; if(nNN->dist2[0] > dist2) { if(nNN->found < nNN->max) { nNN->found++; nNN->dist2[nNN->found] = dist2; nNN->index[nNN->found] = p; } else { int j, parent; if(0 == nNN->got_Heap)//建立大頂堆 { double dst2; const kdNode *nd; int halfFound = nNN->found >> 1; for(int k = halfFound; k >= 1; k--) { parent = k; nd = nNN->index[k]; dst2 = nNN->dist2[k]; while(parent <= halfFound) { j = parent + parent; if(j < nNN->found && nNN->dist2[j] < nNN->dist2[j + 1]) j ++; if(dst2 >= nNN->dist2[j]) break; nNN->dist2[parent] = nNN->dist2[j]; nNN->index[parent] = nNN->index[j]; parent = j; }//while nNN->dist2[parent] = dst2; nNN->index[parent] = nd; }//for nNN->got_Heap = 1; }//if //插入 parent = 1; //if() j = 2; while(j <= nNN->found) { if(j < nNN->found && nNN->dist2[j] < nNN->dist2[j + 1]) j++; if(dist2 > nNN->dist2[j]) break; nNN->dist2[parent] = nNN->dist2[j]; nNN->index[parent] = nNN->index[j]; parent = j; j += j; }//while if((parent != 1)||(dist2 < nNN->dist2[parent])) { nNN->index[parent] = p; nNN->dist2[parent] = dist2; } nNN->dist2[0] = nNN->dist2[1];//?????? }//else }//if } #define swap(kdN,a,b){ kdNode* tmp = kdN[a]; kdN[a] = kdN; kdN = tmp;} void kdTree::medianPartition(kdNode** pOrig,const int start,const int end,const int median,const int axis) { int left = start; int right = end; while(right > left) { const TYPE v = pOrig[right]->pos[axis]; int i = left - 1; int j = right; for(; { while(pOrig[++i]->pos[axis] < v); while(pOrig[--j]->pos[axis] > v && j > left); if(i >= j) break; swap(pOrig, i, j); } swap(pOrig, i, right); if(i >= median) right = i - 1; if(i <= median) left = i + 1; } } void kdTree::balancePartition(kdNode** pBalanced,kdNode** pOriginal,const int index,const int start,const int end) { //計算median，這是怎么計算的呢？？？ int median = 1; while((4 * median) <= (end - start + 1)) median += median; //median*=2; if((3 * median) <= (end - start +1)) { median += median; median += start - 1; } else median = end - median + 1; // 尋找分割數(shù)據(jù)的軸 int axis = 2; if((boundrayMax[0] - boundrayMin[0]) > (boundrayMax[1] - boundrayMin[1])&& (boundrayMax[0] - boundrayMin[0]) > (boundrayMax[2] - boundrayMin[2])) axis = 0; else if((boundrayMax[1] - boundrayMin[1]) > (boundrayMax[2] - boundrayMin[2])) axis = 1; // 按median分割節(jié)點 medianPartition(pOriginal, start, end, median, axis); pBalanced[index] = pOriginal[median]; pBalanced[index]->plane = axis; // 迭代平衡左右子樹 if(median > start) { if(start < median - 1) { const float tmp = boundrayMax[axis]; boundrayMax[axis] = pBalanced[index]->pos[axis]; balancePartition(pBalanced, pOriginal, 2 * index, start, median - 1); boundrayMax[axis] = tmp; } else pBalanced[2 * index] = pOriginal[start]; } if(median < end) { if(median + 1 < end) { const float tmp = boundrayMin[axis]; boundrayMin[axis] = pBalanced[index]->pos[axis]; balancePartition(pBalanced, pOriginal, 2 * index + 1, median + 1, end); boundrayMin[axis] = tmp; } else pBalanced[2 * index + 1] = pOriginal[end]; } } [ Last edited by lxb9721 on 2012-7-2 at 20:27 ] |
回復(fù)此樓» 猜你喜歡
一志愿大連理工大學(xué)材料求調(diào)劑
已經(jīng)有5人回復(fù)
-
材料與化工調(diào)劑一志愿大連海事085600，349
已經(jīng)有6人回復(fù)
-
一志愿中海洋320化學(xué)工程與技術(shù)學(xué)碩求調(diào)劑
已經(jīng)有4人回復(fù)
-
材料科學(xué)與工程調(diào)劑
已經(jīng)有11人回復(fù)
-
311求調(diào)劑一志愿合肥工業(yè)大學(xué)
已經(jīng)有4人回復(fù)
-
一志愿食品科學(xué)與工程083200求調(diào)劑
已經(jīng)有4人回復(fù)
-
材料科學(xué)與工程求調(diào)劑
已經(jīng)有10人回復(fù)
-
一志愿北化085600材料專碩275|有文章專利｜求調(diào)劑
已經(jīng)有11人回復(fù)
-
一志愿 南京航空航天大學(xué) ，080500材料科學(xué)與工程學(xué)碩
已經(jīng)有4人回復(fù)
-
085600材料與化工調(diào)劑
已經(jīng)有15人回復(fù)
» 本主題相關(guān)價值貼推薦，對您同樣有幫助:
- 求助高手幫忙翻譯一小段英文�。。�
已經(jīng)有1人回復(fù)
- 請求高手幫忙翻譯一段德文(不是很長，不超過150個詞)
已經(jīng)有9人回復(fù)
- 求高手幫忙翻譯一段英文，要通順，不要谷歌翻譯之類的！
已經(jīng)有3人回復(fù)
- 求助圖片修改，高手幫忙
已經(jīng)有4人回復(fù)
- 求高手幫忙改一下英文摘要
已經(jīng)有12人回復(fù)
- 【求助】求將c語言改寫為C++，求教高人啊！
已經(jīng)有6人回復(fù)
- 【求助】高手幫看看這段C++代碼
已經(jīng)有4人回復(fù)
- 【求助】求高手幫忙改寫數(shù)據(jù)實時動態(tài)顯示程序~
已經(jīng)有8人回復(fù)
- 【求助】求c++編一個簡單計算器的源代碼
已經(jīng)有6人回復(fù)
- 【交流】VC++, C#, VB答疑專貼
已經(jīng)有145人回復(fù)
libralibra
至尊木蟲 (著名寫手)
驃騎將軍
- 程序強帖: 40
- 應(yīng)助: 817 (博后)
- 金幣: 12914.1
- 紅花: 64
- 帖子: 2238
- 在線: 287.3小時
- 蟲號: 696514
- 注冊: 2009-02-05
- 專業(yè): 計算機軟件
2樓2012-07-02 20:49:24
c55719747
新蟲 (初入文壇)
- 應(yīng)助: 0 (幼兒園)
- 金幣: 8.5
- 帖子: 8
- 在線: 3.2小時
- 蟲號: 1869363
- 注冊: 2012-06-25
- 專業(yè): 計算機軟件
3樓2012-07-02 21:03:23
★ ★ ★ ★ ★ ★ ★ ★ ★ ★
感謝參與，應(yīng)助指數(shù) +1
lxb9721: 金幣+10, ★★★很有幫助, http://emuch.net/bbs/viewthread.php?tid=4698994 2012-07-05 20:38:46
感謝參與，應(yīng)助指數(shù) +1
lxb9721: 金幣+10, ★★★很有幫助, http://emuch.net/bbs/viewthread.php?tid=4698994 2012-07-05 20:38:46
|
本帖內(nèi)容被屏蔽 |
4樓2012-07-02 21:59:18
菩提色
木蟲 (正式寫手)
- 應(yīng)助: 13 (小學(xué)生)
- 金幣: 1592.9
- 紅花: 1
- 帖子: 581
- 在線: 67.4小時
- 蟲號: 1735005
- 注冊: 2012-04-03
- 性別: GG
- 專業(yè): 自然語言理解與機器翻譯
5樓2012-07-03 20:46:23
相關(guān)版塊跳轉(zhuǎn)
我要訂閱樓主 lxb9721 的主題更新
| 5 | 1/1 | 返回列表 |
| 最具人氣熱帖推薦 [查看全部] | 作者 | 回/看 | 最后發(fā)表 | |
|---|---|---|---|---|
|
[考研] 285求調(diào)劑 +5 | AZMK 2026-03-30 | 8/400 |
|
|---|---|---|---|---|
|
[考研] 求調(diào)劑 +3 | 圖鑒212 2026-03-30 | 3/150 |
|
|
|
[考研] 一志愿：西北大學(xué)，英一數(shù)一408-284分求調(diào)劑 +5 | 12.27 2026-03-27 | 5/250 |
|
|
|
[有機交流] 考研調(diào)劑 +8 | watb 2026-03-26 | 8/400 |
|
|
|
[考研] 0703化學(xué)/290求調(diào)劑/本科經(jīng)歷豐富/工科也可 +13 | 丹青奶蓋 2026-03-26 | 15/750 |
|
|
|
[碩博家園] 求調(diào)劑 有機化學(xué)考研356分 +10 | Nadiums 2026-03-25 | 11/550 |
|
|
|
[考研] 337求調(diào)劑 +6 | 《樹》 2026-03-29 | 6/300 |
|
|
|
[考研] 085404求調(diào)劑，總分309，本科經(jīng)歷較為豐富 +6 | 來財aa 2026-03-25 | 6/300 |
|
|
|
[考研] 294分080500材料科學(xué)與工程求調(diào)劑 +8 | 柳溪邊 2026-03-26 | 8/400 |
|
|
|
[考研] 340求調(diào)劑 +6 | Amber00 2026-03-26 | 6/300 |
|
|
|
[考研] 356求調(diào)劑 +4 | gysy?s?a 2026-03-28 | 4/200 |
|
|
|
[考研] 求調(diào)劑 +4 | 零八# 2026-03-27 | 4/200 |
|
|
|
[考研]
 一志愿 西北大學(xué) 總分282 英語一62 求調(diào)劑
+7
|
18419759900 2026-03-25 | 8/400 |
|
|
|
[考研] 308求調(diào)劑 +7 | 墨墨漠 2026-03-25 | 7/350 |
|
|
|
[考研] 305求調(diào)劑 +5 | 哇盧卡庫 2026-03-26 | 5/250 |
|
|
|
[考研] 298調(diào)劑 +3 | jiyingjie123 2026-03-27 | 3/150 |
|
|
|
[考研] 考研調(diào)劑 +10 | 呼呼？~+123456 2026-03-24 | 10/500 |
|
|
|
[考研] 085601求調(diào)劑總分293英一數(shù)二 +4 | 鋼鐵大炮 2026-03-24 | 4/200 |
|
|
|
[考研] 296求調(diào)劑 +4 | 汪！？！ 2026-03-25 | 7/350 |
|
|
|
[考研] 求調(diào)劑 +3 | 李李不服輸 2026-03-25 | 3/150 |
|