论坛 › C\C++交流 › 用链表实现队列，我的代码错在哪儿呢？

andalousie 发表于 2014-1-8 23:14:48

用链表实现队列，我的代码错在哪儿呢？

本帖最后由 andalousie 于 2014-1-8 23:16 编辑

我在看一本叫做《C++实践之路》的书。习题里面的。编不对。。这是链表的头文件#if !defined (LIST_H)
#define LIST_H

class Link
{
public:
        Link (int id) : _id (id) {}
        Link (Link* pNext) : _pNext(pNext) {}
//        Link *SetNext(Link* pNext) { return _pNext = pNext; }
        Link *Next () const { return _pNext; }
        int   Value () const { return _id; }
private:
        Link*_pNext;
        int   _id;
};

class List
{
public:
        List (): _head (0), _tail (_head) {}
        ~List ();
private:
        Link*   _head;
        Link*   _tail;
};

List::~List ()
{
        // free the list
        while ( _head != 0 )
        {
                Link* pLink = _head;
                _head = _head->Next(); // unlink pLink
                delete pLink;
        }
}

#endif下面是队列的cpp文件
#include "List.h"
#include <cassert>
#include <iostream>

const int maxPuts=8;

class Queue: public List
{
public:
        Queue();
        void Put(int i);
        int Get();
private:
        Link*_head;
        Link*_tail;
};

Queue::Queue()
{}

void Queue::Put(int i)
{
        Link * newLink = new Link(i);
        if(_tail == 0)
        {
                _head = newLink;
        }
        else
        {
                _tail->SetNext(newLink);
        }
        _tail = newLink;
}

int Queue::Get()
{
        assert(_head != 0);
        int i = _head->Value();
        Link * tmp = _head;
        _head = _head->Next();
        //Do not use recursions
        tmp->SetNext(0);
        delete tmp;
        if(_head == 0)
                _tail = 0;
        return i;
}

int main()
{
        Queue queue;
        queue.Put(1);
        queue.Put(2);
        std::cout<<"Getting: "<<queue.Get()<<", "<<queue.Get()<<std::endl;
        queue.Put(3);
        std::cout<<"Getting more: "<<queue.Get()<<std::endl;
}总是在SetNext和Value那儿出错，不会改。

五号智能 发表于 2014-1-12 01:44:42

好吧,我承认我只是路过的..今天太困了..就不看程序了,明天有空再看,,

andalousie 发表于 2014-1-21 18:24:59

好吧，我自己终于会实现链队列了。改出来了。。。公布一下答案吧
List.h#if !defined (LIST_H)
#define LIST_H

class Link
{
public:
        Link (int value)
                : _value (value), _pNext (0) {}
        void    SetNext(Link* pNext) { _pNext = pNext; }
        Link *Next () const { return _pNext; }
        int   Value () { return _value; };
private:
        int   _value;
        Link *_pNext;
};

class Queue
{
public:
        Queue();
        ~Queue();
        void Put(int i);
        int Get();
private:
        Link*_head;
        Link*_tail;
};

#endifQueue.cpp#include "List.h"
#include <cassert>
#include <iostream>

const int maxPuts=8;

Queue::Queue()
        : _head(0), _tail(0)
{}

void Queue::Put(int i)
{
        Link * newLink = new Link(i);
        if(_tail == 0)
        {
                _head = newLink;
        }
        else
        {
                _tail->SetNext(newLink);
        }
        _tail = newLink;
}

int Queue::Get()
{
        assert(_head != 0);
        int i = _head->Value();
        Link * tmp = _head;
        _head = _head->Next();
        // don't delete recursively!
        tmp->SetNext(0);
        delete tmp;
        if(_head == 0)
                _tail = 0;
        return i;
}

Queue::~Queue()
{
        while(_head != 0)
        {
                Link* pLink = _head;
                _head = _head->Next();
                delete pLink;
        }
}

int main()
{
        Queue queue;
        queue.Put(1);
        queue.Put(2);
        std::cout<<"Getting: "<<queue.Get()<<", "<<queue.Get()<<std::endl;
        queue.Put(3);
        std::cout<<"Getting more: "<<queue.Get()<<std::endl;
}

wozengcong 发表于 2014-1-22 20:35:17

谢谢LZ分享啊

查看完整版本: 用链表实现队列，我的代码错在哪儿呢？