插入与删除（有头结点）.cpp

数据结构实验--实现链表的插入与删除（源码

/*	实验内容
1．链表是有序的，现在删除数据x，若x不存在，输出一段提示信息。
（有头结点）
2．线性表v的数据递增有序，试将x插入表中并保持有序性
   (2)链表表示（有头结点）
*/

#include <stdlib.h>
#include<iostream.h>
#include<stdio.h>
#include<conio.h>
typedef struct node
{  
	int data;
    node *next;

}LNode,*Listlink;


void wcreate(Listlink *head,int n)//尾插法实现链表的插入

{

    int i;

    Listlink p,q;

       cout<<"尾插法---请输入元素: "<<endl;

    *head=(Listlink )malloc(sizeof(struct node));//生成一个头结点

    (*head)->next=NULL;

    q=*head;//q始终指向终端结点，开始时指向头结点

    for(i=0;i<n;i++)
	{

       p=(Listlink)malloc(sizeof(struct node));//生成一个新的结点

       scanf("%d",&(p->data));

       p->next=q->next;

       q->next=p;//将p插入到q之后

       q=p;

    }

}
/*LNode*creat(int tag)//创建链表，实现以tag的值作为结束标志
{
	int x;
	LNode*p,*r,*h=(LNode*)malloc(sizeof(LNode));
	r=h;
	printf("输入元素：");
	scanf("%d",&x);
	while(x!=tag)
	{
		p=(LNode*)malloc(sizeof(LNode));
		p->data=x;
		r->next=p;
		r=p;
		scanf("%d",&x);
	}
	r->next=NULL;
	return h;
}
*/
/*void qcreate(Listlink *head,int n)//头插法实现链表的创建

{

    int i;

    Listlink p;

       cout<<"前插法---请输入元素: "<<endl;

    *head=(Listlink )malloc(sizeof(struct node));

    (*head)->next=NULL;

    for(i=0;i<n;i++)

    {

       p=(Listlink)malloc(sizeof(struct node));

       scanf("%d",&(p->data));

       p->next=(*head)->next;

       (*head)->next=p;

    }

}
*/
void printf(LNode *head)//输出数据

{

     Listlink p;

     p=head->next;

     while(p!=NULL)

     {

       cout<<p->data<<" ";

       p=p->next;

     }

   cout<<endl;

}

LNode *find(LNode *h,int i,int m)//在链表h的m个数据中查找要插入的结点i
{

     LNode *p=h;

     int j=1;

     if(i>m+1||i<0)  return NULL;//要插入的结点不存在

     else
	 {

       while (p!=NULL&&j<i)
		 {
		   j++;
		   p=p->next;
		 }

        return p;

     }

}

LNode *insert(LNode *h,int i,int x,int m)//在链表h的第i个结点前插入数据x，总共有m个数据
{

     LNode *p,*s;
     
	 s=(LNode *)malloc(sizeof(LNode));
     
	 s->data=x;
	 
	 s->next=NULL;
     
	 if(i==0){s->next=h;h=s;}
       
	 else{

                p=find(h,i,m);

                if(p!=NULL)
				{

                       s->next=p->next;

                       p->next=s;

                }

        else cout<<"输入的结点不存在！"<<endl;

        }

        return h;

}

LNode *del(LNode *h,int i,int m)//在链表h中删除结点i，总共数据有m个
{

       LNode *p=h,*s;

       int j=1;

       if(i==1)
	   {
		   h=h->next;
		   free(p);
	   }

       else
	   {
		   p=find(h,i,m);//找到结点i

           if(p!=NULL&&p->next!=NULL)
	   
		   {
		       s=p->next;
		       p->next=s->next;//删除s结点
		       free(s);
		   }

          else 
		    cout<<"输入的结点不存在！"<<endl;
	   }

     return h;

}

void main()

{  

   Listlink a;

   int n,q,x,y,r,e,g;

   cout<<"请输要创建的元素个数: ";

   cin>>n;

   /*cout<<"请选择创建链表方法:1.前插法 2.尾插法 "<<endl;

   cin>>r;

   switch(r)
   {

   case 1:qcreate(&a,n);break;

   case 2:wcreate(&a,n);break; 
   }*/

   wcreate(&a,n);
   //creat(0);
   cout<<"创建成功!\n";

   printf(a);
   char yes;
   
   yes='y';
    do
	{
       cout<<"请选择操作:1.插入结点 2.删除结点"<<endl;

       cin>>e;
 
       switch(e)
	   {

          case 1: cout<<"请输入要插入的元素值:";
	              cin>>q;
	              cout<<"请输入要在那个结点前插入"; 
                  cin>>x;
		          a=insert(a,x,q,n);
		          cout<<"操作后的链表值为:"<<endl;
		          printf(a);
		          break;
          case 2: cout<<"请输入你要删除的结点: "<<endl;
	              cin>>y;
	     	      a=del(a,y,n);
		          cout<<"删除成功,链表值为:";
		          printf(a);
		          break; 

	   }  
	 cout<<"是否要继续？y/n"<<endl;
	 cin>>yes;
	}while(yes=='y');

}