您所在位置：主题：[原创]双链表运用模板的实现
suimi
[专家分：0] 发布于 2007-05-15 20:55:00
#include <cstddef>
enum Error_code{success,overflow,underflow,range_error};
template <class Node_entry>
struct Node
{
Node_entry entry;
Node<Node_entry> *next;
Node<Node_entry> *back;
Node();
Node(Node_entry item,Node<Node_entry> *link_back,
Node<Node_entry> *link_next);
};
template<class Node_entry>
Node<Node_entry>::Node()
{link_back=NULL;
link_next=NULL;
}
template<class Node_entry>
Node<Node_entry>::Node(Node_entry item,Node<Node_entry>*link_back,Node<Node_entry>*link_next)
{entry=item;
back=link_back;
next=link_next;}
template <class List_entry>
class List{
public:
List();
void clear();
bool empty()const;
int size()const;
Error_code insert(int position,const List_entry &x);
Error_code replace(int position,const List_entry &x);
Error_code retrive(int position,List_entry &x)const;
Error_code remove(int position);
protected:
int count;
mutable int current_position;
mutable Node<List_entry>*current;
void set_position(int position)const;
};
template<class List_entry>
List<List_entry>::List()
{count=0;
current=NULL;
current_position=0;
}
template<class List_entry>
int List<List_entry>::size()const
{
return count;
}
template<class List_entry>
bool List<List_entry>::empty()const{
return count==0;
}
template<class List_entry>
void List<List_entry>::clear(){
while(!empty())remove(0);
}
template <class List_entry>
void List<List_entry>::set_position(int position)const
{
if(current_position<=position)
for(;current_position!=position;current_position++)
current=current->next;
else
for(;current_position!=position;current_position--)
current=current->back;
}
template<class List_entry>
Error_code List<List_entry>::remove(int position)
{
Node<List_entry>*following,*preceding;
if(position<0||position>count)return range_error;
if(position==0&&count==1)delete []current;
else
{
set_position(position);
following=current->next;
preceding=current->back;
if(following!=NULL)following->back=preceding;
if(preceding!=NULL)preceding->next=following;
delete []current;
if(following==NULL){
current=preceding;
current_position=position-1;
}
else{
current=following;
current_position=position;
}
}
count--;
return success;
}
template<class List_entry>
Error_code List<List_entry>::insert(int position,const List_entry &x)
{
Node<List_entry>*new_node,*following,*preceding;
if(position<0||position>count)return range_error;
if(position==0){
if(count==0)following=NULL;
else{
set_position(0);
following=current;
}
preceding=NULL;
}
else{
set_position(position-1);
preceding=current;
following=preceding->next;
}
new_node=new Node<List_entry>(x,preceding,following);
if(new_node==NULL)return overflow;
if(preceding!=NULL)preceding->next=new_node;
if(following!=NULL)following->back=new_node;
current=new_node;
current_position=position;
count++;
return success;
}
template<class List_entry>
Error_code List<List_entry>::retrive(int position,List_entry &x)const
{
set_position(position);
x=current->entry;
return success;
}
template<class List_entry>
Error_code List<List_entry>::replace(int position,const List_entry &x)
{
Node<List_entry>*new_node,*following,*preceding;
if(position<0||position>count)return range_error;
set_position(position);
preceding=current->back;
following=current->next;
new_node=new Node<List_entry>(x,preceding,following);
if(new_node==NULL)return overflow;
if(preceding!=NULL)preceding->next=new_node;
if(following!=NULL)following->back=new_node;
delete []current;
current=new_node;
current_position=position;
return success;
}
#include <iostream.h>
#include <ctype.h>
void help(){
cout<<"H:帮助;"<<" "
<<"A:顺序输入; "
<<"I:插入;"<<" "
<<"M:删除;"<<" "
<<"R:替代;"<<" "
<<"P:打印;"<<" "
<<"T:查看;"<<" "
<<"S:大小;"<<" "
<<"C:清空;"<<" "
<<"Q:退出."<<endl;
}
char get_command()
{
char command;
bool waiting=true;
cout<<"请输入命令并回车:";
while(waiting){
cin>>command;
command=tolower(command);
if(command=='h'||command=='i'||command=='m'
||command=='p'||command=='t'||command=='s'
||command=='q'||command=='r'||command=='c'
||command=='a')waiting=false;
else{
cout<<"请输入正确的命令："<<endl;
help();
waiting=true;
}
}
return command;
}
bool do_command(char command,List<int> &q){
switch(command){
int i,t;
case'h':
help();
break;
case'a':
cout<<"请输入你要写入的内容(中间用空格隔开,退出请输-1):";
while(1){
cin>>i;
while(i==-1)goto loop;
q.insert(q.size(),i);
}
loop:break;
case'i':
cout<<"请输入插入元素的位置和内容(退出请输-1):";
while(1){
cin>>i;
while(i==-1)goto kk;
cin>>t;
q.insert(i,t);
}
kk:break;
case'm':
cout<<"请输入删除元素的位置:";
cin>>i;
q.remove(i);
break;
case'r':
cout<<"请输入要替代元素的位置和要替代的内容:";
cin>>i>>t;
q.replace(i,t);
break;
case't':
cout<<"请输入要查看元素的位置:";
cin>>i;
q.retrive(i,t);
cout<<t<<endl;
break;
case's':
cout<<q.size()<<endl;
break;
case'p':
for(i=0;i<q.size();i++){
q.retrive(i,t);
cout<<t<<" ";}
cout<<endl;
break;
case'c':
q.clear();
break;
case'q':
char k,m;
i=3;k=i;
i=5;m=i;
cout<<'\t'<<'\t'<<k<<" 谢谢您的使用 "
<<m<<" "<<m<<" "<<m
<<" 欢迎下次光临 "<<k<<endl;
return false;
}
return true;
}
void main(){
List<int> q;
cout<<"本程序是双链表的实现，输入数据,修改并查看。"<<endl
<<"本程序的计数从0开始的，在用查看命令时应注意。"<<endl
<<"本程序仅供大家参考学习，如有建议与意见请与本人联系!"<<endl
<<"谢谢合作!"<<endl<<endl<<flush;
help();
while(do_command(get_command(),q));
}
enum Error_code{success,overflow,underflow,range_error};
template <class Node_entry>
struct Node
{
Node_entry entry;
Node<Node_entry> *next;
Node<Node_entry> *back;
Node();
Node(Node_entry item,Node<Node_entry> *link_back,
Node<Node_entry> *link_next);
};
template<class Node_entry>
Node<Node_entry>::Node()
{link_back=NULL;
link_next=NULL;
}
template<class Node_entry>
Node<Node_entry>::Node(Node_entry item,Node<Node_entry>*link_back,Node<Node_entry>*link_next)
{entry=item;
back=link_back;
next=link_next;}
template <class List_entry>
class List{
public:
List();
void clear();
bool empty()const;
int size()const;
Error_code insert(int position,const List_entry &x);
Error_code replace(int position,const List_entry &x);
Error_code retrive(int position,List_entry &x)const;
Error_code remove(int position);
protected:
int count;
mutable int current_position;
mutable Node<List_entry>*current;
void set_position(int position)const;
};
template<class List_entry>
List<List_entry>::List()
{count=0;
current=NULL;
current_position=0;
}
template<class List_entry>
int List<List_entry>::size()const
{
return count;
}
template<class List_entry>
bool List<List_entry>::empty()const{
return count==0;
}
template<class List_entry>
void List<List_entry>::clear(){
while(!empty())remove(0);
}
template <class List_entry>
void List<List_entry>::set_position(int position)const
{
if(current_position<=position)
for(;current_position!=position;current_position++)
current=current->next;
else
for(;current_position!=position;current_position--)
current=current->back;
}
template<class List_entry>
Error_code List<List_entry>::remove(int position)
{
Node<List_entry>*following,*preceding;
if(position<0||position>count)return range_error;
if(position==0&&count==1)delete []current;
else
{
set_position(position);
following=current->next;
preceding=current->back;
if(following!=NULL)following->back=preceding;
if(preceding!=NULL)preceding->next=following;
delete []current;
if(following==NULL){
current=preceding;
current_position=position-1;
}
else{
current=following;
current_position=position;
}
}
count--;
return success;
}
template<class List_entry>
Error_code List<List_entry>::insert(int position,const List_entry &x)
{
Node<List_entry>*new_node,*following,*preceding;
if(position<0||position>count)return range_error;
if(position==0){
if(count==0)following=NULL;
else{
set_position(0);
following=current;
}
preceding=NULL;
}
else{
set_position(position-1);
preceding=current;
following=preceding->next;
}
new_node=new Node<List_entry>(x,preceding,following);
if(new_node==NULL)return overflow;
if(preceding!=NULL)preceding->next=new_node;
if(following!=NULL)following->back=new_node;
current=new_node;
current_position=position;
count++;
return success;
}
template<class List_entry>
Error_code List<List_entry>::retrive(int position,List_entry &x)const
{
set_position(position);
x=current->entry;
return success;
}
template<class List_entry>
Error_code List<List_entry>::replace(int position,const List_entry &x)
{
Node<List_entry>*new_node,*following,*preceding;
if(position<0||position>count)return range_error;
set_position(position);
preceding=current->back;
following=current->next;
new_node=new Node<List_entry>(x,preceding,following);
if(new_node==NULL)return overflow;
if(preceding!=NULL)preceding->next=new_node;
if(following!=NULL)following->back=new_node;
delete []current;
current=new_node;
current_position=position;
return success;
}
#include <iostream.h>
#include <ctype.h>
void help(){
cout<<"H:帮助;"<<" "
<<"A:顺序输入; "
<<"I:插入;"<<" "
<<"M:删除;"<<" "
<<"R:替代;"<<" "
<<"P:打印;"<<" "
<<"T:查看;"<<" "
<<"S:大小;"<<" "
<<"C:清空;"<<" "
<<"Q:退出."<<endl;
}
char get_command()
{
char command;
bool waiting=true;
cout<<"请输入命令并回车:";
while(waiting){
cin>>command;
command=tolower(command);
if(command=='h'||command=='i'||command=='m'
||command=='p'||command=='t'||command=='s'
||command=='q'||command=='r'||command=='c'
||command=='a')waiting=false;
else{
cout<<"请输入正确的命令："<<endl;
help();
waiting=true;
}
}
return command;
}
bool do_command(char command,List<int> &q){
switch(command){
int i,t;
case'h':
help();
break;
case'a':
cout<<"请输入你要写入的内容(中间用空格隔开,退出请输-1):";
while(1){
cin>>i;
while(i==-1)goto loop;
q.insert(q.size(),i);
}
loop:break;
case'i':
cout<<"请输入插入元素的位置和内容(退出请输-1):";
while(1){
cin>>i;
while(i==-1)goto kk;
cin>>t;
q.insert(i,t);
}
kk:break;
case'm':
cout<<"请输入删除元素的位置:";
cin>>i;
q.remove(i);
break;
case'r':
cout<<"请输入要替代元素的位置和要替代的内容:";
cin>>i>>t;
q.replace(i,t);
break;
case't':
cout<<"请输入要查看元素的位置:";
cin>>i;
q.retrive(i,t);
cout<<t<<endl;
break;
case's':
cout<<q.size()<<endl;
break;
case'p':
for(i=0;i<q.size();i++){
q.retrive(i,t);
cout<<t<<" ";}
cout<<endl;
break;
case'c':
q.clear();
break;
case'q':
char k,m;
i=3;k=i;
i=5;m=i;
cout<<'\t'<<'\t'<<k<<" 谢谢您的使用 "
<<m<<" "<<m<<" "<<m
<<" 欢迎下次光临 "<<k<<endl;
return false;
}
return true;
}
void main(){
List<int> q;
cout<<"本程序是双链表的实现，输入数据,修改并查看。"<<endl
<<"本程序的计数从0开始的，在用查看命令时应注意。"<<endl
<<"本程序仅供大家参考学习，如有建议与意见请与本人联系!"<<endl
<<"谢谢合作!"<<endl<<endl<<flush;
help();
while(do_command(get_command(),q));
}