链表模板类问题求解
#include<iostream>
using namespace std;
template<typename T>
struct node
{
T date;
struct node*next;
};
template<typename T>
class list
{
private:
node<T> *head;//链表的头指针
int term;//记录链表中节点的个数
int maxsize;//当前链表可以容纳的最大节点数
public:
list()
{
head=NULL;
term=0;
}
bool empty()//判定链表是否为空
{
if(term==0)
return true;
else
return false;
}
void make_list(int m)//创建指定长度的链表
{
maxsize=m;
node<T>*p=NULL;
node<T>*q=NULL;
int i ;
cout<<"输入数据."<<endl;
for(i=0;i<m;i++)
{
p=new node<T>[1];
cin>>p->date;
if(q==NULL)
head=p;
else
q->next=p;
q=p;
term++;
}
}
void length()//求链表当前的长度
{
cout<<"链表长度:"<<term;
cout<<endl;
}
void insert(int n,T m)//插入一个指定的元素到指定的地点
{
int i;
if(term==maxsize)//链表元素已满
{
if(n<=maxsize)
{
if(n==1)
{
maxsize++;
node<T>*pt;
pt=new node<T>[1];
pt->next=head;
head=pt;
pt->date=m;
term++;
}
else
{
maxsize++;
node<T>*pt=head;
for(i=0;i<n-2;i++)
{
pt=pt->next;
}
node<T> *qt;
qt=new node<T>[1];
qt->date=m;
qt->next=pt->next;
pt->next=qt;
term++;
}
}
else
cout<<"不能插入."<<endl;
}
else if(term<maxsize)//链表还有空位
{
if(n<=term)
{
if(n==1)
{
node<T>*pt;
pt=new node<T>[1];
pt->next=head;
head=pt;
pt->date=m;
term++;
}
else
{
node<T>*pt=head;
for(i=0;i<n-2;i++)
{
pt=pt->next;
}
node<T>*qt;
qt=new node<T>[1];
qt->date=m;
qt->next=pt->next;
pt->next=qt;
term++;
}
}
else
cout<<"不能插入."<<endl;
}
else
cout<<"不能进行插入."<<endl;
}
void dele(int n)//删除指定位置的节点
{
if(n<=term&&&n>0)
{
if(n==1)
{
node<T>*rt;
rt=head;
head=rt->next;
cout<<"删除的数据:"<<rt->date<<endl;
term--;
}
else
{
int i;
node<T>*rt=head;
for(i=0;i<n-2;i++)
rt=rt->next;
node<T>*pt;
pt=rt->next;
rt->next=pt->next;
cout<<"删除的节点元素:"<<pt->date<<endl;
delete pt;
term--;
}
}
else
cout<<"无法删除."<<endl;
}
void add(list&te)//连接两个链表
{
node<T>*pt=head;
for(int i=0;i<term-1;i++)
pt=pt->next;
pt->next=te.head;
term=term+te.term;
maxsize=maxsize+te.maxsize;
}
void display()//输出链表的数据
{
int i;
node<T>*pt=head;
for(i=0;i<term-1;i++)
{
cout<<pt->date<<"->";
pt=pt->next;
}
cout<<pt->date<<endl;
}
};
int main()
{
cout<<"1.链表基本特点演示"<<" "<<"2.在链表中插入数据，删除数据"<<" "<<"3.将两个链表连接"<<endl;
int n;
cout<<"请输入你的选择:";
cin>>n;
list<int>lt1;
list<int>lt2;
int num1,num2;
cout<<"输入要构建的两个链表最初的最大容量值:";
cin>>num1>>num2;
lt1.make_list(num1);
lt2.make_list(num2);
if(n==1)
{
cout<<"第一个链表:";
if(lt1.empty())
cout<<"链表为空"<<endl;
else
cout<<"链表不为空"<<endl;
lt1.length();
lt1.display();
cout<<"第二个链表:";
if(lt2.empty())
cout<<"链表为空"<<endl;
else
cout<<"链表不为空"<<endl;
lt2.length();
lt2.display();
}
if(n==2)
{
lt1.display ();
lt2.display ();
cout<<"第一个链表:";
int num,val;
cout<<"输入要增加节点的位置和数据:";
cin>>num>>val;
lt1.insert (num,val);
lt1.display ();
cout<<"输入要删除的节点位置:";
int dist;
cin>>dist;
lt1.dele (dist);
lt1.display();
cout<<"第二个链表:";
int num2,val2;
cout<<"输入要增加节点的位置和数据:";
cin>>num2>>val2;
lt2.insert (num2,val2);
lt2.display ();
cout<<"输入要删除的节点位置:";
int dist2;
lt2.dele (dist2);
lt2.display ();
}
if(n==3)
{
lt1.display ();
lt2.display ();
lt1.add (lt2);
lt1.display ();
lt2.display ();
}
return 0;
}
