链式线性表.cpp

数据结构中线性表链式结构的操作

typedef struct LNode{
		  int  data;
		 struct LNode    *next;
	 }LNode, *LinkList;

//输出链表
void printList(LNode *L)                
{
   LNode *p;
   p=L->next;
   if(p==NULL)
	   printf("线性表是空的！\n");
   else
   {
     printf("Output List:\n");
	 while(p!=NULL)
     {
		 printf("%d\n",p->data);
		 p=p->next;
	 }  
   }

}
//创建一个链表 
 void CreateList(LinkList L)   
 {  LNode *p1,*p2;
	   int a;
	   printf("Creating a List ......\n");
       printf("Please input a number (if (0) stop)\n");
	   scanf("%d",&a);
	   while(a!=0)
	   {
	     p1=(LNode*)malloc(sizeof (LNode));
		 p1->data=a;
		 if(L->next==NULL)
		 {L->next=p2=p1;}
		 else
		 {
			 p2->next=p1;
			p2=p1;
		 }
		 scanf("%d",&a);
	   }
	   
	   if(L->next==NULL)
             printf("线性表为空!\n");
          else p2->next=NULL;
 }
//在第i个位置之前插入元素e
 int ListInsert(LinkList L, int i, int e)
{
	int j=0;
 LNode *p,*s;
  p=(LNode*)malloc(sizeof(LNode));
  s=(LNode*)malloc(sizeof(LNode));
  p=L;
  while(p&&j<i-1)
  {  p=p->next; ++j ;}  //寻找第i-1 结点
  if(!p||j>i-1)  return  0;
   s=(LNode*)malloc(sizeof (LNode));
   s->data=e;
   s->next=p->next;
   p->next=s;
   return   1;
}
//获得第i个指针所指向的元素,赋值给e
int Getelem(LinkList L, int i)
{
	int  j=1,e;
	LNode *p;
    p=(LNode*)malloc(sizeof (LNode));
	p=L->next;
       while(p&&j<i)
	   {
		   p=p->next;
	      j++;
	   }
	   if (!p||j>i)  return 0;        //元素不存在
	    e=p->data;
		return e;
}
//删除链表中第i 个元素
int ListDelete(LinkList L,int i)
 {
   int j=0,e;
   LNode *p,*q;
   p=(LNode*)malloc(sizeof (LNode));
   p=(LNode*)malloc(sizeof (LNode));
   p=L->next;
   while(p&&j<i-1)
   {
	   p=p->next;
	   ++j;}
   if(!p||j>i-1)
          return  0;
   else
	   q=p->next;
       p->next=q->next;
	   e=q->data;
	   printf("%d\n",e);
	   printf("删除成功！");
	   free(q);     return  1;
}
//删除掉这个链表
 void DestroyList(LinkList L)
 {
    LNode *p;
	p=L->next;
	while(p!=NULL)
	{
		L->next=p->next;
		free(p);
		p=L->next;
	}
 
 }
 //计算线性表的长度
 int ListLength(LinkList L)
 {   LNode *p;
      int a=0;
	 p=L->next;
    while(p)
	{
		p=p->next;
        a++; 
	}
	return  a;
 }
//删除相同元素
void DeleteSameList(LinkList L)
{
   LNode *p,*q;
   p=L->next;
   if(p!=NULL)
   {
      q=p->next;
	  while(q!=NULL)
	  
         if(p->data==q->data)
		  {
				p->next=q->next;
			  free(q);
			  q=p->next;
		  }
		  else
		  {
		   p=q;
		   q=q->next ;
		  }
 }

} 
//求交集
void ConsameEle(LinkList a ,LinkList b,LinkList C)

 {
	 LNode *p,*q,*r;
	 p=(LNode*)malloc(sizeof(LNode)); 
	 q=(LNode*)malloc(sizeof(LNode));
     r=(LNode*)malloc(sizeof(LNode));
	 p=a->next;
	 q=b->next;
	 r=C;
	 while(p!=NULL&&q!=NULL)
	 {
		 if(p->data<q->data)
			 p=p->next;
		 if(p->data>q->data)
			 q=q->next;
		 else
		 {
		    r->next=p;
			r=r->next;
			p=p->next;
			q=q->next;
		 }
	 }

}


//删除a中同时在b和c中出现的元素
 void DelsaList(LinkList a, LinkList b, LinkList c)
 {  
	 LNode *p,*q,*r,*s;
     p=(LNode*)malloc(sizeof(LNode));
	 q=(LNode*)malloc(sizeof(LNode));
	 r=(LNode*)malloc(sizeof(LNode));
     s=a;
     p=a->next;
	 q=b->next;
	 r=c->next;
	 while(q&&r)
	 {
		 if(q->data<r->data)
			 q=q->next;
		  if(q->data>r->data)
			  r=r->next;
		  else
		{
		  
		    while(p)
			  {
				  if(p->data==q->data)
					  {    
						  s->next=p->next;
						   free(p);
						   p=s->next;
					  }
						   
				  else
					   { s=s->next;  p=p->next;}
			  }
		  s=a;
		  p=a->next;
		  q=q->next;
		  r=r->next;
		 }
         
	 }
 }