Question

C++中如何建立一个单链表 遍历 插入 删除 合并

Answer 1

这是我自己写的，代码如下
#pragma once

template<class T>
struct LinkNode
{
T data;
LinkNode<T> *next;
};

template<class T>
class LinkList
{
public:
LinkList();
LinkList(const LinkList<T>&);
~LinkList();
bool IsEmpty()const{return len<=0;}
int Length()const{return len;}
void Clear();
bool GetElem(T&,int)const;
bool SetElem(const T&,int);
int LocateElem(const T&)const;
int LocatePrior(const T&)const;
int LocateNext(const T&)const;
bool Insert(const T&,int);
bool Append(const T&);
bool Delete(T&,int);
void Traverse(void(*visit)(const T&))const;
LinkList<T>& operator=(const LinkList<T>&);

private:
int len;
LinkNode<T> *head;
LinkNode<T> *tail;
void CopyFrom(const LinkList<T>&);
};

template<class T>
LinkList<T>::LinkList()
{
len=0;
head=tail=new LinkNode<T>;
head->next=NULL;
}
template<class T>
LinkList<T>::LinkList(const LinkList<T>& r)
{
CopyFrom(r);
}
template<class T>
LinkList<T>::~LinkList()
{
Clear();
delete head;
}
template<class T>
void LinkList<T>::Clear()
{
LinkNode<T>* p=head->next,*q;
while(p)
{
q=p->next;
delete p;
p=q;
}
tail=head;
head->next=NULL;
len=0;
}
template<class T>
bool LinkList<T>::GetElem(T&e,int i)const
{
if(i<1 || i>len)
return false;
LinkNode<T> *p=head->next;
int k=1;
while(k<i)
{
p=p->next;
k++;
}
e=p->data;
return true;
}
template<class T>
bool LinkList<T>::SetElem(const T&e,int i)
{
if(i<1 || i>len)
return false;
LinkNode<T> *p=head->next;
int k=1;
while(k<i)
{
p=p->next;
k++;
}
p->data=e;
return true;
}
template<class T>
int LinkList<T>::LocateElem(const T&e)const
{
int i=1;
LinkNode<T> *p=head->next;
while(p && p->data!=e)
{
i++;
p=p->next;
}
if(p)
return i;
return 0;
}
template<class T>
int LinkList<T>::LocatePrior(const T&e)const
{
int i=LocateElem(e);
if(i>1)
return i-1;
else
return 0;
}
template<class T>
int LinkList<T>::LocateNext(const T&e)const
{
int i=LocateElem(e);
if(i>=1 && i<len)
return i+1;
else
return 0;
}
template<class T>
bool LinkList<T>::Insert(const T&e,int i)
{
LinkNode<T> *p,*q;
int k=1;
if(i<1 || i>len+1)
return false;
q=new LinkNode<T>;
q->data=e;
p=head;
while(k<i)
{
p=p->next;
k++;
}
q->next=p->next;
p->next=q;
if(i==len+1) //表尾插入后修改尾指针
tail=q;
++len;
return true;
}
template<class T>
bool LinkList<T>::Append(const T&e) //画图分析
{
LinkNode<T> *q;
q=new LinkNode<T>;
q->data=e;
tail->next=q;
tail=q; //漏了一句，要自己写，弄清原理
tail->next=NULL;
++len;
return true;
}
template<class T>
bool LinkList<T>::Delete(T&e,int i)
{
if(i<1 || i>len)
return false;
LinkNode<T> *p,*q;
int k=1;
p=head;
while(k<i)
{
p=p->next;
k++;
}
q=p->next;
p->next=q->next;
if(q==tail)
tail=q;
e=q->data;
delete q;
--len;
return true;
}
template<class T>
void LinkList<T>::Traverse(void (*visit)(const T&e))const
{
LinkNode<T>*p=head->next;
while(p)
{
visit(p->data);
p=p->next;
}

}
template<class T>
LinkList<T>& LinkList<T>::operator=(const LinkList<T>&r)
{
Clear();
delete head;
CopyFrom(r);
return *this;
}
template<class T>
void LinkList<T>::CopyFrom(const LinkList<T>& r)
{
len=0;
head=tail=new LinkNode<T>;
head->next=NULL;
LinkNode<T> *p=r.head->next;
while(p)
{
Append(p->data);
p=p->next;
}
}

#include<iostream>
#include"LinkList.h"

using namespace std;
void print(const int& e)
{
cout<<e<<" ";
}
int main()
{
LinkList<int> lt;
if(lt.IsEmpty())
cout<<"lt is empty,its length is "<<lt.Length()<<endl;
cout<<"input some numbers to the list,end with -100:"<<endl;
int num;
while(true)
{
cin>>num;
if(num==-100)
break;
lt.Append(num);
}

cout<<"Now lt's length is"<<lt.Length()<<endl;
cout<<"Now lt is "<<endl;
lt.Traverse(print);
cout<<endl;
LinkList<int> lt1(lt);
cout<<"lt1 is "<<endl;
lt1.Traverse(print);
cout<<endl;
LinkList<int> lt2=lt;
cout<<"lt2 is "<<endl;
lt2.Traverse(print);
cout<<endl;
lt1.Clear();
cout<<"after clear lt1 "<<endl;
cout<<"Now lt1's length is "<<lt1.Length()<<endl;
lt.SetElem(888,2);
cout<<"after set value 888 in the position 2 lt is "<<endl;
lt.Traverse(print);
cout<<endl;
lt.GetElem(num,2);
cout<<"lt's position 2 is "<<num<<endl;
cout<<num<<" is in the position "<<lt.LocateElem(num)<<endl;
cout<<num<<"'s prior position "<<lt.LocatePrior(num)<<endl;
cout<<num<<"'s next position "<<lt.LocateNext(num)<<endl;
lt.Insert(999,2);
cout<<"after inserting 2 in the position 2,lt is "<<endl;
lt.Traverse(print);
cout<<endl;
lt.Delete(num,2);
cout<<"after deleting 999,lt is "<<endl;
lt.Traverse(print);
cout<<endl<<"Good work !"<<endl;
system("pause");
return 0;
}