数据结构_集合的交并补（链表实现）

2019-10-20 本文已影响0人书虫大王X

一：要实现的功能：
从键盘输入两个字符串，应用链表求它们的差集、并集和交集
二、概要设计：
为实现上述功能，应以有序链表表示集合。为此，需要两个抽象的数据类型：游戏表和集合。

有序表的抽象数据类型定义为：

ADT OrderdList {

数据对象：D={ai | ai ∈ CharSet，i = 1,2,....n, n > 0}

数据关系：R1 = {<ai-1,ai> ai-1ai∈Dai-1< ai , i=2 ,......, n }

基本操作：

InitLIst( &L )

操作结果：构造一个空的有序表L。

DestroyList( &L )

初始条件：有序表L存在。

操作结果：销毁有序表L。

ListLength ( L )

初始条件：有序表L已存在。

操作结果：返回有序表L的长度。

ListEmpty( L )

初始条件：有序表L已存在。

操作结果：如有序表L为空表，则返回True否则返回False。

GetElem( L , pos)

初始条件：有序表L已存在

操作结果：若1≤pos ≤ Length( L )，则返回表中的pos个数据元素。

LocateElem (L , e , &q )

初始条件：有序表L已存在

操作结果：若有序表L中存在元素e，则q提示L中第一个值为e的元素的位置，并返回函数值TRUE；否则q指示第一个大于e的元素的前驱的位置，并返回函数值FLASE。

Append( &L , e)

初始条件：有序表L已存在。

操作结果：自有序表L的末尾插入元素e

InsertAfter( &L , q ,e) 初始条件：有序表L已存在，q指示L中的一个元素。

操作结果：在有序表L中q指示的元素之后插入元素e

ListTraverse( q , visit() )

初始条件：有序表L已存在，q指示L中一个元素

操作结果：依次对L中q指示的元素开始的每个元素调用函数visit()

}ADT OrdereList

集合的抽象数据类型定义为：

ADT Set {

数据对象：D={ ai | ai为小写英文字母并且不相同，i = 1,2,....n, 0 ≤n ≤26}

数据关系： R1 = { }

基本操作：

CreateSet(&T, Str)

初始条件：Str为字符串

操作结果：生成一个有Str 中小写字母构成的集合T

DestroySet( &T)

初始条件：集合T已存在。

操作结果：销毁集合T的结构

Union(& T ,S1 ,S2)

初始条件：集合S1和S2存在

操作结果：生成一个有S1和S2 的并集构成的集合T

Intersection(&T , S1 , S2)

初始条件：集合S1和S2存在

操作结果：生成一个由S1和S2的交集构成的集合T

Difference(&T , S1 ,S2)

初始条件：集合S1和S2存在

操作结果：生成一个由S1和S2的差集构成的集合T

PrintSet( T )

初始条件：集合T已存在

操作结果：按字母顺序显示集合T的全部元素

}ADT Set

本程序包含四个模块：

1）主程序模块：

void main() {

初始化；

do {

接受命令；

处理命令； }while（“命令” = “退出”）；

}

2）集合单元模块 ——实现集合的抽象数据类型；

3）有序表单元模块——实现有序表的抽象数据类型；

4）节点结构单元模块——定义有序表的节点结构

各模块之间的调用关系如下：

主程序模块

↓

集合单元模块

↓

有序表单元模块

↓

节点结构单元模块

函数的调用关系

** 三、代码实现：**

//定义常量
#define  TRUE 1
#define  FALSE   0
#define  OK  1
#define  ERROR   0
#define INFEASIBLE   -1
#define OVERFLOW   -2
//类型重定义
typedef  int  Status;
typedef  char  ElemType;

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <conio.h>

//定义链表的节点
typedef  struct NodeType
{
    ElemType   data;
    struct NodeType* next;
} NodeType, * LinkType;

//定义有序链表的结构体
typedef struct
{
    LinkType head, tail;//定义两个节点，分别指向线性链表的头、尾节点
    int size;//记录线性链表的长度
}OrderedList;

//定义用于保存输入的字符串的数组
ElemType a[100] = "magazine";
ElemType b[100] = "paper";
//定义三个有序链表
OrderedList L1, L2, L3;
//创建节点  参数一：引用节点指针（将创建的节点传递出去），参数二：节点的数据
Status MakeNode(LinkType& p, ElemType e)
{
    p = (LinkType)malloc(sizeof(NodeType));
    if (!p)
        return FALSE;
    p->data = e;
    p->next = NULL;
    return TRUE;
}
//创建有序空链表 参数：引用有序链表（将创建的链表传递出去）
Status InitList(OrderedList& L)
{
    //判断MakeNode函数是否执行成功
    if (MakeNode(L.head, ' '))
    {
        L.tail = L.head;
        L.size = 0;
        return TRUE;
    }
    else
    {
        L.head = NULL;
        return FALSE;
    }
}

//链表查重并排序：向函数传递一个有序链表、元素e和一个节点，将P节点设置为链表的首元结点，
//当节点的数据小于元素e时，将p节点的位置向后移动一位。当p节点的数据等于e时，
//返回e在链表中的位置，并返回true。当e大于链表中的所有元素时，返回链表的尾节点，并返回false
Status LocateElem(OrderedList L, ElemType e, LinkType& p)
{
    NodeType* pre;
    if (L.head)
    {
        pre = L.head;
        p = pre->next;
        //这一步完成了链表的排序
        while (p && p->data < e)
        {
            pre = p;
            p = p->next;
        }
        if (p && p->data == e)
        {
            return TRUE;
        }
        else
        {
            p = pre;
            return FALSE;
        }
    }
    else
        return FALSE;
}
//在链表L中节点q的后面插入节点s
void InsertAfter(OrderedList &L, LinkType q, LinkType s)
{
    if (L.head && q && s)
    {
        s->next = q->next;
        q->next = s;
        if (L.tail == q)
            L.tail = s;
        L.size++;
    }
}
//用字符串创建节点
void CreateSet(OrderedList& T, char* s)
{
    unsigned i;
    LinkType p, q;
    //创建有序空链表 
    if (InitList(T))
    {
        //遍历字符串
        for (i = 0;i <= strlen(s);i++)
        {
            //当字符串数组第i个元素大于a、小于z、并且在链表T中没有找到该元素时，执行以下语句（空格的阿斯克码为32，a为64）
            if (s[i] >= 'a' && s[i] <= 'z' && !LocateElem(T, s[i], p))
            {
                //用第i位元素创建节点
                if (MakeNode(q, s[i]))
                {
                    //在P后面插入q节点
                    InsertAfter(T, p, q);
                }
            }
        }
    }
}
//打印节点的数据
Status Print(LinkType p)
{
    if (p)
    {
        printf("%c", p->data);
        return TRUE;
    }
    else
        return FALSE;
}
//将输入的字符串中重复的字符剔除并排序
void ListTraverse(LinkType p, Status(*visit)(LinkType))
{
    printf("%c", '\t');
    while (p)
    {
        visit(p);
        p = p->next;
    }
    printf("%c", '\n');

}
//在链表结尾添加节点
void Append(OrderedList& L, LinkType s)
{
    if (L.head && s)
    {
        if (L.tail != L.head)
            L.tail->next = s;
        else
            L.head->next = s;
        L.tail = s;
        L.size++;
    }
}

//求两个集合的并集
void Union(OrderedList& T, OrderedList S1, OrderedList S2)
{
    LinkType p1, p2, p;
    if (InitList(T))
    {
        p1 = S1.head->next;
        p2 = S2.head->next;
        // 当两个链表在该位置都有元素时
        while (p1 && p2)
        {
            if (p1->data <= p2->data)
            {
                p = (LinkType)malloc(sizeof(NodeType));
                p->data = p1->data;
                p->next = NULL;
                Append(T, p);
                //当p1.p2数据相等时，p1.p2都指向当前位置的下一个元素再进行比较
                if (p1->data == p2->data)
                    p2 = p2->next;
                p1 = p1->next;
            }
            else
            {
                p = (LinkType)malloc(sizeof(NodeType));
                p->data = p2->data;
                p->next = NULL;
                Append(T, p);
                p2 = p2->next;
            }
        }
        //当只有P1有元素时，直接插入元素
        while (p1)
        {
            p = (LinkType)malloc(sizeof(NodeType));
            p->data = p1->data;
            p->next = NULL;
            Append(T, p);
            p1 = p1->next;
        }
        while (p2)
        {
            p = (LinkType)malloc(sizeof(NodeType));
            p->data = p2->data;
            p->next = NULL;
            Append(T, p);
            p2 = p2->next;
        }
    }
}
//求两个集合的交集
void Intersection(OrderedList& T, OrderedList S1, OrderedList S2)
{
    LinkType p1, p2, p;
    if (!InitList(T))
        T.head = NULL;
    else
    {
        p1 = S1.head->next;
        p2 = S2.head->next;
        while (p1 && p2)
        {
            if (p1->data < p2->data)
                p1 = p1->next;
            else if (p1->data > p2->data)
                p2 = p2->next;
            else
            {
                p = (LinkType)malloc(sizeof(NodeType));
                p->data = p1->data;
                p->next = NULL;
                Append(T, p);
                p2 = p2->next;
                p1 = p1->next;
            }
        }
    }
}
//求两个集合的差集
void Difference(OrderedList& T, OrderedList S1, OrderedList S2)
{
    LinkType p1, p2, p;
    if (!InitList(T))
        T.head = NULL;
    else
    {
        p1 = S1.head->next;
        p2 = S2.head->next;
        // 当两个链表在该位置都有元素时
        while (p1 && p2)
        {
            if (p1->data < p2->data)
            {
                p = (LinkType)malloc(sizeof(NodeType));
                p->data = p1->data;
                p->next = NULL;
                Append(T, p);
                p1 = p1->next;
            }
            else if (p1->data > p2->data)
                p2 = p2->next;
            else
            {
                p1 = p1->next;
                p2 = p2->next;
            }
        }
        while (p1)
        {
            p = (LinkType)malloc(sizeof(NodeType));
            p->data = p1->data;
            p->next = NULL;
            Append(T, p);
            p1 = p1->next;
        }

    }
}
//提示用户输入命令
void ReadCommand(char& cmd)
{
    printf("\n--------------------------------------------------------------------------\n");
    printf("\n\t\t\t\t操  作  提  示");
    printf("\n--------------------------------------------------------------------------\n");
    printf("\tMakeSet1------1\t\t\t\tMakeSet2--------2\n\tUnion---------u\t\t\t\tIntersection----i\n\tDifference----d\t\t\t\tQuit------------q\n\tDisplay-------y");
    do {
        printf("\n\n\t请选择操作：");
        cmd = _getch();
        printf("\n--------------------------------------------------------------------------\n");
    } while (cmd != '1' && cmd != '2' && cmd != 'u' && cmd != 'i' && cmd != 'd' && cmd != 'q' && cmd != 'y');
}
//判断用户输入的命令，并调用相应的函数
void Interpret(char& cmd)
{
    system("cls");   //清屏
    switch (cmd)
    {
    case '1':
        printf("\n\t请输入字符串：");
        gets_s(a);
        printf("\t原始字符串:");
        printf("\t%s\n", a);
        CreateSet(L1, a);
        printf("\t构建的集合:");
        ListTraverse(L1.head->next, Print);
        break;
    case '2':
        printf("\n\t请输入字符串：");
        gets_s(b);
        printf("\t原始字符串:");
        printf("\t%s\n", b);
        CreateSet(L2, b);
        printf("\t构建的集合:");
        ListTraverse(L2.head->next, Print);
        break;
    case 'u':
        CreateSet(L1, a);
        CreateSet(L2, b);
        Union(L3, L1, L2);
        printf("\n\t集合1:");
        ListTraverse(L1.head->next, Print);
        printf("\t集合2:");
        ListTraverse(L2.head->next, Print);
        printf("\t并集:");
        ListTraverse(L3.head->next, Print);
        break;
    case 'i':
        CreateSet(L1, a);
        CreateSet(L2, b);
        Intersection(L3, L1, L2);
        printf("\n\t集合1:");
        ListTraverse(L1.head->next, Print);
        printf("\t集合2:");
        ListTraverse(L2.head->next, Print);
        printf("\t交集:");
        ListTraverse(L3.head->next, Print);
        break;
    case 'd':
        CreateSet(L1, a);
        CreateSet(L2, b);
        Difference(L3, L1, L2);
        printf("\n\t集合1:");
        ListTraverse(L1.head->next, Print);
        printf("\t集合2:");
        ListTraverse(L2.head->next, Print);
        printf("\t差集:");
        ListTraverse(L3.head->next, Print);
        break;
    case 'y':
        printf("\n\t原始字符串:\n");
        printf("\t\t%s\n\t\t%s\n", a, b);
        CreateSet(L1, a);
        CreateSet(L2, b);
        printf("\t由字符串构建的集合:\n");
        printf("\t");
        ListTraverse(L1.head->next, Print);
        printf("\t");
        ListTraverse(L2.head->next, Print);
        Union(L3, L1, L2);
        printf("\t并集:");
        ListTraverse(L3.head->next, Print);

        Intersection(L3, L1, L2);
        printf("\t交集:");
        ListTraverse(L3.head->next, Print);

        Difference(L3, L1, L2);
        printf("\t差集:");
        ListTraverse(L3.head->next, Print);
        break;
    }
}
void main()
{
    char cmd;
    //调用函数
    do
    {
        ReadCommand(cmd);
        Interpret(cmd);
    } while (cmd != 'q');//当输入的命令为q时，结束while循环
}

四、结果展示：