#include"Node.h"
template
class SinglyList
{
public:
Node*head;
SinglyList();
SinglyList(T values[], int n);
~SinglyList();
bool empty();
int count();
T& get(int i);
virtual void set(int i, T x);
Node<T>*insert(int i, T x);
virtual Node<T>*insert(T x);
T remove(int i);
friend ostream &operator<<<>(ostream&, SinglyList<T>&);
void removeAll();
Node<T>*search(T key);
void insertUnrepeatabe(T x);
virtual void removeFirst(T key);
bool operator==(SinglyList<T> &list);
bool operator!=(SinglyList<T>&list);
SinglyList(SinglyList<T>&list);
//SinglyList<T>&operator=(SinglyList<T>&list);
virtual void operator += (SinglyList<T>&list);
};
template
SinglyList::SinglyList()
{
this->head = new Node();
}
template
SinglyList::SinglyList(T values[], int n)
{
this->head = new Node();
Node*rear = this->head;
for (int i = 0; i < n; i++)
{
rear->next = new Node(values[i]);
rear = rear->next;
}
}
template
SinglyList::~SinglyList()
{
this -> removeAll();
delete this->head;
}
template
bool SinglyList::empty()
{
if (this->head == NULL)
return true;
else
return false;
}
template
ostream &operator<<<>(ostream& out, SinglyList&list)
{
out << "（";
for (Node*p = list.head->next; p != NULL; p = p->next)
{
out << p->data;
if (p->next != NULL)
out << ",";
}
out << ")\n";
return out;
}
template
int SinglyList::count()
{
int n = 0;
Node*p = this->head->next;
while (p != NULL)
{
n++;
p = p->next;
}
return n;
}
template
Node*SinglyList::insert(int i, T x)
{
Node*front = this->head;
for (int j = 0; front->next != NULL&&j < i; j++)
front = front->next;
front->next = new Node(x, front->next);
return front->next;
}
template
Node*SinglyList::insert(T x)
{
Node*front = this->head;
while (front->next != NULL)
{
front = front->next;
}
front->next = new Node('j', front->next);
return front->next;
}
template
T SinglyList::remove(int i)
{
Node*front = this->head;
for (int j = 0; front != NULL&&j < i; j++)
front = front->next;
if (i >= 0 && front->next != NULL)
{
Node*q = front->next;
T old = q->data;
front->next = q->next;
delete q;
return old;
}
throw out_of_range("参数制定i元素号超出范围");
}
template
void SinglyList::removeAll()
{
Nodep = this->head->next;
while( p != NULL)
{
Node *q = p;
p = p->next;
delete q;
}
head->next = NULL;
}
template
T& SinglyList::get(int i)
{
Node*p = this->head->next;
for (int j = 0; p != NULL&&j < i; j++)
{
p = p->next;
}
if (i >= 0 && p != NULL)
return p->data;
else
throw out_of_range("参数I制定的元素超出范围");
}
template
void SinglyList::set(int i, T x)
{
Node*p = this->head->next;
for (int j = 0; p != NULL&&j < i; j++)
{
p = p->next;
}
if (i >= 0 && p != NULL)
p->data=x;
else
throw out_of_range("参数I制定的元素超出范围");
}
template
Node SinglyList::search(T key)
{
Node*p = this->head->next;
while (p != NULL)
{
if (p->data == key)
return p;
p = p->next;
}
return NULL;
}
template
void SinglyList::insertUnrepeatabe(T x)
{
Node*p = this->head->next;
int flag=0;
while (p != NULL)
{
if (p->data == x)
{
flag = 1;
break;
}
p = p->next;
}
switch (flag)
{
case 0:
this->insert(x);
break;
case 1:
cout << "该元素已在链表中存在，请重新插入！！！" << endl;
break;
default:
break;
}
}
template
void SinglyList::removeFirst(T key)
{
Node*p = this->head->next;
int flag = 0,n=0;
while (p != NULL)
{
if (p->data == key)
{
flag = 1;
break;
}
n++;
p = p->next;
}
switch (flag)
{
case 1:
this->remove(n);
cout << *this << endl;
break;
case 0:
cout << "链表里无此元素！！！" << endl;
break;
}
}
template
bool SinglyList::operator==(SinglyList&list)
{
int flag = 0;
list.head = new Node();
Node*p = this->head->next;
Node*q = list.head->next;
while (p != NULL&&q != NULL)
{
if (p->data != q->data)
{
flag = 1;
break;
}
p = p->next;
q = q->next;
}
switch (flag)
{
case 0:
cout << "list与该链表相等！！！" << endl;
return true;
break;
case 1:
cout << "list与该链表不相等！！！\n";
return false;
break;
}
}
template
bool SinglyList::operator!=(SinglyList&list)
{
Node*p = this->head->next;
Node*q = list.head->next;
int flag = 0;
while (p != NULL&&q != NULL)
{
if (p->data != q->data)
{
flag = 1;
break;
}
p = p->next;
q = q->next;
}
switch (flag)
{
case 0:
cout << "list与该链表相等！！！" << endl;
return false;
break;
case 1:
cout << "list与该链表不相等！！！\n";
return true;
break;
}
}
template
SinglyList::SinglyList(SinglyList&list)
{
SinglyList list1;
Node*p = list.head->next;
Node*q = list1.head->next;
while (p != NULL)
{
q->next = new Node(p->data, q->next);
p = p->next;
}
delete p;
}
template
void SinglyList::operator += (SinglyList&list)
{
Node*rear = this->head;
while (rear->next != NULL)
rear = rear->next;
rear->next = list.head->next;
list.head->next = NULL;
}
int main()
{
SinglyListlista("abc", 3);
SinglyList<char>listb("abcd", 4);
cout << lista<<endl;
lista.set(2, 'd');
cout << lista<<endl;
lista.insert(1, 'x');
cout << lista<<endl;
lista.insert('j');
cout << lista << endl;
cout<<lista.get(1)<<endl;
cout << lista.search('e')<<endl;
lista.insertUnrepeatabe('e');
cout << lista << endl;
lista.removeFirst('a');
lista == listb;
SinglyList<char> listc(listb);
cout << listc << endl;
system("pause");
return 0;
}
