|
//集合的交并运算.cpp
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include "MyNode.h"
#include "Message.h"
int Menu();
Node *ListCreate();
Node *ListClone(Node *listFrom);
Node *NewNode();
void ListPrint(Node *list);
void ListDelete(Node *list);
Node *ListSub(Node *listA, Node *listB); //A-B
Node *ListMerge(Node *listA, Node *listB); //A∪B
Node *ListIntersect(Node *listA, Node *listB); //A∩B
Node *Example(Node *listA, Node *listB); //(A-B)∪(B-A)
int main()
{
Node *listA , *listB;
listA = NewNode();
listB = NewNode();
listA->next = listB->next = NULL;
int choice;
while ((choice = Menu()) != 7)
{
switch (choice)
{
case 1 :
printf("A\t: ");
ListPrint(listA);
printf("B\t: ");
ListPrint(listB);
printf("A-B\t: ");
ListPrint(ListSub(ListClone(listA), ListClone(listB)));
break;
case 2 :
printf("A\t: ");
ListPrint(listA);
printf("B\t: ");
ListPrint(listB);
printf("A∪B\t: ");
ListPrint(ListMerge(ListClone(listA), ListClone(listB)));
break;
case 3 :
printf("A\t: ");
ListPrint(listA);
printf("B\t: ");
ListPrint(listB);
printf("A∩B\t: ");
ListPrint(ListIntersect(ListClone(listA), ListClone(listB)));
break;
case 4 :
printf("A\t\t: ");
ListPrint(listA);
printf("B\t\t: ");
ListPrint(listB);
printf("(A-B)∪(B-A)\t: ");
ListPrint(Example(ListClone(listA), ListClone(listB)));
break;
case 5 :
ListDelete(listA);
listA = ListCreate();
ListPrint(listA);
break;
case 6 :
ListDelete(listB);
listB = ListCreate();
ListPrint(listB);
break;
default :
Message("WARNING", "请输入一个在1-7之间的数字!");
break;
}
}
ListDelete(listA);
ListDelete(listB);
//getch();
return 0;
}
int Menu()
{
int choice;
Message("集合的交并运算", "1、A-B\n2、A∪B\n3、A∩B\n4、(A-B)∪(B-A)\n5.输入集合A\n6.输入集合B\n7.退出");
printf("请输入你的选择(1-7)：");
if (!scanf("%d", &choice))
{
Message("ERROR", "输入的数据格式有错误！");
exit(3);
}
return choice;
}
Node *ListCreate()
{
Node *newList, *pTail, *pNew;
pTail = newList = NewNode();
int newData;
do
{
if (!scanf("%d", &newData))
{
Message("ERROR", "输入的数据格式有错误！");
exit(3);
}
if (newData == 0)
break;
else
{
pNew = NewNode();
pNew->data = newData;
pTail->next = pNew;
pTail = pNew;
}
} while (1);
pTail->next = NULL;
return newList;
}
Node *ListClone(Node *listFrom)
{
Node *listTo, *pFrom, *pNew, *pToTail;
pToTail = listTo = NewNode();
for (pFrom = listFrom->next; pFrom; pFrom = pFrom->next)
{
pNew = NewNode();
pNew->data = pFrom->data; //ERROR: data是数组类型时可能会出错
pToTail->next = pNew;
pToTail = pNew;
}
pToTail->next = NULL;
return listTo;
}
Node *NewNode()
{
Node *pNew;
pNew = (Node *)malloc(sizeof(Node));
if (!pNew)
{
Message("ERROR", "分配内存时出错！");
exit(1);
}
//pNew->next = NULL; //留给函数自己处理
return pNew;
}
void ListPrint(Node *list)
{
for (list = list->next; list; list = list->next)
{
NodePrint(list);
printf("\t");
}
printf("\n");
}
void ListDelete(Node *list)
{
Node *p;
while ((p = list)) //p为NULL,即链表为空时,结束循环
{
list = list->next;
free(p);
}
}
Node *ListSub(Node *listA, Node *listB) //A-B
{
Node *listC, *pA, *pB, *pCTail, *pToDelete;
pCTail = listC = listA;
for (pA = listA->next; pA; )
{
for (pB = listB->next; pB; pB = pB->next)
{
if (NodeEqual(pA, pB))
break;
}
if (!pB)
{
pCTail->next = pA;
pCTail = pA;
pA = pA->next;
}
else
{
pToDelete = pA;
pA = pA->next;
free(pToDelete);
}
}
pCTail->next = NULL;
ListDelete(listB);
return listC;
}
Node *ListMerge(Node *listA, Node *listB) //A∪B
{
Node *listC, *pC, *pB, *pToDelete, *pToAdd;
listC = listA;
for (pB = listB->next; pB; )
{
for (pC = listC->next; pC; pC = pC->next)
{
if (NodeEqual(pB, pC))
break;
}
if (!pC)
{
pToAdd = pB;
pB = pB->next;
pToAdd->next = listC->next;
listC->next = pToAdd;
}
else
{
pToDelete = pB;
pB = pB->next;
free(pToDelete);
}
}
return listC;
}
Node *ListIntersect(Node *listA, Node *listB) //A∩B
{
Node *listC, *pA, *pB, *pCTail, *pToDelete;
pCTail = listC = listA;
for (pA = listA->next; pA; )
{
for (pB = listB->next; pB; pB = pB->next)
{
if (NodeEqual(pA, pB))
break;
}
if (pB)
{
pCTail->next = pA;
pCTail = pA;
pA = pA->next;
}
else
{
pToDelete = pA;
pA = pA->next;
free(pToDelete);
}
}
pCTail->next = NULL;
return listC;
}
Node *Example(Node *listA, Node *listB) //(A-B)∪(B-A)
{
Node *listASubB, *listBSubA, *result;
listASubB = ListSub(ListClone(listA), ListClone(listB));
listBSubA = ListSub(ListClone(listB), ListClone(listA));
result = ListMerge(listASubB, listBSubA);
return result;
}
//MyNode.h
typedef int DataType;
typedef struct node
{
DataType data;
struct node *next;
} Node;
int NodeEqual(Node *pA, Node *pB)
{
if (pA->data == pB->data)
return 1;
return 0;
}
void NodePrint(Node *p)
{
printf("%d", p->data);
}
//Message.h
#include <string.h>
void Message(char *caption, char *message)
{
int length = (int)strlen(caption);
int beforeCaption = (80 – length) / 2;
int afterCaption = 80 – (length + (80 – length) / 2);
char separateChar = ‘=’;
printf("\n");
for (int i = 0; i < beforeCaption; i++)
printf("%c", separateChar);
printf("%s", caption);
for (int i = 0; i < afterCaption; i++)
printf("%c", separateChar);
printf("%s\n",message);
for (int i = 0; i < 80; i++)
printf("%c", separateChar);
}
|
