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

第二章 线性表

程序员文章站 2022-05-26 12:00:08
...

(4) 巳知两个链表 A 和 B 分别表示两个集合,其元素递增排列。请设计算法 求出两个集合 A
和B 的差集(即仅由在A中出现而不在B中出现的元素所构成的集合),并以 同样的形式存储,
同时返回该集合的元素个数。

#include <stdio.h>
#include <iostream>

#define LENGTH 5

typedef struct LNode
{
    int data;
    struct LNode *next;
} LNode, *LinkList;

void CreatList_R(LinkList &L, int n)
{
    L = new LNode;
    L->next = NULL;
    LNode *r = L;
    for (int i = 0; i < n; i++)
    {
        LNode *p = new LNode;
        printf("请输入第%d个结点data值:", i + 1);
        std::cin >> p->data;
        p->next = NULL;
        r->next = p;
        r = p;
    }
}

void ShowList(LinkList L)
{
    LNode *p = L->next; // 指向首元结点
    while (p)
    {
        printf("%d\t", p->data);
        p = p->next;
    }
    printf("\n");
}

void SubList(LinkList &L1, LinkList &L2, LinkList &L3)
{
    L3 = L1;
    L3->data = 0;
    LNode *r = L3;
    LNode *p2 = L2->next;
    LNode *p1 = L1->next;
    while (p1 && p2)
    {
        if (p1->data == p2->data)
        {
            p1 = p1->next;
            p2 = p2->next;
        }
        else if (p1->data > p2->data)
            p2 = p2->next;
        else
        {
            r->next = p1;
            r = p1;
            p1 = p1->next;
            L3->data++;
        }
    }
    while (p1)
    {
        r->next = p1;
        r = p1;
        p1 = p1->next;
        L3->data++;
    }
    if (r->next)
        r->next = NULL;
    delete L2;
}

int main(void)
{
    LinkList L1, L2, L3;
    CreatList_R(L1, LENGTH);
    printf("L1:");
    ShowList(L1);
    CreatList_R(L2, LENGTH);
    printf("L2:");
    ShowList(L2);
    SubList(L1, L2, L3);
    printf("L3 = L1 - L2\n");
    printf("L3有%d个结点,且data分别为:", L3->data);
    ShowList(L3);
    delete L3;

    return 0;
}

运行结果:
第二章 线性表
第二章 线性表
有时候可能会理解错题义,做错了请告诉一下小茅芦。

相关标签: 数据结构