|
/****************************************************************/
/*
题目:
给定两个已排序的表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请及时留言告诉我,谢谢了!!!
小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)
GMT+8, 2024-4-27 03:29
Powered by Discuz! X3.4
© 2001-2023 Discuz! Team.