单链表的运算.cpp

一个小小的数据结构程序

//-------------------实验三、单链表的运算-------------------------
#include <iostream>
#include <sstream>
using namespace std;
//----------------------------------------------------------------
class node{                                //结点类定义
public:	
	string nodevalue;
	node *next;

	node():next(NULL){}                    //构造函数  
    node(const string item,node *nextnode=NULL):nodevalue(item),next(nextnode){}
};//---------------------------------------------------------------
class L{                                  //单链表类声明
	node *head;                           //结点成员
    static int length;
public:
	L();                                  //构造函数
	bool isListEmpty();                   //判空成员函数
	int ListLength();                     //求表长成员函数
	void DispList();                      //打印单链表函数
	node* GetElem(int pos);               //根据位置找结点
    int LocateElem(string elem);          //查找元素在表中第一次出现的位置
	void ListInsert(string &elem,int pos);//在表中插入一个结点
	int ListDelete(int pos);              //删除一个结点   
	void ListDelete(string &elm);         //重载删除函数
	~L(){}                                //析构函数
};//---------------------------------------------------------------
int L::length=0;                          //初始化表长 
L::L(){                                   //单链表的构造函数定义  
      node *p,*curr;
      string tmp;
      cout<<"请输入字符"<<endl;
      cin>>tmp;
	  if(tmp=="0"){
          length=0;
		  head=NULL;
		  }
      else{
          head=new node(tmp);
          length=1;
          p=head;
		  while(1){
		  cin>>tmp;
		  if(tmp=="0"){
			  p->next=NULL;
			  break;
		  }
		  else{
		  curr=new node(tmp);
	      p->next=curr;
		  p=curr;
	      length++;
		  }
		  }
		  p->next=NULL;
		  }
}//---------------------------------------------------------------
bool L::isListEmpty(){                     //单链表判空函数声明 
	if(length==0)
		return 1;
	else
		return 0;
}//---------------------------------------------------------------

int L::ListLength(){                       //求表长
	return length;
}//---------------------------------------------------------------

void L::DispList(){                        //显示单链表
	node *curr;
	curr=head;
	cout<<"单链表中的元素为:"<<endl;
	if(this->isListEmpty())
		cout<<'\b'<<"空"<<endl;
	else{
		for(int i=1;i<=length;i++){
		cout<<i<<'.'<<curr->nodevalue<<endl;
		curr=curr->next;
		}
		cout<<"单链表中的元素个数为:"<<length<<endl<<endl;
	}
}//---------------------------------------------------------------
node* L::GetElem(int pos){                //根据位置查找，返回结点指针
	node *curr;
	curr=head;
	if(pos>length)
		return NULL;
	else{
		for(int i=1;i<pos;i++)
			curr=curr->next;
		return curr;
	}
}//---------------------------------------------------------------
int L::LocateElem(string elem){            //根据元素查找位置，返回元素的序号   
	node *curr;int n=1;
	curr=head;
	while(curr!=NULL&&curr->nodevalue!=elem){
		curr=curr->next;
		n++;
	}
	if(curr==NULL)
		return(0);
	else
		return(n);
}//---------------------------------------------------------------
void L::ListInsert(string &elem,int pos){  //将elem插入到表的第pos处
	node *curr,*s;
	int j=1;
	if(pos==1){                            //插入到头结点    
		curr=new node(elem,head);
		head=curr;
		length++;
	}
	else if(pos-1==length){                //插入到尾结点
		curr=this->GetElem(pos-1);
		curr->next=new node(elem);
		length++;
	}
	else if(pos>1&&pos<=length){           //插入到中间位置
		curr=head;
		while(j<pos-1){
			curr=curr->next;
			j++;
		}
		s=new node(elem);
		s->next=curr->next;
		curr->next=s;
		length++;
	}
	else
		cout<<"插入位置不合适！"<<endl;

}//---------------------------------------------------------------
int L::ListDelete(int pos){               //删除第pos个元素，根据返回值判断是否成功
	node *curr,*s;
	int j=0;
	curr=this->GetElem(pos-1);
	if((curr->next==NULL)||(j>pos-1))
		return 0;
	if(pos==1&&(length>1)){                //删除头结点   
			s=head;
			head=head->next;
			free(s);
			length--;
			return 1;
	}
	else if(pos==length&&(length>1)){      //删除尾结点
			s=curr->next;
			curr->next=NULL;
			free(s);
			length--;
			return 1;
	}
	else if(length==1){
		free(head);
		length=0;
	}
	else{                                 //删除普通结点
			s=curr->next;
		    curr->next=s->next;
		    free(s);
		    length--;
			return 1;
	}
}//---------------------------------------------------------------
void L::ListDelete(string &elm){           //删除元素elm   
	int j=1;
	j=this->LocateElem(elm);
	if(j!=0){
		cout<<elm<<"的位置是"<<j<<endl;		
		this->ListDelete(j);
	}
}//---------------------------------------------------------------
int menu1(){                               //根菜单 
	int i=0;
	cout<<"【1】"<<"插入元素"<<endl<<"【2】"<<"删除元素"<<endl;
	cout<<"【3】"<<"查找元素"<<endl<<"【4】"<<"显示单链表"<<endl;
	cout<<"【5】"<<"退出"<<endl;
	cout<<"输入操作的序号:";
	cin>>i;
	cout<<endl;
	if((i<=0)||(i>5))
		menu1();
	else
		return(i);
};//---------------------------------------------------------------
int menu2(){                            //删除操作选择菜单
	int j;
	cout<<"【1】"<<"按元素的位置删除"<<endl;
	cout<<"【2】"<<"按元素的值删除"<<endl;
	cout<<"【3】"<<"返回主菜单"<<endl;
    cout<<"请选择操作：";
	cin>>j;
	cout<<endl;
	return j;
}//---------------------------------------------------------------
int menu3(){                              //查找操作选择菜单     
	int k;
	cout<<"【1】"<<"按元素的位置查找"<<endl;
	cout<<"【2】"<<"按元素的值查找"<<endl;
	cout<<"【3】"<<"返回主菜单"<<endl;
    cout<<"请选择操作：";
	cin>>k;
	cout<<endl;
	return k;
}//---------------------------------------------------------------
void main(){//----------------------主函数------------------------
	int i;string elem;
	L list;
	list.DispList();
loop:
	i=menu1();
	if(i==1){                              //插入
		int pos;
		cout<<"输入需要插入元素的值及插入位置：";
		cin>>elem>>pos;
		list.ListInsert(elem,pos);
		list.DispList();
		goto loop;
	}
	else if(i==2){                        //删除
		int returnvalue;
		returnvalue=menu2();
		if(returnvalue==1){               //删除指定位置的元素
			int pos;
			cout<<"请输入元素的位置:";
			cin>>pos;
			if(pos>list.ListLength())
				cout<<"删除位置不合适！"<<endl<<endl;
			else{
				cout<<endl<<"需要删除的元素是："<<list.GetElem(pos)->nodevalue<<endl;
				list.ListDelete(pos);
				cout<<"删除元素后，";
				list.DispList();
			}
			goto loop;

		}
		else if(returnvalue==2){           //删除指定元素
			string elm;
			cout<<"请输入元素的值:";
			cin>>elm;
			cout<<endl;
			list.ListDelete(elm);
			cout<<"删除元素后，";
			list.DispList();
		    goto loop;
		}
		else if(returnvalue==3)
			goto loop;
	}
	else if(i==3){                        //查找
		int returnvalue;
		returnvalue=menu3();
		if(returnvalue==1){               //查找指定位置的元素 
			int pos;
			cout<<"请输入元素的位置:";
			cin>>pos;
			if(list.GetElem(pos)==NULL)
				cout<<"----元素不存在！----"<<endl<<endl;
			else
				cout<<"第"<<pos<<"个元素是："<<list.GetElem(pos)->nodevalue<<endl<<endl;
			goto loop;
		}
		else if(returnvalue==2){          //查找指定元素
			string elm;
			cout<<"请输入元素的值:";
			cin>>elm;
			if(list.LocateElem(elm)==0)
				cout<<"----元素不存在！----"<<endl<<endl;
			else{
			cout<<"元素"<<elm<<"的位置是："<<list.LocateElem(elm)<<endl<<endl;
			}
			goto loop;
		}
		else if(returnvalue==3)           //返回根菜单
			goto loop;
	}
	else if(i==4){                        //打印单链表
		list.DispList();
		goto loop;
	}
	else if(i==5){                        //退出程序 
		exit(0);
		getchar();
	}
	else
		goto loop;
}//---------------------------------------------------------------