# 【c++版数据结构】之单链表的实现（领头结点以及尾节点）

www.MyException.Cn  网友分享于：2015-08-22  浏览：0次
【c++版数据结构】之单链表的实现（带头结点以及尾节点）

```#include<iostream>
#include<cassert>
using namespace std;

typedef enum{FALSE,TRUE}Status;

template<class Type>
class List;

template<class Type>
class ListNode
{
friend class List<Type>;   //友元类可以访问该类的成员
private:
Type data;
ListNode *next;
public:
ListNode() :data(Type()), next(NULL){}
ListNode(Type d, ListNode<Type> *n = NULL) :data(d), next(n){}
void SetData(Type d){ data = d; }
Type GetData()const{ return data; }
~ListNode(){}
};

template<class Type>
class List
{
private:
ListNode<Type> *first; //单链表的头指针
ListNode<Type> *last;  //单链表的尾指针
size_t         size;   //单链表的长度
protected:
/*ListNode<Type> * _BuyNode(const Type &x,ListNode<Type> *_Narg = NULL)//--->有待解决
{
ListNode<Type> *s = new ListNode<Type>(x,_Narg);
}*/
ListNode<Type> * _BuyNode(const Type &x)
{
ListNode<Type> *s = new ListNode<Type>(x);
assert(s != NULL);
return s;
}
public:
List()
{
first = last = _BuyNode(0);
size = 0;
}
~List()
{
destory();
}
Status push_back(const Type &x)
{
ListNode<Type> *s = _BuyNode(x);
last->next = s;
last = s;
size++;
return TRUE;
}
void show_list()
{
ListNode<Type> *s = first->next;
while (s != NULL)
{
cout << s->data << "->";
s = s->next;
}
cout << "NULL" << endl;
}
Status push_front(const Type &x)
{
ListNode<Type> *s = _BuyNode(x);
s->next = first->next;
first->next = s;
if (size == 0)
last = s;
size++;
return TRUE;
}
Status pop_back()
{
if (first == last)//size == 0
{
cout << "单链表已空，无法尾删" << endl;
return FALSE;
}
ListNode<Type> *s = first;
while (s->next != last)
{
s = s->next;
}
delete last;
s->next = NULL;
last = s;
size--;
return TRUE;
}
Status pop_front()
{
if (first == last)//size == 0
{
cout << "单链表已空，无法头删" << endl;
return FALSE;
}
ListNode<Type> *s = first->next;
first->next = s->next;
delete s;
if (size == 1)
last = first;
size--;
return TRUE;
}
ListNode<Type>* find(const Type &x) //返回所查元素的地址：麻烦于（delete_val，next,prio）
{
ListNode<Type> *s = first->next;
while (s != NULL && s->data != x)
{
s = s->next;
}
return s;
}
/*ListNode<Type>* find(const Type &x)//返回所查元素的前一个地址
{
ListNode<Type> *s = first;
while (s->next != NULL &&s->next->data != x)
{
s = s->next;
}
if (s->next == NULL)
return NULL:
else
return s;
}*/

////方法一
//Status delete_val(const Type &x)//常规方法
//{
//	ListNode<Type> *s = find(x);
//	if (s == NULL)
//	{
//		cout << "该元素不存在，无法删除" << endl;
//		return FALSE;
//	}
//	if (s == first->next)
//		pop_front();
//	else if (s == last)
//		pop_back();
//	else
//	{
//		ListNode<Type> *p = first;
//		while (p->next != s)     //寻找所查元素的前一个节点
//		{
//			p = p->next;
//		}
//		p->next = s->next;
//		delete s;
//		size--;
//	}
//	return TRUE;
//}
//方法二
Status delete_val(const Type &x)
{
ListNode<Type> *s = find(x);
if (s == NULL)
{
cout << "该元素不存在，无法删除" << endl;
return FALSE;
}
if (s == last)
pop_back();//--------------->尾节点后面没有节点，无法用后面节点的值覆盖它，所以单独定义
else
{
ListNode<Type> *p = s->next;
s->data = p->data;//后面节点的值覆盖它的值
s->next = p->next;//将后面的节点删除
delete p;
size--;
}
return TRUE;

}

ListNode<Type>* next(const Type &x)
{
ListNode<Type> *s = find(x);
if (s == NULL)
{
cout << "该元素不存在" << endl;
return NULL;
}
if (s == last)
{
cout << "该元素没有后继" << endl;
return NULL;
}
else
{
return s->next;
}
}
ListNode<Type>* prio(const Type &x)
{
ListNode<Type> *s = find(x);
if (s == NULL)
{
cout << "该元素不存在" << endl;
return NULL;
}
if (s == first->next)
{
cout << "该元素没有前驱" << endl;
return NULL;
}
else
{
ListNode<Type> *p = first;
while (p->next != s)
{
p = p->next;
}
return p;
}
}
//单链表逆置：将链表从第一个元素处断开（第一个节点成为最后一个节点）
//将链表之后节点的值，依次进行头插（值头插之后记得删除节点）
void reserve()
{
if (size == 0 || size == 1)
return;
ListNode<Type> *s = first->next;
ListNode<Type> *p = s->next;
last = s;
last->next = NULL;//第一个节点成为最后一个节点

while (p != NULL)
{
s = p;
p = p->next;
//push_front(s->data);
//delete s;
s->next = first->next;
first->next = s;
}
}
//按值插入：先排好序，然后寻找要插入元素的前一个位置，在该位置之后插入该元素
Status insert_val(const Type &x)
{
sort();
ListNode<Type> *p = _BuyNode(x);
ListNode<Type> *s = first;
while (s->next != NULL && s->next->data < p->data)//找到所插元素的前一个节点
{
s = s->next;
}
if (s->next == NULL)//这时候，所插元素是最大的，尾插即可（未找到要插入的前一个位置）
push_back(x);
else
{
p->next = s->next;
s->next = p;
size++;
}
return TRUE;
}
//排序思想：将链表从第一个节点处断开（第一个成为最后一个节点）
//将之后的节点依次按值进行插入（注意值插入之后，节点要释放）
void sort()
{
if (size == 0 || size == 1)
return;
ListNode<Type> *s = first->next;
ListNode<Type> *p = s->next;
last = s;  //------->第一个节点成为最后一个节点
last->next = NULL;
while (p != NULL) //------->断开之后依次按值进行插入
{
s = p;              //保存要插入的节点
p = p->next;        //为下一次插入做准备
insert_val(s->data);//进行插入
delete s;           //释放节点，防止内存泄露
}
}
size_t lenth()
{
return size;
}
/*
void clear()
{
ListNode<Type> *s = first;
ListNode<Type> *p;
while (size--)            //p始终指向第一个节点（总是删除第一个节点，删除size次）
{
p = s->next;
s->next = p->next;
delete p;
}
size = 0;
last = fisrt;
}
*/
void clear()
{
ListNode<Type> *s = first->next;//p始终指向第一个节点（总是删除第一个节点，删除size次）
while (s != NULL)
{
first->next = s->next;
delete s;
s = first->next;
}
size = 0;
last = first;
}

void destory()
{
clear();
delete first;
first = last = NULL;
}
};

```

```#include"SList.h"
int main()
{
List<int> mylist;
int item;
int n;
int select = 1;
ListNode<int> *p;
while (select)
{
cout << "*************************************** *" << endl;
cout << "*[1] push_back           [2] push_front *" << endl;
cout << "*[3] show_list           [4] pop_back   *" << endl;
cout << "*[5] pop_front           [6] insert_val *" << endl;
cout << "*[7] lenth               [8] find       *" << endl;
cout << "*[9] merge               [10] delete_val*" << endl;
cout << "*[11] sort               [12] reserve   *" << endl;
cout << "*[13] next               [14] clear     *" << endl;
cout << "*[15] prio               [0] quit_system*" << endl;
cout << "请选择：>";
cin >> select;
switch (select)
{
case 1:
cout << "请输入要插入的元素（-1结束):>";
while (cin >> item, item != -1)
{
mylist.push_back(item);
}
break;
case 2:
cout << "请输入要插入的元素（-1结束）:>";
while (cin >> item, item != -1)
{
mylist.push_front(item);
}
break;
case 3:
mylist.show_list();
break;
case 4:
mylist.pop_back();
break;
case 5:
mylist.pop_front();
break;
case 6:
cout << "请输入要插入的元素：";
cin >> item;
mylist.insert_val(item);
break;
case 7:
cout << "长度为：" << mylist.lenth() << endl;
break;
case 8:
cout << "请输入要查找的元素：";
cin >> item;
if (mylist.find(item))
cout << "it's found" << endl;
else
cout << "it's not exist" << endl;
break;
case 9:
cout << "请输入要删除的位置：";
cin >> n;
//mylist.delete_pos(n,item);
break;
case 10:
cout << "请输入要删除的元素：";
cin >> item;
mylist.delete_val(item);
break;
case 11:
mylist.sort();
break;
case 12:
mylist.reserve();
break;
case 13:
cout << "请输入要查找后继的元素：";
cin >> item;
p = mylist.next(item);
if (p != NULL)
cout << p->GetData() << endl;
break;
case 14:
mylist.clear();
break;
case 15:
cout << "请输入要查找前驱的元素：";
cin >> item;
p = mylist.prio(item);
if (p != NULL)
cout << p->GetData() << endl;
break;
default:
break;
}
}
system("pause");
return 0;
}```

push_front（）：当插入的是第一个节点时  （尾指针要指向该节点）

pop_front （）：当删除的是最后一个节点时（尾指针要指向头结点）

find（）函数：

1：重新找一遍，定位到前一个元素的位置，然后删除所要删除的元素

2：将所要删除元素后面的元素p覆盖要删除的元素，然后将p删除