0

/* 函数 delete_back() 有问题；我认为删除功能 3 部分有问题。还有 remove_ele() 我不知道怎么做，谢谢。为什么我用同样的方法删除元素不起作用 */ 

#include <iostream>

using namespace std;


template<class T>
class doulinked
{
private:
    doulinked *head;
    doulinked *tail;
    doulinked *prev;
    doulinked *next;

    T data;
public:
    doulinked()
    {
        head=tail=prev=next=NULL;
        T data;
    }
    void Inlist (doulinked *head);
    void add(T d);
    void insert_node();
    void remove(doulinked* v);
    void push_tail(T d); 
    void delete_front();
    void delete_back();
    void remove_ele (T d);
    template <class U>
    friend ostream & operator<<(ostream & os, const doulinked<U> & dll);
};
template<class U>
ostream & operator<<(ostream & os,const doulinked<U> & dll)
{
    doulinked<U> * tmp = dll.head;
    while (tmp)
    {
      os << tmp->data << " ";
      tmp = tmp->next;
    }

  return os;
}
template<class T>
void doulinked<T>::add(T d)
{
    doulinked *n = new doulinked;
    n->data=d;
        if( head == NULL)
        {
            head = n;
            tail = n;
        }
        else
        {
            head->prev = n;
            n->next = head;
            head = n;
        }
}
template<class T>
void doulinked<T>::push_tail(T d)
{
    doulinked *n = new doulinked;
    n->data=d;
        if( tail == NULL)
        {
            head = n;
            tail = n;
        }
        else
        {
            tail->next = n;
            n->prev = tail;
            tail = n;
        }

}
template <class T>
void doulinked<T>::delete_front()
{
    remove(head); 
}
template <class T>
void doulinked<T>::delete_back()
{
    remove(tail);
}
template <class T>
void doulinked<T>::remove(doulinked* v) 
{   
    if(v->prev!=NULL && v->next!=NULL)
    {
        doulinked* p = v->prev; 
        doulinked* n = v->next;             
        p->next = n;                
        n->prev = p;
        delete v;
    }
    else if(v->prev==NULL && v->next!=NULL)
    {
        doulinked* n =v->next;             
        head->next = n;                
        n->prev = head;
        delete head;
        head=n;
    }
    else if(v->prev!=NULL && v->next==NULL) // have some wrong with this loop;
    {
        doulinked* p=v->prev;
        p->next=tail;
        tail->prev=p;
        delete tail;
        tail=p;
    }

 }
template <class T>
void doulinked<T>::remove_ele(T d)  // have some wrong with this loop
{

    if(head->data==d)
    {
        remove(head);
        head=head->next;
    }
    else
        head=head->next;
}

int main()
{
    doulinked<int> dll;
    dll.add(5123);
    dll.add(1227);
    dll.add(127);
    dll.push_tail(1235);
    dll.push_tail(834);
    dll.push_tail(1595);
    dll.delete_front();
    //dll.delete_back();
    //dll.remove_ele(834);
    cout<<dll<<endl;
    system("pause");
}
4

1 回答 1

0

你的设计有点混乱。

设计链表（如std::list）的传统 C++ 方法具有单独的node和list类，而不是充当两者的单个类：

template <typename T> struct node {
    node *prev, *next;
};
template <typename T> struct list {
    node *head, *tail;
};

如果你只想传递node指针，那很好——但是你必须传递节点指针，而不是节点对象。并且 mutator 函数也必须返回一个指针——如果你调用delete_front头节点，你现在得到了一个对删除节点的引用；您需要它next，或者您丢失了对列表的任何引用。由于构造函数必须返回一个指针，所以不能使用真正的公共构造函数；你想要一个静态工厂方法。等等。

您还必须对头部之前（和尾部之后）是否有“哨兵节点”保持一致。如果您在构造函数中创建哨兵——正如你正在做的那样——插入到末尾的新节点需要指向哨兵——你没有这样做。

此外，您使用的整个head/概念对于节点 API 是错误的。tail（此外，混合和匹配来自不同样式的名称非常令人困惑——你需要add匹配delete_front和push_tail匹配delete_back……）要拥有一个push_tail方法，你要么必须遍历整个列表（使其成为 O(N)），要么必须让每个节点都持有tail指针（使任何列表更改 O(N)），或者您必须让头部持有一个tail指针，而尾部持有一个head指针。

最后一个有效（当只有一个节点需要每个节点时，它为每个节点浪费了几个指针，但这并不重要）。但想想就让人困惑。

实际上，只创建一个循环列表要简单得多，其中头部prev指向尾部（或哨兵）而不是 0，而尾部next指向头部（或哨兵）而不是 0。这为您提供了 a 的所有优点单独list的类，不需要那个类——如果你有一个指向头部的指针，那么你只需要引用整个列表（因为node头部和node->prev尾部，或者如果你有一个哨兵，或者类似地）。

此外，您的构造函数没有多大意义：

doulinked()
{
    head=tail=prev=next=NULL;
    T data;
}

这会创建一个名为 的本地默认构造T变量data，然后……什么也不做。你可能想设置data一些东西。您可能想为此使用初始化程序。在这种情况下，您不需要做任何事情，因为这已经是默认设置了。

而且我不确定Inlist应该做什么。

至于remove_ele(T d)，想必你想删除 who 的第一个元素data == d，对吧？如果你find先写一个方法，那么它是微不足道的：remove(find(d)). （我假设这find会引发异常；如果您想find返回 null 或 sentinel 或其他东西，并remove_ele返回trueor false，显然您需要多一行来检查 find 是否有效。）

如果您不知道如何编写find方法……嗯，这就是链表的重点，所有遍历函数都有一个简单的递归定义，包括find：

node *node::find(T d) {
    if (data == d) { return this; }
    if (next) { return next->find(d); }
    return 0;
}

无论如何，我认为与其试图敲打你的代码直到它工作，你应该查看各种设计的现有实现，直到你理解差异，然后选择你想要的设计并尝试实现它。

于 2013-03-25T23:03:59.987 回答