单链表的实现
写在前面
链式存储结构是计算机中另一种最基本和最主要的数据存储结构。和顺序存储结构不同，初始化时链式存储结构为空链，每当有新的元素需要存储时用户向系统动态申请所需的存储空间插入链中。所有高级程序设计语言都为用户提供了向系统动态申请和动态释放存储空间的办法。C++提供了new
和delete运算符，分别用于向系统动态申请所需存储空间和动态释放用new申请的存储空间。new能自动计算要分配的类型大小并自动返回正确的指针类型。delete能自动释放由new分配的存储空间。
在顺序存储结构中，用户向系统申请一块地址连续的有限空间用于存储数据元素，这样任意两个在逻辑上相邻的数据元素在物理上也必然相邻。但在链式存储结构中，由于它在初始化时为空链，每当有新的数据元素需要存储时用户才向系统动态申请所需的存储空间插入链中，而这些在不同时刻向系统动态申请的存储空间在内存上很可能是不连续的。因此，在链式存储结构中，任意两个在逻辑上相邻的数据元素在物理上不一定相邻，数据元素的逻辑次序是通过链中的指针连接实现的。
链式存储结构存储线性结构数据元素集合的方法是用节点（Node)构造链。线性结构数据元素的特点是：除第一个和最后一个元素外，每个元素只有一个唯一的前驱和一个唯一的后继。链式结构中每个节点除数据域外，还有一个或两个以上的指针域，数据域用来存放数据元素，指针域用来构造数据元素之间的关系。
1.单链表
单链表简称链表（linked list)，是表数据元素的单链结构存储。链表使用一个一个的节点链接构成的。
表要求允许在任意位置进行插入和删除。当选用带头节点的单链表时，在第一个位置插入节点和在其他位置插入节点一样不会改变头指针head的值，此时改变的是head->next的值。
在第一个位置删除节点和在其他位置删除节点一样也不会改变头指针head的值，此时改变的也是head->next的值。
2.节点类的定义和实现
在单链表中，每个节点构成包括数据域和指针域两部分。每个节点的基本操作包括构造一个节点对象、建立一个新节点、给出当前节点的下一个节点指针等。
template<class T>
class ListNode
{
friend class LinList<T>;//声明友元类
public:
T data;//数据域
ListNode(ListNode<T> *ptrNext = NULL);//构造函数，用于构造头节点，头节点没有data参数
ListNode(const T &item, ListNode<T> *ptrNext = NULL);//构造函数，主要用于构造非头节点的节点
~ListNode() {};//析构函数
private:
ListNode<T> *next;//指向下一节点的指针
};
template<class T>
inline ListNode<T>::ListNode(ListNode<T>* ptrNext):next(ptrNext)
{}//构造函数，用于构造头节点，头节点没有值
template<class T>
inline ListNode<T>::ListNode(const T & item, ListNode<T>* ptrNext)
{//构造函数，用于构造非头节点的节点
data = item;
next = ptrNext;
}
节点类的成员有data域和next域。data域中存放了该节点的数据值，由于应用问题中需要使用链表中的data值，所以定义为公有数据成员方便使用；next域定义为私有数据成员。节点类的成员函数由两个不同参数的构造函数和空的析构函数。析构函数为空是因为节点类中没有用new函数向系统申请空间，而节点对象本身分配的空间，系统可自动识别释放。
3.单链表类的定义
template<class T>
class LinList
{
public:
LinList();//构造函数
~LinList();//析构函数
//表操作成员函数
int listsize() const;//返回链表中元素的个数
bool listempty() const;//链表是否为空
ListNode<T> *index(int pos);//返回指向第pos个节点的指针
void insert(const T& item, int pos);//在pos节点前插入一个data域为item的元素
T Delete(int pos);//删除第pos个节点并返回被删除节点的data域
T getdata(int pos);//返回第pos个节点的data值
void clearlist();//清空表为初始化状态
//遍历链表的成员函数
ListNode<T> *Reset(int pos = 0);//currPtr指向节点pos并返回currPtr
ListNode<T> *Next();//currPtr指向下一个节点并返回currPtr
bool endOfList() const;//currPtr==head？
private:
ListNode<T> *head;//指向头节点的指针
ListNode<T> *currPtr;//当前指针
int size;//单链表中元素的个数
};
单链表类的数据成员有头指针、元素个数和当前节点指针。头指针指向头结点，任何对单链表中节点的操作都要从头指针进入。初始化状态下，节点个数为0.当前节点指针是遍历链表成员函数使用的数据成员，遍历链表成员函数通过控制当前节点指针来遍历链表。
单链表类的成员函数由三组：构造函数和析构函数、表操作的成员函数和遍历链表的成员函数。由于单链表类中的节点是通过new函数向系统申请的，在释放单链表类对象的时候，系统无法自行释放这些空间，所以析构函数不能为空，析构函数必须用delete函数逐个释放这些空间。表操作成员函数时对表操作的基本成员函数，这与顺序表类中对表进行操作的成员函数意义相同，但是实现方法不同。链表的遍历操作是每次寻找当前节点的下一个节点，由于每次对链表类中节点的操作都要从头指针进入后寻找到相应的节点后才可完成，这样的单链表类遍历操作的时间复杂度返回大大增加，在单链表中增加一组遍历链表的成员函数可使单链表遍历操作的时间复杂度不增加。
4.单链表类的实现
template<class T>
inline LinList<T>::LinList()
{
head = new ListNode<T>();//头指针指向头结点
size = 0;
}
template<class T>
inline LinList<T>::~LinList()
{
clearlist();
delete head;
head = NULL;
}
template<class T>
inline int LinList<T>::listsize() const//返回单链表中元素的个数
{
return size;
}
template<class T>
inline bool LinList<T>::listempty() const
{
return size == 0;
}
template<class T>
inline ListNode<T>* LinList<T>::index(int pos)
{
if (pos == -1)
return head;
if (pos<0 || pos>size)
{
cout << "illegal operator" << endl;
exit(1);
}
ListNode<T> *p = head->next;//p指向第一个节点
int i = 0;
while (p != NULL && i < pos)
{
p = p->next;
i++;
}
return p;
}
template<class T>
inline void LinList<T>::insert(const T & item, int pos)
{
ListNode<T> *p = index(pos - 1);
ListNode<T> *newnode = new ListNode<T>(item, p->next);
p->next = newnode;
size++;
}
template<class T>
inline T LinList<T>::Delete(int pos)
{
if (size == 0)
{
cout << "list is empty" << endl;
exit(1);
}
ListNode<T>*q, *p = index(pos - 1);//p为指向第pos-1个节点的指针
q = p->next;//q指向要删除节点
p->next = p->next->next;//p指向要删除节点的后一节点
T data = q->data; //data保存要删除节点值
delete q;
size--;
return data;
}
template<class T>
inline T LinList<T>::getdata(int pos)
{
ListNode<T> *p = index(pos);//指针p指向第pos个节点
return p->data;
}
template<class T>
inline void LinList<T>::clearlist()
{
ListNode<T> *p, *p1;
p = head->next;
while (p != NULL)
{//delete所有new出来的空间
p1 = p;
p = p->next;
delete p1;
}
size = 0;
}
template<class T>
inline ListNode<T>* LinList<T>::Reset(int pos)
{
if (head == NULL)
return NULL;
if (pos < -1 || pos>size)
{
cout << "mistake" << endl;
exit(1);
}
if (pos == -1)
return head;
if (pos == 0)
{
currPtr = head->next;
}
else
{
currPtr = head->next;
ListNode<T> prevPtr = head;
for (int i = 0; i < pos; i++)
{
prevPtr = currPtr;
currPtr = currPtr->next;
}
}
return currPtr;
}
template<class T>
inline ListNode<T>* LinList<T>::Next()
{
if (currPtr != NULL)
{
currPtr = currPtr->next;
}
return currPtr;
}
template<class T>
inline bool LinList<T>::endOfList() const
{
return currPtr == NULL;
}
这些成员函数基本上实现了单链表所需的基本操作。
5.主函数测试
测试主函数如下：
void test()
{
LinList<int> list;
cout << "单链表中的元素个数为："<<list.listsize() << endl;
for (int i = 0; i < 10; i++)
{
list.insert(15 * i, i);
}
cout << "单链表中的元素个数为：" << list.listsize() << endl;
cout << "5号为：" << list.getdata(5) << endl;
cout<<list.Delete(5)<<"已被删除"<<endl;
cout << "5号为：" << list.getdata(5) << endl;
ListNode<int> *p = list.Reset();
while (!list.endOfList())
{
cout << p->data << endl;
p = list.Next();
}
}
int main()
{
test();
system("pause");
return EXIT_SUCCESS;
}
输出结果如下：
