// "ListNode.h"
#include <iostream>
using namespace std;
template<class T>
class ListNode
{
public:
ListNode():p_next(NULL){ }
ListNode(const T item, ListNode<T>* next = NULL):data(item), p_next(next){ }
T GetData();
protected:
T data; // 存放节点值
ListNode* p_next; // 存放后继地址
};
template<class T>
T ListNode<T>::GetData()
{
return this->data;
}
// SingleList.h
#include "ListNode.h"
template<class T>
class SingleList
{
public:
SingleList();
~SingleList();
int Length(); // 链表长度
void Clear(); // 清空链表
int Find(int n, T &targ); // 查找n号节点,值存入targ
int Insert(int n, T targ); // 将targ插入n号位置
int Delete(int n); // 删除第n个元素
private:
ListNode<T>* head; // 存储一个T的节点指针head
};
template<class T>
inline SingleList<T>::SingleList()
{
head = new ListNode<T>();
}
template<class T>
inline SingleList<T>::~SingleList()
{
Clear();
delete head();
}
template<class T>
int SingleList<T>::Length()
{
ListNode<T>* p = head->p_next;
int count = 0;
while (p != NULL) {
++count;
p = p->p_next;
}
return count;
}
template<class T>
void SingleList<T>::Clear()
{
ListNode<T>* pdel; // 从前到后依次删除连接,直到指向NULL的指针也被删除
while (head->p_next != NULL) {
pdel = head->p_next;
head->p_next = pdel->p_next;
delete pdel;
}
}
template<class T>
int SingleList<T>::Find(int n, T & targ)
{
if (n < 0 || n > Length()) {
cout << "Illegal opration!" << endl;
return 0;
}
ListNode<T>* p = head->p_next;
for (int i = 0; i <= n; && p ++i) {
p = p->p_next;
}
if (p == NULL) {
cout << "overflow" << endl;
return 0;
}
targ = p->data;
return 1;
}
template<class T>
int SingleList<T>::Insert(int n, T targ)
{
if (n < 0 || n > Length()) {
cout << "Illegal n" << endl;
return 0;
}
ListNode<T>* p = head;
ListNode<T>* p_new = new ListNode<T>(targ, NULL);
if (p_new == NULL) {
cout << "Node Error" << endl;
return 0;
}
for (int i = 0; i < n; ++i) {
p = p->p_next;
}
p_new->p_next = p->p_next;
p_next = p_new;
return 1;
}
template<class T>
int SingleList<T>::Delete(int n)
{
if (n < 0 || n > Length()) {
cout << "Illegal n" << endl;
return 0;
}
ListNode<T>* p = head;
ListNode<T>* pdel;
for (int i = 0; i < n && p->p_next; ++i) {
p = p->p_next;
}
pdel = p;
p->p_next = pdel->p_next;
T data = pdel->data;
delete pdel;
return 1;
}