我写过一个类似的，功能差不多，可以参考改一改就可以了，这样也算是你自己完成的。
线性表：单链表综合案例
MyNode.h 结点的信息类
#ifndef MYNODE_H
#define MYNODE_H
#include <iostream>
#include <string>
using namespace std;
class MyNode
{
friend ostream& operator<<(ostream& out,const MyNode& node)
{
return out<<"The employee: "<<node.m_strName<<" Payoff:"<<node.m_dSalary<<endl;
}
public:
string m_strName;
double m_dSalary;
MyNode* next;
MyNode(string _name ="",double _salary=0):m_strName(_name),m_dSalary(_salary) {}
bool operator==(MyNode& Node) //链表的结点之间是要比较是否相等的，不应该在实现中把每个元素都拿出来比较，常用的操作符要重写，才能体现C++的封装思想
{
if (this->m_strName ==Node.m_strName || this->m_dSalary ==Node.m_dSalary)
{
return true;
}
else
{
return false;
}
}
};
#endif
-------------------------------------------------
MyLink.h
#ifndef MYLINK_H
#define MYLINK_H
#include "MyNode.h"
class MyLink
{
public:
MyLink();
~MyLink();
int LinkLength();
bool LinkEmpty();
void LinkClear();
//构造链表的结点有头插入法和尾插入法两种方法，头插入法最终得到的链表的顺序和插入的顺序相反
bool HeadInsert(MyNode& pNode);
bool TailInsert(MyNode& pNode);
//任意位置插入和删除的方法
bool Insert(int _index, MyNode& pNode);
bool Delete(int _index);
//获取指定节点的位置，或者指定位置的节点
int Location(MyNode& pNode);
bool Get(int _index, MyNode& pNode);
//遍历链表
void Traverse();
//找指定元素的前面一个元素和后一个元素，之前试过了，通过返回值的方式返回找到的结果并不好用
bool Prior(MyNode& pNode,MyNode& returnNode);
bool Next(MyNode& pNode,MyNode& returnNode);
private:
MyNode* m_pLink;
int m_iLength;
};
#endif
--------------------------------
MyLink.cpp
#include "MyLink.h"
MyLink::MyLink()
{
//链表的第一个节点的数据域没有意义，初始化一个单链表只需要一个头结点的指针，因为没有第二个节点所以头指针指向NULL
this->m_pLink = new MyNode();
this->m_pLink->next =NULL;
this->m_pLink->m_dSalary =0;
this->m_pLink->m_strName="";
this->m_iLength =0;
}
MyLink::~MyLink()
{
//链表的析构函数和清空函数的区别就是，析构函数多一个操作，需要释放头结点。首先调用清空函数，再释放头结点
LinkClear();
delete this->m_pLink;
this->m_pLink =NULL;
}
int MyLink::LinkLength()
{
return this->m_iLength;
}
bool MyLink::LinkEmpty()
{
return this->m_iLength==0?true:false;
}
void MyLink::LinkClear()
{
//清空链表需要逐个释放链表的节点，但是不释放头结点
MyNode* currentNode =this->m_pLink->next;
while(currentNode !=NULL)
{
MyNode* temp =currentNode->next;
delete currentNode;
currentNode =temp;
}
// 释放完后面的所有节点之后，需要把头结点指向第一个结点的next指针赋值为空，这样再次清空的时候就不要执行循环，也不会使头指针指向未知的区域
this->m_pLink->next=NULL;
this->m_iLength =0; //情况链表之后将链表的长度设置为0，头结点不入算链表的长度
}
bool MyLink::HeadInsert(MyNode& pNode)
{
try
{
//第一步：重新从堆中申请一块内存用于存储要插入的结点 （不能从栈中申请，否则函数执行完成之后会释放栈申请的内存）
MyNode* newNode =new MyNode();
newNode->m_strName = pNode.m_strName;
newNode->m_dSalary = pNode.m_dSalary;
//第二部：保存当前头结点指向的下一个结点的指针，并将头结点指向下一个结点的指针指向当前新插入的结点
MyNode* temp =this->m_pLink->next;
this->m_pLink->next =newNode;
//第三步：将当前插入的结点指向下一个结点的指针，赋值为旧的头结点的指向下一个结点的指针
newNode->next =temp;
this->m_iLength++; //链表的长度加一
return true;
}
catch (...)
{
return false;
}
}
bool MyLink::TailInsert(MyNode& pNode)
{
try
{
//第一步：重新从堆中申请一块内存用于存储要插入的结点 （不能从栈中申请，否则函数执行完成之后会释放栈申请的内存）
MyNode* newNode =new MyNode();
newNode->m_strName = pNode.m_strName;
newNode->m_dSalary = pNode.m_dSalary;
//第二步：找到最后一个结点的后驱
MyNode* temp =this->m_pLink;
while(temp->next!=NULL)
{
temp=temp->next;
}
//第三步：将当前新插入的结点放到最后一个结点之后，并把当前结点的后驱赋空
temp->next =newNode;
newNode->next =NULL;
this->m_iLength++; //链表的长度加一
return true;
}
catch(...) //const bad_alloc& e 捕获内存申请异常
{
return false;
}
}
// 任意位置插入和删除的方法
bool MyLink::Insert(int _index, MyNode& pNode)
{
if (_index<0 || _index>this->m_iLength+1)
{
return false;
}
else
{
try
{
//申请内存，保存插入的节点信息
MyNode* newNode =new MyNode();
newNode->m_strName =pNode.m_strName;
newNode->m_dSalary =pNode.m_dSalary;
MyNode* currentNode =this->m_pLink;
// 我们这里设定的是头结点不算第一个结点，下标从1开始，在第i个位置插入元素，就等于在i-1和i之间插入元素
for (int k=1; k<_index; k++)
{
currentNode =currentNode->next;
}
newNode->next =currentNode->next; //新节点的后驱指向原先第i-1个节点的后驱
currentNode->next =newNode; //新节点加入第i-1个节点之后
this->m_iLength++;
return true;
}
catch (...)
{
return false;
}
}
}
bool MyLink::Delete(int _index)
{
if (_index<0||_index>this->m_iLength)
{
return false;
}
else
{
MyNode* currentNodePrior =this->m_pLink;
for (int k=1; k<_index; k++)
{
currentNodePrior =currentNodePrior->next; //要删除节点的前一个节点指针
}
MyNode* currentNode =currentNodePrior->next; //要删除的节点
currentNodePrior->next =currentNode->next; //覆盖中间的连接
delete currentNode;// 删除当前节点
currentNode =NULL;
this->m_iLength--; // 长度减一
return true;
}
}
int MyLink::Location(MyNode& pNode)
{
int count=1;
MyNode* currentNode =this->m_pLink;
while(currentNode->next !=NULL)
{
currentNode =currentNode->next;
if (*currentNode ==pNode)
{
return count;
}
count++;
}
return -1;
}
bool MyLink::Get(int _index, MyNode& pNode)
{
if (_index<0 || _index>this->m_iLength)
{
return false;
}
else
{
MyNode* currentNode =this->m_pLink;
for (int k=1; k<=_index; k++)
{
currentNode =currentNode->next;
}
pNode =*currentNode;
return true;
}
}
void MyLink::Traverse()
{
MyNode* currentNode =this->m_pLink;
while(currentNode->next!=NULL)
{
currentNode =currentNode->next;
cout<<(*currentNode);
}
}
bool MyLink::Prior(MyNode& pNode,MyNode& returnNode)
{
MyNode* currentNode =this->m_pLink;
MyNode* currentNodePrior =NULL;
while(currentNode->next!=NULL)
{
currentNodePrior =currentNode;
currentNode =currentNode->next;
//当前节点是第一个结点，那么指向它的是头结点，头结点是无效的，不用于判断，返回FALSE
if (*currentNode == pNode)
{
if (currentNodePrior==this->m_pLink) // == 等于判断写成=赋值判断了
{
return false;
}
returnNode = *currentNodePrior;
return true;
}
}
return false;
}
bool MyLink::Next(MyNode& pNode,MyNode& returnNode)
{
//if (pNode.next == NULL) //如果当前结点是最后一个结点则返回FALSE，不能通过对象运算符访问next指针
//{
// return false;
//}
//else
//{
// returnNode = *(pNode.next);
// return true;
//}
/*
cout<<pNode.next<<endl; 能够执行
cout<<(pNode.next)->m_dSalary<<endl; 访问内存错误，编译没有错，指针不能级联使用
*/
MyNode* currentNode =this->m_pLink;
while(currentNode->next !=NULL)
{
currentNode =currentNode->next;
if (*currentNode == pNode)
{
if (currentNode->next ==NULL)
{
return false;
}
returnNode = *(currentNode->next);
return true;
}
//教程中可以使用 currentNode->next->m_strName，这是什么原理，传入的参数不能直接访问下级指针？？
}
return false;
}
-------------------------------
main.cpp
#include <iostream>
#include <stdlib.h>
#include "MyLink.h"
using namespace std;
int main()
{
MyLink link1;
link1.TailInsert(MyNode("Selina",10000));
link1.TailInsert(MyNode("Richard",1000000));
link1.TailInsert(MyNode("Linus",4000000));
link1.TailInsert(MyNode("Mychu",5000));
link1.TailInsert(MyNode("Tang",8000));
link1.TailInsert(MyNode("Elizabeth",100000));
link1.TailInsert(MyNode("Johnaon",20000));
link1.HeadInsert(MyNode("Stephen",50000));
link1.Traverse();
cout<<"-----------------"<<endl;
link1.Insert(2,MyNode("Edward",6000));
link1.Traverse();
cout<<"-----------------"<<endl;
link1.Delete(2);
link1.Traverse();
cout<<"-----------------"<<endl;
cout<<link1.Location(MyNode("Elizabeth",100000))<<endl;
MyNode temp;
link1.Get(3,temp);
cout<<temp;
cout<<"-----------------"<<endl;
link1.Prior(MyNode("Tang",8000),temp);
cout<<temp;
link1.Next(MyNode("Tang",8000),temp);
cout<<temp;
//这里传入进入的MyNode对象是一个从栈中创建的临时对象，在函数调用结束之后内存空间就释放了，所以在调用函数的内部只能访问MyNode这个临时
//变量的值，而不能访问临时变量的内存地址，因为这段内存地址已经被释放，访问会出现内存的错误
cout<<"-----------------"<<endl;
link1.LinkClear();
link1.HeadInsert(MyNode("George",4000));
link1.Traverse();
system("pause");
return 0;
}