list.txt

数据结构中的链表的实现

#include <iostream.h>
#include <malloc.h>
#define Null 0

typedef int elemtype;

typedef struct linknode 
{ elemtype data;
  struct linknode *next;
}node;

class List 
{
protected:
	node *head;
    
public:
    List (){ head=Null;}
	void emplist();
	void destlist();
	void creatlist ();
	void displist ();
	int listlen();
	node *findnode (int i);
	void insnode (int i,elemtype x);
	void delenode(int i);
    node  *nextlist(int i);
	node *priorlist(int i);
	void clearlist ();
    void locateElem(elemtype x);
	void visit(node *p1);
	void trverlist();
};

 
void List ::locateElem(elemtype x)
{  node *p=head;
   for(int i=1;i<=listlen();i++)
   {if(p->data==x){cout<<"it's locate place is :"<<i<<endl;
       break;}
        else {p=p->next;
       if(i==listlen()&&p->data!=x)
	   {cout<<"x is not exist"<<endl;break;}}

}
}
void List::visit(node *p1)
{node *p=p1;
  
  if(p->data!=Null)
	{ cout<<p->data <<endl;
  p=p->next ; }
  else cout<<"ending"<<endl; 
}
void List::trverlist ()
{node *p=head;
   for(int i=1;i<=listlen();i++)
   { visit(p) ;
  p=p->next ;}
	
 
}
  
void List ::emplist()
{node *p=head;
 if(p==Null)
	 cout <<"true"<<endl;
 else cout <<"faulse"<<endl;}

void List ::clearlist()
{node *p=head;
 if(p==Null)
	{ cout <<"this  is a empty list ,不需 要置空"<<endl;}
 else {while (p!=Null) 
{p->data=Null;
      p=p->next;}
 cout<<"链表已清空！"<<endl;}
}
 

void List ::destlist()
{node *p=head->next;
while (p->next!=Null)
{
 free (head);
 head=p;
 p=head->next;}
 free(head);
 free(p);
 head=p=Null;
cout<<"链表已毁！"<<endl;
}

 int List ::listlen()
 {int i=0;
    node *p=head;
   while (p!=Null)
   {p=p->next;
      i++;}
   return i;
 }

void List ::creatlist()
{   elemtype d; 
	node *h=Null,*s,*t;
    int i=1;
	cout <<" 创建单链表"<<endl;
	while (1)
	{cout <<"输入第"<<i<<"节点data 域:";
	 cin >>d;
	 if(d==0) break;
	 if (i==1)
	 {h=(node*)malloc(sizeof(node));
	 h->data=d;h->next=Null;t=h;}
	 else 
	 {s=(node*)malloc(sizeof(node));
	  s->data=d;s->next=Null;t->next=s;
	  t=s;}
	 i++;
	}
	head=h;
}

node *List ::findnode(int i)
{node *p=head;
 int j=1;
 if(i>listlen()||i<=0)
	 return Null;
 else 
 {while (p!=Null && j<i)
 {j++;
  p=p->next;
 }
 return p;
 }
}

void List ::displist()
{ node *p=head;
 if (p==Null) cout <<"this is no list"<<endl;
while (p!=Null)
{ cout <<p->data<<endl;
  p=p->next;}
cout <<endl;
}

void List ::insnode(int i,elemtype x)
{if(i<0||i>listlen())
 cout <<"value error"<<endl;
 node *a=(node*)malloc(sizeof(node));
  a->data=x;
if(i==0)
{a->next=head; head=a;
cout<<"插入成功！"<<endl;}
else 
{ node *p=findnode(i);
  a->next=p->next;
  p->next=a;
cout<<"插入成功！"<<endl;}

} 

void List ::delenode(int i)
{node *h=head;
	if(i<0||i>listlen())
 cout <<"error"<<endl;
 else 
 { if (i!=1)
	 {node *p=findnode(i-1);
   p->next=p->next->next;}
 else {h->data=Null;h=h->next;}
 cout<<i<<"has been delret."<<endl;}
}

node * List ::nextlist(int i)
{node *p=Null;
	if(i<0||i>=listlen())
	{cout <<"error"<<endl;}

   else 
{ p=findnode(i+1);
   
   }
 return p;
 
}

node *List ::priorlist(int i)
{node *p=Null;
   if (i<=0||i>listlen())
   {cout <<"error"<<endl;}
   else 
   {p=findnode(i-1);}
 
   return p;
}
    
    
   
 
 
   

void main()
{List a;
 a.creatlist();
 cout<<  a.listlen()<<endl;
  cout<<  a.findnode(2)<<endl;
  
  a.insnode (2,3);
   
 a.displist();
 
 a.delenode(1);
  
 a.displist();
 
 a.emplist();
 
  
  a.displist();
  
  a.locateElem(2);
 
  a.trverlist ();
  cout << <<a.nextlist(2)<<endl;
  cout << a.priorlist(2)<<endl;
    
  a.clearlist();
   
  a.destlist();
   
  a.emplist();
   
  a.displist();
 

 
}