0

/* 関数 delete_back() に問題があります。remove 関数の 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

あなたのデザインは少し混乱しています。

連結リストを設計する従来の C++ の方法 ( など) には、両方として機能する単一のクラスではなく、std::list個別nodeの とクラスがあります。list

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

ポインターだけを渡したい場合は問題ありませんが、ノードオブジェクトではなく、ノードポインターnodeを渡す必要があります。また、ミューテーター関数もポインターを返す必要があります。ヘッド ノードで呼び出すと、削除されたノードへの参照が取得されます。それが必要か、リストへの参照が失われました。コンストラクターはポインターを返す必要があるため、実際のパブリック コンストラクターは使用できません。代わりに静的ファクトリ メソッドが必要です。等々。delete_frontnext

また、頭の前 (および尾の後ろ) に「センチネル ノード」があるかどうかについても一貫性を保つ必要があります。コンストラクターでセンチネルを作成している場合 (実際に行っているように)、最後に挿入された新しいノードはセンチネルを指す必要がありますが、これは行っていません。

また、使用しているhead/tail概念全体がノード API に対して間違っています。(また、さまざまなスタイルの名前を混ぜて一致させるのは非常に混乱します。add一致delete_frontとpush_tail一致がありdelete_backます…)push_tailメソッドを作成するには、リスト全体を処理する (O(N) にする) か、次のいずれかを行う必要があります。すべてのノードにtailポインターを保持させる (リスト変更を O(N) にする) か、ヘッドにtailポインターを保持させ、テールにポインターを保持させる必要がありheadます。

最後の 1 つは機能します (1 つのノードのみがそれぞれを必要とする場合、すべてのノードに対していくつかのポインターを無駄にしますが、それはほとんど問題になりません)。しかし、考えると混乱します。

実際には、頭prevが 0 ではなく尾 (またはセンチネル) を指し、尾が 0 ではなくnext頭 (またはセンチネル) を指す循環リストを作成する方がはるかに簡単です。これにより、a のすべての利点が得られます。そのクラスを必要とせずに、別listのクラス—ヘッドへのポインターがある場合、リスト全体を参照する必要があるのはそれだけです(nodeヘッドとnode->prevテール、またはセンチネルがある場合は同様であるため)。

また、コンストラクターはあまり意味がありません。

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

これにより、デフォルトで構築されたTという名前のローカル変数が作成されdata、それに対して何も行われません。おそらく何かに設定したかったでしょうdata。そして、おそらくこれにはイニシャライザを使用したいと思うでしょう。その場合は、何もする必要はありません。これが既にデフォルトになっているからです。

そして、私は何をすべきかInlistさえわかりません。

に関してはremove_ele(T d)、おそらく最初の要素を削除したいと思いますよdata == dね？最初にメソッドを作成する場合find、それは簡単です: remove(find(d)). find(例外がスローされると想定しています。find代わりに null またはセンチネルなどremove_eleを返し、trueまたはを返したい場合falseは、検索が機能したかどうかを確認するために、明らかにもう 1 行必要です。)

メソッドの書き方がわからない場合は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 に答える