C++シングルチェーンテーブル実装

23736 ワード

明日の試験で、今日は手書きで単鎖表を作って試験水をします.簡単だと思っていたのに、2時間も書いていた.最初はテンプレートクラスを使おうとしたが、結果はあまりクレイジーに報告されず、結局int型しかできなかった.コードのみを入れます.vectorで書かれたプログラムと合って撮った後が正しいです.
#include 
using namespace std;
typedef long long ll;
class List;

class Node //   
{
private:
    int value;
    Node *next;
public:
    Node(int x): value(x), next(0) {}
    friend class List;
    friend ostream &operator <<(ostream &, List);
    friend List operator +(const List, const List);
};

class List //   
{
private:
    Node *head, *tail;
public:
    List(): head(0), tail(0) {} //      
    ~List();
    List (const List &); //          
    void insert(int x); //    
    void del(int x); //    
    void reverse(); //  
    void display();
    friend ostream &operator <<(ostream &, const List);
    friend List operator +(const List, const List); //    
};

List::~List()
{
    Node *p = head;
    while (p)
    {
        head = head -> next;
        delete p;
        p = head;
    }
    tail = 0;
}

List::List(const List &L)
{
    head = tail = 0;
    Node *p = L.head;
    while (p)
    {
        Node *p_now = new Node(*p);
        if (!head) head = tail = p_now;
        else tail -> next = p_now, tail = p_now;
        p = p -> next;
    }
}

void List::insert(int x)
{
    Node *p = new Node(x);
    if (!head) head = tail = p;
    else tail -> next = p, tail = p;
}

void List::del(int x)
{
    Node *prev = 0, *now = head;
    while (now)
    {
        if (now -> value == x) //        
        {
            if (prev)
            {
                if (now != tail)
                {
                    prev -> next = now -> next;
                    delete now; now = prev -> next;
                }
                else
                {
                    prev -> next = now -> next;
                    delete now; now = prev -> next;
                    tail = prev;
                }
            }
            else
            {
                head = now -> next;
                delete now; now = head;
            }
        }
        else prev = now, now = now -> next;
    }
}

void List::reverse()
{
    Node *prev = 0, *now = head, *latt = head -> next;
    while (now)
    {
        now -> next = prev;
        prev = now, now = latt;
        if (now) latt = now -> next;
    }
    swap(head, tail);
}

void List::display()
{
    Node *p = head;
    while (p)
    {
        cout << p -> value << ' ';
        p = p -> next;
    }
}


ostream &operator <<(ostream &output, const List L)
{
    Node *p = L.head;
    while (p)
    {
        output << p -> value << ' ';
        p = p -> next;
    }
    return output;
}

List operator +(const List a, const List b)
{
    List c;
    Node *p = a.head;
    while (p) c.insert(p -> value), p = p -> next;
    p = b.head;
    while (p) c.insert(p -> value), p = p -> next;
    return c;
}

int main()
{
    List L;
    int n; cin >> n;
    for (int i = 1; i <= n; ++i)
    {
        int t; cin >> t; L.insert(t);
    }
    cout << L << endl; //          
    int d; cin >> d;
    L.del(d);
    cout << L << endl; //          
    L.reverse();
    cout << L << endl; //        
    return 0;
}