标题:多叉树的括号表示法(字符串)然后层序输出。自己检查了好久也没有看出问题 ...
取消只看楼主
yangcaifei
Rank: 4
来 自:陕西
等 级:业余侠客
威 望:2
帖 子:127
专家分:216
注 册:2014-11-3
结帖率:84%
已结贴  问题点数:100 回复次数:6 
多叉树的括号表示法(字符串)然后层序输出。自己检查了好久也没有看出问题来,能运行出来结果,但是提交测试时出错。
输入:(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;
}
搜索更多相关主题的帖子: 字符串 public include 
2015-11-22 23:12
yangcaifei
Rank: 4
来 自:陕西
等 级:业余侠客
威 望:2
帖 子:127
专家分:216
注 册:2014-11-3
得分:0 
测试数据:(a(b,c,d))
//下面是系统给出的判断

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

如果不明白以上所示异常,可以假定是由于数组下标越界引起的。
2015-11-22 23:14
yangcaifei
Rank: 4
来 自:陕西
等 级:业余侠客
威 望:2
帖 子:127
专家分:216
注 册:2014-11-3
得分:0 
回复 2楼 yangcaifei
关键是我在codeblocks上能正确运行,结果也是正确的。
2015-11-22 23:15
yangcaifei
Rank: 4
来 自:陕西
等 级:业余侠客
威 望:2
帖 子:127
专家分:216
注 册:2014-11-3
得分:0 
回复 4楼 rjsp
谢谢你,我知道哪里错了。太不应该了在这种地方出错。
2015-11-23 22:17
yangcaifei
Rank: 4
来 自:陕西
等 级:业余侠客
威 望:2
帖 子:127
专家分:216
注 册:2014-11-3
得分:0 
回复 4楼 rjsp
不过我写的算法没有问题。
2015-11-23 22:22
yangcaifei
Rank: 4
来 自:陕西
等 级:业余侠客
威 望:2
帖 子:127
专家分:216
注 册:2014-11-3
得分:0 
回复 7楼 rjsp
只有一个根节点,不是森林。
2015-11-24 12:43
yangcaifei
Rank: 4
来 自:陕西
等 级:业余侠客
威 望:2
帖 子:127
专家分:216
注 册:2014-11-3
得分:0 
以下是引用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)))时用我这种算法会造成空间的浪费。我想解决的办法是利用计算当前字符所在树的层次那个函数把最大的那个当做树的层次来开辟内存空间。

不过还是要谢谢你的,谢谢你指出程序中的错误。
2015-11-24 23:10



参与讨论请移步原网站贴子:https://bbs.bccn.net/thread-459492-1-1.html




关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.885653 second(s), 8 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved