作业

/****************************************************************/
/*
题目：
给定两个已排序的表L1和L2，只使用基本的表操作编写计算L1∪L2的过程。
*/
/****************************************************************/
#include <stdio.h>
#include <stdlib.h>

#define ERROR  0
#define OK        1

/************************************************/
/*链表声明*/
/************************************************/
typedef int ElementType;
struct Node;
typedef struct Node *PtrToNode;
typedef PtrToNode List;
typedef PtrToNode Position;
struct Node
{
 ElementType element;
 Position next;
};

/************************************************/
/*创建链表*/
/************************************************/
List CreateLinkList( int n )
{
 int TmpCell;

 Position Head = ( Position )malloc( sizeof( Node ) );
 if( Head == NULL )
 return ERROR;

 Position Tail = Head;
 Tail->next = NULL;

 for( int i = 1; i <= n; i++ )
 {
        Position New = ( Position )malloc( sizeof( Node ) );
  if( New == NULL )
   return ERROR;

  printf("请输入第%d个数：",i );
  scanf("%d",&TmpCell);

  New->element = TmpCell;
  New->next = NULL;
  Tail->next = New;
  Tail = New;
 }

 return Head;
}

/************************************************/
/*遍历链表*/
/************************************************/
void TraverseLinkList( List L )
{
 Position p;

 p = L->next ;
 while(p != NULL )
 {
  printf("%d  ",p->element );
  p = p->next ;
 }
}

/************************************************/
/*并集功能函数*/
/************************************************/

/*获得链表的长度*/
int Length(List L)
{
 int counter = 0;
 Position P = L->next ;

 while(P != NULL )
 {
  ++counter;
  P = P->next ;
 }

 return counter;
}

/*获取链表的元素*/
ElementType GetElement(List L, int n )
{
    for(int i = 1; i <= n; i++)
 {
  L = L->next ;
 }
 return L->element ;
}

/*判断一个元素是否存在于一个链表当中*/
bool IsExist(List L, ElementType x)
{
     int len = Length( L );
  Position P = L->next ;
  for(int i = 1; i <= len; i++ )
  {
   if( x == P->element )
   {
    return true;
   }
   else
    P = P->next ;
  }
  return false;
}

/*插入函数*/
bool Insert( List L, int n, ElementType x )
{
 Position New = ( Position )malloc( sizeof( Node ) );
 if( New == NULL )
  return ERROR;
 New->element = x;
    for(int i =  1;i < n; i++ )
 {
  L = L->next ;
 }
 L->next = New;
 New->next = NULL;

 return true;
}

/*将一个链表的元素赋值给另外一个链表，简称复制*/
List CopyList( List L, List P )
{
 Position Tail = P;
 Tail->next = NULL;

    Position LPos = L->next ;

 int n = Length( L );
 for( int i = 1; i <= n; i++ )
 {
  Position TmpCell = ( Position )malloc( sizeof( Node ) );
  if( TmpCell == NULL )
   return ERROR;
  TmpCell->element = LPos->element;
  Tail->next = TmpCell;
  TmpCell->next = NULL;
  Tail = TmpCell;
  LPos = LPos->next;
 }
 
    return P;
}

/*并集函数*/
/*
基本思路：
L1的元素：1,2,3
L2的元素：2,3,4
把L1的所有元素都赋值给L3，
先获取L1，L2的长度len（ Length(List L) ），再取L2第len个元素（ IsExist(List L, ElementType x) ），
看看是否存在于L1中（ IsExist(List L, ElementType x) ），不存在就在L3插进去。。
*/
List Union( List L1, List L2 )
{
     Position L3;
     int len1, len2 ;
  ElementType TmpCell;

  L3 = ( Position )malloc( sizeof( Node ) );
  if( L3 == NULL )
  return ERROR;

  L3 = CopyList( L1, L3 );
  len1 = Length( L1 );                     
     len2 = Length( L2 );                    
  
     for(int i = 1; i <= len2; i++ )
  {
         TmpCell = GetElement( L2, i );
   if( !IsExist( L1, TmpCell ) )
   {
    Insert( L3, ++len1, TmpCell );
   }
  }

     return L3;
}

/************************************************/
/*主函数*/
/************************************************/
int main( )
{
 Position L1, L2, L3;
 int len1, len2;

 printf("请输入第一个链表的长度：");
 scanf("%d",&len1);
 L1 = CreateLinkList( len1 );
 TraverseLinkList( L1 );
 printf("\n\n");

 printf("请输入第二个链表的长度：");
 scanf("%d",&len2);
 L2 = CreateLinkList( len2 );
 TraverseLinkList( L2 );
 printf("\n\n");

 printf("则L1和L2的并集为 ");
 L3 = Union( L1, L2 );
 TraverseLinkList( L3 );
 printf("\n\n");

 return 0;
}

如果有BUG请及时留言告诉我，谢谢了！！！