1、链表
设计一个简单的单项链表。链表的功能包括向尾节点添加数据、遍历链表中的节点和在链表结束时释放所有节点。
定义一个链表类
class cnode //定义一个节点类
{
public:
cnode *m_pnext; //定义一个节点指针，指向下一个节点
int m_data; //定义节点的数据
cnode()
{
m_pnext=NULL; //将m_pnext设置为空
}
};
class clist //定义链表类clist类
{
private:
cnode *m_pheader; //定义头节点
int m_nodesum; //定义节点数量
public:
clist() //定义链表的构造函数
{
m_pheader=NULL; //初始化m_pheader
m_nodesum=0; //初始化m_nodesum
}
cnode *movetrail() //移动到尾节点
{
cnode *ptmp=m_pheader; //定义一个临时节点，将其指向头节点
for(int i=1;i<m_nodesum;i++) //遍历节点
ptmp=ptmp->m_pnext; //获取下一个节点
return ptmp; //返回尾节点
}
void addnode(cnode *pnode) //添加节点
{
if(m_nodesum==0) //判断链表是否为空
m_pheader=pnode; //将节点添加到头节点中
else //链表不为空
{
cnode *ptrail=movetrail(); //搜索尾节点
ptrail->m_pnext=pnode; //在尾节点处添加节点
}
m_nodesum++; //使链表节点数量加1
}
void passlist() //遍历列表
{
if(m_nodesum>0) //判断链表是否为空
{
cnode *ptmp=m_pheader; //定义一个临时节点，将其指向头节点
printf("%4d",ptmp->m_data); //输出节点数据
for(int i=1;i<m_nodesum;i++) //遍历其他节点
{
ptmp=ptmp->m_pnext; //获取下一个节点
printf("%4d",ptmp->m_data); //输出节点数据
}
}
}
~clist() //定义链表析构函数
{
if(m_nodesum>0) //链表不为空
{
cnode *pdelete=m_pheader; //定义一个临时节点，指向头节点
cnode *ptmp=NULL; //定义一个临时节点
for(int i=0;i<m_nodesum;i++) //遍历节点
{
ptmp=pdelete->m_pnext; //获取下一个节点
delete pdelete; //释放当前节点
pdelete=ptmp; //将下一个节点设置为当前节点
}
m_nodesum=0; //将m_nodesum设置为0
pdelete=NULL; //将pdelete设置为空
ptmp=NULL; //将ptmp设置为空
}
m_pheader=NULL; //将m_pheader设置为空
}
};声明一个链表对象，向其中添加节点，并遍历链表节点
void main()
{
clist list; //定义链表对象
for(int i=0;i<5;i++) //利用循环向列表中添加5个节点
{
cnode *pnode=new cnode(); //构造节点对象
pnode->m_data=i; //设置节点数据
list.addnode(pnode); //添加节点到链表
}
list.passlist(); //遍历节点
cout<<endl; //输出换行
}结果如下：
2、链表类模板
使用类模板让链表类clist能够适应各种类型的节点，在原来链表的基础上将链表中出现的cnode类型的地方替换为模板参数type
template <class type>
class clist //定义clist类
{
private:
type *m_pheader; //定义头节点
int m_nodesum; //定义节点数量
public:
clist() //定义构造函数
{
m_pheader=NULL; //初始化m_pheader
m_nodesum=0; //初始化m_nodesum
}
type *movetrail() //移动到尾节点
{
type *ptmp=m_pheader; //定义一个临时节点，将其指向头节点
for(int i=1;i<m_nodesum;i++) //遍历节点
ptmp=ptmp->m_pnext; //获取下一个节点
return ptmp; //返回尾节点
}
void addnode(type *pnode) //添加节点
{
if(m_nodesum==0) //判断链表是否为空
m_pheader=pnode; //将节点添加到头节点中
else //链表不为空
{
type *ptrail=movetrail(); //搜索尾节点
ptrail->m_pnext=pnode; //在尾节点处添加节点
}
m_nodesum++; //使链表节点数量加1
}
void passlist() //遍历列表
{
if(m_nodesum>0) //判断链表是否为空
{
type *ptmp=m_pheader; //定义一个临时节点，将其指向头节点
printf("%4d",ptmp->m_data); //输出节点数据
for(int i=1;i<m_nodesum;i++) //遍历其他节点
{
ptmp=ptmp->m_pnext; //获取下一个节点
printf("%4d",ptmp->m_data); //输出节点数据
}
}
}
~clist() //定义析构函数
{
if(m_nodesum>0) //链表不为空
{
type *pdelete=m_pheader; //定义一个临时节点，指向头节点
type *ptmp=NULL; //定义一个临时节点
for(int i=0;i<m_nodesum;i++) //遍历节点
{
ptmp=pdelete->m_pnext; //获取下一个节点
delete pdelete; //释放当前节点
pdelete=ptmp; //将下一个节点设置为当前节点
}
m_nodesum=0; //将m_nodesum设置为0
pdelete=NULL; //将pdelete设置为空
ptmp=NULL; //将ptmp设置为空
}
m_pheader=NULL; //将m_pheader设置为空
}
};
在定义节点类
class cnet //定义一个节点类
{
public:
cnet *m_pnext; //定义一个节点指针
char m_data; //定义节点类的数据成员
cnet() //定义构造函数
{
m_pnext=NULL; //将m_pnext设置为空
}
};
class cnode //定义一个节点类
{
public:
cnode *m_pnext; //定义一个节点指针
int m_data; //定义节点类的数据
cnode()
{
m_pnext=NULL; //将m_pnext设置为空
}
};构造类模板实例
clist<cnode>nodelist; //构造一个类模板实例
for(int n=0;n<5;n++) //利用循环向链表中添加节点
{
cnode *pnode=new cnode(); //创造节点对象
pnode->m_data=n; //设置节点数据
nodelist.addnode(pnode); //向链表中添加节点
}
nodelist.passlist(); //遍历列表
cout<<endl; //输出换行
clist<cnet>netlist; //构造一个类模板实例
for(int i=0;i<5;i++) //利用循环向链表中添加节点
{
cnet*pnode=new cnet(); //创造节点对象
pnode->m_data=10+i; //设置节点数据
netlist.addnode(pnode); //向链表中添加节点
}
netlist.passlist(); //遍历列表
cout<<endl; //输出换行结果如下
类模板clist虽然能使用不同类型的节点，但是对节点的类型是有一定要求的。
（1）、节点类必须包含一个指向自身的指针类型成员m_pnext，因为clist中访问了m_pnext成员
（2）、节点中必须包含数据成员m_data，其类型被限制为数字类型或有序类型