作业

/****************************************************************/
/*
题目：
给定两个已排序的表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 Position;
typedef PtrToNode List;
struct Node
{
 ElementType element;
 Position next;
};

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

 Position Head = ( Position )malloc( sizeof( Node ) );
 if( Head == NULL )
 {
  printf("动态内存分配失败，程序结束！！！\n");
  return ERROR;
 }

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

 for( int i =  1; i <= n; i++ )
 {
  Position New = ( Position )malloc( sizeof( Node ) );
     if( New == NULL )
  {
       printf("动态内存分配失败，程序结束！！！\n");
       exit( -1 );
  }
         printf("请输入第%d个数：",i);
   scanf("%d",&TmpCell);

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

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

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

/**************************************/
/*插入操作*/
/*基本思路：
将La链表的第一个数与Lb链表的每一个数比较，相同就插入到Ls链表中，
循环一遍，再把La链表的第二个数与Lb链表的每一个数比较，相同就插入到Ls链表中，
如此反复，直到La或者Lb为空。。
*/
/**************************************/
List Insert(List &L,ElementType X )                                  //向链表中插入数据
{
 /*
 Position Head = ( Position )malloc( sizeof( Node ) );
 if( Head == NULL )
 {
  printf("动态内存分配失败，程序结束！！！\n");
  return ERROR;
 }

 Head = L;
 */
 L->next = NULL;

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

      TmpCell->element = X;
      TmpCell->next = L->next;
      L->next = TmpCell;
   L = TmpCell;

   return 0;
}

/**************************************/
/*交集功能函数*/
/**************************************/
List Intersect( List La, List Lb )                                                     //两个链表求交集结果存放在Ls中
{
 Position LaPos, LbPos, Ls;

    Position LsHead = ( Position )malloc( sizeof( Node ) );
 if( LsHead == NULL )
 {
  printf("动态内存分配失败，程序结束！！！\n");
  return ERROR;
 }

    Ls = LsHead;
 Ls->next = NULL;
 LaPos = La->next ;
 LbPos = Lb->next ;

 while( LaPos != NULL && LbPos != NULL )
 {
  while( LbPos != NULL )
  {
      if( LaPos->element == LbPos->element )
   {
         Insert( Ls, LaPos->element );
   }
      LbPos = LbPos->next ;
  }
  LaPos = LaPos->next ;
  LbPos = Lb->next ;
 }

    TraverseLinkList( LsHead );
 
 return 0;
}

/**************************************/
/*主函数*/
/**************************************/
int main()
{
 int len1, len2;
 Position L, P, Ls = NULL;

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

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

   Intersect( L, P) ;
    printf("\n");

 return 0;
}

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