N мерное дерево

@vlad-chk · Регистрация: 29.10.2012

Добый день есть неработающая функция создания n дерева ходов игры, проблема такая она не выделяет память под след элемент когда i=1,2, короче кроме i=0, при i=0 все нормально выделяет. В чем может быть проблема?

C

// Kursovik_AlgoritmY.cpp: определяет точку входа для консольного приложения.
//
 
#include "stdafx.h"
#include <stdlib.h>
int Q=1,N=1;
struct N_N  // список ненулевых элементов из которых возможен ход
{
    int i;
    int j;
    struct N_N * next;
 
};
struct Spis_IJ //Список возможных ходов
{
    int i;
    int j;
    Spis_IJ * next;
 
};
void Create_IJ(int x,int y,struct Spis_IJ ** HEAD)
{
    Spis_IJ * p;
    p=*HEAD;
    if (*HEAD==NULL)
    {
        *HEAD=new(Spis_IJ);
        (*HEAD)->i=x;
        (*HEAD)->j=y;
        (*HEAD)->next=NULL;
 
    }
    else
    {
        while(p->next!=NULL)
            p=p->next;
 
        p->next=new(Spis_IJ);
        p=p->next;
        p->i=x;
        p->j=y;
        p->next=NULL;
        
     }
    
    
}
struct Poln_Spis
{
    int i_O;
    int j_O;
    int i_K;
    int j_K;
    Poln_Spis * next;
};
struct tree
{
    int i_O;
    int j_O;
    int i_K;
    int j_K;
    int Kol;
    int Pos;
    int Gl;
    tree ** next;
};
 
 
int Kolich(int i,int j,int A[9][9])
{
    int N=0;
    if((i-2>0)&&(A[i-2][j]==-2)) N++;
    if((i+2<9)&&(A[i+2][j]==-2)) N++;
    if(((i-1)>=0)&&((j+1)<9)&&(A[i-1][j+1]==-2)) N++;
    if(((i+1)<9)&&((j+1)<9)&&(A[i+1][j+1]==-2)) N++;
    if(((i-1)>=0)&&((j-1)>=0)&&(A[i-1][j-1]==-2)) N++;
    if(((i+1)<9)&&((j-1)>=0)&&(A[i+1][j-1]==-2)) N++;
 
    if(((i-4)>=0)&&(A[i-4][j]==-2)) N++;
    if(((i+4)<9)&&(A[i+4][j]==-2)) N++;
    if(((j-2)>=0)&&(A[i][j-2]==-2)) N++;
    if(((j+2)<9)&&(A[i][j+2]==-2)) N++;
 
    if(((i-3)>=0)&&(j-1>=0)&&(A[i-3][j-1]==-2)) N++;
    
    if(((i-2)>=0)&&(j-2>=0)&&(A[i-2][j-2]==-2)) N++;
    if(((i+3)<9)&&(j+1<9)&&(A[i+3][j+1]==-2)) N++;
    if(((i+2)<9)&&(j+2<9)&&(A[i+2][j+2]==-2)) N++;
    if(((i-3)>=0)&&(j+1<9)&&(A[i-3][j+1]==-2)) N++;
    if(((i-2)>=0)&&(j+2<9)&&(A[i-2][j+2]==-2)) N++;
    if(((i+3)<9)&&(j-1>=0)&&(A[i+3][j-1]==-2)) N++;
    if(((i+2)<9)&&(j-2>=0)&&(A[i+2][j-2]==-2)) N++;
 
    return N;
 
 
 
 
}
 
int Zahvat(int A[9][9], int i,int j,int k)
{
    int N=0;
    if((i-2>0)&&(A[i-2][j]==k)) N++;
    if((i+2<9)&&(A[i+2][j]==k)) N++;
    if(((i-1)>=0)&&((j+1)<9)&&(A[i-1][j+1]==k)) N++;
    if(((i+1)<9)&&((j+1)<9)&&(A[i+1][j+1]==k)) N++;
    if(((i-1)>=0)&&((j-1)>=0)&&(A[i-1][j-1]==k)) N++;
    if(((i+1)<9)&&((j-1)>=0)&&(A[i+1][j-1]==k)) N++;
 
    return N;
}
void Index(int i,int j,int A[9][9],Spis_IJ **HEAD)
{ 
     // создание списка значений I и J при возможных ходах
 
    if((i-2>0)&&(A[i-2][j]==-2))
        Create_IJ(i-2,j,HEAD);
 
    if((i+2<9)&&(A[i+2][j]==-2))
        Create_IJ(i+2,j,HEAD);
 
    if(((i-1)>=0)&&((j+1)<9)&&(A[i-1][j+1]==-2))
        Create_IJ(i-1,j+1,HEAD);
 
    if(((i+1)<9)&&((j+1)<9)&&(A[i+1][j+1]==-2)) 
        Create_IJ(i+1,j+1,HEAD);
 
    if(((i-1)>=0)&&((j-1)>=0)&&(A[i-1][j-1]==-2))
        Create_IJ(i-1,j-1,HEAD);
 
    if(((i+1)<9)&&((j-1)>=0)&&(A[i+1][j-1]==-2)) 
        Create_IJ(i+1,j-1,HEAD);
 
 
 
 
    if(((i-4)>=0)&&(A[i-4][j]==-2))
        Create_IJ(i-4,j,HEAD);
 
    if(((i+4)<9)&&(A[i+4][j]==-2))
        Create_IJ(i+4,j,HEAD);
 
    if(((j-2)>=0)&&(A[i][j-2]==-2)) 
        Create_IJ(i,j-2,HEAD);
 
    if(((j+2)<9)&&(A[i][j+2]==-2)) 
        Create_IJ(i,j+2,HEAD);
 
 
 
 
    if(((i-3)>=0)&&(j-1>=0)&&(A[i-3][j-1]==-2))
        Create_IJ(i-3,j-1,HEAD);
    
    if(((i-2)>=0)&&(j-2>=0)&&(A[i-2][j-2]==-2))
        Create_IJ(i-2,j-2,HEAD);
 
    if(((i+3)<9)&&(j+1<9)&&(A[i+3][j+1]==-2))
        Create_IJ(i+3,j+1,HEAD);
 
    if(((i+2)<9)&&(j+2<9)&&(A[i+2][j+2]==-2)) 
        Create_IJ(i+2,j+2,HEAD);
 
    if(((i-3)>=0)&&(j+1<9)&&(A[i-3][j+1]==-2))
        Create_IJ(i-3,j+1,HEAD);
 
    if(((i-2)>=0)&&(j+2<9)&&(A[i-2][j+2]==-2)) 
        Create_IJ(i-2,j+2,HEAD);
 
    if(((i+3)<9)&&(j-1>=0)&&(A[i+3][j-1]==-2))
        Create_IJ(i+3,j-1,HEAD);
 
    if(((i+2)<9)&&(j-2>=0)&&(A[i+2][j-2]==-2))
        Create_IJ(i+2,j-2,HEAD);
 
}
 
 
void Otk_Kud(int A[9][9],int q, Poln_Spis ** HEAD)
{
    int i,j,k,K;
    Spis_IJ *p=NULL;
    Poln_Spis *pP=NULL;
    for(i=0;i<9;i++)
        for(j=0;j<9;j++)
        {
            if((A[i][j]==q)&&(Kolich(i,j,A)>0))
            {
                Index(i,j,A,&p);
                while(p!=NULL)
                {
                       
                       if (*HEAD==NULL)
                       {
                           *HEAD=new(Poln_Spis);
                          (*HEAD)->i_O=i;
                          (*HEAD)->j_O=j;
                          (*HEAD)->i_K=p->i;
                          (*HEAD)->j_K=p->j;
                          (*HEAD)->next=NULL;
                          pP=*HEAD;
                       }
                       else
                       {
                           while(pP->next!=NULL)
                              pP=pP->next;
                           pP->next=new(Poln_Spis);
                           pP=pP->next;
                           pP->i_O=i;
                           pP->j_O=j;
                           pP->i_K=p->i;
                           pP->j_K=p->j;
                           pP->next=NULL;
                       }
                       p=p->next;
                       
                }
            }
        }
 
 
 
 
    }
                 
                
                
 
int Create_Tree( tree * st,int Q,int A[9][9])
{
    Poln_Spis *Sp=NULL,*p;
    int k=0,i,x;
    while(N<2)
    {
       Otk_Kud(A,Q,&Sp);
        p=Sp;
       while(p!=NULL)
       {
          k++;
          p=p->next;
       }
    p=NULL;
    
    
       st->next=new tree *[k];
       x=sizeof(st->next);
       Q=Q*(-1);
       N++;
       for(i=0;i<k;i++)
       {
           st->next[i]=new tree;
           st=st->next[i];
           st->i_O=Sp->i_O;
           st->j_O=Sp->j_O;
           st->i_K=Sp->i_K;
           st->j_K=Sp->j_K;
           st->Gl=N;
           if(N<2)
           Create_Tree(st,Q,A);
           Sp=Sp->next;
           
      }
       
    }
    return 0;
}
 
 
 
 
 
 
 
 
 
 
 
//*************************************************
int _tmain(int argc, _TCHAR* argv[])
{
    int Mass[9][9];
    Spis_IJ * HEAD_IJ=NULL;
    Poln_Spis * Head_P_S,*P_H;
    struct Spis_IJ *IJp;
    struct tree * ptree=NULL, *tHEAD,**tr;
    struct N_N * HEAD_N_N, *p;
    int i,j,x,y,k=0,q=-1,K;
 
 
 
 
 
    for(i=0;i<9;i++)
        for(j=0;j<9;j++)
            Mass[i][j]=9;
 
    for(j=4;j>-1;j--)
    { 
        q=-1;
        for(i=k;i<9-k;i++)
        {
        
            if(q==(-1))
                Mass[i][j]=-2;
            else
                Mass[i][j]=0;
            q=q*(-1);
 
        }
        k++;
    }
 
 
k=0;
 
    for(j=4;j<9;j++)
    { 
        q=-1;
        for(i=k;i<9-k;i++)
        {
        
            if(q==(-1))
                Mass[i][j]=-2;
            else
                Mass[i][j]=0;
            q=q*(-1);
 
        }
        k++;
    }
 
 
 
 
 
 
 
    Mass[4][4]=1;
    q=0;
    for(x=0;x<9;x++)
        for(y=0;y<9;y++)
        {
            if((Mass[x][y]==1)&&(Kolich(x,y,Mass)>0))
            {
                if(q==0)
                {
                    HEAD_N_N=new(N_N);
                    HEAD_N_N->i=x;
                    HEAD_N_N->j=y;
                    HEAD_N_N->next=NULL;
                    p=HEAD_N_N;
                    
                }
                else
                {
                    p->next=new(N_N);
                    p=p->next;
                    p->i=x;
                    p->j=y;
                    p->next=NULL;
                    
                }
                q++;
            }
        }
if(q!=0)
{
    p=HEAD_N_N;
 
    while(p!=NULL)
    {
       printf("%d %d ",p->i,p->j);
       p=p->next;
 
 
    }
}
Mass[8][4]=-1;
 
/*while(IJp!=NULL)
{
    Mass[IJp->i][IJp->j]=5;
    printf(" % d % d \n",IJp->i,IJp->j);
    IJp=IJp->next;
}
 
*/
 
 
p=HEAD_N_N;
/*while(p!=NULL)
{
    tHEAD=new(tree);
    tHEAD->i=p->i;
    tHEAD->j=p->j;
    tHEAD->Kol=Kolich(p->i,p->j,Mass);
    tHEAD->ms=new tree *[tHEAD->Kol];
    for(i=0;i<tHEAD->Kol;i++)
    {
        tHEAD->ms[i]=new(tree);
 
 
    }
 
 
    
 
}
*/
 
ptree=new tree;
ptree->next=NULL;
 
 
Create_Tree(ptree,Q,Mass);
 
Head_P_S=NULL;
Otk_Kud(Mass,1,&Head_P_S);
P_H=Head_P_S;
 while(P_H!=NULL)
 {
     printf("\n % d % d % d % d \n", P_H->i_K,P_H->j_K,P_H->i_O,P_H->j_O);
         P_H=P_H->next;
 }
 
    for(i=0;i<9;i++)
    {
        printf("\n");
        for(j=0;j<9;j++)
            printf("  % d  ",Mass[i][j]);
    }
 
 
 
system ("pause");
 
    return 0;
}

@Kuzia domovenok · 21.12.2012, 14:16

400-500 строк!!! +куча однотипного копипаста в них. Удачи найти того, кто их станет читать.

@vlad-chk · 22.12.2012, 00:16 **[ТС]**

Читать весь код не нужно, просто он нужен для представления функций , исспользующихся в функции Create_Tree.Впринципе вся проблема моя в ф-ии Create_Tree, она не выделяет память под 2 и более элементов(сынков) в дереве, я не могу понять почему? ошибка в 252 строке , при i!=0 , в чем может быть дело???

@Kuzia domovenok · 22.12.2012, 00:30

Сообщение от vlad-chk

st->next=new tree *[k];
x=sizeof(st->next);
Q=Q*(-1);
N++;
for(i=0;i<k;i++)
{
st->next[i]=new tree;
* * * * * *st=st->next[i];
* * * * * *st->i_O=Sp->i_O;
* * * * * *st->j_O=Sp->j_O;
* * * * * *st->i_K=Sp->i_K;
* * * * * *st->j_K=Sp->j_K;
* * * * * *st->Gl=N;
* * * * * *if(N<2)
* * * * * *Create_Tree(st,Q,A);
* * * * * *Sp=Sp->next;
}

по крайней мере тут неверно.
1) второй раз new вызывать не надо
2) в массиве надо убрать st=st->next[i], для заполнения в глубину у тебя и так есть рекурсивный вызов
3) короче это место должно быть так

C++

st->next=new tree *[k];
Q=Q*(-1);
N++;
for(i=0;i<k;i++)
{
    st->next[i]->i_O=Sp->i_O;
    st->next[i]->j_O=Sp->j_O;
    st->next[i]->i_K=Sp->i_K;
    st->next[i]->j_K=Sp->j_K;
    st->next[i]->Gl=N;
    if(N<2)
    Create_Tree(st->next[i],Q,A);
    //Sp=Sp->next;//а вообще, я не очень понял, что такое sp
}

@vlad-chk · 22.12.2012, 09:30 **[ТС]**

почему не надо? у меня элемент дерева содержит массив указателей на сыновей.
первый раз я вызываю new для создания массива указателей на новые элементы(сыновья) tree, типа tree*;
а потом я вызываю new для выделения памяти под сам новый элемент.... или что-то не так?

@vlad-chk · 23.12.2012, 15:20 **[ТС]**

Up!!!!!

@Alex5 · 23.12.2012, 16:03

C++

//st-> tree1 
//       next[0], next[1], next[2], next[3], ... 
//        |
//        V
//      tree2
//        ...
 
 
//после выполнения операции 
//st=st->next[i]
//получим 
 
//  tree1 
//     next[0], next[1], next[2], next[3], ... 
//       |
//       V
//st-> tree2
 
for(i=0;i<k;i++)
{
    st->next[i]=new tree;  tree* p1 = st;
 
    // после создания next[0] переменной st присваиваем другое значение 
    st=st->next[i];        tree* p2 = st;
 
    // теперь st указывает на другой объект ( *p2 ).
    // в объекте (*p1) next[1], next[2], ... не были созданы  
}

Чтобы next[1], next[2], ..., next[k-1] были успешно созданы, указатель st не должен меняться в цикле for(i...)

@vlad-chk · 23.12.2012, 17:06 **[ТС]**

Все, понял, спасибо Большое!!!

@Kuzia domovenok 3300 / 2681 / 724 Регистрация: 25.03.2012 Сообщений: 9,683 Записей в блоге: 1
	21.12.2012, 14:16	2
	400-500 строк!!! +куча однотипного копипаста в них. Удачи найти того, кто их станет читать. 0

@vlad-chk 0 / 0 / 0 Регистрация: 29.10.2012 Сообщений: 50
	22.12.2012, 00:16 [ТС]	3
	Читать весь код не нужно, просто он нужен для представления функций , исспользующихся в функции Create_Tree.Впринципе вся проблема моя в ф-ии Create_Tree, она не выделяет память под 2 и более элементов(сынков) в дереве, я не могу понять почему? ошибка в 252 строке , при i!=0 , в чем может быть дело??? 0

@vlad-chk 0 / 0 / 0 Регистрация: 29.10.2012 Сообщений: 50
	22.12.2012, 09:30 [ТС]	5
	почему не надо? у меня элемент дерева содержит массив указателей на сыновей. первый раз я вызываю new для создания массива указателей на новые элементы(сыновья) tree, типа tree*; а потом я вызываю new для выделения памяти под сам новый элемент.... или что-то не так? 0

@vlad-chk 0 / 0 / 0 Регистрация: 29.10.2012 Сообщений: 50
	23.12.2012, 15:20 [ТС]	6
	Up!!!!! 0

@vlad-chk 0 / 0 / 0 Регистрация: 29.10.2012 Сообщений: 50
	23.12.2012, 17:06 [ТС]	8
	Все, понял, спасибо Большое!!! 0

Опции темы