#include <iostream>
using namespace std;
struct Node
{
int data; //节点中的数据 结构体Node的成员变量
Node* next; //指向下一节点的指针，习惯用next命名 结构体Node的成员变量
Node( const int& d=int() ) //结构体也可以有构造函数 ,d=T()来指定默认值
:data(d),next(NULL) //用构造函数来初始化成员变量data和指针
{} //所有数据类型，默认初始化都为0，这里data默认初始化为0
};
class Chain //封装链表
{
private: //数据成员通常都是private的
Node* head; //首先，我们要一个Node型的指针来保存链表的第一个节点；
int length; //再用一个整型变量来记录当前链表内的节点数
public:
Chain() //在构造函数里建立一个空链表，即head指向NULL
:head(NULL),length(0){} //节点数为0;
//当我们在类中定义函数时（不是声明），相当于在前面加上一个inline修饰
void delall() //这个函数用来删除链表中的所有节点
{
Node* pdel; //定义一个Node型指针用来保存要删除的节点
while( head != NULL ) //当head的指向不为NULL时，就是链表中还存在节点
{
pdel = head; //这里备份head的当前指向节点
head = head->next; //把head的指向改变为下一节点
delete pdel; //把head的原指向给删除掉
} //如此一直下去，尾节点的next肯定是指向NULL的，那删除最后一个的时候
//head就被赋值为NULL，不满足循环条件，退出循环
length = 0; //把节点数归零
}
~Chain(){ delall(); } //在析构函数中调用delall函数，来完成对象销毁时清理工作
//这样一个链表必须具备的功能就实现了。下面我们来实现他的增、删、查、改功能
Node*& getpoint( int position ) //对链表的操作，其实全部通过指针来实现的，
{ //那就需要定义一个函数来返回当前节点的指针（引用）
if( position<0 || position>length ) //对节点编号进行合法检查
position = length; //如果是非法节点编号，那么就把他修改为最后一个节点编号
if( position==0 ) //如果编号为0，那就是第一个节点了，
return head; //直接返回head就是指向第一个节点的，注意返回的是head本身
Node* head_bak = head; //如果编号合法并且不是第一个节点，就开始遍历链表
for( int i=1; i < position; i++ ) //为什么不直接用head
{ //注意这里修改的是成员变量。你把head改了，以后到哪找链表
//我们都是通过head一个一个的往下找节点的。head被修改了。后果显而易见
head_bak = head_bak->next; //通过备份的指针来遍历到指定编号前一个节点
} //i不从0开始，减少运算，提高效率
return head_bak->next; //这里如果返回head_bak的话。那就是需要的前一个节点了
}
void insert( const int& data, int position ) //如果不修改参数的话，使用引用做参数的时候，最好加上const
{
Node* pin = new Node(data); //需要调用Node的构造函数
pin->next = getpoint(position); //把指定位置的指针返回给新节点的指针
//也就是说，把新的节点的next指向原来这个位置的节点。
getpoint(position) = pin; //getpoint()返回的是引用，我们可以直接修改它
//前面的一个节点的next指向我们新的节点。
length++; //链表的节点数+1
}
int del( const int& data )
{
int position = find(data);
if( position !=-1 ) //-1代表没找到
{
Node* &pnext = getpoint(position); //用getponit()来获得指定节点的指向信息
Node* pbak = pnext; //用来备份节点的指向信息
pnext = pnext->next; //把next指向改为下下个节点。
delete pbak;
length--;
}
return position;
}
//把<<重载，直接输出链表
friend ostream& operator<<( ostream& os, const Chain& oc )
{
Node* phead = oc.head;
os << "[ ";
while( phead !=NULL ) //判断是否到尾节点
{
os << phead->data << ' ';
phead = phead->next;
}
os << "] "; //这个函数，应该没什么好说的了
return os; //如果还是不理解，当成固定模式去背吧
}
};
void show()
{
cout << "******************************" << endl;
cout << "2- 向链表内添加节点（数据，节点号）" << endl;
cout << "3- 删除链表内某一个数据（数据）" << endl;
cout << "0- 退出" << endl;
cout << "******************************" << endl;
}
int main()
{
Chain link;
int position, data, choice, data_new;
while( choice != 0 )
{
show();
cout << "请选择：";
cin >> choice;
switch ( choice )
{
case 2 :
cout << "请输入要插入的数据和插入位置：" ;
cin >> data >> position;
link.insert( data,position );
cout << link << endl;
break;
case 3 :
cout << "请输入要删除的数据：";
cin >> data;
link.del( data );
cout << link << endl;
break;
default :
break;
}
}
}
温馨提示：答案为网友推荐，仅供参考