注册 登录
编程论坛 C++教室

多叉树的括号表示法(字符串)然后层序输出。自己检查了好久也没有看出问题来,能运行出来结果,但是提交测试时出错。

yangcaifei 发布于 2015-11-22 23:12, 1357 次点击
输入:(a(b,c,d,e))
输出样例:abcde

//下面是我写的代码:

#include <iostream>
#include <cstring>
#include <cstdlib>
#include <string>
using namespace std;

template<class T>
struct LinkNode
{
    T data;
    LinkNode<T>* link;
    LinkNode(T value,LinkNode<T>* p=NULL):data(value)
    {
        link=p;
    }
};

template<class T>
class Link_queue
{
protected:
    LinkNode<T> *first,*rear;
public:
    Link_queue():first(NULL),rear(NULL) {}
    ~Link_queue();
    bool Enqueue(const T& x);
    bool Dequeue(T& x);
    bool IsEmpty(){return (first==NULL) ? true:false;}
    void output();
};

template<class T>
void Link_queue<T>::output()
{
    LinkNode<T>* p=first;
    while(p!=NULL)
    {
        cout<<p->data;
        p=p->link;
    }
}

template<class T>
Link_queue<T>::~Link_queue()
{
    LinkNode<T>* p;
    while(first!=NULL)
    {
        p=first;
        first=first->link;
        delete p;
    }
}

template<class T>
bool Link_queue<T>::Enqueue(const T& x)
{
    if(first==NULL)
    {
        first=rear=new LinkNode<T>(x);
        if(first==NULL)
            return false;
    }
    else
    {
        rear->link=new LinkNode<T>(x);
        if(rear->link==NULL)
            return false;
        rear=rear->link;
    }
    return true;
}

template<class T>
bool Link_queue<T>::Dequeue(T& x)
{
    if(IsEmpty()==true)
        return false;
    LinkNode<T>* p=first;
    x=first->data;
    first=first->link;
    delete p;

    return true;
}

int Levels(char*& str)
{
    int levels=0,n=strlen(str);
    for(int i=0;i<n;i++)
    {
        if(str[i]=='(')
            levels++;
    }
    return levels;
}

int InLevels(char*& str,char& x)
{
    int i=0,left=0,right=0;
    char ch=str[0];
    while(ch!=x)
    {
        ch=str[i];
        i++;
        if(ch=='(')
            left++;
        if(ch==')')
            right++;
    }
    return left-right;
}

int main()
{
    string string_str;
    cin>>string_str;
    int Count=string_str.length();
    char* str=new char[Count+1];
    for(int i=0;i<Count;i++)
    {
        str[i]=string_str[i];
    }

    int levels=Levels(str);
    Link_queue<char>* levels_queue=new Link_queue<char>[levels];

    int i;
    for(i=0;i<Count;i++)
    {
        if(str[i]!=','&&str[i]!='('&&str[i]!=')')
        {
            int n=InLevels(str,str[i]);
            levels_queue[n].Enqueue(str[i]);
        }
    }

    for(i=0;i<levels;i++)
    {
        levels_queue[i].output();
    }
    cout<<endl;

    delete [] str;
    delete [] levels_queue;

    return 0;
}
10 回复
#2
yangcaifei2015-11-22 23:14
测试数据:(a(b,c,d))
//下面是系统给出的判断

用户程序在运行时发生如下异常:
非法访问内存,可能是数组下标越界

如果不明白以上所示异常,可以假定是由于数组下标越界引起的。
#3
yangcaifei2015-11-22 23:15
回复 2楼 yangcaifei
关键是我在codeblocks上能正确运行,结果也是正确的。
#4
rjsp2015-11-23 08:59
你的算法完全不对,这一点我不说了,我只说你的代码错误吧

当输入 (a(b,c,d)) 时,
Link_queue<char>* levels_queue=new Link_queue<char>[levels]; // 此时 levels == 2
…………
for(i=0;i<Count;i++)
{
    if(str[i]!=','&&str[i]!='('&&str[i]!=')')
    {
        int n=InLevels(str,str[i]);
        levels_queue[n].Enqueue(str[i]); // 随后n等于1和2,溢出了,C/C++的下标是从0开始的,你只能访问levels_queue[0]和levels_queue[1]
    }
}
#5
yangcaifei2015-11-23 22:17
回复 4楼 rjsp
谢谢你,我知道哪里错了。太不应该了在这种地方出错。
#6
yangcaifei2015-11-23 22:22
回复 4楼 rjsp
不过我写的算法没有问题。
#7
rjsp2015-11-24 08:31
以下是引用yangcaifei在2015-11-23 22:22:50的发言:

不过我写的算法没有问题。
如此自信?
对于 (a(b,c,d,e)),你的 int Levels(char*& str) 函数返回 2,这是正确的;
对于 (a(b),c(d)),你的 int Levels(char*& str) 函数返回 3,明明也是2好不好。

#8
yangcaifei2015-11-24 12:43
回复 7楼 rjsp
只有一个根节点,不是森林。
#9
rjsp2015-11-24 13:15
以下是引用yangcaifei在2015-11-24 12:43:22的发言:

只有一个根节点,不是森林。
(a(b,e(f,g))) 你Levels计算出来的是3,正确
(a(b(c,d),e(f,g))) 你Levels计算出来的是4,错误
#10
yangcaifei2015-11-24 23:10
以下是引用rjsp在2015-11-24 13:15:46的发言:

(a(b,e(f,g))) 你Levels计算出来的是3,正确
(a(b(c,d),e(f,g))) 你Levels计算出来的是4,错误


你说的没错,Levels函数计算出来的结果并不是树的层数,而是大于或等于树的层数,Link_queue<char>* levels_queue=new Link_queue<char>[levels] 在开辟空间时不会少只会多,而计算当前字符的层数时就是字符所在树的层次,所以不会影响答案的正确输出。
当然像你说的那种情况(a(b(c,d),e(f,g),h(i,g),k(l,m)))时用我这种算法会造成空间的浪费。我想解决的办法是利用计算当前字符所在树的层次那个函数把最大的那个当做树的层次来开辟内存空间。

不过还是要谢谢你的,谢谢你指出程序中的错误。
#11
rjsp2015-11-25 08:37
程序代码:
#include <cstdio>

int main( void )
{
    struct tree
    {
        int size;
        char values[27];
    };
    struct tree trees[27] = { 0 };

    for( int c, level=-1; c=getchar(), c!=EOF && c!='\n'; )
    {
        switch( c )
        {
        case '(': ++level; break;
        case ')': --level; break;
        case ' ': break;
        case ',': break;
        default: trees[level].values[ trees[level].size++ ] = c;
        }
    }

    for( size_t level=0; level!=27 && trees[level].size!=0; ++level )
        printf( "%.*s", trees[level].size, trees[level].values );
    putchar( '\n' );

    return 0;
}
1