应《网络安全法》要求，自2017年10月1日起，未进行实名认证将不得使用互联网跟帖服务。为保障您的帐号能够正常使用，请尽快对帐号进行手机号验证，感谢您的理解与支持！

24小时热门版块排行榜    

小木虫论坛-学术科研互动平台 » 计算模拟区 » 程序语言 » C/C++ » 求高手帮忙修改一段c++程序
北京石油化工学院2026年研究生招生接收调剂公告
51/1返回列表
查看: 1285  |  回复: 4
只看楼主 @他人 存档 新回复提醒 (忽略) 收藏    在APP中查看

lxb9721

新虫 (正式写手)

[求助] 求高手帮忙修改一段c++程序

下面是一段建立K-D树的c++程序，其中程序中的数据要修改为用读入txt文件中的数据来表示，且txt文件中的数据为三列，以空格分割。
main.cpp

#include "3dtree.h"

#include
#include

void main()
{
        time_t tt = time(NULL);

        //建立树
        int nodes = 100000;
        kdTree t(nodes);

        //存储数据
        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);
        //调整树
        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树时内存溢出！"<                 exit(-1);
        }

        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位置元素已经转移走
                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;

        // 寻找分割数据的轴
        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分割节点
        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 ]
回复此楼

» 猜你喜欢

» 本主题相关价值贴推荐，对您同样有帮助:
1楼 2012-07-02 20:24:38
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

libralibra

至尊木虫 (著名写手)

骠骑将军

【答案】应助回帖

感谢参与，应助指数 +1
不用代码block的结果就是别人看不懂
赞一下 回复此楼
matlab/VB/python/c++/Java写程序请发QQ邮件:790404545@qq.com
2楼2012-07-02 20:49:24
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

c55719747

新虫 (初入文坛)
引用回帖:
2楼: Originally posted by libralibra at 2012-07-02 20:49:24
不用代码block的结果就是别人看不懂

太长了，应该选择有问题的一段让人修改
赞一下 回复此楼
3楼2012-07-02 21:03:23
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

wangybcn

禁虫 (正式写手)
★ ★ ★ ★ ★ ★ ★ ★ ★ ★
感谢参与，应助指数 +1
lxb9721: 金币+10, ★★★很有帮助, http://emuch.net/bbs/viewthread.php?tid=4698994 2012-07-05 20:38:46
本帖内容被屏蔽
4楼2012-07-02 21:59:18
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

菩提色

木虫 (正式写手)

【答案】应助回帖

★ ★ ★ ★ ★
感谢参与，应助指数 +1
lxb9721: 金币+5, ★★★很有帮助, http://emuch.net/bbs/viewthread.php?tid=4698994 2012-07-05 20:38:58
太长了，直接把源文件搞上来，有空给你看看
赞一下(1人) 回复此楼
天行健，君子以自强不息
5楼2012-07-03 20:46:23
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖
相关版块跳转 我要订阅楼主 lxb9721 的主题更新
51/1返回列表
普通表情 龙 兔 虎 猫
最具人气热帖推荐 [查看全部] 作者 回/看 最后发表
[考研] 材料调剂 +14 壹贰贰亿 2026-04-04 14/700 2026-04-05 23:31 by 来看流星雨10
[考研] 320分人工智能调剂 +8 振—TZ 2026-04-03 8/400 2026-04-05 22:33 by 范式思维
[考研] 277求调剂 数一104分 +6 瓶子PZ 2026-04-05 6/300 2026-04-05 20:38 by 啵啵啵0119
[考研] 复试调剂 +8 春日来信- 2026-04-03 8/400 2026-04-05 18:58 by 蓝云思雨
[考研] 329求调剂 +17 miaodesi 2026-04-02 20/1000 2026-04-05 18:33 by 蓝云思雨
[考研] 一志愿南航，数一英一学硕317求调剂！！ +5 Acaciad 2026-04-04 5/250 2026-04-05 12:31 by 搏击518
[考研] 315求调剂 +13 小羊小羊_ 2026-04-02 14/700 2026-04-04 20:30 by 蓝云思雨
[考研] 求调剂，一志愿南京航空航天大学 ，080500材料科学与工程学硕 +10 @taotao 2026-04-03 10/500 2026-04-04 09:01 by T可可西里T
[考研] 281求调剂 +10 aaawhy 2026-04-03 10/500 2026-04-03 21:42 by lbsjt
[考研] 学硕288调剂!!! +3 小王xw123 2026-04-03 3/150 2026-04-03 21:20 by 啵啵啵0119
[考研] 303求调剂 +9 DLkz1314. 2026-03-30 9/450 2026-04-03 18:34 by ls刘帅
[考研] 301求调剂 +14 A_JiXing 2026-04-01 14/700 2026-04-03 18:31 by ls刘帅
[考研] 考研调剂 +8 不爱喝饮料 2026-04-03 8/400 2026-04-03 16:40 by Mistake-J
[考研] 机械专硕297 +3 Afksy 2026-04-03 3/150 2026-04-03 14:24 by 1753564080
[考研] 283求调剂 +3 jiouuu 2026-04-03 4/200 2026-04-03 13:28 by jiouuu
[考研] 一志愿华东理工大学，080500学硕，317分，求调剂 +13 s1145 2026-03-31 15/750 2026-04-03 11:44 by msi123
[考研] 273求调剂 +20 李芷新1 2026-03-31 20/1000 2026-04-03 09:58 by linyelide
[考研] 一志愿北交大材料工程总分358 +8 cs0106 2026-04-01 9/450 2026-04-02 10:36 by 不吃魚的貓
[考研] 0817化工学硕调剂 +11 努力上岸中！ 2026-03-31 11/550 2026-04-01 20:30 by 赖春艳
[考研] 求0861交通运输专硕or材料专硕调剂 +4 勒布朗@ 2026-03-31 4/200 2026-04-01 09:54 by 一只好果子?
信息提示
关闭
请填处理意见
关闭