欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

已知两个链表A和B分别表示两个集合, 其元素递增排列. 设计一个算法, 求出A与B的交集, 并存放在C链表中

程序员文章站 2022-03-10 12:09:12
...
#include<stdio.h>
#include<stdlib.h>
short InitHeadNode(struct Node* &, struct Node* &);
short RearInsert(struct Node* &, struct Node* &, short);
short GetListLength(struct Node* &);
short IsElemIn(struct Node* &, short);
void FindNodeIn1andIn2(struct Node* &, struct Node* &, struct Node* &, struct Node* &);
void Traversal(struct Node* &);
/* 链表结点定义 */
struct Node
{
    short data;
    struct Node *next;
};
int main()
{
    struct Node *head1;
    struct Node *rear1;
    struct Node *head2;
    struct Node *rear2;
    struct Node *head3;
    struct Node *rear3;
    /* 初始化1#链表的头结点 */
    if(InitHeadNode(head1, rear1) == -1)
    {
        /* 头结点申请失败, 程序直接结束 */
        exit(0);
    }
    short temp;
    /* 向链表中插入数据结点 */
    while(1)
    {
        while(scanf("%hd", &temp) != 1)
        {
            while(getchar() != '\n') ;
            printf("请输入合法数据.\n");
        }
        if(temp == -1)
        {
            break;
        }
        if(RearInsert(head1, rear1, temp) == -1)
        {
            /* 申请结点失败 */
            exit(0);
        }
    }
    /* 初始化2#链表的头结点 */
    if(InitHeadNode(head2, rear2) == -1)
    {
        /* 头结点申请失败, 程序直接结束 */
        exit(0);
    }
    /* 向链表中插入数据结点 */
    while(1)
    {
        while(scanf("%hd", &temp) != 1)
        {
            while(getchar() != '\n') ;
            printf("请输入合法数据.\n");
        }
        if(temp == -1)
        {
            break;
        }
        if(RearInsert(head2, rear2, temp) == -1)
        {
            /* 申请结点失败 */
            exit(0);
        }
    }
    /* 初始化3#链表的头结点 */
    if(InitHeadNode(head3, rear3) == -1)
    {
        /* 头结点申请失败, 程序直接结束 */
        exit(0);
    }
    /* 至此, 三个链表均已初始化 */
    FindNodeIn1andIn2(head1, head2, head3, rear3);
    Traversal(head3);
    /* */
    return 0;
}
/* 判断数据元素value是否在链表中 */
short IsElemIn(struct Node* &head, short value)
{
    struct Node *p = head -> next;
    while(p != NULL)
    {
        if(p -> data == value)
        {
            /* 找到数据元素value */
            return 1;
        }
        p = p -> next;
    }
    /* 未找到数据元素value */
    return -1;
}
/* 求出1#集合和2#集合的交集, 并将结果保存到3#链表中 */
void FindNodeIn1andIn2(struct Node* &head1, struct Node* &head2, struct Node* &head3, struct Node* &rear3)
{
    struct Node *p2 = head2 -> next;
    /* */
    while(p2 != NULL)
    {
        if(IsElemIn(head1, p2 -> data) == 1)
        {
            /* 将结果保存到3#链表中 */
            RearInsert(head3, rear3, p2 -> data);
        }
        p2 = p2 -> next;
    }
}
/* 遍历单链表并输出 */
void Traversal(struct Node* &head)
{
    struct Node *p = head -> next;
    while(p != NULL)
    {
        printf("%3hd", p -> data);
        p = p -> next;
    }
    putchar('\n');
}
/* 获取表长 */
short GetListLength(struct Node* &head)
{
    struct Node *p = head -> next;
    short length = 0;
    while(p != NULL)
    {
        length ++;
        p = p -> next;
    }
    return length;
}
/* 尾插法 */
short RearInsert(struct Node* &head, struct Node* &rear, short value)
{
    struct Node *p = (struct Node*)malloc(sizeof(struct Node));
    if(p != NULL)
    {
        /* 结点申请成功 */
        rear -> next = p;
        p -> next = NULL;
        p -> data = value;
        rear = p;
        return 1;
    }
    else
    {
        /* 结点申请失败 */
        return -1;
    }
}
/* 初始化头结点 */
short InitHeadNode(struct Node* &head, struct Node* &rear)
{
    struct Node *p = (struct Node*)malloc(sizeof(struct Node));
    if(p != NULL)
    {
        /* 头结点申请成功 */
        head = p;
        head -> data = 0;
        head -> next = NULL;
        rear = head;
        return 1;
    }
    else
    {
        /* 头结点申请失败 */
        return -1;
    }
}

已知两个链表A和B分别表示两个集合, 其元素递增排列. 设计一个算法, 求出A与B的交集, 并存放在C链表中

已知两个链表A和B分别表示两个集合, 其元素递增排列. 设计一个算法, 求出A与B的交集, 并存放在C链表中

已知两个链表A和B分别表示两个集合, 其元素递增排列. 设计一个算法, 求出A与B的交集, 并存放在C链表中

已知两个链表A和B分别表示两个集合, 其元素递增排列. 设计一个算法, 求出A与B的交集, 并存放在C链表中