l2_2.cpp

《数据结构（C++描述）》-李根强-源代码

//单链表的建立、插入、删除、查找
#include<iostream.h>
struct link
{   int  data; //元素类型
 link     *next;   //指针类型,存放下一个元素地址
};
  
//头插法建立带头结点的单链表
link *hcreat( )
  { link *s,*p;
   int i;
   cout<<"输入结点数值，为0时算法结束";
   cin>>i;       
   p=new link;
   p->next=NULL;
   while(i)
   { s=new link;
     s->data=i;
     s->next=p->next;
     p->next=s;
     cin>>i;     }
return p;
}

//输出单链表
 void print(link *head)
 {  
 link *p;
    p=head->next;
    while(p->next!=NULL)
  { 
 cout<<p->data<<"->"; //输出表中非最后一个元素
p=p->next;
  }
  cout<<p->data;   //输出表中最后一个元素
 cout<<endl;
}
 
 
 link *Locate(link *head,int x) //在单链表中查找值为x的结点
  {
 link *p;
   p=head->next;
   while((p!=NULL)&&(p->data!=x))
   p=p->next;
   return p;
   
   }

  link *delete1(link *head,int x)
//在head为头指针的单链表中,删除值为x的结点
  { 
link *p,*q;
   q=head;
   p=head->next;
   
   while((p!=NULL)&&(p->data!=x))
   {
     q=p;
     p=p->next;}
      if(p==NULL)cout<<"要删除的结点不存在";
   else
   {  
q->next=p->next;
delete(p);
   }
   return head;
      }


 link  *insert(link *head,int x,int  y)
//在头指针head所指单链表中,在值为y的结点之后插入值为x的结点
{
 link *p,*s;
  s=new link;
  s->data=x;
    if(head->next==NULL)  //链表为空
  {
 head->next=s;
s->next=NULL;
  }
	
p=Locate(head,y);       //调用查找算法
 
 if(p==NULL)
   cout<<"插入位置非法";
   else
   {  s->next=p->next;
p->next=s;
}
 return head;//在单链表中查找值为x的结点
 }


 void main()
 {
	 int x,y;
	 link *p;
	 p=hcreat(); //头插法建立链表
	 print(p);    //输出刚建立的单链表
	 cout<<"请输入要删除的元素";
	 cin>>y;
	 p=delete1(p,y);
	 print(p);//输出删除后的结果
	 cout<<"请输入待插元素位置及值";
	 cin>>x>>y;
	 p=insert(p,x,y);
	 print(p);//输出插入后的结果 
 }