| //首先是Link类的实现
#include
template
class Link
{
public:
Elem element;
Link *next;
Link(const Elem& eleval,Link* nextval=NULL)
{
element=eleval;
next=nextval;
}
Link(Link *nextval=NULL){next=nextval;}
};
//下面是Llist类的实现
#include"link_h.h"
#include
template
class LList
{
public:// 这里声明为public型，因为private型发现无法访问 ？
Link* head;
Link* tail;
Link* fence;
int leftcnt;
int rightcnt;
void init()
{
fence=tail=head=new Link;
head->next=fence;
leftcnt=rightcnt=0;
}
void removeall ()
{
while(head->next!=head)
remove2(1);
}
public:
LList () {init();}
~LList() {removeall();}
void clear() {removeall(); init();}
bool insert(const Elem);
bool append(const Elem&);
bool remove( Elem&);
bool remove2(const Elem&);
bool find(const Elem&);
void setstart()
{if(head==tail)
return;
fence=head;
rightcnt+=leftcnt;
leftcnt=0;}
void setend()
{if(head==tail)
return;
fence=tail;
leftcnt+=rightcnt;
rightcnt=0;}
void prev();
void next()
{if (fence!=tail)
{fence=fence->next;
leftcnt++;
rightcnt--;}
else
setstart();
}
int leftLength() const {return leftcnt;}
int rightLength() const {return rightcnt;}
bool setPos(int pos);
bool getvalue(Elem& it)const{
if (leftcnt==rightcnt==0)
return false;
it=fence->next->element;
return true;
}
void print ()const;
};
template
bool LList::insert(const Elem item){
fence->next=new Link(item,fence->next);
if(fence==tail)
tail=fence->next;
fence=fence->next;
leftcnt++;
return true;
}
template
bool LList::append(const Elem& item)
{
tail=tail->next=new Link(item,head);
rightcnt++;
if(fence==head)
{fence=head->next;
leftcnt++;
rightcnt--;
}
return true;
}
template
bool LList::remove( Elem& item){
if(head==tail)
return false;
Link* ltemp=fence->next;
item=ltemp->element;
fence->next=ltemp->next;
if (ltemp==tail)
{delete ltemp;
tail=fence;
rightcnt--;
return true;
}
if (ltemp==head)
{delete ltemp;
head=fence->next;
leftcnt--;
return true;
}
delete ltemp;
rightcnt--;
return true;
}
template
bool LList::remove2(const Elem& item)
{
Link*temp1=head;
if(item<=0||item>(leftcnt+rightcnt))
return false;
int i;
if(item==1)
{fence=head;
if(head->next->next==head)
{delete head->next;
tail=head->next=head;
leftcnt--;
return true;
}
if(head->next->next!=head)
{ Link * temp5;
temp5=head->next;
head->next=temp5->next;
delete temp5;
setstart();
rightcnt--;
fence=head->next;
rightcnt--;
leftcnt++;
return true;
}
}
setPos(item-1);
remove(i);
return true;
}
template
bool LList::find(const Elem& item){
Link* ltemp;
ltemp=head;
for(int i=1;inext;
if(ltemp->element==item)
cout<<"the position is:"<element<<'\n';
}
return true;
}
template
void LList::prev(){
Link* ltemp;
ltemp=head;
while(ltemp->next!=fence)
ltemp=ltemp->next;
if(fence==head)
setend();
else
{fence=ltemp;
leftcnt--;
rightcnt++;
}
}
template
bool LList::setPos(int pos){
if ((pos<0)||(pos>(leftcnt+rightcnt)))
return false;
setstart();
for(int i=0;inext;
rightcnt--;
leftcnt++;
}
return true;
}
template
void LList::print() const
{
Link* temp;
temp=head->next;
if(head==tail)
{cout<<'|';
return;
}
while(temp!=fence)
{
cout<element<<' ';
temp=temp->next;
}
while(temp==fence)
{
cout<<' '<element<<'|';
temp=temp->next;}
while(temp!=tail->next)
{
cout<element<<' ';
temp=temp->next;
}
}
void main(){
LList intLList;
//intLList.print();
cout<<"\n 1. 清除 ";
cout<<"\n 2. 插入 ";
cout<<"\n 3. 追加 ";
cout<<"\n 4. 删除fence后面元素 ";
cout<<"\n 5. 删除指定位置的节点 ";
cout<<"\n 6. 查找链表元素的位置 ";
cout<<"\n 7. 查看该链表当前状态 ";
cout<<"\n 8. exit \n";
cout<<" (注:本程序中head指针始终指向一个空内存，清除时不会清除该节点 #_#)\n";
char choice;
do{
cout<<"\nplease input your choice:\n";
cin>>choice;
switch(choice)
{
case '1':
cout<<"removeall?? Yes or No\n";
char flag;
cin>>flag;
if(flag=='y')
intLList.removeall();
intLList.print();
break;
case '2':
cout<<"\nPlease input the data:";
int it1;
cin>>it1;
intLList.insert(it1);
intLList.print();
break;
case '3':
cout<<"plesase input the data you want appand:\n";
int it3;
cin>>it3;
intLList.append(it3);
intLList.print();
break;
case '4':
cout<<"即将删除fence后面的元素！！！\n";
int it2;
intLList.remove(it2);
intLList.print();
break;
case '5':
cout<<"请输入要删除的数据的位置:\n";
cout<<"该数字必须大于0，小于等于"<<(intLList.leftLength()+intLList.rightLength())<<'\n';
int it;
cin>>it;
intLList.remove2(it);
intLList.print();
break;
case '6':
cout<<"please input the date you want to find:\n";
int it4;
cin>>it4;
intLList.find(it4);
intLList.print();
break;
case '7':
cout<<"output the information:\n";
cout<<"leftcnt:"<next->element;
cout<<"\nthe tail element is:"<element;
cout<<"\n表头元素:"<next->next->element;
case '8':
break;
default:
cout<<"you input a invalid choice.";
}
}while(choice!='8');
觉得程序很是有多余的地方，可是自己已经无法修改了，请批评！！！
|
