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

关于链表的问题

mfkblue 发布于 2009-08-05 20:26, 339 次点击
一个题目要求函数,写了两三天还是写不出来。原来的类全是模板写的,一部分功能是直接抄书例题的。
因为写不出来,所以把代码简化了,重写了这题需要的功能,不过还是错了。
Line是个线性类,按顺序存储数据。
Chain是个链表类,每个节点ChainNode保存数据和下一个节点的地址。
题目要求是写一个函数调用Insert()和Take()将Line对象的数据放入Chain对象里。
下面代码debug时在Transfrom里面的Insert函返回的非常奇怪,返回主函数的上面的Insert()去了,即使把上面的调用Insert函数去掉。代码执行完毕后还是会错了。
还有我这vc++在debug时碰到cout和new就弹出来一堆东西像内存地址,汇编代码,需要文件之类的东西无法再继续下去了.
#include <iostream>
using namespace std;
class Chain;
class Line
{
    friend Chain;
public:
    Line(int M=10);
    ~Line()
    {delete []element;}
    int Length()
    {return length;}
    void Take(int k,int& x);
    Line& Insert(int k,int x);
    void Output(ostream& out);
private:
    int length;
    int Max;
    int *element;
};

Line::Line(int M)
{
    Max=M;
    element=new int[Max];
    length=0;
}

void Line::Take(int k,int& x)//第k个位置,拿出x
{
    x=element[k];
}

Line& Line::Insert(int k,int x)//第k个位置,放入x
{
    int i;
    if(k>=length)
    {
        Max=2*Max;
        int *n=new int[Max];
        for(i=0;i<length;i++)
            n[i]=element[i];
        delete []element;
        element=n;
    }
    for(i=length;i>=k-1;i--)
        element[i+1]=element[i];
    element[k]=x;
    length++;
    return *this;
}

void Line::Output(ostream& out)
{
    for(int i=0;i<length;i++)
        out<<element[i]<<" ";
    cout<<endl;
}

ostream& operator<<(ostream& out, Line& x)
{
    x.Output(out);
    return out;
}

class Chain;
class ChainIterator;

class ChainNode
{
    friend Chain;
    friend class ChainIterator;
    private:
        int data;
        ChainNode *link;
        
};

class Chain
{
public:
    Chain(){first=0;}
    ~Chain();
    int Length();
    Chain& Insert(int k,int x);
    void Output(ostream& out) ;
    Chain& Transform(Line x);
private:
    ChainNode *first;
};

Chain::~Chain()
{
    ChainNode *t;
    while(first)
    {
        t=first->link;
        delete first;
        first=t;
    }
}

int Chain::Length()//返回长度
{
    int i=0;
    ChainNode *t=first;
    while(t)
    {
        t=t->link;
        i++;
    }
    delete t;
    return i;
}

Chain& Chain::Insert(int k,int x)//第k个位置,插入x
{
    ChainNode *t;
    t=new ChainNode;
    t->data=x;
    t->link=0;
    if(k==0) first=t;
    else
    {
        ChainNode *p=first;
        for(int i=1;i<k&&p;i++)
            p=p->link;
        p->link=t;
    }
    
    return *this;
}

Chain& Chain::Transform(Line x)
{
    int t;
    for(int i=0;i<x.Length();i++)
    {
        x.Take(i,t);
        Insert(i,t);      //从上一行拿出数据存进去应该是没问题的
    }
    return *this;    
}

void Chain::Output(ostream& out)
{
        ChainNode  *current;
    for(current=first;current;current=current->link)
        out<<current->data<<" ";
    cout<<endl;
}

ostream& operator<<(ostream&out,Chain& x)
{
    x.Output(out);
    return out;
}

int main()
{
    Chain a;
    int i;
    for(i=0;i<10;i++)
        a.Insert(i,i+1);//下面的Tranform里的Insert会返回到这个位置是怎么回事?
    cout<<a;
    i=a.Length();
    cout<<i<<endl;
    Line l;
    l.Insert(0,3).Insert(1,2).Insert(2,12).Insert(3,21).Insert(4,4);
    cout<<l;
    Chain b;
    b.Transform(l); //这个函数出问题了
    cout<<b;
    return 0;
}
1 回复
#2
pangding2009-08-06 17:06
回复 楼主 mfkblue
程序代码:
#include <iostream>
using namespace std;
class Chain;
class Line
{
    friend Chain;
public:
    Line(int M=10);
    ~Line()
    {delete []element;}
    int Length()
    {return length;}
    void Take(int k,int& x);
    Line& Insert(int k,int x);
    void Output(ostream& out);
private:
    int length;
    int Max;
    int *element;
};

Line::Line(int M)
{
    Max=M;
    element=new int[Max];
    length=0;
}

void Line::Take(int k,int& x)//第k个位置,拿出x
{
    x=element[k];
}

Line& Line::Insert(int k,int x)//第k个位置,放入x
{
    int i;
    if(k>=length)   // 这个的逻辑是不是有点怪?k >= length,只是说它要插入的地方比表长,但并不一定表中的剩余空间就不够用。
                    // 比如刚开始的时候,表长是M,但lentgh是0.如果程序员想在第1个位置插数,就要倍长这个表吗?
    {
        Max=2*Max;
        int *n=new int[Max];
        for(i=0;i<length;i++)
            n[i]=element[i];
        delete []element;
        element=n;
    }
    for(i=length;i>=k-1;i--)
        element[i+1]=element[i];
    element[k]=x;
    length++;
    return *this;
}

void Line::Output(ostream& out)  
{
    for(int i=0;i<length;i++)
        out<<element[i]<<" ";
    cout<<endl;
}

ostream& operator<<(ostream& out, Line& x)
{
    x.Output(out);
    return out;
}

class Chain;
class ChainIterator;

class ChainNode
{
    friend Chain;
    friend class ChainIterator;
    private:
        int data;
        ChainNode *link;
         
};

class Chain
{
public:
    Chain(){first=0;}
    ~Chain();
    int Length();
    Chain& Insert(int k,int x);
    void Output(ostream& out) ;
    Chain& Transform(Line x);
private:
    ChainNode *first;
};

Chain::~Chain()
{
    ChainNode *t;
    while(first)
    {
        t=first->link;
        delete first;
        first=t;
    }
}

int Chain::Length()//返回长度
{
    int i=0;
    ChainNode *t=first;
    while(t)
    {
        t=t->link;
        i++;
    }
    delete t;
    return i;
}

Chain& Chain::Insert(int k,int x)//第k个位置,插入x
{
    ChainNode *t;
    t=new ChainNode;
    t->data=x;
    t->link=0;
    if(k==0) first=t;   // 如果有要链表头插数,是不是要在first指向t之前,把t->link指向原来的表头呢?
    else
    {
        ChainNode *p=first;
        for(int i=1;i<k&&p;i++)
            p=p->link;
        p->link=t;
    }
     
    return *this;
}

Chain& Chain::Transform(Line x)
{
    int t;
    for(int i=0;i<x.Length();i++)
    {
        x.Take(i,t);
        Insert(i,t);      //从上一行拿出数据存进去应该是没问题的
    }
    return *this;     
}

void Chain::Output(ostream& out)  
{
        ChainNode  *current;
    for(current=first;current;current=current->link)
        out<<current->data<<" ";
    cout<<endl;
}

ostream& operator<<(ostream&out,Chain& x)
{
    x.Output(out);
    return out;
}

int main()
{
    Chain a;
    int i;
    for(i=0;i<10;i++)
        a.Insert(i,i+1);//下面的Tranform里的Insert会返回到这个位置是怎么回事?
    cout<<a;
    i=a.Length();
    cout<<i<<endl;  
    Line l;
    l.Insert(0,3).Insert(1,2).Insert(2,12).Insert(3,21).Insert(4,4);
    cout<<l;
    Chain b;
    b.Transform(l); //这个函数出问题了
    cout<<b;
    return 0;
}

暂时就看出了这么点问题,你再改改看~~

还有你说的那个Debug的问题,不要什么都用step(f11),有的用next(f10)就行了。这两个还是有点区别的。

[ 本帖最后由 pangding 于 2009-8-6 17:07 编辑 ]
1