debug：First-chance exception in 1.exe: 0xC0000005: Access Violation.

a372187663 · 发表于 2014-4-27 13:48:15

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

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

typedef char ElemType;

ElemType pmid[N] = "DCBGEAHFIJK"; //中序序列
ElemType post[N] = "DCEGBFHKJIA"; //后序序列

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

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

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,j); // 小于m的是左孩子，大于m的是右孩子
leftlen = m - i; //以m为根，左孩子的长度
rightlen = j - m;//以m为根，右孩子的长度

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

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

void PreOrderTraverse(BiTree T)
{
if( T )
{
visit(T->data);
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild);
}
}

int main()
{
BiTree T;
int i,j,s;
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);
CreatBiTree_pmid_post(&T,0,N-1,s);
printf("创建后前序遍历为： ");
PreOrderTraverse(T);

return 0;
}

我不知道算法逻辑有没有问题，但是调试不下去，不知道问题出在哪。源码在此，望各位朋友帮忙。是.c后缀。

rockerz · 发表于 2014-4-27 13:48:16

第8，9行 ElemType pmid[N] = {'D','C','B','G','E','A','H','F','I','J','K'};
因为你的 pmid[n]是字符数组，不是String。所以不能直接定义为 "DCBGEAHFIJK"。必须以数组的方式定义。

FindPos函数不知道你在干什么。。但是为什么只有一个有条件的return? 如果x永远不等于pmid[i]，你的软件如何终结？就算你说x肯定会等于一个pmid[i]，电脑哪里知道？编程你不能假设，每个函数必须得有肯定能到达的return。

a372187663 · 发表于 2014-4-27 15:29:52

rockerz 发表于 2014-4-27 14:37

登录/注册后可看大图

第8，9行 ElemType pmid[N] = {'D','C','B','G','E','A','H','F','I','J','K'};
因为你的 pmid[n]是字符数 ...

噢，谢谢，我改了。但是后面又出现 0xC00000FD: stack overflow.. 应该是我的递归没弄好吧？

rockerz · 发表于 2014-4-27 17:37:02

Stack overflow 是溢出。把数组设定大点看看

a372187663 · 发表于 2014-4-27 17:47:19

rockerz 发表于 2014-4-27 17:37

登录/注册后可看大图

Stack overflow 是溢出。把数组设定大点看看

没用还是谢谢你了。

a372187663 · 发表于 2014-4-27 19:41:42

本帖最后由 a372187663 于 2014-4-27 19:44 编辑

a372187663 发表于 2014-4-27 17:47

登录/注册后可看大图

没用还是谢谢你了。

我没有币悬赏了- -。还是麻烦您一下。
我更改了一下。发现还有问题貌似是出在递归调用右子树上，能帮我看看右子树的递归调用算法有问题么？ FindPos函数改了一下方便找出哪里错了int FindPos(char x,char pmid[],int start) //从start处开始查找
{
int i;
for(i = start;i >= 0;i--)
{
if(x == pmid[i])
{
printf("第%d次找到%c\n",11-i,pmid[i]);
return i; //返回中序根节点位置
}
else
{
printf("第%d次查找不到%c\n",11-i,x);
}
}
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,j); // 小于m的是左孩子，大于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,len-leftlen-1);
}
}

rockerz · 发表于 2014-4-27 22:13:05

大致修改了下。主要还是老问题，你的递归没有返回，导致无限循环。 CreatBiTree_pmid_post这个函数我猜着给你写了个Base Case。PreOrderTraverse这个函数我不知道该怎么写所以你自己看看吧。具体修改都加了备注。我回答问题不是为了币。主要是兴趣爱好。顺便蹭点积分好早日到鱼油I。新鱼油限制太多了。。

像你这种经常语法错误的我建议用geany。虽然错误显示是英文的，但是我觉得这是最好用的了。问题描述比较具体。从你编写代码的用词来看，你的英文应该不差。所以用geany搓搓有余。

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

char pmid[N] = {'A','C','B','G','E','A','H','F','I','J','K'}; //中序序列  //定义char就不用typedef elemtype了吧。。
char post[N] = {'A','C','E','G','B','F','H','K','J','I','A'}; //后序序列

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

int FindPos(char x,char pmid[],int start) //从start处开始查找
{
        int i;
        for(i = start;i >= 0;i--)
        {
                if(x == pmid[i])
                {
                        printf("第%d次找到%s\n",11-i,pmid);
                        return i; //返回中序根节点位置
                }
                else
                {
                        printf("第%d次查找不到%c\n",11-i,x);
                }
        }
        return 0;
}

void CreatBiTree_pmid_post(BiTree *T,int i,int j,int len) //i为mid[]中的首字符下标，j为post[]中的尾字符下标，len为子树字符串长度
{
                if (i<0||i>len)return;     //递归最重要的是base case.就是如果某某为真，停止递归。否则程序会一直调用这个函数，直到爆炸。
                else if (j<0||j>len)return;//这是我猜的base case，对不对自己修改。
        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,j); // 小于m的是左孩子，大于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,len-leftlen-1);
        }
}

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

void PreOrderTraverse(BiTree T)
{
        if(!T)return;
        visit(T->data);
        PreOrderTraverse(T->lchild);
        PreOrderTraverse(T->rchild);
}

int main()
{
        BiTree T;
        int s;
        printf("中序序列为:\n");
        for (int i=0;i<N;i++)printf("%c",pmid[i]);
        
        printf("\n");
        printf("后序序列为：\n");
        for (int i=0;i<N;i++)printf("%c",post[i]);
        printf("\n");
        
        s = strlen(pmid);
        CreatBiTree_pmid_post(&T,0,N-1,s);
        printf("创建后前序遍历为：   ");
      //  PreOrderTraverse(T);                ///这个和你CreatBiTree_pmid_post函数一样，没有合适的Return条件，进入死循环。我不知道你的base case该是什么。
        
        return 0;
}

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

debug：First-chance exception in 1.exe: 0xC0000005: Access Violation.

最佳答案