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;
}