链表实现集合的交并差

第一版

#include <iostream> #include <string> using namespace std; //可以用于类似于检测卷面相似度 或者 答题卡答案的比对 struct LNode { char data; struct LNode *next; }; LNode* createList() { int n; LNode* head = new LNode; //在堆上生成，函数结束后才可以保存 LNode* pre = head; cout << "请输入字符串的字母个数" << endl; cin >> n; while(n<=0) { cout << "请输入一个大于零的数" << endl; cin >> n; } cout << "请输入字符串" << endl; for (int i = 0; i < n; i++) { LNode* p = new LNode; cin >> p->data; pre->next = p; pre = p; p->next = NULL; } return head; } //遍历单链表函数 void display(LNode* head) { LNode* p = head->next; while(p != NULL) { cout << p->data; p = p->next; cout << " "; } cout << endl; } //排序 void sort(LNode* head) { LNode* cur = NULL; LNode* tag = NULL; cur = head; while(cur != tag) { while(cur->next != tag) { if(cur->data > cur->next->data ) { char tmp = cur->data ; cur->data = cur->next->data ; cur->next->data = tmp; } cur = cur->next ; } tag = cur; cur = head ; } } //消除相同元素 void erase(LNode *head) { LNode *p = head->next; if(!p) return; while(p != NULL) { LNode *q = p; LNode *temp; while(q != NULL && q->next != NULL) { if (q->next->data == p->data) { temp = q->next; q->next = temp->next; delete temp; } else q=q->next; } p = p->next; } } //求交集 void JiaoJi(LNode* head1,LNode* head2) { LNode* p = head1->next; LNode* q = head2->next; while(p != NULL && q != NULL) { if(p->data == q->data ) { cout << p->data << " "; q = q->next; p = p->next; } else if(p->data < q->data) { p = p->next; } else if(p->data > q->data) { q = q->next; } } } //求并集 void BingJi(LNode* head1,LNode* head2) { LNode* p = head1->next; LNode* q = head2->next; while(p != NULL && q != NULL) { if(p->data < q->data) { cout << p->data << " "; p = p->next; } else if (p->data > q->data) { cout << q->data <<" "; q = q->next; } else if (p->data == q->data) { cout << p->data << " "; q = q->next; p = p->next; } } while(p != NULL) { cout << p->data << " "; p = p->next; } while(q != NULL) { cout << q->data <<" "; q = q->next; } } //求差集 void ChaJi(LNode* head1,LNode* head2) { LNode* p = head1->next; LNode* q = head2->next; while(p != NULL && q != NULL) { if(p->data < q->data) { cout << p->data << " "; p = p->next; } else if (p->data > q->data) { cout << q->data <<" "; q = q->next; } else if (p->data == q->data) { q = q->next; p = p->next; } } while(p != NULL) { cout << p->data << " "; p = p->next; } while(q != NULL) { cout << q->data <<" "; q = q->next; } } int main() { //LNode *La = createList(); //LNode *Lb = createList(); //sort(La); //sort(Lb); //erase(La); //erase(Lb); while(1) { LNode *La = createList(); LNode *Lb = createList(); sort(La); sort(Lb); erase(La); erase(Lb); int choice; cout << "——————————————————————" << endl; cout << endl; cout << " 请输入对应数字以执行操作：" << endl; cout << " 1.执行AB取并集操作" << endl; cout << " 2.执行AB取交集操作" << endl; cout << " 3.执行AB作差操作" << endl; cout << endl; cout << "——————————————————————" << endl; cin >> choice; switch(choice) { case 1: BingJi(La,Lb); system("pause"); getchar(); system("cls"); break; case 2: JiaoJi(La,Lb); system("pause"); getchar(); system("cls"); break; case 3: ChaJi(La,Lb); system("pause"); getchar(); system("cls"); break; } } } /* 测试内容： 1.两个链表均为空 2.其中一个链表为空 3.两个链表都为重复内容且内容相同 4.其中一个链表为重复内容另一个链表为空 5.其中一个链表为重复内容但另一个链表正常 */