原创 单链表实现A-B操作

下面这个是头文件LinkList.h主要实现的是一些链表的基本操作：

#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>

#define ListSize 100

typedef int DataType;

typedef struct Node
{
 DataType data;
 struct Node *next;
}ListNode, *LinkList;

/*******************************************************************************
函数名:InitList(LinkList *head)
函数功能:单链表的初始化操作
入口参数:
出口参数:
********************************************************************************/
void InitList(LinkList *head)
{
/*将单链表初始化为空，动态生成一个头结点，并将
头结点的指针域置为空*/
 if((*head=(LinkList)malloc(sizeof(ListNode)))==NULL)/*为头结点分配
  一个存储空间*/
  exit(-1);
 (*head)->next=N****************************************************************
函数名:ListEmpty(LinkList head)
函数功能:判断单链表是否为空
入口参数:
出口参数:
********************************************************************************/
int ListEmpty(LinkList head)
{
/*判断单链表是否为空，就是通过判断头结点的指针域
是否为空*/
 if(head->next==NULL)/*判断单链表的头结点的指针域是否为空*/
  return 1;/*当单链表为空时，返回1，否则返回0*/
 else
  return 0;
}

/*******************************************************************************
函数名:         *Get(LinkList head, int i)
函数功能:  按序号查找操作
入口参数:
出口参数:
********************************************************************************/
ListNode *Get(LinkList head, int i)
{
/*查找单链表中第i个结点。查找成功返回该结点的指针表示成
功，否则返回NULL表示失败*/
 ListNode *p;
 int j;
 
 if(ListEmpty(head))/*在查找第i个元素之前，判断链表是否
  为空*/
  return NULL;
 
 if(i<1)/*在查找第i个元素之前，判断该序号是否合法*/
  return NULL;
 
 j=0;
 p=head;
 
 while(p->next != NULL && j<i)
  {
   p=p->next;
   j++;
  }
 if(j==i)/*查到第i个结点，返回指针p*/
  return p;
 else
  return NULL;/*如果没有找到第i个元素，返回NULL*/
}

/*******************************************************************************
函数名:        *LocateElem(LinkList head, DataType e)
函数功能:  按内容查找操作
入口参数:
出口参数:
********************************************************************************/
ListNode *LocateElem(LinkList head, DataType e)
{
/*查找线性表中元素值为e的元素，查找成功将对应元素
的结点指针返回，否则返回NULL表示失败*/
 ListNode *p;
 p=head->next;/*指针p指向第一个结点*/
 while(p)
  {
   if(p->data!=e)
    p=p->next;
   else
    break;/*如果等于e的话推出*/
  }
 return p;
}

/*******************************************************************************
函数名:        LocatePos(LinkList head,DataType e)
函数功能:  定位操作
入口参数:
出口参数:
********************************************************************************/
int LocatePos(LinkList head,DataType e)
{
/*查找线性表中元素值为e的元素，查找成功将对应元素
的序号返回，否则返回0表示失败*/
 ListNode *p;
 int i;
 if(ListEmpty(head))/*查找第i个元素之前判断链表是否为空*/
  return 0;
 p=head->next;/*指针p指向第一个结点*/
 i=1;
 while(p)
  {
   if(p->data==e)/*找到与e相等的元素，返回该序号*/
    return i;
   else
    {
     p=p->next;
     i++;
    }
  }
 if(!p) /*如果没有找到与e相等的元素，返回0表示失败*/
  return 0;
}

/*******************************************************************************
函数名:   InsertList(LinkList head, int i, DataType e)
函数功能:  插入操作
入口参数:
出口参数:
********************************************************************************/
int InsertList(LinkList head, int i, DataType e)
{
/*在单链表中第i个位置插入一个结点，结点元素值为e，插入
成功返回1，否则失败返回0*/
 ListNode *p,*pre;/*定义指向第i个元素的前驱结点指针pre
指针p指向新生成的结点*/
 int j;
 pre=head;/*指针p指向头结点*/
 j=0;
 while(pre->next != NULL && j<i-1)/*找到第i-1个结点，即第i个结点的
  前驱结点*/
  {
   pre=pre->next;
   j++;
  }
 if(j!=i-1)
  {
   printf("插入位置错");
   return 0;
  }
 /*新生成一个结点，并将e值赋给改结点的数据域*/
 if((p=(ListNode *)malloc(sizeof(ListNode)))==NULL)
  exit(-1);
 p->data=e;
 /*插入结点操作*/
 p->next=pre->next;
 pre->next=p;
 return 1;
}

/*******************************************************************************
函数名:  DeleteList(LinkList head, int i, DataType *e)
函数功能:  删除操作
入口参数:
出口参数:
********************************************************************************/
int DeleteList(LinkList head, int i, DataType *e)
{
/*删除单链表中的第i个位置的结点。删除成功返回1，失败返回
0*/
 ListNode *pre,*p;
 int j;
 pre=head;
 j=0;
 while(pre->next !=NULL && pre->next->next !=NULL && j<i-1)
  {
   pre=pre->next;
   j++;
  }
 if(j!=i-1)
  {
   printf("删除位置错误");
   return 0;
  }
 /*指针p指向单链表中的第i 个结点，并将该结点的数据域
 值赋给e*/
 p=pre->next;
 *e=p->data;
 /*将前驱结点的指针域指向要删除结点的下一个结点，也
 就是将p指向的结点与单链表断开*/
 pre->next=p->next;
 free(p);/*释放p指向的结点*/
 return 1;
}

/*******************************************************************************
函数名: ListLength(LinkList head)
函数功能: 查表长度操作
入口参数:
出口参数:
********************************************************************************/
int ListLength(LinkList head)
{
 ListNode *p;
 int count=0;
 p=head;
 while(p->next != NULL)
  {
   p=p->next;
   count++;
  }
 return count;
}

/*******************************************************************************
函数名: DestroyList(LinkList head)
函数功能: 销毁链表操作
入口参数:
出口参数:
********************************************************************************/
void DestroyList(LinkList head)
{
 ListNode *p,*q;
 p=head;
 while(p != NULL)
  {
   q=p;
   p=p->next;
   free(q);
  }
}

下面是主程序：

#include"LinkList.h"

/*******************************************************************************
函数名:main()
函数功能:主函数
入口参数:
出口参数:
********************************************************************************/
void DelElem(LinkList A,LinkList B)
{
 int i,pos;
 DataType e;
 ListNode *p;
 /*在单链表B中，取出每个元素与单链表A中的元素比较
 如果相等则删除A中元素对应的结点*/
 for(i=1; i<=ListLength(B); i++)
  {
   p=Get(B, i);
   if(p)
    pos=LocatePos(A, p->data);
   if(pos>0)
    DeleteList(A, pos, &e);
  }
}

/*******************************************************************************
函数名:main()
函数功能:主函数
入口参数:
出口参数:
********************************************************************************/
void main()
{
 int i;
 DataType a[]={2,3,6,7,9,14,56,45,65,67};
 DataType b[]={3,4,7,11,34,54,45,67};
 
 LinkList A,B;/*声明单链表A和B*/
 ListNode *p;
 
 InitList(&A);/*初始化单链表A*/
 InitList(&B);/*初始化单链表B*/

 for(i=1; i<=sizeof(a) / sizeof(a[0]); i++)
  {
   if(InsertList(A, i, a[i-1])==0)
    {
     printf("位置不合法");
     return;
    }
  }
 for(i=1; i<=sizeof(b) / sizeof(b[0]); i++)
  {
   if(InsertList(B, i, b[i-1])==0)
    {
     printf("位置不合法");
     return;
    }
  }
 printf("单链表A中的元素有%d个:\n",ListLength(A));
 for(i=1; i<=ListLength(A); i++)
  {
   p=Get(A,i);
   if(p)
    printf("%4d",p->data);
  }
 printf("\n");
 printf("单链表B中的元素有%d个:\n",ListLength(B));
 for(i=1; i<=ListLength(B); i++)
  {
   p=Get(B,i);
   if(p)
    printf("%4d",p->data);
  }
 printf("\n");
 DelElem(A,B);/*将单链表A中出现B的元素删除，即A-B*/
 printf("将在A中出现B的元素删除后(A-B)，现在A中的元素还有%d个:\n",ListLength(A));
 for(i=1; i<=ListLength(A); i++)
  {
   p=Get(A, i);
   if(p)
    printf("%4d",p->data);
  }
 printf("\n");
 
}

上面的执行A-B操作的函数还可以不调用链表的基本函数可以直接用下列函数来实现：

/*******************************************************************************
函数名:DelElem2(LinkList A, LinkList B)
函数功能:实现A-B操作方法2
入口参数:
出口参数:
********************************************************************************/
void DelElem2(LinkList A, LinkList B)
{
/*删除A中出现B的元素的函数实现*/
 ListNode *pre,*p,*q,*r;
 pre=A;/*首先将pre指向A结点首地址*/
 p=A->next;/*然后将p指向第一个结点*/
 /*在单链表B中，取出每个元素与单链表A中的元素比较
 如果相等则删除A中元素对应的结点*/
 
 while(p !=NULL)
  {
   q=B->next;/*从B的第一个结点的元素开始与A中的结点
   的元素比较*/
    
   while(q !=NULL && q->data!=p->data )/*不相等则指向下一个结点*/
    q=q->next;/*没有到最后一个结点并且不相等的话指向
   下一个结点*/
    
   if(q!=NULL)/*当没有指向最后一个结点时证明有元素相等*/
    {
     r=p;/*指针指向要删除的结点*/
     pre->next=p->next;/*将前驱结点的指针指向p的后继结点
     ，即将p指向的结点与链表断开*/
     p=r->next;/*将p指向A中下一个待比较的结点*/
     free(r);
    }
   else
    {
     pre=p;/*将pre指向刚比较过的结点*/
     p=p->next;/*指针p指向下一个待比较的结点*/
    }
   
  }
}