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

24小时热门版块排行榜    

小木虫论坛-学术科研互动平台 » 计算模拟区 » 程序语言 » C/C++ » 求高手帮忙修改一段c++程序
北京石油化工学院2026年研究生招生接收调剂公告
51/1返回列表
查看: 1284  |  回复: 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返回列表
普通表情 龙 兔 虎 猫
最具人气热帖推荐 [查看全部] 作者 回/看 最后发表
[考研] 22408 总分320，一篇论文二作，两个国三，求调剂 +3 Leomulufu 2026-04-04 5/250 2026-04-05 19:04 by chongya
[考研] 数一英一 347 人工智能国奖论文都有求调剂 +3 乌拉儿山脉 2026-03-30 7/350 2026-04-05 10:32 by zhq0425
[考研] 266分，一志愿电气工程，本科材料，求材料专业调剂 +11 哇呼哼呼哼 2026-04-01 12/600 2026-04-04 23:17 by 永字号
[考研] 一志愿211，化学学硕，310分，本科重点双非，求调剂 +11 努力奋斗112 2026-04-04 11/550 2026-04-04 20:51 by 蓝云思雨
[考研] 085601，一志愿厦大334复试被刷求调剂 +13 曾仰之 2026-04-03 15/750 2026-04-04 20:13 by dongzh2009
[考研] 一志愿安徽某211 0703化学总分339求调剂 +6 晚风不晚 2026-04-04 6/300 2026-04-04 20:11 by dongzh2009
[考研] 26调剂 086003 +6 失活的细胞 2026-04-04 6/300 2026-04-04 09:50 by zhangdingwa
[考研] 求调剂 +3 wos666 2026-04-03 3/150 2026-04-04 05:16 by gswylq
[考研] 320调剂 +4 农业工程与信息� 2026-04-03 4/200 2026-04-03 21:40 by lbsjt
[考研] 285求调剂 +14 AZMK 2026-04-02 14/700 2026-04-02 15:54 by 上九天揽月（好�
[考研] 286分调剂 +20 Faune 2026-03-30 22/1100 2026-04-02 13:24 by clyblh
[考研] 08工科求调剂290分 +5 1314捧花 2026-04-02 8/400 2026-04-02 13:16 by 乔哒哒哒
[考研] 0710生物学求调剂 +9 manman511 2026-04-01 9/450 2026-04-02 10:00 by zxl830724
[考研] 354求调剂 +4 lxb598 2026-03-31 5/250 2026-04-02 09:55 by Jaylen.
[考研] 一志愿346上海大学生物学 +3 上海大学346调剂 2026-04-01 3/150 2026-04-02 08:36 by w虫虫123
[考研] 一志愿安徽大学计算机科学与技术学硕，331分求调剂 +5 蒋昌鹏qtj 2026-04-01 5/250 2026-04-02 08:10 by fxue1114
[考研] 085602化学工程268分蹲调剂 +8 月照花林。 2026-04-01 8/400 2026-04-01 22:08 by 无际的草原
[考研] 265求调剂 +11 yelck 2026-04-01 12/600 2026-04-01 19:12 by 549790059
[考研] 285求调剂 +7 AZMK 2026-03-30 13/650 2026-04-01 17:00 by 七度不信任
[考研] 一志愿西交大080500材料学硕349 +6 jqx1258 2026-03-31 7/350 2026-03-31 21:08 by yuq
信息提示
关闭
请填处理意见
关闭