为什么我的数组定义了12个数，它还会变成24个数呢？

a372187663 · 发表于 2014-4-29 13:53:15

本帖最后由 a372187663 于 2014-4-29 14:30 编辑

如图
求解释！！

//已知中序序列和后序序列，建立一颗二叉树

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 12

typedef char ElemType;

ElemType pmid[N] = {'G','D','J','H','K','B','E','A','C','F','M','I'}; //中序序列

ElemType post[N] = {'G','J','K','H','D','E','B','M','I','F','G','A'}; //后序序列

typedef struct BiTNode
{
      char data;
      struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;

int FindPos(char x,char pmid[]) //从start处开始查找
{
      int i;
      for(i = N;i >= 0;i--)
      {
            if(x == pmid[i])
            {
      return i; //返回中序根节点位置
            }

      }

      return 0;
}

void CreatBiTree_pmid_post(BiTree *T,int i,int j,int len) //i为mid[]中的首字符下标，j为post[]中的尾字符下标，len为子树字符串长度
{
      int m;
      int leftlen,rightlen;
      if(len <= 0)
      {
            (*T) = NULL;
      }
      else
      {
            (*T) = (BiTree)malloc(sizeof(BiTree));
            (*T)->data = post[j];
            m = FindPos(post[j],pmid);// 小于m的是左孩子，大于m的是右孩子
            printf("根节点位于第%d个字符，元素为%c\n",m+1,pmid[m]);
      leftlen = m - i; //以m为根，左孩子的长度
            rightlen = len - leftlen -1;//以m为根，右孩子的长度

            CreatBiTree_pmid_post(&(*T)->lchild,i,j-1-rightlen,leftlen);
            CreatBiTree_pmid_post(&(*T)->rchild,m+1,j-1,rightlen);
      }
}

void exchange(BiTree T)
{
BiTree p;
if(T)
{
p = T->lchild;
T->lchild = T->rchild;
T->rchild = p;
exchange(T->lchild);
exchange(T->rchild);
}
}

void copyTree(BiTree T,BiTree *S) //递归复制一颗二叉树
{
if(!T)
{
*S = NULL;
}
else
{
(*S) = (BiTree)malloc(sizeof(BiTree));
(*S)->data = T->data;
copyTree(T->lchild,&(*S)->lchild);
copyTree(T->rchild,&(*S)->rchild);
}
}

void visit(char c)
{
      printf("%c", c);
}

void PreOrderTraverse(BiTree T,int level)
{
      if( T )
      {
            visit(T->data);
            PreOrderTraverse(T->lchild,level+1);
            PreOrderTraverse(T->rchild,level+1);
      }
}

int main()
{
int level = 1;
BiTree T = NULL;
BiTree S;
   int  i,j,s,f;
   printf("中序序列为:\n");
   for(i = 0;i<N;i++)
   {
            printf("%c",pmid[i]);
   }
   printf("\n");
   printf("后序序列为：\n");
   for(j = 0;j<N;j++)
   {
            printf("%c",post[j]);
   }
   printf("\n");

s = strlen(pmid);
f = strlen(post);
   CreatBiTree_pmid_post(&T,0,N-1,s);
   printf("创建后前序遍历为:\n");
   PreOrderTraverse(T,level);
   printf("\n");

exchange(T);
printf("交换后前序遍历为:\n");
PreOrderTraverse(T,level);
printf("\n");

copyTree(T,&S);
printf("复制后:\n");
PreOrderTraverse(T,level);
printf("\n");

   return 0;
}

源代码

HHR · 发表于 2014-4-29 13:53:16

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 13 // 结束符

typedef char ElemType;

ElemType pmid[N] = {'G','D','J','H','K','B','E','A','C','F','M','I'}; //中序序列

ElemType post[N] = {'G','J','K','H','D','E','B','M','I','F','G','A'}; //后序序列

typedef struct BiTNode
{
        char data;
        struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;

int FindPos(char x,char pmid[]) //从start处开始查找
{
        int i;
        for(i = N;i >= 0;i--)
        {
                if(x == pmid[i]) // 不得不服啊,[i]这个能漏？ 
                {  
                        return i; //返回中序根节点位置
                }
                
        }
        
        return 0;
}


// 这里就有问题了。。。
void CreatBiTree_pmid_post(BiTree *T,int i,int j,int len) //i为mid[]中的首字符下标，j为post[]中的尾字符下标，len为子树字符串长度
{
        int m;
        int leftlen,rightlen;
        if(len <= 0)
        {
                (*T) = NULL;
        }
        else
        {
                (*T) = (BiTree)malloc(sizeof(BiTree));
                (*T)->data = post[j];

                m = FindPos(post[j],pmid);// 小于m的是左孩子，大于m的是右孩子
                printf("根节点位于第%d个字符，元素为%c\n",m+1,pmid[m]);

                leftlen = m - i; //以m为根，左孩子的长度
                rightlen = len - leftlen -1;//以m为根，右孩子的长度
                
                CreatBiTree_pmid_post(&(*T)->lchild,i,j-1-rightlen,leftlen);
                CreatBiTree_pmid_post(&(*T)->rchild,m+1,j-1,rightlen);
        }
}

void exchange(BiTree T)
{
        BiTree p;
        if(T)
        {
                p = T->lchild;
                T->lchild = T->rchild;
                T->rchild = p;
                exchange(T->lchild);
                exchange(T->rchild);
        }
}


void copyTree(BiTree T,BiTree *S) //递归复制一颗二叉树
{
        if(!T)
        {
                *S = NULL;
        }
        else
        {
                (*S) = (BiTree)malloc(sizeof(BiTree));
                (*S)->data = T->data;
                copyTree(T->lchild,&(*S)->lchild);
                copyTree(T->rchild,&(*S)->rchild);
        }
}

void visit(char c)
{
        printf("%c", c);
}

void PreOrderTraverse(BiTree T,int level)
{
        if( T )
        {
                visit(T->data);
                PreOrderTraverse(T->lchild,level+1);
                PreOrderTraverse(T->rchild,level+1);
        }
}

int main()
{
        int level = 1;
        BiTree T = NULL;
        BiTree S;
        int  i,j,s,f;

        printf("中序序列为:\n");
        for(i = 0;i<N;i++)
        {
                printf("%c",pmid[i]);// 不得不服啊,[i]这个能漏？
        }
        printf("\n");

        printf("后序序列为：\n");
        for(j = 0;j<N;j++)
        {
                printf("%c",post[j]); 
        }
        printf("\n");
        system("pause");
        
        s = strlen(pmid);
        f = strlen(post);
        CreatBiTree_pmid_post(&T,0,N-1,s);
        printf("创建后前序遍历为:\n");
        PreOrderTraverse(T,level);
        printf("\n");
        system("pause");

        exchange(T);
        printf("交换后前序遍历为:\n");
        PreOrderTraverse(T,level);
        printf("\n");
        
        copyTree(T,&S);
        printf("复制后:\n");
        PreOrderTraverse(T,level);
        printf("\n");
        
        return 0;
}

我觉得是算法问题，表示自己修改。。。你可以先运行一次看看{:1_1:}

sidfate · 发表于 2014-4-29 14:48:44

ElemType pmid[N+1] = {'G','D','J','H','K','B','E','A','C','F','M','I'}; //中序序列

C语言字符串借宿的标志是 '\0' ,所以总共有13个字符。

a372187663 · 发表于 2014-4-29 15:58:24

sidfate 发表于 2014-4-29 14:48

登录/注册后可看大图

ElemType pmid[N+1] = {'G','D','J','H','K','B','E','A','C','F','M','I'}; //中序序列

C语言字符串借宿 ...

没用的，你看我调试的那个窗口，post[N]的长度是f = 12 而pmid[N]的长度是s = 24, 不知道你发现没有 pmid的前12个是全局定义的pmid,而它后面的12个是post的全部元素。我不懂为什么他们会合在一起了

HHR · 发表于 2014-4-29 16:40:37

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 13 // 结束符

typedef char ElemType;

ElemType pmid[N] = {'G','D','J','H','K','B','E','A','C','F','M','I'}; //中序序列

ElemType post[N] = {'G','J','K','H','D','E','B','M','I','F','G','A'}; //后序序列

typedef struct BiTNode
{
        char data;
        struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;

int FindPos(char x,char pmid[]) //从start处开始查找
{
        int i;
        for(i = N;i >= 0;i--)
        {
                if(x == pmid[i]) // 不得不服啊,[i]这个能漏？ 
                {  
                        return i; //返回中序根节点位置
                }
                
        }
        
        return 0;
}


// 这里就有问题了。。。
void CreatBiTree_pmid_post(BiTree *T,int i,int j,int len) //i为mid[]中的首字符下标，j为post[]中的尾字符下标，len为子树字符串长度
{
        int m;
        int leftlen,rightlen;
        if(len <= 0)
        {
                (*T) = NULL;
        }
        else
        {
                (*T) = (BiTree)malloc(sizeof(BiTree));
                (*T)->data = post[j];

                m = FindPos(post[j],pmid);// 小于m的是左孩子，大于m的是右孩子
                printf("根节点位于第%d个字符，元素为%c\n",m+1,pmid[m]);

                leftlen = m - i; //以m为根，左孩子的长度
                rightlen = len - leftlen -1;//以m为根，右孩子的长度
                
                CreatBiTree_pmid_post(&(*T)->lchild,i,j-1-rightlen,leftlen);
                CreatBiTree_pmid_post(&(*T)->rchild,m+1,j-1,rightlen);
        }
}

void exchange(BiTree T)
{
        BiTree p;
        if(T)
        {
                p = T->lchild;
                T->lchild = T->rchild;
                T->rchild = p;
                exchange(T->lchild);
                exchange(T->rchild);
        }
}


void copyTree(BiTree T,BiTree *S) //递归复制一颗二叉树
{
        if(!T)
        {
                *S = NULL;
        }
        else
        {
                (*S) = (BiTree)malloc(sizeof(BiTree));
                (*S)->data = T->data;
                copyTree(T->lchild,&(*S)->lchild);
                copyTree(T->rchild,&(*S)->rchild);
        }
}

void visit(char c)
{
        printf("%c", c);
}

void PreOrderTraverse(BiTree T,int level)
{
        if( T )
        {
                visit(T->data);
                PreOrderTraverse(T->lchild,level+1);
                PreOrderTraverse(T->rchild,level+1);
        }
}

int main()
{
        int level = 1;
        BiTree T = NULL;
        BiTree S;
        int  i,j,s,f;

        printf("中序序列为:\n");
        for(i = 0;i<N;i++)
        {
                printf("%c",pmid[i]);// 不得不服啊,[i]这个能漏？
        }
        printf("\n");

        printf("后序序列为：\n");
        for(j = 0;j<N;j++)
        {
                printf("%c",post[j]); 
        }
        printf("\n");
        system("pause");
        
        s = strlen(pmid);
        f = strlen(post);
        CreatBiTree_pmid_post(&T,0,N-1,s);
        printf("创建后前序遍历为:\n");
        PreOrderTraverse(T,level);
        printf("\n");
        system("pause");

        exchange(T);
        printf("交换后前序遍历为:\n");
        PreOrderTraverse(T,level);
        printf("\n");
        
        copyTree(T,&S);
        printf("复制后:\n");
        PreOrderTraverse(T,level);
        printf("\n");
        
        return 0;
}

我觉得是算法问题，表示自己修改。。。你可以先运行一次看看

sidfate · 发表于 2014-4-29 16:50:21

a372187663 发表于 2014-4-29 15:58

登录/注册后可看大图

没用的，你看我调试的那个窗口，post[N]的长度是f = 12 而pmid[N]的长度是s = 24, 不知道你发现没有 pm ...

就是因为我说的原因啊，pmid这个字符串你没有给他终止符，他当然吧后面的字符串（post）也给显示出来了啊

sidfate · 发表于 2014-4-29 16:52:15

HHR 发表于 2014-4-29 16:41

登录/注册后可看大图

我觉得是算法问题，表示自己修改。。。你可以先运行一次看看

对的，楼主你写的那部分的算法有问题。两个递归里面的参数要改一下

HHR · 发表于 2014-4-29 16:56:13

24 行、114 行忘记写上 [i]

a372187663 · 发表于 2014-4-29 17:32:10

HHR 发表于 2014-4-29 16:41

登录/注册后可看大图

我觉得是算法问题，表示自己修改。。。你可以先运行一次看看

由中序序列和后序序列建立一颗二叉树，出了问题
http://bbs.fishc.com/thread-46428-1-1.html

你看我的这个回帖我自己改出来了元素只有11个我的N也是11 也没错啊能运行啊为什么这个元素12个就不行了

a372187663 · 发表于 2014-4-29 17:37:35

sidfate 发表于 2014-4-29 16:52

登录/注册后可看大图

对的，楼主你写的那部分的算法有问题。两个递归里面的参数要改一下

由中序序列和后序序列建立一颗二叉树，出了问题
http://bbs.fishc.com/thread-46428-1-1.html
看我的回帖，基本上一样就是中序序列和后序序列换成12个元素的了那一篇里面元素是11个，我的N也是11 但是可以运行出来，换成12个元素的，N换成12就不行了。

a372187663 · 发表于 2014-4-29 17:54:58

HHR 发表于 2014-4-29 16:41

登录/注册后可看大图

我觉得是算法问题，表示自己修改。。。你可以先运行一次看看

ElemType post[N] = {'G','J','K','H','D','E','B','M','I','F','G','A'}; //后序序列

不好意思是我的全局变量写错了，，第一个跟倒数第二个写成一样的了= =。。。是我打的草稿字写的太丑了
:cry:cry:cry

a372187663 · 发表于 2014-4-29 17:55:51

sidfate 发表于 2014-4-29 16:52

登录/注册后可看大图

对的，楼主你写的那部分的算法有问题。两个递归里面的参数要改一下

ElemType post[N] = {'G','J','K','H','D','E','B','M','I','F','G','A'}; //后序序列

不好意思是我的全局变量写错了，，第一个跟倒数第二个写成一样的了= =。。。现在可以运行了。。。。
是我打的草稿字写的太丑了把C写成了G。。。
:cry:cry:cry

HHR · 发表于 2014-4-29 18:31:40

嗯，问题解决就好，继续加油！
这些问题都要琢磨琢磨，练练总有好处。。

青玄 · 发表于 2014-4-30 08:54:50

恩恩！非常支持楼上的回答！:lol:

账号		自动登录	找回密码
密码			立即注册

为什么我的数组定义了12个数，它还会变成24个数呢？

最佳答案