A-B差集的计算

本文主要是介绍A-B差集的计算，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

算法代码：

/****************
作者：一叶扁舟
时间：23:29 2016/9/2
问题：递增有序的链表A和B,不存在相等的数据，求出A-B的集合，
即A中存在B中不存在
****************/#include "stdio.h"
#include "string.h"
#include "stdlib.h"typedef struct LinkNode{int data;LinkNode *next;
}LinkNode;//从键盘中输入数据，然后建立成链表
LinkNode *Creat_SList(LinkNode **pHead);
int SqList_Print(LinkNode *pHead);
//在结点数值为x的前面插入y
int SqList_NodeInsert(LinkNode *pHead, int x, int y);//创建链表
LinkNode *Creat_SList(){//1.准备环境LinkNode *pHead = NULL;LinkNode *pCurrent = NULL;LinkNode *tempNode = NULL;//创建头结点pHead = (LinkNode*)malloc(sizeof(LinkNode));pHead->next = NULL;pCurrent = pHead;if (pHead == NULL){return NULL;}int inputData = 0;printf("请输入一个数据（-1结束）：");scanf("%d", &inputData);while (inputData != -1){//2创建临时空间tempNode = (LinkNode*)malloc(sizeof(LinkNode));tempNode->data = inputData;tempNode->next = NULL;//3.链表的建立pCurrent->next = tempNode;pCurrent = pCurrent->next;printf("请输入一个数据（-1结束）：");scanf("%d", &inputData);}return pHead;
};
//输出链表
int SqList_Print(LinkNode *pHead){if (pHead == NULL){return -1;}LinkNode *pCurrent = pHead->next;printf("链表的结果:\n");while (pCurrent != NULL){printf("%3d ", pCurrent->data);pCurrent = pCurrent->next;}printf("\n");return 0;
}
/*
思路：
1.以B为基础外围基础，逐个在A链表中查找
2.如果A中的数据比B大，终止A的查找，B链表中下移一个
3.如果A中的数据比B小，此时A向下移动，B不动
4.如果A中的数据等于B，此时删除A的当前结点，并终止A的查找，B下移一个
算法的复杂度：0(N*M)
注：代码还是存在问题！！！
*/void findDifference(LinkNode *&pHeadA,LinkNode *pHeadB){//1.环境的准备LinkNode *pPreA = pHeadA;LinkNode *pTemp = NULL;LinkNode *pCurrentA = pHeadA->next;LinkNode *pCurrentB = pHeadB->next;//2.外围的链表Bwhile (pCurrentB != NULL){while (pCurrentA != NULL){//A中有和B相等的元素if (pCurrentB->data == pCurrentA->data){//用于释放的内存pTemp = pCurrentA;//找到以后删除并释放内存pPreA->next = pCurrentA->next;pCurrentA = pCurrentA->next;free(pTemp);//链表B下移一个结点pCurrentB = pCurrentB->next;//跳出while循环break;}else if (pCurrentB->data < pCurrentA->data){//B中的当前元素比A中的小，那么此轮结束循环，因为之后的B比A更加的小pCurrentB = pCurrentB->next;break;}else{pPreA = pCurrentA; pCurrentA = pCurrentA->next;}}}
}
/*
核心思想一样但是，代码编写的不一样
*/
void findDifference2(LinkNode *&pHeadA, LinkNode *pHeadB){//1.环境的准备LinkNode *pPreA = pHeadA;LinkNode *pTemp = NULL;LinkNode *pCurrentA = pHeadA->next;LinkNode *pCurrentB = pHeadB->next;//2.外围的链表Bwhile ((pCurrentB != NULL) && (pCurrentA != NULL)){if (pCurrentB->data > pCurrentA->data){pPreA = pCurrentA;pCurrentA = pCurrentA->next;}else if(pCurrentB->data < pCurrentA->data){pCurrentB = pCurrentB->next;}else{//用于释放的内存pTemp = pCurrentA;//找到以后删除并释放内存pPreA->next = pCurrentA->next;pCurrentA = pCurrentA->next;free(pTemp);}}
}
void main(){LinkNode *pHeadA;LinkNode *pHeadB;printf("建立链表A:\n");pHeadA = Creat_SList();printf("\n建立链表B:\n");pHeadB =Creat_SList();printf("\n链表A的数据:\n");SqList_Print(pHeadA);printf("\n链表B的数据:\n");SqList_Print(pHeadB);
//	findDifference1(pHeadA, pHeadB);findDifference2(pHeadA, pHeadB);printf("删除A中不存在B中的元素后的链表数据:\n");SqList_Print(pHeadA);system("pause");
}

运行效果图：

这篇关于A-B差集的计算的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---