模板类链表
编写过程参考了：
http://blog.csdn.net/qinmusiyan/article/details/39830195
头结点不为空
节点计数从1开始
由于是模板类，声明和定义都放在头文件里
编写注意事项：
每个节点增加时有且只能定义一个分配一个动态内存（new）
时时判断头结点是否为空，如果为NULL，插入时必须在header上进行
#ifndef Linklist_h
#define Linklist_h
#include <iostream>
template <typename T>
struct node
{
T date;
node* pNext;
};
template <typename T>
class Linklist
{
public:
Linklist();
Linklist(const Linklist<T> &list);
Linklist<T>& operator= (const Linklist<T> &rhs);
~Linklist();
public:
void headAdd(const T& date); //在头结点插入
void rearAdd(const T& date); //在尾节点插入
int size() const; //返回链表长度
bool isEmpty() const; //判断是否为空
void print() const; //遍历链表
T getNElement(int n) const; //返回链表第n个节点值
void insertNElement(int n,const T& data);//将元素插入在链表的第pos位置上;
void deleteNElement(int n = 1); //删除第n个节点
void modifyElement(int n, const T& date); //修改n位置的元素值为x;
int find(const T& date); //查找x第一次出现的位置，若没有，返回-1;
void sort(); //对链表元素进行升序排序;
void destroy();//销毁链表，将链表成为空链表;
private:
node<T>* header;
int length;
};
template <typename T>
Linklist<T>::Linklist() :header(NULL), length(0) {};
template <typename T>
Linklist<T>::Linklist(const Linklist<T> &list) : header(NULL), length(0)
{
int i = 1;
while (i <= list.size())
{
rearAdd(list.getNElement(i));
i++;
}
}
template <typename T>
Linklist<T>& Linklist<T>::operator= (const Linklist<T> &rhs)
{
if (this == &rhs)
{
return *this;
}
destroy();
for (int i = 1; i <= rhs.size(); ++i)
{
rearAdd(rhs.getNElement(i));
}
return *this;
}
template <typename T>
Linklist<T>::~Linklist()
{
destroy();
}
template <typename T>
void Linklist<T>::headAdd(const T& date)
{
node<T> *pnode = new node<T>;
pnode->date = date;
pnode->pNext = NULL;
if (header == NULL)
{
header = pnode;
}
else
{
pnode->pNext = header;
header = pnode;
}
length++;
}
template <typename T>
void Linklist<T>::rearAdd(const T& date)
{
node<T> *pnode = new node<T>;
pnode->date = date;
pnode->pNext = NULL;
if (header == NULL)
{
header = pnode;
}
else
{
node<T>* rear = header;
while (rear->pNext != NULL)
{
rear = rear->pNext;
}
rear->pNext = pnode;
}
length++;
}
template <typename T>
int Linklist<T>::size() const
{
return length;
}
template <typename T>
bool Linklist<T>::isEmpty() const
{
return header == NULL;
}
template <typename T>
void Linklist<T>::print() const
{
node<T> *ptemp = header;
int count = 0;
while (ptemp != NULL)
{
std::cout << ptemp->date << "\t";
ptemp = ptemp->pNext;
count++;
if (count % 5 == 0)
{
std::cout << std::endl;
}
}
std::cout << std::endl;
}
template <typename T>
T Linklist<T>::getNElement(int n) const
{
if (n < 1 || n > length)
{
throw "获得元素位置非法！";
}
else
{
int i = 1;
node<T> *ptemp = header;
while (i++ < n)
{
ptemp = ptemp->pNext;
}
return ptemp->date;
}
}
template <typename T>
void Linklist<T>::insertNElement(int n, const T& date)
{
if (n < 1 || n > length)
{
std::cout << "插入元素位置非法！" << std::endl;
}
else
{
if (n == 1)
{
node<T> *ptemp = new node<T>;
ptemp->date = date;
ptemp->pNext = header;
header = ptemp;
}
else
{
int i = 1;
node<T> *ptemp = header;
while (++i < n)
{
ptemp = ptemp->pNext;
}
node<T> *pinsert = new node<T>;
pinsert->date = date;
pinsert->pNext = ptemp->pNext;
ptemp->pNext = pinsert;
}
length++;
}
return;
}
template <typename T>
void Linklist<T>::deleteNElement(int n = 1)
{
if (n < 1 || n > length)
{
std::cout << "删除元素位置非法！" << std::endl;
}
else
{
node<T> *deleteElement;
if (n == 1)
{
deleteElement = header;
header = header->pNext;
}
else
{
int i = 1;
node<T> *ptemp = header;
while (++i < n)
{
ptemp = ptemp->pNext;
}
deleteElement = ptemp->pNext;
ptemp->pNext = deleteElement->pNext;
}
delete deleteElement;
length--;
}
return;
}
template <typename T>
void Linklist<T>::modifyElement(int n, const T& date)
{
if (n < 1 || n > length)
{
std::cout << "修改元素位置非法！" << std::endl;
}
else
{
if (n == 1)
{
header->date = date;
}
else
{
node<T> *ptemp = header;
int i = 1;
while (i++ < n)
{
ptemp = ptemp->pNext;
}
ptemp->date = date;
}
}
return;
}
template <typename T>
int Linklist<T>::find(const T& date)
{
int i = 1;
int re = -1;
node<T> *ptemp = headr;
while (!ptemp)
{
if (ptemp->date == date)
{
re = i;
break;
}
i++;
ptemp = ptemp->pNext;
}
return re;
}
template <typename T>
void Linklist<T>::sort()
{
if (length > 1)
{
for (int i = length; i > 0; --i)
{
for (int j = 1; j < i; j++)
{
T lift = getNElement(j);
T right = getNElement(j + 1);
if (lift > right)
{
modifyElement(j, right);
modifyElement(j + 1, lift);
}
}
}
}
return;
}
template <typename T>
void Linklist<T>::destroy()
{
while (header != NULL)
{
node<T> *ptemp = header;
header = header->pNext;
delete ptemp;
}
length = 0;
}
#endif测试运行部分：
#include "Linklist.h"
#include <iostream>
int main()
{
Linklist<int> link;
for (int i = 10; i > 0; --i)
{
link.rearAdd(i);
}
link.print();
std::cout << link.size() << std::endl;
Linklist<int> link1(link);
link1 = link1;
link1.print();
link1.deleteNElement(100);
link1.modifyElement(5, 100);
link1.insertNElement(3, 50);
std::cout << link1.size() << std::endl;
link1.print();
link1.sort();
link1.print();
link1.destroy();
std::cout << link1.size() << std::endl;
system("pause");
return 0;
}