debug：First-chance exception in 1.exe: 0xC0000005: Access Violation.,数据结构与算法,技术交流,鱼C论坛

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

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

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

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

typedef char ElemType;

ElemType pmid = "DCBGEAHFIJK"; //中序序列
ElemType post = "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)
{
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;
m = FindPos(post,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;
inti,j,s;
printf("中序序列为:\n");
for(i = 0;i<N;i++)
{
printf("%c",pmid);
}
printf("\n");
printf("后序序列为：\n");
for(j = 0;j<N;j++)
{
printf("%c",post);
}
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 = {'D','C','B','G','E','A','H','F','I','J','K'};
因为你的 pmid是字符数组，不是String。所以不能直接定义为 "DCBGEAHFIJK"。必须以数组的方式定义。

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

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

rockerz 发表于 2014-4-27 14:37 static/image/common/back.gif
第8，9行 ElemType pmid = {'D','C','B','G','E','A','H','F','I','J','K'};
因为你的 pmid是字符数 ...

噢，谢谢，我改了。但是后面又出现 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 static/image/common/back.gif
Stack overflow 是溢出。把数组设定大点看看

没用还是谢谢你了。

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

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

a372187663 发表于 2014-4-27 17:47 static/image/common/back.gif
没用还是谢谢你了。
我没有币悬赏了- -。还是麻烦您一下。
我更改了一下。发现还有问题貌似是出在递归调用右子树上，能帮我看看右子树的递归调用算法有问题么？ FindPos函数改了一下方便找出哪里错了int FindPos(char x,char pmid[],int start) //从start处开始查找
{
int i;
for(i = start;i >= 0;i--)
{
if(x == pmid)
{
printf("第%d次找到%c\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为子树字符串长度
{
int m;
int leftlen,rightlen;
if(len <= 0)
{
(*T) = NULL;
}
else
{
(*T) = (BiTree)malloc(sizeof(BiTree));
(*T)->data = post;
m = FindPos(post,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 = {'A','C','B','G','E','A','H','F','I','J','K'}; //中序序列//定义char就不用typedef elemtype了吧。。
char post = {'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)
            {
                     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;
            m = FindPos(post,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);

   printf("\n");
   printf("后序序列为：\n");
   for (int i=0;i<N;i++)printf("%c",post);
   printf("\n");

   s = strlen(pmid);
   CreatBiTree_pmid_post(&T,0,N-1,s);
   printf("创建后前序遍历为： ");
   //PreOrderTraverse(T);             ///这个和你CreatBiTree_pmid_post函数一样，没有合适的Return条件，进入死循环。我不知道你的base case该是什么。

   return 0;
}

页: [1]

鱼C论坛's Archiver

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