#include <iostream.h>
template <class T>
class linear_list
{
public:
virtual int is_empty() = 0;
virtual int length() = 0;
virtual int find(int i, T &x) = 0;
virtual int search(T x) = 0;
virtual int insert(int i, T x) = 0;
virtual int _delete(int i) = 0;
virtual int updata(int i, T x) = 0;
virtual void output(ostream &out) = 0;
virtual int add(T x) = 0;
protected:
int n;
};
template <class T> class single_list;
template <class T>
class node
{
private:
T element;
node<T> *link;
friend class single_list<T>;
};
template <class T>
class single_list:public linear_list<T>
{
public:
single_list()
{
first = NULL;
n = 0;
};
~single_list();
int is_empty();
int length() ;
int find(int i, T &x);
int search(T x) ;
int insert(int i, T x);
int _delete(int i);
int update(int i, T x);
void output(ostream &out) ;
int add(T x);
private:
node<T> *first;
};
template <class T>
single_list<T> :: ~single_list()
{
node<T> *p;
while (first)
{
p = first -> link;
delete first;
first = p;
}
}
template <class T>
int single_list<T> :: length()
{
return n;
}
template <class T>
int single_list<T> :: is_empty()
{
if (n == 0)
return 1;
else
return 0;
}
template <class T>
int single_list<T> :: find(int i, T &x)
{
if (i < 0 || i > n - 1)
{
cout << "Out Of Bounds";
return 0;
}
node<T> *p = first;
for(int j = 0; j < i; j++)
p = p -> link;
x = p -> element;
return 1;
}
template <class T>
int single_list<T> :: search(T x)
{
node<T> *p = first;
for (int j = 0; p && p -> element != x; j++)
p = p -> link;
if(p)
return j;
return -1;
}
template <class T>
int single_list<T> :: insert(int i, T x)
{
if (i < -1 || i > n-1)
{
cout << "Out Of Bounds";
return 0;
}
node<T> *q = new node<T>;
q -> element = x;
node<T> *p = first;
for(int j = 0; j < i; j++)
p = p -> link;
if (i > -1)
{
q -> link = p -> link;
p -> link = q;
}
else
{
q -> link = first;
first = q;
}
n++;
return 1;
}
template <class T>
int single_list<T> :: _delete(int i)
{
if (!n)
{
cout << "UnderFlow" << endl;
return 0;
}
if (i < 0 || i > n-1)
{
cout << "Out Of Bounds" << endl;
return 0;
}
node<T> *p = first, *q =first;
for(int j = 0; j < i-1; j++)
q = q -> link;
if (i == 0)
first = first -> link;
else
{
p = q -> link;
q -> link = p -> link;
}
cout << "element:" << p -> element << " will be delete..." << endl;
delete p;
n--;
return 1;
}
template <class T>
int single_list<T> :: update(int i, T x)
{
if (i < 0 || i > n-1)
{
cout << "Out Of Bounds" << endl;
return 0;
}
node<T> *p = first;
for (int j = 0; j < i; j++)
p = p -> link;
p -> element = x;
return 1;
}
template<class T>
void single_list<T> :: output(ostream &out)
{
node<T> *p = first;
while(p)
{
out << p -> element << " ";
p = p -> link;
}
out << endl;
}
template<class T>
int single_list<T> :: add(T x)
{
node<T> *p = first, *q = new node<T>;
q -> element = x;
for (int j = 0; j < n - 1; j++)
{
p = p -> link;
}
if (n == 0)
{
p -> element = q -> element;
p -> link = NULL;
}
else
{
p -> link = q;
q -> link = NULL;
}
n++;
return 0;
}
void main()
{
single_list <char> test_list();
char flag, temp, x;
int k;
cout << "判断是否为空链表<Y/N>:" << endl;
if (test_list().is_empty())
cout << "Y" << endl;
else
cout << "N" << endl;
for(;;)
{
cout << "是否对链表添加元素<Y/N>:" << endl;
cin >> flag ;
if (flag == 'Y' || flag == 'y')
{
cout << "请输入添加的元素:" << endl;
cin >> temp;
test_list().add(temp);
}
else if (flag == 'N' || flag == 'n')
break;
}
cout << "请输入链表待查找元素的位置:";
cin >> k;
test_list().find(k, x);
cout << "第" << k << "个元素是:" << x << endl;
cout << "请输入链表待查找元素:";
cin >> x;
cout << "待查找元素位置是第" << test_list().search(x) << "个";
cout << "请输入要删除元素的位置:";
cin >> k;
test_list()._delete(k);
cout << "请输入要插入元素的位置:";
cin >> k;
cout << "元素的值:";
cin >> x;
test_list().insert(k, x);
}
template <class T>
class linear_list
{
public:
virtual int is_empty() = 0;
virtual int length() = 0;
virtual int find(int i, T &x) = 0;
virtual int search(T x) = 0;
virtual int insert(int i, T x) = 0;
virtual int _delete(int i) = 0;
virtual int updata(int i, T x) = 0;
virtual void output(ostream &out) = 0;
virtual int add(T x) = 0;
protected:
int n;
};
template <class T> class single_list;
template <class T>
class node
{
private:
T element;
node<T> *link;
friend class single_list<T>;
};
template <class T>
class single_list:public linear_list<T>
{
public:
single_list()
{
first = NULL;
n = 0;
};
~single_list();
int is_empty();
int length() ;
int find(int i, T &x);
int search(T x) ;
int insert(int i, T x);
int _delete(int i);
int update(int i, T x);
void output(ostream &out) ;
int add(T x);
private:
node<T> *first;
};
template <class T>
single_list<T> :: ~single_list()
{
node<T> *p;
while (first)
{
p = first -> link;
delete first;
first = p;
}
}
template <class T>
int single_list<T> :: length()
{
return n;
}
template <class T>
int single_list<T> :: is_empty()
{
if (n == 0)
return 1;
else
return 0;
}
template <class T>
int single_list<T> :: find(int i, T &x)
{
if (i < 0 || i > n - 1)
{
cout << "Out Of Bounds";
return 0;
}
node<T> *p = first;
for(int j = 0; j < i; j++)
p = p -> link;
x = p -> element;
return 1;
}
template <class T>
int single_list<T> :: search(T x)
{
node<T> *p = first;
for (int j = 0; p && p -> element != x; j++)
p = p -> link;
if(p)
return j;
return -1;
}
template <class T>
int single_list<T> :: insert(int i, T x)
{
if (i < -1 || i > n-1)
{
cout << "Out Of Bounds";
return 0;
}
node<T> *q = new node<T>;
q -> element = x;
node<T> *p = first;
for(int j = 0; j < i; j++)
p = p -> link;
if (i > -1)
{
q -> link = p -> link;
p -> link = q;
}
else
{
q -> link = first;
first = q;
}
n++;
return 1;
}
template <class T>
int single_list<T> :: _delete(int i)
{
if (!n)
{
cout << "UnderFlow" << endl;
return 0;
}
if (i < 0 || i > n-1)
{
cout << "Out Of Bounds" << endl;
return 0;
}
node<T> *p = first, *q =first;
for(int j = 0; j < i-1; j++)
q = q -> link;
if (i == 0)
first = first -> link;
else
{
p = q -> link;
q -> link = p -> link;
}
cout << "element:" << p -> element << " will be delete..." << endl;
delete p;
n--;
return 1;
}
template <class T>
int single_list<T> :: update(int i, T x)
{
if (i < 0 || i > n-1)
{
cout << "Out Of Bounds" << endl;
return 0;
}
node<T> *p = first;
for (int j = 0; j < i; j++)
p = p -> link;
p -> element = x;
return 1;
}
template<class T>
void single_list<T> :: output(ostream &out)
{
node<T> *p = first;
while(p)
{
out << p -> element << " ";
p = p -> link;
}
out << endl;
}
template<class T>
int single_list<T> :: add(T x)
{
node<T> *p = first, *q = new node<T>;
q -> element = x;
for (int j = 0; j < n - 1; j++)
{
p = p -> link;
}
if (n == 0)
{
p -> element = q -> element;
p -> link = NULL;
}
else
{
p -> link = q;
q -> link = NULL;
}
n++;
return 0;
}
void main()
{
single_list <char> test_list();
char flag, temp, x;
int k;
cout << "判断是否为空链表<Y/N>:" << endl;
if (test_list().is_empty())
cout << "Y" << endl;
else
cout << "N" << endl;
for(;;)
{
cout << "是否对链表添加元素<Y/N>:" << endl;
cin >> flag ;
if (flag == 'Y' || flag == 'y')
{
cout << "请输入添加的元素:" << endl;
cin >> temp;
test_list().add(temp);
}
else if (flag == 'N' || flag == 'n')
break;
}
cout << "请输入链表待查找元素的位置:";
cin >> k;
test_list().find(k, x);
cout << "第" << k << "个元素是:" << x << endl;
cout << "请输入链表待查找元素:";
cin >> x;
cout << "待查找元素位置是第" << test_list().search(x) << "个";
cout << "请输入要删除元素的位置:";
cin >> k;
test_list()._delete(k);
cout << "请输入要插入元素的位置:";
cin >> k;
cout << "元素的值:";
cin >> x;
test_list().insert(k, x);
}