| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 1357 人关注过本帖
标题:多叉树的括号表示法(字符串)然后层序输出。自己检查了好久也没有看出问题 ...
只看楼主 加入收藏
yangcaifei
Rank: 4
来 自:陕西
等 级:业余侠客
威 望:2
帖 子:127
专家分:216
注 册:2014-11-3
结帖率:84%
收藏
已结贴  问题点数:100 回复次数:10 
多叉树的括号表示法(字符串)然后层序输出。自己检查了好久也没有看出问题来,能运行出来结果,但是提交测试时出错。
输入:(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
rjsp
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:528
帖 子:9011
专家分:53957
注 册:2011-1-18
收藏
得分:100 
你的算法完全不对,这一点我不说了,我只说你的代码错误吧

当输入 (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]
    }
}
2015-11-23 08:59
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
rjsp
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:528
帖 子:9011
专家分:53957
注 册:2011-1-18
收藏
得分:0 
以下是引用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好不好。

2015-11-24 08:31
yangcaifei
Rank: 4
来 自:陕西
等 级:业余侠客
威 望:2
帖 子:127
专家分:216
注 册:2014-11-3
收藏
得分:0 
回复 7楼 rjsp
只有一个根节点,不是森林。
2015-11-24 12:43
rjsp
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:528
帖 子:9011
专家分:53957
注 册:2011-1-18
收藏
得分:0 
以下是引用yangcaifei在2015-11-24 12:43:22的发言:

只有一个根节点,不是森林。
(a(b,e(f,g))) 你Levels计算出来的是3,正确
(a(b(c,d),e(f,g))) 你Levels计算出来的是4,错误
2015-11-24 13:15
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
快速回复:多叉树的括号表示法(字符串)然后层序输出。自己检查了好久也没有看出 ...
数据加载中...
 
   



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

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